Thread: RE: [Algorithms] Tris intersection
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Steve W. <Ste...@im...> - 2000-07-24 03:05:00
|
I think the best way to find if the triangles intersect is to take the 3 vertexes from each triangle one at a time and use it to divide the other triangle up into three separate triangles (geometry now not math). If the sum of the area of the three triangles is equal to the area of the whole triangle then the triangles intersect (OK, put away your thought compass and do the math). You will need to do this 6 times, 3 times for each triangle... Once you find a vertex where the areas are equal then they intersect and you won't have to do the rest of them. It's impossible to illustrate with ansii characters so in your mind draw a line from point p which represents one of the vertices from the other triangle to each vertex a, b, and c to divide the triangle into 3 triangles...add up the sum of the three triangles, apc, bpa, cpb and compare it to the area of abc. If They are equal then the point is inside, or on the triangle (be sure to allow some margin of error for rounding). Sound like a plan? a intersects a does not intersect |\ |\ | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ | . \ | \ . | p \ | \ p | \ | \ |___________\ |___________\ c b c b If it solves analytic geometry problems to relax after 10 hours of straight TFC and Q3A-CTF then it's, Rockn-Roll > -----Original Message----- > From: Jeffrey C [mailto:pl...@as...] > Sent: Sunday, July 23, 2000 5:54 PM > To: gda...@li... > Subject: [Algorithms] Tris intersection > > > Hi, > > Anyone could tell me a quick way to know whether 2 triangle > that lie on the same plane > intersect each other? > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), > here is some example that the > triangles intersect each other. > > |\ /| > | / B| > | -\-- > |___\ > A > > /| > / | > / B| > / | > / |\ | > /--| \- > |A \ > ---- > > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Andrew S. <as...@di...> - 2000-07-24 03:39:06
|
You could just use Moller's (excellent) triangle/triangle intersection code - no point in re-inventing the wheel - andrew http://www.ce.chalmers.se/staff/tomasm/code/ > -----Original Message----- > From: Steve Wood [mailto:Ste...@im...] > Sent: Sunday, July 23, 2000 9:59 PM > To: 'gda...@li...' > Subject: RE: [Algorithms] Tris intersection > > > I think the best way to find if the triangles intersect is to > take the 3 > vertexes from each triangle one at a time and use it to > divide the other > triangle up into three separate triangles (geometry now not > math). If the > sum of the area of the three triangles is equal to the area > of the whole > triangle then the triangles intersect (OK, put away your > thought compass and > do the math). You will need to do this 6 times, 3 times for each > triangle... Once you find a vertex where the areas are equal > then they > intersect and you won't have to do the rest of them. > > It's impossible to illustrate with ansii characters so in > your mind draw a > line from point p which represents one of the vertices from the other > triangle to each vertex a, b, and c to divide the triangle into 3 > triangles...add up the sum of the three triangles, apc, bpa, > cpb and compare > it to the area of abc. If They are equal then the point is > inside, or on > the triangle (be sure to allow some margin of error for > rounding). Sound > like a plan? > > a intersects a does not intersect > |\ |\ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | . \ | \ . > | p \ | \ p > | \ | \ > |___________\ |___________\ > c b c b > > > If it solves analytic geometry problems to relax after 10 > hours of straight > TFC and Q3A-CTF then it's, > Rockn-Roll > > > > -----Original Message----- > > From: Jeffrey C [mailto:pl...@as...] > > Sent: Sunday, July 23, 2000 5:54 PM > > To: gda...@li... > > Subject: [Algorithms] Tris intersection > > > > > > Hi, > > > > Anyone could tell me a quick way to know whether 2 triangle > > that lie on the same plane > > intersect each other? > > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), > > here is some example that the > > triangles intersect each other. > > > > |\ /| > > | / B| > > | -\-- > > |___\ > > A > > > > /| > > / | > > / B| > > / | > > / |\ | > > /--| \- > > |A \ > > ---- > > > > > > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Robert D. <RD...@ac...> - 2000-07-24 10:21:15
|
This is not valid for all cases, since it is possible to have two
intersecting triangles where none of the vertices of either triangle are in
the other one ... like this
a
|\
| \
x---+--\------y
| | \ /
| | \ /
| | \/
| | /\
| | / \
| | / \
| | / \
| | / \
| |/ \
| / \
| /| \
| / | \
|/ b---------------c
z
in which case no point will give you the same area when used to make three
more triangles.
The only guaranteed way I know is to test each edge to see if the other
triangle is completely 'outside' it, which simply requires three
cross-products for each case, and you must test all six edges to be certain
that you haven't missed one. I'm sure there must be an easier way, but I've
never bothered to figure one out.
Robert
-----Original Message-----
From: Steve Wood [mailto:Ste...@im...]
Sent: 24 July 2000 03:59
To: 'gda...@li...'
Subject: RE: [Algorithms] Tris intersection
I think the best way to find if the triangles intersect is to take the 3
vertexes from each triangle one at a time and use it to divide the other
triangle up into three separate triangles (geometry now not math). If the
sum of the area of the three triangles is equal to the area of the whole
triangle then the triangles intersect (OK, put away your thought compass and
do the math). You will need to do this 6 times, 3 times for each
triangle... Once you find a vertex where the areas are equal then they
intersect and you won't have to do the rest of them.
It's impossible to illustrate with ansii characters so in your mind draw a
line from point p which represents one of the vertices from the other
triangle to each vertex a, b, and c to divide the triangle into 3
triangles...add up the sum of the three triangles, apc, bpa, cpb and compare
it to the area of abc. If They are equal then the point is inside, or on
the triangle (be sure to allow some margin of error for rounding). Sound
like a plan?
a intersects a does not intersect
|\ |\
| \ | \
| \ | \
| \ | \
| \ | \
| \ | \
| \ | \
| \ | \
| . \ | \ .
| p \ | \ p
| \ | \
|___________\ |___________\
c b c b
If it solves analytic geometry problems to relax after 10 hours of straight
TFC and Q3A-CTF then it's,
Rockn-Roll
> -----Original Message-----
> From: Jeffrey C [mailto:pl...@as...]
> Sent: Sunday, July 23, 2000 5:54 PM
> To: gda...@li...
> Subject: [Algorithms] Tris intersection
>
>
> Hi,
>
> Anyone could tell me a quick way to know whether 2 triangle
> that lie on the same plane
> intersect each other?
> Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2),
> here is some example that the
> triangles intersect each other.
>
> |\ /|
> | / B|
> | -\--
> |___\
> A
>
> /|
> / |
> / B|
> / |
> / |\ |
> /--| \-
> |A \
> ----
>
>
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
|
|
From: Steve W. <Ste...@im...> - 2000-07-25 02:27:05
|
Oh...your right...checking to see if any of the line segments intersect would be a better test. R&R > From: Robert Dibley [mailto:RD...@ac...] > > This is not valid for all cases, since it is possible to have two > intersecting triangles where none of the vertices of either > triangle are in > the other one ... like this > > a > |\ > | \ > x---+--\------y > | | \ / > | | \ / > | | \/ > | | /\ > | | / \ > | | / \ > | | / \ > | | / \ > | |/ \ > | / \ > | /| \ > | / | \ > |/ b---------------c > z > > in which case no point will give you the same area when used > to make three > more triangles. > > The only guaranteed way I know is to test each edge to see if > the other > triangle is completely 'outside' it, which simply requires three > cross-products for each case, and you must test all six edges > to be certain > that you haven't missed one. I'm sure there must be an > easier way, but I've > never bothered to figure one out. > > Robert > > -----Original Message----- > From: Steve Wood [mailto:Ste...@im...] > Sent: 24 July 2000 03:59 > To: 'gda...@li...' > Subject: RE: [Algorithms] Tris intersection > > > I think the best way to find if the triangles intersect is to > take the 3 > vertexes from each triangle one at a time and use it to > divide the other > triangle up into three separate triangles (geometry now not > math). If the > sum of the area of the three triangles is equal to the area > of the whole > triangle then the triangles intersect (OK, put away your > thought compass and > do the math). You will need to do this 6 times, 3 times for each > triangle... Once you find a vertex where the areas are equal > then they > intersect and you won't have to do the rest of them. > > It's impossible to illustrate with ansii characters so in > your mind draw a > line from point p which represents one of the vertices from the other > triangle to each vertex a, b, and c to divide the triangle into 3 > triangles...add up the sum of the three triangles, apc, bpa, > cpb and compare > it to the area of abc. If They are equal then the point is > inside, or on > the triangle (be sure to allow some margin of error for > rounding). Sound > like a plan? > > a intersects a does not intersect > |\ |\ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | \ | \ > | . \ | \ . > | p \ | \ p > | \ | \ > |___________\ |___________\ > c b c b > > > If it solves analytic geometry problems to relax after 10 > hours of straight > TFC and Q3A-CTF then it's, > Rockn-Roll > > > > -----Original Message----- > > From: Jeffrey C [mailto:pl...@as...] > > Sent: Sunday, July 23, 2000 5:54 PM > > To: gda...@li... > > Subject: [Algorithms] Tris intersection > > > > > > Hi, > > > > Anyone could tell me a quick way to know whether 2 triangle > > that lie on the same plane > > intersect each other? > > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), > > here is some example that the > > triangles intersect each other. > > > > |\ /| > > | / B| > > | -\-- > > |___\ > > A > > > > /| > > / | > > / B| > > / | > > / |\ | > > /--| \- > > |A \ > > ---- > > > > > > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Robert D. <RD...@ac...> - 2000-07-25 07:58:13
|
Yup, thats what that suggestion from someone else does, in coplanar cases - in fact its quite neat, I wish I'd thought of it. Just test for intersection (total of 9 intersection tests any one of which can return true - very nice if you expect most cases to intersect) and then if still not determined just test if any point of one is in the other, which because there are now no intersections means you only have to test one point of each against the other. Rob -----Original Message----- From: Steve Wood [mailto:Ste...@im...] Sent: 24 July 2000 17:52 To: 'gda...@li...' Subject: RE: [Algorithms] Tris intersection Oh...your right...checking to see if any of the line segments intersect would be a better test. R&R |
|
From: Steve W. <Ste...@im...> - 2000-07-25 17:54:02
|
> From: Robert Dibley [mailto:RD...@ac...] > > Yup, thats what that suggestion from someone else does, in > coplanar cases - > Code word there is coplanar...that's why I brought up the area test since that's what I use in my 3D collision detection, but I'm sooo glad you asked that question; cause now that I think about it I'm not testing for the case where the line is in the same plane...DOH! R&R |
|
From: Robert D. <RD...@ac...> - 2000-07-25 20:11:48
|
In that case go back to the posting which gave the reference, I can't remember where it was to, but the coplanar part was only a small section of the stuff, it was in reality a full blown three dimensional triangle intersection routine. Rob -----Original Message----- From: Steve Wood [mailto:Ste...@im...] Sent: 25 July 2000 18:48 To: 'gda...@li...' Subject: RE: [Algorithms] Tris intersection > From: Robert Dibley [mailto:RD...@ac...] > > Yup, thats what that suggestion from someone else does, in > coplanar cases - > Code word there is coplanar...that's why I brought up the area test since that's what I use in my 3D collision detection, but I'm sooo glad you asked that question; cause now that I think about it I'm not testing for the case where the line is in the same plane...DOH! R&R _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X