Skip to main content
added 4 characters in body
Source Link
Kromster
  • 10.7k
  • 4
  • 55
  • 67

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.

 

I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.

I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.

 

I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.

Source Link
Jon
  • 544
  • 2
  • 9

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.

I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.