| View previous topic :: View next topic |
| Author |
Message |
banshee777
Member
Joined: 10 Feb 2005
Posts: 37
|
 Posted: Thu May 12, 2005 11:44 pm Post subject: Need help with collision system |
 |
|
I've given up about two months ago. Now i'm back to attack the city again.
'm trying to get triangle collision going. I've tried many sites but i can't seem to understand it.
Could someone write a little pieace of code or try to expalin in very simple terms as in steps.
1. You need a normal
2. Vector
3. Check if triangle is in the way, how far?
4. If hit then stop
I know there are more thing's required.
I did collision with box's, but it's not good for games, since your walking on invisible box, then plane of a triangle. |
|
| Back to top |
|
 |
IndrekSnt
Member
Joined: 20 Apr 2005
Posts: 16
Location: Estonia
|
|
| Back to top |
|
|
Mr.Fletcher
DeleD PRO user
Joined: 07 Aug 2004
Posts: 1772
Location: Germany
|
| Posted: Fri May 13, 2005 4:40 pm Post subject: |
|
|
He could, but setting up Newton so that he can use it properly for his player character is probably more difficult than getting done a reay-triangle collision code.
_________________
Behold! The DeleD Wiki! Please help us expanding it 
DeleD on IRC |
|
| Back to top |
|
|
Signot
Member
Joined: 18 Feb 2005
Posts: 25
Location: Canada
|
| Posted: Wed May 18, 2005 3:16 pm Post subject: Polygon Collision Detection |
|
|
Well I know from experience that trying to find the proper resource on the web can be a daunting task. So I will try and help you out by showing how to do simple line-polyogn collision detection. I use this in my engine right now, but I will be switching to sphere-plane sweep test in the future. May I will write a tut on that sometime
Anyways, here is the listing for my code
| Code: |
//Determines if the ray passed in intersects the polygon
//in some way or another
bool polygon_t::rayIntersects( vec3_t start, vec3_t end )
{
vec3_t ray;
vec3_t intersectionPt;
float t;
//Vectors are constructed from start ----------> end
ray = end - start;
//Check to see if the normal and the ray are parallel to
//each other, if so, return no intersection
//This is a simple DOT product of the two vectors. The property
//of a DOT product is that it gives you 0 if the vectors are parallel
//otherwise it returns a value != 0. If you were to take the ARCCOS
//of this value, it would give you the angle between the vectors
if ( (n^ray) == 0.0f )
return false;
//now we have to calculate the variable t, which gives
//us the position on the line which intersects
//with the plane (polygon) we are interested in.
//A parametric line equation. Remember the ^ symbol is
//the DOT product of 2 vectors.
//variable d is the ploygons d calcualted during its construction
// d - the distance from the origin to the plane
// n - the normal of the ploygon
// start, ray - vectors
//The t represents where on the line the intersection occurs.
//t should be in teh range [0,1]. 0 being the BEGINNING of the line
//and 1 being the END of the line. If t is outside of this range
//then its beyond the vector we are considering.
t = -((n^start) + d)/(n^ray);
//Check range of var t
if ( t < 0.0f || t > 1.0f )
return false;
//calculate the actual intersection point
//because t is a parameter for our line, we use its
//value to find out intersection point along our vector
intersectionPt = start + (ray*t);
//call our function to check if we actually HIT
//INSIDE the polygon
return pointIntersects(intersectionPt);
}
//Returns TRUE if the point lies within the bounds
//of the polygon. The point must be inside the polygon for
//this test to return true. It takes the angle between the
//point and all the vertices making up the polygon and adds
//them up. If the angle summs to approx 180 degrees, then
//the point lies inside, otherwise, it doesn't.
bool polygon_t::pointIntersects( vec3_t point )
{
double dAngle;
vec3_t v0, v1, v2;
v0 = (point - v[0]);
v1 = (point - v[1]);
v2 = (point - v[2]);
v0.normalize();
v1.normalize();
v2.normalize();
dAngle = acos(v0 ^ v1) +
acos(v1 ^ v2) +
acos(v2 ^ v0);
if ( fabs(dAngle - 2* PI) < 0.99f )
return true;
return false;
}
|
Well I hope this helps you out. If you still are having trouble, just leave a post and perhaps I can clarify something up for you.
Good luck out there! |
|
| Back to top |
|
|
Paul-Jan
Site Admin
Joined: 08 Aug 2004
Posts: 3066
Location: Lage Zwaluwe
|
| Posted: Thu May 19, 2005 4:39 am Post subject: |
|
|
Do you use a LUT for that acos? If not, that is probably the most expensive point-in-triangle test around  You might want to google for MollerTrumbore97 (which is what most of us are using), but you can get faster too, especially if you are willing to keep some more state.
Then again, your current implementation probably works fine. |
|
| Back to top |
|
|
Signot
Member
Joined: 18 Feb 2005
Posts: 25
Location: Canada
|
| Posted: Thu May 19, 2005 5:57 am Post subject: ACOS |
|
|
| Ya it's not the most efficient instruction around. But it gets the point across I will definitely take a look for faster methods. |
|
| Back to top |
|
|
Signot
Member
Joined: 18 Feb 2005
Posts: 25
Location: Canada
|
| Posted: Wed May 25, 2005 3:41 pm Post subject: |
|
|
Hey again!
Thanks for the previous tip about that collision detection speed up. I found the MollerTrumbore97 paper and implemented it into my code. I find this method is just as easy to implement and gave me a speed boost. Thanks for the tip. Anyways, I thought I would post my code for anyone that is interested.
| Code: |
//Newest polygon collision uses MollerTrumbore97 algorithm
bool polygon_t::rayIntersects(vec3_t start, vec3_t end) {
double EPSILON = 0.000001;
vec3_t edge1, edge2, tvec, pvec, qvec;
vec3_t bary;
double det, inv_det;
double t;
vec3_t dir;
dir = end - start;
//find vectors for two edges sharing vert0
edge1 = v[1] - v[0];
edge2 = v[2] - v[0];
//Cross product
pvec = dir * edge2;
det = edge1 ^ pvec;
if ( det > -EPSILON && det < EPSILON )
return false;
inv_det = 1.0 / det;
//calculate distance from vert0 to ray origin
tvec = start - v[0];
bary.y = (tvec ^ pvec)*inv_det;
if ( bary.y < 0.0 || bary.y > 1.0 )
return false;
//preprase to test V parameter
qvec = tvec*edge1;
//calculate v parameter and test bounds
bary.z = (dir ^ qvec)*inv_det;
if ( bary.z < 0.0f )
return false;
bary.x = 1.0f - bary.y - bary.z;
if ( bary.x < 0.0f )
return false;
//t at which ray intersects triangle
t = (edge2 ^ qvec)*inv_det;
if ( t > 0.0f && t < 1.0 )
return true;
return false;
} |
In my code, I have overloaded the operators ^ and *. The ^ is the equivalent to the DOT product and the * is equivalent to the CROSS product.
Thanks for the tip again Paul-Jan  |
|
| Back to top |
|
|
Paul-Jan
Site Admin
Joined: 08 Aug 2004
Posts: 3066
Location: Lage Zwaluwe
|
| Posted: Wed May 25, 2005 6:20 pm Post subject: |
|
|
| Good work, Signot |
|
| Back to top |
|
|
Signot
Member
Joined: 18 Feb 2005
Posts: 25
Location: Canada
|
| Posted: Fri May 27, 2005 4:12 pm Post subject: Better Collision System |
|
|
I found an old paper that I used in a previous engine. The collision system implements a Collide and Slide system. With this, you character can be surrounded by a bounding ellipsoid. This ellipsoid is used to detect collision detections in the world. The paper describes how you would implement this feature and then use the fact that a sphere is nice and round to achieve the "rolling" effect. This means you can walk across different heights in your world, and not have to worry about getting stuck on corners. It's a smooth implementation and works really well. I recently just implemented this into my new engine and it works like a charm.
here's the reference:
http://www.peroxide.dk/papers/collision/collision.pdf
Enjoy |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
