ingemar
Site Admin
Joined: 03 Jan 2007
Posts: 113
|
 Posted: Wed Mar 04, 2009 10:08 pm Post subject: Point in triangle |
 |
|
On the last lecture, I showed this code:
| Code: | typedef unsigned int uint32;
#define in(a) ((uint32&) a)
bool checkPointInTriangle(const VECTOR& point,
const VECTOR& pa,const VECTOR& pb, const VECTOR& pc)
{
VECTOR e10=pb-pa;
VECTOR e20=pc-pa;
float a = e10.dot(e10);
float b = e10.dot(e20);
float c = e20.dot(e20);
float ac_bb=(a*c)-(b*b);
VECTOR vp(point.x-pa.x, point.y-pa.y, point.z-pa.z);
float d = vp.dot(e10);
float e = vp.dot(e20);
float x = (d*c)-(e*b);
float y = (e*a)-(d*b);
float z = x+y-ac_bb;
return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000);
}
|
which had shown up on a game programming mailing list the same morning. I have tested the code and it works. But how?
I figured that out too. It splits one side of the triangle onto the other, to calculate a vector that is orthogonal to the first and pointing into the half plane where the other is. The same is done the other way. (e10 and e20.) This gives us an easy way to check the point "point" towards these two sides. Then a different, slightly different test can be done for the third side. (The same would work but would cost a few more calculations.)
A nice way to test. I wouldn't convert to integer as in the last line though. It makes it range dependent, so the methods may fail if used for very small triangles. |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
