중간점 원 알고리즘

브레센햄 중간점 원 알고리즘으로 반지름 23의 원을 래스터라이징합니다.초록색 옥탄트만 계산되고8번 반사되어 나머지 7개의 옥탄트가 됩니다

브레센햄 알고리즘에 의해 그려진 반지름 23의 원

컴퓨터 그래픽스에서 중간점 원 알고리즘은 원의 래스터라이징에 필요한 점을 결정하기 위해 사용되는 알고리즘입니다.브레센햄의 원 알고리즘은 중간점 원 ^{[citation needed]}알고리즘에서 파생되었습니다.알고리즘은 원뿔 섹션으로 ^[1]일반화할 수 있습니다.

이 알고리즘은 Pitteway와^[2] Van Aken의 ^[3]작업과 관련이 있습니다.

요약

이 알고리즘은 각 기본 방향(0°, 90°, 180°, 270°)에서 시작하여 8개의 옥탄트를 동시에 그립니다.45°, 135°, 225°, 315°의 가장 가까운 배수에 도달하도록 양방향으로 확장합니다.y = x일 때 45°에 도달했기 때문에 멈출 위치를 결정할 수 있습니다.이러한 각도를 사용하는 이유는 위 그림에 나와 있습니다.x 가 증가해도 45° 가 될 때까지 x 값을 건너뛰거나 반복하지 않습니다.따라서 while loop 동안 x는 반복할 때마다 1씩 증가하며 y는 1씩 감소하는 경우가 있습니다.한 번의 반복으로 1을 초과하지 않습니다.탄젠트가 상승=실행되는 지점이므로 45°에서 변합니다.앞서거니 뒤서거니 뒤서거니.

문제의 두 번째 부분인 결정 인자는 훨씬 까다롭다.이것은 y를 감소시킬 시기를 결정합니다.첫 번째 픽셀의 반지름 아래로 가지 않기 때문에 보통 반복할 때마다 픽셀을 그린 후에 표시됩니다.연속함수에서 구에 대한 함수는 반지름이 z(또는 제3변수)에 의존하는 원에 대한 함수이기 때문에 이산(복셀) 구에 대한 알고리즘도 이 중간점 원 알고리즘에 의존한다는 것을 알 수 있습니다.그러나 구를 볼 때, 몇몇 인접한 원의 정수 반지름은 동일하지만, 같은 반구에서 자신과 인접한 정확한 원을 가질 것으로 예상되지 않는다.대신, 같은 반지름을 가진 원에는 곡선이 중심에 약간 가깝게 들어오거나 더 길게 뻗을 수 있도록 다른 행렬식이 필요합니다.

중간점 원 알고리즘으로 그린 150개의 동심원
왼쪽에는 모든 원이 검은색으로 그려져 있습니다.
오른쪽에는 빨간색, 검은색, 파란색이 함께 사용되어 원의 동심을 나타냅니다.

알고리즘.

알고리즘의 목적은 $x^{2}+y^{2}=r^{2}$ $x^{2}+y^{2}=r^{2}$ 2 + $x^{2}+y^{2}=r^{2}$ 2 $x^{2}+y^{2}=r^{2}$ $x^{2}+y^{2}=r^{2}$ 2 {\ $displaystyle$ x $^{2}+y^{2$ }에 근사하는 것입니다. $}=r^{$ 2 $x^{2}+y^{2}=r^{2}$ }}: 픽셀을 사용합니다. 평신도 용어로 말하면 모든 픽셀은 중심에서 거의 같은 거리에 있어야 합니다.각 단계에서 $x^{2}+y^{2}\leq r^{2}$ $x^{2}+y^{2}\leq r^{2}$ $x^{2}+y^{2}\leq r^{2}$ $x^{2}+y^{2}\leq r^{2}$ $x^{2}+y^{2}\leq r^{2}$ ${\$ x $^{$ 2} + $y^{2$ }를 $x^{2}+y^{2}\leq r^{2}$ 하는 인접 화소를 선택함으로써 경로를 확장한다. $}\leq r^{$ 2 $x^{2}+y^{2}\leq r^{2}$ }}은 $x^{2}+y^{2}$ 는) $x^{2}+y^{2}$ $x2$ + $x^{2}+y^{2}$ {{ $displaystyle x^{2$ } + $x^{2}+y^{2}$ y $^{$ 2}}입니다.후보자 픽셀이 인접해 있기 때문에 후자 식을 계산하는 연산은 간단하며 비트 이동과 추가만 필요합니다.단, 비트 시프트를 이해하기 위해 단순화할 수 있습니다.이진수의 왼쪽 비트 시프트는 2를 곱하는 것과 같습니다.Ergo는 반지름의 왼쪽 비트 시프트가 반지름 곱하기 2로 정의된 직경만 생성합니다.

이 알고리즘은 원 방정식으로 시작합니다.간단하게 하기 위해 원의 중심이 ( $(0,0)$ $)$ $displaystyle (0,0$ 이라고 가정합니다.첫 번째 8진수만 고려하여 ( $)$ { $displaystyle (r,0)}$ 지점에서 $(r,0)$ 시작하여 시계 반대 방향으로 45의 각도에 도달하는 곡선을 그립니다.

여기서 빠른 방향(값의 증가가 큰 기본 벡터)은 $\displaystyle$ y 방향입니다 $y$ .알고리즘은 항상 양의 $y방향$ )으로 $y$ 한 걸음씩 이동하며 느린 방향( $x$ 의 $x방향)$ 으로 $x$ 한 걸음씩 이동하기도 합니다.

원 방정식 x $x^{2}+y^{2}-r^{2}=0$ + $x^{2}+y^{2}-r^{2}=0$ 2 - $x^{2}+y^{2}-r^{2}=0$ 2 $=$ {\ $displaystyle$ x $^{2}+y^{2}-r^{2$ }= $0$ 에서 r $r^{2}$ {\ $displaystyle$ r $^{2}}$ 은 $r^{2}$ 초기화 $r^{2}$ 에 한 번만 계산된다.

원의 점이 해당 점에 대한 벡터 좌표의 연속이라고 가정합니다(통상적인 기준).포인트는 가 그려진 순서에 따라 번호가 매겨지며, $=$ 1 { $displaystyle$ n=1}은 $n=1$ 첫 번째 $(r,0)$ $, 0$ )에 할당됩니다 $(r,0)$

각 점에 대해 다음 사항이 유지됩니다.

{displaystyle}x_{n}^{2}+y_{n}^2}=r^{2}\end{aligned}

이것은 다음과 같이 재배열할 수 있습니다.

{argined}x_{n2}=r^{2}-y_{n}^{2}\end{aligned}

마찬가지로 다음 사항도 마찬가지입니다.

{argined}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}

첫 번째 옥탄트의 경우 다음 포인트는 항상 마지막 옥탄트보다 최소 1픽셀 높아지므로(단, 연속성을 유지하기 위해 최대 1픽셀 높아지므로) 다음과 같은 사실이 있습니다.

{aligned}y_{n+1}^{2}&=(y_{n}+1)^2}\\&=y_{n}^2}+2y_{n}+1\end{aligned}

{argined}x_{n+1}^{2}=r^{2}-y_{n}^2}-2y_{n}-1\end{aligned}

$x_{n}^{2}=r^{2}-y_{n}^{2}$ x $x_{n}^{2}=r^{2}-y_{n}^{2}$ 2 $=$ $x_{n}^{2}=r^{2}-y_{n}^{2}$ 2 - $x_{n}^{2}=r^{2}-y_{n}^{2}$ n $x_{n}^{2}=r^{2}-y_{n}^{2}$ {\ $display style$ x_ ${n}^{$ 2}= $r^{2}-y_{n}^{$ 2 $x_{n}^{2}=r^{2}-y_{n}^{2}$ 을(를) 대입하여 다음 점포를 재귀적 점으로 재작업합니다.

{displaystyle}x_{n+1}^2}=x_{n}^2}-2y_{n}-1\end{aligned}

원의 연속성과 두 축의 최대값이 같기 때문에, 원은 시퀀스를 진행할 때 x점을 건너뛰지 않습니다.보통은 같은 x좌표 위에 유지되며 때로는 1씩 전진하기도 합니다.

그런 다음 중간점 좌표를 추가하여 결과 좌표를 변환합니다.이러한 정수를 자주 추가해도 성능은 크게 제한되지 않습니다. 이러한 제곱(루트) 계산은 내부 루프에서 차례로 발생할 수 있기 때문입니다.다시 변환된 원 방정식의 0이 오차항으로 대체된다.

오차항의 초기화는 시작 시 of 픽셀의 오프셋에서 도출됩니다.수직선과의 교차점까지는 오차항 중 누적값 $r$ r이 되므로 이 값은 초기화에 사용됩니다.

원 방정식, 삼각 표현식 및 제곱근의 잦은 제곱 계산은 모든 것을 단일 단계로 분해하고 이전 반복에서 2차 항의 재귀 계산을 사용함으로써 다시 피할 수 있습니다.

정수 기반 산술이 있는 변종

브레센햄의 선 알고리즘과 마찬가지로 이 알고리즘은 정수 기반 수학에 최적화될 수 있습니다.대칭성이 있기 때문에 하나의 옥탄트 화소만을 계산하는 알고리즘을 찾을 수 있으면 화소를 반사시켜 전체 원을 얻을 수 있다.

우선 반지름 오차를 원의 정확한 표현과 각 픽셀의 중심점(또는 픽셀의 다른 임의의 수학적 점) 사이의 차이로 정의합니다(모든 픽셀에서 일관성이 있는 한). $(x_{i},y_{i})$ 이 ( $(x_{i},y_{i})$ $(x_{i},y_{i})$ , $(x_{i},y_{i})$ i $(x_{i},y_{i})$ ) { $displaystyle ( x _$ { i , y _ { i $(x_{i},y_{i})$ )인 픽셀의 경우 반지름 오차는 다음과 같이 정의됩니다.

\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert}

명확하게 하기 위해 원점에서 원의 이 공식을 도출하지만 알고리즘은 모든 위치에 대해 수정할 수 있습니다.양의 X 축에 있는 점 $(r,0)$ , $(r,0)$ ) { $displaystyle (r,0)}$ 부터 $(r,0)$ 시작하는 것이 유용합니다.반경은 픽셀의 정수이기 때문에 반경의 오차는 0이 됩니다.

RE(x_{i},y_{i}=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0

첫 번째 반시계 방향의 양의 8진수에서 시작되므로 Y $y_{i+1}=y_{i}+1$ 으로 가장 많이 이동하므로 y $y_{i+1}=y_{i}+1$ i + $y_{i+1}=y_{i}+1$ $y_{i+1}=y_{i}+1$ $y_{i+1}=y_{i}+1$ i + $y_{i+1}=y_{i}+1$ { $displaystyle y_{i+1$ } $= y_{i}+1$ }인 $y_{i+1}=y_{i}+1$ 이 분명합니다.또한 이 8진수에만 관계되므로 X 값에는 이전 반복과 동일하게 유지하거나 1씩 감소하는 두 가지 옵션만 있습니다.다음 조건이 충족되는지 여부를 결정하는 결정 변수를 생성할 수 있습니다.

({displaystyle RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)}

이 부등식이 유지되면 플롯 $(x$ - 1, $(x_{i}-1,y_{i}+1)$ $(x_{i}-1,y_{i}+1)$ + $(x_{i}-1,y_{i}+1)$ 1) $(x_{i}-1,y_{i}+1)$ { $displaystyle$ ( $x_{i}-1$ , $(x_{i},y_{i}+1)$ ${i}+1$ 그렇지 않으면 플롯 $(x_{i},y_{i}+1)$ i, $(x_{i},y_{i}+1)$ + $(x_{i},y_{i}+1)$ ) $(x_{i},y_{i}+1)$ { $displaystyle (x_{i$ }, $y_{i$ 1)}을 플롯합니다.그렇다면, 이 불평등이 지속될지를 어떻게 판단해야 할까요?radius error의 정의부터 시작합니다.

{\displaystyle\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^2}-r^{2}\vert & <\left\vert x_{i}^2}+(y_{i}+1)^{2}-r^{\vert left (좌회전)\vert } \좌회전

절대값 함수는 도움이 되지 않으므로 정사각형이 항상 양수이므로 양쪽을 제곱하십시오.

{\displaystyle{\begin{정렬}[(x_{나는}{2}-2x_{나는}+1)+(y_{나는}^{2}+2y_{나는}+1)-r^{2}^\right]^{2}&, <, \left[x_{나는}{2}+(y_{나는}^{2}+2y_{나는}+1)-r^{2}^\right]^ᆰ\\\left[(x_{나는}{2}+y_{나는}{2}^-r^^{2}+2y_{나는}+1)+(1-2x_{나는})\right]^{2}&,<>\left[x_{나는}{2}+y_{나는}{2}^-r^^{2}+2y_{나는}+1\right]^ᆲ\\\left(x_{나는}{2}+y_{나는}{2}^-r^^{2}+2y_{나는}+1\right)^ᆳ+2(1-2x_{나는})()_{나는}^{2}+y_{나는}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left [x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^2}\\2(1-2x_{i}+y_{i}^2}^2}+y_{i}+1-1)^{2}&<0\\\end{aligned}}

$(1-2x_{i})<0$ > 0 $(1-2x_{i})<0$ 、 $(1-2x_{i})<0$ ( 1 - 2 x i $(1-2x_{i})<0$ \ $displaystyle$ ( 1 - $2x$ _ { $i$ }< $0$ ）。따라서 나눗셈은 다음과 같습니다.

\ displaystyle { arigned } 2 \ left [ ( x _ { i }^{2} - r^{2} + ( 2y _ { i } + \ right ) + ( 1 - 2x _ { i } )&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}\right]+X_{\text{Change}}&>0\\end{aligned}}

따라서 결정기준은 부동소수점 연산을 사용하는 것에서 단순한 정수 덧셈, 뺄셈 및 비트 시프트(2연산을 곱한 경우)로 변경됩니다.2 $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ ( $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ E $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ + $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ ) + $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ > $2(RE+Y_{\text{Change}})+X_{\text{Change}}>0$ ( \ $displaystyle$ 2 $( RE$ + Y _ { \ $text$ { $Change$ } ) + X $_$ { \ $text$ { $Change$ } > $0$ )의 경우 X 값은 감소합니다.2 $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ ( $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ E $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ + $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ ) + $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ 0 ( \ $displaystyle$ 2 ( $RE$ + Y $_$ { \ $text$ { Change } ) + $X _$ { \ $text$ { Change } \ $leq$ 0 $2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0$ )의 경우 동일한 X 값을 유지합니다.이 점들을 모든 8진수에 반영하면 완전한 원이 됩니다.

이전 단계의 값에서 이 결정 공식 값 사이의 델타만 계산하여 계산을 줄일 수 있습니다.만약 E을 우리는 E을 부여함으로써{E\displaystyle}3− 공식의(x0, y0))(r, 0){\displaystyle(x_{0}일 경우 ,y_{0})=(r,0)}를 지급하는 것 초기 값 2r{3-2r\displaystyle}처럼 각 단계 다음 위와 같이에서;0{\displaystyle E>0}우리가 E은+2(5− 2x+2이 어두워져서){\displaystyle E. 그것 E를 업데이트 시작=E+2( $5-2x+2y)}($ 및 감소 X), 그렇지 $E=E+2(3+2y)$ E $E=E+2(3+2y)$ $E=E+2(3+2y)$ + $E=E+2(3+2y)$ ( $E=E+2(3+2y)$ + $E=E+2(3+2y)$ y $){displaystyle$ E $=E+2 (3+2y)}$ 는 $E=E+2(3+2y)$ 평소대로 Y를 증가시킵니다.

불완전한 8진수 그리기

위의 구현에서는 항상 완전한 8진수 또는 원만 그립니다. $(\displaystyle \alpha)$ 에서 $\alpha$ $(\displaystyle \beta$ 로 특정 호만 그리려면 알고리즘이 먼저 이들 끝점의 $(\displaystyle$ x $)$ $y$ y(\ $displaystyle$ y $)$ 좌표를 $y$ 계산해야 합니다. 여기서 삼각근 또는 제곱근 계산에 의존해야 합니다(방법 참조). 제곱근 계산)을 제공합니다.그런 다음 브레센햄 알고리즘이 전체 8진수 또는 원에 걸쳐 실행되며 원하는 간격에 해당하는 경우에만 픽셀을 설정합니다.이 아크를 종료하면 알고리즘이 조기에 종료될 수 있습니다.

각도가 기울기로 지정된 경우 삼각법이나 제곱근은 필요하지 않습니다. y $y/x$ / $y/x$ { $displaystyle$ y $/x}$ 가 $y/x$ 원하는 기울기 사이에 있는지 $y/x$ 만 하면 됩니다.

일반화

또한 동일한 개념을 사용하여 포물선,^[4] 타원 또는 기타 2차원 곡선을 래스터화할 수도 있습니다.

레퍼런스

^ Donald Hearn; M. Pauline Baker (1994). Computer graphics. Prentice-Hall. ISBN 978-0-13-161530-4.
^ 피트웨이, M.L.V., "디지털 플로터로 타원 또는 하이퍼볼라를 그리기 위한 알고리즘", 컴퓨터 J., 1967년 11월 10일, 페이지 282-289
^ Van Aken, J.R., "효율적인 타원 그리기 알고리즘", CG&A, 4(9), 1984년 9월, 페이지 24-35
^ Zingl, Alois (December 2014). "The Beauty of Bresenham's Algorithm: A simple implementation to plot lines, circles, ellipses and Bézier curves". easy.Filter. Alois Zingl. Retrieved 16 February 2017.

외부 링크

동그라미 그리기 - 동그라미 그리기 기사로서 단순한 스킴에서 효율적인 스킴으로 이어지는 것
여러 프로그래밍 언어의 중간점 원 알고리즘

[HearnBaker1994-1] Donald Hearn; M. Pauline Baker (1994). Computer graphics. Prentice-Hall. ISBN 978-0-13-161530-4.

[2] 피트웨이, M.L.V., "디지털 플로터로 타원 또는 하이퍼볼라를 그리기 위한 알고리즘", 컴퓨터 J., 1967년 11월 10일, 페이지 282-289

[3] Van Aken, J.R., "효율적인 타원 그리기 알고리즘", CG&A, 4(9), 1984년 9월, 페이지 24-35

[4] Zingl, Alois (December 2014). "The Beauty of Bresenham's Algorithm: A simple implementation to plot lines, circles, ellipses and Bézier curves". easy.Filter. Alois Zingl. Retrieved 16 February 2017.

[1]

[2]

[3]

[4]

Search