Jump to content

  • Log In with Google      Sign In   
  • Create Account

BVH translation and rotation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Bacterius   Crossbones+   -  Reputation: 9280

Like
0Likes
Like

Posted 02 December 2012 - 05:55 AM

Hello,
I want to improve my path tracer by being able to add, remove, move and rotate meshes in real time (to add interactive physics). The geometry of the mesh will never be modified. But it would seem that every time I do any of those operations, I need to rebuild the BVH, which takes time and is annoying.

I was wondering if I could somehow avoid this by computing an intermediate BVH for every mesh (in object space, so it would be constant), and rotate the BVH (or the ray) using the mesh's object-to-world matrix for BVH traversal? And I could also then combine those multiple different BVH's into a single one somehow by translating and rotating the bounding boxes. This would cut down the cost of mesh manipulation to essentially zero, but it sounds too good to be true - can it be done?

Again, I only care about insertion, deletion, translation and rotation of meshes. I will not modify the geometry in any way, so I think this could be a sufficient condition for this optimization, since after all, each triangle in the mesh will be translated and rotated equally, so the bounding boxes will be too.

Thanks!

Edited by Bacterius, 02 December 2012 - 05:56 AM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


Sponsor:

#2 ZBethel   Members   -  Reputation: 603

Like
0Likes
Like

Posted 02 December 2012 - 11:36 AM

I have never written a path tracer, so take my response with a grain of salt. I don't see why you couldn't have a child node in your BVH be another BVH with a transform associated with it. In fact, that makes the most sense to me and I would venture to guess that production systems do exactly that. What complicates things, like you said, is if you are morphing geometry or otherwise changing/rebuilding the BVH for a dense object with millions of triangles. You should give it a shot and let us know how it goes!

Edited by ZBethel, 02 December 2012 - 11:37 AM.


#3 Bacterius   Crossbones+   -  Reputation: 9280

Like
0Likes
Like

Posted 02 December 2012 - 09:23 PM

Thanks, I will try when I get the time. I feel it is theoretically sound, though I'll need to find a way to introduce the per-mesh transform in a consistent way since I want to be using the BVH on the GPU. Perhaps using a hybrid tree with the first few levels consisting of BVH+transform nodes..

Additional input is welcome!

Edited by Bacterius, 03 December 2012 - 02:01 AM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS