ПРОГРАММНЫЙ МОДУЛЬ ДЛЯ ПОСТРОЕНИЯ ПЕРЕСЕЧЕНИЯ ТРИАНГУЛИРОВАННЫХ ПОВЕРХНОСТЕЙ

  • Владимир Витальевич Курганский Ярославский государственный университет им. П.Г. Демидова http://orcid.org/0000-0002-3648-3396
  • Эльвира Васильевна Гайдук Ярославский государственный университет им. П.Г. Демидова http://orcid.org/0000-0001-7428-8375

Аннотация

Предлагается эффективный алгоритм реализации булевых операций над триангулированными поверхностями, а именно: дизъюнкции, конъюнкции и булевой разности, и его программная реализация. Идея алгоритма состоит в следующем. Сначала выясняются пары пересекающихся треугольников: локализуется место пересечения двух поверхностей с помощью ограничивающих объём параллелепипедов и дальнейшего их пересечения. Затем строится линия пересечения для каждой пары треугольников: выбирается пара пересекающихся треугольников, строится отрезок, по которому они пересекаются. Далее, благодаря введённой структуре данных, выбираются "соседние" треугольники, среди который выбираются те, которые образуют пересекающуюся пару. После этого описанный процесс продолжается. После этого треугольники, участвующие в пересечении, ретриангулируются. Для каждого треугольника известны все ребра, по которым он пересекается с треугольниками из другой поверхности. Эти ребра являются структурными ребрами в задаче триангуляции с ограничениями для данного треугольника. Затем поверхности объединяются в одну и формируются циклы пересечений. Далее по циклам пересечения выделяются подповерхности, ограниченные найденными циклами. Поскольку линия пересечения поверхностей строилась последовательно, возможно задать направление каждого ребра. Выбирается любое ребро из линии пересечения. В строящуюся подповерхность добавляется треугольник, который включает в себя это ребро и его ориентация совпадает с направлением ребра. Из линии пересечения удаляется выбранное на предыдущем шаге ребро, но добавляются два новых – оставшиеся ребра добавленного треугольника, их ориентация задается таким образом, чтобы не нарушалась возможность пройти по линии пересечения по циклу. Этот процесс повторяется до тех пор, пока линия пересечения не пуста. Процесс построения подповерхности необходимо проделать для каждой линии пересечения. После этого все треугольники, не вошедшие ни в одну из построенных подповерхностей, объединяются и образуют новую подповерхность. Затем из полученных подповерхностей в зависимости от выполняемой булевой операции собираются итоговые поверхности. Рассмотренный алгоритм реализован на языке Java 7 и успешно внедрён в специализированные программные продукты: "3D-SchoolEdit" и "3D-ChemistryEdit" Первый из них представляет собой программу для построения 3D-моделей для школьных задач по стереометрии с возможностью 3D-печати данных моделей, второй – редактор химических соединений с возможностью 3D-печати.

Сведения об авторах

Владимир Витальевич Курганский, Ярославский государственный университет им. П.Г. Демидова

студент, математический факультет 

Эльвира Васильевна Гайдук, Ярославский государственный университет им. П.Г. Демидова

магистрант, математический факультет 


Научный руководитель: Игорь Евгеньевич Преображенский, инженер-исследователь международной научно-исследовательской лаборатории «Дискретная и вычислительная геометрия» им. Б.Н. Делоне, ассистент кафедры дифференциальных уравнений, Ярославский государственный университет им. П.Г. Демидова

Литература

[1] Mei G, Tipper J.C. Simple and robust boolean operations for triangulated surface. Computing Research Repository. 2013. Vol. abs/1308.4434. Pp. 1-18. Available at: https://arxiv.org/pdf/1308.4434.pdf (accessed 10.02.2018).
[2] Ernst M., Greiner G. Early split clipping for bounding volume hierarchies. Proceedings of the IEEE Symposium on Interactive Ray Tracing. 2007. Pp. 73 - 78. DOI: http://doi.org/10.1109/RT.2007.4342593
[3] Bergen G.V.D. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools. 1997; 2(4):1-13. DOI: https://doi.org/10.1080/10867651.1997.10487480
[4] Baumgart B.G. Winged Edge Polyhedron Representation. Technical Report, Stanford University, Stanford, CA, USA. 1972.
[5] Skvortsov A.V. Delaunay triangulation and its application. Tomsk: Publishing house Tom. University. 2002. 128 p. (In Russian)
[6] Sâm Landier. Boolean operations on arbitrary polygonal and polyhedral meshes. Computer-Aided Design. 2017; 85:138-153. DOI: https://doi.org/10.1016/j.cad.2016.07.013
[7] Kugler M., Hostettler A., Soler L., Rémond Y., George D. A new algorithm for volume mesh refinement on merging geometries: Application to liver and vascularization. Journal of Computational and Applied Mathematics. 2018; 330(C):429-440. DOI: https://doi.org/10.1016/j.cam.2017.09.012
[8] Bagley B., Sastry Sh.P., Whitaker R.T. A Marching-tetrahedra Algorithm for Feature-preserving Meshing of Piecewise-smooth Implicit Surfaces. Procedia Engineering. 2016; 163:162-174. DOI: https://doi.org/10.1016/j.proeng.2016.11.042
[9] Xu S., Keyser J. Fast and robust Booleans on polyhedral. Computer-Aided Design. 2013; 45(2):529-534. DOI: https://doi.org/10.1016/j.cad.2012.10.036
[10] Attene M. Direct repair of self-intersecting meshes. Graphical Models. 2014; 76(6):658-668. DOI: https://doi.org/10.1016/j.gmod.2014.09.002
[11] Zhoufang Xiao, Jianjun Chen, Yao Zheng, Jianjing Zheng, Desheng Wang. Booleans of triangulated solids by a boundary conforming tetrahedral mesh generation approach. Computers & Graphics. 2016; 59(C):13-27. DOI: http://dx.doi.org/10.1016/j.cag.2016.04.004
[12] Monterde D.L., Martinez J., Vigo M., Pla N. A practical and robust method to compute the boundary of three-dimensional axis-aligned boxes. GRAPP 2014 - Proceedings of the 9th International Conference on Computer Graphics Theory and Applications. 5-8 Jan. 2014. Pp. 34-42. Available at: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7296027&isnumber=7295996 (accessed 10.02.18).
[13] Guo K.B., Zhang L.C., Wang C.J. et al. Boolean operations of STL models based on loop detection. International Journal of Advanced Manufacturing Technology. 2007; 33(5-6):627-633. DOI: https://doi.org/10.1007/s00170-006-0487-5
[14] Wang Ch. Approximate Boolean Operations on Large Polyhedral Solids with Partial Mesh Reconstruction. IEEE transactions on visualization and computer graphics. 2011; 17(6):836-849. DOI: https://doi.org/10.1109/TVCG.2010.106
[15] Jiang X., Peng Q., Cheng X., Dai N., Cheng Ch., Li D. Efficient Booleans algorithms for triangulated meshes of geometric modeling. Computer-Aided Design and Applications. 2016; 13(4):419-430. DOI: https://doi.org/10.1080/16864360.2015.1131530
[16] Chen, Ming & Yu Chen, Xiao & Tang, Kai & Yuen, Matthew. Efficient Boolean Operation on Manifold Mesh Surfaces. Computer-Aided Design and Applications. 2013; 7:405-415. DOI: https://doi.org/10.3722/cadaps.2010.405-415
[17] Lo S.H., Wang W.X. A fast robust algorithm for the intersection of triangulated surfaces. Engineering with Computers. 2004; 20(1):11-21. DOI: https://doi.org/10.1007/s00366-004-0277-3
[18] Campen M., Kobbelt L. Exact and Robust (Self-)Intersections for Polygonal Meshes. Computer Graphics Forum. 2010; 29:397–406. DOI: https://doi.org/10.1111/j.1467-8659.2009.01609.x
[19] Zaharescu A., Boyer E., Horaud R. Topology-Adaptive Mesh Deformation for Surface Evolution, Morphing, and Multiview Reconstruction. IEEE Transactions on pattern analysis and machine intelligence. 2011; 33(4). DOI: https://doi.org/10.1109/TPAMI.2010.116
[20] Garcıґa A.L., Ruiz de Miras J., Feito F.R. Evaluation of Boolean operations between free-form solids using extended simplicial chains and PN triangles. The Visual Computer. 2011; 27(6-8):531–541. DOI: https://doi.org/10.1007/s00371-011-0566-y
[21] Hoffmann C. Geometric and solid modeling. Morgan Kaufmann, San Mateo, California, 1989.
[22] Lo S.H, Wang W.X. Finite element mesh generation over intersecting curved surfaces by tracing of neighbours. Finite Elements In Analysis And Design. 2005; 41(4):351–370. DOI: http://dx.doi.org/10.1016/j.finel.2004.07.002
[23] Pavic D, Campen M, Kobbelt L. Hybrid Booleans. Computer Graphics Forum. 2010; 29(1):75–87. DOI: https://doi.org/10.1111/j.1467-8659.2009.01545.x
[24] Schifko M., Juttler B., Kornberger B. Industrial application of exact Boolean operations for meshes. Proceedings of the 26th Spring Conference on Computer Graphics, (SCCG '10). ACM, New York, NY, USA, 2010. Pp. 165–172. DOI: http://dx.doi.org/10.1145/1925059.1925089
Опубликована
2018-03-30
Как цитировать
КУРГАНСКИЙ, Владимир Витальевич; ГАЙДУК, Эльвира Васильевна. ПРОГРАММНЫЙ МОДУЛЬ ДЛЯ ПОСТРОЕНИЯ ПЕРЕСЕЧЕНИЯ ТРИАНГУЛИРОВАННЫХ ПОВЕРХНОСТЕЙ. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 14, n. 1, p. 213-221, mar. 2018. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/284>. Дата доступа: 21 nov. 2019 doi: https://doi.org/10.25559/SITITO.14.201801.213-221.
Раздел
Исследования и разработки в области новых ИТ и их приложений