C++의 중심에서 채워진 원을 그립니다.

Question

원 중심에서 한 픽셀 씩 선을 따라 (예 : 시계 방향으로) 그립니다. 그러나 픽셀을 다시 그리지 마십시오 (느림).

이것은 매 턴마다 한 번만 업데이트되는 "레이더"와 같다고 상상해보십시오.

모든 채워진 픽셀 (최대 이전 선 점)과 GPU 또는 하이 레벨 라이브러리 (DrawPoint (x, y) 함수로 그리기)의 배열을 저장할 RAM이 없습니다.

void DrawLineFromCenterXYToAngle(int centerX, int centerY, float angle) 
{ 
.... instead of angle it is possible to find points of the circle and iterate it 
.... find line points by Bresenham's line algorithm 
{ 
    DrawPoint(int x, int y); 
} 
} 

void DrawPoint(int x, int y) 
{ 
    PixelDraw_Slow(x,y)=GetColor_VerySlow(x,y); 
} 

가 지금은 각도를 반복하고 매우 느리게 때문에 여러 번 다시 그릴 중앙에 픽셀로, 원을 가지고 :

나는 라인과 포인트를 그릴 기능을 가지고 있습니다. 그리고 최적화가 필요합니다.

빠른 속도를 내면 모양이 완벽한 원이 아닐 수도 있습니다.

Answer 1

원에 Bresenham 그리기 알고리즘이 있습니다.

Example with code

int r = 200, ymax, x, y, yp, xp, d; 
ymax = r/sqrt(2); 
x = r; /* start at the bottom of the first octant */ 
/* d measures whether the midpoint of two pixel locations 
is inside or outside the ideal circle. positive means outside */ 
d = -1*r; /* to be precise, this should be r^2 - (r - 0.5)^2 */ 
xp = r; yp = -1; /* these hold the old values across iterations */ 
for(y=0; y<=ymax; y++) { 
    plot_8_ways(x,y); 
    if (d > 0) { /* midpoint is outside circle, go NW */ 
    x--; 
    d += (2*yp - 2*xp + 3); 
    } 
    else { /* midpoint is inside circle, go N */ 
    d += (2*yp + 1); 
    } 
    yp = y; 
    xp = x; 
} 

Answer 2

모두 채워 화소 (최대 이전 광고 점)없이 GPU 또는 하이 - 레벨 라이브러리 어레이를 보유 할 RAM 없다 (기능 DrawPoint (x, y)에 의해 드로잉) .

점의 한 줄을 저장할 수 있으면 효율적으로 표현하면 모든 채워진 픽셀을 추적 할 수있는 충분한 메모리가 있습니다.

레이더 스위프가 12시 또는 6시 위치에서 시작한다고 가정하면 (시계 방향 또는 반 시계 방향으로 스윕하는 것은 중요하지 않음) 원을 렌더링하는 동안 언제든지 수직 선은 채워진 픽셀 블록을 한 번만 교차합니다 (즉 한 번 입력하고 한 번 종료). 따라서 픽셀의 각 열에 대해 수직 최소 및 최대 채우기 y 좌표를 저장하면됩니다. 3시 또는 9시 위치에서 시작하는 경우 각 행에 대해 최소 및 최대 x를 저장할 수 있습니다.

당신은 배열의 부부와 함께 할 단지 수 있습니다

int minY[X_RANGE]; 
int maxY[X_RANGE]; 

X_RANGE 픽셀의 최대 열 수 있습니다. 서클 경계 상자의 왼쪽 X를 기준으로 오프셋 할 수 있기 때문에 전체 화면이 아니라 서클 크기만큼만 필요합니다. 마찬가지로, Y_RANGE는 최대 행 수입니다. 당신은 픽셀을 렌더링 할 때 이미 배열 확인하여 렌더링 된 경우 바로 확인, 그리고

void InitColumnArrays() 
{ 
    for(int x = 0; x < X_RANGE; x++) 
    { 
     minY[x] = Y_RANGE - 1; 
     maxY[x] = 0; 
    } 
} 

:

void DrawPointCheckingRanges(int x, int y) 
{ 
    // TODO: range check values 

    // check if point has already been drawn and draw it and extend ranges if not: 
    if((y < minY[x]) || (y > maxY[x])) 
    { 
     DrawPoint(x + offsetX, y + offsetX); 
     if(y < minY[x]) 
      minY[x] = y; 
     if(y > maxY[x]) 
      maxY[x] = y; 
    } 
} 

당신이 렌더링을 시작하면

, 빈 열을 나타내는 배열을 초기화

offsetX 및 offsetY는 위에서 설명한 옵 션 옵 션입니다.

다른 답변에서 Bresenham 원 그리기 알고리즘과 함께 사용하면 효율적으로 줄의 끝점을 줄 수 있습니다.

위 코드는 DrawPoint가 이러한 범위 검사 및 배열 읽기 및 쓰기와 비교하여 느린 것으로 가정합니다.