# Tag Info

## Hot answers tagged bounding-volume-hierarchy

5

Consider using spatial hashing, especially if your objects are similarly sized. Basically, divide your world into uniformly-sized grid cells (2D and 3D are both valid possibilities depending on the amount of vertical motion). Each update, assign your object to each bin that it overlaps—if the cells are decently sized relative to the objects, most objects ...

4

@Christian Pagot I think it is worth mentioning, that DXR is using Bottom Level Acceleration Structures (BLAS) as well as Top Level Acceleration Structures (TLAS): Figure 3: Overview of raytracing building blocks Figure 4: Overview of raytracing building blocks https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-1 - please refer ...

3

You could try to simply make the bounding volumes a bit larger than necessary so that the objects don't cross their boundaries on every move but then again, you would have to rebuild the structure now-and-then anyway. Or, there is Bounding interval hierarchy which tries to address precisely this scenario. Or, the paper by Ingo Wald, Solomon Boulos and ...

2

I'd like to add some practical perspective to this. Let me preface that I'm operating on limited information here: I don't know how many objects you are dealing with. I don't know what exactly your acceleration structure is used for. Frustum culling? Ray tracing? Collision detection between objects in the BVH? Going forward I'm going to assume you are ...

2

Not 3D as such, but it seems in 1963 Ivan Sutherland's seminal "Sketchpad" (and wikipedia) had instancing. eg. See "Chapter VI RECURSIVE FUNCTIONS" of the 2nd reference. IIRC somewhere there's a video of it in action - it made me annoyed as to how some of today's vector drawing tools don't seem to be able to do some of what sketchpad ...

1

I agree with @xasp's answer, but to understand why you would do it like that: Checking for ray-circle intersections is not the most expensive in terms of cpu-time required, but a ray-aabb intersection is frighteningly faster. Apparently Shirley found that in his scenes, checking the leaf's AABB first led to better results, because in a "sparse bounding ...

1

It does indeed do exactly what you described. Have a close look at how the bvh is constructed, it is a passed a list of concrete shapes that implement hittable, e.g. xy_rect, sphere, etc. The base cases for the recursive bvh construction create leaf nodes that directly reference the concrete shapes that make up the scene. bvh_node::bvh_node( const std::...

1

Bounding Volumes A bounding volume is for example an Axis-Aligned Bounding-Box (AABB), a generaal Bounding-Box not aligned with the major axes or a Bounding-Sphere. They differ in how much memory they take (e.g. a sphere takes only 4 floats, AABB 6 floats) how good they enclose the object's geometry how fast are the related computations (mainly intersection ...

1

In your example of a BVH cell partitioned along the x axis, if the ray is going left to right (increasing x), then the cell with the lower x comes first; but if it's going right to left (decreasing x), then the cell with the higher x comes first. So, you can look at the sign of the x component of the direction vector to determine which cell to test first.

1

You gave the formula as: $$Cost(cell) = C_t + \frac{S_L}{S_{Cell}} \times N_L \times t_i + \frac{S_R}{S_{Cell}} \times N_R \times t_i$$ (You put $r_i$ at the right-hand end, but I assume that was a typo.) There's a more general form of this formula $$Cost(cell) = C_t + \sum_{k\ \in\ K} \frac{S_k}{S_{Cell}} \times N_k \times t_i$$ where $K$ is the set ...

1

Regarding optimizations: Could you calculate the min and max corners in modelspace beforehand? Then you could check on the CPU-side the NDCs of these two points and skip the processing of the whole mesh if it is outside of the desired range. This needs only two matrix-vector multiplications on cpu side. And since for rigid bodies these two points do not ...

Only top voted, non community-wiki answers of a minimum length are eligible