Advertisement Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

395 Neutral

About Pragma

  • Rank
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. In the first approach you create a triangle that is larger than the viewport. It will automatically get clipped to the viewport, so the results will be identical to the method where you render a quad. However, the triangle might be slightly faster on some GPUs. First, you have to transform fewer vertices (though this is almost certainly negligible). Second, in the latter method you send two triangles, which means there is a seam running down the diagonal. Depending on the GPU, it may render pixels along the seam twice. So there might be a slight performance benefit to using a single triangle, but it is probably not noticeable.
  7. Also I have an implementation of 3D signed distance transform in GPU Gems 2, chapter 8. You can find it here: The code is in dispmap/distance.cpp.
  8. The fastest CPU algorithm I know is the one described in this paper: It is linear in the number of pixels (unlike the algorithm you describe, which is quadratic).
  9. Pragma

    Any PhD's in the house?

    It sounds like you should go for the PhD. The fact is that most PhD's don't wind up in academia, especially in a field like computer graphics where so much of the research comes from industry. In fact, if you look at the proceedings of Siggraph or other graphics journals you will see that a huge percentage of the papers come from industry (MSR, NVidia, Intel, Pixar, ...). When you think about it, there are way more PhD graduates than academic positions. Why? A typical professor may create dozen's of new PhD's in his career. How many faculty positions does he create? One: the one he opens up when he retires. So don't worry about being forced into academia, because only those who are really dedicated to staying in academia will make it (and not all of them will). Most PhDs go into industry. If you are interested in research related to game development specifically, I would be wary of game companies. A few of them do good cutting edge research, but many of them are just interested in churning out more titles. It should be clear which ones are which: look at who is producing good papers. If a game company thinks a PhD makes you overqualified, chances are you don't want to work there. Generally a better bet would be companies like Intel or NVidia where researchers generally have more freedom, since they are less constrained by hardware and deadlines. Of course this changes all the time, and the landscape might be quite different by the time you finish. My background: I almost entered PhD studies for computer graphics, but switched to physics at the last minute because I decided I liked it more. I wrote one good paper in computer graphics, and already that was enough to get the interest of game studios and other companies. So my impression is that a PhD can only help you.
  10. You have the right idea. The derivative instructions have to be able to sample the texture coordinates for neighbouring pixels. This is easy when you process 2x2 blocks of pixels in parallel (though you will have to rasterize some extra pixels around the edges of your triangles). In a serial implementation it's a bit trickier - I guess you have to pause execution of the shader when you hit a texture instruction and switch the next pixel, then come back once you have texture coordinates for all 4 pixels in the block. It becomes even trickier once you allow for control flow (what if the other pixels took a different branch and don't ever execute the texture instruction?).
  11. For the code you posted they should be in the range [0,1]. But in principle this doesn't matter - you could use world space distances and the only thing you would need to do is change the minimum variance (from 0.00002 to some scene-dependent number). Incidentally, Chebyshev's inequality still works if you replace the linear distance with any increasing function of distance. You can also combine multiple different functions together to get better results. I think the best results have been achieved using two functions, exp(x) and -exp(-x). This is described in section 4.2 of Andrew's thesis (
  12. Pragma

    BRDF / BTDF pdf

    Yes. Exactly.
  13. Pragma

    BRDF / BTDF pdf

    But from the code it's clear he isn't doing MIS, but Russian roulette sampling. Notice that the pdf he is dividing by has nothing to do with the BRDF being sampled, it's equal to the percentage of light that is reflected by the objects (as opposed to refracted). So dividing by pdf makes no sense.
  14. Pragma

    BRDF / BTDF pdf

    Don't divide by the pdf. Try averaging a few hundred runs of the code that made the image on the right, and you should get something that looks like the picture on the left.
  15. Pragma

    Directx ddx/ddy

    I worked at nvidia for a while (though it was quite some time ago). But it's also been discussed before on this forum, see
  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!