fullKG

28. Алгоритм выявления видимости части отрезка на основе его разбиения средней точкой.

Yв

	Рн
	Рср’
		Yн
Хл	Рср	Хп

Рк

Находим среднюю точку Анализируются полученных два отрезка (Рн-Рср) и (Рср – Рк).

Рср – Рк – невидим, перенесли точку Рк на место Рср.

Оставшийся отрезок делит пополам Рср’.

Рассматриваем отрезок Рн-Рср’ виден

Рн - запомнили; Рср’-Рк – неизвестно

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

Как только выходим на границу у нас обе точки видны и мы можем вывести полученный отрезок.

Если длина дошла до 0, а мы о нем ничего не знаем то он попал на границу и его надо выводить

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

29. Алгоритм отсечения отрезка сторонами произвольно расположенного выпуклого окна (алгоритм Кируса-Бека).

		P2
Pi		0 t 1
		P(t)=P1+(P2-P1)t
i
P(t)	n	Bнi
		Bн-внутреннее,
P1
		nВНi нормаль к “i”грани

( p(t) pi ) nВНi 0 (если это так, то можем найти точку пересечения с границей)

Можем найти t.

Можем определить видимую часть отрезка.

Все точки мы можем поделить на две группы:

-Точки входа в окошко

-Точки выхода из окна

	(( p p ) ( p				p ) t) n			0
	1	i		2	1		ВНi
	Можно разделить эти две составляющие и получить “t”
		( p p		) nВНi			W	скалярное произведение векторов
	t	1	i
		( p	p ) nВНi				Q	в числителе и знаменателе
		2	1

Если Q>0 , то точка входа

Если Q<0 , то точка выхода

Если Q=0 , то -либо отрезок выражается в точку

-либо отрезок параллелен рассматриваемой стороне окна

p p	// p	p
1 2	i 1	i

Если W<0 , то точка находится вне окна Если W≥0, то точка P1 находится в окне.

2 3

1

4

0 5

вне окна

в окне

30. Алгоритм последовательного отсечения произвольного

многоугольника сторонами выпуклого окна.

Мн-к

окно

Мн-к

Если работаем с выпуклым окном, то рассматриваются стороны окна и смотрится: все что по стороне окна оставляем, а остальную часть отсекаем и так со всеми сторонами. Так мы можем сформировать всё, что останется в окошке, т.е. постепенно отсекается то что лежит вне окна.

1 вар

p

s

вне окна

В выходной массив заносим «0» точек.

2 вар

p

Внутри I окна

s

Вне окна

Тут мы должны найти точку пересечения «I» и занести в выходной массив, и конечную точку тоже заносим в выходной массив.

3 вар

p

s

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

4 вар

p

I

s

Заносим только точку “I” в массив.

Далее меняем стартовую и конечную точку местами. S->P (S – стартовая точка P - конечная)

4

2	3

1

Рассматриваем эту сторону и запоминаем точки 1 и 2.

31. Алгоритм отсечения произвольных многоугольников невыпуклыми окнами (алгоритм Вейлера-Азертона).

		p2		w2
	w2	p5	p1	i1	i2	p2
	w6			i6		i3
w1	w5	p4
	p6 w4		p3
			w1	i5	i4	w3
p1	w3			p3

Точки пересечения принадлежат и окну и многоугольнику. Для окна и многоугольника составляются циклические списки.

p		w
	1	1
p	2	w
		2
p		w
	3	3

В эти циклические списки вставляются точки пересечения окно со сторонами мн-ка.

p			w
		1		1
I	1		I	6
I	2		I	1
p		2	w
				2
I	3		I	2
I	4		I	3
p			w
		3		3
I	5		I	4
I	6		I	5

При этом устанавливаются взаимно односложные двунаправленные связи.

Списки составляют так, что контур многоугольника и контур окна описываются по часовой стрелке.

Ищется любая точка входа в окно для описания списка многоугольника.

32. Алгоритм выявления охватывающего и внешнего многоугольника по отношению к окну.

(4) (5)

Если использовать четырех битовый код для всех точек для определения типа многоугольника:

Для определения (5) или (4) вариант используют лучевой тест.

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

Если нечетное: n=2m+1 следовательно вариант (4) Если четное: n=2m следовательно вариант (5)

одна

точка

одна	2	точки
точка	или
	0	точек

попали на вершину, т.е. пересечение с двумя сторонами

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

33. Методы выявления факта выпуклости многоугольника и способы определения внутренних нормалей к его стороне.

1.Определить, что окно выпуклое.

2.Определить нормаль к стороне.

1.Определить, что окно выпуклое.

P2

P1 P3

P4

P0P6 P5

P(t)=P0+(P1-P0)t

Если в матричное уравнение прямой подставить значения точек P0…P6, то значение тестовой функции будет одного знака.

Матричное уравнение:

f(xi,yi)=

x x		y y
i	0	i	0
x x		y	y
1	0	1	0

, i

2…5. - это тестовая функция

Если в эту значения P0…P6 , то

x x		y y			0
	1			1
x	x	y	2	y
2	1			1

-	2

тестовую функцию постепенно поставить эта функция будет иметь один знак.

- Матричное представление прямой.

1 +

Все точки, которые лежат на прямой будут давать 0.

Справа от прямой точки будут давать знак “+”. А слева – “-”.

Выпуклость проверяется по всем сторонам, проверять знак долго, легче сравнить с “0”.

Если f2+fi<0 – окно не выпуклое.

37. Алгоритм удаления невидимых линий, использующий принцип плавающего горизонта.

Используется когда есть функциональное описание поверхности: f (x,y,z)=0

Делается срез по координате z, т.е. при z=const.

g(x, y)

z const 0

м ожем получить y g1 (x)

Далее для этих функций должны построить кривые.

Построение начинается от	z zmax т.к. оно наиболее близкое к наблюдателю
имеем y g1 (x) z max	и эта функция строится.

Иными словами на экране

y
i, j	z 1
y
i, j	z
	i
х1 х хj
При следующем срезе		zi

строится новая функция

	g
	1		z max
z	max	z y		i	g	(x)	zi
					1

y	i, j	g	1	(x	j	)	zi

если

1.yi, j zi yi, j zi 1

2.yi, j zi yi, j zi 1

то эта часть видна не видна.

Необходимо для каждого “ x j ” отслеживать “ yij max	”.
Для проверки (сравнения) видна точка или не видна.

Точки аппроксимируем отрезками, при этом получаем видимую и обратную сторону поверхности.

38. Общая структура блока просмотра и варианты, обрабатываемые блоком решения для алгоритма выявления видимости, в котором используется принцип деления окна.

m – количество	Блок анализа
многоугольников	начало
начальная установка
Zmin=0 т.е. совпадает с плоскостью визуализации
i=1
	i>m		да		конец
	нет
взять i-ый многоугольник (наиболее дальний) с Zmax=min
проверка на отношение к предшествующему окну (если						i=i+1
оно было, т.е. не первый раз в цикле)
внутри пересечение пересечение		охватывает			вне
стороной	вершиной	окно			окна

*

проверка на отношение к текущему окну

*

да	Zмн-ка> Zокнаmin

Zокна =Zмн-ка

нет

?

в окне больше одного мн-ка и окна надо делить

конец

39. Алгоритм Вейлера-Азертона выявления видимости граней.

Он базируется на алгоритме Вейлера-Азейтона.

Он позволяет отсекать произвольные многоугольники произвольным окном.

1 этап:

Предварительная сортировка по zmax ↓ всех многоугольников

2 этап:

он связан с отсечением многоугольников на плоскости визуализации

берем самый удаленный многоугольник (т.е. тот который ближе к наблюдателю)

	z	i
		max

и используем его в качестве отсекателя.

При этом формируется два списка многоугольников: внутренний список и внешний список.

1	y
2	проекции
0	на XOZ

	z		x
	1	2	I вариант
			II вариант
	1’	2’	один многоугольник
			пересекает другой
	1’’		III вариант
		2’’

Если на первом этапе: после предварительной сортировки по zmax ↓ всех многоугольников получился следующий порядок многоугольников: 1, 2, то на втором этапе: 21

	1	2н(1)
		2
		отсекатель	внутренний	внешний
			список	список
		12
1н(2)		1	1
			21	2н

40. Алгоритм, использующий принцип трассировки лучей.

Н

Экран разбит на пиксели.

Находят точки пересечения луча со всеми объектами сцены (т.е. находят z для пиксельного элемента) для объектов i, j, k и т.д.

Далее их сортируют по z↑: zi , zk, zj , у того, где z максимум этим цветом и подкрашивают точку на экране.

Если лучи параллельны, то проходим по всем пикселям и формируем картинку.

75-95% времени алгоритма сводится к определению точек пересечения (т.е. z).

Для ускорения стремятся упростить задачу поиска точке пересечения.

Не ищут точки пересечения, а сначала объект заменяют на сферичискую или кубовидную оболочку.

Кубовидная: ymax

ymin хmin хmax

хороша тем, что четко определены: хmin , хmax , ymin , ymax. Следовательно зная координаты луч (хi , хi) можем сразу сказать лежит

ли «х» в пределах хmin - хmax и «y» в пределах ymin - ymax или нет. Если нет, то переходим к рассмотрению следующего объекта.

Сферическая:

(x,y) - центр

если хi , yi: (xi xц )2 ( yi yц )2 Rоболочки2

то попадает в оболочку, тогда имеет смысл искать точки пересечения, иначе переходим к следующему объекту.