<h2>Working Towards an Exact solution</h2>

<p><sup>Just some quick thought before I must run!</sup></p>

<p>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.</p>

<p><a href="https://i.sstatic.net/Ou8QT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Ou8QT.png" alt="enter image description here"></a></p>

<p><strong>Image 1</strong>: Let's calculate this problem instead.</p>

<p>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$. </p>

<p><a href="https://i.sstatic.net/kE7Wa.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kE7Wa.png" alt="enter image description here"></a></p>

<p><strong>Image 2</strong>: We know this solution.</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-07-15T13:36:53.297Z
I betcha the size of the arc size can be computed with closest point on line that would make this very neat.
joojaa
CC BY-SA 3.0
2016-07-16T12:25:00.307Z
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.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-07-17T15:33:36.233Z
@joojaa This can indeed be computed using the sagitta, and there even is an approximate formular for this (Harris and Stocker 1998). See http://mathworld.wolfram.com/CircularSegment.html
David Kuri
CC BY-SA 3.0
2016-07-17T15:34:33.203Z
@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...
David Kuri
CC BY-SA 3.0
2016-07-15T12:57:23.850Z
2016-07-16T12:18:25.760Z
2016-07-16T12:18:25.760Z
joojaa
<p>I am trying to implement <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.6170&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Ray Tracing with Cones (Amanatides 1984)</a>. 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.</p>

<p>The author, unfortunately, does not give a lot of detail about his solution. Here is what he writes on cone-plane intersections:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>And then, after projecting a polygon to the plane perpendicular to the
direction vector of the cone:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>I found <a href="https://stackoverflow.com/questions/540014/compute-the-area-of-intersection-between-a-circle-and-a-triangle">a solution to the problem</a> over at StackExchange. I have ported the code from <a href="https://stackoverflow.com/a/22420313/776142">NowIGetToLearnWhatAHeadIs' answer</a>, 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.</p>

<ol>
<li>What is this <em>polynomial approximation</em> that Amanatides talks about, and how is it to be applied to polygons (espc. triangles)?</li>
<li>Is there any approximation to the problem that will give resonably accurate results (say ±10%) at considerable performance / code simplicity gains?</li>
<li>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?</li>
</ol>

CC BY-SA 3.0
2016-07-15T12:21:18.653Z
You have no doubt read [this](http://stackoverflow.com/questions/540014/compute-the-area-of-intersection-between-a-circle-and-a-triangle) already? Would you be open to a montecarlo of say 16 samples?
joojaa
<raytracing><performance><computational-geometry><compute-shader>
Estimating the area of a triangle-circle intersection
David Kuri
# Estimating the area of a triangle-circle intersection

(Asked by: username_0 on 2016-07-15)

I am trying to implement [Ray Tracing with Cones (Amanatides 1984)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.6170&rep=rep1&type=pdf). 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](https://stackoverflow.com/questions/540014/compute-the-area-of-intersection-between-a-circle-and-a-triangle) over at StackExchange. I have ported the code from [NowIGetToLearnWhatAHeadIs' answer](https://stackoverflow.com/a/22420313/776142), 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?

**Tags:** raytracing, performance, computational-geometry, compute-shader

> **Comments:**
> **username_1**: You have no doubt read [this](http://stackoverflow.com/questions/540014/compute-the-area-of-intersection-between-a-circle-and-a-triangle) already? Would you be open to a montecarlo of say 16 samples?  

---

## 1 answers

### Answer by username_1 on 2016-07-15. Score: 4

## 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](https://i.sstatic.net/Ou8QT.png)](https://i.sstatic.net/Ou8QT.png)

**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](https://i.sstatic.net/kE7Wa.png)](https://i.sstatic.net/kE7Wa.png)

**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.

> **Comments:**
> **username_1**: I betcha the size of the arc size can be computed with closest point on line that would make this very neat.  
> **username_2**: 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.  
> **username_0**: @username_1 This can indeed be computed using the sagitta, and there even is an approximate formular for this (Harris and Stocker 1998). See http://mathworld.wolfram.com/CircularSegment.html  
> **username_0**: @username_2 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...  

---

