gdalgorithms-list

Re: [Algorithms] Kinematic Collision

[Mat N. <mat...@bu...>]

Simple level geometry does not mean simple appearance.

MSN
-----Original Message-----
From: chr...@pl... [mailto:chr...@pl...] 
Sent: Wednesday, September 09, 2009 9:34 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Kinematic Collision

James Robertson wrote:
>> Simple. You tell your art/design team not to design
>> geometry like that! (No, really.)
>
> That's only a solution for the most simplistic
> single player games these days.

Perhaps God of War is simplistic to you, but it
works just fine for us.

Programmers overengineer way too much.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica


------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
trial. Simplify your report design, integration and deployment - and focus on 
what you do best, core application coding. Discover what's new with 
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Kinematic Collision

[James D. <jd...@gm...>]

Agree with Christer here that ultimately fixing the mesh is the  
answer, such defects will cause artifacts in any algorithm to some  
degree... but one thing that is pretty useful is having code that  
validates input from the artist and smacks them around a bit if they  
decide to put in a bunch of T-junctions or gaps.

-james

On Sep 9, 2009, at 9:33 AM, chr...@pl... wrote:

> James Robertson wrote:
>>> Simple. You tell your art/design team not to design
>>> geometry like that! (No, really.)
>>
>> That's only a solution for the most simplistic
>> single player games these days.
>
> Perhaps God of War is simplistic to you, but it
> works just fine for us.
>
> Programmers overengineer way too much.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> 30-Day
> trial. Simplify your report design, integration and deployment - and  
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Kinematic Collision

[<chr...@pl...>]

James Robertson wrote:
>> Simple. You tell your art/design team not to design
>> geometry like that! (No, really.)
>
> That's only a solution for the most simplistic
> single player games these days.

Perhaps God of War is simplistic to you, but it
works just fine for us.

Programmers overengineer way too much.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Kinematic Collision

[James R. <ja...@fu...>]

That's only a solution for the most simplistic single player games these 
days.


chr...@pl... wrote:
> Alen Ladavac wrote:
>   
>> [...]
>> As far as I understand the approach, there is no way to differentiate
>> A from B, as the capsule doesn't touch anything, and the ray always
>> hits just the floor. However in B, the character is slipping through a
>> narrow passage, and the rendering will show his legs in the two
>> M-labeled rocks.
>>     
>
> Simple. You tell your art/design team not to design
> geometry like that! (No, really.)
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

Re: [Algorithms] Kinematic Collision

[<chr...@pl...>]

Alen Ladavac wrote:
> [...]
> As far as I understand the approach, there is no way to differentiate
> A from B, as the capsule doesn't touch anything, and the ray always
> hits just the floor. However in B, the character is slipping through a
> narrow passage, and the rendering will show his legs in the two
> M-labeled rocks.

Simple. You tell your art/design team not to design
geometry like that! (No, really.)

Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Kinematic Collision

[Alen L. <ale...@cr...>]

Tuesday, September 8, 2009, 8:33:27 PM, Jon wrote:
> If there are upwards-facing contacts from the bottom of the capsule
> of the lollipop, I do extra processing on that.

Hm, I fear some ASCII art is due, please use fixed font...

Situation A:

   O
   |
  ---

Situation B:

   O
  M|M
  ---

As far as I understand the approach, there is no way to differentiate
A from B, as the capsule doesn't touch anything, and the ray always
hits just the floor. However in B, the character is slipping through a
narrow passage, and the rendering will show his legs in the two
M-labeled rocks.

Does thise make sense?

Alen

Re: [Algorithms] Kinematic Collision

[Jon W. <jw...@gm...>]

Alen Ladavac wrote:
> Jon wrote at 9/7/2009:
>   
>> The simplest character I find that I can get away with in the general
>> case is the lollipop. One ray for legs, and a capsule for the body.
>>     
>
> I see the lollipop mentioned every once in a while, and I just have to
> ask this: Do you have some trick for when the character gets between
> two knee-high rocks (or similar)? Or do you just accept the fact that
> its legs will be deeply embedded in the floor?
>   

If there are upwards-facing contacts from the bottom of the capsule of 
the lollipop, I do extra processing on that. Others may have other 
options. However, because you get those lollipop contacts anyway, the 
additional processing cost is de minimis, and it does add some robustness.

Sincerely,

jw




-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Kinematic Collision

[<chr...@pl...>]

Pierre Terdiman wrote:
> >The problem we've found with a single ray is unwelded geometry or cracks
> >in geometry - the ray can fit between them and not register a hit
>
> ...and I seem to remember a presentation from Christer about this
> problem, listing "using fat rays" as one way to solve the problem.
> But then again, what is a fat raycast if not a sweep test? :)

You don't need fat tests to solve the robustness problem. You can
do robust (standard) rays just fine as long as you do the testing
properly and adhere to some rules.

Proper testing involves sharing all computations that can be shared
between neighboring primitives. Adhering to some rules involves
not letting your test point go into the surface of the polygons
and making sure the geometry is well-formed (welded, properly
convex, etc).


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Kinematic Collision

[Pierre T. <pie...@gm...>]

>The problem we've found with a single ray is unwelded geometry or cracks
>in geometry - the ray can fit between them and not register a hit

...and I seem to remember a presentation from Christer about this problem,
listing "using fat rays" as one way to solve the problem. But then again,
what is a fat raycast if not a sweep test? :)

- Pierre

Re: [Algorithms] Kinematic Collision

[Alen L. <ale...@cr...>]

Jon wrote at 9/7/2009:
> The simplest character I find that I can get away with in the general
> case is the lollipop. One ray for legs, and a capsule for the body.

I see the lollipop mentioned every once in a while, and I just have to
ask this: Do you have some trick for when the character gets between
two knee-high rocks (or similar)? Or do you just accept the fact that
its legs will be deeply embedded in the floor?

Thanks,
Alen

Re: [Algorithms] Kinematic Collision

[Mark W. <Mwa...@to...>]

The problem we've found with a single ray is unwelded geometry or cracks
in geometry - the ray can fit between them and not register a hit, and
the character falls for a frame or two (maybe longer if the player has a
very small velocity). Using multiple rays (clustered for a single
spatial query) solves this relatively easily. Then there's the situation
where the ray(s) don't collide with anything but the body object (eg.
capsule) does, like if you jump into a barrel where the rays don't touch
the bottom but the capsule sits on the rim of the barrel. As long as you
handle these cases it works pretty well - though it is pretty funny to
jump into a barrel and get "wedged" like a fat dude (the first time
anyway!) :-)

Cheers,
Mark

> -----Original Message-----
> From: Jon Watte [mailto:jw...@gm...] 
> Sent: Tuesday, 8 September 2009 3:21 AM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Kinematic Collision
> 
> 
> The simplest character I find that I can get away with in the 
> general case is the lollipop. One ray for legs, and a capsule 
> for the body. The capsule extends between the knees and the 
> top of the head, and is slightly wider than shoulders (to 
> give some space for swinging arms, etc). This is fairly cheap 
> (capsule tests are cheap, and seldom actually collide with 
> things), and nicely prevents you from penetrating things 
> you're not supposed to.
> 
> If you're really worried about sideways penetrations, or want 
> to cut a hundred more cycles from the collision test, you can 
> replace the capsule with a sphere. It won't let characters 
> get as close to things (or each other, if you test char/char), though.
> 
> Sincerely,
> 
> jw
> 
> 
> David Black wrote:
> > Figuring out what surface is fine to "be on" and how to handle 
> > surfaces you should not be in, or the penetration into either is a 
> > major pain.  In the simple cases its trivial, but in the face
> >   
> 
> -- 
> 
>   Revenge is the most pointless and damaging of human desires.
> 
> 
> --------------------------------------------------------------
> ----------------
> Let Crystal Reports handle the reporting - Free Crystal 
> Reports 2008 30-Day trial. Simplify your report design, 
> integration and deployment - and focus on what you do best, 
> core application coding. Discover what's new with Crystal 
> Reports now.  http://p.sf.net/sfu/bobj-july 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgo
> rithms-list
> 
> 

Re: [Algorithms] Kinematic Collision

[Jon W. <jw...@gm...>]

The simplest character I find that I can get away with in the general 
case is the lollipop. One ray for legs, and a capsule for the body. The 
capsule extends between the knees and the top of the head, and is 
slightly wider than shoulders (to give some space for swinging arms, 
etc). This is fairly cheap (capsule tests are cheap, and seldom actually 
collide with things), and nicely prevents you from penetrating things 
you're not supposed to.

If you're really worried about sideways penetrations, or want to cut a 
hundred more cycles from the collision test, you can replace the capsule 
with a sphere. It won't let characters get as close to things (or each 
other, if you test char/char), though.

Sincerely,

jw


David Black wrote:
> Figuring out what surface is fine to "be on" and how to handle
> surfaces you should not be in, or the penetration into either is
> a major pain.  In the simple cases its trivial, but in the face
>   

-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Kinematic Collision

[Glenn F. <ga...@ga...>]

spot on really
key point here is to avoid arbitrary geometry from the artists when using
the raycast technique. if you can't do this and you have to support
arbitrary geometry and/or dynamic geometry - it's probably best to use a
modern technique, even though it is more expensive.

On Sun, Sep 6, 2009 at 8:48 AM, David Whatley <da...@pl...> wrote:

> Figuring out what surface is fine to "be on" and how to handle surfaces you
> should not be in, or the penetration into either is a major pain.  In the
> simple cases its trivial, but in the face of arbitrary geometry from the
> artists, the slightest things can creep in to mess up algorithms that use to
> work fine.  What amazes me is that this is one of those problems where the
> solution is more or less obvious to a human, but is difficult to express in
> realtime code.
>
>

Re: [Algorithms] Kinematic Collision

[David B. <db...@fa...>]

>>>
Figuring out what surface is fine to "be on" and how to handle
surfaces you should not be in, or the penetration into either is
a major pain.  In the simple cases its trivial, but in the face
of arbitrary geometry from the artists, the slightest things can
creep in to mess up algorithms that use to work fine.  What
amazes me is that this is one of those problems where the
solution is more or less obvious to a human, but is difficult to
express in realtime code.
<<<

While perhaps not relevant to big games, my opinion is that the best way
to tackle this is 2 pronged. Firstly handle all casses as well as
possible, dont assume that the player is ever in a valid location and
handle interpenetration as gracefully as possible. 

Secondly "prevent" the artists from creating unpleasant geometry as far
as possible by defining collision geometry editing operations in such a
way as to make it tricky to create invalid objects. ie just allow CSG
with convexes(yeah CSG has pitfalls but problems can be detected during
editing) + primitives like capsules/spheres/boxes. General triangle mesh
collision geometry, created by artists rather than code, just seems like
something which speeds up initial creation but then has a large cost
later on trying to solve all the problems which appear during play.

David

-- 
http://www.fastmail.fm - One of many happy users:
  http://www.fastmail.fm/docs/quotes.html

Re: [Algorithms] Kinematic Collision

[David W. <da...@pl...>]

Yeah, character controllers are tough.  We use PhysX in HeroEngine 
(www.heroengine.com) and have been an early adopter of their original 
character controller... and made a lot... a lot... of code fixes to it 
(via John Ratcliff).  But still, is yet to be as solid as I'd hope.  And 
does not perform fast enough for all the NPCs to use it.

Of course the engine let you do whatever you want.  So you can just do 
simple "grounding" raycasts for NPCs and only use a character controller 
for your character or those close, or whatever fits your game best.

But, in general, raycast colllision detection is pretty awful and 
leaky.  I used that technique before PhysX and it had so many 
pathological cases that it was endless tweaking that would correct one 
thing and break another.

Figuring out what surface is fine to "be on" and how to handle surfaces 
you should not be in, or the penetration into either is a major pain.  
In the simple cases its trivial, but in the face of arbitrary geometry 
from the artists, the slightest things can creep in to mess up 
algorithms that use to work fine.  What amazes me is that this is one of 
those problems where the solution is more or less obvious to a human, 
but is difficult to express in realtime code.

-- David


Jeff Russell wrote:
>
>     I saw a lot of people using the "complex" version for all
>     characters in the world, all the time, while there is often
>     another sub-system doing pretty much the same job for NPCs:
>     path-finding. The path-finder already computed a collision-free
>     path, so for those characters it's a lot easier to "get away with"
>     simple raycasts.
>
>
> Agreed.
>
> Just finished a title where I had to make that exact call - the 
> character controllers were very expensive to run and we had large 
> character counts. Removing character controllers from most NPCs (and 
> using a few simple raycasts instead) solved the problem nicely, and 
> the pathfinding picked up the slack.
>
> Tried a distance based LOD scheme on these too. Proved unnecessary though.
>
> -- 
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com <http://www.8monkeylabs.com>
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Kinematic Collision

[Jeff R. <je...@8m...>]

>
> I saw a lot of people using the "complex" version for all characters in the
> world, all the time, while there is often another sub-system doing pretty
> much the same job for NPCs: path-finding. The path-finder already computed a
> collision-free path, so for those characters it's a lot easier to "get away
> with" simple raycasts.


Agreed.

Just finished a title where I had to make that exact call - the character
controllers were very expensive to run and we had large character counts.
Removing character controllers from most NPCs (and using a few simple
raycasts instead) solved the problem nicely, and the pathfinding picked up
the slack.

Tried a distance based LOD scheme on these too. Proved unnecessary though.

-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

[Algorithms] Antonio Martini is out of the office.

[<Ant...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


I will be out of the office starting  01/09/2009 and will not return until
07/09/2009.

I will respond to your message when I return.


**********************************************************************
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom
Registered in England: 3277793
**********************************************************************


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: us-ascii

wsBVAwUBSqHVUGCVqsCql6XBAQhymwf9Ezkt4wxh3R+ifwzt4n0wmB7yTwVqfehk
iq8/rHT6nHlzv58WuCkgFmlCSESH7V5IaHbGE++vM7ap9q3gIbXq8FfH02wFpnOZ
wN26l2LzJmim9YLcByQc2Gj46NSsHwGHRtXvdmYLxd5m3XwSa3NSNDIXk41hMYAs
rtaaWH+4olMsD37vPiDMR8pDA+t3tTiJiCXLwm27wyg62T6kRKSs8krnxkqcogXP
6FgB7zKn4rq+es3345hgbDivK74PBe2ZBfI0LZ+k79XbCb9Eg/ZAa6yQkazpDqBw
R+S2xztCZRVs9JlUZXVrYOenBBYJC+pDLi6BtO0w57pBM7q2x/c6Ug==
=+hEm
-----END PGP SIGNATURE-----

Re: [Algorithms] Kinematic Collision

[Pierre T. <pie...@gm...>]

>
> I think a lot of people are overthinking character collision
> detection and think you need volumetric representation
> with sweep tests, etc.
>

I think a lot of people are overthinking a lot of things those days... :)

When in actuality you can often get away with a few line
> segment probes to detect collision with the world and use
> a simple capsule test (or similar) to avoid character-
> character interpenetration.
>

I remember a PPT describing the system used in GoW, yeah. It looked a lot
like what we used some 10 years ago now, when I was working for a french
compagny that should remain nameless. It was my first attempt at character
collision detection with the world, and I used raycasts because I didn't
know anything else. And indeed, it worked ok. Not perfect or anything but
good enough for our needs.

Now, 10 years later, writing code for a middleware... we can't decently sell
simple raycasts to customers constantly asking for "next gen" solutions, can
we? They never let you "get away with" anything :)

That being said, and just to stay on-topic rather than going on a tangent to
discuss the pros & cons of middleware, it might be worth it to provide two
different CCTs to users: one "complex" version and one "light", simpler
version. I saw a lot of people using the "complex" version for all
characters in the world, all the time, while there is often another
sub-system doing pretty much the same job for NPCs: path-finding. The
path-finder already computed a collision-free path, so for those characters
it's a lot easier to "get away with" simple raycasts. And when all NPCs use
the cheapest version, it doesn't matter anymore if the player uses a more
costly but perhaps more robust test. (Whether it really -needs- it or not is
another story, whose answer is probably game-specific),

- Pierre

Re: [Algorithms] Kinematic Collision

[<chr...@pl...>]

Pierre Terdiman wrote:
> Unless something really changed in the 2 years I spent
> outside of the physics world, computing a good
> depenetration vector was not so easy. [...] In any
> case *not* running any of those algorithms was certainly
> faster than doing so, in the context of a character
> controller. So that's what we did.

I think a lot of people are overthinking character collision
detection and think you need volumetric representation
with sweep tests, etc.

When in actuality you can often get away with a few line
segment probes to detect collision with the world and use
a simple capsule test (or similar) to avoid character-
character interpenetration.

Keep it simple.

Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Kinematic Collision

[Pierre T. <pie...@gm...>]

>
> Requiring a seperate query to test for initial intersection seems very
> wasteful, since you are going to have to traverse the
> broadphase/midphase structures twice as often as otherwise.


Well it depends on a lot of things, including "irrelevant" bits like
implementation details. For example:

- if this is really only used (and useful) for the "initial intersection",
then it doesn't really matter that you traverse the BP structure twice. At
least you pay the price only once when it is useful, rather than all the
time "just in case" somebody needs the results.

- with the implementation we had, providing a correct depenetration vector
*was* more expensive than not doing so. Hence, we decided not to run that
often-useless-code all the time.

Anyway I don't think there is a real clear best answer here, as usual with
middleware. Best approach depends on your game\usage patterns\etc, and
approach A will please a group of people and piss off another group, which
would prefer approach B.


> Also I think the depenetration vector is the important part... I guess
> you could perform some sort of binary search to depenetrate but that
> seems error prone and expensive.
>

No, binary searches suck for this. In our case there was clearly a set of
functions missing from the API.

The depenetration vector is the important part... sometimes :) Again, it
really depends on your game requirements. I would say it's the important
part to expose in a middleware because that's the part which would be
difficult for users to re-implement, in any case!


>
> I dont think it is terribly difficult to provide depenetration results,
> the way I do it is detect initial penetration and if detected compute
> the direction of least penetration and perform another sweep(with just
> the relevant parts of the objects) to determine the depentration
> distance. It probably amounts to 50 lines of code per sweep test, which
> could be easily disabled with a flag if not needed.
>

Unless something really changed in the 2 years I spent outside of the
physics world, computing a good depenetration vector was not so easy. I mean
last time I checked, EPA was bloody painful to implement and not terribly
reliable, SAT-based approaches were easy to implement but not very fast or
scalable, and anything involving arbitrary triangle meshes was a nightmare
because "simply" computing depenetration vectors for each triangle
individually was next to useless. Maybe I'm missing something here. In any
case *not* running any of those algorithms was certainly faster than doing
so, in the context of a character controller. So that's what we did.

(I'm travelling atm so I may have missed a few posts. Brb!)

Re: [Algorithms] Kinematic Collision

[David B. <db...@fa...>]

>>>>
  Yes, I agree with that. That's why we exposed a set of
  functions to test exactly this (if a given position is valid),
  However it puts the power (or the burden, depending on your
  point of view) in the hands of users: -they- have to test for
  valid positions. At the time we felt that it was more
  efficient than running the "useless" depenetration code
  automatically all the time.
  The only problem with PhysX is that the queries to test for
  valid positions only return a boolean answer (position is
  valid or not). When it is not, the depenetration vector is not
  provided. So it is not as useful as it could be. (Boolean
  queries are a lot faster and often enough, so that was the
  reason IIRC).
  - Pierre
<<<<

Requiring a seperate query to test for initial intersection seems very
wasteful, since you are going to have to traverse the
broadphase/midphase structures twice as often as otherwise. Not to
mention the maths that would have been saved by providing the result
with the sweep query.

Also I think the depenetration vector is the important part... I guess
you could perform some sort of binary search to depenetrate but that
seems error prone and expensive. 

I dont think it is terribly difficult to provide depenetration results,
the way I do it is detect initial penetration and if detected compute
the direction of least penetration and perform another sweep(with just
the relevant parts of the objects) to determine the depentration
distance. It probably amounts to 50 lines of code per sweep test, which
could be easily disabled with a flag if not needed.

David

-- 
http://www.fastmail.fm - Send your email first class

Re: [Algorithms] Kinematic Collision

[Pierre T. <pie...@gm...>]

> >Handling intersections in the initial state - or at least a separate query
> that determines

>whether a given starting position is valid - is fairly important for a lot
> of things you might

>do with the character.  In our games characters transition between
> collision states,

>change models, transition from AI to player control, get teleported, get in
> and out of

>vehicles, transition from animation control to physical control, etc.  Most
> of these are far

>easier to implement if you can test for a valid starting position.
>
> Yes, I agree with that. That's why we exposed a set of functions to test
exactly this (if a given position is valid), However it puts the power (or
the burden, depending on your point of view) in the hands of users: -they-
have to test for valid positions. At the time we felt that it was more
efficient than running the "useless" depenetration code automatically all
the time.

The only problem with PhysX is that the queries to test for valid positions
only return a boolean answer (position is valid or not). When it is not, the
depenetration vector is not provided. So it is not as useful as it could be.
(Boolean queries are a lot faster and often enough, so that was the reason
IIRC).

- Pierre

Re: [Algorithms] Kinematic Collision

[Jay S. <Ja...@va...>]

> > I found that the most important thing to make this work is a very
> robust
> > sweep test(including hit normal etc). The sweep should also handle
> > initial intersection (no matter what you do 8h1t Happens(tm)) giving a
> > sensible depenetration vector and a distance to move to depenetrate
> the
> > objects. Pair wise seems good enough, although it would probably be
> > possible to make this recursive as well.
> >
> > Since I added initial penetration handling my controller has not had
> any
> > problems, including moving lifts/platforms.
> 
> I suppose it depends on your game. It's true that providing a
> "depenetration
> vector" can be useful, but I found it easier and more robust to just
> make
> sure it's never needed. In my small-game-at-home
> (http://www.codercorner.com/blog/?p=355) I more-or-less use the same
> code as
> NxCharacter, and so far it has been robust enough. Granted, I don't have
> big
> needs or requirements out there, but I do have moving platforms :)

Handling intersections in the initial state - or at least a separate query that determines whether a given starting position is valid - is fairly important for a lot of things you might do with the character.  In our games characters transition between collision states, change models, transition from AI to player control, get teleported, get in and out of vehicles, transition from animation control to physical control, etc.  Most of these are far easier to implement if you can test for a valid starting position. 

Jay

Re: [Algorithms] Kinematic Collision

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> ...but you are talking about a physics engine here. I was only talking 
about
> an old-style "character controller", a.k.a. collide-and-slide, à la Paul
> Nettle / Quake / etc. Typical "modern" physics engines certainly need
> penetration vectors. Character controllers, not necessarily - you can go 
a
> long way without.

Ahhh, yes, you might get away with a lot more with a simple character 
controller. As long as nothing is allowed to 'push' the character into the 
ground or weigh it down, that is! :)

> Can you give more details here? I think you can find "a" penetration
> vector -in the direction of motion-, yes, but it is vastly different 
from
> "the" penetration vector, a.k.a. MTD, which can be in a completely 
different
> direction. I don't think I know a way to compute both with the same 
piece of
> code.

Ok, so if we're talking about a generic convex linear cast here, we can do 
the ray intersection (where the ray is the delta velocity vector of the 
two objects) against the minkowski difference of the two shapes (which is 
now static) iteratively as long as we have a utility function that will 
give us the closest point on the MD and the normal at that point. This 
information is actually already giving us penetration info if we start 
initially penetrated. 

Basically, you iterate (starting with the ray start position) asking the 
system for the closest point on the MD to the current ray pos and the 
normal. Then you intersect the ray with that normal and carry on. It 
usually converges very quickly, especially for poly objects and you get 
the TOI and the penetration info in one, should there be a TOI of 0. You 
can even use this to handle objects that rotate as well with slight 
modification of the algorithm.

This is gino van den bergen's algorithm btw, where he uses GJK for the 
utility function - but we don't have to use GJK, we can use any custom 
written algorithm. So for two spheres, you just need closest point on 
sphere to given point, which is easy to write, or for triangle vs sphere 
you just need a distance to triangle function...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: ISO-8859-1

wsBVAwUBSp99P3ajGqjtoMHxAQiBKQf8Ch+o3+FpA1QqT0KJBDVDQ3g26+UT6EvP
lQO4KwCHlVFDKYMpxnP76W3JFNixxpfTo6vBWyuupau1ps5+Nhq+LJWUwIQoSI9l
A4BFDekzcssFnR78MEffFyr6aLa/II0RclIcVl2tDCou6wLpLRSd6ojk29h6dW59
RhX5kIdTYPEZlqLtlh2bCGKxPMqT5q5l7JjPHdIesaEGws3pfSMtWFRIK4XDAm1q
CUjmk6PcuNa+GZqzZ4JuMECW8xTGAZ4LITjKd4+aC/l4LP8Ewr2KGr47IHk6BLI0
dIrPmxB6zblEwK6U1spUsruPVJpPvgh3KhOZOg+6QfPVkrAudQ3PPQ==
=PUTi
-----END PGP SIGNATURE-----

Re: [Algorithms] Kinematic Collision

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> How can you be sure that interpenetration never occurs then? Floating 
> point errors seems to produce small but very relevant
> problems for me. As an example, when simply dropping a capsule to the 
> floor using the 'inner skin' method without bias the
> solved position right before penetration should be 0.0 but the 
> calculations will very often produce a number such as -2e-06,
> so in my world creating 'a perfectly stable' solver doesn't exist.

The idea with the inner hull is that even if (more like when, actually) 
you get a slight error like you mention, it doesn't matter because you can 
move the object back by the distance between outer hull and the inner hull 
which means that next frame you don't start penetrated.

> Why is using a bias considered a 'hack', isn't it just to avoid this 
> kind of problems?

Its a hack because it introduces other problems - just using the outer 
hull and then moving that back means you are moving the object to a point 
just before where it was the last time; this can push it through other 
objects (imagine being on the inside of a triangle (in 2d) in a corner).

> I also run with a bounce of 0, meaning I never apply a position vector 
> away from the contact, maybe its not legal to have it
> zero?

No, thats perfectly legal :) Otherwise all your characters would bounce 
around the world like they were on pogo sticks! :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSp951XajGqjtoMHxAQjGkwf/V0yO90qpM1KlHGgAZsWELt4EqF1lQiBQ
faApgU0iPGtmGHx8p8HSTAIMoSvtyBCN8klXzynNxeCgeQnqrdQJ27QMcYCSVGTA
vN/PwRD/FPERoPis6yGSNwP510OAPh/kQZOdZ6YxBeHfqVYlUWAak7/zszLUziPh
s4tafQRk877eIjzKu+Wc7mi2ElSOU+DnSoEB3WMtoHcxuQPpY2ZwTqSYKaisC96f
/XMBnEqb/sqNKuhgPVIe2VMRr+yqzgQjYUlbBiKlAqidos6Jch0EZA5hwV9yDF+o
SjOiHqxNpOyL1vO1kuODddnPITLgb0Ao1NOkXrqHk85E4WfkiFZZyA==
=tDp5
-----END PGP SIGNATURE-----