Bresenham 브레센함 알고리듬 : 원 그리기

 

 

비트맵 형식으로 원을 그리는 알고리듬, 원 중심점에서 실제의 반지름에 해당하는 지점에서 가장 가까운 픽셀을 찍는 방식이다. 제곱근이나 삼각함수 없이 정수 연산으로 빠르게 처리할 수 있다.

찾으려는 다음 픽셀은 예를 들어, 시계의 12시 지점에서 오른쪽으로 1픽셀 이동 또는 오른쪽 1픽셀이동 아래로 1픽셀 이동한 점이 된다. 쉽게 생각하면, 시계 12시 지점에서 시계방향으로 원을 그리는데 있어 연필의 진행방향이 오른쪽 또는 오른쪽 아래가 된다는 것. 프로그램 코딩상에서 실제로 식에 의해 그리게 되면 중심각 45도가 되는 지점까지의 원호를 그리게 된다.

 

>>>사용되는 수식 정의<<<

 

원 방정식 :  x²+ y²- r²= 0 (중심점 x, y 반지름 r)

 

해당 픽셀 : P_k = (x_k, y_k)

오차     : E_k = x_k² + y_k² - r²

 

P_k 다음 진행 지점 픽셀 : x축 1픽셀 더한 지점 : x_k + 1, y축 1픽셀 뺀 지점 y_k - 1

P1 = (x_k + 1 , y_k)

P2 = (x_k + 1 , y_k - 1)

 

오차  :  E1 = (x_k + 1)² + y_k² - r²   

  E2 ₌ (x_k + 1)² + (y_k – 1)² - r²  

 

(단 E1 > E2)

 

여기서 오차가 0일 때 실제 원 중심점에서 반지름에 해당하는 정확한 지점이 되는데 오차가 양수 일 때는 반지름 보다 큰 지점이 되고 음수일 때는 그 반대가 된다.  

 

두 개의 다음 진행 픽셀 중에 오차가 작은 픽셀을 선택한다. 하지만 두 오차의 값이 양수 음수 일 경우가 생기게 되는데 두 오차가 양수일 때는 항상E2 가 E1 보다 작으므로 P2 픽셀을 선택한다. 다시 말해 정확한 반지름 위치에 더 접근한 픽셀이다.

그리고 둘 다 음수일 때는 P1을 선택한다. 다시 말해 정확한 반지름 위치보다 안쪽으로 들어오게 되므로 음수의 절대치가 큰 쪽을 선택한다.

그러나 E1 이 양수 E2가 음수일 경우(오른쪽 다음 픽셀은 원의 바깥쪽 오른쪽 아래 픽셀은 원의 안쪽에 위치할 때) 에는 두 오차의 절대치 값이 작은 쪽을 선택하면 된다.

그리고 E1 이 음수 E2 가 양수일 수는 없다.

      

E1 > 0, E2  > 0 : P2 선택

E1 < 0, E2  < 0 : P1 선택

E1 > 0 , E2 < 0 : P1, P2 중에 절대치가 작은 쪽을 선택, 절대치가 같은 경우 어느 쪽을 선택해도 상관없다.

 

결론적으로 수식으로 정의 하면, 두 오차의 합이 음수일 때 둘 다 음수일 경우에는 물론 P1을 선택하게 되고 E1양수, E2음수 일 때 E2의 절대치가 크다는 사실이 되므로 오차가 작은 P1을 선택해야 된다.

또한 두 오차의 합이 양수일 때 P2 선택, E1양수, E2음수 일 때 E1의 절대치가 크다는 사실이 되므로 오차가 작은 P2를 선택해야 된다.

마지막으로 두 오차의 합이 0일 때는 두 오차의 절대치가 같다는 경우이므로 어느 쪽을 선택해도 상관없다.  

 

E1 + E2 < 0 : P1 선택

E1 + E2 > 0 : P2 선택

E1 + E2 = 0 : 둘 중 아무거나 선택(자바 코딩상에서는 P2 선택)

 

판별식 :

F(k) = E1 + E2

       = (x_k + 1)² + y_k² - r² + (x_k + 1)² + (y_k – 1)² - r²     

       = 2(x_k² + 2x_k + 1) + y_k² + (y_k² - 2y_k + 1) - 2r²

       = 2x_k² + 4x_k + 2 + 2y_k² - 2y_k + 1 - 2r²

       = 2x_k² + 2y_k² + 4x_k - 2y_k - 2r² + 3

       = 2(x_k² + y_k² - r²) + 4x_k - 2y_k + 3

       = 2E_k + 4x_k - 2y_k + 3

 

 

P의 최초 시작점(초기화, 12시) : x_k = 0, y_k = r, p = -2r + 3

F(0) = 2E_k + 4x_k - 2y_k + 3

       = -2y_k + 3

       = -2r + 3

 

 

다음 진행 픽셀 수식:

 

P1 경우 : P1 = (X_k + 1, y_k)

     F(k + 1) = 2E1 + 4(x_k + 1) - 2y_k + 3 

             = 2(x_k² + 2x_k + 1 + y_k² - r²) + 4x_k + 4 - 2y_k + 3

             = 2x_k² + 2y_k² - 2r² + 2 + 4x_k + 4x_k + 4 - 2y_k + 3

             = 2(x_k² + y_k² - r²) + 4x_k - 2y_k + 3 + 4x_k + 6

= 2E_k + 4x_k - 2y_k + 3 + 4x_k + 6

             = F(k) + 4x_k + 6

 

P2 경우 : P2 = (X_k + 1, y_k – 1)

F(k + 1) = 2E2 + 4(x_k + 1) – 2(y_k – 1) + 3 

             = 2(x_k² + 2x_k + 1 + y_k² - 2y_k + 1 - r²) + 4x_k + 4 - 2y_k + 2 + 3

             = 2x_k² + 2y_k² - 2r² + 4x_k + 2 - 4y_k + 2  + 4x_k + 4 - 2y_k + 2 + 3

             = 2(x_k² + y_k² - r²) + 4x_k - 2y_k + 3 + 4x_k - 4y_k + 10

= F(k) + 4x_k - 4y_k + 10

= F(k) + 4(x_k - y_k) + 10

 

 

 

 

자바 코드 : 안드로이드 SurfaceHoler 를 사용해 그리는 메서드

* 주의점은 drawRect()로 그릴 때 Y축의 개념은 흔히 쓰는 그래프상의 위치와     

  상반된다는 것. 

   *  8부분으로 나누어 서로 상반되게 x축과 y축을 지정해서 그리게 된다.

 *  기본적으로 x축 값을 1 픽셀씩 증가시키면서 위 판별식을 이용해서 Y축 값을     

감소시키는 때를 선택하는 알고리듬이 된다.

 

//Canvas.drawRect() 를 이용한 원주 그리기, Bresenham 알고리즘

private void circle(Canvas canvas, int x, int y, int radius){

if(radius <= 0) return; //반지름 0 이하일때 실행 안함

             

//값 초기화

     int xK = 0; //x축 해당값 초기화

     int yK = radius;//y축 해당값 반지름 값으로 초기화  

     int pK = 3 - (radius + radius); //3 - 2 * r, 픽셀 초기 시작지점

 

     do{

  //북

          paint.setColor(Color.LTGRAY);

//동, 회색          

canvas.drawRect(x + xK, y - yK, x + xK + 4, y - yK + 4, paint);

          paint.setColor(Color.BLUE);

//서, 청색

          canvas.drawRect(x - xK, y - yK, x - xK + 4, y - yK + 4, paint); 

                      

          //남

          paint.setColor(Color.WHITE);

//동, 흰색

          canvas.drawRect(x + xK, y + yK, x + xK + 4, y + yK + 4, paint);

          paint.setColor(Color.RED);

//서, 적색

          canvas.drawRect(x - xK, y + yK, x - xK + 4, y + yK + 4, paint);

                      

          //동

          paint.setColor(Color.CYAN);

//북, 하늘색

          canvas.drawRect(x + yK, y - xK, x + yK + 4, y - xK + 4, paint);

          paint.setColor(Color.MAGENTA);

//남, 분홍색

          canvas.drawRect(x + yK, y + xK, x + yK + 4, y + xK + 4, paint);

 

          //서

          paint.setColor(Color.YELLOW);

//북

          anvas.drawRect(x - yK, y - xK, x - yK + 4, y - xK + 4, paint);

          paint.setColor(Color.GREEN);

//남

          canvas.drawRect(x - yK, y + xK, x - yK + 4, y + xK + 4, paint);

 

          xK++; // x축 다음 픽셀 1씩 증가

                      

          //P1 선택 : pK + xK * 4 + 6 판별식

          if(pK < 0) pK += (xK << 2) + 6;  //판별할 pK 값 갱신

                    /*

                     * 쉬프트 연산자 << : xK << n --> xK * 2의 n 승  

                     * >> : xK >> n --> xK / 2^n(승), 쉬프트연산자가 '*',     

* '/' 연산속도 보다 빠르다.

                     */

                      

          //P2선택 : pK + (xK - yK) * 4 + 10 판별식, yK 감소                 

            

          else {

          --yK; // 다음 픽셀 y축 1씩 감소

               pK += ((xK - yK) << 2) + 10; //판별할 pK 값 갱신

     }

}while(xK <= yK); //x축 증가치가 y축 감소치의 합이 반지름과 같을때 까지, 45도

}