Re: [Algorithms] Dumb OBB-tree optimization ?
Brought to you by:
vexxed72
From: Pierre T. <p.t...@wa...> - 2001-03-25 21:58:20
|
> Okay. Prototyping what though? You know, power plants and such..... Here's what got me thinking about all this: http://www.cs.unc.edu/~larsen/290/project.html > I would have thought that the objective of > any collision system is to provide enough feedback for any calling client to > be able to respond to the collision. Otherwise this is an academic exercise > only. Not only academic, as you can see above. But don't get me wrong either: I totally share this feeling anyway. I even asked on that same GD-List one day, if something like RAPID could be used within a rigid-body simulator - because I was really not convinced. Apparently Adam M. managed to do this anyway (check the archives), starting from the list of colliding triangles coming out of RAPID. So I guess it's also do-able with OPCODE, since I provide the exact same list of triangles. >Providing a yes or no answer to whether a collision occured or not is > perhaps not quite enough, surely you need at least a contact with > information such as time and normal. The boolean answer is enough to find Tc, the collision time. It has been discussed in many places, for example in Brian Mirtich's thesis. Baraff then suggested a distance estimate would be better to do the job, but both methods work. Now, this has actually little to do with penetration depth, which is only required with penalty methods to compute collision response. In order to find the collision time, a distance estimate is enough. There's a subtle difference here: computing separation distances, even between non-convex bodies, is relatively easy. For non-convex penetration depths, I don't even know where to start.... Finally, as far as the "time and normal" information is concerned, there are two things: - The time belongs to the dynamics part of the pipeline, what Mirtich calls the "glue" (or the "lousy mortar" in Timewarp Dynamics). It should *not* be included in the collision detection system! The collision system does not do the bisection. That's the task ahead for the app. - Since the list of colliding triangles is returned, the normals are of course available (even better to recompute them on the fly) Only my views on the subject, sure. > As you stated though you can get the time by bisecting and I suppose theres > some way of getting the first triangles to collide. All you need then is the > points of collision from Tri vs Tri. Yup. And since the boolean answer is cheaper, I definitely think it's worth using the yes/no answer during recursive collision queries, then only a second Tri vs Tri routine to compute exact intersection points (on colliding triangles only). So once again, a job for the app. > Tricky to think of any theoretical improvements. I suppose the pencil case > could be made better by using an OBB (perhaps just stored as 6 planes) for > the object hull only and resort the the AABB tree from then on. This would > give you better broad phase collision rejection while taking advantage of > your other speedups from then on and prevent unnecessary exhaustive > compares. I'm actually thinking of mixing the current code with a GJK... i.e. first perform a hull-hull test, then only use the BV-trees. In the pencil case, it would work especially well since the pencil is convex. But it's not very fair when it comes to comparing this to RAPID :) > How about a collision method whereby you pass in an integration functor, two > objects with angular rotation and travelling distances and it returns with > the collision triangles and points of first collision... > Just kidding. ;) > > Triangles and point of intersections would be really useful though. As said above, you almost got them :) Pierre |