Disk-Disk intersection surface

Disk-Disk intersection surface

Post by Eric Grang » Wed, 09 Jul 2003 00:12:56



Is there some formula/code out there that would compute the surface
of the intersection of two disks?
(of slightly different radiuses, and that can fully overlap).

I have started writing such a function, but it's full of special
cases and surface decompositions (disk slices, triangles, etc.),
and I'm not sure I am confident about the results it gives...

My aim is to use it to compute penumbra textures (for eclipses),
so it would essentially intersect a moon disk with a sun disk,
and use the remaining (visible) sun disk surface to compute lighting
intensity.
Of course, I could always paint the two disks on a huge bitmap and
count color-coded pixels, but that isn't very satisfying. :)

Thanks.

Eric Grange
http://glscene.org

 
 
 

Disk-Disk intersection surface

Post by Hans-Bernhard Broeke » Wed, 09 Jul 2003 00:47:23



> I have started writing such a function, but it's full of special
> cases and surface decompositions (disk slices, triangles, etc.),
> and I'm not sure I am confident about the results it gives...

You need to handle at least 3 cases: enclosure, disconnected areas,
and actual intersection.

Once you know you have an actual intersection, the area you need is
the sum of two disk "cut-offs" (I don't know the true English term for
that...), i.e. the addition of two area formed by a circular arc and a
secant to that circle.  The common secant joins the two areas.

Now all you need is some formula to calculate the area of such a
cut-off.  It's usually done by taking an angular area (angle/2*r^2)
and adding the signed(!) area of a triangle formed by the circle
center and the secant endpoints.
--

Even if all the snow were burnt, ashes would remain.

 
 
 

Disk-Disk intersection surface

Post by Dave Eberl » Wed, 09 Jul 2003 00:48:08



Quote:> Is there some formula/code out there that would compute
> the surface of the intersection of two disks? (of slightly
> different radiuses, and that can fully overlap).

I assume by "surface" you mean the area of intersection.

Let the disk centers be C0 and C1 and the circle radii
be r0 and r1.  Define U = C1 - C0.  The important
numbers here are the length of U, |U|, and the values
|r0+r1| and |r0-r1|.

(1) |U| > |r0+r1| : the disks are disjoint
(2) |U| = |r0+r1| : the disks are just touching, but each outside the other
(3) |r0-r1| < |U| < |r0+r1| : the disks are overlapping, but not full
containment
(4) |U| = |r0-r1| : the disks are just touching, but one inside the other
(5) |U| > |r0-r1| : one disk is strictly contained by the other

For cases (4) and (5), the area is that of the smaller disk.

Case (3) is the most challenging for computing the area.  If
U = (u0,u1), let V = (u1,-u0).  The two circles intersect at
points C0+s*U+t*V for appropriate chosen s and t.  Some
algebra will show that
  s = 0.5*((r0^2-r1^2)/|U|^2 + 1)
and
  t^2 = -(|U|^2-(r0+r1)^2)*(|U|^2-(r0-r1)^2)/(4*|U|^4)
so there are two choices for t.  Call the two points of
intersection P and Q.  The area of intersection is

  Area(Sector(C0,P,Q)) - Area(Triangle(C0,P,Q))
 + Area(Sector(C1,P,Q)) - Area(Triangle(C1,P,Q))

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Disk-Disk intersection surface

Post by Eric Grang » Wed, 09 Jul 2003 02:17:23


Thanks to both of you!

Quote:> I assume by "surface" you mean the area of intersection.

Yep. "Area" *hits head with hammer to get word in*.

After checking my code against your decompositions, I spotted a gross
mistake in my triangle area code... :(

Eric

 
 
 

1. Book/Disk combo; Disk missing files

Last night, I bought "Fractal Programming and Ray Tracing with C++" by
Roger T Stevens.  The back cover stated that the enclosed disk contained
"the listings needed to generate all of the images described in the book".

Well, that's not completely true.  There are a few programs included in
executable for which are NOT included in source code form on the disk, even
though the source is provided in the text.  I'd like to modify these
programs to take advantage of my particular super-VGA card.
card.  

Has anybody taken the time to type in (or scan in) the missing text?  
Specifically, I need the listing to 800proc.cpp, and a couple
of others.

Thanx,

Mike

--
===========================================================================
                        Blasphemy is a victimless crime.

===========================================================================

2. digital nature tools, goes gnarly at res over 320x240

3. Memory (Disk cache, Virtual,Ram Disk)?

4. advanced nurbs tutorial

5. A RAM disk as a scratch disk?

6. Quark Mailing List?

7. -----===== NEED DISK 8 - 3D Studio 4.1 DOS - due to disk corruption =====-----

8. Need help in Surface/surface Intersections

9. surface/surface intersection

10. surface/surface intersection problems (new address)