Item collision code conundrums
by Joel Baxter · in Torque Game Engine · 04/13/2002 (12:16 am) · 13 replies
Having some difficulty convincing myself that Item::updatePos is doing the right things in a couple of places. Maybe it's late-night mental blockage, maybe not...
Down in the doToughCollision block, there are two important loops. One to do a quick conservative test to bail early if there is no possibility of collision with any of the objects in the working list, and then one more involved test to check for collisions and find out where they occur.
The first of those loops looks like this:
So the first of the two changes I'm pondering is that I believe that the second line should be
In any case, if the box overlap test succeeds, then there's another, presumably more stringent test. mConvex->getPolyList can compare actual surfaces of the working list object against sEarlyOutPolyList. So, what's sEarlyOutPolyList? Previously it was defined as
Note that there is some collision code in player.cc which is very much like this, but it only uses the early-out polylist with that definition once it has determined that the player's new bounding box will still be partially overlapping his original bounding box; there's no such check in this Item code.
My initial impression is that this code should instead define the planes of sEarlyOutPolyList to be the same as testBox, not wBox.
Down in the doToughCollision block, there are two important loops. One to do a quick conservative test to bail early if there is no possibility of collision with any of the objects in the working list, and then one more involved test to check for collisions and find out where they occur.
The first of those loops looks like this:
CollisionWorkingList& eorList = mConvex.getWorkingList();
CollisionWorkingList* eopList = eorList.wLink.mNext;
while (eopList != &eorList) {
if ((eopList->mConvex->getObject()->getType() & mask) != 0)
{
Box3F convexBox = eopList->mConvex->getBoundingBox();
if (testBox.isOverlapped(convexBox))
{
eopList->mConvex->getPolyList(&sEarlyOutPolyList);
if (sEarlyOutPolyList.isEmpty() == false)
break;
}
}
eopList = eopList->wLink.mNext;
}OK, so, first it tests to see if the bounding box of the working-list-object-to-be-tested overlaps with testBox. I'd expect testBox to be a box that includes both the item's bounding box at the beginning of this tick and also the item's bounding box at its desired position for the end of the tick. However, testBox was previously constructed like this:end = pos + mVelocity * time;
collisionMatrix.setColumn(3, end);
Box3F wBox = getObjBox();
collisionMatrix.mul(wBox);
Box3F testBox = wBox;
Point3F oldMin = testBox.min;
Point3F oldMax = testBox.max;
testBox.min.setMin(oldMin + (mVelocity * time));
testBox.max.setMin(oldMax + (mVelocity * time));AFAICT, that places the item's bounding box at its desired end position (the first four lines of that code) and then moves it even further beyond that position to see if that affects the overall min/max values of the box.So the first of the two changes I'm pondering is that I believe that the second line should be
collisionMatrix.setColumn(3, pos);which puts the bounding box in its position at the beginning of this tick (and then the subsequent lines determine how moving it over the course of the tick affects the min/max).
In any case, if the box overlap test succeeds, then there's another, presumably more stringent test. mConvex->getPolyList can compare actual surfaces of the working list object against sEarlyOutPolyList. So, what's sEarlyOutPolyList? Previously it was defined as
sEarlyOutPolyList.clear();
sEarlyOutPolyList.mNormal.set(0,0,0);
sEarlyOutPolyList.mPlaneList.setSize(6);
sEarlyOutPolyList.mPlaneList[0].set(wBox.min,VectorF(-1,0,0));
sEarlyOutPolyList.mPlaneList[1].set(wBox.max,VectorF(0,1,0));
sEarlyOutPolyList.mPlaneList[2].set(wBox.max,VectorF(1,0,0));
sEarlyOutPolyList.mPlaneList[3].set(wBox.min,VectorF(0,-1,0));
sEarlyOutPolyList.mPlaneList[4].set(wBox.min,VectorF(0,0,-1));
sEarlyOutPolyList.mPlaneList[5].set(wBox.max,VectorF(0,0,1));I haven't chased those function calls, but it looks to me like sEarlyOutPolyList is being set up as the six planes enclosing the volume of wBox. If we look at how wBox was defined above, it's the item's bounding box translated to its desired end position. Or, if the fix substituting pos instead of end is applied, then it's the item's bounding box translated to its position at the beginning of this tick. This doesn't seem right in either case... if we're checking for collisions over the entire path of the item through the duration of the tick, we shouldn't be bailing out early once we have only checked for collisions at its end position (or start position).Note that there is some collision code in player.cc which is very much like this, but it only uses the early-out polylist with that definition once it has determined that the player's new bounding box will still be partially overlapping his original bounding box; there's no such check in this Item code.
My initial impression is that this code should instead define the planes of sEarlyOutPolyList to be the same as testBox, not wBox.
#2
In the SDK code, thrown items are created with a random yaw rotation, but the updatePos code assumes an unrotated item when making bounding boxes. It also doesn't take into account that the item might have been scaled.
So it looks like we might want to get rid of the use of collisionMatrix in the doToughCollision block and do the following instead.
To create testBox, something like this:
The other piece of code we'd need to change is the code that makes sBoxPolyhedron for use in the second loop. Currently it looks like this:
---
There are more interesting collision-related things, although I'm not sure yet which if any are problems, in Item::updateWorkingCollisionSet.
The query box is intended to conservatively enclose the space the item might cover in the upcoming tick. So, it starts as the current bounding box of the scaled, rotated item and is then enlarged.
The comments mention "It is assumed that we will never accelerate more than 10 m/s for gravity." (An item's motion is purely controlled by gravity, except on bounces.) So, the velocity at the end of the tick is assumed to be not greater than 10 + the current velocity. In fact the code is even more conservative than that; it assumes that the item could be travelling at 10 greater than the current velocity for the entire tick:
Now here is how the query box is initially created:
Can't explain that. But, onward.
The code then checks to see if the old query box completely contains this new one; if so, there is no need to update the query box, so it bails without changing the query box or updating the working collision list. This seems odd at first. Of course it doesn't necessarily have to modify the query box size in this case, but other objects may have entered the query box since the last time the working list was updated.
The way this is apparently dealt with is that when the working list does get updated, the query box is extended (by twice that "l" variable in all dimensions) before doing the update. So presumably if the item is moving fast and sets its working list and its extended query box, then it slows down so that its path over the next tick has no chance of exiting the previously calculated extended query box... it will continue to test against the same working list without updating it, assuming that the extension of the query box was enough to catch any objects that might come along to collide with it.
But it can still happen that a new object comes along while the item is not updating its working list. As a simple example let's say that an item has its sticky datablock field set, so that it instantly sticks to the terrain where it lands, rather than bouncing. After the item sticks, it is not going to be updating its working collision list anymore, because its possible path over the upcoming tick (i.e. no path at all) will always be contained inside the last extended query box it calculated. Now what if a player comes along and collides with the item? The item won't know. The player object will detect the collision, and in this case maybe the player object will pick up the item and everything will be cool. But in general, it seems like you can't 100% trust an item to detect when stuff collides with it, which could be problematic if the colliding object doesn't do whatever is necessary to manage the collision.
I noticed that the vehicle code does not bother with extended query boxes and checking to see if the query box and working list should be updated... instead, it always updates the query box and working list, each time. The player code on the other hand does the same thing as the item code, which makes me go hmmm.
04/13/2002 (10:22 am)
"But wait, there's more!" as they say.In the SDK code, thrown items are created with a random yaw rotation, but the updatePos code assumes an unrotated item when making bounding boxes. It also doesn't take into account that the item might have been scaled.
So it looks like we might want to get rid of the use of collisionMatrix in the doToughCollision block and do the following instead.
To create testBox, something like this:
F32 displacement = mVelocity * time;
end = pos + displacement;
Box3F testBox = getWorldBox();
Point3F oldMin = testBox.min;
Point3F oldMax = testBox.max;
testBox.min.setMin(oldMin + displacement);
testBox.max.setMin(oldMax + displacement);That sets the endpoint as before (just including that part to show I wasn't suggesting deleting it or anything), then gets the bounding box for the scaled, rotated item at the beginning of this tick and proceeds from there.The other piece of code we'd need to change is the code that makes sBoxPolyhedron for use in the second loop. Currently it looks like this:
collisionMatrix.setColumn(3, pos);
sBoxPolyhedron.buildBox(collisionMatrix, mObjBox);but instead I'd guess we could do this:Box3F scaledObjBox = mObjBox;
scaledObjBox.min.convolve(mObjScale);
scaledObjBox.max.convolve(mObjScale);
sBoxPolyhedron.buildBox(mObjToWorld, scaledObjBox);Any reason why that wouldn't work?---
There are more interesting collision-related things, although I'm not sure yet which if any are problems, in Item::updateWorkingCollisionSet.
The query box is intended to conservatively enclose the space the item might cover in the upcoming tick. So, it starts as the current bounding box of the scaled, rotated item and is then enlarged.
The comments mention "It is assumed that we will never accelerate more than 10 m/s for gravity." (An item's motion is purely controlled by gravity, except on bounces.) So, the velocity at the end of the tick is assumed to be not greater than 10 + the current velocity. In fact the code is even more conservative than that; it assumes that the item could be travelling at 10 greater than the current velocity for the entire tick:
Point3F scaledVelocity = mVelocity * dt; F32 len = scaledVelocity.len(); F32 newLen = len + (10 * dt);So it looks like newLen is the length the item could have travelled at that conservative velocity estimate.
Now here is how the query box is initially created:
Box3F convexBox = mConvex.getBoundingBox(getTransform(), getScale()); F32 l = (newLen * 1.1) + 0.1; // from Convex::updateWorkingList convexBox.min -= Point3F(l, l, l); convexBox.max += Point3F(l, l, l);OK, that's a little weird. We have this outer bound on the length of the item's travel path... and then we add ten percent to it, and then add 0.1 on top of that. I don't know what the attached comment means; I don't see anything relevant to that heuristic in Convex::updateWorkingList. (In the related vehicle code, this same line exists with the comment "fudge factor"... heh.)
Can't explain that. But, onward.
The code then checks to see if the old query box completely contains this new one; if so, there is no need to update the query box, so it bails without changing the query box or updating the working collision list. This seems odd at first. Of course it doesn't necessarily have to modify the query box size in this case, but other objects may have entered the query box since the last time the working list was updated.
The way this is apparently dealt with is that when the working list does get updated, the query box is extended (by twice that "l" variable in all dimensions) before doing the update. So presumably if the item is moving fast and sets its working list and its extended query box, then it slows down so that its path over the next tick has no chance of exiting the previously calculated extended query box... it will continue to test against the same working list without updating it, assuming that the extension of the query box was enough to catch any objects that might come along to collide with it.
But it can still happen that a new object comes along while the item is not updating its working list. As a simple example let's say that an item has its sticky datablock field set, so that it instantly sticks to the terrain where it lands, rather than bouncing. After the item sticks, it is not going to be updating its working collision list anymore, because its possible path over the upcoming tick (i.e. no path at all) will always be contained inside the last extended query box it calculated. Now what if a player comes along and collides with the item? The item won't know. The player object will detect the collision, and in this case maybe the player object will pick up the item and everything will be cool. But in general, it seems like you can't 100% trust an item to detect when stuff collides with it, which could be problematic if the colliding object doesn't do whatever is necessary to manage the collision.
I noticed that the vehicle code does not bother with extended query boxes and checking to see if the query box and working list should be updated... instead, it always updates the query box and working list, each time. The player code on the other hand does the same thing as the item code, which makes me go hmmm.
#3
see here: www.garagegames.com/index.php?sec=mg&mod=forums&page=result.thread&qt=4618
related ...?
04/13/2002 (10:42 am)
And the vehicle crashes when it encounters a static item...see here: www.garagegames.com/index.php?sec=mg&mod=forums&page=result.thread&qt=4618
related ...?
#4
Lemme pop over to that thread for further discussion of that crash case.
04/13/2002 (11:08 am)
Shouldn't be related to my last paragraph about the difference in the vehicle query box calculations... I don't think that updating the working list more frequently could cause a crash vs. non-crash difference in behavior.Lemme pop over to that thread for further discussion of that crash case.
#5
with my door object the collision is working but when I rotate my door or move it the collision does not know
what is the best way to perform this update? as
ive been using a updateWorkingCollisionSet I have in there where I call
should I be more concerned with the buildConvex?
am I one the right track here?
thanks ahead of time :)
04/13/2002 (3:47 pm)
Joel? maybe I can ask you a question?with my door object the collision is working but when I rotate my door or move it the collision does not know
what is the best way to perform this update? as
ive been using a updateWorkingCollisionSet I have in there where I call
Box3F Convex::getBoundingBox(const MatrixF& mat, const Point3F& scale) constand then I call
void Convex::updateWorkingList(const Box3F& box, const U32 colMask)is this appropriate? will this not rotate the current convex based on my matrix? if this is the one stolen from the list representing my door
should I be more concerned with the buildConvex?
am I one the right track here?
thanks ahead of time :)
#6
04/13/2002 (5:13 pm)
Well, let me come over to your thread now and see what's up. :-)
#7
The original Item::buildPolyList code looks like this:
The comment there is not strictly true if you account for the fact that the item may be rotated. This doesn't really matter if your items are approximately the same size in all dimensions, but for long thin items it might.
I think you could do something like this to take item rotation into account:
04/13/2002 (9:58 pm)
More schtuff.The original Item::buildPolyList code looks like this:
static MatrixF IMat(1);
bool Item::buildPolyList(AbstractPolyList* polyList, const Box3F&, const SphereF&)
{
// Collision with the item is always against the item's object
// space bounding box axis aligned in world space.
Point3F pos;
mObjToWorld.getColumn(3,&pos);
IMat.setColumn(3,pos);
polyList->setTransform(&IMat, mObjScale);
polyList->setObject(this);
polyList->addBox(mObjBox);
return true;
}The comment there is not strictly true if you account for the fact that the item may be rotated. This doesn't really matter if your items are approximately the same size in all dimensions, but for long thin items it might.
I think you could do something like this to take item rotation into account:
static MatrixF xlateXform(1);
bool Item::buildPolyList(AbstractPolyList* polyList, const Box3F&, const SphereF&)
{
// Collision with the item is always against the item's object
// space bounding box axis aligned in world space.
// Split transform into rotation matrix and translation matrix.
MatrixF rotXform = getTransform();
Point3F pos;
rotXform.getColumn(3, &pos);
rotXform.setColumn(3, Point3F(0, 0, 0));
xlateXform.setColumn(3, mPos);
// Get our axis-aligned object space box.
Box3F objectSpaceBounds = getObjBox();
// Enlarge it as necessary to account for item rotation.
rotXform.mul(objectSpaceBounds);
// Specify the translation and scaling for the box we're about to set.
polyList->setTransform(&xlateXform, getScale());
// Note the associated object.
polyList->setObject(this);
// Set the axis-aligned bounding box.
polyList->addBox(objectSpaceBounds);
return true;
}
#8
For the "real" collision test, after the early conservative tests pass, the Item code uses an ExtrudedPolyList to represent the path of the item's axis-aligned bounding box over the course of the tick.
Turns out that if the item does not move at all, then rather than just taking the shape of the unmoving bounding box (as I was assuming), the ExtrudedPolyList becomes nothing at all, and therefore cannot collide with anything.
Not sure if this is intentional or not. The result is that when an item is motionless, it can't detect collisions with other things; instead, other things have to take responsibility for detecting collision with the item. As mentioned above, for the current item behaviors this works out fine, as the only moving object interested in item collisions (Player) does indeed take responsibility for checking for them.
04/21/2002 (1:51 pm)
Another random tidbit...For the "real" collision test, after the early conservative tests pass, the Item code uses an ExtrudedPolyList to represent the path of the item's axis-aligned bounding box over the course of the tick.
Turns out that if the item does not move at all, then rather than just taking the shape of the unmoving bounding box (as I was assuming), the ExtrudedPolyList becomes nothing at all, and therefore cannot collide with anything.
Not sure if this is intentional or not. The result is that when an item is motionless, it can't detect collisions with other things; instead, other things have to take responsibility for detecting collision with the item. As mentioned above, for the current item behaviors this works out fine, as the only moving object interested in item collisions (Player) does indeed take responsibility for checking for them.
#9
04/21/2002 (7:02 pm)
Your research explains a lot about the behaviour I was seeing with my item-based ball objects - collision behaviour that can only be described as "erratic".
#10
In the code that generates the test box for the collision checks, we've got this:
Anyway, a couple of general comments at this point, about my intentions with these sorts of threads.
Coincidentally, I'm also working on a "ball" object, derived from ShapeBase, which is why I've been examining other ShapeBase-derived classes fairly closely the past couple of weeks. (Maybe we can compare notes at some point.) I'm being slowed down a little by simultaneously having to work on another new type of object that has to interact with the ball, but I'm pretty much done with the code and "just" need to test things now.
Since the objects I'm working on sport several of the fixes/changes I've posted about, I'm going to make sure they work, and only then see about rolling changes into TGE.
Possibly it would also be interesting to create a stripped-down version of the ball object and make it available with some commentary. Not sure about that one though, because once you get past the very most basic stuff a lot of the code zooms off rapidly into implementation that is very specific to a particular design and needs.
04/22/2002 (3:04 am)
I ain't done yet. :-)In the code that generates the test box for the collision checks, we've got this:
testBox.min.setMin(oldMin + (mVelocity * time));
testBox.max.setMin(oldMax + (mVelocity * time));Pretty sure that second line should use testBox.max.setMax.Anyway, a couple of general comments at this point, about my intentions with these sorts of threads.
Coincidentally, I'm also working on a "ball" object, derived from ShapeBase, which is why I've been examining other ShapeBase-derived classes fairly closely the past couple of weeks. (Maybe we can compare notes at some point.) I'm being slowed down a little by simultaneously having to work on another new type of object that has to interact with the ball, but I'm pretty much done with the code and "just" need to test things now.
Since the objects I'm working on sport several of the fixes/changes I've posted about, I'm going to make sure they work, and only then see about rolling changes into TGE.
Possibly it would also be interesting to create a stripped-down version of the ball object and make it available with some commentary. Not sure about that one though, because once you get past the very most basic stuff a lot of the code zooms off rapidly into implementation that is very specific to a particular design and needs.
#11
Anyway, Joel, I went ahead and implemented all of the changes you've described above, and everything seemd to work quite well, until I collided the Land Rover with the tent (see above pic) at the angle you see. The Rover then became stuck; you can see the intersection of the two collision boxes in the picture. Is this explainable by your expected new behaviour with the a/m changes ... ?
04/22/2002 (6:25 am)
Anyway, Joel, I went ahead and implemented all of the changes you've described above, and everything seemd to work quite well, until I collided the Land Rover with the tent (see above pic) at the angle you see. The Rover then became stuck; you can see the intersection of the two collision boxes in the picture. Is this explainable by your expected new behaviour with the a/m changes ... ?
#12
04/22/2002 (8:08 pm)
Couldn't tell ya what is going on there without having my hands on the debugger controls. :) But, is either the land rover or the tent an Item object? I wouldn't have expected that to be the case.
#13
04/23/2002 (5:26 am)
No item objs. Tent is an interior... I'm gonna look at it hard tonight after work. Duhhhh... just realized that neither is an item ...
Torque 3D Owner Joel Baxter
Back up in the block of code invoked if the early raycast hits something, in the non-sticky case... the Item's velocity gets modified, and it calls queueCollision if it is hitting a ShapeBase object. But it never changes the item's position or the value of the "time" variable, and then it falls directly into the doToughCollision block of code. I haven't worked out all the implications of that... maybe it all works out OK... but it sure seems like badness waiting to happen, starting with the "end = pos + mVelocity * time" line of code in the doToughCollision block (using the now-modified velocity and the unmodified pos and time) and snowballing from there.
The other strangeness I've noticed so far is the mCollisionObject->enableCollision() line in between the early raycast block and the doToughCollision block. Seems out of place, as it will enable the collisions on that object (which I believe is used for things like the player throwing this item) for the doToughCollision case. It also means that the mCollisionObject->enableCollision and mCollisionObject->disableCollision calls are unbalanced in updatePos (two of the former, one of the latter). There's also a stray enableCollision for the Item itself near the end of the file, not sure what that's doing.