# More on swept sphere trees

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

## Recommended Posts

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.

• 10
• 12
• 13
• 9
• 12