## detecting whether a point lies in a triangle

dave05
Unregistered

Post: #1
Hey everyone,

I'm getting into the collision detection area of my game now, and because of the way my sprites are set up, and the general shape of the players' sprite, I'm in need of an algorithm which detects whether a point lies in an arbitrary triangle...

the actual triangle will be
{(playerX+52.0, playerY+52.0),
(playerX+77.0, playerY+127.0),
(playerX+127.0, playerY+127.0)}

now, the detection also has to work for any rotation about (playerX, playerY), the center of the sprite. (the sprite consists of 4 such triangles for each corner of the 256x256 sprite rectangle).

I know this is largely math-based, and that's why I'm so intimidated by this hurdle... I'm using AGL/OpenGL... Is there a way to simply check whether the given point lies on the texture somewhere where alpha != 0? If so, I'd rather go in that direction, but I have a feeling that support isn't built-in.
Member
Posts: 508
Joined: 2002.05
Post: #2
Here is my code from GL Golf to detect whether or not a point is in a triangle -

ip is the intersection point were checking and vtx0-3 are the triangles vertexes. epsilon gives us room for rounding errors.

Code:
```tip.x = -ip.x + vtx0.x;            //puts the difference of ip  and the first vertex into a temperary vector             tip.y = -ip.y + vtx0.y;             tip.z = -ip.z + vtx0.z;             vec0 = [self normalize:(tip)];        //normalizes the vector                          tip.x = -ip.x + vtx1.x;             tip.y = -ip.y + vtx1.y;             tip.z = -ip.z + vtx1.z;             vec1 = [self normalize:(tip)];                          tip.x = -ip.x + vtx2.x;             tip.y = -ip.y + vtx2.y;             tip.z = -ip.z + vtx2.z;             vec2 = [self normalize:(tip)];                      /*Adds the angles between the vectors here*/             dAngle = acos([self dot: vec0 plus: vec1]) + acos([self dot: vec1 plus: vec2]) + acos([self dot: vec2 plus: vec0]);                          if( fabs( dAngle - 2*3.1415926 ) < epsilon )    //if the angle is about 360 degrees we are in the triangle```

Here are two important methods, I am wondering why I made the normalize more complicated than it needed to be... oh well.
Code:
```- (VECTOR) normalize:(VECTOR)a {     VECTOR result;     float distance;          result.x = a.x;     result.y = a.y;     result.z = a.z;          distance = sqrt(result.x*result.x + result.y*result.y + result.z*result.z);          result.x = result.x/distance;     result.y = result.y/distance;     result.z = result.z/distance;          return result; } - (float) dot:(VECTOR)a plus:(VECTOR)b {     return (a.x * b.x) + (a.y * b.y) + (a.z * b.z); }```
dave05
Unregistered

Post: #3
hey jake, thanks for the response, you've got a good looking software company website up; you're where I hope to be.. soon.

I actually wrote a routine myself, that uses less calls to acos, asin, etc. which i believe might make it slightly faster... that being said, I'm really uncomfortable making my computer do tons and tons of calculations...

Code:
```int        UI_CheckForCollisionP1 (Position enemy_position) {     float    xOffset = enemy_position.h - player1_position.h;     float    yOffset    = enemy_position.v - player1_position.v;          float    r = sqrt(xOffset*xOffset + yOffset*yOffset);     float    degree_range;     float    enemyTheta;          if (r < kR1 || r > kR2)         return -1;     // no collision.  enemy_position is too far from or too close to crosshair          degree_range = 13 * ((r-kR1) / (kRadiusRange));          if (yOffset > 0) {         enemyTheta = asin(yOffset / r);         if (xOffset < 0)             enemyTheta = 180-enemyTheta;     }     else if (xOffset < 0)         enemyTheta = 180+atan(yOffset / xOffset);     else         enemyTheta = 360-acos(xOffset / r);          if ((abs(enemyTheta - (player1_rotation + 45)) % 90) < degree_range)     {         return (enemyTheta - (player1_rotation + 45)) / 90; // for you forumers, there are 4 possible quadrants to be "damaged" or "hit," at 4 // corners of a rect.  i return an int from 0 to 3 indicating which one was hit.  I hope.     }          return -1; }```

now, how do trigonometric calls work anyways? Am I correct to assume that they just return an approximate value from a look-up table? I know some of my math is probably wrong and I'll probably get some kooky results when i test this, but I was sort of proud of this method so I had to post it.
Member
Posts: 508
Joined: 2002.05
Post: #4
now, how do trigonometric calls work anyways? Am I correct to assume that they just return an approximate value from a look-up table? I know some of my math is probably wrong and I'll probably get some kooky results when i test this, but I was sort of proud of this method so I had to post it.[/quote]

I think they calculate it every-time but I'm not positive. Thats good you wrote your own method, its always better to do that than just use someone elses (unless you want to borrow something REAL big like a framework lol).
Member
Posts: 469
Joined: 2002.10
Post: #5
Anybody remember how to do barycentric coords? I seem to be a bit fuzzy on my math.

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Member
Posts: 142
Joined: 2002.11
Post: #6
Jake Wrote:now, how do trigonometric calls work anyways? Am I correct to assume that they just return an approximate value from a look-up table? I know some of my math is probably wrong and I'll probably get some kooky results when i test this, but I was sort of proud of this method so I had to post it.

Jake Wrote:I think they calculate it every-time but I'm not positive. Thats good you wrote your own method, its always better to do that than just use someone elses (unless you want to borrow something REAL big like a framework lol).

I'm pretty sure it's calculated every time, using a series approximation of the function. For example, take the Taylor series of Sin(x)

Sin(x) = x/1! - x^3/3! + x^5/5! - x^7/7! ...
Tasnu Arakun
Unregistered

Post: #7
kelvin Wrote:Anybody remember how to do barycentric coords? I seem to be a bit fuzzy on my math.

The advantage of using barycentric coordinates would be that you do not need any trigonometric functions. On the other hand you'll need a few matrix operations and you might have to write those by yourself. Still, a few multiplications takes much less time than trigonometry.

To calculate the barycentric coordinates, given a triangle abc and a point p, one must find a transform from (a, b, c) to ((0,0), (1,0), (0,1)). The barycentric coordinates u, v, w are defined as:

p = u * a + v * b + w * c
u + v + w = 1

So to find the barycentric coordinates you have to do the following calculations (i hope i got it all right). Note that you'll have to do a Matrix Inversion. Oh, and one more thing. ( x | y ) is how i write the dot product.

I = ( b - a, c - a ) ^ -1
( u, v ) = ( p - a | I )
w = 1 - u - v

If any of u, v and w is outside the intervall [0, 1] then the point P is outside the triangle.

Here's a page as well. The best one i could find with 5 minutes of Googling.
Member
Posts: 260
Joined: 2005.05
Post: #8
I use barycentric coordinates, or rather a reformulation of it. I express the point as a linear combination of two sides of the triangle, with the vertex as origin. With the triangle a,b,c that is written

p = a + ab*i + ac*j

(Yes, this is barycentric coordinates, only slightly rewritten.) In 3D, this is an overdetermined equation system which is rather straightforward to solve. Then you check:

i > 0
j > 0
i+j < 1

Then you are inside the triangle.

Another approach is to take three cross products, ab x ap, bc x bp, ca x cp. If all are in the same direction, same side of the abc plane, then the point is in the triangle.