ПРОГРАММНЫЙ МОДУЛЬ ДЛЯ ПОСТРОЕНИЯ ПЕРЕСЕЧЕНИЯ ТРИАНГУЛИРОВАННЫХ ПОВЕРХНОСТЕЙ - Курганский, Владимир Витальевич; Гайдук, Эльвира Васильевна (Современные информационные технологии и ИТ-образование, 2018)
Предлагается эффективный алгоритм реализации булевых операций над триангулированными поверхностями, а именно: дизъюнкции, конъюнкции и булевой разности, и его программная реализация. Идея алгоритма состоит в следующем. Сначала выясняются пары пересекающихся треугольников: локализуется место пересечения двух поверхностей с помощью ограничивающих объём параллелепипедов и дальнейшего их пересечения. Затем строится линия пересечения для каждой пары треугольников: выбирается пара пересекающихся треугольников, строится отрезок, по которому они пересекаются. Далее, благодаря введённой структуре данных, выбираются "соседние" треугольники, среди который выбираются те, которые образуют пересекающуюся пару. После этого описанный процесс продолжается. После этого треугольники, участвующие в пересечении, ретриангулируются. Для каждого треугольника известны все ребра, по которым он пересекается с треугольниками из другой поверхности. Эти ребра являются структурными ребрами в задаче триангуляции с ограничениями для данного треугольника. Затем поверхности объединяются в одну и формируются циклы пересечений. Далее по циклам пересечения выделяются подповерхности, ограниченные найденными циклами. Поскольку линия пересечения поверхностей строилась последовательно, возможно задать направление каждого ребра. Выбирается любое ребро из линии пересечения. В строящуюся подповерхность добавляется треугольник, который включает в себя это ребро и его ориентация совпадает с направлением ребра. Из линии пересечения удаляется выбранное на предыдущем шаге ребро, но добавляются два новых – оставшиеся ребра добавленного треугольника, их ориентация задается таким образом, чтобы не нарушалась возможность пройти по линии пересечения по циклу. Этот процесс повторяется до тех пор, пока линия пересечения не пуста. Процесс построения подповерхности необходимо проделать для каждой линии пересечения. После этого все треугольники, не вошедшие ни в одну из построенных подповерхностей, объединяются и образуют новую подповерхность. Затем из полученных подповерхностей в зависимости от выполняемой булевой операции собираются итоговые поверхности. Рассмотренный алгоритм реализован на языке Java 7 и успешно внедрён в специализированные программные продукты: "3D-SchoolEdit" и "3D-ChemistryEdit" Первый из них представляет собой программу для построения 3D-моделей для школьных задач по стереометрии с возможностью 3D-печати данных моделей, второй – редактор химических соединений с возможностью 3D-печати.