Реферат: Трёхмерная компьютерная графика

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пиксела желательно использовать только знак ошибки, а не её величину.

2.6 Пересечение окружности и сетки растра

При D < 0 диагональная точка ( x_i + 1, y_i - 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой ситуации следует выбрать либо пиксел ( x_i + 1, y_i )т. е. m_H, либо пиксел ( x_i + 1, y_i - 1), т. е. m_D . Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний отокружности до пикселов в горизонтальном и диагональном направлениях:

При d < 0 расстояние от окружности до диагонального пиксела

(m_D )больше, чем до горизонтального (m_H ). Напротив, если d > 0, расстояние до горизонтального пиксела (m_H )больше. Таким образом,

при d < 0 выбираем m_H ( x_i + 1, у_i )

при d > 0 выбираем m_D ( x_i + 1, у_i – 1 )

При d = 0, когда расстояния от окружности до обоих пикселоводинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины d, можно сократить, если заметить, что в случае 1

так как диагональный пиксел ( x_i + 1, у_i – 1 ) всегда лежит внутри окружности, а горизонтальный ( x_i + 1, у_i ) - вне ее. Таким образом, d можно вычислить по формуле

Дополнение до полного квадрата члена ( y_i )² с помощью добавления и вычитания - 2у_i + 1 дает

В квадратных скобках стоит по определению D_i , и его подстановка

d = 2(D_i + y_i ) – 1

существенно упрощает выражение.

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран горизонтальный пиксел ( x_i + 1, у_i ), так как у является монотонно убывающей функцией. Проверка компонент d показывает, что

поскольку в случае 2 горизонтальный ( x_i + 1, у_i ) и диагональный ( x_i + 1, у_i – 1 ) пикселы лежат внутри окружности. Следовательно, d < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел ( x_i + 1, у_i ).

Если D_i > 0, то диагональная точка ( x_i + 1, у_i – 1 ) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел ( x_i + 1, у_i – 1 ), т. е. m_D , либо ( x_i , у_i – 1 ), т. е. m_V . Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального m_D и вертикального m_V пикселов, т. е.

При d^\ < 0 расстояние от окружности до вертикального пиксела ( x_i , у_i – 1 ) больше и следует выбрать диагональный шаг m_D , к пикселу ( x_i + 1, у_i – 1 ). Напротив, в случае d^\ > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу ( x_i , у_i – 1 ). Таким образом,

при d£0 выбираем m_D в ( x_i + 1, у_i – 1 )

при d< 0 выбираем m_V в ( x_i , у_i – 1 )

Здесь в случае d = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент d^\ показывает, что