# Pragma

Member

260

395 Neutral

• Rank
Member
1. ## Find nearest triangle to a point (not ray)

A KD tree is a good choice. Just recurse down the tree as follows:[list] [*]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. [/list] 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. ## Acceleration structures for photon mapping on a GPU

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. ## Acceleration structures for photon mapping on a GPU

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. ## Acceleration structures for photon mapping on a GPU

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. ## Acceleration structures for photon mapping on a GPU

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.

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. ## Fast way to calculate 2D signed distance field

Also I have an implementation of 3D signed distance transform in GPU Gems 2, chapter 8. You can find it here: ftp://download.nvidia.com/developer/GPU_Gems_2/CD/Copy%20of%20Index.html The code is in dispmap/distance.cpp.
8. ## Fast way to calculate 2D signed distance field

The fastest CPU algorithm I know is the one described in this paper: http://perso.telecom-paristech.fr/~bloch/ANIM/Danielsson.pdf It is linear in the number of pixels (unlike the algorithm you describe, which is quadratic).

10. ## ddx/ddy functions, software rasterization, and texture filtering

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. ## Range of distance in Chebyshev's inequality?

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 ([url="http://uwspace.uwaterloo.ca/handle/10012/3640"]http://uwspace.uwaterloo.ca/handle/10012/3640[/url]).
12. ## BRDF / BTDF pdf

[quote name='hick18' timestamp='1307878863' post='4822362'] So do I just leave it as is but without the divide? [/quote] Yes. [quote name='hick18' timestamp='1307878863' post='4822362'] I thought I had to dived by the pdf to "boost" up cases where there might be say only 5% reflection and 95% refraction, and the 5% route happended to be chosen, giving almost black in those cases. But now I realise I dont need to boost it becuase Im not actually multiplying the result by the fresnel factor, im just using the fresnel to bias a route of 100% refraction or 100% reflection. [/quote] Exactly.
13. ## 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. ## 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. ## Directx ddx/ddy

[quote name='hick18' timestamp='1302629486' post='4797572'] Thankyou. Where did you learn this? [/quote] 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 [url="http://www.gamedev.net/topic/478820-derivative-instruction-details-ddx-ddy-or-dfdx-dfdy-etc/"]http://www.gamedev.net/topic/478820-derivative-instruction-details-ddx-ddy-or-dfdx-dfdy-etc/[/url].