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 :)

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.

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.

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.

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.