Основные этапы алгоритма Робертса и их содержание. Математические основы.
См. вопросы № 28, 27, 26
Удаление невидимых линий и поверхностей в пространстве изображений. Алгоритм Варнока (разбиение окнами): последовательность действий и основные принципы.
Единственной версии алгоритма не существует. Окно разбивается на части, если оно не пусто. Это продолжается, пока не получим окно в 1 пиксель. В более сложных версиях, ставится вопрос о том, что изображается в окне. Окно делим пока нельзя сказать, что изображено в окне.
- Все многоугольники являются внешними – окно закрасить цветом фона
- Многоугольник, связанный с окном является внутренним – закрасить окно цветом фона, растровая развёртка многоугольника
- Многоугольник, связанный с окном является пересекающим – отсечение по границе окна и п. 2
- С окном связан один охватывающий многоугольник – закрасить цветом многоугольника
- С окном связаны внутренние пересекающие мноугольники, и есть хотя бы один охватывающий, расположенный ближе всех остальных к наблюдателю.
Рекомендуемая последовательность
- Проводится простейший габаритный тест с прямоугольной оболочкой, определяется как можно большее количество пустых окон и окон с единственным внутренним многоугольником
- Выполнение теста с целью определения окон, пересекаемых единственным многоугольником
- Тест с целью распознавания внешних и охватывающих многоугольников. Получаем новые пустые окна и окна, охватываемые пустым многоугольником
- Можно проводить разбиение окна на подокна или проводить ещё тест на обнаружение охватывающего многоугольника, лежащего ближе к наблюдателю
|
|
|
Типы многоугольников, анализируемых в алгоритме Варнока. Методы их идентификации.
См. вопрос № 30
Алгоритм Вейлера Азертона удаления невидимых линий и поверхностей.
Алгоритм – попытка минимизировать количество шагов в алгоритме Варнока путём разбиения окна вдоль границ многоугольника.
Алгоритм
- Предварительная сортировка по глубине (для формирования списка приблизительных приоритетов)
- Отсечение по границам ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости (в качестве отсекателя используется копия первого многоугольника из списка приблизельных приоритетов. отсекаться будут все многоугольники в этом списке, включая первый. формируется 2 списка – внутренний (для каждого отсекаемого многоугольника то часть, которая оказывается внутри отсекателя) и внешний (оставшаяся часть))
- Удаление многугольников внутреннего списка, которые экранируются отсекателем
- Если глубина многоугольника из внутреннего списка больше, чем Zmin отсекателя, то такой многоугольник частично экранирует отсекатель. Нужно рекурсивно разделить плоскость, используя многоугольник, нарушивший порядок в качестве отсекателя (нужно использовать копию исходного, а не остаток после предыдущего отсечения). Отсечению подлежат все многоугольники из внутреннего списка
- По окончанию отсечения или рекурсивного разбиения изображаются многоугольники из внутреннего списка (те, которые остались после удаления всех экранируемых на каждом шаге многоугольников – остаются только отсекающие многоугольники)
- Работа продолжается с внешним списком (шаги 1-5)
Если многоугольники пересекаются, то для корректной работы данного алгоритма нужно плоскость одного разбить другой на две части.
|
|
|
Дата добавления: 2019-01-14; просмотров: 383; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!