gdalgorithms-list

Re: [Algorithms] Kinematic Collision

[Jeremiah Z. <jer...@vo...>]

I haven't worked in this area in a long time but I remember numerical
problems were a major problem (along with subtle and difficult to find
bugs). I had to make the character bounce away from the surface a small
amount or else the character would get stuck. And you have to be very
careful and explicit about the bounce away part:

	// Modify the velocity.
	{
		// Normalize the velocity and then project it into the
slide plane.
		float32 const original_magnitude =
vm_VectorNormalize(&velocity);
		if(original_magnitude == 0.0f)
		{
			velocity = Zero_vector;
		}
		
		float32 wall_part = velocity_slide_normal * velocity;
		{
			if(wall_part < 0.0f)
			{
				wall_part = fabsf(wall_part);
				velocity += velocity_slide_normal *
(wall_part + wall_epsilon);
			}
			
			// Fractional velocity in the slide plane due to
the projection.
			velocity *= original_magnitude;
			
			if(velocity_param > 0.0f)
			{
				// Tweak the amount of velocity.
				float32 const projected_magnitude =
vm_VectorNormalize(&velocity);
				if(projected_magnitude == 0.0f)
				{
					velocity = Zero_vector;
				}
				else
				{			
					// Scale the amount of velocity
between the original amount and the projected amount.
					velocity *= projected_magnitude
+ velocity_param * (original_magnitude - projected_magnitude);
				}
			} // end if
		}
	}

Notice how the velocity is normalized before the bounce away epsilon is
added and then scaled back up as opposed to projecting the full velocity
into the plane and adding a small amount to it.

Another problem is sliding up against a wall on a slanted surface. You
need to make sure the resulting velocity is parallel to the surface yet
still sliding against a wall. You can think of this as being constrained
to the direction of a line defined by the intersection of the ground and
wall surface planes. Corners are another problem because you'll get
jitter as you transition back and forth between walls. You need to know
that you are in a corner and are affectively constrained to a point (the
intersection of 3 planes).

One more thing, the swept-test should ignore collisions that are
occurring as you move away from a surface (velocity dot normal > 0) so
that if you are initially penetrating, you can move away from the
surface without getting stuck.

-----Original Message-----
From: Johan Gustafsson [mailto:spi...@gm...] 
Sent: Wednesday, September 02, 2009 1:02 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Kinematic Collision

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.

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

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?

The code is not very long and if some extremely helpful soul with a 
better math/physics background then me would give it
a look I'd be in heaven.

------------------------------------------------------------------------
------
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-lis
t

Re: [Algorithms] Kinematic Collision

[Johan G. <spi...@gm...>]

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.

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

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?

The code is not very long and if some extremely helpful soul with a 
better math/physics background then me would give it
a look I'd be in heaven.

Re: [Algorithms] Kinematic Collision

[Pierre T. \(GMail\) <pie...@gm...>]

(for some reasons I don't receive my posts to the list, but they still seem
to go through. Weird.)

> It can happen for many reasons; our constraint solver runs for a fixed
> number of iterations, so it can terminate without fully resolving - stacks
> of objects will sink into each other over time, and the penetration vector
> is essential for resolving this. Also we have lots of motored joints like
> pistons etc which can force objects through each other.

...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.

> If you code the collision routines carefully, you should be able to pull
> out the penetration info at the same time as finding the TOI...

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.

- Pierre

Re: [Algorithms] Kinematic Collision

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

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

> AFAIK it is still the case, yes. The rationale was that:
> - when used correctly (again, see small game above) penetration never
> happens
> - running an initial overlap check "just in case" seemed too costly

In our projects we find that its essential to be able to recover from 
penetration, and we weren't able to rule it out... :/

It can happen for many reasons; our constraint solver runs for a fixed 
number of iterations, so it can terminate without fully resolving - stacks 
of objects will sink into each other over time, and the penetration vector 
is essential for resolving this. Also we have lots of motored joints like 
pistons etc which can force objects through each other.

If you code the collision routines carefully, you should be able to pull 
out the penetration info at the same time as finding the TOI...

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

wsBVAwUBSp6jcnajGqjtoMHxAQhpQQf+PfUOPGvZGRaO69slR7mNmlwq6pcSeOvZ
ksS2efm9KiHujNu6cuDj26FuUqGkdGRYlnPF7DCQhIu/9AAFJFCis5+ziPjPDzbZ
5XDME6LEigCuQC3gb/zCh8KzUTZg6lnfvsBo7EAP9n2/i8gSJ7HxohJNdDbTWxqL
WEJ2xVziB4pcFms2g6adzAQcCgKAlCoUA3PSRMcO+BN81Q+QUV06rHkDQ7UC8ZwL
aTskWbP+PIUvPrkmBZpfpRq9SbYQtPgzJE13/1BCNgKqgEMXvNPq9qptNXfBnRIb
1Lv7SMnJVCIuEOlpxf8NZl+ou1yRXd7NBZkGLOyHUa/B4c+pGS5aeA==
=vS+X
-----END PGP SIGNATURE-----

Re: [Algorithms] Kinematic Collision

[Pierre T. \(GMail\) <pie...@gm...>]

(Hi Dave! It's great to hear from you!)

> 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 :)


> About using the PhysX stuff, I would say the CCD is OK for demo/basic
> use but is probably not modular enough to do something more
> sophisticated (eg Tomb Raider style) it doesnt have the concept of
> states/transitions

I think there is a lot of IK in Tomb Raider that is clearly beyond the scope
of a classic character controller. I would say that states/transitions are
part of an animation engine, it's unrelated to "the CCT". (But maybe we are
not talking about the same things here.). In the game above for example, I
have some small IK, a hell of a lot of "states" and "transitions", and a
"character controller". They all interact with each other, but I would say
they are different things.

In any case if you guys have requests/suggestions about this, what to
improve, what to add, what to do better, etc, feel free to list them here.


> plus it seems too tied to the underlying geometric
> database.

I have to strongly disagree about that one :) It's like the opposite. The
game above uses "NxCharacter" but does *not* use PhysX otherwise. The
character controller logic is the same, but the collision queries are
performed against a completely different database than PhysX.


> Plus I think that handling of initial
> intersection is "undefined". Not sure if this is still the case? (Any
> idea Pierre?)

AFAIK it is still the case, yes. The rationale was that:
- when used correctly (again, see small game above) penetration never
happens
- running an initial overlap check "just in case" seemed too costly

I left the company 2 years ago (although I'm going back now), so take this
with the proverbial grain of salt, things might have changed.

- Pierre

Re: [Algorithms] Kinematic Collision

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

Hi,

About the inner/outer hull method, I think this is definitely the way to
go. Plus using recursion to handle sliding etc. (multiple checks to
handle gravity(sweep down), stepping(a sweep at a higher offset),
climbing, crouching etc).

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.

About using the PhysX stuff, I would say the CCD is OK for demo/basic
use but is probably not modular enough to do something more
sophisticated (eg Tomb Raider style) it doesnt have the concept of
states/transitions plus it seems too tied to the underlying geometric
database.

I also decided not to use the PhysX sweeps in my hobby project for a
couple of reasons, ie I didn't want to call into native code for every
shape query(this is XNA). Plus I think that handling of initial
intersection is "undefined". Not sure if this is still the case? (Any
idea Pierre?)

David 


On Wed, 02 Sep 2009 14:45 +0200, "Johan Gustafsson"
<spi...@gm...> wrote:
> Thanks for the feedback, very helpful.
> 
> About the the inner hull sweeptest, this is kinda inverted to my bias,
> with my bias I did a sweep 
> using a larger hull and then when finding collision i calculate the
> position to intersection and
> subtract the bias. To me they are both the same but I'll definitely give
> it a try.
> 
> Using rigid bodies seems to me much more problematic and having to
> control the character using impulse/forces
> is the main reason I choose the first method.
> 
> 
> James Robertsson Wrote:
> /"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.)"
> /
> I'm actually using PhysX SDK for collision detection and working under
> the assumption that it
> should be very stable and problem free, but who knows.
> 
> 
> ------------------------------------------------------------------------------
> 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

-- 
http://www.fastmail.fm - A fast, anti-spam email service.

Re: [Algorithms] Kinematic Collision

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

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

> About the the inner hull sweeptest, this is kinda inverted to my 
> bias, with my bias I did a sweep 
> using a larger hull and then when finding collision i calculate the 
> position to intersection and
> subtract the bias. To me they are both the same but I'll definitely 
> give it a try.

The trouble with the way you're doing it is that you are physically moving 
the capsule to a place where it wasn't the frame/iteration beforehand (it 
will move a little before the start of its travel, by your bias). Where 
as, if you use the inner hull, you do move the object back as well but you 
never end up before where you started because you always do the TOI test 
with the smaller inner hull.

It may seem like a subtle difference, but its very important for stability 
:)

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

wsBVAwUBSp5wH3ajGqjtoMHxAQhBfwf/XfvMuFoJVIVAgf+hhdpZhYIYEzt7axM6
mIe5/6fu47TeG5hsjIGNmcmhRb69U+C2+2eyg2dqOsF+dDJQSM92/rXDCWwRXJaQ
vSA1UhiogPziIaOWePd1eyg3e3Dyo1gZACJ5nH6jGurjc0sG5OA3K+lKczzJ+87h
UKJd2jywM9xgHdNXsMGy2LViEbglqSfeoSLAptAjYP9GLn1xUkr/20URyLRKftY0
KaJ9lTsgggbePKo2qcmtnFe+8inVqW4xsPptMN3Ap2Y4pLIi+GdtmkrHjv2QfMYJ
12vB1GoimhwgZOHLFeOfEBDYDqAOBxHwDLkBSY89OLg2LYtW/Yltdg==
=J9mp
-----END PGP SIGNATURE-----

Re: [Algorithms] Kinematic Collision

[Johan G. <spi...@gm...>]

Because NxCharacter is not integrated with Gamebryo Lightspeed.

Pierre Terdiman (GMail) wrote:
>> I'm actually using PhysX SDK for collision detection and working under the
>>     
> assumption that it
>   
>> should be very stable and problem free, but who knows.
>>     
>
> So... you're using the PhysX SDK already and you're trying to replicate
> NxCharacter which, as you noticed, "looks ALOT more advanced" than what you
> are doing.
>
> Why not simply using NxCharacter? Any problem with it?
>
> - Pierre
>
>
> ------------------------------------------------------------------------------
> 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

[Pierre T. \(GMail\) <pie...@gm...>]

> I'm actually using PhysX SDK for collision detection and working under the
assumption that it
> should be very stable and problem free, but who knows.

So... you're using the PhysX SDK already and you're trying to replicate
NxCharacter which, as you noticed, "looks ALOT more advanced" than what you
are doing.

Why not simply using NxCharacter? Any problem with it?

- Pierre

Re: [Algorithms] Kinematic Collision

[Johan G. <spi...@gm...>]

Thanks for the feedback, very helpful.

About the the inner hull sweeptest, this is kinda inverted to my bias, with my bias I did a sweep 
using a larger hull and then when finding collision i calculate the position to intersection and
subtract the bias. To me they are both the same but I'll definitely give it a try.

Using rigid bodies seems to me much more problematic and having to control the character using impulse/forces
is the main reason I choose the first method.


James Robertsson Wrote:
/"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.)"
/
I'm actually using PhysX SDK for collision detection and working under the assumption that it
should be very stable and problem free, but who knows.

Re: [Algorithms] Kinematic Collision

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

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

Hi Johan,

>     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

This biasing is part of your problem, instead of biasing you need to do 
something similar yet different:

When doing your swept shape-cast, you need an inner-hull shape of slighter 
smaller radius than the outer hull. Then, when you get a TOI intersection 
(which would obviously embed your outer hull in the ground, and the inner 
hull just touching), you can 'move back' the whole shape so that the outer 
hull is just touching. This means that next frame you won't find yourself 
initially embedded in the ground.

Ideally, you wouldn't need to move the shape back and you'd have some kind 
of method for finding the TOI which puts your shape some known distance 
from the ground (i.e. the distance from the outer hull to the inner), but 
this routine is more expensive than a straight intersection test.


>     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

Here, ideally, you'd give your character a velocity vector and then you 
can project his velocity into the plane of the normal of the contact point 
(and subtract friction in the tangential velocity direction, as you 
mentioned). As others have said you could make it a rigid body, but i 
don't think you need to go that far for just a character capsule.

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

wsBVAwUBSp4rN3ajGqjtoMHxAQiUHgf+OXbrlifgpUTqi57rWlkY7EZFuN25BQv6
WznoeV8qB/araugRn1rXSJH5nU0VDR+MtbyxvBPWks9Ekx9RUcLJmaM++pYEeh4E
MbaVsyITsbS97kMhQURjZwC2MdOaMAFSi93PEqrccZ1kH2IdhRFxTA8Dmke+DawN
BTcgS85LUCmHom15W9pI6bpSrzEEZARZ9THaOgqJfNFP2ha9Eraac2bt4E9y/xpm
0NPOT8rMdsGCaRVicMK7Pc4KnaxwFih0byDL5K9n2VVXrjCp2WGKEuDQ9xuHe91H
OAE9i+Ikc+uoO7k87AfUIZzKcyzemNYhqwU6/g5vrQeE/VthSTbluw==
=MATM
-----END PGP SIGNATURE-----

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
>
>   

Re: [Algorithms] Kinematic Collision

[Juan L. <re...@gm...>]

What you are describing is usually the standard way of handling a character
through a level, or at least what it used to be standard up to a few years
ago. I'm not sure if i'm solving your problem, but at least i'll try to
share some experience:

Nowadays, physics engines can handle this in 2 different ways

1) The way you propose, plus usually a "solver" check if your character
ended up embedded (may always happen.. ) so it ends up unembedded. This
results in very "correct" character motion, but with poor interaction with
other dynamic objects.
2) Under a physics engine, you can treat your character as a rigid body with
infinite inertial tensor (0 inverted) so it can't rotate (stays straight all
the time, and just solve the contacts as you would solve any rigid body
(applying force and remving friction while it walks, etc). This works pretty
well except for a few side effects i'll commend below.

The second way has some extra problems to solve:

a) Characters or other objects can go through floors if moving too fast,
this can be solved by using CCD, raycasting from the support in the
direction it's moving, or use binary steps with the swept motion volume to
the point first intersecting.
b) Characters can slide slowly in ramps (not stay still).. there are many
small ways to fix this, the one i like the most is disabling gravity on our
character if you are not moving your character for a while and it stays n
floor, or you can just reenable friction when your character is still (you
are not trying to move it).
c) Characters may bounce when falling from too high or at high speed, this
can be fixed either hacking the solver,or using the raycast mentioned in (a)
to preapply an impulse that decreases the impact velocity. Also, i noticed
techniques such as split/accumulated impulses described by erin catto help
this scenario.


Cheers!

Re: [Algorithms] Curve fitting problem

[David B. <dbe...@na...>]

That sounds like a great idea.  It seems to me that the one tricky bit will be to break up the spline curve segments from the spline that goes through only some points into multiple segments to make the interpolation between curve segments work.

For curves that pass through all the points I would recommend the Catmul-Rom algorithm, a special case of the Cubic Hermite spline given earlier (and listed on that wikipedia page -- http://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull.E2.80.93Rom_spline)

David Bennett
NAMCO BANDAI Games America Inc.

________________________________
From: Juan Linietsky [mailto:re...@gm...]
Sent: Tuesday, September 01, 2009 2:32 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Curve fitting problem

My suggestion may feel hackish but i think it gets the closest to what you may need.

Just use a cubic spline between the points you want to pass by for sure, and ignore the others.
Use a second cubic spline that goes through ALL the points.

Interpolate both to the measure you want, and you should have a curve that passes by some points and gets close to the others.



On Tue, Sep 1, 2009 at 4:23 PM, Ivan Vorobeychyk <iv...@gm...<mailto:iv...@gm...>> wrote:
Hi, guys.

I have a problem that I think has been solved many times,
hope somebody can point me to appropriate technique.

I have an ordered set of points in 2-d space, that represents a curve
(like set of pixels, drawn with pencil in Paint).
I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
of these points (control points) and will pass CLOSE to other points
from the given set.

Any help much appreciated.
Thanks,
Ivan

------------------------------------------------------------------------------
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...<mailto:GDA...@li...>
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[Algorithms] Kinematic Collision

[Johan G. <spi...@gm...>]

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.

Re: [Algorithms] Curve fitting problem

[Juan L. <re...@gm...>]

My suggestion may feel hackish but i think it gets the closest to what you
may need.
Just use a cubic spline between the points you want to pass by for sure, and
ignore the others.
Use a second cubic spline that goes through ALL the points.

Interpolate both to the measure you want, and you should have a curve that
passes by some points and gets close to the others.



On Tue, Sep 1, 2009 at 4:23 PM, Ivan Vorobeychyk <iv...@gm...> wrote:

> Hi, guys.
>
> I have a problem that I think has been solved many times,
> hope somebody can point me to appropriate technique.
>
> I have an ordered set of points in 2-d space, that represents a curve
> (like set of pixels, drawn with pencil in Paint).
> I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
> of these points (control points) and will pass CLOSE to other points
> from the given set.
>
> Any help much appreciated.
> Thanks,
> Ivan
>
>
> ------------------------------------------------------------------------------
> 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] Curve fitting problem

[Jarkko L. <al...@gm...>]

Not exactly what you are looking for, but I have some code online which
iteratively fits a spline constructed of cubic curves to a set of n-d points
within given tolerance constraints (e.g. distance, velocity, etc.) It also
assumes that the input keys are evenly distributed on a timeline. This is
mainly meant for animation key frame compression (position & rotation), but
might be a useful reference for you. It's the fit_spline() function of the
following link:

http://spinxengine.svn.sourceforge.net/viewvc/spinxengine/src/core/math/para
metric.inl?view=markup

... and here is some unit test code for use cases (search for fit_spline):

http://spinxengine.svn.sourceforge.net/viewvc/spinxengine/src/unittest/core/
math/parametric.cpp?view=markup


Cheers, Jarkko


-----Original Message-----
From: Ivan Vorobeychyk [mailto:iv...@gm...] 
Sent: Tuesday, September 01, 2009 10:24 PM
To: GDA...@li...
Subject: [Algorithms] Curve fitting problem

Hi, guys.

I have a problem that I think has been solved many times,
hope somebody can point me to appropriate technique.

I have an ordered set of points in 2-d space, that represents a curve
(like set of pixels, drawn with pencil in Paint).
I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
of these points (control points) and will pass CLOSE to other points
from the given set.

Any help much appreciated.
Thanks,
Ivan

----------------------------------------------------------------------------
--
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] Curve fitting problem

[Fabian G. <f.g...@49...>]

> Hi, guys.
> 
> I have a problem that I think has been solved many times,
> hope somebody can point me to appropriate technique.
> 
> I have an ordered set of points in 2-d space, that represents a curve
> (like set of pixels, drawn with pencil in Paint).
> I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
> of these points (control points) and will pass CLOSE to other points
> from the given set.

It depends on what kind of spline you need, how it is parametrized, and 
what type of smoothness you need.

The parametrization (i.e. at what "time" the curve passes through or 
close to a given point) in particular makes a large difference; 
interestingly, the problem is a lot easier if you have very specific 
requirements on the parametrization, because that means you don't have 
to optimize for it. Determining optimal control points given a set of 
samples with explicit "timestamps" can be efficiently solved as a linear 
least squares system. But if the "timestamps" aren't fixed, the problem 
is nonlinear and quite difficult to solve.

For a relatively simple solution, just fit cubic splines. Assign the 
timestamps based on geometric distance between your sample points (not 
necessarily ideal, but probably not bad, either). Decide on which spline 
type you want to fit. For this type of problem, I'd try a cubic hermite 
curve first, with one segment per pair of "exact" control points. For 
smoothness, require that the derivatives between adjacent spline 
segments match; that gives you C^1 continuity (you can't do better in 
the general case with cubic curves as long as you require the curve to 
interpolate certain points).

Your constraints fix the start and end points of each segment and 
requires derivatives to match; that leaves one derivative per spline 
segment (plus one extra at the end) as unknowns. Given target 
"timestamps" for each of the sample points you want the curve to pass 
closely, you can solve for them using linear least squares, as mentioned 
above.

That's one way to do it. If you need something different, state your 
problem more precisely :)

Kind regards,
-Fabian Giesen

Re: [Algorithms] Curve fitting problem

[Danny K. <dr...@we...>]

> I have a problem that I think has been solved many times,
> hope somebody can point me to appropriate technique.
> 
> I have an ordered set of points in 2-d space, that represents a curve
> (like set of pixels, drawn with pencil in Paint).
> I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
> of these points (control points) and will pass CLOSE to other points
> from the given set.

What do you mean by 'close' and by 'certain points'? Do you have a picture?

Danny

Re: [Algorithms] Curve fitting problem

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

Ivan Vorobeychyk wrote:
> Hi, guys.
>
> I have a problem that I think has been solved many times,
> hope somebody can point me to appropriate technique.
>
> I have an ordered set of points in 2-d space, that represents a curve
> (like set of pixels, drawn with pencil in Paint).
> I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
> of these points (control points) and will pass CLOSE to other points
> from the given set.
>   

A "default" cubic spline will fit through all of the points, smoothly 
(C0 and C1 AFAICR). You treat each sub-segment of 4 points as one 
segment to interpolate -- 0,1,2,3 generates data for the 1-2 segment; 
1,2,3,4 generates data for the 2-3 segment etc.

If that's not good enough, you can start with that spline, and then 
adjust the points that are adjustable in a direction that makes the 
spline "better" (whatever that means), while making sure they are still 
"close" (whatever that means).

If you can come up with an algorithmic definition of "better" and 
"close," then you can just throw a regular LP optimization solver at the 
problem. Because the system is semi-local (a change affects neithbors at 
most two segments away) it might also be amenable to greedy optimization 
and/or recursive subdivision optimization.

Sincerely,

jw



-- 

  Revenge is the most pointless and damaging of human desires.

[Algorithms] Curve fitting problem

[Ivan V. <iv...@gm...>]

Hi, guys.

I have a problem that I think has been solved many times,
hope somebody can point me to appropriate technique.

I have an ordered set of points in 2-d space, that represents a curve
(like set of pixels, drawn with pencil in Paint).
I need to build SMOOTH spline that will pass EXACTLY through CERTAIN
of these points (control points) and will pass CLOSE to other points
from the given set.

Any help much appreciated.
Thanks,
Ivan

Re: [Algorithms] A computational geometry problem

[Danny K. <dr...@we...>]

>> Problem: Given n lines, determine a point minimizing the summation of the
>> distances from the point to the n lines.
>>
>
> This is a Least Absolute Deviations problem, which are normally solved by
> simplex methods; see the Wikipedia page for more details. If an O(n^3)
> running time is acceptable to you, however, a minimal solution will always
> be found at the intersection of two of the lines, so you can just check 
> all
> the intersection points if you like.

What if the lines are parallel? For two parallel lines, any point between or 
on the lines will solve it, for three it'll be a point on the middle line, 
etc.

Sounds like an odd thing to want, really - there's presumably often lots of 
these points. Under what circumstances might one look for this rather than, 
say, a least squared distance?

<relurk>
Danny 

Re: [Algorithms] A computational geometry problem

[Ben Sunshine-H. <sn...@gm...>]

On Sat, Aug 22, 2009 at 8:17 AM, J.-R. Jiang <jr...@cs...>wrote:

> Problem: Given n lines, determine a point minimizing the summation of the
> distances from the point to the n lines.
>

This is a Least Absolute Deviations problem, which are normally solved by
simplex methods; see the Wikipedia page for more details. If an O(n^3)
running time is acceptable to you, however, a minimal solution will always
be found at the intersection of two of the lines, so you can just check all
the intersection points if you like.

Ben

[Algorithms] A computational geometry problem

[J.-R. J. <jr...@cs...>]

Dear Colleagues,

I am solving the following problem by a computer program. Has anybody known
of any algorithm that can solve the problem?

Problem: Given n lines, determine a point minimizing the summation of the
distances from the point to the n lines.

Regards,
Jehn-Ruey Jiang
Department of Computer Science and Information Engineering
National Central University
Jhongli City, Taoyuan, 320, Taiwan

[Algorithms] [CFP][P2PNVE 2009][Submission is open until August 30, 2009]The 3rd International Workshop on Peer-to-Peer Networked Virtual Environments

[J.-R. J. <jr...@cs...>]

Dear Colleagues,

 

The paper submission deadline (August 20, 2009) of the 3rd International Workshop on Peer-to-Peer Networked Virtual Environments (P2PNVE'09) has been passed. Now we are proceeding with the review process. However, the paper submission system will remain open until August 30, due to the request of some authors. You are invited to register and submit your papers via  <http://acnlab.csie.ncu.edu.tw/P2PNVE2009/submission> http://acnlab.csie.ncu.edu.tw/P2PNVE2009/submission. P2PNVE’09 will be held in conjunction with The 15th International Conference on Parallel and Distributed Systems (ICPADS’09) on December 8 -11, 2009. Attached is the CFP, where you can find useful information about the paper submission. Please note that the topics of interest include not only specific topics related to peer-to-peer networked virtual environments but also general topics of peer-to-peer networking.

 

We are looking forward to receiving your papers.

 

Best regards,

Jehn-Ruey Jiang

General Chair

P2PNVE 2009

 

================ CALL FOR PAPERS =================

P2PNVE 2009
The 3rd International Workshop on Peer-to-Peer Networked Virtual Environments
in conjunction with
The 15th International Conference on Parallel and Distributed Systems (ICPADS 2009) 
December 8 -11, 2009
Shenzhen, China 
 <http://acnlab.csie.ncu.edu.tw/P2PNVE2009> http://acnlab.csie.ncu.edu.tw/P2PNVE2009

 

=================================================
About P2PNVE 2009
The rapid growth and popularity of networked virtual environments(NVEs) such as Massively Multiplayer Online Games (MMOGs) in recent years have spawned a series of research interests in constructing large-scale virtual environments. For increasing scalability and decreasing the cost of management and deployment, more and more studies propose using peer-to-peer (P2P) architectures to construct large-scale NVEs for games, multimedia virtual worlds and other applications. The goal of such research is to support an Earth-scale virtual environment or to make hosting virtual worlds more affordable than existing client-server approaches. However, existing solutions for consistency control, persistent data storage, multimedia data dissemination, cheat-prevention, topology mismatching, and virtual world interoperability are not straightforwardly adapted to such new environments. Novel ideas and designs thus are needed to realize the potential of P2P-based NVEs.
 
The 1st and the 2nd International Workshop on Peer-to-Peer Networked Virtual Environments were in conjunction with the 13th and 14th International Conference on Parallel and Distributed Systems in 2007 and 2008, respectively. To adhere to the theme of P2PNVE workshops, the theme of P2PNVE 2009 is to solicit original and previously unpublished new ideas on general P2P schemes and on the design and realization of P2P-based NVEs. The workshop aims to facilitate discussions and idea exchanges by both academics and practitioners.
 
Topics of interest include, but are not limited to:
 
-P2P systems and infrastructures 
-Applications of P2P systems 
-Performance evaluation of P2P systems 
-Trust and security issues in P2P systems 
-Network support for P2P systems 
-Fault tolerance in P2P systems 
-Efficient P2P resource lookup and sharing 
-Distributed Hash Tables (DHTs) and related issues 
-Solutions to topology mismatching for P2P overlays 
-P2P overlays for NVEs 
-P2P NVE multicast 
-P2P NVE interoperability 
-P2P NVE content distribution 
-P2P NVE 3D streaming 
-P2P NVE voice communications 
-P2P NVE architecture designs 
-P2P NVE prototypes 
-P2P NVE consistency control 
-Persistent storage for P2P NVEs 
-Security and cheat-prevention mechanisms for P2P games 
-P2P control for mobile NVEs 
-P2P NVE applications on mobile devices 
 
Important Dates
Submission:                August 20, 2009
Notification:               September 20, 2009
Camera ready:           October 1, 2009
 
Paper Submission
Authors are invited to submit an electronic version of original, unpublished manuscripts, not to exceed 8 double-columned, single-spaced pages, to web site  <http://acnlab.csie.ncu.edu.tw/P2PNVE2009/submission> http://acnlab.csie.ncu.edu.tw/P2PNVE2009/submission. Submitted papers should be in be in PDF format in accordance with IEEE Computer Society guidelines (Word or Latex). All submitted papers will be refereed by reviewers in terms of originality, contribution, correctness, and presentation.

 

Organizing Committees

 

Steering Chair: 

Shing-Tsaan Huang, National Central University, Taiwan  

 

General Chair: 

Jehn-Ruey Jiang, National Central University, Taiwan

 

International Program Committee Members 

(Listed in alphabet order):

Maha Abdallah, University of Paris VI, France

Sonja Buchegger, University of California, Berkeley, USA

Bing-Yu Chen, National Taiwan University, Taiwan

Jui-Fa Chen, TamKang University, Taiwan

Li-Der Chou, National Central University, Taiwan

Zoran Despotovic, NTT DoCoMo Euro-Labs, Germany

Gwendal SIMON, GET / ENST-Bretagne, France

David Hales, University of Bologna, Italy

Aaron Harwood, University of Melbourne, Australia

Pilar Herrero, Madrid University of Technology, Spain

Jiung-yao Huang, National Taipei University, Taiwan

Minoru Ito, Institute of Science and Technology, Japan

Sam Joseph, University of Hawaii, Manoa, USA

Yoshihiro Kawahara, University of Tokyo, Japan

Chung-Ta King, National Tsing Hua University, Taiwan

Nicolas Liebau, Technical University Darmstadt, Germany

Chuan-Ming Liu, National Taipei University of Technology, Taiwan

Gianluca Moro, University of Bologna, Italy

Wei Tsang Ooi, National Singapore University, Singapore

Juan Orduna, University of Valencia, Spain

Kai-Uwe Sattler, Tech. University of Ilmenau, Germany

Gregor Schiele, Mannheim University, Germany

Peter Sturm, Trier University, Germany

Sandeep Singhal, Microsoft Corporation, USA

Wernhuar Tarng, Nat’l Hsinchu University of Education, Taiwan

Pedro Morillo Tena, University of Valencia, Spain

Orazio Tomarchio, University of Catania, Italy

Li-Ming Tseng, National Central University, Taiwan

Shinichi Ueshima, Kansai University, Japan

Spyros Voulgaris, ETH Zurich, Switzerland

Wei-Jen Wang, National Central University, Taiwan

Michael Welzl, University of Innsbruck, Austria

Wai Gen Yee, Illinois Institute of Technology, USA

Suiping Zhou, NanYang Tech. University, Singapore