Thread: [Algorithms] Kinematic Collision
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Johan G. <spi...@gm...> - 2009-09-01 22:34:12
|
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.
|
|
From: Juan L. <re...@gm...> - 2009-09-02 05:57:38
|
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! |
|
From: James R. <ja...@fu...> - 2009-09-02 07:36:27
|
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 > > |
|
From: Johan G. <spi...@gm...> - 2009-09-02 12:45:55
|
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. |
|
From: <Pau...@sc...> - 2009-09-02 13:16:32
|
-----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----- |
|
From: David B. <db...@fa...> - 2009-09-02 14:55:43
|
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. |
|
From: Jay S. <Ja...@va...> - 2009-09-03 17:26:46
|
> > 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 |
|
From: David B. <db...@fa...> - 2009-09-04 16:38:07
|
>>>> 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 |
|
From: Pierre T. <pie...@gm...> - 2009-09-04 17:39:00
|
> > 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!) |
|
From: <chr...@pl...> - 2009-09-04 18:07:03
|
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 |
|
From: Pierre T. <pie...@gm...> - 2009-09-05 00:46:32
|
> > 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 |
|
From: Jeff R. <je...@8m...> - 2009-09-06 03:16:14
|
> > 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 |
|
From: David W. <da...@pl...> - 2009-09-06 16:02:39
|
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 |
|
From: David B. <db...@fa...> - 2009-09-06 17:46:03
|
>>> 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 |
|
From: Jon W. <jw...@gm...> - 2009-09-07 17:21:43
|
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. |
|
From: Mark W. <Mwa...@to...> - 2009-09-08 00:39:17
|
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 > > |
|
From: Pierre T. <pie...@gm...> - 2009-09-08 09:56:16
|
>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 |
|
From: <chr...@pl...> - 2009-09-08 16:13:09
|
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 |
|
From: Alen L. <ale...@cr...> - 2009-09-08 06:31:25
|
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 |
|
From: Glenn F. <ga...@ga...> - 2009-09-06 19:13:34
|
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. > > |
|
From: Jon W. <jw...@gm...> - 2009-09-08 18:33:47
|
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. |
|
From: Alen L. <ale...@cr...> - 2009-09-08 22:05:01
|
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 |
|
From: <chr...@pl...> - 2009-09-09 00:56:56
|
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 |
|
From: James R. <ja...@fu...> - 2009-09-09 07:36:29
|
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 > > |
|
From: <chr...@pl...> - 2009-09-09 16:34:07
|
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 |
Thanks for helping keep SourceForge clean.
X