Last night I dreamt in beziers
by Matt Fairfax · 01/29/2004 (7:08 am) · 9 comments
Ok, so it is the end of January and my Quake 3 interiors are *still* not done =\
I was originally colliding against the actual leaf faces (what you see) and this worked great for the player collisions but was hideously slow for the vehicle collisions even after an enourmous amount of optimization. One thing I ran into was that the vehicle collisions would often consider themselves to be "inside" a solid brush in certain situations (bad things would ensue).
So, I decided to actually make use of the collision brush info that is stored in the bsp. The only problem was that Quake 3 collisions occur against the planes in the brushes (this is why the .map is the way it is) while Torque collisions occur against individual polys so I needed to generate vertices and faces for each of the brushes. I grabbed some code from map2dif and, after a bit of hacking, I got this working beautifully:
I then ran into a problem that had me baffled for almost 2 weeks. I would fall through some brushes if I approached them from certain angle. I wrote a lot of debug rendering functions to look at what was going on. I played with expanding the bounding boxes. I tried adding *every* brush every tick. Nothing seemed to work...until I started to step through a certain part of my code that I had always assumed was correct. It turned out that when I had wrapped the check against the current working list up in a for loop, I had forgotten to change a "return" into a "continue". The return made sense when I was only performing the check once but when I was trying to perform it multiple times if the first brush happened to already be on the working list it would return out of the function, skipping all of the rest of the brushes in the leaf. In some cases there was only the one brush in the leaf and in some cases the first brush was the correct one to collide against and sometimes the brush wasn't on the working list and it would never hit the return. Very subtle behavior.
I really hate that I lost 2 weeks to a simple mistake though but that is programming for you and next time I will be far more careful about it.
Ok, so where am I now? Players and vehicles collide wonderfully against the collision brushes (though it can still bog on vehicle collisions if the brushes are small and tightly packed):
Players also collide beautifully against the bezier patches. My last issue lies in that I can't get the vehicles to collide against the bezier patches at a reasonable speed. Part of the problem is that beziers are rarely convex (they tend to be concave) and the vehicle collisions are fairly dependent on them being convex (the Player collisions aren't). The Player collisions use an ExtrudedPolylist to generate a CollisionList (some nice code inside ExtrudedPolylist) while the Vehicles use the gjk algos. I attempted to swap out the gjk algos for an ExtrudedPolylist call in the vehicle code and it seems to run faster but it barfed somewhere in the forces calcs afterward (still trying to pinpoint it) virtually freezing up TGE. So, while I am still interested in pursuing that course a bit further, I am left with optimizing the bezier collisions until they are reasonably fast.
I am going to try to move the bezier collision check into the bsp tree walk where the brush check is already occurring so that it will happen a bit less (right now I loop through all of the beziers each time checking against their bounds). I am going to play with turning down the resolution on the collision patches (they are currently at one less than the resolution of the visible patches). I also want to make sure that I am not adding the bezier "convexes" more than once to the working list. I might even try to degenerate the collision patches into a set of actual convexes to see if that would help.
Another option I want to look at is adding a special case in the vehicle collision code for collisions against bezier patches but I am not completely certain where I'd want to do that.
Hopefully I will have something done soon =)
I was originally colliding against the actual leaf faces (what you see) and this worked great for the player collisions but was hideously slow for the vehicle collisions even after an enourmous amount of optimization. One thing I ran into was that the vehicle collisions would often consider themselves to be "inside" a solid brush in certain situations (bad things would ensue).
So, I decided to actually make use of the collision brush info that is stored in the bsp. The only problem was that Quake 3 collisions occur against the planes in the brushes (this is why the .map is the way it is) while Torque collisions occur against individual polys so I needed to generate vertices and faces for each of the brushes. I grabbed some code from map2dif and, after a bit of hacking, I got this working beautifully:
I then ran into a problem that had me baffled for almost 2 weeks. I would fall through some brushes if I approached them from certain angle. I wrote a lot of debug rendering functions to look at what was going on. I played with expanding the bounding boxes. I tried adding *every* brush every tick. Nothing seemed to work...until I started to step through a certain part of my code that I had always assumed was correct. It turned out that when I had wrapped the check against the current working list up in a for loop, I had forgotten to change a "return" into a "continue". The return made sense when I was only performing the check once but when I was trying to perform it multiple times if the first brush happened to already be on the working list it would return out of the function, skipping all of the rest of the brushes in the leaf. In some cases there was only the one brush in the leaf and in some cases the first brush was the correct one to collide against and sometimes the brush wasn't on the working list and it would never hit the return. Very subtle behavior.
I really hate that I lost 2 weeks to a simple mistake though but that is programming for you and next time I will be far more careful about it.
Ok, so where am I now? Players and vehicles collide wonderfully against the collision brushes (though it can still bog on vehicle collisions if the brushes are small and tightly packed):
Players also collide beautifully against the bezier patches. My last issue lies in that I can't get the vehicles to collide against the bezier patches at a reasonable speed. Part of the problem is that beziers are rarely convex (they tend to be concave) and the vehicle collisions are fairly dependent on them being convex (the Player collisions aren't). The Player collisions use an ExtrudedPolylist to generate a CollisionList (some nice code inside ExtrudedPolylist) while the Vehicles use the gjk algos. I attempted to swap out the gjk algos for an ExtrudedPolylist call in the vehicle code and it seems to run faster but it barfed somewhere in the forces calcs afterward (still trying to pinpoint it) virtually freezing up TGE. So, while I am still interested in pursuing that course a bit further, I am left with optimizing the bezier collisions until they are reasonably fast.
I am going to try to move the bezier collision check into the bsp tree walk where the brush check is already occurring so that it will happen a bit less (right now I loop through all of the beziers each time checking against their bounds). I am going to play with turning down the resolution on the collision patches (they are currently at one less than the resolution of the visible patches). I also want to make sure that I am not adding the bezier "convexes" more than once to the working list. I might even try to degenerate the collision patches into a set of actual convexes to see if that would help.
Another option I want to look at is adding a special case in the vehicle collision code for collisions against bezier patches but I am not completely certain where I'd want to do that.
Hopefully I will have something done soon =)
About the author
I am a Game Designer at PopCap who has worked on PvZ Adventures, PvZ2, Peggle Blast, and Bejeweled Skies. I am an ex-GarageGames employee who helped ship TGE, TGEA, Torque 3D, and Constructor.
#2
I am trying to go for a much simpler collision mesh than the actual curve but even that is giving me issues. I think I may just extrude the polys a little "downward" and make a really thin brush.
This might also be a good time for me to work on my polysoup->convexes code =)
01/29/2004 (8:27 am)
Actually, for the game I am working on, I need for pipes and rails to work =)I am trying to go for a much simpler collision mesh than the actual curve but even that is giving me issues. I think I may just extrude the polys a little "downward" and make a really thin brush.
This might also be a good time for me to work on my polysoup->convexes code =)
#3
This stuff is definitely coming along. You still idle on IRC much?
01/29/2004 (9:32 am)
Nice plan, Matt!This stuff is definitely coming along. You still idle on IRC much?
#4
01/29/2004 (10:40 am)
my brain hurts from just reading that :-)
#5
The culprit might be the iterative solver in the vehicle collision code (Vehicle::resolveCollision). It's based on Baraff's algorithm but places Coulomb friction inside the iteration step (inside Rigid::resolveCollision), which frequently causes a dramatic increase in the number of iterations required to derive a solution, sometimes overcalculates (or was that undercalculates? :/ ) restitution, and in the worst case produces float errors and astronomically incorrect values for force. The former two cause CPU chugging and non-intuitive physical behaviour, but the lattermost produces an astronomical value for linVelocity causing a gigantic bounding box to be calculated in Vehicle::updateWorkingCollisionSet, so that Convex::updateWorkingList tries to add a massive number of terrain polys to the working list (TerrainBlock::buildConvex). ALT-TAB back to your debugger when you get a freeze, DEBUG->BREAK-ALL, then you'll probably need to switch to the main thread, and you'll probably find the main thread at Convex::getType which was called from TerrainBlock::buildConvex.
At this point check the vehicle's values for torque and force, and the size of the bounding box being used to build the working set. You should see float errors (probably in torque) and ridiculous values for force and linVelocity, and a bounding box that's probably spanning multiple terrain blocks.
If that isn't what is happening, ignore the following :) . You can just fine tune the datablock parameters until the freezes go away (keeping bodyFriction low appears to work well, because it stops the Coulomb friction from destabilizing the iterative solver), but I actually broke the Coulomb friction calculation step out of the Rigid::resolveCollision, calculate it in a separate step in Vehicle::resolveCollision, and then let the Baraff iterative solver do its work (the friction must be done first, because otherwise it will invalidate the iterative solver's results!). I never could find a reference justifying placing the Coulomb friction inside Baraff's iterative solver (if anyone has a reference, I'd really appreciate it), and so far my techique eliminated the CPU chugging, overbounce, and engine freezes, and produces intuitive behaviour. Plus, I can use fairly high values for bodyFriction and not be limited to simulating everything as if it had the friction coefficient of Teflon on Teflon.
I still have problems with the vehicle sometimes missing collisions, but it usually happens at high speeds so I suspect the bounding box used to calculate the collision working set might be undersized, but I have no justification for that other than 'educated guess'. That problem is lower on my list (much lower than fixing the engine freeze, anyway).
If you think this is your problem and you'd like, I'll send you a patch or sample code.
But there are other conditions that cause force or torque to destabilize (but they cause similar engine freezes).
01/29/2004 (7:04 pm)
Quote:
seems to run faster but it barfed somewhere in the forces calcs afterward (still trying to pinpoint it) virtually freezing up TGE
The culprit might be the iterative solver in the vehicle collision code (Vehicle::resolveCollision). It's based on Baraff's algorithm but places Coulomb friction inside the iteration step (inside Rigid::resolveCollision), which frequently causes a dramatic increase in the number of iterations required to derive a solution, sometimes overcalculates (or was that undercalculates? :/ ) restitution, and in the worst case produces float errors and astronomically incorrect values for force. The former two cause CPU chugging and non-intuitive physical behaviour, but the lattermost produces an astronomical value for linVelocity causing a gigantic bounding box to be calculated in Vehicle::updateWorkingCollisionSet, so that Convex::updateWorkingList tries to add a massive number of terrain polys to the working list (TerrainBlock::buildConvex). ALT-TAB back to your debugger when you get a freeze, DEBUG->BREAK-ALL, then you'll probably need to switch to the main thread, and you'll probably find the main thread at Convex::getType which was called from TerrainBlock::buildConvex.
At this point check the vehicle's values for torque and force, and the size of the bounding box being used to build the working set. You should see float errors (probably in torque) and ridiculous values for force and linVelocity, and a bounding box that's probably spanning multiple terrain blocks.
If that isn't what is happening, ignore the following :) . You can just fine tune the datablock parameters until the freezes go away (keeping bodyFriction low appears to work well, because it stops the Coulomb friction from destabilizing the iterative solver), but I actually broke the Coulomb friction calculation step out of the Rigid::resolveCollision, calculate it in a separate step in Vehicle::resolveCollision, and then let the Baraff iterative solver do its work (the friction must be done first, because otherwise it will invalidate the iterative solver's results!). I never could find a reference justifying placing the Coulomb friction inside Baraff's iterative solver (if anyone has a reference, I'd really appreciate it), and so far my techique eliminated the CPU chugging, overbounce, and engine freezes, and produces intuitive behaviour. Plus, I can use fairly high values for bodyFriction and not be limited to simulating everything as if it had the friction coefficient of Teflon on Teflon.
I still have problems with the vehicle sometimes missing collisions, but it usually happens at high speeds so I suspect the bounding box used to calculate the collision working set might be undersized, but I have no justification for that other than 'educated guess'. That problem is lower on my list (much lower than fixing the engine freeze, anyway).
If you think this is your problem and you'd like, I'll send you a patch or sample code.
But there are other conditions that cause force or torque to destabilize (but they cause similar engine freezes).
#6
Ive seen the exact same thing in many physics situations, basically a build up of error which accumulates to the point where your objects go "off to neptune" as we usually put it.
Anyway, great work, and thanks for the info too Brad, perhaps make that a resource so that others can take a look? (not too useful for me, seeing that I'm not using much in the way of vehicle physics from torque :)
01/30/2004 (3:23 am)
i guess just having a bunch of asserts that check for boundary values in the different variables would be a great place to start tracking down when the things gets unstable.Ive seen the exact same thing in many physics situations, basically a build up of error which accumulates to the point where your objects go "off to neptune" as we usually put it.
Anyway, great work, and thanks for the info too Brad, perhaps make that a resource so that others can take a look? (not too useful for me, seeing that I'm not using much in the way of vehicle physics from torque :)
#7
Wow! My own tests had led me to believe that the issue was in resolveCollision() but I hadn't gotten any further into debugging it. This very well might be my issue and I would appreciate any help/code you wish to send me =) matt@rustycode.com
I am still having major issues even after applying most of the optimizations I had discussed above so it is time to tackle this in a different way. I need to generate some closed convex volumes to accurately represent the collision meshes for the beziers. I can see a few ways to "cheat" this with bezier patches but I think this is as good a time as any to tackle to polysoup->convexes issue (something I have been meaning to code for almost a year now). I have a few different ideas on how I want to do this but would appreciate any additional suggestions. I will post shots of my progress as it occurs.
01/30/2004 (5:04 am)
Brad,Wow! My own tests had led me to believe that the issue was in resolveCollision() but I hadn't gotten any further into debugging it. This very well might be my issue and I would appreciate any help/code you wish to send me =) matt@rustycode.com
I am still having major issues even after applying most of the optimizations I had discussed above so it is time to tackle this in a different way. I need to generate some closed convex volumes to accurately represent the collision meshes for the beziers. I can see a few ways to "cheat" this with bezier patches but I think this is as good a time as any to tackle to polysoup->convexes issue (something I have been meaning to code for almost a year now). I have a few different ideas on how I want to do this but would appreciate any additional suggestions. I will post shots of my progress as it occurs.
#8
I really have no justification for moving the Coulomb friction into a separate step (I looked really hard for online resources relating Baraff's algorithm and friction), other than it stabilizes the Baraff iterative solver and produces intuitive results. I was going to visit Eberly's site today and see if he has anything applicable.
@Matthew: As long as you understand that any code I might send is experimental. What CVS version of code are you using?
There are other places where the physics code destabilizes -- for instance damping in FlyingVehicle if the mass value is low (but still reasonable), because it gets into a positive feedback loop on errors in the float calculations and can destabilize in a very small number of steps (higher mass counteracts the float errors).
In practise, the physics can often be kept stable by appropriate values in the datablock, but getting these values right is a bit of black magic.
01/30/2004 (8:32 am)
@Phil: I'm still working with the physics stuff, and I'd probably turn it into a resource or code patch when I'm real comfortable where it's at. I've heard that most physics engines can exhibit instability, and using single float precision doesn't help. Right now the best thing might be a code patch to add a check for linVelocity magnitude in Vehicle::updateWorkingCollisionSet and assert when it is obviously too large and will generate an oversized bounds box that will freeze the engine.I really have no justification for moving the Coulomb friction into a separate step (I looked really hard for online resources relating Baraff's algorithm and friction), other than it stabilizes the Baraff iterative solver and produces intuitive results. I was going to visit Eberly's site today and see if he has anything applicable.
@Matthew: As long as you understand that any code I might send is experimental. What CVS version of code are you using?
There are other places where the physics code destabilizes -- for instance damping in FlyingVehicle if the mass value is low (but still reasonable), because it gets into a positive feedback loop on errors in the float calculations and can destabilize in a very small number of steps (higher mass counteracts the float errors).
In practise, the physics can often be kept stable by appropriate values in the datablock, but getting these values right is a bit of black magic.
#9
hehe :)
01/30/2004 (1:45 pm)
Actually, for the game I am working on, I need for pipes and rails to work =)hehe :)
Torque 3D Owner Eric Forhan
Do you think that it's important to have collision brushes with bezier patches? Obviously, something would have to be there to stop a person from going through walls, but maybe it's not so important to have it exactly follow the curve? I wonder if even a straight collision brush form pointA to pointB would be ok, even if it stopped the player from actually touching the wall.
Seems like splitting hairs to get it exact. :-) I could be mistaken, though ;-)
-Eric F
EDIT: A pipe made of two bezier patches would be an example of the collision plane not working. Hmmm.... maybe just no collision at all?