# More on swept sphere trees

This topic is 4835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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]

##### Share on other sites
Quote:
 Original post by MotorherpHi. 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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by MotorherpI 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...

##### Share on other sites
Quote:
 Original post by oliiiso 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.

##### Share on other sites
Quote:
 Original post by Eelcohow 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]

##### Share on other sites
Quote:
Original post by Motorherp
Quote:
 Original post by Eelcohow 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??

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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by Eelcohowever 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.

Top down can certainly be done more easily, at least for an inefficient approach like I'm currently using. I just subdivide the space like for an AABB tree regardless of tri configurations (unless there's no tris contained by that node anyway). I eventually plan on improving this by using the objects medial axis to work from. For a good starting place on top down construction of tight fitting sphere trees check this out:

http://isg.cs.tcd.ie/spheretree/

As for which is more optimal I think depends on how deep you want your trees to be. If you intent to stop when you can only just contain the tris then I imagine bottom up like you suggest to be better.

##### Share on other sites

it seems a little geared toward aproximating volumes rather than encompassing things like tris, but i think there is plenty of usefull general information.

##### Share on other sites
Quote:
 Original post by Nathaniel HammenI 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.

yes youre right the only way to know for sure is to try.

however, i think chances are good its faster and easier to code.

for 2D, which im mainly interested in atm:

with only a linetree i would need to do:
-check one tree vs the other.
-do a linesegment - linesegment test (which is infact the same as 4 vert-line tests!)
-filter out the doubles

with a linetree aswell as a verttree this would be:
-check one verttree vs linetree
-do linesegment - point test
-check the other verttree vs the other linetree
-do linesegment - point test

ok, there is more tree traversing, but only half the amount of line-vert tests and no need to worry about removing doubles. maybe the first levels of the tree can be shared between the lines and tris so there actually much less than double traversal. it sure seems more elegant to me, but if its faster..?

##### Share on other sites
I have no clear idea if it's useful to separate the trees.

Notation :
SS swept sphere (not nazi policeman)
VSS = SS of vert(ex).
ESS = SS of edge
FSS = SS of face.

Consider the micro-example you gave. A vertex Va is in contact with a face Fb (meshes a and b) with ... 3 edges. Say the vertex is adjacent to 4 triangles, thus also adjacent to 4 edges. So, around this vertex, in one case you'll most probably deal with :
4 ESS(a) against 3 ESS(b) = 12 SS tests or a bit less plus
1 VSS(a) x 1 FSS(b) and probably 1 FSS(a) x 3 VSS(b).

In the other case, you will certainly deal with
4 FSS(a) against 1 FSS(b) = 4 SS tests

Thus more work for the swept-sphere side of the algo.

One advantage though is that next the geometric tests are faster. Vert x Face does not have to deal with Vert x Edge(Face), because this is done elsewhere. You only have to care if the normal projection of vert is on the face, well otherly stated if it's inside the Voronoi cell of the face. 4 dot or cross products and done. You don't have to care of collisions of the vertex outside this cell. As a consequence, a pair of edges is processed only once whereas with FSS only, this could be done up to 4 times. 4 times redundancy.

But now here is my intuitive conclusion :
- The overall bounding volumes used are more numerous and their union is bigger. Thus more computations of swept spheres, that is 2nd degree root finding (one can optimize a bit for swept spheres). That is quick but not free.

- The redundancy I exposed can most certainly be avoided by flagging the d-facets (vert, edge, face) of each mesh. This can be tricky to do, but there is surely a way. I mean if edge AB has been tested against edge GH, while processing ABC, it should not be tested against the same GH while processing ABD. the problem is you can not store a dynamic array of all the edges that have already been tested against AB. That's na*nb complexity in terms of memory. But with a limited array, with for instance up to four elements, that should remove most redundant checks.

##### Share on other sites
i think ive found an elegant solution to the problem.

only one tree, with a tri in the leaf.

however, each leaf also contains pointers to the verts and edges that belong to this triangle AND leaf, and to this leaf alone.

as might be obvious by now, then its simply a case of checking the one tree vs the other, the verts ONLY in this leaf vs the tri in the other and vice versa, and owned edges vs edges.

actually, storing pointers wouldnt be necisary. it would at most require six bits of additional storage per leaf, to specify which subgeometry of the triangle belongs to this leaf.

the only slight drawback i can see is that some leafs will have to contain more than one edge, so a leaf-leaf collision might result in 4 edge-edge checks, or in case no attention is given to speading out ownership of edges and verts over the leafs, 9 checks worst case. still a heck of a lot better than complete tri-tri, and no double collisions returned.

seems like a pretty good solution to me.

##### Share on other sites
I want to be sure I understood your solution.

- this is meant to avoid the redundant checks on edges and verts.

- each leaf <=> triangle 'owns' only some of what's normally its edges and vertices so that for the whole mesh, one vert or one edge belongs to one and only one triangle.

Then 6 bits thing is a far more elegant solution than my previous fixed size array solution. And you add only 1 byte per face which is pretty small. Sounds very good. Do you have some money for a patent ? ;)

The only minor problem is that this bitfield must be passed to the triangle/triangle col. det. primitive. Not a big deal. You can check the other thread about tri-tri. I think Voronoi can be exploited to make it more speedy than the brute separating axis technique used by Oii (already efficient though). In the case of the separating axis, it will be easy to add something like if(!bDisabled[iAxis]).

Globally, with a well optimized algo for the sphere-tree/sphere-tree part, the whole should give a very efficient technique for predictive collision detection of arbitrary meshes.

Here is an idea to cull much of the tree/tree recursion in case of time based col. det. At each step of the recursion, the predicted time intervals of potential contact should be processed chronologically. And also the biggest spheres should be visited in priority.

This way :
-----------------------------------------------------> time4)          X[--- removed ----------------------------]                  ([SS1.1/SS2.1])3)     [SS1.1/SS2.2]         ([---------------SS1.2/SS2]-----])2)   [---------SS1.1/SS2-------]1) [-------------------SS1/SS2--------------------]

(SS1.1 is one of the sons of SS1, etc ...)
X is a potential contact detected.

So the recursion should target to find two leaves has soon as possible (example SS1.1/SS2.2). The goal is to find an exact potential contact between triangles (that will actually happen if no other contact is found earlier). Next the time of this contact (tmax) will reduce the time interval of search. This will cull most time intervals later, very high in the recursion hierarchy.

Once tmax has been found it's probably not useful to compute at the triangle/triangle level during the recursion. Unless the leaf/leaf interval has an upper boundary lower than tmax. Then there is a chance to make tmax even lower, which will help culling even more.

##### Share on other sites
Quote:
 Original post by Charles BI want to be sure I understood your solution.- this is meant to avoid the redundant checks on edges and verts.

yes, and avoid having to cull multiple reports of the same collision, but its two sides of the same coin really.

Quote:
 - each leaf <=> triangle 'owns' only some of what's normally its edges and vertices so that for the whole mesh, one vert or one edge belongs to one and only one triangle.Then 6 bits thing is a far more elegant solution than my previous fixed size array solution. And you add only 1 byte per face which is pretty small. Sounds very good. Do you have some money for a patent ? ;)

no, but aside from solving this problem, its nice knowing to have tackled a problem which seemingly hasnt been done a hundered times before, seemingly simple as it seems afterwards.

Quote:
 The only minor problem is that this bitfield must be passed to the triangle/triangle col. det. primitive. Not a big deal. You can check the other thread about tri-tri. I think Voronoi can be exploited to make it more speedy than the brute separating axis technique used by Oii (already efficient though). In the case of the separating axis, it will be easy to add something like if(!bDisabled[iAxis]).

im not really familiar with the voronoi method yet, but it sounds promising. (used in GJK isnt it?) ill look at it in more depth.

Quote:
 Globally, with a well optimized algo for the sphere-tree/sphere-tree part, the whole should give a very efficient technique for predictive collision detection of arbitrary meshes.

i hope and think so. ive been working out the swept sphere with rotation in maple, and it looks very promising. for all cases with non-absurd rotation speeds the root (and its existance) can be found with one quadratic approx of the interval, but it also handles huge rotation speeds at the same accuracy, only it will take more quadratic solving.

Quote:
 Here is an idea to cull much of the tree/tree recursion in case of time based col. det. At each step of the recursion, the predicted time intervals of potential contact should be processed chronologically. And also the biggest spheres should be visited in priority.This way :-----------------------------------------------------> time4) X[--- removed ----------------------------] ([SS1.1/SS2.1])3) [SS1.1/SS2.2] ([---------------SS1.2/SS2]-----])2) [---------SS1.1/SS2-------]1) [-------------------SS1/SS2--------------------](SS1.1 is one of the sons of SS1, etc ...)X is a potential contact detected.So the recursion should target to find two leaves has soon as possible (example SS1.1/SS2.2). The goal is to find an exact potential contact between triangles (that will actually happen if no other contact is found earlier). Next the time of this contact (tmax) will reduce the time interval of search. This will cull most time intervals later, very high in the recursion hierarchy.Once tmax has been found it's probably not useful to compute at the triangle/triangle level during the recursion. Unless the leaf/leaf interval has an upper boundary lower than tmax. Then there is a chance to make tmax even lower, which will help culling even more.

hey thats a very good (find tmax as soon as possible from the most promising candidates) idea that hadnt occurred to me yet. when recursing the tree, pass tmax back to the parent as an upper limit. yeah this would indeed be pretty efficient.

still im kind of in the dark regarding how to combine stacking with exact collisions. but everything except stacking seems to be coming together now, maybe its time to put the non-stacking part of this to code..

##### Share on other sites
also:

caching a couple of closest features from the last frame and handling those first to get a good tmax beforehand will eliminate almost all quadratic solving except for the shallowest levels in the tree.

##### Share on other sites
Stacking and more generally simultaneaous and/or maintained contacts (constraints) would surely make the global algo even more complex. Applied brutaly, predictive CD (col. det.) risks to bug in cases where you'll find many successive contact events. You need some infos, like relative kinetic energy or relative tangential and normal speeds in order to disable or treat separately some collision tests. When the objects are stacked and still they should not be computed anymore until one object hits the stack.

But I'd like to see a demo of predictive CD with hundreds of fast moving and rotating arbitrary meshes.

If an impulse based engine could work in continous time that would already be great. It would show some power and precision compared to the standard methods : contact time recursions, or constant time steps.

Today multiple constraints are solved trough big matrices and linear programming. Else with hacks (pseudo springs and all the stuff). I think the same hacks would work with continuous time algos. Next maybe new ways will be found to handle constraints much more accurately than they are today, that is with a minimalization of the penetration distances.

I'd prefer something based more on geometry. Example : this vertex slides on this plane (until it quits the Voronoi cell). So temporarilly consider this vertex translates and the whole body rotates around it, instead of its mass center. But that would be quite another story.

At the primitive level (tri/tri, tri/sphere, etc...) I am pretty certain that time interval col. det. queries are not much more difficult to handle than instant queries.

So in the end I wish processing speed, like the algorithmic complexity, mostly depends on the relevant output that is to be processed by the physics. I mean the actual collision events, or more generally the number of state changes in the list of contacts (instant or continuous).

Maybe all I say here has already been studied. I am not so well informed of the research. But I am pretty sure it has not been done yet for the video games.

##### Share on other sites
Quote:
 Original post by Eelcoalso: caching a couple of closest features from the last frame and handling those first to get a good tmax beforehand will eliminate almost all quadratic solving except for the shallowest levels in the tree.

Right, but add closest elements closing down (sign of the normal velocity). If it's after the contact, that won't help much. And if no such case remains from the previous frame, then my advise may still hold true.

##### Share on other sites
yes, i know the problems that arise with stacking and accurate collisions detection. i was considering deliberatly lowering accuracy in cases where contact with low relative velocities is found, and use an impulse based method as descibed in this forum the past week.

if youd want to do it exactly, i indeed think youd have to integratein steps, and change the impulse every time a contact breaks or forms on the vert-tri level. but this would get very very complex with for example a round shape resting and rotating in a concave bowl, and be very complex to code aswell.

however, i think stacking is doable with a hackish yet good method like impulse based and the right simplifications.

i also wonder what research has been done in this field. all papers i find are always geared towards games/not-too-realistic simulation. interest in physically accurate simulation or avoiding degenerate cases usually isnt too high. they expect the programmer to taylor and tweak the algorithm to his specific needs, and trust him to put in some hacks like limiting rotation speed.

anyway, i think speed is going to be fine, if the right global algorithm is used. my very quick and unoptimized sweep&prune can handle a dense cloud of 1000 objects in 3ms. after this youre left with 500 potential contacts at most, which will rapidly fall with each level of the test.

##### Share on other sites

This topic is 4835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628711
• Total Posts
2984341

• 23
• 11
• 10
• 13
• 14