algorithm choice

Starting easy.
dmt
Posts: 2
Joined: Mon Jan 12, 2015 2:10 am

algorithm choice

Postby dmt » Thu May 14, 2015 9:35 pm

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?

papaboo
Posts: 41
Joined: Fri Jun 21, 2013 10:02 am
Contact:

Re: algorithm choice

Postby papaboo » Mon May 18, 2015 6:20 am

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.

dmt
Posts: 2
Joined: Mon Jan 12, 2015 2:10 am

Re: algorithm choice

Postby dmt » Mon May 18, 2015 10:59 pm

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?)

papaboo
Posts: 41
Joined: Fri Jun 21, 2013 10:02 am
Contact:

Re: algorithm choice

Postby papaboo » Tue May 19, 2015 12:05 pm

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. ;)

rtpt
Posts: 6
Joined: Wed May 20, 2015 1:17 pm

Re: algorithm choice

Postby rtpt » Thu May 21, 2015 2:39 pm

Hallo papaboo, what i have seen is, that the quality of bvh depends strongly
on the scene itself.

papaboo
Posts: 41
Joined: Fri Jun 21, 2013 10:02 am
Contact:

Re: algorithm choice

Postby papaboo » Tue May 26, 2015 7:54 am

That's true for any acceleration structure though.

papaboo
Posts: 41
Joined: Fri Jun 21, 2013 10:02 am
Contact:

Re: algorithm choice

Postby papaboo » Tue May 26, 2015 7:56 am

Regarding general BVH quality On Quality Metrics of Bounding Volume Hierarchies might be an interesting read.

atlas
Posts: 26
Joined: Thu Apr 16, 2015 12:01 am

Re: algorithm choice

Postby atlas » Sun May 31, 2015 1:53 am

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


Return to “My First...”

Who is online

Users browsing this forum: No registered users and 1 guest