Ньюэл М., Ньюэл Р., Санча

1. Упорядочить все многоугольники в соответствии с max Z-координаты. {P}

2. Разрешить все неопределенности с Z-оболочками => сформировать окончательный список.

3. Преобразовать каждый из многоугольников в растровую форму в порядке убывания Z-координаты (можно методами заполнения) в соответствии с правилами закраски.

Неопределенности

 

Алгоритм проверки: для простоты будем считать, что рассматривается параллельное проектирование вдоль оси Oz.

Перед выводом грани Р следует убедиться, что никакая другая грань Q, проекция которой на ось Oz пересекается с проекцией грани Р, не может закрываться гранью Р. И если это условие выполнено, то грань Р должна быть выведена раньше. Предлагаются следующие 5 тестов в порядке возрастания сложности проверки (хотя бы один «нет» и переход к след. паре граней):

 

1. Пересекаются ли проекции этих граней на ось Ох?

X-оболочки не перекрываются => многоугольники также не перекрываются

 

2. Пересекаются ли их проекции на ось Оу?

Y-оболочки не перекрываются

 

(PXmax<QXmin) or (PXmin>QXmax) (PYmax<QYmin) or (PYmin>QYmax)

 

3. Находится ли грань Р по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)?

P целиком лежит со стороны от плоскости Q, которая дальше от точки зрения (наблюдения)

 

4. Находится ли грань Q по ту же сторону от плоскости, проходящей через грань Р, что и начало координат (наблюдатель)?

Q лежит со стороны плоскости, содержащей P, которая ближе к точке наблюдения

 

Уравнение плоскости Ax+By+Cz+D=0 заданной тремя точками P1, P2, P3.

A=(y2-y1)(z3-z1)-(y3-y1)(z2-z1)

B=(z2-z1)(x3-x1)-(z3-z1)(x2-x1)

C=(x2-x1)(y3-y1)-(x3-x1)(y2-y1)

D= -Ax1-By1-Cz1

С какой стороны от плоскости находится точка?

P4(x4,y4,z4), P5(x5,y5,z5)

fТ=Ax+By+Cz+D

fТ>0 – точка лежит дальше от плоскости к точке наблюдения;

fТ<0 – точка лежит ближе к плоскости к точке наблюдения;

fТ=0 – точка лежит на плоскости.

 

5. Пересекаются ли проекции этих граней на картинной плоскости?

Проекции P и Q на плоскости XY не пересекаются

Задача: С какой стороны от прямой лежит точка?

Уравнение прямой через две точки

=>

y=bx+d

тогда fТ=y–bx–d

fТ>0 – выше, правее (дальше);

fТ<0 – ниже, левее (ближе);

fТ=0 – лежит на прямой.

 

Задача: Пересекаются ли 2 ребра? è

 

Задача Пересекаются ли 2 многоугольника?

Каждое ребро одной грани сравнить с каждым ребром другой. Если найдены 2 пересекающихся ребра => многоугольники пересекаются.

 

Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем что эти две грани - Р и Q упорядочены верно, и сравниваем Р со следующей гранью. В противном случае считаем, что эти грани необходимо поменять местами, для чего проверяются следующие тесты:

3'. Находится ли грань Q по другую сторону от плоскости, проходящей через грань Р, чем начало координат?

4'. Находится ли грань Р по ту же сторону от плоскости, проходящей через грань Q, что и начало координат?

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

 








Дата добавления: 2016-04-14; просмотров: 480;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.