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

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

Пончик определяется r1, r2, x0, y0.

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

Есть идеи?

2 ответа

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

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

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

  2. Бресенхэм далек от оптимума в эти дни … как насчет использования уравнения окружности:

    (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, не говоря уже о легко параллелизируемом.