## Collision detection

### Collision detection

Hi there
Im currently working on a project for my master thesis at DIKU, copenhagen.
It's about simulating liquids, deformable objects and rigid bodies with a
mass-spring model. More info can be found at

2-0187-6.htm

All different bodies are discretized and represented by spheres in different
resolutions. My first problem is collision detection. All detection of
collisions is done at a sphere to sphere basis. The collision detection
should be fast so it should use the properties like frame coherency(nothing
changes for small timesteps). It's also possible to divide the spheres into
three sets. One set of spheres represents the liquids and can change their
relative position freely. Another set represents deformable bodies and can
change their relative position with a little amount and the last group is
the spheres who represents the rigid bodies and doens't change their
relative positions. Detection should done between all spheres

Can anybody give hint to methods/algoritms  which could do the thing, or
articles who consider the topic or just general suggestions.

Thanks
Niels

### Collision detection

Here are some papers you could try (or some of the related ones)..
ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/immpact.pdf
http://www.cs.unc.edu/~geom/collide/papers.shtml
http://citeseer.nj.nec.com/313190.html

The "sweep and prune" method is a common one for doing quick collision
detection and can also take advantage of frame coherency..
Hope this helps!

-Buddy

> Hi there
> Im currently working on a project for my master thesis at DIKU, copenhagen.
> It's about simulating liquids, deformable objects and rigid bodies with a
> mass-spring model. More info can be found at

> 2-0187-6.htm

> All different bodies are discretized and represented by spheres in different
> resolutions. My first problem is collision detection. All detection of
> collisions is done at a sphere to sphere basis. The collision detection
> should be fast so it should use the properties like frame coherency(nothing
> changes for small timesteps). It's also possible to divide the spheres into
> three sets. One set of spheres represents the liquids and can change their
> relative position freely. Another set represents deformable bodies and can
> change their relative position with a little amount and the last group is
> the spheres who represents the rigid bodies and doens't change their
> relative positions. Detection should done between all spheres

> Can anybody give hint to methods/algoritms  which could do the thing, or
> articles who consider the topic or just general suggestions.

> Thanks
> Niels

### Collision detection

I'm wondering if you intend to handle collisions between
spheres of the same body ?

You could just colllide the groups of spheres with each other
but that will give you problems when colliding rigid bodies
with soft bodies, beacause the spheres may penetrate the
hull, and get stuck if they wat to be pulled out again.
So perhaps you can collide the spheres of the one object
to the convex hull of the other object and vice versa
( http://www.geom.uiuc.edu/software/qhull/ )

I'd like to tell you that Im at the university of Amsterdam
doing similar research. that is, Im building a system that does
interactive semi-rigid body simulation, for the purpose of what
can be called 'Suggested Physics', in particular for games.
Ive had a lot of help from
http://www.ioi.dk/Homepages/thomasj/publications/gdc2001.htm
There's a demo at www.xs4all.nl/~vdspek/LC.zip
for me, the major problem is also related to collision detection,
namely, deriving a collision-normal from a static pair of objects in such a
way
that when the objects are interpenetrating and translated/rotated relative
to
eachother, the normal follows smoothly. as you can see from the demo,
between
spheres and parallelipeds this can be done nicely, but tetrahedrons pose
severe
problems. perhaps together we can find a solution.

please email me personally if you'd like to.

Jonathan Bacon

-------------------------------------------------------------
please tear the sticker off my eddress before use
-------------------------------------------------------------

> Here are some papers you could try (or some of the related ones)..
> ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/immpact.pdf
> http://www.cs.unc.edu/~geom/collide/papers.shtml
> http://citeseer.nj.nec.com/313190.html

> The "sweep and prune" method is a common one for doing quick collision
> detection and can also take advantage of frame coherency..
> Hope this helps!

>  -Buddy

> > Hi there
> > Im currently working on a project for my master thesis at DIKU,
copenhagen.
> > It's about simulating liquids, deformable objects and rigid bodies with
a
> > mass-spring model. More info can be found at

- Show quoted text -

Quote:> > 2-0187-6.htm

> > All different bodies are discretized and represented by spheres in
different
> > resolutions. My first problem is collision detection. All detection of
> > collisions is done at a sphere to sphere basis. The collision detection
> > should be fast so it should use the properties like frame
coherency(nothing
> > changes for small timesteps). It's also possible to divide the spheres
into
> > three sets. One set of spheres represents the liquids and can change
their
> > relative position freely. Another set represents deformable bodies and
can
> > change their relative position with a little amount and the last group
is
> > the spheres who represents the rigid bodies and doens't change their
> > relative positions. Detection should done between all spheres

> > Can anybody give hint to methods/algoritms  which could do the thing, or
> > articles who consider the topic or just general suggestions.

> > Thanks
> > Niels

### Collision detection

hi,
just out of curiosity (i'm still using good-old braindead
"minkowski-sum-based" penetration vector), how fast is all of this?

it sounds like a LOT of work -- especially the clipping A-vs-B then
B-vs-A.

just a (probably silly) thought, but is there any way at all to use
the output from gjk/penetration-type queries to construct the volume?

i.e from the standard minksum-penetration routine, you can get the
"most penetrating" feature of each shape; since:

-these features are guaranteed to be features of the penetration
volume
-the rest of the features of the penetration-volume must be made of
the neighbor-features (on the original shapes) of these
most-penetrating features

it seems like there should be some way of building the volume by
walking form these deepest points..

or perhaps not..
raigan

> raigan,

> > -use penetration VOLUME: unlike a simple penetration vector, this changes
> > smoothly, but (as you might imagine) is much more complicated to
> calculate.

> That's what I do now, Ive got box-box, sphere-box, sphere-sphere and
> - since yesterday, tetrahedron-tetrahedron functions producing a 'smooth'
> collision-normal. ( took me 4 months... ). The direct "normal = pos A - pos
> B"
> approach is insufficient for my purposes, especially with non-compact shapes
> like beams.

> For the box-box, ( box = paralleliped ) collision, I calculate
> the intersecting area from clippping A vs B anb B vs A, this gives me
> flat polygons that form the surface of the intersecting volume. I get
> the normals and areas of these polygons, then weigh the centers and
> normals of these polygons against the total surface area. The weighted
> sum of the normals belonging to A are then subtracted from the weighted
> sum of the normals of B to form the collision normal and the collision
> center is calculated as the weighted sum of the centers of all the polygons.
> this works perfectly as long as the calculation of the intersecting volume
> is accurate ( and thus expensive, but a 'good' normal is worth a lot )

> the box-sphere is similar, but can be less accurate. Since the most
> important
> thing is 'smoothness', an intersection of a sphere and a plane gives a
> circle
> whose vertices are on the circle of intersection in the -x, +x, -y, +y
> directions
> with respect to the xy axis of the plane of intersection and at the
> intersection
> of the circle and the perpendicular sides of the box, all marked x

>                          +-------------+
>                          |   /x \             |
>                         x/       \            |
> sphere - >     x/ |          /x         |
>                        x|        /            |
>                          |  \ x /             |
>                          |                     |   < - box
>                          +-------------+

> This polygon is guaranteed to give a 'smooth' area transition when the
> sphere is
> moved over and through the surface. For tetra vs tetra things are similar,
> but each
> object has its own difficulties, im working on a generalized function to do
> convex
> polytopes. So, this method gives very nice results, there's just horribly
> many things
> you need to consider when implementing it.

> Meanwhile, ive been experimenting with optimizing the normal so that the
> plane of collision cuts the least off any of the polytopes. This gave me a
> fitness
> landscape of the reoriented normals. Then you have to find the maximum
> fitness
> in this landscape. This gives you very pretty energy-landscape pictures (
> sent on req )
> but is infeasible, unless you can describe this landscape as a parametrized
> funcion and
> then have a clever way of finding the minima quickly, rather than just
> sample-and-
> descend-the-hill. So I left that trajectory and hurled meself back into
> reality with
> implementing the tetrahedron-sphere case. then Cylinders, Spheroids, etc.
> anyone cares to join ?

> J

### Collision detection

Quote:> just out of curiosity (i'm still using good-old braindead
> "minkowski-sum-based" penetration vector), how fast is all of this?

you obviously havent looked at the demo I mentioned earlier ; )
this demo is not optimised at all, but still handles 60+ objects stacked
on top of each other in real time.  the collision detection should become
quite fast, when properly optimised ( using caching of closest features,
bsp's etc ), the calculations for the clipping are actually quite simple.
Indeed,
a full contact volume calculation will always be expensive, but in my
scheme,
i only do this once every frame for intersecting objects and because the
normal
is so "smooth", i can avoid any time-search for the first time of contact.
anyway, Ive once spent a little time to hook up solid and swift libraries
but
Ive been unsuccesfull up till now to fully integrate it, ill have a go at
that later on,
this might reduce the cost of it all immensly when it gives me just the
intersecting faces of a polytope.

j

> hi,
> just out of curiosity (i'm still using good-old braindead
> "minkowski-sum-based" penetration vector), how fast is all of this?

> it sounds like a LOT of work -- especially the clipping A-vs-B then
> B-vs-A.

> just a (probably silly) thought, but is there any way at all to use
> the output from gjk/penetration-type queries to construct the volume?

> i.e from the standard minksum-penetration routine, you can get the
> "most penetrating" feature of each shape; since:

> -these features are guaranteed to be features of the penetration
> volume
> -the rest of the features of the penetration-volume must be made of
> the neighbor-features (on the original shapes) of these
> most-penetrating features

> it seems like there should be some way of building the volume by
> walking form these deepest points..

> or perhaps not..
> raigan

- Show quoted text -

Quote:> > raigan,

> > > -use penetration VOLUME: unlike a simple penetration vector, this
changes
> > > smoothly, but (as you might imagine) is much more complicated to
> > calculate.

> > That's what I do now, Ive got box-box, sphere-box, sphere-sphere and
> > - since yesterday, tetrahedron-tetrahedron functions producing a
'smooth'
> > collision-normal. ( took me 4 months... ). The direct "normal = pos A -
pos
> > B"
> > approach is insufficient for my purposes, especially with non-compact
shapes
> > like beams.

> > For the box-box, ( box = paralleliped ) collision, I calculate
> > the intersecting area from clippping A vs B anb B vs A, this gives me
> > flat polygons that form the surface of the intersecting volume. I get
> > the normals and areas of these polygons, then weigh the centers and
> > normals of these polygons against the total surface area. The weighted
> > sum of the normals belonging to A are then subtracted from the weighted
> > sum of the normals of B to form the collision normal and the collision
> > center is calculated as the weighted sum of the centers of all the
polygons.
> > this works perfectly as long as the calculation of the intersecting
volume
> > is accurate ( and thus expensive, but a 'good' normal is worth a lot )

> > the box-sphere is similar, but can be less accurate. Since the most
> > important
> > thing is 'smoothness', an intersection of a sphere and a plane gives a
> > circle
> > whose vertices are on the circle of intersection in the -x, +x, -y, +y
> > directions
> > with respect to the xy axis of the plane of intersection and at the
> > intersection
> > of the circle and the perpendicular sides of the box, all marked x

> >                          +-------------+
> >                          |   /x \             |
> >                         x/       \            |
> > sphere - >     x/ |          /x         |
> >                        x|        /            |
> >                          |  \ x /             |
> >                          |                     |   < - box
> >                          +-------------+

> > This polygon is guaranteed to give a 'smooth' area transition when the
> > sphere is
> > moved over and through the surface. For tetra vs tetra things are
similar,
> > but each
> > object has its own difficulties, im working on a generalized function to
do
> > convex
> > polytopes. So, this method gives very nice results, there's just
horribly
> > many things
> > you need to consider when implementing it.

> > Meanwhile, ive been experimenting with optimizing the normal so that the
> > plane of collision cuts the least off any of the polytopes. This gave me
a
> > fitness
> > landscape of the reoriented normals. Then you have to find the maximum
> > fitness
> > in this landscape. This gives you very pretty energy-landscape pictures
(
> > sent on req )
> > but is infeasible, unless you can describe this landscape as a
parametrized
> > funcion and
> > then have a clever way of finding the minima quickly, rather than just
> > sample-and-
> > descend-the-hill. So I left that trajectory and hurled meself back into
> > reality with
> > implementing the tetrahedron-sphere case. then Cylinders, Spheroids,
etc.
> > anyone cares to join ?

> > J

### Collision detection

hi,

Quote:> you obviously havent looked at the demo I mentioned earlier ; )

it wouldn't run on my work computer ;)

i tried it at home last night -- very cool!

Quote:> a full contact volume calculation will always be expensive, but in my
> scheme,
> i only do this once every frame for intersecting objects and because the
> normal
> is so "smooth", i can avoid any time-search for the first time of contact.

one thing i noticed was that sometimes the normal was "too" smooth ;)
i.e i was trying to stack some boxes, but they kept "rolling/tilting"
off of each other.. it was actually very similar to what happens when
you collide "spherically inflated" boxes off of each other -- since
the edges of the box are rounded, stacked boxes sometimes "roll" off
of each other.

is there a significant difference (in terms of the normal's
behaviour/etc.) between penetration-volume and
"minimum-distance-using-radially-expanded-shapes" results? the only
thing i can think of is, if the objects actually ARE penetrating
(instead of just their radii overlapping), min-distance tests don't
work anymore.

i'm sure i'm missing something important here though...

raigan

### Collision detection

hi,

Ive been struggling with it for quite some time and for all
practical apps that have to run in real time and allow
a completely uninformed user to drag objects around -
I cannot tell them 'not to be so rough' or not to stack any
objects together, it's games, not science - it works ok.

I had Solid2.0 hooked up to my own rigid-body
simulator once and odeR3 and that worked beautifully,
but there was always something the matter. Especially it
wouldnt allow for a constant framerate, f.i. when many objects
collide, objects would start jittering requiring the simulator to
change its accuracy, or fall through the floor when the engine
wasnt tweaked exactly according to that specific environment
and scale.
Indeed, the stacking in the demo is still a bit unhappy, most
parts were solved by applying friction to the spheres that are
outprojected and I think this can be done much better than
what I have now.The normal produced by any ( free )
package Ive found up to now is jumping discretely from
place to place with large displacements ( closest feature )
or changes with the motion of the objects.
The biggest problem was however with the other simulation
methods ( Baraff, Witkin, Barenburg ) that they try very hard
not to allow interpenetration, which can be very expensive and
not allow for calculation of any collision normal when the objects
intersect and have little frame coherence. For instance, if two
objects collide head-on, then bounce back and at the next
timestep they still interpenetrate, their relative speed has
changed due to the previous collision or has even become
zero and so produce a different normal.

The people I talk to in the CG industry doing games and
animations, they all, without exception, complain about the
difficulties of the available systems - MAYA's baraff
implementation, SOFTIMAGE's impulse-based system,
havoks' Xtra ( also baraff, I believe ) - for short timespan
productions when it comes to complex situations. You are facing
a week of calculations, objects are flying about that you have to
fix manually or interpenetrations wreck the simulation altogether
so you have to fix-and-calculate from scratch. Especially so for
interactive game environments. Of course, you cannot tell beforehand
wether the sim will survive through the end unless you calculate it
and you have to have quite some knowledge of the system to
understand why these things happen. Actually Im facing an acute
symptom of this, a company I work with wants to sell a bowling
game they once made as a demo with the Havok Xtra in Director,
but they have a very hard time getting all those bugs out that I just
described. So it actually costs money. It seems that finding a less
perfect, yet robust and generic method for them is very valuable.

so if you can think of a way to do nicer friction or find a better
way to calculate the normal in a frame incoherent scheme,
dont hesitate ; )

Jonathan *phew* Bacon

Quote:> hi,
> > you obviously havent looked at the demo I mentioned earlier ; )

> it wouldn't run on my work computer ;)

> i tried it at home last night -- very cool!

> > a full contact volume calculation will always be expensive, but in my
> > scheme,
> > i only do this once every frame for intersecting objects and because the
> > normal
> > is so "smooth", i can avoid any time-search for the first time of
contact.

> one thing i noticed was that sometimes the normal was "too" smooth ;)
> i.e i was trying to stack some boxes, but they kept "rolling/tilting"
> off of each other.. it was actually very similar to what happens when
> you collide "spherically inflated" boxes off of each other -- since
> the edges of the box are rounded, stacked boxes sometimes "roll" off
> of each other.

> is there a significant difference (in terms of the normal's
> behaviour/etc.) between penetration-volume and
> "minimum-distance-using-radially-expanded-shapes" results? the only
> thing i can think of is, if the objects actually ARE penetrating
> (instead of just their radii overlapping), min-distance tests don't
> work anymore.

> i'm sure i'm missing something important here though...

> raigan

### Collision detection

hey,

Quote:> so if you can think of a way to do nicer friction or find a better
> way to calculate the normal in a frame incoherent scheme,
> dont hesitate ; )

i'm trying! ;)
..i wasn't trying to be critical -- the demo's quite impressive.
it's just that i've found (with my very simple 2D attempts) that
either:

(a) the normals are well-behaved and you can never get a decent
sharp/hard corner.

(b) the normals jump around the surface of the shape, but the edges of
things no longer have to be rounded.

Quote:> The normal produced by any ( free )
> package Ive found up to now is jumping discretely from
> place to place with large displacements ( closest feature )
> or changes with the motion of the objects.

i'm trying to solve things based purely on the configuration of the
objects, but i have a feeling i may have to take their movement into
account -- i really don't want to though, because in the past
everytime i attempted something like this, it broke previously
well-behaved behaviours and in general seemed like a big hack.

the problem is (as far as i can tell), you can ALWAYS pick an
arbitrarily large displacement that will break things. how are you
handling this?

Quote:> described. So it actually costs money. It seems that finding a less
> perfect, yet robust and generic method for them is very valuable.

these are my goals exactly -- make it impossible to blow the sim up.
at the same time, i _really_ need stacking to work -- for instance,
most urban scenes have sharp corners/etc. (for instance, building
tops) that really do need to feel "flat".

..i just reread your ealier post, and i wanted to ask: how are you
simulating the rigid-body dynamics? i.e vanilla jakobsen, or did you
homebrew something?

i'm not sure if you've read it already, but the phd thesis of jeroen
wagenaar presents an alternate approach to the one jakobsen described
-- still based on "dynamic-model-rigidly-embedded-in-collision-shape",
but handling forces and collision resolution differently. apparently
they worked together on this stuff -- wagenaar's now working at ioi.

anyway, i've found it pretty useful, since it covers many topics much
more thoroughly. what i'm using right now is kind of a mixture of
their ideas, plus a few of my own...

here's the reference:
Jeroen Wagenaar: "Physically Based Simulation and Visualization: A
particle-based approach", Ph.D.-thesis at the M?rsk Mc-Kinney M?ller
Institute for Production Technology, 2001.

anyway, thanks for the great discussion -- if you have anything else
raigan

### Collision detection

Quote:> i'm trying! ;)
> ..i wasn't trying to be critical -- the demo's quite impressive.
> it's just that i've found (with my very simple 2D attempts) that
> either:

and I wasnt challenging you : )

Quote:> (a) the normals are well-behaved and you can never get a decent
> sharp/hard corner.

> (b) the normals jump around the surface of the shape, but the edges of
> things no longer have to be rounded.

> > The normal produced by any ( free )
> > package Ive found up to now is jumping discretely from
> > place to place with large displacements ( closest feature )
> > or changes with the motion of the objects.

> i'm trying to solve things based purely on the configuration of the
> objects, but i have a feeling i may have to take their movement into
> account -- i really don't want to though, because in the past
> everytime i attempted something like this, it broke previously
> well-behaved behaviours and in general seemed like a big hack.

Actually, I do have a nice 2d version running with one minor
problem, when a stack of objects fall down and two objects
touch slightly at a corner in their fall, the higher object gets a bit
'blocked' in the direction of the collision normal, whereas only
the colliding part(icles) of the objects should be blocked.
Unfortunately, this engine is not public, but I can tell you this
much, as you already suggested: you will have to revert to
frame-coherency at some point if you want to get 'sharp' normals,
because there's no way to tell from a static configuration where
one object entered the other.

Quote:

> the problem is (as far as i can tell), you can ALWAYS pick an
> arbitrarily large displacement that will break things. how are you
> handling this?

I dont, seems like we're trying exactly the same thing, I've already
made the choice of having too smooth collision-normals rather than
frame-coherency and its problems of degenerate normals, having to
find the time of collision, etc.

Quote:> > described. So it actually costs money. It seems that finding a less
> > perfect, yet robust and generic method for them is very valuable.

> these are my goals exactly -- make it impossible to blow the sim up.
> at the same time, i _really_ need stacking to work -- for instance,
> most urban scenes have sharp corners/etc. (for instance, building
> tops) that really do need to feel "flat".

At the moment, I feel 'true' stacking of say 10 identical cubes just
wont work if you dont support the structure by additional constraints
when using the Jakobsen method. There's one stupidly fundamental problem
with our approach: since we try to be frame-incoherent, we dont know if
a particle of an object is coming to a halt or speeding up. It would be nice
to stop an object by clamping its particles when it has hit the floor
(or an underlying object ) and comes to a halt due to friction, but that
will prevent it from speeding up again too, when it is hit by another
object,
moved by the user, moved due to a change in direction of gravity, blown
away by wind, etc. Once you try to mix the two approaches ( put additional
constraints on slowing down and speeding up particles ) all hell breaks
loose
in terms of complexity, everything starts to influence every other thing,
weird
things pop up with close-to-zero motion etc.etc, I think exactly like you
said
before.

Quote:> ..i just reread your ealier post, and i wanted to ask: how are you
> simulating the rigid-body dynamics? i.e vanilla jakobsen, or did you
> homebrew something?

I once called my engine the 'emergent rotation engine'. It's based on the
Jakobsen paper, so no force, velocity, etc. just displacements with, of
course,
as he says: "Naturally, a lot of additional tweaking was necessary to get
the
result just right. " and this lot he talkes about is the secret stuff. Its a
huge lot.
for instance how to get a proper matrix out of the configuration of the
particles that make up a body, when to update that matrix, when to update
the boundingboxes, etc. etc.

Quote:> i'm not sure if you've read it already, but the phd thesis of jeroen
> wagenaar presents an alternate approach to the one jakobsen described
> -- still based on "dynamic-model-rigidly-embedded-in-collision-shape",
> but handling forces and collision resolution differently. apparently
> they worked together on this stuff -- wagenaar's now working at ioi.

strangely enough, I dont find the paper online. c'd you send it to me ?

Quote:> anyway, i've found it pretty useful, since it covers many topics much
> more thoroughly. what i'm using right now is kind of a mixture of
> their ideas, plus a few of my own...

feels a lot like cooking, doesnt it - Potter style though ; )

c'd you tell me a bit more about your project, why, how and where ?
I think we should get off the newsgroup now, so feel free to reply to my
own eddress ( remember to tear off the *sticker* )

J

Hi, I have read an article on the web (I forgot where it is) about using
collision map for pixel-accurate 2D collision detection - the basic idea is
to bitwise AND the maps to find any non-zero bits.

Is it plausible to apply similar techniques for 3D collision detection?
My idea is to flatly project the objects onto the XY, YZ and XZ planes
respectively, and see if all of the 2D maps collide.

Have anyone thought about this?  Does it sound like a slow algorithm for
an OpenGL game?