Алгоритм развертки окружности (эллипса, дуги).
Для упрощения возьмем эллипс с полуосями a и b, совпадающими с вертикалью и горизонталью экрана. Пусть центр эллипса имеет координаты (0,0). Уравнение такого эллипса имеет вид:
b2x2+a2y2=a2b2
Существуют различные алгоритмы рисования эллипса и его частного случая – окружности: по вышеприведенной формуле (нерационально – большое количество действий с вещественными числами, в том числе и операция квадратного корня) и инкрементные алгоритмы, учитывающие, что рисовать надо не весь ортогональный эллипс, а только его ¼ часть (например, первый квадрант). Остальные точки симметрично расставляются: (X,Y); (-X,Y); (X,-Y); (-X,-Y). Для окружности достаточно рисовать лишь ее 1/8 часть (от 90° до 45°), остальное симметрия: (-Y,X); (-X,Y); (X,Y); (Y,X);
(-Y,-X); (-X,-Y); (X,-Y); (Y,-X);.
Если X1=0, то Y1=R, и далее X i+1 = X i +1, а Y i+1 ={ Y i или Y i -1} и так до X i = Y i и все алгоритмы отличаются методом определения выбора {Yi или Yi-1}.
Рассмотрим самый простой алгоритм рисования окружности – инкрементный алгоритм Хардебурга. И хотя в нем используется вещественная операция, но алгоритм оптимизирован.
Основное уравнение Y 2 = R 2 - X 2 (R –радиус окружности). Х постоянно инкрементируется, зная Y 2 = R 2 в начальной точке, в каждой следующей точке Y 2 вычисляется так: X i+1 = X i +1
Yi+12=R2-Xi+12=R2-(Xi+1)2=(R2-Xi2)-2Xi-1=Yi2-(2Xi+1)
|
Procedure Put8Pixels(x,y,color:integer);
begin SetPixel(x,y,color); SetPixel(-x,y,color);
SetPixel(x,-y,color); SetPixel(-x,-y,color);
SetPixel(y, x,color); SetPixel(-y,x,color);
SetPixel(y,-x,color); SetPixel(-y,-x,color);
end;
VAR X, Y, YY :longint;
Begin
X:=0; Y:=R; YY:=R*R;
Put8Pixels(X,Y,Color);
While X<Y do begin
X:=X+1; Put8Pixels(X,Y,Color);
YY:=YY – (2*X+1);
IF YY<=(Y*Y-Y) then Y:=Y-1;
{ YY<=Sqr(Y-0.5) }
end;
End.
|
|
|
Недостатки многих инкрементных алгоритмов:
1. вырожденные эллипсы (a=0 или b=0) рисуются
неправильно
2. эллипсы с очень большим радиусом могут приводить
к переполнению целочисленных переменных
3. пикселы с координатами (±a,0) и (0,±b) будут
сформированы дважды, что при XOR-выводе приводит
к их стиранию и требует коррекции алгоритма
(эта ошибка присутствует в Borland Pascal)
Растровая развертка многоугольников.
Объект задан в каркасной форме в ГСК.
В порядке сканирующихся строк экранным лучом определить принадлежность точки многоугольнику и вывести с заданными атрибутами.
Такой процесс неэффективен, поскольку последовательность соседних пикселей обычно принадлежит многоугольнику.
Свойство когерентности растровых строк: соседние пиксели имею один атрибут, смена атрибута происходит на пересечении с ребрами. На сканирующей строке 8 (рис.11.25) внутри многоугольника находятся две полосы пикселей, которые можно закрасить тремя этапами:
1. Найти пересечения сканирующей строки со всеми ребрами многоугольника.
2. Упорядочить точки пересечений по возрастанию координаты х.
3. Раскрасить все пиксели между парами точек пересечения.
Для рис. 11.25 в упорядоченном списке x-координат точек пересечения будут числа (2, 4, 9, 13). Поэтому закрашиваются все пиксели в интервалах 2—4 и 9—13.
|
|
|
Горизонтальные ребра не могут пересекать сканирующие строки и поэтому не рассматриваются.
Пересечения вершин.
Проблема: если число точек пересечения в отсортированном списке нечетно, процедура раскраски работает неправильно. Это возможно, когда сканирующая строка пересекает вершину, в результате чего в список пересечений заносятся две точки пересечения. Рассмотрим, например, строку с у=3 (рис. 11.25). Она пересекается с ребрами многоугольника в точках 2, 2 и 10. Тогда последовательность пикселей от 2 до 2 (т. е. пиксель в точке x=2, у=3) закрасилась бы, совокупность пикселей от 3 до 9 осталась бы незакрашенной, а последовательность от 10 до правой границы буфера закрасится.
Прохождение сканирующей строки через вершину следует считать за одно пересечение. Однако это не приводит к правильным результатам в случаях, когда с вершинами пересекаются строки 1, 7, 9 или 11. Вводят локальные минимумы и максимумы (считаются за два пересечения), а остальные учитываются как одно пересечение. Локальный минимум - Y-координаты предыдущей и последующей вершин больше, чем у рассматриваемой вершины. Аналогично определяется локальный максимум. На сканирующих строках 1 и 7 локальные минимумы, на строках 9 и 11 — локальные максимумы. Убедиться, что такие промежуточные вершины пересекаются только один раз, довольно легко: одно из смежных ребер укорачивается до того, как вычисляются пересечения (рис. 11.26).
|
|
|
Такое укорачивание проводится только в том случае, если вершина лежит на сканирующей строке, что случается всегда, когда координаты вершин — целые числа, и редко, если координаты вершин представлены с более высоким разрешением, чем сама растровая сетка.
Дата добавления: 2020-11-15; просмотров: 377; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!