ПРОГРАММНЫЙ МОДУЛЬ ДЛЯ ПОСТРОЕНИЯ ПЕРЕСЕЧЕНИЯ ТРИАНГУЛИРОВАННЫХ ПОВЕРХНОСТЕЙ
Аннотация
Предлагается эффективный алгоритм реализации булевых операций над триангулированными поверхностями, а именно: дизъюнкции, конъюнкции и булевой разности, и его программная реализация. Идея алгоритма состоит в следующем. Сначала выясняются пары пересекающихся треугольников: локализуется место пересечения двух поверхностей с помощью ограничивающих объём параллелепипедов и дальнейшего их пересечения. Затем строится линия пересечения для каждой пары треугольников: выбирается пара пересекающихся треугольников, строится отрезок, по которому они пересекаются. Далее, благодаря введённой структуре данных, выбираются "соседние" треугольники, среди который выбираются те, которые образуют пересекающуюся пару. После этого описанный процесс продолжается. После этого треугольники, участвующие в пересечении, ретриангулируются. Для каждого треугольника известны все ребра, по которым он пересекается с треугольниками из другой поверхности. Эти ребра являются структурными ребрами в задаче триангуляции с ограничениями для данного треугольника. Затем поверхности объединяются в одну и формируются циклы пересечений. Далее по циклам пересечения выделяются подповерхности, ограниченные найденными циклами. Поскольку линия пересечения поверхностей строилась последовательно, возможно задать направление каждого ребра. Выбирается любое ребро из линии пересечения. В строящуюся подповерхность добавляется треугольник, который включает в себя это ребро и его ориентация совпадает с направлением ребра. Из линии пересечения удаляется выбранное на предыдущем шаге ребро, но добавляются два новых – оставшиеся ребра добавленного треугольника, их ориентация задается таким образом, чтобы не нарушалась возможность пройти по линии пересечения по циклу. Этот процесс повторяется до тех пор, пока линия пересечения не пуста. Процесс построения подповерхности необходимо проделать для каждой линии пересечения. После этого все треугольники, не вошедшие ни в одну из построенных подповерхностей, объединяются и образуют новую подповерхность. Затем из полученных подповерхностей в зависимости от выполняемой булевой операции собираются итоговые поверхности. Рассмотренный алгоритм реализован на языке Java 7 и успешно внедрён в специализированные программные продукты: "3D-SchoolEdit" и "3D-ChemistryEdit" Первый из них представляет собой программу для построения 3D-моделей для школьных задач по стереометрии с возможностью 3D-печати данных моделей, второй – редактор химических соединений с возможностью 3D-печати.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
