I see that your sort function is using a recursive implementation of Quicksort to order the photons. With 40,000 photons you’re going to have recursion 16 levels deep in the best case, and probably more than that in real life; too much recursion will cause the stack overflow. There may be a way to increase the stack size in Java, but I’m not familiar with how to do that. The best solution would probably be to rewrite the function in an iterative way (google for “iterative quicksort”). You may also want to do this with your other recursive functions, like find.

Also, just for reference, there are actually faster algorithms for computing medians than sorting the list and picking the middle element. See here for a simple one that runs in ‘expected’ O(n) time (it’s randomized), and here for discussion of some more algorithms, including ones that execute in worst-case O(n) time. (Most of these are also written recursively, but you can convert them to iterative implementations if you still have stack problems.)

Regarding the use of alternative shapes like ellipsoids or cylinders, one easy way to do it would be to draw points out of the kd-tree in a sphere large enough to encompass the shape you actually want, and then perform a second pass on just those results to throw out the extras. However, you should be able to extract points in any shape that you can easily intersect with a plane, as that will let you find out which branches of the kd-tree to descend into. For cylinders, I assume you’re thinking of capped (not infinite) ones; you can intersect these with a kd-tree plane by using CSG techniques (let the cylinder be the CSG intersection of an infinite cylinder and two capping planes). Ellipsoids are just scaled spheres, so you can define a coordinate system in which the ellipsoid is a sphere and transform the kd-tree plane into that coordinate system to do the intersection.

BRDFs are tricky. What they return is a reflectance (ok…technically, a
reflectance *density*), which is a wavelength-dependent scalar (i.e. a
function from wavelength to reflectance). However, most rendering
systems just bin wavelength into ‘red’, ‘green’, and ‘blue’. So, the
BRDF would return a 3-vector giving the average reflectances over the
red, green, and blue wavelength ranges.

Hello, I’ve been trying to implement a photon map in java, but I’ve run into some problems. Unlike Jensen’s implementation I stored references to each node explicitly. My implementation is based off of his psuedo-code.

I usually get a StackOverflow exception in the sort method when using 40,000 photons, but not always. The probability of crashing increases with the number of photons I’m using. I’m guessing this is because I allocate too many integers when the sorting method calls itself. I don’t know though, I can’t really debug an error like this and I don’t know that particulars of the stack.

The algorithm’s pretty simple: I find the splitting plane for which the bounding box is the greatest, sort the photons according to that plane, and then pick the median out of the middle.

At the bottom you’ll see two internal classes dealing with the collection of photons. I was originally going to change the gathering algorithm from a sphere to a cylinder, but in Jensen’s code he uses the search radius to find potential photons. I don’t know how that’d work out using a cylinder. I used the distance to the plane defined by the normal and the distance to the point to see if it’s contained within the cylinder. None of this is actually added yet, mind you. Jensen also mentions using an ellipsoid to collect photons, but I have no idea how one would do that.

So, I basically have two questions; Is the balancing done correctly (and is there a faster sorting algorithm out there than quick sort), and how can I implement other photon gathering algorithms?

Also, the whole check of the incident direction is messed up somehow. I haven’t tried to debug that though, so I don’t expect anyone to know what’s wrong with it.

Oh, and I’m lost as far BRDF’s. Does it return a scalar, a color, or a direction?

The code should be self-explanitory:

Any help would be greatly appreciated.