Re: [Algorithms] Kinematic Collision

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

Get rid of your bias.  It sounds like a hack and, from what you say, 
isn't helping.  My guess is you're seeing problems because of bugs in 
your code that actually calculates the collision times.  (Ie the 
capsule/primitive intersection functions.)

To manage steps and slopes the way I've always done it is to raise the 
capsule slightly above the ground (to avoid such collisions), and then 
force your character to stand on the ground after each move.  You can 
calculate exactly how far up the capsule needs to be moved depending on 
how high your steps are and how steep the slopes your character can walk 
up are (iirc for a 45 degree slope you raise the capsule up by its 
radius).  If the point under the character after the move is higher than 
where he was before you need to move him up - you would need to run the 
same collision checks for this upward movement too.  If the point is 
lower you either move him down (again while performing the same tests), 
or if it's much lower start him falling.

Performance will come mostly from the speed at which you can traverse 
your collision data.  Which basically boils down to data organisation.  
A good kdtree (or even better kdop) should help you out there - assuming 
you don't have anything like that already.  Minimise the size of your 
tree nodes (we currently have 16 bytes per node for our kdtree but it's 
possible to do a lot better), index your vertices to reduce the overall 
size of the geometry data and make sure your tree traversal code isn't 
recursive.


Johan Gustafsson wrote:
> Does anyone know any good paper on handling collision between kinematic 
> objects & static shapes, I dont know the correct term but I think I'm 
> aiming at the collision model used in almost all games today, i.e. a 
> none-physical solution with bump & slide. My current implementation is 
> almost working but I have a couple of question marks I need to sort out, 
> mainly stability, performance and slope/stepping.
>
> The way I'm doing it now is a recursive collision response, performing 
> the following steps.
>
> While iterations are not to high
>
>     Step 1:
>     If our current position is our target position we can end, otherwise 
> do a capsulesweep from our current position to our target position + a 
> small bias, if no collision is reported we can end otherwise continue to 
> step 2
>
>     Step 2:
>     Calculate the closest position before the collision point and offset 
> with the bias, Set our current position to this location.
>
>    * NewPosition = Position + Direction * (DistanceToImpact - Bias)
>
>     Step 3:
>     Find the vector from the new position and the target location and 
> retrieve the reflection/tangent components. Set new target position to 
> the new current position and add both components scaled by a
>     bounce/friction value [0, 1] to it..
>
>     * NormalMotion = NormalComponent * Bounce
>     * TangentMotion = TangentComponent * Friction
>     * NewTargetPosition = NewPosition + NormalMotion + TangentMotion
>
>     Repeat Step 1:
>
> This algo is not very stable, sometimes when I calculate the position 
> right before the impact point it will closer then my bias, resulting in 
> weird behavior, but I'm unsure how this can happen since I make sure to 
> include the bias during the offset, and I have also tried setting the 
> collision point with 2x bias as offset.
>
> I'm also worried that it will fail to solve the collision before running 
> out of iterations, but building the level with some constraints is maybe 
> enough promise to never allow this to happen? How are you guys doing 
> this? I have also peaked on the NxCharacter source and it looks ALOT 
> more advanced then my simple algo and I take it like I'm missing to 
> perform some important steps?
>
> I also whonder how stepping & sloping could be handled, right now I was 
> hoping that the capsule hemispheres would automatically solve this issue 
> by giving me tangential motion for objects small enough, causing 
> automatic stepping, but so far no luck, but this is probably due to the 
> bias issue.
>
> Atleast the capsule cannot interpenetrate objects, but I need to be able 
> to handle slops & stairs, any link to a good paper or personal 
> experience/knowledge is highly appreciated.
>
> ------------------------------------------------------------------------------
> 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
>
>