<p>I have a set of non-intersecting packed tetrahedrons in 3D space. What is the most optimized way to find the tetrahedron inside which a query point lies?</p>
<p><strong>Edit:</strong> I tried some data structures and techniques for this problem like Octree, Spatial Hashing, UniformGrid and BVH. Octree gets built fast, but querying is slow. Querying in BVH is very fast but the process of building BVH from the tetrahedrons has a high computational complexity. Spacial Hashing is super fast but does not guarantee accuracy. Building UniformGrid and storing tetrahedrons for each grid cell takes a lot of time. I want both building and querying to be fast.</p>
<p>I want the method to be efficient but am very much concerned about the accuracy of the method.</p>
<p>The number of tetrahedrons is of the order 10^6.</p>

CC BY-SA 4.0
2024-07-25T08:47:28.987Z
A bounding volume hierarchy could be used.
lightxbulb
CC BY-SA 4.0
2024-07-28T20:22:10.883Z
@lightxbulb, I performed the querying using BVH. I have edited the question to include that
Prakhar
<3d><algorithm><optimisation>
Querying a point to find the tetrahedron it lies inside in 3D
Prakhar
# Querying a point to find the tetrahedron it lies inside in 3D

(Asked by: username_0 on 2024-07-25)

I have a set of non-intersecting packed tetrahedrons in 3D space. What is the most optimized way to find the tetrahedron inside which a query point lies?

**Edit:** I tried some data structures and techniques for this problem like Octree, Spatial Hashing, UniformGrid and BVH. Octree gets built fast, but querying is slow. Querying in BVH is very fast but the process of building BVH from the tetrahedrons has a high computational complexity. Spacial Hashing is super fast but does not guarantee accuracy. Building UniformGrid and storing tetrahedrons for each grid cell takes a lot of time. I want both building and querying to be fast.

I want the method to be efficient but am very much concerned about the accuracy of the method.

The number of tetrahedrons is of the order 10^6.

**Tags:** 3d, algorithm, optimisation

> **Comments:**
> **username_1**: A bounding volume hierarchy could be used.  
> **username_0**: @username_1, I performed the querying using BVH. I have edited the question to include that  

---

## 0 answers

