Oii, in the case of convex/convex Voronoi based algos are just an extension of the separation plane.
BTW, semantically I prefer saying plane than axis (normal of the said plane, because it adds the info where in affine space. It helps thinking in terms of infinite half spaces instead of 1D projections which is equivalent. Usually the plane is a support plane or at least attached to an edge of one of the convexes.
Next Voronoi is just a way to use connexity info to speed up the search of the 2 nearest d-facets (equivalently axis) in static case with no info cached from previous frame. It also greatly helps once a separating plane is invalidated.
For triangle triangle the raw power axis search requires to find a maximum (of minima) for :
- 9 edge/edge axes
- 2 face/vert axes
11 you are right. In each case you need 3*2 vertices be checked.
So 66 dot products. Am I right ?
The generalized Voronoi 3D algo takes 1-6 dot products to find the cell of (ABC) closest to D. Then connexity usually sorts E,F in a few iterations more (say 2-6). So it's probably 5 times faster 'algorithmically' in the triangle/triangle case.
More, this connexity info is particularilly useful when you want to deal with non translating movements, including fast rotations and parabolic movements of the mass center. Then it's easier to make a robust algo that will not miss any potential penetration that would happen during a short duration.
When you are in a Voronoi cell of d-facet Fa of A only 3 types of events happen to the nearest d-facet Fb of B and you treat whichever happens first :
a) Fb is beaten by one of its neighbours Fb', seek(Fa, Fb').
b) Fb goes out of cell(Fa), seek(Fa', Fb).
c) Fb hits Fa : all algo done, first contact found.
'Your' method deals very badly with cases a) and b). I know that in general c) happens first, specially if triangles are translating. But for a) and b), you need to compute the 66 dot products don't you ?
tri-tri min seperation
... although you have to be careful in degenerate cases. I prioritise the axes, so that in case I got a degenerate case, or if two axes return the same intersection depth/collision time, I use the most sensible.
goes like something like this...
goes like something like this...
bool Collide(CTri Tri1, CTri Tri2, Vector Velocity, float &fCollParam, Vector& vCollNormal){ // max of 12 axes to tests. // there are several types of test we can perform // depending on the triangle configuration. axes are //------------------------ // static case //------------------------ // Tri1.Normal // Tri2.Normal // Tri1.E0 x Tri2.E0 // Tri1.E0 x Tri2.E1 // Tri1.E0 x Tri2.E2 // Tri1.E1 x Tri2.E0 // Tri1.E1 x Tri2.E1 // Tri1.E1 x Tri2.E2 // Tri1.E2 x Tri2.E0 // Tri1.E2 x Tri2.E1 // Tri1.E2 x Tri2.E2 //------------------------ // dynamic case (most frequent) //------------------------ // Tri1.Normal // Tri2.Normal // Velocity // Tri1.E0 x Tri2.E0 // Tri1.E0 x Tri2.E1 // Tri1.E0 x Tri2.E2 // Tri1.E1 x Tri2.E0 // Tri1.E1 x Tri2.E1 // Tri1.E1 x Tri2.E2 // Tri1.E2 x Tri2.E0 // Tri1.E2 x Tri2.E1 // Tri1.E2 x Tri2.E2 //------------------------ // coplanar tris, static case //------------------------ // Tri1.Normal // Tri1.E0 x Tri1.Normal // Tri1.E1 x Tri1.Normal // Tri1.E2 x Tri1.Normal // Tri2.E0 x Tri1.Normal // Tri2.E1 x Tri1.Normal // Tri2.E2 x Tri1.Normal //------------------------ // coplanar tris, dynamic case //------------------------ // Tri1.Normal // Velocity // Tri1.E0 x Tri1.Normal // Tri1.E1 x Tri1.Normal // Tri1.E2 x Tri1.Normal // Tri2.E0 x Tri1.Normal // Tri2.E1 x Tri1.Normal // Tri2.E2 x Tri1.Normal Vector vAxes[12]; float fSep[12]; int iNumAxes; if (!CalculateCollisions(Tri1, Tri2, Velocity, vAxes, fSep, iNumAxes)) return false; int iSepAxis=-1; float fSepD; Vector fSepNormal; for(int i = 0; i < iNumAxes; i ++) { float a2 = vAxes * vAxes; if (a2 < 0.000001f) // degenerate continue; float d = fSep / a2; // normalise the axis parameter bool bCandidate = false; // the first valid axis we found. use it if (iSepAxis == -1) { bCandidate = true; } else { // we are dealing with interections? if(fSepD < 0.0f) { if (d > fSepD) bCandidate = true; } // we have found at least one collision else { if (d >= 0.0f && d < fSepD) bCandidate = true; } } if (bCandidate) { iSepAxis = i; fSepD = d; vSepNormal = vAxes / sqrt(a2); // normalise axis } } if (iSepAxis == -1) return false; fCollParam = fSepD; vCollNormal = vSepNormal; return true;}
I don't usually need to calculate the distance all the time, merely if they collide, and how. I guess I'm therefore off-topic. I'll read into that Voronoi stuff. It looks better for general convex structures than just triangles. I must say the
I prefer axis than plane, because ultimately, you end up doing 1D calculations, therefore along a line :) So I'm all the way round.
I think V-clip uses Voronoi regions. Well, another thing to research.
I prefer axis than plane, because ultimately, you end up doing 1D calculations, therefore along a line :) So I'm all the way round.
I think V-clip uses Voronoi regions. Well, another thing to research.
Author
Indeed V-Clip does use voronoi regions extensively. I've tried creating a V-Clip algo of my own but its really not easy to implement. I almost got it working with all my feature walking going in the right directions. The only problem was I became unstuck when verts lie very close or on region boundaries and math error could cause my feature walking to step back and forth accross this boundary in an infinite loop. Eventually I was about to throw my laptop through the window and so put it on the back burner. Maybe I'll come back to it sometime in the future though. If you're interested though:
http://www.merl.com/reports/docs/TR97-05.pdf
PS: Cheers for the code snippet. Much appreciated :)
http://www.merl.com/reports/docs/TR97-05.pdf
PS: Cheers for the code snippet. Much appreciated :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
