Skip to main content
gamedev.net
🔒 Locked

Triangle intersections

Started by Aardvajk Jul 30, 2007 at 5:09 PM 3 replies 2.4k views
Original Post
Aardvajk
Aardvajk
Never posted in the Math and Physics forum before. Hello. Bearing in mind that I'm a maths idiot and have no understanding whatsoever of the jargon or symbols that you lot use, I'm trying to figure out a simple way of finding out if either two triangles intersect, or failing that, if a point is inside a triangle. All in 2D space (or all on a single plane, if that is what that means). There are thousands of pages about this all over the web, but they all seem to assume a basic understanding of maths that I don't possess. Is it possible for anyone to explain how I can do this in incredibley simple terms, or will I need to improve my maths before I can even begin to attempt this? Thanks in advance.
Zakwayda
Zakwayda
The problem of determining whether two 2-d triangles (or any two 2-d polytopes) intersect is most easily solved (IMO) using the SAT (separating axis test).

This algorithm does get discussed a lot in this forum, but it's simple enough that I'll just sketch out some code here rather than trying to find previous threads on the topic (this will just be typed into the post, and so has not been compiled or tested):

bool test_axis(vector2 axis, vector2 tri1[], vector2 tri2[]){    float min1 = std::min(dot(tri1[0],axis),std::min(dot(tri1[1],axis),dot(tri1[2],axis)));    float max1 = std::max(dot(tri1[0],axis),std::max(dot(tri1[1],axis),dot(tri1[2],axis)));    float min2 = std::min(dot(tri2[0],axis),std::min(dot(tri2[1],axis),dot(tri2[2],axis)));    float max2 = std::max(dot(tri2[0],axis),std::max(dot(tri2[1],axis),dot(tri2[2],axis)));        return max1 >= min2 && max2 >= min1;}bool test_tris(vector2 tri1[], vector2 tri2[]){    for (size_t i = 0; i < 3; ++i) {        vector2 edge = tri1[(i+1)%3] - tri1;        vector2 normal = edge.perp(); // perp(x,y) = (-y,x)        if (!test_axis(normal, tri1, tri2)) {            return false;        }    }    for (size_t i = 0; i < 3; ++i) {        vector2 edge = tri2[(i+1)%3] - tri2;        vector2 normal = edge.perp(); // perp(x,y) = (-y,x)        if (!test_axis(normal, tri1, tri2)) {            return false;        }    }        return true;}

This can easily be extended to cover convex n-gons (rather than just triangles, as in the above example). The algorithm can also be extended to provide contact info (first time of contact, penetration depth and direction, contact manifold, etc.), but that gets a little more complicated.

If you want an explanation (rather than just code), I'd recommend Dave Eberly's papers on the SAT, the 'N Tutorials' paper, and oliii's tutorials and code (gotta run in a moment, so don't have time to provide links right now...).

[Edit: Dave's papers can be heavy on math symbols/terminology, so if you're not as comfortable in that area you might start with the other references I mentioned. (On the other hand, I can say from personal experience that reading Dave's stuff is a good way for the math-uninitiated to get up to speed - 'immersion therapy', if you will :).]
Aardvajk
Aardvajk
Man, are you ever a star. I'm not going to pretend I understand the code you posted, but I've just used it as the basis for some simpler research about these dot product thingies, and managed to implement your algorithm in C# in order to quickly test it.

namespace Lines{    public partial class Form1:Form    {        public Point [] P1=new Point[3];        public Point [] P2=new Point[3];         int Plot=0;        public Form1()        {            InitializeComponent();            P1[0]=new Point(100,100);            P1[1]=new Point(200,300);            P1[2]=new Point(50,200);        }        private void pBox_Paint(object sender,PaintEventArgs e)        {            e.Graphics.FillRectangle(new SolidBrush(Color.Black),0,0,pBox.Width,pBox.Height);            e.Graphics.DrawLine(new Pen(Color.White),P1[0],P1[1]);                e.Graphics.DrawLine(new Pen(Color.White),P1[1],P1[2]);                e.Graphics.DrawLine(new Pen(Color.White),P1[2],P1[0]);                if(Plot==3)                {                e.Graphics.DrawLine(new Pen(Color.White),P2[0],P2[1]);                    e.Graphics.DrawLine(new Pen(Color.White),P2[1],P2[2]);                    e.Graphics.DrawLine(new Pen(Color.White),P2[2],P2[0]);                    if(test_tris(P1,P2)) Text="Intersects";                else                 Text="No";                }            else Text="";        }        private void pBox_MouseDown(object sender,MouseEventArgs e)        {            if(Plot==3) Plot=0;            P2[Plot].X=e.X;            P2[Plot].Y=e.Y;            ++Plot;            pBox.Invalidate();        }        Point perp(Point P)        {            return new Point(-P.Y,P.X);        }        float dot(Point a,Point b)        {            float dp=0.0f;            dp+=(float)a.X*(float)b.X;            dp+=(float)a.Y*(float)b.Y;                        return dp;        }        float min(float a,float b){ return(ab ? a : b); }        bool test_axis(Point axis,Point [] tri1,Point [] tri2)        {            float min1=min(dot(tri1[0],axis),min(dot(tri1[1],axis),dot(tri1[2],axis)));            float max1=max(dot(tri1[0],axis),max(dot(tri1[1],axis),dot(tri1[2],axis)));            float min2=min(dot(tri2[0],axis),min(dot(tri2[1],axis),dot(tri2[2],axis)));            float max2=max(dot(tri2[0],axis),max(dot(tri2[1],axis),dot(tri2[2],axis)));                        return max1>=min2 && max2>=min1;        }        Point sub(Point a,Point b)        {            return new Point(a.X-b.X,a.Y-b.Y);        }        bool test_tris(Point [] tri1,Point [] tri2)        {            for(int i=0;i<3;++i)                {                Point edge=sub(tri1[(i+1)%3],tri1);                Point normal=perp(edge);                if(!test_axis(normal,tri1,tri2)) return false;                }            for(int i=0;i<3;++i)                {                Point edge=sub(tri2[(i+1)%3],tri2);                Point normal=perp(edge);                if(!test_axis(normal,tri1,tri2)) return false;                }                        return true;        }    }    }


Works like a charm. You can click three points to define the second triangle, and so far every test has had the correct result appear in the title bar.

Should be a breeze to convert that back to C++ for the application I need it for.

Thanks muchly indeed and I was suprised to note you'd never had a rating off me before. Thoroughly corrected.
Zakwayda
Zakwayda
Glad it worked, and thanks for the rate++ (although, to be fair, a number of people who frequent this forum would have been able to whip out that code just as easily - I just happened to come along at the right time :-).

Although the code may seem a bit unintuitive, the idea behind the separating axis test is actually pretty simple. The whole thing revolves around the idea of 'projecting' a 2-d or 3-d shape onto a line (the 'axis' in 'separating axis test'). By 'project', we mean something like this:
   -------   |  a  |   | box |   -------   .     .   .     .   .     .<--*-----*--> a line (axis)
Here, a shape (the box) is being projected onto a line. The asterisks demarcate the 'interval of projection' for the box on the given axis.

The separating axis theorem states, in short, that if an axis (infinite line) can be found for which the projections of two convex objects do not overlap, then the objects themselves do not intersect. The separating axis test then reduces, more or less, to testing some number of axes until it can be determined that the objects either do or do not intersect. In the case of triangles in 2-d, the axes to test are the normals to the triangle edges (that is, the vectors perpendicular to the triangle edges). That gives us six axes to test in all, and if you look at the code for the test_tris() function, you can see that this is exactly what's being done.

The other function does the actual work of projecting the triangles onto the axis in question. Here we rely on the properties of the vector dot product to compute, in essence, the locations of the two asterisks in the diagram above. From there we can determine, via simple comparison, whether the projections of the triangles onto that axis do or do not overlap.
Aardvajk
Aardvajk
Well, I appreciate your efforts, but I still have no idea what you are talking about [smile]. I guess maybe I need to start at the beginning of maths again really.

Just been looking through Oliii's tutorials that you mentioned. There's some seriously impressive stuff going on there. I think I need to just work through those one little step at a time and see if anything clicks.

Cheers for all the help.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.