Sign in to follow this  
Charles B

col. prediction at 2nd order

Recommended Posts

I have studied the boring underlying maths required to know in which conditions quadratic approximation of motions would be enough to deal with the prediction of contact points in time and space. The result tends to prove that physics based on predictive algos can be efficient and robust. It's obvious that any given metric precision of quadratic approximations can be achieved with enough rate of update (physics updates frequency). It's also intuitive that it depends on the maximum accelerations, angular speeds and radii of the objects. Here is the formula I have obtained. I spare you the details, unless one requests them. This is the metric error in world coordinates for a solid translating (no acceleration) and rotating at angular speed w and with a max radius R around its gravity center : d = R*((w*t)^3)/6! For R=1m, w=2PI/s, d=1mm, t=1/40 s. This means that a physics update of 40 FPS is enough for 1mm precision, 400FPS for 1 micro meter precision, that is below the floating point precision (relative to meters). When considering two objects rotating errors cumulate. The same if one considers the movement of one in the motion frame of the other since metrics are conserved. Thus if both objects have roughly the same R and w params we need 80FPS for 1mm precision and 800FPS for floating point precision or more. It's also easy to cumulate the metric error due to the accelerations relative to the previous problem. Since err = 1/2 a*t*t. For t=1/40 s, err = a/3200, if a=10m/s*s (1G), err=3mm. For typical real life accelerations, this means this error is slightly preponderant. For 400FPS, we have err=30 micro meters. Now here is a how quadratics could be used for quasi immediate contact point resolution. Imagine we're in the context of 2 convexes, an algo uses the separating plane theorem. At t0=0 (start of the current frame), the currently cached plane is one support plane Ha of object A, the plane of face Fa. Thus I deal with Face/Vert case for simplicity. We work in the frame of A. We use the polynomial matrix (M0,M1,M2) quadratics. Say, the nearest vertex Vb of object B has 4 adjacent edges thus vertex neighbours. We seek the first vertex hitting the plane, the time being t. That's very easy and root finding inside a [0,1] (by scaling time) interval (thus optimizable) three outcomes are possible : a) t> tmax, the end of the time interval of research (maybe the end of the current frame. Then no collision (this frame). b) The first vertex that crosses the plane is not the nearest vertex at t0. c) The nearest vertex is not in the Voronoi cell of Fa. d) else the collision is found. In cases c and d a new maximum separation axis must be found. t will advance very quickly and d will be < epsilon very quickly if a contact exists. I have dug the details, and the algo will not stall. In my opinion a contact is found in 1 step mainly, and 3 steps at max, very rarely. No contact will be missed.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
interesting stuff. makes sense, accuracy with t^(order+1)

an inituative and at first glance good maximum interval size for swepth spheres is 1/(wb-wa), ie the period of their relative rotation speed, possibly multiplied by a constant to tweak accuracy. however, your intergrationstep is going to be smaller than this value for about all cases anyway.

accuracy indeed doesnt seem a problem then.

i understand how to apply all this to spheres: evaluate position and speed at tmin, and position at tmax, and you can use these three constraints to obtain a quadratic (on the interval 0-1 for simplicity indeed).

then:
if at both times relative position < 0, collision along the whole interval.
if one relative position < 0, there is one root: use the quadratic to find it
if both are positive (most likely), get the determinant to see if there are roots, and find them if so.


however, how would you use a quadratic to sweep edge-edge or vertex-plane? youd need a way to evaluate their positions at a time t (ok easy) but also one derivative. the formula for the distance between a rotating plane and rotating point is probably a bitch, and its derivative even worse. the same goes for edges. id be interested to know what you think is a good way to handle this.

Share this post


Link to post
Share on other sites
@Eelco

interesting stuff. makes sense, accuracy with t^(order+1)

Yes, t^3 indeed for 2nd order, and I think your formula also works at any degree. This comes from the third order term of sinus, cosinus does not have one. The theory of alternate limited series is the heart of this mathematic demonstration. At the 3rd order it would be O(t^4/4!), a coefficient that comes from cosinus.

This all means that you really have to compute the appropriate sampling frequency, adapt to each collision pair or to the whole context if your speeds and radii can be bounded.


... an inituative and at first glance good maximum interval size for swepth spheres is 1/(wb-wa) ...


- wb-wa only works if the axes of rotation are the same.
- In case each rotations are around the center of mass=center of sphere, then wa and wb do not even count except for the collision response. Else, right the sampling frequency it linear to the absolute (I forgot to mention) rotation frequency.



However, your intergrationstep is going to be smaller than this value for about all cases anyway.

Yes I think 400FPS for the physics can be achieved on any modern PC, specially if collision prediction accelerates things, which is the even more case for small time steps. 400 FPS means don't worry anywhere, we're beyond floating point precision. That's nearly magic, we're 'exact'.

... and you can use these three constraints to obtain a quadratic (on the interval 0-1 for simplicity indeed).


Yes rescaling the polynomial is a few SSE operations. Next it will be ez to cull much root computations very early as you said. I have written the code in the past. If you detail the computation more than you did, make quick study of the params and quadratic properties, you'll find how to exploit the [0,1] constraint first and very efficiently. You'll discover analytically a condition that means reject early if the spheres go in opposite directions. Then a second condition (for t=1) with a bit more computations. Computing the determinant will be in rare cases. And getting the root only once you are sure one contact exists in the interval.



However, how would you use a quadratic to sweep edge-edge or vertex-plane ?


I mentionned it in () and you probably failed to notice or did not see what it was. The collision prediction needs what I call a 2nd degree polynomial matrix for each mesh, that is three matrices. That will be the only additionnal information required between the physics engine and the collision prediction module.

These matrices are easilly derived from the body state informations at time t=0. During the canonical physics frame (time rescaled), you'll have for any point attached to the solid, P(t)/world = M(t)*P/local. The inaccuracy is described by the previous post. P(t) is thus a quadratic vector <=> position at t=0, velocity and double acceleration.

Face vs Vert
------------
the formula for the distance between a rotating plane and rotating point is probably a bitch

Now here is how you can do. Say we have cached a separating plane that is the support of a face (of A), that we have to check vs a vert (of B).

Compute M(t)b/a = [sup]t[/sup]Ma(t)*Mb(t). Keep only up to the second order coeffs for the reasons I mentionned earlier : "cumulating errors". Thus 1+2+3 = 6 matrix muls (use SIMD). Maybe quaternions and translations would help, or any other quicker method. But anyway it has to be done only once per candidate mesh-pair during a frame, thus not a prioritary optimization.

For edge/edge :
---------------
In fact we usually cache a separating plane statically attached to A (or B, whatever) in the frame of A. Then it's the same as previous. When a plane is invalidated, a new one is searched on adjacent d-facets, until we get close to a contact in space and time. This should cull most cases in one or two steps.

If the case is not culled, a true edge/edge must be done. There a contact is quasi certain (99%). A special computation is required. One edge is fixed since we're in the frame of A. It's a bit trickier, since the nearest points are moving on both meshes. Thus the root finding is of higher degree in theory.

There are special conditions to be sure a contact will happen in the Voronoi cell of the edge (thus remove roots on the infinite line that would not belong to the finite edge). This is tested quickly. If it fails a new nearest d-facet pair (thus separating plane) must be searched, at a given time (static algo, usually one step required). Then, when a contact is certain, a root extraction must be done using a Taylor algo.

Roughly it's a coplanar test between 3 vectors so it results in a 3x3 determinant and a degree 4 polynomial : (AB^AC(t))*AD(t). But this can be optimized with the useful time interval constraint. I think it can be optimized and made degree 2 or 3 root finding.

Share this post


Link to post
Share on other sites
Yes, quadratic spline approximates cicrle pretty well.. it's kinda related to that spherical mirrors can be used in telescope instead of parabolic ones, even with required accuracy of light wavelength /8

Truing to derive edge-edge formula:
let edge 1 have ends A(t),B(t) and edge2 have ends A'(t),B'(t)

Collision happen when
( (A(t)-B(t) )Cross( A'(t)-B'(t) ))Dot( A(t)-A'(t) )=0
(geometrically-derived in mind)

i'm using notation
A(t).x = t2*A.x2+t*A.x1+A.x0
and same for y and z.
so A is 3 quadratic polynomials for xyz, with "overloaded operator()"

Let
P=A-B
Q=A'-B'
R=A-A'

So let's rewrite equation component-by-component:
(P(t).y*Q(t).z-P(t).z*Q(t).y)*R(t).x + [same blabla for other components,y and z] = 0
P(t).y * Q(t).z * R(t).x - P(t).z * Q(t).y * R(t).x + [same blabla for other components] = 0

There [same blabla for other components] can be written by substituting z->x, y->z , x->y

It's looks like we will have 6th degree polynomial, not 4th , and also it looks like it will be very long to write.... Probably i started with bad collision equation.:(

6th degree polynomials can be solved numerically pretty well and it's not that slow.

Notation: "." mean the same as in C++, like if all variables is a classes/structs, and polynomials also have overloaded operator (t).

Share this post


Link to post
Share on other sites

It's looks like we will have 6th degree polynomial, not 4th , and also it looks like it will be very long to write.... Probably i started with bad collision equation.:(

No it's OK. But in the case I described, that is compute in the frame of A, P=A-B is constant. So your own formula gives 4th degree too. I have explained why I can transform B into the frame of A and keep its 2nd order motion equations valid (somehow clamping the coefficients of higher degree).

Metrics approximations just cumulate in each transfo. So as long as the preconditions concerning wa, wb are true, the results concerning precision hold true.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yes,you're right, i haven't noticed we can do things in one system.

So, as i understand, you interpolate matrix that transforms from one coordinate system to other? That's good idea!

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B

... an inituative and at first glance good maximum interval size for swepth spheres is 1/(wb-wa) ...


- wb-wa only works if the axes of rotation are the same.

my formula was meant for the 2D case. in 3D finding a good metric for the number of subdivisions of your interval is probably more difficult, but for 2D, the above will work fine, since its a worst case formula.

Quote:

- In case each rotations are around the center of mass=center of sphere, then wa and wb do not even count except for the collision response. Else, right the sampling frequency it linear to the absolute (I forgot to mention) rotation frequency.

im not sure what youre saying here... the rotation velocity certainly is important for contact determination. if its several radians/frame, only one quadratic approximation certainly isnt going to suffice.

oh wait i think were talking about different things here.. i was thinking along the lines of as little physics updates as possible, ie as much as the framerate or something, and get the desired accuracy by subdividing the timeinterval where needed, whereas you seem talking about getting the desired accuracy by making more calls to UpdatePhysics.

the former is faster i think, and can handle unlimited rotationspeeds without loss of accuracy, by taking only smaller timesteps where its actually needed. it does require finding a good criterium on which to base your choice of timestep though. but i think its better than brute force, ie just making a huge number of calls to the physics update, and still introducing a limit on rotationspeed.

Quote:


However, how would you use a quadratic to sweep edge-edge or vertex-plane ?


I mentionned it in () and you probably failed to notice or did not see what it was. The collision prediction needs what I call a 2nd degree polynomial matrix for each mesh, that is three matrices. That will be the only additionnal information required between the physics engine and the collision prediction module.

These matrices are easilly derived from the body state informations at time t=0. During the canonical physics frame (time rescaled), you'll have for any point attached to the solid, P(t)/world = M(t)*P/local. The inaccuracy is described by the previous post. P(t) is thus a quadratic vector <=> position at t=0, velocity and double acceleration.

Face vs Vert
------------
the formula for the distance between a rotating plane and rotating point is probably a bitch

Now here is how you can do. Say we have cached a separating plane that is the support of a face (of A), that we have to check vs a vert (of B).

Compute M(t)b/a = [sup]t[/sup]Ma(t)*Mb(t). Keep only up to the second order coeffs for the reasons I mentionned earlier : "cumulating errors". Thus 1+2+3 = 6 matrix muls (use SIMD). Maybe quaternions and translations would help, or any other quicker method. But anyway it has to be done only once per candidate mesh-pair during a frame, thus not a prioritary optimization.

For edge/edge :
---------------
In fact we usually cache a separating plane statically attached to A (or B, whatever) in the frame of A. Then it's the same as previous. When a plane is invalidated, a new one is searched on adjacent d-facets, until we get close to a contact in space and time. This should cull most cases in one or two steps.

If the case is not culled, a true edge/edge must be done. There a contact is quasi certain (99%). A special computation is required. One edge is fixed since we're in the frame of A. It's a bit trickier, since the nearest points are moving on both meshes. Thus the root finding is of higher degree in theory.

There are special conditions to be sure a contact will happen in the Voronoi cell of the edge (thus remove roots on the infinite line that would not belong to the finite edge). This is tested quickly. If it fails a new nearest d-facet pair (thus separating plane) must be searched, at a given time (static algo, usually one step required). Then, when a contact is certain, a root extraction must be done using a Taylor algo.

Roughly it's a coplanar test between 3 vectors so it results in a 3x3 determinant and a degree 4 polynomial : (AB^AC(t))*AD(t). But this can be optimized with the useful time interval constraint. I think it can be optimized and made degree 2 or 3 root finding.


hmm youve kinda lost me here... however, i only today realized you dont really need to bother with derivatives of the distance function: simply calcing the distance on THREE timeintervals (does require one more state evaluation, quat->matrix (ouch) though) instead of using two and a derivative is much easier and just as accurate. then find roots and make sure that for each root found were inside the voronoi cell. quite easy actually. your method does sound faster though, since there is more potential for early rejection.

Share this post


Link to post
Share on other sites
EDIT : something went wrong here too with the login.

Quote:

- In case each rotations are around the center of mass=center...
I'm not sure what youre saying here...
oh wait i think were talking about different things here...

I mentionned the case of a single swept sphere, not part of a tree, centered at it's mass center. Then due to spherical symetry collision prediction here would not care of the rotations. But that did not make much sense to point this trivial case out I admit. I hope you do not feel insulted ;)


Quote:

... by making more calls to UpdatePhysics.


Yes, it is actually required if you want to have a constant accuracy whatever the angular speed..

But it does not have to be a full integration necessarilly. To be more precise one can still subdivide the physics in two functionalities :
- The dynamics integration (may be 50FPS). With updated forces, forces that might depend on the first order body state, example : damping.
- The kinetics integration that supposes both linear accelerations and angular velocities (or accelerations) are constant during 1/fq.

What counts for me is the kinetic part. I want to be able to retrieve State(Body)(t) enough times. Depending on the implementation, using quaternions and slerps maybe, it should handle cycloid vertex movements accurately. (Imagine a dart thrown. You want to know which part hits the wall, on the blade end or not). I suppose these computations do not approximate sinus and cosinus. Else it's the problem of the integration, not the prediction.

I mentionned a context where dynamic parameters (accelerations and angular velocities) are bounded as an example. Then the physics fq (both dynamics and kinetics all at once) can be set once for all for a given precision, at compile time for instance. The prediction also works mainly at the same fq. The interval of search is the same as the physics frame except the tmax optimization I have mentionned in the swept sphere thread.

I also said that in the general case the (kinetic) fq could be locally adaptable. Think of typical engines, that manage multiple constraints and collisions they also request more physics updates from time to time. (And usually they do it the whole scene which causes huge stalls). Also consider that when you deal with contacts, you also have to call the physics too. There is nothing new here. Still using prediction instead of detection warrants that 400FPS is almost always sufficient for 24bits of precision ! (40FPS for 10bits). Plus in each interval, operations are done in quasi-linear time.

So let's take a context where the upper limitation of w is not known. A vertex path can then be a portion of cycloid during your 10 milliseconds (say fq=100Hz).

If you keep you physics (integration) frequency constant and only subdivide the prediction part. Then the quadratic approximation of the kinetics between two integration steps might be too unprecise for two given solids. As I explained it, with rotations, the metric error grows in t cube ! So if you don't call back more integration steps and retrieve 'fresh' body states, whatever the number of subdivisions you'll make in your collision prediction (your stance if I understood you well), this error exists. And it may well not be acceptable.

It's basically the conclusion of the math I have studied in details in the first post.

Quote:

... simply calcing the distance on THREE timeintervals (does require one more state evaluation, quat->matrix (ouch) though) ...


It this does not change the required physics fq for a given context and precision tolerance. So I'll compare the two solutions in the same interval.

This is a possibility, it's just a matter of implementation and interface between the physics and the collision prediction modules. But it also heavilly impacts on the underlying algorithms :

Here is what you do :

M0 Mhalf M1
-|--------------|---------------|--> t
0 0.5 1


- 3 matrices required.
- You do not need to retrieve full body states. Just 3 frames cached, giving you any point at t=0, t=0.5 and t=1. You need a small computation to get the quadratic (easy). The problem to me is it requires 3 instants of physics (or just kinetic) evaluation.
- When you request P(t) you need 3 matrix*vert plus the construction of the vertex quadratic.


M0
+M1*t
+M2*t*t
-|------------------------------|--> t
0 1

- 3 matrices required
- For the same time step, no body state is required in advance, which is certainly more convenient. A quadratic matrix just requires one body state at t=0.
- When you want P(t) you need three matrix*vert
- I can also get V(t) with two matrix*vert.
- Crucial : I can get the path of Pb(t) relative to the kinetic frame of the other solid (A). This is done with 3 matrix multiplications for the whole interval and once. Cf my solution for moving faces against moving vertices.

Both solutions are just equivalent in theory but the last crucial point. Yours gives the polynomial by 'control points' and mine by its coefficients more directly. It's mainly a question of convenience and implementation. It depends on your engine architecture. But think of the face-vert case again.


Last word :
On the largest scale, to me the goal of a physics engine mostly based on prediction is to have a computational complexity linear to the number of objects (inputs) AND linear to the discrete events it has to treat (outputs) : the changes of contact states, impulsions, start/ends of constraints, triggered events (ex : enter teleport). The goal is thus algorithmic optimality.

[Edited by - Charles B on September 22, 2004 7:36:27 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B

Quote:

... by making more calls to UpdatePhysics.


Yes, it is actually required if you want to have a constant accuracy whatever the angular speed..

But it does not have to be a full integration necessarilly. To be more precise one can still subdivide the physics in two functionalities :
- The dynamics integration (may be 50FPS). With updated forces, forces that might depend on the first order body state, example : damping.
- The kinetics integration that supposes both linear accelerations and angular velocities (or accelerations) are constant during 1/fq.

What counts for me kinetic part. What I want is to be able to retrieve State(Body)(t) enough times. Depending on the implementation, using quaternions and slerps maybe, it should handle cycloid vertex movements accurately. (Imagine a dart thrown. You want to know which part hits the wall, on the blade end or not). I suppose these computations do not approximate sinus and cosinus. Else it's the problem of the integration, not the prediction.

I mentionned a context where dynamic parameters (accelerations and angular velocities) are bounded as an example. Then the physics fq (both dynamics and kinetics all at once) can be set once for all for a given precision (at compile time for instance) and the prediction also works mainly at the same fq. The interval of search is the same as the physics frame except the tmax optimization I have mentionned.

I also said that in the general case the (kinetic) fq could be locally adaptable. Think of typical engines, that manage multiple constraints and collisions they also request more physics updates from time to time. (And usually they do it the whole scene which causes huge stalls). Also consider that when you deal with contacts, you also have to call the integration. There is nothing new here. Still using prediction instead of detection warrants that 400FPS is almost always sufficient for 24bits of precision ! (40FPS for 10bits). Plus in each interval, operations are done in quasi-linear time.

So let's take a context where the upper limitation of w is not known. A vertex path can then be a portion of cycloid during your 10 milliseconds (say fq=100Hz).

If you keep you physics (integration) frequency constant and only subdivide the prediction part. Then the quadratic approximation of the kinetics between two integration steps might be too unprecise. As I explained it, with rotations, the metric error grows in t cube ! So if you don't call back more integration steps and retrieve 'fresh' body states, whatever the number of subdivisions you'll make in your collision prediction (your stance if I understood you well), this error exists. And it may well be not acceptable.

It's basically the math I have studied in details that tell to beware in choosing the right physics (kinetic) update frequency. In exact collision prediction the physics and collision frequency are the same.

yes, indeed, we now both understand eachother i think. however, what do you mean by not being able to archieve sufficient precision with a large timestep? (thats MY holy grail to be exact, algorithmic optimality comes a close second for me :))

in my case youre indeed looking at an arbitrary cycloid movement: the distance function can in theory be highly fluctuative. however, if you decide on the amount of timestep subdivisions at this moment instead of at the highest level, youre able to pick the right amount of subdivision of the interval in seperate quadatics, instead of the same amount between all objects even where its really not needed. indeed it requires finding a good condition on which to base your size of timestep, but i think it should be possible, and certainly worth the effort. more on this later.

Quote:

Quote:

... simply calcing the distance on THREE timeintervals (does require one more state evaluation, quat->matrix (ouch) though) ...


But this does not change the required physics fq for a given context and precision tolerance.

This is a possibility, it's just a matter of implementation and interface between the physics and the collision prediction modules. But it also heavilly impacts on the underlying algorithms :

Here is what you do :

M0 Mhalf M1
-|--------------|---------------|--> t
0 0.5 1


- You do not need to retrieve full body states. Just 3 frames cached, giving you any point at t=0, t=0.5 and t=1. You need a small compuation to get the quadratic (easy). The problem to me is it requires 3 instants of physics (or just kinetic) evaluation.
- When you request P(t) you need 3 matrix*vert plus the construction of the vertex quadratic.


M0
+M1*t
+M2*t*t
-|------------------------------|--> t
0 1


- For the same time step, I just no body state in advance. A quadratic matrices just requires one body state at t=0.
- When you want P(t) you need three matrix*vert
- I can also get V(t) with two matrix*vert.
- Crucial : I can get the path of Pb(t) relative to the kinetic frame of the other solid.. This is done with 3 matrix multiplications for the whole interval and once. Cf my solution for moving faces against moving vertices.

Both solutions are just equivalent in theory but the last crucial point. Yours gives the polynomial by 'control points' and mine by its coefficients more directly. It's mainly a question of convenience and implementation. It depends on your engine architecture. But think of the face-vert case again.

yes, thats a good summation of both our methods. mine does require more state evaluations, but as you rightly point out you can cache one state-matrix so two evaluations/frame are all thats needed, and the evaluation of the atate at t=1 is needed anyway.

so its a case of one extra state evaluation vs finding the first and second derivatives of the distance function to construct a taylor polynome. again im not sure how you plan to go about finding these derivatives in an elegant manner for all different cases. one extra state evaluation sure seems easier to me, if potentially slower. besides the error function has three roots at t=0, 0.5, 1 for my method, giving an quite equally spread out error, whereas with a taylor polynome the error would be distributed less favorably.

besides i had an idea regarding the adaptation to smaller timesteps where needed and this interpolation method. aside from the state at the end of the last frame, the derivative found there with the use of the quadatic approx can also be cached. if this derivative is too different from the one found using the quadratic at the start of this frame, our approximation is poor, so we split the interval in two, do two new state evaluations at t=1/4&3/4 and recurse.

you can recuse up the the precision of 400hz, you can go even further, but most of the time you will have sufficient precision without any recursion.

Quote:

Last word :
On the largest scale, to me the goal of a physics engine mostly based on prediction is to have a computational complexity linear to the number of objects (inputs) linear to the discrete events it has to treat (outputs) : the changes of contact states, impulsions, start/ends of constraints, triggered events (ex : enter teleport). The goal is thus algorithmic optimality.

as i said, i certainly think linear time complexity and efficiency is an important goal. however, to me, robustness and elegance (no hacks like capping speeds) are even more important.

ideally we could have both :)

Share this post


Link to post
Share on other sites
About the Update Physics stuff. I think it was mostly a qui proquo. I never have to update the whole physics and certainly not the whole scene. This frequency will be constant as long as it handles damping and such difficult 'differentials' well.

I just need to integrate the motion (with quaternions, or matrices whatever) at a sufficient frequency so that the quadratics match, within the preset metric margin, what the physics would produce if they were continuous. Just what you are probably obliged to do to obtain your 3 matrices.



About the approximation stuff, using înterpolation instead of extrapolation is better. I admit your claim is right. But I can also consider 3 degree 0 matrices and do the same as you. The choice then is more between forming quadratics at the matrix level or at the point level.

You did not answer to the fact that having quadratics at the point (vertex) level instead of the matrix level will not allow you to compute in the local referential of A or B. Thus quite a problem for prediction at the primitive level.

My first idea was yours. But just like you I wondered how I would cope with 'exact' face-vert and edge-edge prediction routines. That's why I have pushed the math issue and found the idea of quadratic matrices to simplify and solidify the primitive routines.

Using the 3 points interpolation method, you will certainly block your prediction system to the level of swept spheres. Or else, as Dmytry pointed out, you will have to seek the roots of higher degree equations, and more complex computations to do. The precision predicates will also be much more difficult to analyse.

Edit :

BTW, your interpolation brings something probably valuable to optimize my quadratic matrices. Compute the transfos from B to A at t=0, t=0.5, t=1 and THEN transform it into a quadratic matrix ... or use your method, 3 transfos, and form a quadratic point. This way you can deal with one static plane or one static edge in every case.

Since it's all linear algebra, in the case of the face-vertex, one can also make 3 point transfos, three plane equations, and form a quadratic at the scalar level : distance(t).

Share this post


Link to post
Share on other sites
i have to say your take on the maths seems to go a little over my head, so excuse me if im missing something obvious. i havnt had too much linear algebra in uni yet, infact most i know is from simple self-taught 3x3 geometry transformations for use in computer graphics. i yet fail to wholly grasp the purpose and implementation of transforming quadratic functions.

Quote:

You did not answer to the fact that having quadratics at the point (vertex) level instead of the matrix level will not allow you to compute in the local referential of A or B. Thus quite a problem for prediction at the primitive level.

Using the 3 points interpolation method, you will certainly block your prediction system to the level of swept spheres. Or else, as Dmytry pointed out, you will have to seek the roots of higher degree equations, and more complex computations to do. The precision predicates will also be much more difficult to analyse.

i dont see why you claim my interpolation method wouldnt work for the geometry level. i think thats the beauty of it: the genericness: evaluate a distance function at three points (beit the distance function of sphere-sphere, edge-edge or plane-point, doesnt really matter), interpolate, possibly recurse for higher precision, and in the case of geometry collisions, make sure the roots occur inside the voronoi cell.

i realize the distance function of for example edge-edge is of higher order than that of sphere-sphere, thus harder to approximate, but it doesnt require seeking the roots of higher order equations. the recursion should handle it given it knows when to subdivide the interval into more quadratics.

i really should get off my lazy ass and implement some of this. reality is most of the time the best test-envirnoment.

Share this post


Link to post
Share on other sites
No it's not about the interpolation issue. (Read the edit). I take it for granted it's equivalent, and certainly more precise and easier to code. So a point for you.

The problem is being able to work in the referential of A or B.

My claim is : don't compare in world coords. Try to have the maximum number of vertices (3 or 2) static. The way how I understood your method, you would have :

Plane A(t), B(t), C(t) vs Vert D(t)
=> 6th degree, relative to A.

I have a simple :

Plane A, B, C vs Vert D(t)
=> 2nd degree plain and simple.

Since plane vertex is the base of separating axis or Voronoi speed ups it's really important.

To be clear the general algo would be :

For each candidate mesh pair.
For each mesh.
Compute Ma(0), Ma(.5), Ma(1), smae for B.
If the previously cached nearest facet of A was a face.
Compute Mb/A(0), Mb/A(.5), Mb/A(1) ...
Then for the vertex of B compute Vb(t)/a


BTW, Ma(1), Mb(1) and certainly Ma/b(1) will be used the next frame. That's an advantage of your interpolation idea. And in fact we could cache even more if the actual time step between physics frames is 0.5 instead of 1.

[Edited by - Charles B on September 22, 2004 1:42:19 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
No it's not about the interpolation issue. (Read the edit). I take it for granted it's equivalent, and certainly more precise and easier to code. So a point for you.

no its not the interpolation that i was talking about in my last post, rather the ability of the recursive part of the algorithm to also handle more complex, higher order functions. after all, its able to cope with periodic functions, which have infinite order.

Quote:

The problem is being able to work in the referential of A or B.

My claim is : don't compare in world coords. Try to have the maximum number of vertices (3 or 2) static. The way how I understood your method, you would have :

Plane A(t), B(t), C(t) vs Vert D(t)
=> 6th degree, relative to A.

I have a simple :

Plane A, B, C vs Vert D(t)
=> 2nd degree plain and simple.

Since plane vertex is the base of separating axis or Voronoi speed ups it's really important.

To be clear the general algo would be :

For each candidate mesh pair.
For each mesh.
Compute Ma(0), Ma(.5), Ma(1), smae for B.
If the previously cached nearest facet of A was a face.
Compute Mb/A(0), Mb/A(.5), Mb/A(1) ...
Then for the vertex of B compute Vb(t)/a


BTW, Ma(1), Mb(1) and certainly Ma/b(1) will be used the next frame. That's an advantage of your interpolation idea. And in fact we could cache even more if the actual time step between physics frames is 0.5 instead of 1.

ok i understand what youre after now. it certainly sounds promising, but i have one fundamental (and maybe stupid) question. how would you transform a function thats higher order in nature to something of a lesser order? then either the higher order part can be simplified away if you write things out more precisely (and my algo wouldnt even be bother by these higher order terms then), or youre simplifying/approximating things in one step somewhere along the way.

i suspect the latter, in which case our methods arent all that different.

Share this post


Link to post
Share on other sites
I am not certain of your concern. I can interpret your question as :

"Where is the difference gone between the two computations since one method give second order in the end and the first gives 6th order ?"

Well it's in my preample where I justify that the errors of two consecutive quadratic transformations (4x4 matrix) cumulate. This means that the conditions on fq, wa, wb, Rb, Ra are enough to warrant that the last algo has the precision I mentionned in the first post. It's because this algo is based on the same maths, and you pointed out rightly that interpolating is even more precise than my original solution.

Else if your question was rather :

"Does it really work for any kind of movement ?"

Not totally. My predicate is a certain class of movement :
- constant linear acceleration.
- constant angular velocity.

I only warrant that, for any point that belongs to one of the solids, seen in any of the world or local referentials, a metric difference (say 2^-20) is ensured compared to such a class of movement.

But in real life this class of movement is far enough to describe the kinetics between two physics frames. Because it falls well under the precision of the typical (discrete) integrators. Anyway, implicitely between each time steps, typical integrators do not model more than acc=ct and w=ct.


"and my algo wouldn't even be bother by these higher order terms then"
Clamp the higher order ... Beware of the intuition here. At first glance, roughly, it looks equivalent. But it would require some more in depth and math to see if it does not add important errors. This may be an additionnal factor 2 or 10, or nothing, I have no way to answer atm. Think of your faces and edges deforming with quadratics in world coords. The face normals changing also not very linearilly, etc... I can assert my demo (I had a solid math formation in the past, forgot most of it though), I can detail it if you want. But I can not respond to this new question by a sure yes or no atm.

But there is something certain though, efficiency. In my method you can use precomputed plane equations in local coords, which gives distances directly (no sqrt required). There are many advantages exploiting static coordinates in one local referential. You can also cache separating planes safely between frames, since they are always in the same local coordinates. This all also certainly affects precision somehow.

[Edited by - Charles B on September 22, 2004 4:50:03 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
"Where is the difference gone between the two computations since one method give second order in the end and the first gives 6th order ?"

Well it's in my preample where I justify that the errors of two consecutive quadratic transformations (4x4 matrix) cumulate. This means that the conditions on fq, wa, wb, Rb, Ra are enough to warrant that the last algo has the precision I mentionned in the first post. It's because this algo is based on the same maths, and you pointed out rightly that interpolating is even more precise than my original solution.

aha, i think i understand it now.

Quote:

But there is something certain though, efficiency. In my method you can use precomputed plane equations in local coords, which gives distances directly (no sqrt required). There are many advantages exploiting static coordinates in one local referential. You can also cache separating planes safely between frames, since they are always in the same local coordinates. This all also certainly affects precision somehow.

good points.

i think ill start working on my method tomorrow or the day after. if you ever get around to implementing yours, it will be interesting to compare.

Share this post


Link to post
Share on other sites
You maybe know that I am currently all dedicated to my optimal high perfs and multiplatform Open Source math lib. If I keep on visiting the math/physics forum it's to gather some thoughts and feedback on the many potential applications of maths for games.

It helps me designing a better interface of the lib. I also had the project to build a physics engine based on prediction and continuous time some years ago. But in the end I prefered concentrating on terrain engines. And now it's this math lib, I'll be back to terrain rendering next, with some awesome ideas and unitary tests already on my PC. And this will all hugely benefit of speedy maths.

So I surely won't have the time to implement my ideas on physics in a short term. However, if you dare to share some unitary, case tests with me, I will probably be able to write some highly optimized and generic primitive routines for collision prediction. For instance the optimized [0,1] quadratic root finder. Upper level would be :

moving sphere vs moving sphere
plane vs moving vertex.
plane vs moving spheres.
edge vs moving edge.

It would be a good application to test both the efficiency of my library and verify our ideas on collision prediction.

Last, my purpose is not to be necessarilly always right, but wouldn't it be simpler for you to implement the 'half in local coords' algo first ? The primitive routines will certainly be easier and faster to code.

You can write simple unitary tests in glfw, glut or whatever light framework, in order to verify and benchmark each routine separately. For each primitive, compare a detection method with a very small time step and the prediction method. Compare the results visually. Some keys bound to commands like : zoom in/out, replay, freeze at collision, rewind, slow down, etc... Since one d-facet is static, it will be easier to set the camera.

Then it would be easier to test new optimized versions of the primitives in these unitary tests, so that you can integrate them safely in your engine later.

Any thoughts on these proposals ?


Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
You maybe know that I am currently all dedicated to my optimal high perfs and multiplatform Open Source math lib. If I keep on visiting the math/physics forum it's to gather some thoughts and feedback on the many potential applications of maths for games.

It helps me designing a better interface of the lib. I also had the project to build a physics engine based on prediction and continuous time some years ago. But in the end I prefered concentrating on terrain engines. And now it's this math lib, I'll be back to terrain rendering next, with some awesome ideas and unitary tests already on my PC. And this will all hugely benefit of speedy maths.

So I surely won't have the time to implement my ideas on physics in a short term. However, if you dare to share some unitary, case tests with me, I will probably be able to write some highly optimized and generic primitive routines for collision prediction. For instance the optimized [0,1] quadratic root finder. Upper level would be :

moving sphere vs moving sphere
plane vs moving vertex.
plane vs moving spheres.
edge vs moving edge.

It would be a good application to test both the efficiency of my library and verify our ideas on collision prediction.

yes, working at too much things at a time isnt a good idea. i myself also do not really have the time to dedicate to this project it deserves, but ill see where it ends up.

Quote:

Last, my purpose is not to be necessarilly always right, but wouldn't it be simpler for you to implement the 'half in local coords' algo first ? The primitive routines will certainly be easier and faster to code.

You can write simple unitary tests in glfw, glut or whatever light framework, in order to verify and benchmark each routine separately. For each primitive, compare a detection method with a very small time step and the prediction method. Compare the results visually. Some keys bound to commands like : zoom in/out, replay, freeze at collision, rewind, slow down, etc... Since one d-facet is static, it will be easier to set the camera.

Then it would be easier to test new optimized versions of the primitives in these unitary tests, so that you can integrate them safely in your engine later.

Any thoughts on these proposals ?

its not my purpose to be always right either. :) yet my reason for coding is mainly implementing things ive come up with: implementing a paper or copying someone elses work is nowhere near as statisfying to me.

i have a clear picture in my head of what i want to to, and most importantly HOW to do it. i cant really say the same of your method, but when i have this up and running id love to try your method aswell. it shouldnt requite too much chance since they have a lot in common.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this