gdalgorithms-list

Re: [Algorithms] Using RAPID within a rigid body simulator

[Adam M. <amo...@dp...>]

No, I successfully postprocess RAPID's output to do that.  Specifically, I
need a vertex-face pair or an edge-edge pair to be used as contacts.  RAPID
gives you intersecting triangle pairs, but if you look at where those
triangles were one step earlyer (before they intersected) you can do some
distance computations to find which of their features (verticed and edges)
were the closest at that point, which gives the vertex face and edge pairs.

The rigid body simulation itself typically doesn't need to track closest
points, unless they are really close, as above.  Permanent closest point
tracking between objects is usually used to speed up the collision detector
(temporal coherence).

--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo



>example, say I'm just using OBBs, as with RAPID. RAPID will detect
>collisions, but won't give me a distance or a pair of closest points. Does
>it mean it can't be used efficiently within a rigid body simulator ?
>
>I think I'm missing something there.
>
>Pierre

Re: [Algorithms] Using RAPID within a rigid body simulator

[<Chr...@Pl...>]

Pierre Terdiman wrote:
>In rigid body simulations, one needs a correct estimation of the distance
>and contact points between two bodies, in order to:
>- backup the simulator in search of the exact collision time
>- compute an accurate collision response
>
>If you followed the recent GJK thread, you know this algorithm works well
>for such tasks. But what about other collision detection methods? For
>example, say I'm just using OBBs, as with RAPID. RAPID will detect
>collisions, but won't give me a distance or a pair of closest points. Does
>it mean it can't be used efficiently within a rigid body simulator ?


A potential problem with RAPID is that it works from a 'polygon soup', and
as such has no concept of solidity to distinguish between insideness and
outsideness.

So, depending on how small or fast your objects are, RAPID might not be
able to detect all your collisions (i.e. object A fully inside object B)
unless it's enhanced to do so. I guess this is probably not a problem
in general, as you're probably running your physical simulation at a fairly
high frame rate, but it could be an issue in some cases. Of course, the
triangle-triangle test could of course be extended to handle velocity,
which would fix this problem.


Also, I'm no expert on physical simulation, but one important aspect is
computing the contact manifold (the set of points of contact) and again
this is something RAPID would have to be enhanced with, to be able to
provide.


Christer Ericson
SCEA, Santa Monica

Re: [Algorithms] Using RAPID within a rigid body simulator

[Pierre T. <p.t...@wa...>]

> A potential problem with RAPID is that it works from a 'polygon soup', and
> as such has no concept of solidity to distinguish between insideness and
> outsideness.

Sure, but the concept does not exist in RAPID for a good reason : it does
not exist at all for polygon soups. It remains the only library so far to
deal with such cases. Tell me if I'm wrong, but say I want to simulate 256
stupid teapots, what choices do I have ?


> So, depending on how small or fast your objects are, RAPID might not be
> able to detect all your collisions (i.e. object A fully inside object B)

That's what swept volumes are for, I guess. Painful problem indeed.


> unless it's enhanced to do so. I guess this is probably not a problem
> in general, as you're probably running your physical simulation at a
fairly
> high frame rate, but it could be an issue in some cases. Of course, the
> triangle-triangle test could of course be extended to handle velocity,
> which would fix this problem.

Yes, this is the big issue: 4D collision detection. A real PITA:
- difficult to implement and visualize
- difficult to design since it suddenly links a perfectly static stand-alone
collision detection library to the heart of your dynamic simulation.

Perfectly painful.


> Also, I'm no expert on physical simulation, but one important aspect is
> computing the contact manifold (the set of points of contact) and again
> this is something RAPID would have to be enhanced with, to be able to
> provide.

Actually that's what we were discussing, I think. (...err I hope... because
that was my question at first !) The way I see it, the closest pair of
points becomes the points of contacts, as soon as the distance between the
two bodies is less than your favorite threshold.

All that junk starts to be very clear IMHO. The only nasty remaining part
will probably be the linear programming one for resting contacts, but I'm
really not in a hurry for that one.

...hmm and there are also those KDS thingies I still must read about... oh,
well.

Pierre

[Algorithms] N-body processing

[Pierre T. <p.t...@wa...>]

Ok, while we are deeply in touch with the subject (GJK, RAPID, Q-COLLIDE,
wacky patents...) let me introduce my new brain-blaster for the week-end:
N-body processing.

Some CD libraries such as RAPID only deal with two bodies. On top of that,
you need some more code to handle collision between multiple pairs,
something known as N-body processing. For example V-Collide is just made of
some N-body code built on top of RAPID.

I know the usual ways to deal with it: cut your world into sectors, use
spatial partitionning techniques, octrees, quadtrees, whatever, and use some
sweep&prune approach as a final death-blow.

In other words, assume I know which pairs are possibly colliding. My concern
is about the way I can manage (not detect) all of them. For example, for
each pair I could have to do some processing the first time the pair gets
active, and some processing when it stops colliding. For example in GJK it
would involve computing the initial supporting vertices in an efficient way.
Then, for each possible pair I may need some data structure to store some
values. I then need a way to:
- allocate and de-allocate ram for active pairs
- track active pairs
- access any possible pair in an efficient way

The most obvious and stupid solution would be something like an array of N*N
structures, with N = the number of objects in the simulation. Of course,
this is absolutely out of question. My standard test sets N = 1024, to give
you some ideas.

I'm curious about the solutions you people could imagine. Something with an
hash-table maybe, but then what would be a good hash-key? This also can be
seen as the reference/owner problem one can have with shared
materials/textures/etc, since an (owner, ref) couple is nothing more than a
pair of colliding/touching/linked/related entities. I don't think I have any
brilliant ideas for the moment, but I'm curious about yours....

Cheers,

Pierre

Re: [Algorithms] Using RAPID within a rigid body simulator

[Adam M. <amo...@dp...>]

>and simpler distance computations can be used. Would you mind sharing some
>details there? (..oh... wouldn't this code be included in Source Commander
>? - I think that was the name of the project IIRC. I'll check that.)

Sun, not Source!  But yes, the source code is all on my site, as part of SC.
It is all in this function, in the file CollBody.cpp:

void CollBody::GetCollisionReport(Mat33 &q1, Mat33 &q2, Vec3 &pos1,  Vec3
&pos2, clCollisionReport & cr);

It is rather long, so I won't paste it all in here.  It doesn't use anything
complicated like Johnson's whatever, only some heuristics.  It is also used
in the bouncy rigid body demo on the site, there you can see (I think the
faces and edges which are used are marked in red) that it is quite robust.

I'd like to point out that I am no longer using this code with my current
resting contact project.  I am currently using custom algorithmic collision
detection for simple cases as seen in the MathEngine demos, and am working
on implementing an OBB and space partition tree based approach I made up
myself.  This will not descend to the level of triangles!  Aside from the
obvious speed benefit, I believe getting perfect edge/vertex/face pairs for
resting contact is far more important than for colliding-only contact, and I
don't think I can guarantee this when I use arbitrary geometry and a simple
heuristics based scheme.  Also, as I have mentioned earlyer, I don't think
we will be able to/want to use display geometry to do physics on anyway,
with the rise of HW T&L in grx boards, and the associated explosion of
polygon counts, as well as the introduction of progressive meshes and
subdivision surfaces which keep the display geometry in constant flux
anyway.  I think bounding volumes can provide enough information about the
shape of an object to create very realistic looking physically based
animation.

--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo

>
>
>> The rigid body simulation itself typically doesn't need to track closest
>> points, unless they are really close, as above.  Permanent closest point
>> tracking between objects is usually used to speed up the collision
>detector
>> (temporal coherence).
>
>I don't follow you there. To me, permanent closest point tracking (as used
>in I-Collide for example) is only used to waste CPU time :) Because most of
>the time you just don't need them: you just need them when there's a
>collision. Makes sense ?
>
>Pierre
>
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] ENOUGH ABOUT THE PATENTS, PLEASE

[Matthew M. <ma...@me...>]

Hey folks;

Can we stop talking about ghost cars, centrifugal *ahem* devices, and
whatnot? We've got a bad noise problem here. This is not a political forum.

And please do NOT "list any current patents on 3d character animation that
they know about." COME ON!

It's an *extremely* worthwhile topic, but it's not an algorithm.

-- Matt

RE: [Algorithms] ENOUGH ABOUT THE PATENTS, PLEASE

[Akbar A. <sye...@ea...>]

just couldn't-

we write software.
patents effect us.
we also write algoritms.
algoritms are getting patented.
we can be effected.
we make a living of writing software.

it's better to be "prepared";
then to ship your game/application,
only 3 weeks later to hear a certain lawywer/company barking up
your ass.
and court fees cost "money". going to court is not _FUN_ and "giving" away
money in court costs is not something most people enjoy.
some of the gcc developers have been to court on there software.
see the gcc archives, there was a thread on patents, going to court and
being prepared; which lasted for a few months.
LOTS of "IMPORTANT" people (including linus as well) had something to say on
this.


i don't know about you, but this thread has helped me a lot on
what "TO AVOID".

a perfect exaple was the one where the guy got in trouble with a midway
cause they included a ghost option.
do you think they would have included this in the game if he had heard about
the patent?


akbar A.



-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Matthew MacLaurin
Sent: Thursday, August 17, 2000 2:40 PM
To: gda...@li...
Subject: [Algorithms] ENOUGH ABOUT THE PATENTS, PLEASE


Hey folks;

Can we stop talking about ghost cars, centrifugal *ahem* devices, and
whatnot? We've got a bad noise problem here. This is not a political forum.

And please do NOT "list any current patents on 3d character animation that
they know about." COME ON!

It's an *extremely* worthwhile topic, but it's not an algorithm.

-- Matt


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] ENOUGH ABOUT THE PATENTS, PLEASE

[Stephen J B. <sj...@li...>]

On Thu, 17 Aug 2000, Matthew MacLaurin wrote:

> Can we stop talking about ghost cars, centrifugal *ahem* devices, and
> whatnot? We've got a bad noise problem here. This is not a political forum.
 
I agree.

> And please do NOT "list any current patents on 3d character animation that
> they know about." COME ON!
 
I disagree.

We often talk about algorithms and why they may or may not be applicable
to some particular application.

Knowing that some algorithm isn't usable because it's patented is
just as important as knowing that it isn't usable because it's too
slow or generates some nasty artifacts or something.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] Using RAPID within a rigid body simulator

[Pierre T. <p.t...@wa...>]

I'm glad to see it works! Exactly what I wanted to see confirmed, thanks.


> No, I successfully postprocess RAPID's output to do that.  Specifically, I
> need a vertex-face pair or an edge-edge pair to be used as contacts.
RAPID

Agreed, those are the usual suspects.


> gives you intersecting triangle pairs, but if you look at where those
> triangles were one step earlyer (before they intersected) you can do some
> distance computations to find which of their features (verticed and edges)
> were the closest at that point, which gives the vertex face and edge
pairs.

This is what I was expecting to do, since this is the method used in
Q-Collide as well. I was actually wondering what kind of distance
computation would be the best here. I mean, while I'm at it I guess I can
use Johnson's distance subalgorithm on two triangles reported by RAPID as
intersecting in the next frame. But maybe there's no need for such a tool,
and simpler distance computations can be used. Would you mind sharing some
details there? (..oh... wouldn't this code be included in Source Commander
? - I think that was the name of the project IIRC. I'll check that.)


> The rigid body simulation itself typically doesn't need to track closest
> points, unless they are really close, as above.  Permanent closest point
> tracking between objects is usually used to speed up the collision
detector
> (temporal coherence).

I don't follow you there. To me, permanent closest point tracking (as used
in I-Collide for example) is only used to waste CPU time :) Because most of
the time you just don't need them: you just need them when there's a
collision. Makes sense ?

Pierre