Алгоритм поиска освещенных участков многогранных пересекающихся поверхностей в плоскопараллельном световом потоке
Ключевые слова:
алгоритм, поток, параллельных вычисленийАннотация
В данной статье представлен метод поиска освещенных/обдуваемых участков выпуклых пересекающихся многогранников. Ограничение на выпуклость следует из ограничений в алгоритмах Б.Шазеля [3] и С.Хертела [4] поиска линий пересечений многогранников, использованных при подготовке данных для представленного алгоритма. Разработанный алгоритм определяет освещенность областей объектов, основываясь на взаимном расположении проекций контурных циклов и линий пересечений. При этом не ставится ограничения на выпуклость объектов в этапе определения освещенных участков по известным линиям пересечений. Это является большим плюсом, так как при дальнейших исследованиях позволяет снять ограничение на выпуклость многогранников, изменив лишь этап поиска линий пересечений. Разработанный алгоритм прост в понимании и гибок в реализации. Имеет логически обоснованное разделение на этапы, в том числе и пригодные для параллелизации вычислений. Для задач реального времени возможность параллельных вычислений является одним их ключевых характеристик алгоритма.
Библиографические ссылки
[2] JAppel A. The Notion of Quantitative Invisibility and Machine Rendering of Solids // Proc. of ACM National Conference. - Thompson Book, 1967. - pp. 387.
[3] Chazelle B. An optimal algorithm for intersecting three-dimensional convex polyhedral // Society for Industrial and Applied Mathematics. - SIAM J.Comput.- Vol.21. - No. 4.- pp. 671-696
[4] Bentley J. L. andOttmann T. A. Algorithms for reporting and counting geometric intersections // IEEE Transactions on Computers, 1979. -C-28 (9): 643-647, doi:10.1109/TC.1979.1675432
