detecting whether a point lies in a triangle
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.
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.
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.
Here are two important methods, I am wondering why I made the normalize more complicated than it needed to be... oh well.
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 triangleHere 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);
}
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...
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.
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.
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).
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).
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
Post: #6Jake 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! ...
Post: #7kelvin 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.
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.
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.
Possibly Related Threads...
| Thread: | Author | Replies: | Views: | Last Post | |
| detecting 2 touches, is order of touch significant? | sefiroths | 4 | 9,342 |
Sep 30, 2011 07:29 AM Last Post: @iOS_blog |
|
| Ray-Triangle Intersection | mikey | 2 | 3,576 |
Aug 15, 2010 05:11 AM Last Post: mikey |
|
| Detecting OS and Mac version | xiotex | 2 | 2,721 |
Nov 14, 2009 03:02 PM Last Post: xiotex |
|
| Detecting window focus events | Coyote | 2 | 2,989 |
Oct 23, 2009 03:01 PM Last Post: Coyote |
|
| Triangle Intersection Tests | merrill541 | 1 | 2,522 |
Feb 6, 2009 12:13 PM Last Post: scgames |
|