|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Vadim Ajuev 2:5023/39.10 16 May 2001 22:22:43 To : Leonid Kravets Subject : RE:Варнака --------------------------------------------------------------------------------
LK> Подскажите алгоритм удаление невидимых граней методом Варнака.
LK>
LK> Leonid
Разбиваем видимую часть картинной плоскости на 4 равные части и рассматриваем,
каким образом могут соотносится между собой проекции граней и получившиеся части
картинной плоскости.
Возможны следующие случаи:
1) Проекция грани полностью накрывает область;
2) Проекция грани пересекает область, но не содержится в ней полностью;
3) Проекция грани полностью содержится внутри области;
4) Проекция грани не имеет общих внутренних точек с рассматриваемой областью
(очевидно, что в этом случае грань вообще никак не влияет на то, что видно в
данной области).
Сравнивая область с проекциями всех граней, можно выделить случаи, когда
изображение, получившееся в рассматриваемой области, определяется сразу:
* Проекция ни одной грани не попадает в область;
* Проекция только одной грани содержится в области или пересекает область; в
этом случае грань разбивает всю область на две части, одна из которых
соответствует этой грани;
* Существует грань, проекция которой полностью накрывает данную область, и эта
грань расположена к картинной плоскости ближе, чем все остальные грани,
проекции которых пересекают данную область; в этом случае вся область
соответствует этой грани.
Если ни один из рассмотренных трёх случаев не имеет места, то область снова
разбивается на 4 равные части и проверяется выполнение этих условий для каждой
из частей. Те части, для которых видимость таким образом определить не удалось,
разбиваются снова и т.д.
Критерием, на основании которого можно прекращать разбиение (чтобы избежать
бесконечного зацикливания), можно считать размер области: как только размер
области станет не более размера 1 пикселя, то производить дальнейшее разбиение
не имеет смысла и для данной области ближайшая к ней грань определяется явно.
Удачи!
Vadim Ajuev
aka cre@tor
* Origin: (2:5023/39.10)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/32903b02c573.html, оценка из 5, голосов 10
|