7
$\begingroup$

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.

  1. What is this polynomial approximation that Amanatides talks about, and how is it to be applied to polygons (espc. triangles)?
  2. Is there any approximation to the problem that will give resonably accurate results (say ±10%) at considerable performance / code simplicity gains?
  3. 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?
$\endgroup$
  • 1
    $\begingroup$ You have no doubt read this already? Would you be open to a montecarlo of say 16 samples? $\endgroup$ – joojaa Jul 15 '16 at 12:21
4
$\begingroup$

Working Towards an Exact solution

Just some quick thought before I must run!

Ok, let us turn the problem on its head. What if one does not calculate the area of the triangle cut by the circle. Instead let's calculate the inverse of this. The area of three segments cut out of the circle. The beauty of this approach is that we can make a single piece of code that we can repeat three times. Of course some of the time the answer will be 0 but that is OK.

enter image description here

Image 1: Let's calculate this problem instead.

Now it turns out we know how to calculate the inverse, it is the segment of a circle. So we can just say that $A_{int}=A_{circle}-A_1-A_2-A_3$.

enter image description here

Image 2: We know this solution.

The formula for the area of a segment is simply $A_{sector}-A_{triangle}$ and that has a well known solution in literature.

So now all you need to do is find the intersections between the edges and the circle in a space centered on the circle, calculate the angle between those and then calculate each segment. And the only special case is if no intersection exists. I dont know if this is fast but at least code should be somewhat easy to implement.

$\endgroup$
  • $\begingroup$ I betcha the size of the arc size can be computed with closest point on line that would make this very neat. $\endgroup$ – joojaa Jul 15 '16 at 13:36
  • $\begingroup$ I love the elegance of this approach. Does it need a special case approach when one of the vertices is inside the triangle? It looks like that could count part of the area twice. $\endgroup$ – trichoplax Jul 16 '16 at 12:25
  • $\begingroup$ @joojaa This can indeed be computed using the sagitta, and there even is an approximate formular for this (Harris and Stocker 1998). See mathworld.wolfram.com/CircularSegment.html $\endgroup$ – David Kuri Jul 17 '16 at 15:33
  • $\begingroup$ @trichoplax Indeed this method would fail if at least one vertex is inside the circle, and I can't guarantee it won't. Still looking for a nice solution there... $\endgroup$ – David Kuri Jul 17 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.