[ODE] My Latest Approach to Polyhedron Collision Management

[Thomas Harte]

This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.

--=_NextPart_Lycos_0254481038339519_ID
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

I'm continuing to make progress in my pursuit of the perfect arbitrary polyhedron on arbitrary polyhedron collision management. I am looking for comments or suggestions regarding my current approach, from those on this list who must have worked on, or be working on, the same thing. In particular, I am worried about the efficiently of my constraint generation calculations. 

My driving physics engine is fairly typical. It is assumed that at the start of a time step, no objects are inter-penetrating. If, at the end of the time step, there continue to be no objects inter-penetrating, then the time step is complete. If objects do inter-penetrate, then a binary search reveals something very close to the last time before inter-penetration occurred, at which point the relevant constraints are added to prevent that from happening, and the whole process repeats, this time considering only the remaining portion of the time step after the penetration.

Therefore, two discrete binary operations are supported on polyhedron types - an overlap test and a constraint calculation.

All polyhedron's have BSP trees and hierarchical bounding sphere sets for :

- their vertices
- their edges

In my hierarchy, every sphere has (at most) 8 children. Obviously the number of children represents a balance between hierarchy depth and bredth, and all the related factors when it comes to eliminating possible edge on polygon tests. I picked 8 to match up with the natural geographical division that occurs under an octree.

I understand that a sphere probably models the shape of sets of edges and vertices terribly, but on the other hand it is really cheap to test one against a plane.

The overlap test can be achieved using the edge and related bounding sphere information from one object with the BSP tree of another.

For any given BSP node, if a particular sphere is entirely on one particular side of the plane, then its tests head that way down the tree. If it sits on the plane, then its children are considered. If a leaf node is found to be intersecting a plane, then complete edge on polygon tests are done. If any edge intersects a polygon, then the two objects are said to overlap, and no further tests are carried out.

Obviously a first 'quick throwaway' test on distance between the highest level bounding spheres of both objects is performed, but in my simulation there is already a higher order octree related means to calculating which objects are 'near' which other objects, so that test isn't as useful as it might otherwise be.

This BSP approach is a smarter version of testing every polygon of one object against every polygon of the other. It therefore is fooled by the same problems, such as one object being totally enclosed by another object - but these are a result of using a discrete model of time, and things my simulation will simply be built to deal with.

Most tests performed by my engine when two objects begin contact will be overlap tests due to the binary search for collision time, and the constraint calculation will only occur once. When two objects start a time step rubbing up against each other, the focus will be the constraint calculation, but still this should only be required once per time step. Therefore, in my engine where objects will frequently change what they are rubbing against, it is the overlap test that needs be most optimal.

The constraint calculation needs to detect when vertices on one object are very close to polygons on the other, and when edges on one object are very close to edges on the other. My engine attempts to keep all objects seperated by an invisibly small border, negating the need for the binary search for collision time to be desperately accurate, and generally helping smooth numerical accuracy problems.

The edges problem isn't hard. Its more or less like the overlap test, but this time edges which are close to a plane in the BSP are tested in addition to those that cross the plane, and all are tested only against original edges that lie on that plane, not against the edges of the polygons used to construct the BSP tree - the distinction being that I am not interested in the artificial edges generated when splitting polygons for BSP purposes.

Vertices on planes is slightly more difficult. My current solution is to push each object's vertices down the BSP tree of the other object. But this means that I have to do two BSP traversals per constraint calculation - which I am sure could probably be only 1 if it weren't for some gross thickness on my part.

Is there any way to do this more efficiently?

-Thomas

BA flight sale now at http://www.lycos.co.uk Caracas, =A3129 rtn. including tax, Tues, 11am


--=_NextPart_Lycos_0254481038339519_ID--