Алгоритм растеризации тора/dougnut

Question

Я хочу растеризовать 2d-пончик в матрицу/пиксели (результат должен быть заполненным пончиком).

Ореол определяется r1, r2, x0, y0.

Я подозреваю, что оптимальным решением является некоторая функция алгоритма Bresenham в https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Любые идеи?

Answer 1

Да, можно наполнить пончик кругом Брешенема или алгоритмом средней точки.

Начать параллельные прогулки для внутренних и внешних кругов для 1-го квадранта. Постройте горизонтальные сегменты при изменении Y. Остановитесь на прогулку по внутреннему кругу, когда он достиг вершины и продолжит внешний.

Обратите внимание, что вы должны помнить, первый (самый большой) наружный X-значение, но последний (самый маленький) внутренний X-значение для той же Y.

Answer 2

Bresenham далека от оптимальной в эти дни ... что об эксплуататорской уравнения окружности:

(x-x0)^2 + (x-y0)^2 = r^2 

так пусть:

x0,y0 - center 
r1 - outer radius 
r2 - inner radius 
r1<=r2 
xs,ys - screen resolution 
scr[ys][xy] - screen matrix 

в C++ это выглядит следующим образом:

int x,y,xx,yy,rr,rr1=r1*r1,rr2=r2*r2; 
for (y=y0-r1;y<=y0+r1;y++)     // loop all y positions 
if ((y>=0)&&(y<ys))      // clip to screen 
    for (yy=y-y0,yy*=yy,x=x0-r1;x<=x0+r1;x++) // loop all x positions 
    if ((x>=0)&&(x<xs))      // clip to screen 
    { 
    xx=x-x0; xx*=xx; rr=xx+yy; 
    if ((rr>=rr2)&&(rr<=rr1))    // is in between radiuses? 
    scr[y][x]=fill_color; 
    } 

Вы можете избавиться от экрана обрезкой if заявления легко предварительно вычисления оценок для обеих петель, которые находятся внутри экрана ...

Для закрашенных окружностей такой подход, как правило, быстрее, чем Bresenham не говоря уже о легко параллелизуемо.