More on swept sphere trees
Author
When thinking a little more about this subject:
consider a tree with triangles in the nodes. imagine a cube for example, falling with a corner on a plane. in the worst case that would yield six triangle-triangle collisions, even though infact there is only one vertex-triangle collision.
now you could filter this out in a later stage, but then your time is already wasted. to combat this i came up with something else, but im not sure if its a good idea since ive never seen it done before. we need to check verts against faces, and edges against edges. well why not construct a seperate tree for them all? check the verttree of one object against the facetree of the other and vice versa, and crosscheck their edgetrees aswell. this greatly reduces the complexity of the collision check too.
one might argue that this triples memory requirements, but then again i argue collision geometry should be like an order of magnitude less detailled as graphical geometry anyway, and thus hardly significant.
am i reinventing the wheel again? or is the reason ive never seen this before because this is somehow a bad idea?
Hi. If your using swept spheres then when you reach the leaf node level its very unlikey that any of the contained tris will be colliding since the collision time returned will be when the leaf spheres first touch. Because of this its pointless to actually collide the tris together since 99% of the time it'll just return non-colliding (I'm talking static tri collision tests here of course. Since you'll already be in close proximity I don't think its worth trying a moving tri test - you can just assume they will collide very soon). Instead I move on to min seperation tests at this point and I'm not sure if you could leverage a sphere tree to help you with this.
If you plan to use swept sphere test on your 'tri-sphere trees' then I suppose it could work. Its an interesting idea and its never occured to me before. I think its usefulness will depend on the depth of your 'object-sphere tree' and the size of the tris though cause you could end up checking 'tri-sphere nodes' which are bigger than the 'object-leaf sphere nodes' if the tri is contained by several leaf nodes. I'm not sure if it would give you a speed boost either though. Sphere trees are used to speed collisions with complex objects whereas tris are very simple. It might just be quicker to bite the bullet and do the tri tests.
PS: just occured to me that to be useful the 'tri-sphere tree' root node would have to be smaller than the 'object-sphere trees' leaf node's child if you were to progress another level. If not you might as well just add another level to your objects tree rather than changing trees.
PPS: How do you construct a sphere tree around a vert??
[Edited by - Motorherp on September 18, 2004 7:13:27 AM]
If you plan to use swept sphere test on your 'tri-sphere trees' then I suppose it could work. Its an interesting idea and its never occured to me before. I think its usefulness will depend on the depth of your 'object-sphere tree' and the size of the tris though cause you could end up checking 'tri-sphere nodes' which are bigger than the 'object-leaf sphere nodes' if the tri is contained by several leaf nodes. I'm not sure if it would give you a speed boost either though. Sphere trees are used to speed collisions with complex objects whereas tris are very simple. It might just be quicker to bite the bullet and do the tri tests.
PS: just occured to me that to be useful the 'tri-sphere tree' root node would have to be smaller than the 'object-sphere trees' leaf node's child if you were to progress another level. If not you might as well just add another level to your objects tree rather than changing trees.
PPS: How do you construct a sphere tree around a vert??
[Edited by - Motorherp on September 18, 2004 7:13:27 AM]
Author
Quote:Original post by Motorherp
Hi. If your using swept spheres then when you reach the leaf node level its very unlikey that any of the contained tris will be colliding since the collision time returned will be when the leaf spheres first touch. Because of this its pointless to actually collide the tris together since 99% of the time it'll just return non-colliding (I'm talking static tri collision tests here of course. Since you'll already be in close proximity I don't think its worth trying a moving tri test - you can just assume they will collide very soon). Instead I move on to min seperation tests at this point and I'm not sure if you could leverage a sphere tree to help you with this.
yeah well that kinda depends on the maximum triangle size i think. for quite big triangles this might not be such a safe assumption to make, since their encompassing sphere would be quite big and thus extend quite a bit away from the tris surface.
Quote:
If you plan to use swept sphere test on your 'tri-sphere trees' then I suppose it could work. Its an interesting idea and its never occured to me before. I think its usefulness will depend on the depth of your 'object-sphere tree' and the size of the tris though cause you could end up checking 'tri-sphere nodes' which are bigger than the 'object-leaf sphere nodes' if the tri is contained by several leaf nodes.
im not sure what your saying....
however, a tri will never be contained by several leafnodes by definition the way i have things in mind, since the tree will be constructed bottom up, with each triangle centered in its own leafsphere.
I see. I'm currently using top down construction. The way I do it, the nodes can be smaller than the tris. In fact I make it so that the leaf nodes are of a radius which gives an acceptably small error for min seperation at collision.
so it's an adaptive sphere tree.
There is no real diference in generating 3 trees for mesh, to separate edges, triangle 'planes', and vertices. If you build a tree around edges, you'll have an awful lot of wasted space anyway (large sphere for little 'space' occupied by the edge), so you might as well put the edges in the same tree as the triangle plane. For the vertices, it's a litle bit more arguable, since the tree would be tighter than using the triangle tree.
But for the sake of memory and simplicity, I still think using a single tree for all the mesh features would be better. If you have a tri-sphere intersecting another tree-sphere, just do each vertex against the planes, and each edge against each edge. As you pointed out, you can also filter out an awful lot of these.
Otherwise, you'll have to do 3 tree trasversal anyway, and there is no real gain for edges.
There is no real diference in generating 3 trees for mesh, to separate edges, triangle 'planes', and vertices. If you build a tree around edges, you'll have an awful lot of wasted space anyway (large sphere for little 'space' occupied by the edge), so you might as well put the edges in the same tree as the triangle plane. For the vertices, it's a litle bit more arguable, since the tree would be tighter than using the triangle tree.
But for the sake of memory and simplicity, I still think using a single tree for all the mesh features would be better. If you have a tri-sphere intersecting another tree-sphere, just do each vertex against the planes, and each edge against each edge. As you pointed out, you can also filter out an awful lot of these.
Otherwise, you'll have to do 3 tree trasversal anyway, and there is no real gain for edges.
Author
Quote:Original post by Motorherp
I see. I'm currently using top down construction. The way I do it, the nodes can be smaller than the tris. In fact I make it so that the leaf nodes are of a radius which gives an acceptably small error for min seperation at collision.
yes, i also considered that.
however, i forsee some nasty problems that way. how do you determine contact points? well getting them is not the pproblem, rather restricting them. stacking objects is hard and over defined enough already as is. what if two simply cubes return dozens of contact points? thats not going to be pretty i think...
Author
Quote:Original post by oliii
so it's an adaptive sphere tree.
There is no real diference in generating 3 trees for mesh, to separate edges, triangle 'planes', and vertices. If you build a tree around edges, you'll have an awful lot of wasted space anyway (large sphere for little 'space' occupied by the edge), so you might as well put the edges in the same tree as the triangle plane. For the vertices, it's a litle bit more arguable, since the tree would be tighter than using the triangle tree.
But for the sake of memory and simplicity, I still think using a single tree for all the mesh features would be better. If you have a tri-sphere intersecting another tree-sphere, just do each vertex against the planes, and each edge against each edge. As you pointed out, you can also filter out an awful lot of these.
Otherwise, you'll have to do 3 tree trasversal anyway, and there is no real gain for edges.
well, the gain is not ending up with mutliple collisions between tris which actually could be represented by only one much simpler event, ie a collision between a vert and a tri. i think thats especially important when stacking things, as i explained above.
sure, and edge tree would contain a lot of empty space. but not any more so than an edgetree for the 2d case where youd need one anyway. my ultimate goal in using these sphere trees is not maximum efficiency, but rather making sure no collisions are missed regardless of circumstances, which requires sweeping, and sweeping is only practical for spheres as far as i know (or aabb's but rotation is a must).
besides, empty space in these trees might not be as bad as it seems at first. the actual volume being sweeped is the intersection of the current sphere AND all of its parents, since volume not colliding with the parent wont collide with any of its children either. thus if the tree is cleverly constructed, a lot of volume of a leafnode would fall outside one of the parents volumes, and thus the total bounding volume would be rather tight.
Quote:Original post by Eelco
how do you determine contact points? well getting them is not the pproblem, rather restricting them. stacking objects is hard and over defined enough already as is. what if two simply cubes return dozens of contact points? thats not going to be pretty i think...
The algo I've written constantly filters as it goes. Basically during the swept sphere tests, for each tree level combination a min collision time is maintained so that nodes can be discounted high up the tree. This keeps the number of intersecting leaf nodes down. Also before moving onto tris I wait till the complete list of intersecting leaf nodes is formed. Then from this a list of unique tri combinations which need checking is formed so that tri checks aren't repeated. Only then do I move onto collision point determination. By filtering at every level like this I only end up with 4 collision points for two parallel touching cube faces which is no worse than any other method. Currently the only filtering bit that needs improving is the node filtering cause for deep trees and perfectly aligned faces the leaf node list can grow substantially.
PS: I wouldn't use this method to stack cubes though or to represent any simple geometry with large flat faces. There's a fair bit of overhead involved with using this method which only pays off for complex geometry.
PPS: I'm interested to know how you go about your bottom up sphere tree construction. How do you know which spheres to merge into parent spheres etc??
[Edited by - Motorherp on September 18, 2004 9:56:30 AM]
Author
Quote:Original post by MotorherpQuote:Original post by Eelco
how do you determine contact points? well getting them is not the pproblem, rather restricting them. stacking objects is hard and over defined enough already as is. what if two simply cubes return dozens of contact points? thats not going to be pretty i think...
The algo I've written constantly filters as it goes. Basically during the swept sphere tests, for each tree level combination a min collision time is maintained so that nodes can be discounted high up the tree. This keeps the number of intersecting leaf nodes down. Also before moving onto tris I wait till the complete list of intersecting leaf nodes is formed. Then from this a list of unique tri combinations which need checking is formed so that tri checks aren't repeated. Only then do I move onto collision point determination. By filtering at every level like this I only end up with 4 collision points for two parallel touching cube faces which is no worse than any other method. Currently the only filtering bit that needs improving is the node filtering cause for deep trees and perfectly aligned faces the leaf node list can grow substantially.
PS: I wouldn't use this method to stack cubes though or to represent any simple geometry with large flat faces. There's a fair bit of overhead involved with using this method which only pays off for complex geometry.
ah yes filter out the doubles. not that bad an idea indeed if you deal with complex geometry, but for large plane areas i can indeed imagine this getting difficult.
Quote:
PPS: I'm interested to know how you go about your bottom up sphere tree construction. How do you know which spheres to merge into parent spheres etc??
i havnt really thought much about this part yet, but i was thinking about something along these lines:
simply group the closest pairs of spheres. iterate around a bit trough possible configurations to find a minimum. however i can see this being far from optimal for some cases. maybe topdown would actually be easier, since that problem has less degrees of freedom. maybe finding the two children farthest apart, start at both of these and add the others to parent that causes the least volume-growth. i dont know these are just quick ideas, i need to do some studying on this subject i guess.
I agree with oliii, that you should include edges in the plane shpere. But I've never seen anyone do what you're suggesting, so what I say is, the best way to find out is to try each possibility.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
