Collision Shape World Transformation Storage

I'm not sure if I understand your question, but typically, shapes used for collision are stored in local space and then transformed as needed (e.g. every update, or when a narrow-phase test needs to be performed).

For most common shapes the transformation is trivial, and the associated costs are negligible. Just as an example, an OBB in local space is typically represented using only a set of extents (one for each axis). For intersection tests involving the OBB, the current transform for the object (specifically the position and three orthonormal basis vectors) is used directly. (This assumes that the transform consists of translation and rotation only; if other transforms, such as scale, are involved, it's a bit more complicated.)

But doesn't that still seem excessive to do? Why not do something like this.



It seems like a waste to only keep local information and transform it every single time you need to do a check.

Quote:

Original post by AntiGuy But doesn't that still seem excessive to do?

A smart implementation of an intersection test will do the minimum amount of work necessary (or close to it). Among other things, that means not performing transformations that don't need to be performed. If what I'm describing seems excessive, then you're probably just not understanding it completely.

One thing worth noting is that oriented bounding boxes are often centered and axis-aligned in local space, meaning that their local transform is identity. As such, the object's world transform is also the world transform for the box, meaning there's no need to perform an extra transform. In essence, you get the box transform 'for free'.

Even if a transform is required though, performing the transform every update (as in your example code) is unlikely to be optimal. Assuming you have a broad-phase culling step in place, for most updates, a given bounding box (or other shape) is not going to be involved in any narrow-phase tests. If you transform the shape into world space each update, that means you're doing unnecessary work for most updates (that is, for those updates in which the shape is not involved in a narrow-phase test). If instead you only transform the shapes as needed, the overall number of transforms performed per update will likely be far less than if you transform every shape every update.

Also sometimes you can get away with transforming the collider into the local space of each collidee, instead of transforming the collidees into world space. This can be a win if it helps you avoid transforming each vertex of a collidee and instead just transform the fewer vertices of the collider (imagine the collider is a ray (two vectors) and the collidees are triangle-meshes with many vertices each).

Quote:

Original post by jyk If instead you only transform the shapes as needed, the overall number of transforms performed per update will likely be far less than if you transform every shape every update.

Quote:

Original post by Steve_Segreto Also sometimes you can get away with transforming the collider into the local space of each collidee, instead of transforming the collidees into world space.

Perhaps I am misunderstanding you. Here are a few points.

1. I want to store the world transformation
2. I only want to update the world transform when the orientation/position of the object changes.

I can't see how it could be faster to apply the local transform for every single pair of objects you check against. I can update A, B, C, and Ds transform before the collisions are checked and that's 4 updates. If I check them as pairs it's 12 updates(indiviually) or 6 updates combined (which would require some matrix multiplication). This is all assuming that the objects have changed, if the objects haven't changed, I would have 0 transformation updates before the collision or still 12-6 updates still retrieving relative transformation data to perform the collision test.

Quote:

Original post by jyk One thing worth noting is that oriented bounding boxes are often centered and axis-aligned in local space, meaning that their local transform is identity. As such, the object's world transform is also the world transform for the box, meaning there's no need to perform an extra transform. In essence, you get the box transform 'for free'.

I'm not sure but it sounds like you're saying objects only contain the world transform which makes much more sense. On the other hand, keeping the local transform around makes direct changes much easier and more controlled. I'm always thinking something might get out of synch.

Quote:

1. I want to store the world transformation

Sure, it's practically a given that the world transform for your objects will need to be stored somewhere.

Quote:

2. I only want to update the world transform when the orientation/position of the object changes.

This is a little vague. In most cases, the world transform *is* the orientation and position, so it doesn't necessarily make sense to say 'you only want to change the world transform when the orientation or position changes'. Or are you talking about keeping some other representation of the transform (such as a 4x4 matrix) up to date?

Quote:

I can't see how it could be faster to apply the local transform for every single pair of objects you check against. I can update A, B, C, and Ds transform before the collisions are checked and that's 4 updates. If I check them as pairs it's 12 updates(indiviually) or 6 updates combined (which would require some matrix multiplication). This is all assuming that the objects have changed, if the objects haven't changed, I would have 0 transformation updates before the collision or still 12-6 updates still retrieving relative transformation data to perform the collision test.

Have you actually started writing your narrow-phase intersection tests yet? I think one thing you might be overlooking (I mentioned this earlier) is that for many types of shapes, the 'transforming' that you speak of is either free (e.g. oriented boxes that are centered and axis-aligned in local space) or cheap (e.g. spheres, capsules, etc.).

Can you tell us what types of shapes you plan on using? (I can't remember if you've already mentioned this.)

Beyond that though, it largely depends on how many objects there are, and whether you have a good broad-phase culling system in place. For all but a relatively small number of objects, broad-phase culling is generally necessary (or at least a good idea), so let's assume that you do in fact have broad-phase culling in place.

Let's say, for example, that you have 100 objects. Let's also say that on average, in any given update the broad-phase system reports 10 potentially intersecting pairs, for a total of 20 objects (assuming each object is associated with only one pair).

In this scenario, if you transform the collision shapes (whatever that entails) each update, you perform 100 such transformations per update. However, if you transform the collision shapes only as needed, you perform an average of 20 such transformations each update. This is why transforming on demand can potentially be less expensive than transforming every collision shape each update.

Now, you did mention only updating transforms when the transform has changed, but it's still not really clear what you mean by that. Also, again, keep in mind that for many types of shapes, the 'transformation' step is either trivial or nonexistent.

Quote:

Have you actually started writing your narrow-phase intersection tests yet? I think one thing you might be overlooking (I mentioned this earlier) is that for many types of shapes, the 'transforming' that you speak of is either free (e.g. oriented boxes that are centered and axis-aligned in local space) or cheap (e.g. spheres, capsules, etc.).

The code is in place and everything works in world space, but I'm having trouble figuring out how to work compound objects. I found it a bit weird when everyone was using only a local transformation while I was using only a world transformation and thought the reason I may be having trouble was the organization of my code.

Quote:

I only want to update the world transform when the orientation/position of the object changes.

Looking over that code it is confusing. : )
I was thinking in terms of compound objects. When the base matrix or whatever representation you're using changes, you would call this update. I was just making pseudo code really.

Quote:

Can you tell us what types of shapes you plan on using? (I can't remember if you've already mentioned this.)

Boxes, Spheres, Capsules, and lots of Triangles

Quote:

In this scenario, if you transform the collision shapes (whatever that entails) each update, you perform 100 such transformations per update. However, if you transform the collision shapes only as needed, you perform an average of 20 such transformations each update. This is why transforming on demand can potentially be less expensive than transforming every collision shape each update.

Well that is a point. I guess the best idea would be adding a flag if the object needs an update or not but it does seem trivial when you put it that way.

If you have collision meshes made out of lots of triangles and some control of your collision system one thing you might try is this:

1. Leave the triangle collision mesh in local space. If it has 1000 vertices, leave *ALL* of them in local (object) space. Never translate them ever for any reason.

2. For each instance of a large triangle collision mesh keep a world transform and an inverse world transform. Also keep AABBs or OBBs for each collision mesh.

3. Broad-phase: identify which triangle collision mesh instances could potentially be collided with by the current collider given its position and velocity vector.

4. Narrow-phase: Take the collider shape (likely a capsule or sphere if it's a player controller) and transform all of its vectors by the inverse world transform of each of your large triangle collision meshes that made it past the broad-phase sweep. This moves the collider shape into the object space of the collision mesh at the correct rotation and translation.

5. If a collision is detected, you will have a hit point and time. Move the hit point vector out of object space and into the instance's world space via that instance's world transform. Use this world space "hit point" for collision response.

I have done this in the past and it worked quite well and the number of transforms was bounded by the number of vectors required for the character controller (which I just represented by an origin and velocity vector).

You do need to be a bit careful with scaling transforms on your instances and take care that they are uniform along all three axis.

EDIT: Thanks jyk

[Edited by - Steve_Segreto on December 23, 2010 2:00:19 PM]

@Steve_Segreto: Did you maybe mix up 'Narrow-phase' and 'Broad-phase' in your headings above? (It looks like they might be backwards.)

I think I have a good understanding of all his now.
Thanks for the help fellas!