On Wed, 25 Nov 1998, Tuukka Toivonen wrote:
> On Wed, 25 Nov 1998, Novak Elliott wrote:
>
> >does anyone have some c code for calculating the intersection of two
> >planar polygons - i've found a few on the net but they have been either
>
> Sorry -- no.
>
> But since there has been couple of graphics algorithms questions, I though
> that people might be interested to know that the FAQ for
> comp.graphics.algorithms is fairly nice to check first.
>
> ftp://rtfm.mit.edu/pub/usenet/comp.graphics.algorithms/
also the Graphics Gems series of books are superb for this kind of thing.
And the source code is on the web. I am not sure that the answer to just
this question is in it, though.
...
Anyway, if it is hard to find the code, you might be able to code it
in shorter time than it will take to find it 8-)
I think the following would work:
Consider polygon 1 to be a list of directed, connected line segments and
create a list of those segments. Then intersect all of those lines with
the plane that contains the second polygon. That should give you a list of
intersections. Do the same thing to the other polyogns.
You now have two lists of vertices. The vertices where polyogon 1
intersects plane 2 and the vertices where polygon 2 intersects plane1.
If your polygons are convex each list should contain exactly two items,
but we can't assume that.
What we want is to represent the vertices as points on a parametric line
p = p0 + t dir
calculate dir as the cross product between the two plane normals
dir = plane1.normal X plane2.normal
choose an arbitrary point on either list as p0 and project all points from
both lists onto your new line
t = dot(dir, p - p0)
You now have two new lists. The parameter values for your line where the
first polygon intersects the second plane and vice versa.
Now begins the fun. sort each list in order of increasing value of t.
(The following should work if your polygons don't self-intersect or have
vertices at infinity or something)
Last step but one: create a new list of spans t0 - t1, t2 - t3, t3 - t4
for both lists.
These spans are the line segments where polygon 1 intersects plane 2 -
and vice versa.
Finally, the intersection between the two span lists should be the
span list where polygon 1 intersects polygon 2.
Span lists and binary set operations on span lists are at the
heart of ray tracing CSG models, and I recently wrote a very small ray
tracer, and I could send you the span list and set operation on span lists
code, although it is C++.
...
Anyway, I hope my ideas above are comprehensible ... I haven't tried it,
but I am almost sure it will work. However, parts of it require auxiliary
data structures and the span-set operations are also a few hundred lines
of code which might be why it is hard to find on the web.
Andreas
