Файл: GOSY.doc

а) б)

Рис. 1 - Четырехсвязная (а) и восьмисвязная (б) развертки отрезка.

Четырехсвязная развертка отрезка включает те и только те точки, квадратные окрестности которых пересекаются с отрезком. Восьмисвязная развертка отрезка включает те и только те точки, боковые стороны квадратных окрестностей которых пересекаются с отрезком.

Приведем алгоритм для генерации четырехсвязной развертки:

x:=x1;

y:=y1;

n:=x2-x1;

m:=y2-y1;

d:=(m/n);

e:=d/2;

for i:=1 to n+m do

begin

x:=x+1;

e:=e+d; { отклонение }

if e>0.5 then

begin

y:=y+1;

e:=e-1

end

else

begin

x:=x+1;

e:=e+d

end;

PutPixel(x,y)

end;

Здесь в переменной е хранится разница между координатой Y текущей точки отрезка и координатой Y точки пересечения отрезка с правой границей квадратной окрестности текущей точки растровой развертки. При e0.5 отрезок пересекает окрестность точки, лежащей справа от текущей, и нужно сместиться вправо. При e0.5 отрезок пересекает окрестность точки, лежащей выше текущей, и надо сместиться вверх (Рис. ).

Рис. 2 – Схема работы алгоритма четырехсвязной развертки отрезка.

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

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

Procedure Bresenham(x1,y1,x2,y2,Color: integer);

var

dx,dy,incr1,incr2,d,x,y,xend: integer;

begin

dx:= ABS(x2-x1);

dy:= Abs(y2-y1);

d:=2*dy-dx; {начальное значение для d}

incr1:=2*dy; {приращение для d<0}

incr2:=2*(dy-dx); {приращение для d>=0}

if x1>x2 then {начинаем с точки с меньшим знач. x}

begin

x:=x2;

y:=y2;

xend:=x1;

end

else

begin

x:=x1;

y:=y1;

xend:=x2;

end;

PutPixel(x,y,Color); {первая точка отрезка}

While x<xend do

begin

x:=x+1;

if d<0 then

d:=d+incr1 {выбираем нижнюю точку}

else

begin

y:=y+1;

d:=d+incr2; {выбираем верхнюю точку, y-возрастает}

end;

PutPixel(x,y,Color);

end;{while}

end;{procedure}

Еще одна задача, часто решаемая в ходе визуализации – заливка цветом некоторой заданной границей области. Область обычно задается или в векторном виде массивом координат вершин многоугольника, или в растровом – набором пикселов определенного цвета, образующих замкнутый контур.

Для решения задачи заливки векторного многоугольника необходимо закрашивать тем или иным цветом выводимые на экран пиксели в зависимости от того, лежат они внутри многоугольника или снаружи. Таким образом, задача векторной заливки сводится к задаче определения принадлежности точки P(x,y) многоугольнику, заданному координатами вершин. Идея алгоритма для решения этой задачи состоит в следующем (Рис.).

Рис.3 –Определение принадлежности точки многоугольнику.

Проведем через точку P горизонтальную полупрямую (луч) и определим число пересечений этой полупрямой с ребрами многоугольника. Если это число нечетно, то точка Р лежит внутри многоугольника, четно – снаружи.

Заполнение растровой области хорошо знакомо программистам, поскольку почти во всех языках программирования есть соответствующие команды (например, в языке Pascal это команда FloodFill, в Delphi – метод FloodFill объекта TCanvas и т.д.)

Рис.4 – Заполнение растровой области с затравкой.

Граница области является четырех- или восьмисвязной растровой кривой, все пикселы которой имеют один и тот же цвет. Внутри области могут находиться "острова", которые закрашивать не надо. Предполагается, что внутри области задана точка начала закраски, называемая затравкой (Рис.).

Для выполнения заливки используется специальная структура данных, называемая стеком (stack). Стек работает по принципу "первым вошел – последним вышел" (Рис.).

Рис.5 - Стек.

Хорошим аналогом стека является магазин автомата Калашникова (программистская шутка гласит, что АКМ – лучшее средство для превращения стека в очередь). При извлечении значений из стека нужно помнить о том, что теперь они будут идти в обратном порядке. Если мы занесли в стек сначала а, потом b, потом c, то первым извлечется с, затем b и, наконец, а.

Эффективный алгоритм заливки основан на построчном сканировании заполняемой области. Вот его схема:

Инициализируем стек, помещая в него координаты затравочного пиксела. Пока стек не пуст:

извлекаем пиксел (х,у) из стека;

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

запоминаем крайнюю левую Lx и крайнюю правую Rx абсциссы заполненного интервала;

в соседних строках над и под интервалом (Lx,Rx) находим незаполненные к настоящему моменту внутренние пикселы области, которые, как мы уже заметили, объединены в интервалы, а в каждом из этих интервалов находим крайние правые пикселы. Каждый из этих пикселов вносим в стек в качестве затравочного.

Такой алгоритм правильно заполняет область любой конфигурации, в том числе и с "островами" внутри.

5. Содержание отчета

1. Математическая постановка задачи (описание метода или алгоритма);

2. Описание входных - выходных данных;

3. Блок-схема алгоритма;

4. Текст программы;

5. Результат работы программы.

Вопрос 3 – Создать объекты.

Для начала необходимо настроить единицы измерения: зайдите в главном меню Customize - Unitssetup. В появившемся окне выставите Metric, и в раскрывающемся списке выберите Centimeters.

Затем надо выставить шаг сетки (допустим 10 см.): в главном меню Customize - Grid and snaps settings, далее см. рисунок.

Создание стен (один из способов). Стены будем создавать сплайнами (беря размеры с плана или просто измеряя свою комнату) с последующим “вытягиванием” (Extrude). Включите привязки и убедитесь, что у привязки к узлам сетки стоит галочка (для этого щелкните правой кнопкой мышки на этой кнопке).

На основной панели инструментов активируйте Create – Shapes – Line.

И пользуясь привязками к узлам сетки, в соответствии с размерами, вычертите контуры стен (при этом выкидывая окна и двери). В результате должно получиться что-то подобное…

Если у вас получилось несколько отдельных сплайнов (как на картинке), необходимо их объединить. Выделите один из сплайнов, перейдите на Modify, нажмите кнопку «Attach» и выделите остальные сплайны.

Далее экструдируйте полученный сплайн на высоту помещения (допустим 270 см.). На основной панели инструментов активируйте Modify и в раскрывающемся списке выберите модификатор Extrude.

Параметр Amount установите на 270 см., количество сегментов – 3.