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

Abstract

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.