Custom Collision Detection

#1 Michael,

If you set your objects or preferably object to have a collision-method of "custom" then T2D will redirect the detection processing to "t2dSceneObject::onCustomCollisionDetection()". Search for "T2D_DETECTION_CUSTOM" in "t2dPhysics.cc" for this.

In your custom t2dSceneObject which might just be inheriting from a standard static sprite or preferably a whole new type of object, just override the virtual "onCustomCollisionDetection()" method. For examples of the code needed to populate a collision structure, see the other ones such as "t2dPhysics::sweptPolyToPolyCollision()". You can find the calls to the stock ones in the same location as specified above.

This also applies to collision-response in an identical manner with the exception that you're look for "T2D_RESPONSE_CUSTOM" and a call to "t2dSceneObject::onCustomCollisionResponse()". Again, for an idea of what to do in this function, look at existing functions such as "t2dPhysics::resolveBounceCollision()".

Back to collision-detection though; in your function, it's best to initially execute...

// Invalidate Collision.
    pCollisionStatus->mValidCollision = false;

    // Set Collision Integration Interval.
    pCollisionStatus->mFullTimeStep = elapsedTime;

... to invalidate the collision before you begin and to also set the full time-step to the specified elapsed-time.

If you don't find a collision then you can simply return "false" at this point and no collision will be indicated. If however you find a collision then you are required to calculate a few details and populate the collision-info further.

You must fill out the following info:

- Source contact point(s)
- Destination contact point(s)
- Contact point count (1 or 2)
- Collision normal (normalised)
- Real collision time (a real portion of "pCollisionStatus->mFullTimeStep")
- Normalised collision time (0->1) with respect to the "pCollisionStatus->mFullTimeStep".
- Overlapped flag.
- Valid Collision Flag.

These above are set as follows...

pCollisionStatus->mSrcContacts[0] = ???
pCollisionStatus->mDstContacts[0] = ???
pCollisionStatus->mContactCount = ???
pCollisionStatus->mCollisionNormal = ??? (normalised)
pCollisionStatus->mCollisionTimeReal = ???
pCollisionStatus->mCollisionTimeNorm = ???
pCollisionStatus->mOverlapped = ???
pCollisionStatus->mValidCollision = true;

If you're using multiple objects and inheriting from an existing object and want to use a single-edge of a polygon (which is a bit of a nasty way to do it) then you'll have to ensure that your polygon definition is fixed so that you can identify the single edge that you want to use to check collisions against. This is a really nasty way to do it though.

It would be much easier to create a whole new object and simply add in a few calls to specify the landscape surface. You'll need to ensure that you define the surface points in local-space only. This way, you can easily utilise some of the existing functionality in the "t2dPhysics" class to check for collisions against objects. The thing to watch out for here is that custom collision-detection is for "source" objects only. This means that you'll always get the collision of the landscape touching or overlapping an object so swept collisions are probably not something you'll be interested in.

Quote:But the source comments in t2dPhysics.cc are a bit sparse

You're kidding right? There are comments on almost every line. I know you're kidding. ;)

- Melv.

#2 Melv,

thanks for the long response. I fear I gotta bug you a bit more.

Quote:
If you set your objects or preferably object to have a collision-method of "custom" then T2D will redirect the detection processing to "t2dSceneObject::onCustomCollisionDetection()". Search for "T2D_DETECTION_CUSTOM" in "t2dPhysics.cc" for this.

In your custom t2dSceneObject which might just be inheriting from a standard static sprite or preferably a whole new type of object, just override the virtual "onCustomCollisionDetection()" method. For examples of the code needed to populate a collision structure, see the other ones such as "t2dPhysics::sweptPolyToPolyCollision()". You can find the calls to the stock ones in the same location as specified above.

Ok, until here I figured it out myself. My custom object (boldly called t2dTerrain) is derived directly from t2dSceneObject. Since this afternoon it uses a vertex array to render itself which works quite well performance-wise.

Quote:
If you're using multiple objects and inheriting from an existing object and want to use a single-edge of a polygon (which is a bit of a nasty way to do it) then you'll have to ensure that your polygon definition is fixed so that you can identify the single edge that you want to use to check collisions against. This is a really nasty way to do it though.

Oh, no nasty things for me. I just completely rewrote the object to remove all nasty things. :)

Quote:
It would be much easier to create a whole new object and simply add in a few calls to specify the landscape surface. You'll need to ensure that you define the surface points in local-space only. This way, you can easily utilise some of the existing functionality in the "t2dPhysics" class to check for collisions against objects. The thing to watch out for here is that custom collision-detection is for "source" objects only. This means that you'll always get the collision of the landscape touching or overlapping an object so swept collisions are probably not something you'll be interested in.

I am listening! Whole new object is created, add a few calls to specify the landscape surface? What do you mean with that?
Using local-space should not be a problem. My initial question actually was what existing functionality there is to serve my needs. But some more insight on the whole collision detection system is very appreciated.

Ok, so what I need is a function to test (or helps me testing) circles and polygons against this line-strip. But I don't understand this time-axis and vertex-axis stuff. Maybe I have to take a good look at some of the references in t2dPhysics.h. I have never done collision detection other than rectangle to rectangle. Would it be sufficient to check every line in the collision polygon if it intersects the line strip of the landscape?

How is it done with t2dTileLayers? From what I see in the code every tile has its own t2dPhysics object. Doing this here too would be not so hard I think, but I seems that it would reintroduce the huge overhead that I just got rid of by NOT using 800 single objects for one screen of landscape. (btw, does a 40x40 tile map really contain 1600 tile objects? This sounds like massive waste of memory within a structure invented to fight waste of memory? Or is there something like an internal tileset that prevents redundancy behind the scene?)

I think, I'll sleep over this and maybe read the MethodOfSeparatingAxes.pdf.

Thanks again, Melv!

-Michael

Oh, almost forgot :)

Quote:
You're kidding right? There are comments on almost every line. I know you're kidding. ;)

Sounds like someone still gets the shivers when thinking back to writing certain portions of code ;)
Yes, there are lots of comments! I just don't understand them. I know the words but...

#3 Funny; I'm working on something very similiar to this right now. I was planning to add a new t2d object to handle the drawing of the landscape; basically, a version of sprite that allows you to specify the sprite's verticies and UV coordinates. Right now I've been using t2dshapes, which seem to work pretty well even for collision. But obviously they don't provide texture, hense the new object.

Anyway, I've tried duplicating the sprite class, and get my new class to compile fine. I can even create the objects in the console fine as well, but as soon as I try to use them I get a crash in ApplyFieldSelectedValue. Accourding to the doumentation, you need to assign any new object types a GUID address, but that enumeration doesn't seem to exist in the code anymore. How did you manage to create your new object? Am I just not finding the enumeration, or has the method changed completely?

#4 Melv,

could you please explain this to me further:

Quote:
The thing to watch out for here is that custom collision-detection is for "source" objects only. This means that you'll always get the collision of the landscape touching or overlapping an object so swept collisions are probably not something you'll be interested in.

This seems to be the core of my confusion. What's the difference between a source and a destination object? Does this have to do with collision send and receive flags? I got the feeling I am asking something really stupid :(

-Michael

#5 Michael,

Sorry I've not got back to you, just not enough damn time!! Bah!!

Quote:This seems to be the core of my confusion. What's the difference between a source and a destination object?

During the scene-integration, each scene-object has its "integrateObject()" called. In this function, the standard "t2dSceneObject" deals with many updating features, one of which is the collision-detection.

Let's assume we have two objects called "A" and "B".

In the collision-detection update for object "A" (assuming collisions are on for this object), the object will sweep for collisions along the path in which it intends to move. Now assuming it is either already overlapped or it will hit object "B" during the move, we have the definition you're asking for. The object that is moving (object "A" is the source object and the object that is either being overlapped or will be hit during a move (object "B") is the destination.

Let's assume that after this has been actioned, the scene continues to process the objects and it then comes to what was previously called the destination (object "B"). It will now process this in the same way and again, assuming it is moving and has collision detection active, it moves in such a way as to collide with the previously discussed object "A". In this case we're current integrating the source object "B" and it's hitting the destination object "A" so the roles are reversed.

So as you can see above, potentially two collisions could happen during a single scene-update involving two scene-objects. This is a bi-directional collision model where each object takes on either role of "source" or "destination".

To now answer your question; If you look at the collision detection system, you can see that it is setup to process a "source" object colliding with "destination" object. The complexity comes from the different types of collision systems used by each object. For instance, we've got swept-circles and swept-polygons currently. If you create a new type of collision-detection and want to be able to do all combinations with existing types, you'll need to implement those combinations yourself. This can be very complex and cumbersome.

There are interface methods that allow abstract collision-frame collisions but I decided that there wasn't a need for such an interface and I also wanted to at least attempt to keep the speed up.

What T2D does provide is a callback when your custom-collision object has collisions-active. In this case, it ends up calling the functions described in my previous post and here's the issue. What it can't do is make your custom-collision object the "destination" object as the "source" object has no idea on how your objects collision-detection works and so can't check itself against your custom-object.

What can happen however, is that it can call the "t2dSceneObject::onCustomCollisionDetection()" function on your object to allow it to process collisions against the known collision-types in the system e.g. circle/polygon. You also have the opportunity to utilise some of the existing code to help you make your collision-detection work.

What all this waffle means is that custom collision detection only works for "sent" collisions e.g. objects that are the "source", not for "received" collisions e.g. objects that are the "desintation".

Hey, are you going to the TGB bootcamp? If so, I'll sit down with you and go through it in detail if you wish. :)

Hope that helps more than it confuses,

- Melv.

#6 Thanks a lot Melv! You are great!

Yes this helps. Knowing that source object is the moving one and "sends" to the destination is the important info. So if my terrain object has turned collision-send on (and collision-receive off by default), and the objects I want to collide with the terrain have at least collision receive turned on, everything should work like my custom collision detection was one of the stock modes?

I'm looking forward to experimenting with this when I have time in the evening. Found the t2dPhysics::castLine() routines earlier today. Looks like those will help me too.

Quote:
Hey, are you going to the TGB bootcamp? If so, I'll sit down with you and go through it in detail if you wish. :)

I'd love to but being a student I don't think it's in my budget to fly to America :(

Thanks again, Melv!

-Michael

#7 Cool, I got some progress here. CLAMP response nearly works correctly. There are still issues with overlapping, multiple contact points and this mCollisionTimeReal (why is it set to -mFullTimeStep?). When set to RIGID response the test-object does not react at all. Yet, this is start. Maybe, if I really get this to work right, I'll write some docs for TDN.

The downside: its 3:24 AM :-P

-Michael

#8 Hey Melv,

I've got some questions.

1) What does t2dPhysics::findSupportPoints() do? It looks useful somehow, to calculate contact points properly.

2) Where should the contact points be? From the code, it does not look, like they should be, where the polys intersect and they seem to be used to solve overlaps.

3) There can only be 1 or 2 contact points? If there are more, how do I decide which to use?

4) What is mCollisionTimeReal exactly?

5) Gonna have lunch now. :)

-Michael

#9 Michael,

1) Not easy to explain in detail without pictures! This routine (in the context of "findContactPoints()") attempts to calculate the contact points. For these stock routines to work for you, each object will need two convex polygons, something which I think you don't have. It essentially calculates the contact points based upon two types of collisions, point->edge and edge-edge. I'm not sure it's going to be that useful for what you'll need so I'll cut short the explanation there.

2) The number of contact points is either 1 for a point->edge collision and 2 for an edge->edge collision. The contact point for a point->edge collision is the vertex of one object (even if that is within the other object e.g. an overlapped collision) and an edge of the other object parallel with the collision normal. The contact points for an edge->edge collision is more complex to explain but it can be either a vertex/edge, vertex/vertex or edge/edge combo on one object and the same on another. Essentially though, a contact point isn't necessarily the point of contact for the object, in the case of an overlap, it's the point/edge of the object but the object being overlapped does indicate the point of interpenetration. In the case of a non-overlap, the contact for both objects should approximately be the same at some point in forward-time. The overlap confuses things though. Overlaps can be caused through precision issues (although I've tried to reduce that case) or that the objects have simply been positioned in such an overlap.

3) Don't go there! Dealing with 1 contact is easy, 2 is problematic and is a step-changed from 1 contact. Going to n contacts means you're going to have to purchase some collision/physics books! To be honest, dealing with more than a single contact can get pretty involved and I try to avoid it where possible. The essence of the problem is how to deal with all these contacts; simultaneously or serially?

4) "mCollisionTimeReal" is a copy of the incoming elapsed-time that was used to sweep for collisions. It's essentially a copy of the "elapsedTime" coming in from the scene-update. You can use this to calculate normalised collision-time (0->1) and to refer back to what this normalised time actually means. It also means you don't have to know what the update-interval was, you've got everything you need in the collision structure.

5) Enjoy!

- Melv.

#10 1) Ok, I'll leave it

2,3)
So, is there a way to deal with a situation like this properly?

Maybe averaging the collision points? Or just only consider the more "severe" collision? (I'll try the second approach)

I don't fully understand what you write in 2).

Quote:
The contact point for a point->edge collision is the vertex of one object (even if that is within the other object e.g. an overlapped collision) and an edge of the other object parallel with the collision normal.

How can a point by a vertex and an edge? Does this mean, the contact point is the world position of the penetrating vertex for the destination object and the projection of that vertex onto the penetrated edge on the source object?

I'll have a look at the other case later.

4) So I don't have to modify it, right?

5) Thanks!

#11 Michael,

Quote:So, is there a way to deal with a situation like this properly?

It depends on what you mean by this. Are you talking about the collision-response now? If you're talking about the contact-points then there are two, one for each corner vertex.

With regards to the point->edge collision; this only applies to a partial overlap e.g. an object has partially, not totally interpenetrated another object. Imagine a triangle interpenetrating a square in such a way that a single vertex of the triangle penetrates the square through an edge. In that situation, the triangle (as the source object) would have a single contact-point (which is the vertex point) and the square (as the destination object) would have a single contact-point at the edge (perpendicular to the edge-normal). The seperation of these contacts can be used to calculate the minimum seperation needed to move the objects apart. How you seperate the objects is another issue.

Here are a couple of images I just put together to try to show this situation...


4) You need to do what I put in the first codeblock on my post of "Feb 22, 2006 15:40 GMT". Just fill it in for later reference.

5) No problem. :)

- Melv.