Collider

Engines, Libraries and Tools Xith3D Forums
#1

Could everyone take a look at the proposed interface for a Collider and let me know if it looks correct?

Similar to an Occluder, a Collider will be attachable to any “model” (a branch group with transforms and shapes).

Using this, a physics system or a simple collision system will be able to adjust transforms and/or provide callbacks between moving objects.

The first implementation of a Collider will probably be a BiTree (similar to BSP but axis aligned).

A special implementation of the collider wil be a Hull which can be constructed so that the number of triangles being used for collision is reduced from the high res set.

http://www.sword-and-sorcery.com/javadoc/

#2

For a first look, it is OK.

I was thinking about using OPCODE for collision detection, so it would be great to see an example for Collider (even simplest implementation).

Yuri

#3

Question, one of the things we need to do is slide along a wall. With the point of impact and the normal of the surface, should I be able to adjust the velocity to cancel the part of the vector which would normally push the object into the wall?

So the idea is that we would, for example, form a collider around an avatar, then when when we applied a velocity we can can check each frame and calculate the adjustment for the avatar’s tranformation to account for the surrounding geometry.

Example:

  1. So if the velocity is -1,0,0 and (thats a 1 meter per second movement in the -x direction).

  2. FPS is 10 fps and last frame we were 0.05 meters from the surface from the wall.

  3. Now we need to calculate the new position from 100 milliseconds ago.

  4. we determine that the first intersection was at 50 ms ago, so we move the transform and adjust the velocity by comparing the normal of the surface to velocity of the object.

  5. We then ask for a collision check again, with the modified velicity for 50 ms.

  6. It reports no collision (since we should be moving coplanar to the wall. Although I am not sure how to make sure coplanar checks do not count as a collision.

Bah… am I heading in the right direction here?

#4

One issue which is kinda nasty is when there is any kind of error and one object embedds itself slightly in a wall. The next frame would detect that it had happend, but since the point of intersection is inside the plane how can we figure out the proper adjustment? It would be easier if all objects including walls were “solids” but when you have a model of something it is just a bunch of polygons. I guess you could “push out” the model by reversing the velocity, then move forward in time?

#5

Is then the idea to have bounds or real geometry collison ckecking system? I am picturing avarat with moving limbs going towards the wall. Unless real geometry is used how would one be able to ckeck intersection with wall at the moment when avatar stops just before the wall and raises his hand - using geometry would be quite expensive. And then again maybe I am missing point here. But if you dont know you better ask :slight_smile:

#6

A collider can be either a convex hull derrived from the geometry or all the triangles in the geometry itself. In the case of a building you want to use all the geometry. In the case of a moving object most of the time you will use a simple 8 sided bounding box which you adjusted to contain its geometry. In the case of an animated skin on a character you would want to adjust that box to always perfectly enclose your character’s geometry. Most games collide that box against the geometry surrounding it.

The geometry of a collider is placed into a spatial container which is formed of half spaces (like a BiTree or BSP). Comparing two colliders can be done by recusivly comparing half spaces, so you quickly elliminate most of the geometry from consideration. Casting rays or checking triangles against a spatial container is very fast and you would only even attempt this if the bounds intersected in the first place.

#7

Now that makes sense. Over the weekend I was thinking how to do somethin like this and all the time was following path …ok it should be bounds based BUT at certain point you should be able to switch to use real geometry - and of course completely missed idea that you can adjust size/volume of enclosing object. That is simple and should perform nicely. Thanks Dave for this input.

#8

David,

I think this is an excellent proposal.

Regarding your wall problem - I encountered the same thing with a simple 2D game I made where I wanted the objects to slide along the wall. What I did IIRC was to move the vehicle ignoring the wall. Then - if it was detected to be in a wall, move it out out of the wall using the shortest side of the right angle trangle consisiting of the wall, and the object’s path. Only after these calculations would the frame be drawn, so the user never saw the vehicle in the wall. This had the effect where it would slide quite nicely along the wall. I have no doubt there is probably a better way to do it, but for this game it was all that was needed :slight_smile:

Pushing out the object by reversing it’s velocity means that one loses the nice sliding effect. This is indeed what I did at first for the aforementioned game, but what happened is that despite the object is pushing against the wall at an angle and should move along the face of the wall - it get’s “stuck” and doesn’t slide which really killed the gameplay. In the case of an calculation error however this is probably the best way out - otherwise you may run the risk that they could go though the wall which is probably worse.

Will.

#9

Now on memory. I am indexing all the geometry used in the collider, so only unique coords are stored. Assuming that most geometry has 6 faces sharing each coord you have about roughly 3 ints and 1.3 floats per face just to store the converted geometry. Then you really need a plane equation (4 floats) per face and a triangle center point (3 floats) and a triangle radius so you can do triangle to triangle collision. The center and radius is used for a fast sphere to sphere check on individual triangles and the plane is needed (if the prior check passes) to check for intersecting the three triangle edge line segments against the plane of the opposing triangle. That means an overhead of 11.3 * 4 bytes or 45.2 bytes per face. So an object which has 1000 triangles would cost 45k of memeory for accurrate triangle to triangle. Now for most models which had a lot of triangles you would use a hull, which would be extremely small, but for buildings you could not do that. But I think for buildings it is expected to have fairly high memory requirements.

Thoughts?

#10

First thought:

1000 triangles ~= 45k, I wouldn’t worry too much, that doesn’t seem like such a high overhead.

I’m finding it really difficult to get my head round mixing collision in with the scenegraph so I’m afraid I can’t really comment much on the Collider interface apart from it looks like it’d do the job.

Up to now I’d always thought of the scenegraph as the visualisation layer of something else (view/model) and I guess I would have assumed the collision/physics sit in the model not in the view, but then this might just be me having trouble with a paradigm shift.

Kev

#11

Do you plan to have brute force triangle versus triangle collision check ? Even with fast sphere check, with two models of 2000-3000 triangles (which is not so big these days) we are talking about 5-10M checks for pair of objects. It won’t work in real time…

I think that VERY generic hull is a must for anything trying to do such kind of collisions. By generic I mean not more than maybe 100 triangles per object. In such case, memory usage is not really a concern and number of checks is manageable.

Do you plan to have some kind of hierarchy tree for triangles in static objects ? This could reduce number of checks tremedously. Probably AABB boxes would be more useful here than spheres down to certain detail level.

#12

Yes Artur, we would put the triangles into a BiTree probably and do a recursive check of one tree against the other. We should only have to check triangles when we get to children buckets.

#13

kevglass:

Its not really in the scenegraph. Its a seperate package and completely optional.

#14

[quote]Regarding your wall problem - I encountered the same thing with a simple 2D game I made where I wanted the objects to slide along the wall. What I did IIRC was to move the vehicle ignoring the wall. Then - if it was detected to be in a wall, move it out out of the wall using the shortest side of the right angle trangle consisiting of the wall, and the object’s path.
[/quote]
You may do that in 3d too, i.e. move the collider into the obstacle and push it back into the direction of the normal of the plane it collides with, until it there’s no intersection. This will give you the sliding you want, but you can’t implement stair climbing and similar effects with this in a reliable way. If you collide with the front of a step for example, the normal will just push you back…you’ll never climb the stairs.
Another (and in this case preferable) solution is to determine the “sliding plane” and correct the velocity so that the collider moves in parallel to this plane. The sliding plane is the tangent plane of the sphere at the point on the sphere where the collision takes place (therefor, you have to calculate the exact time when the collision happens…you can’t just move it into it and correct your fault later). For a unit sphere, you can simply use the vector from the sphere’s origin to the point to correct your velocity, because this already is the face normal of the tangent plane.
For ellipsoids, transfer your geometry and velocity into ellipsoid space first (i.e. divide x by rx, y by ry and z by rz), so that you can work with a unit sphere again…makes things much easier IMO.

#15

Some of this sounds very familiar, I struggled with collision reaction for a while with S-Type until i got something i was happy with.

My current solution is:

  • Find intersection edge between hulls
  • Backtrack moving object to point of first intersection.
  • Project velocity vector onto intersection edge
  • Move the object forwards by the remaining portion of the timeslice.

This works quite nicely for the most part, however if you’ve played it you’ll notice its not perfect - sometimes sliding will ‘snag’ when moving along a surface due to it finding the wrong collision edge (imagine sliding along a couple of adjacent squares, it picks up the shared edge as you move from one to the other).

The other problem is with multiple collisions - imagine two long rectangles in a V, then moving down and into the V, one surface will push you though the other with its own sliding behaviour.

I’m not sure how to solve my first problem, but taking the velocity into account when finding the sliding edge might do it. The second problem can be solved by iterating the collision behaviour over mutliple times until it reaches some kind of stable state. Obviously this can loop forever so some sort of get-out clause needs to be added (like after 10 iterations, just reset to the original position and set speed to 0).

Hopefully that’ll give you a few ideas as to what needs to be included, you can tinker with S-Type if you want to see how well (or not!) it works.

#16

I have completed the lowest level code for the collider and have been running some unit tests. The cost of determining if a line segment intersects a single triangle and returning the exact point of intersection is coming in at 703 nanoseconds. This test is done by creating a sphere with 39000 faces and casting the line segment against each one. Doing that 1000 times took 28 seconds, which is 28 milliseconds to test all 39000 faces, which is an average of 703 nanoseconds a face. Each triangle is checked by first casting a ray against its sphere bounds, then if that passes I intersect with the plane. if the distance to the plane within the line segment length I then check to see if the point of intersection is within the triangle.

Now once I put the triangles in a spatial tree it should reduce the number of actual checks against triangles to hopefully a few dozen on each check. But still, does the 703 nanoseconds seem high? (2GHz CPU) If so I can profile it and see eactly where the time is being spent.

#17

Just an update. With the triangles sorted into an adaptive bi-tree I am getting the following speed:

Sphere of 40,000 triangles:

100,000 random rays against the sphere penetrating to its center : 12 seconds, which is 120 microseconds a pick. Returned is distance from ray start to inpact and the exact intersection with the triangle.

100,000 random ray segments against the sphere penetrating to just under its skin : 6.51 seconds, which is 65 microseconds a pick.

Sphere of 1,000 triangles:

100,000 random ray segments against the sphere penetrating to just under its skin : 1 second, which is 1 microsecond a pick.

Next to do is collision check of a bounding box and a bounding sphere.

BTW the BiTree is stored in just 3 arrays, 2 of int and one of floats so it can be stored and loaded blazing fast. The time to take the Shape and build the underlying ColliderGeometry and the subsequent BiTree is 900 ms for the 40,000 polygon sphere, so it is possible to do it at runtime if necessary. I would expect your internal game formats for models you would probably want to store the precomputed collision and occluder data structures though.

#18

just a few thoughts…

Since your tree is array-based, it looks like you are probably
using the median node as the splitting criterion and
exploiting the fact that your tree is balanced. Is that
what it is ? OK ! that’s at least what I do, since my problems
are a big memory hog. However, IIRC I’m not really sure if a
balanced tree is more efficient for queries compared to the one
that is based on splitting along the coordinate, etc. There is
actually a paper by Sowizral et al.(ex-Java3D) that talks about this
in the context of bounding polytopes. BTW, Kelvin Chung also
has a paper on collision detection I think.

Are you using quick sort or some such sorting algorithm while
building the tree ? Again, I’m not sure how well this applies in
general, but what I do is not a full but partial sorting since you
just want to simply partition the nodes into two groups w.r.t.
the median node such that the left are “<=” and the right are
“>” while the order within the groups itself is irrelevant.
The speed, of course, may not be that important if the tree is
precomputed and especially so if the polycount is small.

Great show…