Page **1** of **1**

### algorithm choice

Posted: **Thu May 14, 2015 9:35 pm**

by **dmt**

Is there a current consensus in the year 2015 on the most performant algorithm + data structure for ray acceleration, traversal, and intersection on gpu?

Assumptions:

- Cuda, Windows

- OpenGL 4.x+ gpu

- dynamic scene geometry (topology consistent but could be morphing etc, like an animated character)

- some static scene geometry could be marked

- i can separate ray intersection from material resolution. i just want the ray hits and some data about the local geometry. (e.g. position, normal, uv, surface derivatives)

- scene geometry fits in gpu memory

Is there a generally accepted "go-to" data structure that everyone has settled on now?

### Re: algorithm choice

Posted: **Mon May 18, 2015 6:20 am**

by **papaboo**

The bounding volume hierarchy in one of its many forms.

- Memory requirements can be determined before construction, so no dynamic memory allocations during construction.
- Very fast to construct if you choose to use Morton Codes.
- Can be refitted to dynamic data instead of requiring a complete reconstruction. (Do perform a partial/complete reconstruction once in a while though, otherwise doom on your performance.)
- You can construct a high quality BVH over static scene data, a low quality one on dynamic and combine them via the root node. If this is better strategy then constructing an optimal one once, refitting and doing partial updates I have no idea.

As NVIDIA uses the (Tr|L|S)BVH for OptiX, you can find a lot of papers on the subject on their research page.

### Re: algorithm choice

Posted: **Mon May 18, 2015 10:59 pm**

by **dmt**

Thanks for the reply.

I guess what I was asking for was *which* gpu BVH implementation (data structure, construction and traversal) is recommended for the listed assumptions. Is there a single reference implementation or paper somewhere, that is generally agreed upon as "the best" right now? (Perhaps optix TrBVH?)

### Re: algorithm choice

Posted: **Tue May 19, 2015 12:05 pm**

by **papaboo**

OptiX TrBVH is probably the current state-of-the-art for GPUs. What I don't know though is if they build it on top of a 'normal' BVH or an MBVH.

Either way. The optimization of treelet restructuring should be applicable to both, so maybe you can try it out.

### Re: algorithm choice

Posted: **Thu May 21, 2015 2:39 pm**

by **rtpt**

Hallo papaboo, what i have seen is, that the quality of bvh depends strongly

on the scene itself.

### Re: algorithm choice

Posted: **Tue May 26, 2015 7:54 am**

by **papaboo**

That's true for any acceleration structure though.

### Re: algorithm choice

Posted: **Tue May 26, 2015 7:56 am**

by **papaboo**

Regarding general BVH quality

On Quality Metrics of Bounding Volume Hierarchies might be an interesting read.

### Re: algorithm choice

Posted: **Sun May 31, 2015 1:53 am**

by **atlas**

Depending on your usage, keep in mind some structures/methods are patented (nVidia likes to do this)