I am trying to implement Ray Tracing with Cones (Amanatides 1984). Instead of rays, cones are shot into the scene and intersected with geometry. Since multiple triangles can occupy the cone's aperture, we need to calculate (or rather quickly estimate, since cone tracing makes a lot of approximations anyway) the relative area of the circle that is covered by the triangle. Afterwards, the individual contributions are weighted and summed up.
The author, unfortunately, does not give a lot of detail about his solution. Here is what he writes on cone-plane intersections:
The spread angle and the angle between the ray and plane computed above together indicate how the distance between the center of the circle and the edge of the half plane [sic]. Given this distance, the area of intersection is computed using a polynomial approximation. This completes the intersection calculation for planes.
And then, after projecting a polygon to the plane perpendicular to the direction vector of the cone:
We then must calculate the intersection between the projected polygon and a circle. This can be accomplished by calculating the distance from the center of the circle to each of the edges and then using the circle - half plane intersection estimation mentioned earlier.
I found a solution to the problem over at StackExchange. I have ported the code from NowIGetToLearnWhatAHeadIs' answer, and it works fine, but seems pretty complicated to me. I am working with Compute Shaders, so branching is a bad thing, and the solutions rely heavily on it.
- What is this polynomial approximation that Amanatides talks about, and how is it to be applied to polygons (espc. triangles)?
- Is there any approximation to the problem that will give resonably accurate results (say ±10%) at considerable performance / code simplicity gains?
- Working with GPUs, I am interested in an optimized solution that uses min/max over branching, for example. Maybe something like this already exists. Any luck?