Delgine 3D Tools & Content DeleD Community Edition
Forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Need help with collision system

 
This forum is locked: you cannot post, reply to, or edit topics.   This topic is locked: you cannot edit posts or make replies.    DeleD Community Edition Forum Index -> DeleD User Game Projects
View previous topic :: View next topic  
Author Message
banshee777
Member


Joined: 10 Feb 2005
Posts: 37

PostPosted: Thu May 12, 2005 11:44 pm    Post subject: Need help with collision system Reply with quote

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
View user's profile Send private message
IndrekSnt
Member


Joined: 20 Apr 2005
Posts: 16
Location: Estonia

PostPosted: Fri May 13, 2005 4:31 pm    Post subject: Newton Game Dynamics Reply with quote

You could use some of the free physics libraries like:
Open Dynamics Engine (http://ode.org/)
Newton Game Dynamics (http://www.newtondynamics.com/)
Robust and Accurate Polygon Interference Detection (http://www.cs.unc.edu/~geom/OBB/OBBT.html)
Software Library for Interference Detection (http://www.win.tue.nl/~gino/solid/index.html)
Optimized Collision Detection (http://www.codercorner.com/Opcode.htm)
and so on..

But I like Newton, as it is very simple to use and seems to be quite accurate also,
I hope this helps, Thank You..
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
Mr.Fletcher
DeleD PRO user


Joined: 07 Aug 2004
Posts: 1772
Location: Germany

PostPosted: Fri May 13, 2005 4:40 pm    Post subject: Reply with quote

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 Smile
DeleD on IRC
Back to top
View user's profile Send private message
Signot
Member


Joined: 18 Feb 2005
Posts: 25
Location: Canada

PostPosted: Wed May 18, 2005 3:16 pm    Post subject: Polygon Collision Detection Reply with quote

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 Smile

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
View user's profile Send private message Send e-mail Visit poster's website
Paul-Jan
Site Admin


Joined: 08 Aug 2004
Posts: 3066
Location: Lage Zwaluwe

PostPosted: Thu May 19, 2005 4:39 am    Post subject: Reply with quote

Do you use a LUT for that acos? If not, that is probably the most expensive point-in-triangle test around Wink 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. Smile
Back to top
View user's profile Send private message Visit poster's website
Signot
Member


Joined: 18 Feb 2005
Posts: 25
Location: Canada

PostPosted: Thu May 19, 2005 5:57 am    Post subject: ACOS Reply with quote

Ya it's not the most efficient instruction around. But it gets the point across Smile I will definitely take a look for faster methods.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Signot
Member


Joined: 18 Feb 2005
Posts: 25
Location: Canada

PostPosted: Wed May 25, 2005 3:41 pm    Post subject: Reply with quote

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 Very Happy
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Paul-Jan
Site Admin


Joined: 08 Aug 2004
Posts: 3066
Location: Lage Zwaluwe

PostPosted: Wed May 25, 2005 6:20 pm    Post subject: Reply with quote

Good work, Signot Smile
Back to top
View user's profile Send private message Visit poster's website
Signot
Member


Joined: 18 Feb 2005
Posts: 25
Location: Canada

PostPosted: Fri May 27, 2005 4:12 pm    Post subject: Better Collision System Reply with quote

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 Very Happy
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
This forum is locked: you cannot post, reply to, or edit topics.   This topic is locked: you cannot edit posts or make replies.    DeleD Community Edition Forum Index -> DeleD User Game Projects All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum