Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР. 1 отображение просранства пользователя и машинного носителя 4
![]()
|
2.2 Формирование дуги окружности.Данный алгоритм обеспечивает формирование дуги окружности с центром в начале координат, расположенной в первом квадранте (Рис. Формирование дуги окружности.-11). Используя зеркальное отображение относительно координатной оси, можно на основании дуги, сформированной для первого квадранта, получить изображение окружности во всех оспальных квадрантах. ![]() Рис. Формирование дуги окружности.‑11 При формировании дуги окружности пиксел, который должен быть использован в качестве следующей точки формируемой окружности, выбирается из трех возможных претендентов, и его координаты рассчитываются за счет приращения координат предыдущей найденной точки. Тремя точками-претендентами являются горизонтальная, диагональная и вертикальная точки (), из которых выбирается та, которая ближе всего находится от расчетной окружности. На рис.2.2-2 приведены последняя найденная точка Тi с координатами xi, yi , горизонтальный претендент ПH с координатами xi+1, yi , диагональный претендент ПD с координатами xi+1, yi -1 и вертикальный претендент ПV с координатами xi, yi-1. Кроме того, на этом рисунке показано пять возможных положений расчетной окружности по отношению к последней наёденной точке и трем претендентам. В качестве критерия выбора одного из претендентов используется квадрат расстояния до окружности mH, mD, mv, ![]() Рис. Формирование дуги окружности.‑12 соответственно, претендентов ПH, ПD, и ПV. Значения этих квадратов расстояний, которые называются отклонениями, рассчитываются по следующим формулам: mH =|( xi+1)2 +yi2 –R2|; mD =|( xi+1)2 +(yi -1) 2-R2|; mV =|xi2 +(yi2 -1)-R2|, где через R обозначен радиус окружности Принятие решения о выборе следующей точки формируемой дуги из трех претендентов осуществляется следующим образом. Введем базовую погрешность i для текущей i-ой точки, определяемую через ее координаты как: i( xi+1)2 +(yi -1) 2-R2. Логика выбора одного из трех претендентов в качестве очередной точки формируемой дуги представлена на следующем рисунке(Рис. Формирование дуги окружности.-13). ![]() Рис. Формирование дуги окружности.‑13 На рисунке приняты следующие обозначения: - базовое отклонение; - разность расстояний горизонтального и диагонального претендентов от окружности; - разность расстояний диагонального и вертикального претендентов до окружности. Найдем компактные аналитические выражения для расчета и 2. Разность расстояний горизонтального и диагонального претендентов до окружности рассчитывается только в случае, когда выполняется условие: 0 , (2.2-1) при выполнении которого может иметь место расчетное положение окружности 1, 2, 5. В этом случае формируется за счет вычитания из абсолютного значения расстояния горизонтального претендента до окружности h1 абсолютного значения расстояния диагонального претендента до окружности h2, что можно записать как: = h1 + h2 =|( xi+1)2 +yi2 -R2| - |( xi+1)2 +(yi -1) 2-R2|. (2.2-2) Для положения окружности между горизонтальным и диагональным претендентами (положение 1 или 5 на ) h1 положительное, а h2 – отрицательное, что позволяет перейти от выражения 2.2-2 к выражению: = ( xi +1)2 + yi2 - R2 + ( xi + 1)2 +(yi -1) 2- R2. Выразим через базовую погрешность i: = (xi + 1)2 + yi2 - R2 + (xi +1)2 +(yi - 1) 2-R2 - 2yi + 1 + 2yi - 1 = =(xi +1)2 + yi2- 2yi + 1+ R2 + (xi + 1)2 + (yi -1) 2- R2 + 2yi - 1 = = 2i +2yi - 1, что позволяет использовать для расчета сравнитедбно простое выражение: =2I + 2yi - 1. (2.2-2) Таким образом, если при выполнении условия (2.2-1) расчетное положение окружности соответствует положению 1 или 5, то при отрицательном значении в качестве очередной точки выбирается горизонтальный претендент. Заметим, что при расчетном положении окружности, соответствующем положению 2, тем более будет отрицательным, что также обусловит выбор горизонтального претендента. Разность 2 расстояний диагонального и вертикального претендентов до окружности рассчитывается только в случае, когда выполняется условие: >0 , при выполнении которого может иметь место расчетное положение окружности 5, 3, 4. В этом случае 2 формируется за счет вычитания из абсолютного значения расстояния диагонального претендента до окружности h2 абсолютного значения расстояния вертикального претендента до окружности h3, что можно записать как: = h2 + h3 =|( xi+1)2 +(yi - 1)2 -R2|-| xi2 +(yi -1) 2-R2| (2.2-3) Для положения окружности между вертикальным и диагональным претендентами (положение 3 или 5 на ), h2 положительное, а h3 отрицательное, что позволяет перейти от выражения (2.2-3) к выражению: 2= h2 - h3 =( xi+1)2 +(yi -1) 2-R2 - xi2 +(yi-1)2 -R2. Выразим 2 через базовую погрешность i: 2= ( xi+1)2 +(yi -1) 2-R2 - xi2 +(yi-1)2 -R2 + 2yi +1 – 2yi -1 = = ( xi+1)2 +(yi -1) 2-R2 - xi2 + (yi-1)2 -R2– 2xi -1 = 2i-2yi -1, т.е. для расчета 2 можно использовать выражение: =2I -2xi -1. (2.2-4) Таким образом, если при не выполнении условия (2.2-1) расчетное положение окружности соответствует положению 3 или 5, то при положительном значении 2 в качестве очередной точки выбирается вертикальный претендент. Заметим, что при расчетном положении окружности, соответствующем положению 4, 2 тем более будет положительным, что также обусловит выбор вертикального претендента. Начальной точкой формируемой дуги является точка с координатами xн=0, yн=R. Для этой точки базовое отклонение н определяется как: н =( xн+1)2 +(yн -1) 2-R2 =2(1 –R). Расчет по результату выбора претендента координат очередной точки формируемой дуги и соответствующего ей базового отклонения выполняется следующим образом. Если в качестве очередной точки выбран горизонтальный претендент ПH, тогда: xi+1= xi +1; yi+1= yi; i+1 = ( xi+1+1)2 +(yi+1 -1)2-R2 = xi+12+2xi+1 +1 +(yi- -1)2-R2 = = ( xi +1) 2+(yi -1)2-R2+2xi+1 +1 = i +2xi+1 +1. Если в качестве очередной точки выбран вертикальный претендент ПV, тогда: xi+1 = xi; yi+1= yi-1; i+1 =( xi+1+1)2 +(yi+1 -1)2-R2= ( xi+1)2 +yi+12- 2yi+1 + 1-R2 = = ( xi +1) 2+(yi -1)2-R2 -2yi+1 +1 = i -2yi+1 +1. Если в качестве очередной точки выбран диагональный претендент ПD, тогда: xi+1 = xi +1; yi+1 = yi-1; i+1 = ( xi+1+1)2 +(yi+1 -1)2 - R2 = xi+12+2xi+1 +1 +yi+12 - 2yi+1 +1-R2= = ( xi +1) 2 + (yi -1)2 - R2 + 2xi+1+1 - 2yi+1 +1 = i +2xi+1 - 2yi+1+2. Учитывая выше изложенное, алгоритм формирования дуги окружности можно представит в виде граф-схемы, приведенной на следующем рисунке (Рис. Формирование дуги окружности.-14). Так как при формировании очередной точки рассчитываются и используется или 1, или 2 и никогда оба вместе, для них в алгоритме используется одна и та же переменная . Особенностью данного алгоритма является отсутствие длинных операций, что способствует уменьшению длительности его реализации. ![]() Рис. Формирование дуги окружности.‑14 |