Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 12 Oct 2000
Offline Last Active Dec 05 2012 06:38 AM

Posts I've Made

In Topic: Find nearest triangle to a point (not ray)

21 August 2012 - 10:05 AM

A KD tree is a good choice. Just recurse down the tree as follows:
  • If the node is a leaf, just scan over the triangles and find the closest one. Return the index of the triangle and the distance to it.
  • If the current node is not a leaf, figure out which side of the split plane that contains the query point, and recurse down that side. You will get the index and distance to the closest triangle in that subtree. Then, check if the distance to the nearest triangle is closer to the query point than the distance between the query point and the split plane. If it is closer, there is no need to recurse down the other side of the KD tree and you can just return. Otherwise, you will need to recurse down the other way too, and return whichever result is closer.
Hope that was clear enough.

Keep in mind that the closest point on your mesh could be an edge or a point, and in that case you will have a tie ... this may or may not be a problem depending on what you want to do with the triangle index you get.

In Topic: Acceleration structures for photon mapping on a GPU

13 April 2012 - 09:24 AM

I said you recurse on the two subtrees, but actually no recursion is necessary when building the tree, since you know in advance which regions you will have to sort at each level. Though I suppose you do have to do some kind of recursion (i.e. have a stack) when you traverse the tree. But usually you need some sort of local data structure for collecting the photons anyway, so I don't see why adding a small stack (of depth log(SCENE_MAX_PHOTONS)) would be difficult.

In Topic: Acceleration structures for photon mapping on a GPU

12 April 2012 - 06:02 PM

I'm not really familiar with OpenCL, but in my implementation I just sorted all the photons along one axis (say the x axis). Then the middle photon (call it n) becomes the root of the tree. You can then recurse, sorting 0..n-1 and n+1 .. N-1 along the next axis (in this case y). That way the whole KD Tree building algorithm reduces to sorting, which presumably has some fast OpenCL implementations.

In Topic: Acceleration structures for photon mapping on a GPU

12 April 2012 - 03:16 PM

You don't store the photons only in the leaf nodes. Every node of the tree IS a photon - i.e. each node of the tree has exactly one photon. The number of nodes in your tree is equal to SCENE_MAX_PHOTONS and you can store them in a preallocated array.

In Topic: Acceleration structures for photon mapping on a GPU

12 April 2012 - 02:55 PM

You can make a KD tree structure with fixed storage requirements if you use a balanced KD tree. This is well described in Henrik Wann Jensen's book (it's probably in his papers too if you don't have the book). The key is that when you split your photons, you always split on the median (so that there are an equal number of photons left and right branches of the tree). The resulting KD tree is a complete binary tree, and its structure is known completely beforehand. As a result, you don't need any variable size storage, or even pointers.