Книги-online

Графика.

И в библиотеке бывают рекламные паузы.

Графика.

Алгоритм Брезенхема генерации 4-х связной развертки отрезка.

Алгоритм генерирует 4-х связную развертку отрезка, заданного координатами концов (x1,y1),(x2,y2). В качестве выходного устройства используется массив Screen: array [0.. ScW-1,0..ScH-1] of TColor, в случае реализации для конкретного устройства, присвоение цвета Color элементу массива Screen[i,j] следует заменить соответствующей процедурой "закраски" точки с координатами (i,j) устройства.

Свойство 4-х связности представления, допускает изменения только одной координаты (вертикальной или горизонтальной) текущей точки и не более чем на единицу. "Закраска" точек растрового представления отрезка происходит в цикле.

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

Алгоритм Брезенхема генерации 8-ми связной развертки отрезка.

Свойство 8-ми связности представления, допускает изменения сразу обеих координат (и вертикальной, и горизонтальной) текущей точки но не более чем на единицу. "Закраска" точек растрового представления отрезка происходит в цикле.

Алгоритм генерации развертки выпуклого многоугольника (метод построчного сканирования).

Алгоритм генерации растрового представления выпуклого многоугольника заданного набором вершин (xi,yi),i=0..n-1. Многоугольник закрашивается цветом Color.В качестве выходного устройства используется массив Screen:array[0..ScW-1,0..ScH-1] of TColor.

Алгоритм закрашивает отрезки сканирующей прямой попадающие внутрь выпуклого многоугольника.Заметим, что границу выпуклого многоугольника можно разбить на две ломаные "левую" и "правую" и, возможно, два ребра "верхнее" и "нижнее" так что каждая из боковых ломаных имеет ровно одно пересечение с каждой сканирующей прямой. Далее используя алгоритм Брезенхема и одновременно генерируя растровое представление для ребер левой и правой части ломаных границ получаем левый и правый пикселы границы многоугольника на каждой сканирующей горизонтальной прямой. Последовательно заполняя интервалы между этими пикселами для каждого значения ординаты от верхней строки развертки до нижней получим растровое представление многоугольника.

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

Алгоритм заполнения произвольной области с затравкой.

Алгоритм закрашивает цветом IC область на экране (в нашем случае в качестве выходного устройства используется массив Screen:array[0..ScW-1,0..ScH-1] of TColor.). Область должна быть ограничена, некоторой линией цвет которой храниться в переменной BC. В качестве затравочной точки, в алгоритм передаются координаты некоторой внутренней точки области (x0,y0).

Алгоритм использует идею, примененную нами в алгоритме построчного сканирования. Заметим, что на каждой строке множество точек подлежащих закраске, состоит из интервалов, принадлежащих внутренности области. Эти интервалы отделены друг от друга интервалами из точек, принадлежащих границе или внешности области. Кроме того, если набор точек образует связный интервал, принадлежащий внутренней части области, то точки над и под этим интервалом либо являются граничными, либо принадлежат внутренней части области. Последние могут служить затравочными для строк лежащих выше и ниже рассматриваемой строки. Суммируя все это, получаем такой алгоритм:

Поместим затравочную точку на стек.

Извлекаем координаты точки с вершины стека в переменные (x,y)

Заполняем максимально возможный интервал, в котором находится точка, вправо и влево вплоть до достижения граничных точек.

Запоминаем крайнюю левую xl и крайнюю правую xr абсциссы заполненного интервала.

В соседних строках над и под интервалом (xl,xr) находим незаполненные к настоящему моменту внутренние точки области, которые объединены в интервалы, а в правый конец каждого такого интервала помещаем на стек.

Если стек не пуст, то переходим к пункту 3.

Алгоритм правильно заполняет любую область включая достаточно сложные области в которых присутствуют отверстия. Наверх

Алгоритм Брезенхема генерации развертки окружности.

Алгоритм генерирует растровую развертку окружности заданной координатами центра (xc,yc) и радиусом r. Его работа достаточно подробно описана в статье алгоритма растровой графики (часть вторая), поэтому здесь останавливаться на этом не буду, отмечу только, что алгоритм использует только целочисленную арифметику, за счет чего удается получить высокую скорость работы. Наверх

Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном.

Часто возникает необходимость отсечь выводимое изображение по границе области, область обычно имеет вид прямоугольника. Данный алгоритм позволяет для некоторого отрезка заданного координатами начала и конца((x1,y1),(x2,y2)), и некоторой прямоугольной области, определить координаты начала и конца части отрезка лежащей внутри области.

Алгоритм разделяет плоскость на 9 частей, и каждой из них ставит в соответствие 4-х битный код следующим образом: включенный бит 0 означает, что точка лежит левее прямоугольника, включенный бит 1 означает, что точка лежит правее прямоугольника, включенный бит 2 означает, что точка лежит выше прямоугольника, включенный бит 3 означает, что точка лежит ниже прямоугольника, Таким образом получаем:

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

Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном.

Данный алгоритм решает ту же задачу, что и предыдущий, но используя другую идею. Сравнение по скорости я не проводил, если кто-то займется буду рад опубликовать результаты. Я взял алгоритм из книги "Основные алгоритмы компьютерной графики", автор П.В.Вельтмандер, книжка есть в электронном виде, но поскольку она то появляется, то исчезает, хочу сразу предупредить, что если Вы не смогли ничего найти по указанной ссылке, ко мне не обращайтеся, я ничем не смогу помочь.

Итак вначале об обозначениях (x0,y0);(x1,y1) - координаты соответственно начала и конца отрезка. (XS1,YS1);(XS2,YS2) - координаты соответственно левого-верхнего и правого-нижнего углов "экрана"(- области по которой производим отсечения).

Итак идея алгоритма. Так как область отсечения является прямоугольником, то ее можно представить в виде неравенств.

	XS1 ≤ x ≤ XS2,
	YS1 ≤ y ≤ YS2

Представим наш исходный отрезок в параметрическом виде.

	x=x0+dx t,
	y=y0+dy t, 0 ≤ t ≤ 1

здесь dx=x1-x0 , dy=y1-y0, при этом в случае когда t изменяется вне отрезка (0,1), получаем координаты точки лежащей на прямой содержащей исходный отрезок, но вне самого отрезка. Подставим это представление в неравенства, определющие область отсечения. Получаем

	-dx·t ≤ x0 - XS1 ,
	dx·t ≤ XS2 - x0 , 
	-dy·t ≤ y0 - YS1 , 
	dy·t ≤ YS2 - y0 .

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

	Pit ≤ Qi , i=1,2,3,4.

при этом

	P1=-dx; Q1=x0 -XS1
	P2=dx; Q2=XS2-x0
	P3=-dy; Q3=y0 -YS1
	P4=dy; Q4=YS2-y0

Решение неравенства зависит от знака Pi, а именно: если Pi < 0, то получаем ограничение на параметр t снизу. если Pi > 0, то получаем ограничение на параметр t сверху. если Pi = 0, то все зависит от знака Qi: если Qi < 0, то решений нет и делаем вывод, что отрезок не видим, если Qi ≥ 0, то любое t является решением и данное неравенство можно не рассматривать.

Таким образом решив систему получим ограничения на t. Следует учесть, что для отрезка диапозон изменения параметра ограничен, а именно 0 ≤ t ≤ 1. И наконец если нашли решение системы с учетом пары ограничений для отрезка можем используя параметрическое представление получить координаты концов точек отсеченного отрезка.

Непосредственно алгоритм будет выглядеть следующим образом: Зададимся величинами t0=0,t1=1 Для i=1,2,3,4 изменим в соответствии со знаком Pi нижнее (t0) или верхнее (t1) ограничение на параметр, или в случае если Pi=0 и Qi < 0, то отрезок не видим и выйдем из цикла. Если отрезок видим вычислим координаты начала и конца видимой части отрезка, используя параметрическое задание.

Алгоритм можно посмотреть по блок-схеме. Наверх