Idea for new collision mechanism.
by FruitBatInShades · in General Discussion · 06/16/2004 (5:28 am) · 32 replies
I am not good at maths so am talking from a theoretical perspective. I have been involved in a debate about BSP and DTS and the problems with line of sight, rendering and collision.
I have a theoretical idea and would like to discuss the possibilities with people that do understand the math.
DTS collision idea
What about having nodes that deal with collision? You could set up a series of nodes that are responsible purely for collision and then have them report to the engine when they make contact with other things. This would be less resource intensive than having multiple collision meshes.
A standard charcater would only need 6, Top, Bottom, Left, Front, Right, Back, Front. The nodes would automatically be part of the model, therefore no changes are required when speed is an issue. At present I believe that the collision mesh has to be updated in relation to the model.
Each node would have a region setting side ones would be 2 units, bottom would be 0 or 1 and the top one would cover the width,bredth of the character, say 6 units.
The engine would only need to check these 6 regions when notified that an objects position is in the threshold of the nodes:-
Node To Test: 100, 100, 17
Object to collision test: 110, 97, 18
The engine could then keep a tree (which I believe torque does) and whenever an object needs to test for collision it binary searches the tree for objects in it's collision region. Seriously quick lookup, then does the full maths on items in it's region. That would mean no collision maths would need to be done when nothing is in region.
Each object:
X: Location in gamespace
Y: Location in gamespace
Z: Location in gamespace
Width: Size
Breadth: Size
Orientation: rotation/orientation of predicted face (X,Y,Z,Viewable direction)
BSP collision
The problem with BSP is that you cannot have convex faces. Using the same theory as above this could be changed. Using a face node with the same region information mean collision check will only be performed when in the moving object threshold.
It would also mean that DTS objects could be used as buildings because collision is simple. A complicated house with lots of bending polys (a dome) would only require 6 nodes to cover it's region and the engine could then switch to poly detection if actual contact is made. When you are that close to an object it usually fills most of your field of vision anyway.
Pseudocode: If Node is in Building/object Region, switch to poly/face detection.
BSP Viewing
The BSP tree makes deciding what can seen quite easy. Using the node technique above would be a case of checking items in range for only two things.
1. Is the Orienation facing the camera?
2. Is the X,Y,Z orientation of objects further down the stack the same, if so don't draw them.
This would obviously needs some serious tweakage and thought and be FOV based, the key to this entire theory is to have a filterable tree structure that can be filtered quickly on a main triangle or poly that is projected over the tree, immediately filtering out out of view objects.
1. Project viewable area over tree and get object locations and orientations
2. Start at nearest node, find first visible face, check for what area of the viewable poly that has discounted.
So in 2 checks we have narrowed the field to check significantly.
The white areas are what need to be checked after the first two checks. You can immediatly discount what is too far away. Mathematical checks would only be triangular polys (1,1)(158,999)(237,123,99), so a filter on objects that have nodes in that region should should significantly lower required checks. In the example above we are check 3 triangular polys.
It would even be possible to pre-generate these poly's as they only adjust slightly with movement and predict what objects would be coming into view soon. So it would be a case of updating the poly's, not regenerating them every frame.
What do you think?
I have a theoretical idea and would like to discuss the possibilities with people that do understand the math.
DTS collision idea
What about having nodes that deal with collision? You could set up a series of nodes that are responsible purely for collision and then have them report to the engine when they make contact with other things. This would be less resource intensive than having multiple collision meshes.
A standard charcater would only need 6, Top, Bottom, Left, Front, Right, Back, Front. The nodes would automatically be part of the model, therefore no changes are required when speed is an issue. At present I believe that the collision mesh has to be updated in relation to the model.
Each node would have a region setting side ones would be 2 units, bottom would be 0 or 1 and the top one would cover the width,bredth of the character, say 6 units.
The engine would only need to check these 6 regions when notified that an objects position is in the threshold of the nodes:-
Node To Test: 100, 100, 17
Object to collision test: 110, 97, 18
The engine could then keep a tree (which I believe torque does) and whenever an object needs to test for collision it binary searches the tree for objects in it's collision region. Seriously quick lookup, then does the full maths on items in it's region. That would mean no collision maths would need to be done when nothing is in region.
Each object:
X: Location in gamespace
Y: Location in gamespace
Z: Location in gamespace
Width: Size
Breadth: Size
Orientation: rotation/orientation of predicted face (X,Y,Z,Viewable direction)
BSP collision
The problem with BSP is that you cannot have convex faces. Using the same theory as above this could be changed. Using a face node with the same region information mean collision check will only be performed when in the moving object threshold.
It would also mean that DTS objects could be used as buildings because collision is simple. A complicated house with lots of bending polys (a dome) would only require 6 nodes to cover it's region and the engine could then switch to poly detection if actual contact is made. When you are that close to an object it usually fills most of your field of vision anyway.
Pseudocode: If Node is in Building/object Region, switch to poly/face detection.
BSP Viewing
The BSP tree makes deciding what can seen quite easy. Using the node technique above would be a case of checking items in range for only two things.
1. Is the Orienation facing the camera?
2. Is the X,Y,Z orientation of objects further down the stack the same, if so don't draw them.
This would obviously needs some serious tweakage and thought and be FOV based, the key to this entire theory is to have a filterable tree structure that can be filtered quickly on a main triangle or poly that is projected over the tree, immediately filtering out out of view objects.
1. Project viewable area over tree and get object locations and orientations
2. Start at nearest node, find first visible face, check for what area of the viewable poly that has discounted.
So in 2 checks we have narrowed the field to check significantly.
The white areas are what need to be checked after the first two checks. You can immediatly discount what is too far away. Mathematical checks would only be triangular polys (1,1)(158,999)(237,123,99), so a filter on objects that have nodes in that region should should significantly lower required checks. In the example above we are check 3 triangular polys.It would even be possible to pre-generate these poly's as they only adjust slightly with movement and predict what objects would be coming into view soon. So it would be a case of updating the poly's, not regenerating them every frame.
What do you think?
#2
Collision only occurs when two objects' bounding boxes intersect. Moving objects query the scenegraph for a list of all the objects that have overlapping bounding boxes (the "Seriously quick lookup" you mention). They then handle the per-poly/bounding box/convex/whatever collisions however is best for them and the colliding object (at least in theory...in practice it boils down to a handful of different methods).
As far as BSP goes...only when a moving object is inside the bounding box of an interior does it start the BSP collision scheme. The basic idea is that you then walk the BSP tree to determine which node the player is in and then only test the brushes/faces in that node that the player's bounding box intersects with and that face the desired movement vector. Very fast, very efficient.
Torque doesn't pre-calculated potential visibility lists (what you are getting at with your BSP visibility stuff) like Quake or Unreal based engines. Instead it uses a hand-tuned zoning scheme. For older systems this *can* be a lot slower in some cases. However, it should be noted that the new Dooom 3 engine and the next Unreal engine will both be using the same visibility scheme as TGE b/c with the latest video cards it is more efficent to send larger batches of polys. This zoning visibility scheme also allows for dynamic visibility changes (a moving interior or a mirror turning on/off etc.) that a pre-calcualted pvs won't.
TGE's collision is definitely a weak point. I have recently been doing a lot of research into various collision methodogies and have had some interesting and successful tests (I implemented a very nice and *very* fast spherical collision scheme for a vehicle last week that dropped vehicle collision from 8% total execution time to just over 1% in my test case). I have also been talking with some collision experts who have pointed me in very interesting directions. This is an active area of interest for me not just b/c of tech but also b/c of application to my game. Unfortuntately, "fixing" TGE's collision isn't going to happen over night...but there is serious progress being made in this area. Look for some kinda code pack to be released later this year =)
Lee,
You really should check out my Collision Tutorial Object
06/16/2004 (6:56 am)
Umm...not to knock the wind out of your sails but TGE's collision already basically works like this except instead of "6, Top, Bottom, Left, Front, Right, Back, Front" nodes it uses the object's bounding box (same thing ;).Collision only occurs when two objects' bounding boxes intersect. Moving objects query the scenegraph for a list of all the objects that have overlapping bounding boxes (the "Seriously quick lookup" you mention). They then handle the per-poly/bounding box/convex/whatever collisions however is best for them and the colliding object (at least in theory...in practice it boils down to a handful of different methods).
As far as BSP goes...only when a moving object is inside the bounding box of an interior does it start the BSP collision scheme. The basic idea is that you then walk the BSP tree to determine which node the player is in and then only test the brushes/faces in that node that the player's bounding box intersects with and that face the desired movement vector. Very fast, very efficient.
Torque doesn't pre-calculated potential visibility lists (what you are getting at with your BSP visibility stuff) like Quake or Unreal based engines. Instead it uses a hand-tuned zoning scheme. For older systems this *can* be a lot slower in some cases. However, it should be noted that the new Dooom 3 engine and the next Unreal engine will both be using the same visibility scheme as TGE b/c with the latest video cards it is more efficent to send larger batches of polys. This zoning visibility scheme also allows for dynamic visibility changes (a moving interior or a mirror turning on/off etc.) that a pre-calcualted pvs won't.
TGE's collision is definitely a weak point. I have recently been doing a lot of research into various collision methodogies and have had some interesting and successful tests (I implemented a very nice and *very* fast spherical collision scheme for a vehicle last week that dropped vehicle collision from 8% total execution time to just over 1% in my test case). I have also been talking with some collision experts who have pointed me in very interesting directions. This is an active area of interest for me not just b/c of tech but also b/c of application to my game. Unfortuntately, "fixing" TGE's collision isn't going to happen over night...but there is serious progress being made in this area. Look for some kinda code pack to be released later this year =)
Lee,
You really should check out my Collision Tutorial Object
#3
By using nodes and progressive testing you would be able to save a lot of cycles and not be too concerned with faces, all maths would be based on a nearness to other nodes formula.
I will do a little theoretical demo to explain what i mean more clearly. I'm not having a go at torque, this was an off topic idea :o)
06/16/2004 (7:05 am)
The idea is that there would be no performance impact for viewability/collision based on the complexity of the objects. We could do away with the restrictions of BSP modelling. Simple flat models would render like lightening but you would have the option of using more complex poly objects and the only impact difference would be the rendering of the polys.By using nodes and progressive testing you would be able to save a lot of cycles and not be too concerned with faces, all maths would be based on a nearness to other nodes formula.
I will do a little theoretical demo to explain what i mean more clearly. I'm not having a go at torque, this was an off topic idea :o)
#4
Yes...that is how TGE's collision works...
If there are no moving objects...no collision calcs.
If the moving object doesn't intersect anything else's bounding box...no collision calcs.
If the moving object only wants to do bounding box vs bounding box collisions...very simply calcs like your "nearness to other nodes formula".
If the moving object wants to to bounding sphere vs bounding sphere...very fast calcs.
If the moving object wants to do oriented bounding box vs polys...slower (TGE player does this).
If the moving object wants to do polys vs polys....*much* slower (TGE vehicles).
Etc.
06/16/2004 (7:20 am)
Lee,Yes...that is how TGE's collision works...
If there are no moving objects...no collision calcs.
If the moving object doesn't intersect anything else's bounding box...no collision calcs.
If the moving object only wants to do bounding box vs bounding box collisions...very simply calcs like your "nearness to other nodes formula".
If the moving object wants to to bounding sphere vs bounding sphere...very fast calcs.
If the moving object wants to do oriented bounding box vs polys...slower (TGE player does this).
If the moving object wants to do polys vs polys....*much* slower (TGE vehicles).
Etc.
#5
He said "It's called an Alternator son...look into it."
06/16/2004 (7:27 am)
This feels like the day I ran to my Dad as a kid "Dad! Dad! I got this great idea! Hook up the battery in a car to a *generator* and recharget he battery as you drive!"He said "It's called an Alternator son...look into it."
#6
Before collision
Player Move
>Have I moved into a new zone?
>>Yes, get new zone nodes
>Check current external nodes, are any in my nodes?
>>No
On Collision
>Check current external nodes, are they in my nodes?
>>Yes, House West Wall 1 has a larger X co-ord than me and is in 2 units. I have reached it's area.
>>>Either, If FlatFace then callback collision occurred
>>>or, switch to poly-collision mode.
06/16/2004 (7:34 am)
Here is a simple demo. The character moves as normal, checking the tree for nearby collision nodes. I'd probably implement this as an 16 bit reference or zone so you can immediately jump to the relevant section.Before collision
Player Move
>Have I moved into a new zone?
>>Yes, get new zone nodes
>Check current external nodes, are any in my nodes?
>>No
On Collision
>Check current external nodes, are they in my nodes?
>>Yes, House West Wall 1 has a larger X co-ord than me and is in 2 units. I have reached it's area.
>>>Either, If FlatFace then callback collision occurred
>>>or, switch to poly-collision mode.
#7
What I'm suggesting is to use nodes instead of collision faces, even on a basic bounding box that has cut your maths from 8 nodes to 6.
Adding a new collision point(like a sword) is just a case of putting a new node on the tip of the sword, not creating a new bounding box. It would be more precise.
It would also enable collision detection on all surfaces, which BSP does not support.
Picture a garabage collector like in .net.
Cycle 1, check node visibilty and collisions, mark as active if they meet either criteria
Cycle 2, process cycle1's results and render.
Each cycle would be able to run in a seperate thread, and cycle one would get faster on each iteration as it would only be checking on the poly regions idea above, so removal from the stack will be what has left the poly, heavy processing only occurs on what has just entered the poly.
If the node hit's a single poly, no more maths needs to be done, no need to get a ConvexCollision object.
06/16/2004 (7:42 am)
If it already works like that, how come we have to use BSP for buildings?What I'm suggesting is to use nodes instead of collision faces, even on a basic bounding box that has cut your maths from 8 nodes to 6.
Adding a new collision point(like a sword) is just a case of putting a new node on the tip of the sword, not creating a new bounding box. It would be more precise.
It would also enable collision detection on all surfaces, which BSP does not support.
Picture a garabage collector like in .net.
Cycle 1, check node visibilty and collisions, mark as active if they meet either criteria
Cycle 2, process cycle1's results and render.
Each cycle would be able to run in a seperate thread, and cycle one would get faster on each iteration as it would only be checking on the poly regions idea above, so removal from the stack will be what has left the poly, heavy processing only occurs on what has just entered the poly.
If the node hit's a single poly, no more maths needs to be done, no need to get a ConvexCollision object.
#8
06/16/2004 (7:43 am)
@Paul:Quote:This feels like the day I ran to my Dad as a kid "Dad! Dad! I got this great idea! Hook up the battery in a car to a *generator* and recharget he battery as you drive!"ROFL, I was actually thinking of a very similar event in my life when I got to your post....
He said "It's called an Alternator son...look into it."
#9
The buildings don't solely use BSP. They use CSG to generate triange strips which are then rendered based on portalized visibility checks. BSP is used mostly for fast ray casts, rezoning, and in some cases geometry queries. If you look in Interior::buildPolyList, you'll see that the actual BSP tree code is buried several layers down.
And indeed, if you poke at some of the collision code, it does get convexes to check against, then garbage collect them in time (or at least, wants it to work that way).
I would suggest rereading and becoming more familiar with Torque's collision code before you go further with this discussion.
06/16/2004 (8:10 am)
Actually, multithreaded collision checks would be a bad idea if you were going to have any of the geometry you were checking against move...The buildings don't solely use BSP. They use CSG to generate triange strips which are then rendered based on portalized visibility checks. BSP is used mostly for fast ray casts, rezoning, and in some cases geometry queries. If you look in Interior::buildPolyList, you'll see that the actual BSP tree code is buried several layers down.
And indeed, if you poke at some of the collision code, it does get convexes to check against, then garbage collect them in time (or at least, wants it to work that way).
I would suggest rereading and becoming more familiar with Torque's collision code before you go further with this discussion.
#10
The key would be the iterative fashion of the tree, this is NOT implemented in torque or any other engine I know of. I am talking about a tree structure that is filtering in real time and if this could be made fast enough, it would lead to less CPU cycles as most of the time the tree is only changing slightly. Moving view would only shift view co-ordinates and require no calculations unless they fall out of or into the current viewing poly.
This would allow extra cycles for predictive rendering which would mean that objects about to be loaded into view could be pre-calculated. This should hopefully help with framerate in busy areas.
OK, I'll crawl under my rock and keep my childish ideas to myself. Sorry Jorgan and Paul, I'll come back when I've grown up a bit :P
06/16/2004 (8:23 am)
Just to re-state the point I am not talking about torque in particular and I don;t think people have read the above points in a clear fashion. There are lots of optimizations that could be done from the simple 8 points - 6 points for collision boxes. The key would be the iterative fashion of the tree, this is NOT implemented in torque or any other engine I know of. I am talking about a tree structure that is filtering in real time and if this could be made fast enough, it would lead to less CPU cycles as most of the time the tree is only changing slightly. Moving view would only shift view co-ordinates and require no calculations unless they fall out of or into the current viewing poly.
This would allow extra cycles for predictive rendering which would mean that objects about to be loaded into view could be pre-calculated. This should hopefully help with framerate in busy areas.
OK, I'll crawl under my rock and keep my childish ideas to myself. Sorry Jorgan and Paul, I'll come back when I've grown up a bit :P
#11
Is that it?
06/16/2004 (9:07 am)
So let me get this right. What youre proposing is having 6 collision "nodes" (please dont use that word, its far too generic), which you are checking for overlap of bounding objects, if 2 overlap, youre going to consider a collision?Is that it?
#12
No hard feelings pal, ok ?
06/16/2004 (9:22 am)
@Lee: Sorry if I sounded rude, really didn't mean that.No hard feelings pal, ok ?
#13
What about a mortal combat type situation. You could have collision points on both feet, hands, elbows, knees and know precisely where contact is occuring. Left knee contacted opponents right arm at 100,100,20. You could also easily track velocity and direction by taking two readings a few milliseconds apart.
The other option that stands out is manipulating those nodes at run-time. If the character is running, increase the collision nodes sensitivity/distance from 2 to 8 so you have more time to react in-engine. You could also increase the number depending on what is going on. In the mortal combat example, if Left knee is entering 30 units away from targets collision node, add 4 more for precison, then drop them after contact.
06/16/2004 (9:31 am)
Quote:So let me get this right. What youre proposing is having 6 collision "nodes" (please dont use that word, its far too generic), which you are checking for overlap of bounding objects, if 2 overlap, youre going to consider a collision?Not just 6, any amount that is required. That would enable you to have a sword collision point for example, just by adding a new collision point to the model. This would allow very precise collision detection but not use much resources. Say your character had a tail? 1 point in the middle, 1 at the end gives the tail full collision so it could naturally bounce.
What about a mortal combat type situation. You could have collision points on both feet, hands, elbows, knees and know precisely where contact is occuring. Left knee contacted opponents right arm at 100,100,20. You could also easily track velocity and direction by taking two readings a few milliseconds apart.
The other option that stands out is manipulating those nodes at run-time. If the character is running, increase the collision nodes sensitivity/distance from 2 to 8 so you have more time to react in-engine. You could also increase the number depending on what is going on. In the mortal combat example, if Left knee is entering 30 units away from targets collision node, add 4 more for precison, then drop them after contact.
#14
06/16/2004 (9:32 am)
Quote:No hard feelings pal, ok ?Sorry dude, been one of those days. No probs
#15
you simply cant represent a player model as a point or a bunch of points and have it work properly. We got away with a similar thing in W3D but that was by necessity (of having a truly destructible terrain that would just NOT allow collision boxes of any sort).
But its NOT optimal, its also kind rubbish, with issues like being able to fire a bullet which doesnt collide or overlap any of the nodes your testing, but still needs to collide with the player.
06/16/2004 (9:36 am)
The problem with that idea lee, is that a point isnt really enough, or even a bunch of points.you simply cant represent a player model as a point or a bunch of points and have it work properly. We got away with a similar thing in W3D but that was by necessity (of having a truly destructible terrain that would just NOT allow collision boxes of any sort).
But its NOT optimal, its also kind rubbish, with issues like being able to fire a bullet which doesnt collide or overlap any of the nodes your testing, but still needs to collide with the player.
#16
06/16/2004 (9:41 am)
I thought you were going to say that, look again at the original post:-Quote:X: Location in gamespaceThe node is the centre of a poly that is never rendered or instantiated, it's just the source of the base number for the maths.
Y: Location in gamespace
Z: Location in gamespace
Width: Size
Breadth: Size
Orientation: rotation/orientation of predicted face (X,Y,Z,Viewable direction)
Quote:Seriously quick lookup, then does the full maths on items in it's regionAlso it is meant to be generic so can be applied to buildings and animated objects. Tuning would be done depending on the use of the collision node. I didn't draw the collision points as rects cos I can't get translucent ones in milkshape at the mo :)
#17
We only need two collision points for the barell to cover it's entire area. When the projectile enters it's region we can either explode it straight away or use the velocity and direction to know exactly where it will hit and draw a bullet hole.
We would always be one step ahead of the action in this scenario.
So in this example we have gone from 8 points for a bounding box to 2 collision points. Again the actual region doesn't matter and we don't need to know where the corners are beacause no matter where we enter the barrells region, it still takes the same formula, whether we hit the corner at 45 degrees and only hit the first 'pixel' we still get a collision callback so no box is required.
Barrell Collision Point Plane X = Entered at 10,10,14, Add event to the stack
Barrell Collision Point Plane Y = Entered at 20,17,19, Add event to the stack
The only maths we are ever doing is a distance calculation from collision point to region. Another thing that occurs to me is that if the wind is blowing or the projectile is reacting to gravity, it's irrelevant. It will still use the same formula, all we need to do for more realism on contact, is see where the last two reading were for the projectile and get the velocity and direction if the projectile does not supply that info.
06/16/2004 (10:02 am)
Another example of the theory. The projectile has it's collision node set to a unit of 10 to account for the speed. It is about to enter 2 collision points regions which both belong to the barrel. By setting the projectiles collsion node far away from the projectile itself we have a long time to react.We only need two collision points for the barell to cover it's entire area. When the projectile enters it's region we can either explode it straight away or use the velocity and direction to know exactly where it will hit and draw a bullet hole.
We would always be one step ahead of the action in this scenario.
So in this example we have gone from 8 points for a bounding box to 2 collision points. Again the actual region doesn't matter and we don't need to know where the corners are beacause no matter where we enter the barrells region, it still takes the same formula, whether we hit the corner at 45 degrees and only hit the first 'pixel' we still get a collision callback so no box is required.Barrell Collision Point Plane X = Entered at 10,10,14, Add event to the stack
Barrell Collision Point Plane Y = Entered at 20,17,19, Add event to the stack
The only maths we are ever doing is a distance calculation from collision point to region. Another thing that occurs to me is that if the wind is blowing or the projectile is reacting to gravity, it's irrelevant. It will still use the same formula, all we need to do for more realism on contact, is see where the last two reading were for the projectile and get the velocity and direction if the projectile does not supply that info.
#18
06/16/2004 (10:15 am)
What happens if I shoot the left hand side of the barrel? If I'm viewing your diagram properly, nothing would happen?
#19
:( Does anyone good at 3d maths fancy meeting me on ICQ or MSN to chat this over and discuss it in a mathematical way :D
06/16/2004 (10:21 am)
Quote:What happens if I shoot the left hand side of the barrel? If I'm viewing your diagram properly, nothing would happen?Your right it would need 3 not 2. But your forgetting the projectiles collision node too. Never mind.
:( Does anyone good at 3d maths fancy meeting me on ICQ or MSN to chat this over and discuss it in a mathematical way :D
#20
06/16/2004 (10:23 am)
Lee it sounds like you are re-inventing collision meshes. If there is an original idea buried in here and I just cant see it because i have not read carefully through your stuff, then I apologize, but it sounds like you are not familiar enough with how collision schemes already tend to work, and that once you extend your "collision node" idea far enough to be usable in all cases then you will find your collision nodes are really just convex collision meshes. 
Torque Owner Stefan Lundmark