Given the points of two triangles, how do I test for intersection?
Thanx

--
David Fontaine     <dav### [at] faricynet>     ICQ 55354965
Please visit my website: http://www.faricy.net/~davidf/

Post a reply to this message

David Fontaine wrote:
> 
> Given the points of two triangles, how do I test for intersection?

Try this:

Find the planes that contain each triangle; if they are parallel (but
not coincident), the triangles do not intersect.

Find the line along which the planes intersect.

Find the part of the line that lies within the first triangle.  If the
line lies out of the triangle, the triangles do not intersect.

Find the part of the line that lies within the second triangle.  If the
line falls out of the triangle, the triangles do not intersect.

If the two resulting line segments overlap, the triangles intersect.
Otherwise, they don't.

Hope this helps,
John

Post a reply to this message

John VanSickle <van### [at] erolscom> wrote:
: Find the line along which the planes intersect.

  What is the equation for the intersection line of two planes?

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Warp wrote:
> 
>   What is the equation for the intersection line of two planes?
> 

Well, I'm making this up on the go, but:

The function for a plane is

x * Normal.x + y * Normal.y + z * Normal.z - Distance = 0

And along the intersection line, the functions of the two planes would be equal,
so the function should be:

F(Plane1) - F(Plane2) = 0

-- 
Margus Ramst

Personal e-mail: mar### [at] peakeduee
TAG (Team Assistance Group) e-mail: mar### [at] tagpovrayorg

Post a reply to this message

"David Fontaine" <dav### [at] faricynet> wrote in
news:392B20F3.726230DD@faricy.net...
> Given the points of two triangles, how do I test for intersection?

Try this page:
http://apodeline.free.fr/FAQ/CGAFAQ/CGAFAQ-6.html#ss6.22


Sebastian Strand
  E-mail: thezeb -at- bigfoot -dot- com
  URL: http://www.zeb.f2s.com/

Post a reply to this message

John VanSickle wrote:

> Try this:
>
> Find the planes that contain each triangle; if they are parallel (but
> not coincident), the triangles do not intersect.
>
> Find the line along which the planes intersect.
>
> Find the part of the line that lies within the first triangle.  If the
> line lies out of the triangle, the triangles do not intersect.
>
> Find the part of the line that lies within the second triangle.  If the
> line falls out of the triangle, the triangles do not intersect.
>
> If the two resulting line segments overlap, the triangles intersect.
> Otherwise, they don't.
>
> Hope this helps,
> John

Wow, sounds like it will take a long time to parse. (I actually want it to
test cubes for intersection, but the faces can be considered two triangles,
and if the faces don't intersect the cubes don't. For the bowl-full-o-cubes
thing...)

--
David Fontaine     <dav### [at] faricynet>     ICQ 55354965
Please visit my website: http://www.faricy.net/~davidf/

Post a reply to this message

On Wed, 24 May 2000 17:22:30 -0500, David Fontaine wrote:
>and if the faces don't intersect the cubes don't. For the bowl-full-o-cubes
>thing...)

Not necessarily true, unless all the cubes are the same size.

If you're intersecting cubes, and they're all the same size, and they're 
axis-aligned, it suffices to check whether any corner of either cube is 
inside the other cube.  If they're not axis-aligned but still the same
size, you can check whether any edge of one cube intersects a face of the 
other cube.  (Likewise, to see if two triangles intersect, it suffices to 
check whether any edge of one triangle intersects the face of the other 
triangle.)

If you're using MegaPOV, you can use trace to determine whether they 
intersect.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
These are my opinions.  I do NOT speak for the POV-Team.

Post a reply to this message

Ron Parker wrote:

> Not necessarily true, unless all the cubes are the same size.

? How can two cubes intersect if their faces never do?

> If you're intersecting cubes, and they're all the same size, and they're
> axis-aligned, it suffices to check whether any corner of either cube is
> inside the other cube.  If they're not axis-aligned but still the same
> size, you can check whether any edge of one cube intersects a face of the
> other cube.  (Likewise, to see if two triangles intersect, it suffices to
> check whether any edge of one triangle intersects the face of the other
> triangle.)

<Data> I assure you the set is sufficiently randomized. </Data>

> If you're using MegaPOV, you can use trace to determine whether they
> intersect.

*opening docs*

--
David Fontaine     <dav### [at] faricynet>     ICQ 55354965
Please visit my website: http://www.faricy.net/~davidf/

Post a reply to this message

Warp wrote:
> 
> John VanSickle <van### [at] erolscom> wrote:
> : Find the line along which the planes intersect.
> 
>   What is the equation for the intersection line of two planes?

Not an equation, but a specification.  This requires a point
(any point that lies along the desired line will do), and a vector.

I would get the vector by taking the cross-product of the normal
vectors of the two original planes.

To find the point, I would find the plane to which this vector
is normal and which contains the origin.  The place where all
three planes intersect is as good a point to use as any (it
happens to be the point on the line that is closest to the
origin).

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message

David Fontaine wrote:
> 
> ? How can two cubes intersect if their faces never do?

If they are the same size, they can't.  If they are different sizes,
then one could be contained entirely within another.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message