C++ Bresenham의 선 알고리즘이 호를 그리며 회전 함

Question

Bresenham의 선 알고리즘을 사용하여 호를 만드는 방법을 찾고 있습니다. 이 알고리즘은 완전한 원을 그리지 만, 원호를 그려야하고 (예 : 0도에서 Pi까지) 30도 회전해야합니까?

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{ 
     int x = 0; 
     int y = radius; 
     int delta = 2 - 2 * radius; 
     int error = 0; 

     while(y >= 0) { 
       //SetPixel(hdc,x0 + x, y0 + y,pencol); 
       SetPixel(hdc,x0 + x, y0 - y,pencol); 
       //SetPixel(hdc,x0 - x, y0 + y,pencol); 
       SetPixel(hdc,x0 - x, y0 - y,pencol); 
       error = 2 * (delta + y) - 1; 
       if(delta < 0 && error <= 0) { 
         ++x; 
         delta += 2 * x + 1; 
         continue; 
       } 
       error = 2 * (delta - x) - 1; 
       if(delta > 0 && error > 0) { 
         --y; 
         delta += 1 - 2 * y; 
         continue; 
       } 
       ++x; 
       delta += 2 * (x - y); 
       --y; 
     } 
} 

Answer 1

원형을 1/2로 (pi까지) 얻으려면 SetPixel 루틴 중 하나만 호출하십시오. 호를 30도 회전 시키려면 약간의 삼각 관계가 필요합니다. x/y 비율이 tan (30 degrees)과 동일해질 때까지 위의 루프를 실행할 수 있습니다. 그런 다음 비율이 중지 할 값에 도달 할 때까지 실제로 그리기를 시작하십시오. 가장 효율적인 방법은 아니지만 작동 할 것입니다. 더 나은 결과를 얻으려면 시작 4 변수를 미리 계산해야합니다. 위의 실행에서 값을 가져 와서 시작 값으로 연결하면 매우 효율적입니다.

Michael Abrash's Black Book에서 위의 알고리즘을 얻었습니까? 그렇지 않다면 나는 고속 원/원호 드로잉에 대한 참조의 두 번째 포인트로서이를 구글에 넣을 것이다.

글쎄, 아아, 찢어진 챕터가 거기에 포함되지 않은 타원. 여기에 내가 Abrash에서 주장 웹에서 발견 뭔가는 다음과 같습니다

/* One of Abrash's ellipse algorithms */ 

void draw_ellipse(int x, int y, int a, int b, int color) 
{ 
    int wx, wy; 
    int thresh; 
    int asq = a * a; 
    int bsq = b * b; 
    int xa, ya; 

    draw_pixel(x, y+b, color); 
    draw_pixel(x, y-b, color); 

    wx = 0; 
    wy = b; 
    xa = 0; 
    ya = asq * 2 * b; 
    thresh = asq/4 - asq * b; 

    for (;;) { 
     thresh += xa + bsq; 

     if (thresh >= 0) { 
      ya -= asq * 2; 
      thresh -= ya; 
      wy--; 
     } 

     xa += bsq * 2; 
     wx++; 

     if (xa >= ya) 
      break; 


     draw_pixel(x+wx, y-wy, color); 
     draw_pixel(x-wx, y-wy, color); 
     draw_pixel(x+wx, y+wy, color); 
     draw_pixel(x-wx, y+wy, color); 
    } 

    draw_pixel(x+a, y, color); 
    draw_pixel(x-a, y, color); 

    wx = a; 
    wy = 0; 
    xa = bsq * 2 * a; 

    ya = 0; 
    thresh = bsq/4 - bsq * a; 

    for (;;) { 
     thresh += ya + asq; 

     if (thresh >= 0) { 
      xa -= bsq * 2; 
      thresh = thresh - xa; 
      wx--; 
     } 

     ya += asq * 2; 
     wy++; 

     if (ya > xa) 
      break; 

     draw_pixel(x+wx, y-wy, color); 
     draw_pixel(x-wx, y-wy, color); 
     draw_pixel(x+wx, y+wy, color); 
     draw_pixel(x-wx, y+wy, color); 
    } 
} 

아이디어는 시간 X4에서 원의 8을 그린 후 그려진 다른 3/8을 얻을 플립 것. 그래도 여전히 직접 귀하의 질문에 대답하지 않습니다. 작업 중 ...

다시 위의 코드가 작동해야합니다. 시작 및 종료 조건을 신중하게 제어하면됩니다. y> = 0은 '호'길이를 끝낼 때 y가 될 필요가 있고 시작 값은 호의 시작으로 계산되어야합니다.

이것은 곧바로 앞으로하는 일이 아닙니다. 대신 부동 소수점 루틴을 사용하는 것이 더 쉬울 수도 있습니다. 수학은 훨씬 더 직설적이며 프로세서는 정수 루틴이 만들어 질 때보 다 프로세서를 더 잘 처리합니다.

Answer 2

확실히 Bresenham를 들어, 포인트와 아크 각도 시작 중심점을 설정할 수 in this SO post을 도입 빠른 단계 방법이 필요하지 않은 경우. 이미 알고리즘에 포함되어 있기 때문에 (원호 각도로) 정지 기준이 필요하지 않습니다. 속도를 빠르게하는 이유는 접선 및 방사형 이동 요소의 사전 계산이며 실제 루프에는 삼각 함수 호출이없고 곱하기, 더하기 및 빼기 만 있습니다.

는 AFAIK 방법의 세 가지 유형이있다 : Bresenham 등
A) 증분
B) 세분화 I 단계의 느린 예 걸릴 것이다 this
C) 단계 (또는 세그먼트) 방법

같은 방법 방법은 (속도가 중요한 경우이를 사용하지 않음) :

// I know the question is tagged c++, but the idea comes clear in javascript 
var start_angle = 0.5, end_angle = 1.1, r = 30; 
for(var i = start_angle; i < end_angle; i = i + 0.05) 
{ 
    drawpixel(50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (50,100) 
} 

속도 저하는 루프 (불필요) 반복 왜냐하면 죄에서 비롯됩니다. 이것은 위에서 언급 한대로 SO와 cos을 미리 계산하여 해결할 수 있습니다. 이는 엄청난 속도 향상 (상위 5 개 자바 스크립트 엔진에서 평균 12 배)을 의미합니다.

나는 다양한 서클 및 호 그리기 알고리즘의 완전 비교가 불가능한 speedtest을 만들었습니다. Bresenham은 빠르지 만 시작 및 중지 기준 논리를 추가해야 알 고를 약간 늦출 수 있습니다. Bresenham과 arc가 정말로 필요하다면, 나는 이것을위한 준비된 해결책이 없으며 아직 발견되지 않았습니다. 반드시 가능합니다.그건 그렇고, precalculated 삼각법을 사용하여 단계 방법은 너무 나쁜 성능 Bresenham에 비해 (자바 스크립트에서 적어도). C++로 테스트하고보고하십시오.