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


  • Kotenko Roman
  • Bozhukha Liliia



data structures, octant tree, kd-tree, bounding volume hierarchy, regular mesh, 3D graphics, polygonal mesh, mesh intersection search, optimization.


In the context of optimizing intersection search in three-dimensional space, various data structures are used, such as Octree, KD-Tree, BVH (Bounding Volume Hierarchy), and Regular Grid. Approaches to finding the intersection may be different depending on the complexity of the meshes and the requirements for the accuracy of the results. For complex meshes (a large number of faces and vertices), the methods of building bounding volumes can be used, which allow you to quickly filter out areas that do not exactly intersect, reducing the computational complexity. It is this approach that will be used in this work. The purpose of the work is to develop software with various data structures. Three-dimensional objects were selected to test the software: Stanford Bunny (~70,000 primitives), Stanford Dragon (~870,000 primitives), Stanford XYZRGB Dragon (~7,200,000 primitives). For the selected shapes, the construction of structures was performed with different parameters of depth and types of distribution. To evaluate and compare the speed of construction of structures, three versions of the mesh with different number of polygons were chosen: ~ 16 thousand triangles - small mesh; ~ 260 thousand triangles - average mesh; ~ 1 million triangles - a large mesh. Construction of tree-like structures was performed with the following parameters: maximum depth: for octree - 10, for kd-trees - 30; the number of triangles per node is 20. These tree construction parameters ensure the maximum speed of intersection search. To build the grid, the size parameter was set to - 20 cells. For a more accurate check of the grid, additional velocity measurements were made at different values of the grid size for a small mesh. Technologies for searching for intersections with three-dimensional objects have been studied and problems that may arise during this operation under certain conditions have been identified. One of these difficulties is the speed of finding an intersection with large sets of primitives that make up objects.


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

Brian Curless. Ray-triangle intersection. URL:https://courses.cs. (date of application 23.05.2022).

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

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

URL: (date of application 23.05.2022).

Ingo Wald. On fast Construction of SAH-based Bounding Volume Hierarchies. URL: /ParallelBVHBuild/fastbuild.pdf (date of application 23.05.2022).

Polygonal grid in computer graphics. URL: (date of application 09.12.2024).

Finding Intersecting Mesh. URL: 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: (date of application 09.01.2024).

Spatial Partition. URL: (дата звернення 09.12.2024).

How octree work. URL: /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:

Tree_Construction_for_3D-Rendering_Algorithms_Like_Ray_Tracing (date of application 09.12.2024).

Spatial Splits in Bounding Volume Hierarchies.

URL: (date of application 09.12.2024).