Sign in to follow this  

3D Collision detection between fast moving meshes

This topic is 4838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently trying to work out a method for detecting the exact point of collisions between moving meshes, which deals with tunneling, that is the case where one object moves completely through another in a single timestep. What I ideally need is a mathematical function f(t) where f is a function of time t (t ranges from 0 to 1 over a single frame) and returns the exact location of a moving point at that specific time. This would've been: f(t) = A + tV where A is the position of the point at the start of a frame and V is it's total displacement within that frame if no collision occurs. So f(0) = A is the point's position at the start of the frame and f(1) is the point's position at the end of the frame. However, I have to include angular velocities (and remember this is in 3 dimensions so the angular velocity could be about any arbitrary axis). So how would this change f(t)? Or moreover, what's the best way to determine the exact point of collisions of moving objects that deals with tunneling. I've seen a lot of sites but they either don't account for angular velocities or don't go into enough depth. Hope someone can help, as my brain's about to explode!

Share this post


Link to post
Share on other sites
Hi. The best way I know of to prevent tunneling is to use predictive collision routines. For example if your objects were spheres then over the time step the path they sweep out would be capsule shapes. The trick is to do the collision detection using the swept volumes which will let you know if two objects should have collided that frame. Spheres are a simple case since they are rotationaly invarient and things get more complicated for arbitrary meshes. To keep things simple you could wrap your objects with spheres and use the swept sphere test to 'zoom in' on the exact collision time and then use regular collision on time subdivisions around that time to determine when/if they actually collide. This wouldn't be the fastest though. Alternatively you can integrate your object to the end of the time step then create a convex hull around the its start and end positions to get its swept volume. Collision detection is then perfomed on these swept hulls using any of the methods available for convex meshes (eg: seperating planes). Unfortunately this still doesn't account for rotation along that time step and so will break down for long, thin, and faslty spinning objects. However if your time steps are small enough and your objects rotations are capped to within sensible values this method should work fine. I don't know of any predictive methods that take into account the rotation of the objects but I imagine they would be very complex and as far as I'm aware every collision method I've ever come accross just assumes the rotation within each frame to be negligable. Hope this helps

PS: just incase that convex hull thing wasn't too clear this is what i mean:



Share this post


Link to post
Share on other sites
Thanks for your reply. Ok, putting angular velocities aside just for the moment, consider the following tunneling problem:

Frame t=0:

->
. .
A B


Frame t=1:

->
. .
B A

I would like to find a point in time between t=1 and t=0 where A and B are overlapping. But how do I do this? The method you mentioned using convex hulls is not gauranteed to find a time when A and B are overlapping - If you find the convex hulls are intersecting this may not necessarily mean A and B ever intersect. Furthermore, even if we do find the convex hulls intersect, how do we use this information to determine at what point in time were A and B really intersecting. This is all I need to know, as once I know this I can perform a binary search to determine the exact point when the two objects first made contact.

Share this post


Link to post
Share on other sites
For abitrarily shaped meshes I'm not aware of an anylitacal method for determining exact collision times/points in this way. What I suggest is to wrap your objects with spheres and do the swept tests with these since it is possible to determine collision times between swept spheres analytically. Once a collision time estimate is found you can then move your objects to this time and perform mesh-mesh collisions in forward time steps to find the exact point in time they touch (or at least to within a given tolerance). To speed this up I'd use seperating axis theorem and cache the seperating plane from time slices were they don't collide. Then in the next time slice check this plane first since it will probably still be the seperating case. To make it even quicker, although less accurate, linearly interpolate the objects positions between time slices rather than firing up your integrator each time.
Are you sure you need to worry about exact collision times and tunneling though. In my experience this only becomes a problem for very small fast objects (eg: bullets), for which case you'll be better of firing rays to determine collisions. Either that or collisions with flat tri meshes (eg: the terrain mesh) but these tend to be static and so aren't as difficult (just one swept volume). Do you mind me asking what it is thats causing your tunneling problems since I might be able to heklp further with more info??

Share this post


Link to post
Share on other sites
Sure, I'm currently trying to write the physics for a space combat game. So I'll need to run collision tests between space ships, missiles and a terrain.

I don't really have anything running and working yet, but I'm predicting that if the frame rate gets jerky enough and a missile is fired fast enough at a small spaceship, I'll get the tunneling problem.

What I have at the moment is a binary search through time to find the exact point of contact. Of course in a binary search, at every iteration you need to know which half of the previous iteration you want to recurse your search on. This is only possible if you can assume that if on a current iteration you're not intersecting then the collision is later in time and if you are intersecting then obviously you need to move back in time to get to the point of contact (to whatever accuracy you feel sufficient). If tunneling is a possibility you can't safely make this assumption, because if during your search the tested objects are not intersecting, the collision may either have already happened or may not have happened yet.

Can you elaborate on how the separating theorem works? I'm assuming you try to find a plane that fully separates the two objects and if such a plane can be found then obviously the two objects aren't yet intersecting. But couldn't finding this plane get computationally more expensive then a direct mesh-mesh intersection test? how do you exactly find the separating plane anyway? Are you sure this is the best way to do this (without getting insanely complicated).

Share this post


Link to post
Share on other sites
Ok, if you analytically find the collsion time between both objects bounding spheres this is garaunteed to be before the actual collision occurs (actually I think the solution will return two answers, one at first contact and one at last contact, simply take the smaller one). This at leasts gives you a starting point on the right half and close to the actual collision time. If you just step forward from here in small increments then you wont overshoot (adjust the time slices for the best speed / accuracy trade off).
Now for seperating axis theorem. Don't worry too much about its speed, its certainly faster than just intersecting all the tris each time. Heres how its done:

STEP 1
For each tri in turn in mesh A calculate which half of that tris plane each vert in mesh B lies on. If the all lie on the same half then you've found a seperating plane. Cache this plane for later and quite the seperating plane routine. else go to step 2.

STEP 2
Do step 1 but with mesh B's tris against mesh A's verts. If no seperating plane found go to step 3.

STEP 3
Now the difficult and expensive bit but chances are you wont get this far very often. For each edge combination between the two meshes in turn form a vector (which I'll call the cross axis from now on) which is the cross product between the two edges. Then project all the verts from one mesh onto the cross axis forming a range of how far they span it. Then for each vert of the other mesh project it onto the cross axis and check if it lies within the range calculated earlier. If so then this isn't a seperating axis so drop out and go to the next edge combination. If non of the projected verts lie in the range then this is a seperating plane. If no seperating planes are found after all this then the objects are intersecting.

Sorry if the explanation isn't too clear but google it and you'll no doubt find plenty of hits. The beauty of this method is that with a seperating plane cached this can be checked first in the next time slice which is very fast. if its still valid then move to the next time slice. This way you should be able to rapidly converge on an intersection time. Just one thing though, this method wont give you intersecting points. When you've found your intersection time you'll have to use another method to get those.

This will all give you very accurate collision but this may not always be needed. Have you considered representing your objects with hierarchies of bounding volumes like spheres and boxes. Collision checks between these types of objects are MUCH faster than arbitrary meshes. Also for missiles I'd either use ray collision or represent the path of the missile each frame as a capsule (swept sphere) and use that alone to determine collisions. I don't think theres much point colliding with the missile mesh and it'll much faster and I don't think the decrease in accuracy will be that noticable for these small objects. Just think of the huge swarms of missles you'll be able to handle :)

PS: Just occured to me I didn't explain why I say you should step forward linearly rather than use binary subdivision with this method and its quite important so I'll explain now. Firstly by stepping forward linearly you get the most benefit from your cached seperating planes. But more importantly by stepping forward linearly you will only reach the situation where the seperating axis algorithm returns intersecting once, whereas jumping back and forth will return many. This is important because for the algo to return intersecting it must try all possible cases which can take a long time, especially for complex meshes.

[Edited by - Motorherp on September 13, 2004 10:24:04 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
For abitrarily shaped meshes I'm not aware of an anylitacal method for determining exact collision times/points in this way.


In theory it's not possible efficiently in the referential of one convex, the other can describe complex movements, resulting on equations really hard to inverse. If you consider numerical precision limits (ex: 24 bits) I am nearly certain it can be done quickly, in quasi constant time, if rotational speeds (refered to as Omega later) are not too great. I wish to be back to physics programming and test the many ideas I have compended on paper the last months.


As Motorherp said use the swept spheres to find a reduced time interval of potential collision.

The spheres do not have to be in linear translation (constant velocity vector). To be totally conservative you can take the accelerations into account. Majorate them and you can grow the spheres linearilly. Thus no collision will be missed here. Let the sphere centers match the gravity centers even if the radius is bigger, it's easier.

Next finding the first time of contact is the big deal. If you have the contact time, just integrate, run a static coldet and you get the contact point, the relative velocities, etc ...

Binary recursion algorithms suppose abusively (if not erronously) the precondition that the MIN DISTANCE between the two objects is monotonously decreasing. In many cases it works but with fast rotations, the mindist(t) curve might well be of sinusoidal shape. Even around the time of contact the curve might be parabolic shaped :


A 'parabolic' shaped min-distance curve.

\ /
0--X---*---> time
\_/ <- inflexion point here

X is the contact time


My assumption is that the frequency of inflexion points is closely related to the two Omegas. This way slicing the function enough on the time line we can certainly assert to be left with the monotonous and parabolic cases.

Then we need to check each slice in chronological order. It's easy to see that for quick rotations, no other way will be quicker. In each slice we need :

d(t0) d'(t0) (d' is the derivative)
d(t1) d'(t1)

d(t) can easilly be found with the algos based on the well documented separating axis theorem. A connexity graph or a 3D Voronoi diagrams can be used to speed it greatly with space time coherency. The power of this method is in most cases only 5-6 dot products (plane-point distances) are required.
d'(t) can also be evaluated once the two nearest d-facets in each convex (point/plane, plane-point, edge/edge), that define the separating plane are identified.

Thus a probably very good approximation of the parabolic curve. Find the time of minimum. Then you are left with the monotonous case. You can easilly use a binary recursion quite confidently and find the first zero, normally on the left side.

If you understand this well, it's quite obvious that the algorihtm is really close to optimality. I could comment it in details but that would make the post very lengthy.

[Edited by - Charles B on September 13, 2004 3:07:19 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
... Collision detection is then perfomed on these swept hulls using any of the methods available for convex meshes (eg: seperating planes). ... doesn't account for rotation ... time steps are small enough ...


It's also something I have in mind for many years.

Merging hulls.
--------------
Getting this hull caps cand be fast using merge methods, that is taking advantage of the prexisting connexity graphs.

Also note that you can merge as many hulls as you want in
log(n) time : Hull(A0,A1,A2,A3) = (Hull(A0,A1), Hull(A2,A3))

This can reduce the problem of rotations.

However merging hulls, requires walking in connexity graphs which is usually inefficient in runtime. (AGIs, prediction and cache problems)

Growing hulls
-------------

You can also grow the convex polyhedra by pushing the planes in their normal direction by Delta. Recompute the vertices as intersections, or something quicker.

With this error volume added, it might become a conservative rejection test.

Also, the big problem is you can't exploit the accelerated version (space-time coherent) of the separating plane algos because the convex shapes are recreated each frame. However I think it's possible to greatly improve the static algorithms in real life.

So in the end I am not sure this idea might be really efficient.

Share this post


Link to post
Share on other sites
It took me a couple reads but I think I see what you're getting at. basically what you're saying is to progress up time slices chronologically until you can be sure that in the remaining time slices up to the exact collision time the min distance between the two objects is only decreasing. At this point you then use binary subdivision to converge on the exact collision time faster. Is this correct?? It sounds good but there are a couple of issues I have that maybe you could clear up for me. Firstly in order to make the determination that in the remaining time its safe to use binary subdivision wouldn't you already have to know the exact collision time??? Also it sounds like a lot of extra checking and calculating which would only pay off when the objects got very close to the collision time. I'm not convinced you would get a speed boost over just skipping the extra checking and progressing up time slices in chronological order regardless. Finally as I finished with my last post, by jumping beyond the collision time you are entering the region where the objects are colliding and the seperating axis algo drags. By progressing chronologically you only enter this region once (when the collision time is determined) whereas with subdivision you'd be entering it n/2 times where n is the number of jumps taken to determine the collision time. But then again maybe I've just understood you wrong??

Share this post


Link to post
Share on other sites
"Firstly in order to make the determination that in the remaining time its safe to use binary subdivision wouldn't you already have to know the exact collision time ???"

Monotony is the only condition I see. For "Binary subdivision", I think more and more in my case I'll replace it by a highly disymetric trinary search :


a0 a1 b1 b0
[ [t0] ]

t is evaluated (root of polynomial)
[a1=t0-Delta, b1=t0+Delta] is recursed first.
If invalid (0,0001%), then [a0,a1] or [b1, b0] are recursed.


Somehow it's Newton Raphson modified because only an approximation (say p(t)) of d(t) is known instead of d(t). But p(t) gets closer to d(t) when [ai,bi] shrinks. Thus instead of a serie of points, it's a serie of intervals.



"wouldn't you already have to know the exact collision time ???"

??? Not sure I see your question here :/.

No the error done by approximating d(t) to a second degree polynomial is not around the contact time (d(t)=0) it's around the minimum of d(t) which is after the collision if it's negative. If this minimum is positive, there is no collision in the slice. Quick rejection BTW (*). Maybe in the next slice if there is one, that is only with very high angular velocities. In rare cases the contact time may be very close to the minimum (negative) distance time, but then it means that the objects hardly touch, and if a collision is missed there, it's of nearly no consequence since this also means the normal relative speed is very small, and would have a very small impact. (I put apart angent speed and friction).



Example :

^ \ __
| \ / \ /
| \____/ |\ /
-------|------|-X-m-/----> t
| | \_/
<-----><-----><----->
0-1 1-2 2-3


Slice 0-1
- all monotonous, d'(0)<0, d'(1)<0,
- Since d(1)>0, no collision. Two calls to d(t) (boosted separation plane algo)

Slice 1-2
- all monotonous since d'(0)>0, d'(1)>0,
- Since d(1)>0, no collision. One call to d(t) (boosted separation plane algo)

Slice 2-3
- one inflexion point, 2nd degree approximation
- quick search closing X (b1=max(b1,m))
- X found in 1 or 2 steps (a few calls to d(t), 2,3,4 ? )

Calls to d(t) (collision primitive) : 6,7, or 8 ?

As you can see the boosted trinary recursion is only done in one slice at max, here 2-3 (*)

Slice frequency must be chosen appropriately. Omegas and other factors to study very precisely on paper. But it's sure one such freq exists. There will always be a possibility to majorate it so that the slices are always chosen small enough.


"Finally as I finished with my last post, by jumping beyond the collision time you are entering the region where the objects are colliding"

Depends how far beyond. Not necessarilly. In some cases the objects hardly touch. And then you miss ;). It's not always a 'frontal' collision. That's the whole issue I think my algo treats with both solidity and speed.


"By progressing chronologically you only enter this region once (when the collision time is determined) whereas with subdivision you'd be entering it n/2 times where n is the number of jumps taken to determine the collision time."

"the seperating axis algo drags."

I think I know how to handle negative distances in the collision detection primitive, with Voronoi stuff. Positive or negative d(t) should be returned as fast. Even if I was wrong :

First you probably admit that this n is very small with my trinary search. Probably 2 or 3. Samples are (cf my example scheme) 3, and t0+Delta.

To be accurate enough you need very small time steps if ou don't recurse.

Conclusion :

For very high rotations, traditional methods would fail. If you read carefully I can't see any important objection against the speed of my algo. Except maybe the negative d(t) 'stall' issue. I need to check my ideas about Voronoi. But then I object against your algo (precision). But you might say since it's rotating or translating very fast, or if the error is not too big, the gamer will not notice ... hmm right maybe.

Share this post


Link to post
Share on other sites
Another post, because a totally different approach, quite rough.

I know programmers who have used sphere trees very efficiently in a commercial (race) game. Speed counts there, thus the tunneling issue.

You can handle thousands of spheres and thus approximate surfaces and volumes rather precisely. And it give decent results if you don't cope with too many objects.

Spheres are :
- compact (128bits)
- swept spheres easilly deal with tunneling.
- col det is fast (second degree equation to solve, quick rejection easy)
- deals well with static meshes.

Some algos are available to transform any arbitrary mesh into a sphere tree.

Share this post


Link to post
Share on other sites
Ah ok, looks like I totally misunderstood you Charles. Its interesting stuff, I've never considered the implications that rotation has on collision this in depth. I'm interested to know how you'd evaluate the d'(t) curve though, for moving spinning arbitrarily shaped objects I can imagine this to get quite intensive.

I second the sphere tree idea, I've tried it before myself and it works well. Not only does it allow fast collision detection using 'after the fact' or predictive collision, but you also get your collision points out of it for free effectively. The only problem I had was that for accurate collision many depths to the tree were needed which means the memory requirements can be very large. Like Charles says, its good as long as you don't try to handle to many different types of objects. Alternativly reducing the tree depth to save memory could give you some pretty nasty looking collision since a large sphere isn't a good representation of a flat surface. I'm currently working on a hybrid sphere tree method that overcomes these memory restrictions and lets you stop recursing quicker. Basically a tree is constructed with a limited depth and each leaf node of this tree contains an approximation of the normal and plane constant of the surface contained within that sphere (effectively a plane). When two leaf node spheres are colliding there planes are intersected giving a line of intersection which can be tested for inclusion in the spheres to check the validity of that collision. Its still a work in progress though so I don't know yet how well its going to work. Still its another option for you to consider.

Share this post


Link to post
Share on other sites
Some interesting stuff... But I was also wandering how you'd represent a curved movement caused by a non-zero linear and angular velocity as a parabolic function. But I believe as long as I follow Motorherp's advice in performing a sequential search as opposed to a binary one, I shouldn't have to worry about this. I think the only thing I need to know now is how one performs a swept sphere test. So if you could help me on that, that would be great.

But one thing I was wandering is whether step 3 of the separating theorem is just (or nearly) as expensive as a mesh-mesh intersection test. If so, we could just perform step 1, then step 2 and if we still haven't found a seperating plane then just do an mesh-mesh intersection test, that way we'll also get an intersection point, which step 3 won't do for us.

Share this post


Link to post
Share on other sites
for a space combat sim, a per-poly collision seems really OTT. I'd go with the sphere tree, or sphere-approximated shapes. Should be much faster, simpler, and well within your requirements. Or even box approximations.

You can always do swept tests between triangles. Dave Eberly has some code on his site, for swept triangles, and boxes. It's not hard to extrapolate from the normal separation axis theorem.

Share this post


Link to post
Share on other sites
Heres some articles that explain the swept sphere thing:

clicky
clicky

Regarding Step 3 it depends how you do your mesh-mesh intersections. Tri-tri collision checks are fairly expensive whereas each loop through step 3 can be done quite quickly. Also the main advantage of using this method is that although you might take an initial performance hit from the first time you find a seperating plane, this plane can be reused many times before it becomes invalid which will give you a large performance boost. On the other hand if you were to do mesh-mesh collision you would have to repeat this collision routine in full for every time slice which over several time slices would be more expensive. Again though it really does depend on the mesh-mesh collision routine used, if its a fast one that can take advantage of coherence between time slices then by all means it may be faster. The best advice I can give is to experiment and see for yourself. Set up a time counter around your collision routines and try several different methods to see which is the best.

Share this post


Link to post
Share on other sites
Quote:

badroom.

Some interesting stuff... But I was also wandering how you'd represent a curved movement caused by a non-zero linear and angular velocity as a parabolic function.


I don't pretend to represent the movement (3D). I pretend that for a relevant thin time slice, a second degree polynomial is enough to approximate the d(t) function (minimum distance between the objects). The goal again was to cut this case as two monotonous curves, condition for recursive search, that is not miss any collision.

Imagine fast moving and rotating object (a hammer ?) thrown at your avatar head and it's a near miss, it passes very close, still it collides, and does a minor injury. Now you know the cause of your head ache. Most techniques would fail to detect this case accurately. But if they don't, maybe no gamer will notice it.

Share this post


Link to post
Share on other sites
i have been planning to do something very similar to what charles explain for a while. i intend not to miss any collisions save for numerical inaccuracies regardless of linear or rotational speed.

-sweep & prune on all axises(sp?) to retrieve potential colliding pairs in linear time. obviously the bounding box should be extended by the speed of the object.

-swept outer bounding sphere to more acccurately determine collision interval and stop tunneling.

-meshes are built out of unions of convex hulls each with its own bounding sphere. these inner bounding spheres can rotate obviously, so this cant be analitically solved. however, the distance function between these spheres consists of two parts: distance caused by linear motion, which (duh) varies linearly, and a periodic harmonic motion caused by both rotations. finding roots of period functions is hard. however, the key here is cleverly subdividing the interval depending on distance and the combination of rotation speeds so that the interval youre looking at doesnt contain more than half a period or so, so that with indeed for example a quadratic or cubic function fitted trough these distances and their derivatives (speed), should yield a close to perfect approximation of the distance function at this point, and thus of the collision time. refining with binary search now doesnt make much sense since the hulls themselves still need to be handled, so we only need a roughish estimate yet.

-if you have found a pair of colliding bounding spheres, the hulls themselves need to be tested. fortunatly you should have quite a narrow time interval by now. however, im not yet sure how to handle this best. obviously using seperating planes, but im not sure how to apply this. anyway having come this far not much can go wrong anymore, brute force should suffice. simply checking an x number of instants in the interval, maybe depending on speed should do the trick, since youve filtered out so much possible collisions by now, this check only needs to be done for the tinies fraction of objects. obviously the last step would be a binary time search to refine the exact time of collision.

this is all fine and dandy for a spaceshooter i think, however, backstepping to collision time doesnt combine very well with stacking. i really need to do some research on hybrid methods regarding backstepping and stacking. if anyone has some papers adressing this issue id love to read them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
i have been planning to do something very similar

Thanks for your post written in concise and natural language. This renders my previous explanations clearer to all. You show it in the global context of multiple collisions.

Still I have a suggestion for an hybrid version of forward search and recursion (intervals). As you explained, quadratic extrapolation will be very accurate at close range.

So it should be easy to guess a first estimate of the contact time (t_contact_0) within a given and known margin of error (t_error_0). On paper, movement equations will have to be compared to their quadratic approximation and a formula giving a strict majorant of the approximation error in time should be found analytically.

This way you can advance to t_contact_0-t_error_0. Iterate and you will always move forward, always before the contact time. Closing the t_contact_infinite, the approximation error will fall quickly under the precision of floating points. In the end the contact distance function is quasi linear around the exact contact time (C1 function) so t_error_i will soon be null.

Share this post


Link to post
Share on other sites
i just had another thought regarding this issue. in my mind its 2D but i think the idea could easily be extended to 3D.

instead of convex hulls with a bounding sphere, use a sphere tree with ONE linesegment in the leave nodes. this way concavity is easily handled, and these sphere trees should be easily constructed from arbitrary datasets. much easier than modelling or extracting convex hulls.

pairs of colliding spheres could be found using the same above algorithm, which would be quite fast due to the hierachic sphere tree.

the root sphere would still be centered at the centre of mass and be done analiticly, then its a matter of children of one parent vs children of the other, and check the pairs of children that both collide with the other parent and recurse.

when two colliding leave nodes are found, all that needs to be checked is one linesegment-linesegment collision, which is not too hard if you use a stripped down version of the seperating planes (both endpoints need to stay on one side of the other linesegment). this can be done iteratively, or if there is a reasonably simple expression for the distance between a rotating point and rotating line and its derivative, a solution can be found in the same way as for the spheres.

one other advantage of this method is that aside from angular geometry, spheres can also be included by simply not using a leave-node on a branch where you wish to have a curved surface. all it would involve is writing an overloaded function for sphere-linesegment solving, which isnt too hard either.

i think it would be pretty effecient and easier to code than what we previously discussed.

your thoughts?

Share this post


Link to post
Share on other sites
Quote:

children of one parent vs children of the other, and check the pairs of children that both collide with the other parent


one second thought, in case of a binary sphere tree (which is easier to code and probably faster), checking against the parent first doesnt make much sense. doing one check to prevent two others at most might not make much sense. then again for slow moving objects the first test might often return false. then again, they are not the bottleneck but rather the fast moving objects and most importantly the stacked objects, and in their case the check against the parent is not likely to result in early rejection.

well i guess trying it out works best...

Share this post


Link to post
Share on other sites
Sounds famliliar

Quote:
Original post by Motorherp
I'm currently working on a hybrid sphere tree method that overcomes these memory restrictions and lets you stop recursing quicker. Basically a tree is constructed with a limited depth and each leaf node of this tree contains an approximation of the normal and plane constant of the surface contained within that sphere (effectively a plane). When two leaf node spheres are colliding there planes are intersected giving a line of intersection which can be tested for inclusion in the spheres to check the validity of that collision.


The big problem I had though is determining sensible collision normals without knowing the relation between the underlying triangles. Instead now I use predictive sphere-sphere tests on the sphee trees to narrow down to a collision time and a limited set of potentially colliding tris. Then I calc the min distance between these tris to find the closest ones and the remaining distance and also get my collision points and normals to boot.

Share this post


Link to post
Share on other sites
hehe i totally missed that, and its in the same thread only a couple of posts above :). well it was a couple of days ago when i read this thread from start to end :P

Share this post


Link to post
Share on other sites
the link you provided to the gamedev article is also very nice i see. basicly what charles and i talked about all worked out.

damn its hard coming up with something that hasnt been done before these days :)


as for the normal extraction: if you only store a plane in the sphere this is indeed going to be a problem, but if you store the entire triangle (or linesegment) you should be facing a simple tri-tri collision.

Share this post


Link to post
Share on other sites

This topic is 4838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this