Study of data structures for the optimization problem of searching the intersection of three-dimensional objects

Kotenko Roman; Bozhukha Liliia

doi:10.34185/1562-9945-6-149-2023-10

Автор(и)

Kotenko Roman
Bozhukha Liliia

DOI:

https://doi.org/10.34185/1562-9945-6-149-2023-10

Ключові слова:

структури даних, дерево октантів, kd-дерево, ієрархія обмежувальних об’ємів, регулярна сітка, тривимірна графіка, полігональна сітка, пошук перетину між ме-шами, оптимізація.

Анотація

У роботі досліджуються підходи та алгоритми вирішення задачі оптимізації пошуку перетину з тривимірними об’єктами. Приділена увага вибору структури даних. Розроблено програмне забезпечення з набором структур даних (дерево октантів, kd-дерева, ієрархія обмежувальних об’ємів, регулярна сітка) для оптимізації пошуку перетину. Одержані результати аналізу роботи оптимізаційних структур даних задачі пошуку перетину тривимірних об’єктів. Проведено порівняльний аналіз швидко-сті побудови та пошуку перетину між тривимірними об’єктами. Програмне забезпе-чення написано на мові JavaScript у середовищі Visual Studio Code. Результати дослі-дження можуть бути використані при роботі з тривимірною графікою, моделюван-ням, 3D інженерією, обчислювальною геометрією та у вебдодатках з необхідністю реалізації модуля взаємодії з тривимірними об’єктами.

Посилання

Introduction to Polygon Meshes. URL: https://www.scratchapixel.com /lessons/3d-basic-rendering/introduction-polygon-mesh (date of application 23.05.2022).

Brian Curless. Ray-triangle intersection. URL:https://courses.cs. washington.edu/courses/csep557/10au/lectures/triangle_intersection.pdf (date of application 23.05.2022).

Hamzah Asyrani Sulaiman, Abdullah Bade. Bounding Volume Hierarchies for Collision Detection. URL: https://www.researchgate.net /publication/224829148_Bounding_Volume_Hierarchies_for_Collision_Detection (date of application 23.05.2022).

what-when-how — In Depth Tutorials and Information.

URL:http://what-when-how.com/advanced-methods-in-computer-graphics/collision-detection-advanced-methods-in-computer-graphics-part-6/ (date of application 23.05.2022).

Ingo Wald. On fast Construction of SAH-based Bounding Volume Hierarchies. URL: https://www.sci.utah.edu/~wald/Publications/2007 /ParallelBVHBuild/fastbuild.pdf (date of application 23.05.2022).

Polygonal grid in computer graphics. URL: https://termin.in.ua/polihonal-na-sitka/ (date of application 09.12.2024).

Finding Intersecting Mesh. URL:https://www.sandia.gov/files/cubit/15.5/ help_manual/WebHelp/mesh_generation/mesh_quality_assessment/find_intersecting_mesh.htm (date of application 09.12.2024).

A Fast Triangle-Triangle Intersection Test.

URL: https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tritri.pdf (date of application 09.01.2024).

Spatial Partition. URL:https://gameprogrammingpatterns.com/spatial-partition.html (дата звернення 09.12.2024).

How octree work. URL: https://castle-engine.io/vrml_engine_doc /output/xsl/html/section.how_octree_works.html (date of application 09.01.2024).

Fast kd-Tree Construction for 3D-Rendering Algorithms Like Ray Tracing. URL: https://www.researchgate.net/publication/228573134_Fast_kd

Tree_Construction_for_3D-Rendering_Algorithms_Like_Ray_Tracing (date of application 09.12.2024).

Spatial Splits in Bounding Volume Hierarchies.

URL: https://www.nvidia.in/docs/IO/77714/sbvh.pdf (date of application 09.12.2024).