Jump to content
  • Advertisement
Sign in to follow this  
Fibonacci One

kdtree for raytracing

This topic is 4831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone! It's been a while since I've posted here due to some time consuming real life(tm) things. I wonder if anyone remembers me? Anyway, to the topic. I just finished reading Realistic Image Synthesis Using Photon Mapping and I am starting to put together the design and some of the simple bits of code. I believe I have everything prepared except for how to build the kdtree. What I understand about kdtrees so far is that you have a tree where each node contains an object (or multiple objects?), zero to two child nodes, and information about which of the three axes the node is split along (I'll call it the dividing plane). The problem I am having is that I don't understand what to do when I'm adding an object that intersects the dividing plane of some preexisting node. I'd like to have the nodes contain only one object to guarantee I don't just end up with a single node that contains all of the objects in the scene. My problem is that shoving the second object into the first node is the only practical solution I can think of. Does anyone know how to handle this? I have one other question. I would like to create my meshes so that all of the geometry information is stored in one place and all of the instances of this mesh just contain some base location and a pointer to the geometry. The problem I see is that now I'm doing a matrix multiplication for every point in every mesh every time I check to see if a ray intersects it. This is obviously a very bad idea. If I wanted to draw a scene with thousands of copies of the same mesh would I need to just suck it up store them all separately? Thanks, Joe

Share this post


Link to post
Share on other sites
Advertisement
If you partition your mesh, you can translate (and perform other transformations on) that spatial partition to the location of the mesh, and as you traverse it, you only have to transform the triangles you need to perform intersection tests against.

Share this post


Link to post
Share on other sites
Right. I just reread what I said and see I made a mistake. As you said, I wouldn't have to do the multiplication for every single triangle in the mesh every time I sent a ray to intersect it. However, that still leaves me doing a decent amount of multiplications for each ray. I would almost definitely be repeating a lot of these multiplications as well. If this is my only solution I would probably prefer to just make all of the geometry unique and enjoy the extra speed. Memory is cheap nowadays, right? =)

Share this post


Link to post
Share on other sites
Quote:
Original post by Fibonacci One
Right. I just reread what I said and see I made a mistake. As you said, I wouldn't have to do the multiplication for every single triangle in the mesh every time I sent a ray to intersect it. However, that still leaves me doing a decent amount of multiplications for each ray. I would almost definitely be repeating a lot of these multiplications as well. If this is my only solution I would probably prefer to just make all of the geometry unique and enjoy the extra speed. Memory is cheap nowadays, right? =)


I suppose there is another option. You can encompass the mesh within a bounding volume, with its own space partition, and transform only the ray in object space, test for intersection, and transform the resulting intersection point (if any) back in world space. It simplifies the computations.

Share this post


Link to post
Share on other sites
Quote:
Original post by Max_Payne
Quote:
Original post by Fibonacci One
Right. I just reread what I said and see I made a mistake. As you said, I wouldn't have to do the multiplication for every single triangle in the mesh every time I sent a ray to intersect it. However, that still leaves me doing a decent amount of multiplications for each ray. I would almost definitely be repeating a lot of these multiplications as well. If this is my only solution I would probably prefer to just make all of the geometry unique and enjoy the extra speed. Memory is cheap nowadays, right? =)


I suppose there is another option. You can encompass the mesh within a bounding volume, with its own space partition, and transform only the ray in object space, test for intersection, and transform the resulting intersection point (if any) back in world space. It simplifies the computations.


thats the idea, it worked well enough for me.

transforming the ray into object space isnt that big a cost compared to traversing it anyway.

Share this post


Link to post
Share on other sites
Awesome! That sounds so obvious now that you've said it, but I'm certain that I would have just gone with the make all of the geometry unique approach if you had not. Thanks for the idea.

As for the first question. Unless anyone has any better ideas I think I may try just putting objects that intersect the dividing plane into both children. This will be slower when the ray intersects both children, but should prevent any situations where I'm always running at O(n).

Thanks

Share this post


Link to post
Share on other sites
Just do reference objects in both children. You can also keep track of which objects were tested for intersection within this ray tracing test by flipping the value of a boolean (or incrementing an integer) which changes meaning for every ray you trace. That way you can know which objects youve tested before. However, the cost induced on every test might not be beneficial. You'd have to benchmark this small optimization.

Splitting the object in half isn't any faster anyhow, thats for sure.

Share this post


Link to post
Share on other sites
you don't really need to transform the mesh, why would you? you simply transform the ray by the inverse of the objects matrix and test against the original object.. this is probably the most efficent way

Share this post


Link to post
Share on other sites
sorry I didn't notice I just posted the same answer someone else gave lol. I do have to throw my opinion around tho, I have to say I don't like kd-tree partitioning algorithms, it's great for the photon map, but for ray tracing I'd suggest a bvh of hiractical grids. this is a memory hog, but as you say memory is cheap. I find the use of hiractical grids the fastest method I've seen and I've tried many, you want a to combine the two methods because a straight hiractical grid around the entire scene isn't friendly to instancing which is what we want, to store only one copy of each model in the scene. each model is given an hiractical grid, and each grid(bounding rectangle) is placed in the bvh for quick object identification. just stating my opinion on the matter is all.

Tim

Share this post


Link to post
Share on other sites
Quote:
Original post by Max_Payne
Just do reference objects in both children.
Of course =)

Quote:
You can also keep track of which objects were tested for intersection within this ray tracing test by flipping the value of a boolean (or incrementing an integer) which changes meaning for every ray you trace. That way you can know which objects youve tested before. However, the cost induced on every test might not be beneficial. You'd have to benchmark this small optimization.

I think that would only work if you were certain that every single object would be intersected by every single ray. Otherwise you'd need to set the bit for every ray and that would have to be a little impractical. Nice idea though, I may toss it around a bit.

Quote:
Splitting the object in half isn't any faster anyhow, thats for sure.

Haha, yes. Especially the spheres. =)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!