Skip to main content
gamedev.net
🔒 Locked

Recognizing Deformations

Started by haphazardlynamed Jul 4, 2004 at 7:41 AM 5 replies 800+ views
Original Post
haphazardlynamed
haphazardlynamed
Hi, Ive drawn a little picture to help explain... http://people.ucsc.edu/~asue/deform.jpg Suppose we have an initial box defined by 4 verts joined by 4 edges as in diagram A. It has a local X and Y axis as shown in diagram B, which are aligned with the horizontal and vertical edges. But suppose the verts have been displaced as in C, I can easily do some vector averaging to find the new Local X and Y (which are not orthoganal anymore, but are offset by a degree corresponding to the deformation amount). However, How do I perform this same operation for a complex arbitrary object, as in diagram D? In this situation, the edges are not parralel nor are they aligned with the initial Local X and Y. So I cant do simple vector math to find them in the event of a deformation/ rotation/ etc. Now before you tell me that I should already know the local X and Y beforehand. In my model the object as a whole is 'abstract', it only exists as a relationship between verts -simple particles with simple translational physics thus there is no directly controlled rotation or deformations, rather they are 'measured' context...(tho i suspect not directly relavant to the solution) This is all going to be part of an interesting physics engine i'm building... based upon the principals introduced in Jakobsen's Adv. Char. Physics. Except to be much more computationaly effecient, rather than resolve many individual constraints I derive Local X and Y axis of the object as a whole, then enforce a single angle constraint between them, and reposition the verts accordingly once i have the new reference frame. The structure then, is defined by my initial 'snapshot' with Jakobsen's constraints being used only to resolve torques and rotations, not to create the object. This allows me to have much more complex objects, but without the computational overhead of resolving all the geometric constraints to hold it together. (assuming I can generalize this for arbitrary meshs, not just simple box)
LilBudyWizer
LilBudyWizer
Depends upon the transform applied. Translation, rotation, non-uniform scaling and shear would be easy enough as long as you have enough points. You have a matrix of unknown coefficients. You have a set of known points that are transformed to a set of known points. Assuming a 3x3 matrix you have nine unknowns. Each point gives you three equations. Three points gives you nine equations of nine unknowns. You can solve that.

Twist, bend, taper and similar deformations are much harder. That is because they are not done by a matrix of constant coefficents. As an example twist is a rotation about an axis where the angle of rotation is dependant upon your displacement along the axis. Now you're not dealing with simple linear equations. The transform matrix has equations rather than simple constants. Without any knowledge of the deformation then you are trying to find the "right" equations from the set of all possible equations. Not possible to solve. Even knowing where the equations occur and their form the exact solution would depend on their form. You can't solve sin(x+t)^2 for x the same as you would for (x+t)^2.
Keys to success: Ability, ambition and opportunity.
haphazardlynamed
haphazardlynamed
I think I see what youre suggesting
most of the simpler transforms are simple matrix operations, so provided I know the general form it would only be a matter of solving for the coefficeints.

Unfortunatly, the displacement on the verticies is due to collisions with other objects in the physics model, thus they are not guaranteed to fit any known transformation.(essentially random) So solving matrixes... I dont think would really work.

My goal isnt really to find the Exact transform/deform that occured, only to get a measure of the objects new orientation -the local X and Y
Since the object is likey deformed... this would have to be an approximation of the new orientation... some kind of weighted average over the verticies.... though Im not sure how to represent such a thing

Bucket_Head
Bucket_Head
Probably the easiest thing to do would be to introduce a few artificial points, one for each axis, and let those get transformed along with the rest of them, and then just use those for your transformed objects' relative axes. You could constrain them in place relative to all the other points, so they'd probably come out very close to right in the end. You could always add a few extra of these orientation points too to average results, if you're concerned about the results being skewed based on where in the model they're placed.

Hooray for imprecise models, woo.
Hai, watashi no chichi no kuruma ga oishikatta desu!...or, in other words, "Yes, my dad's car was delicious!"
MrRowl
MrRowl
I did something very similar - using a combination of the particle/verlet method with a rigid-body approach. I think you can use a technique called "singular value decomposition" to derive the best-guess orientation change between one "sea" of points/particles and another. An implementation of svd is given in the "Numerical Recipies" book. Some stuff here:
http://kwon3d.com/theory/jkinem/rotmat.html
However, I never got it working properly, though it nearly did... :( In the end I got it working by embedding 6 non-colliding points in the object that were meant to track the orientation. You can have a look at http://www.rowlhouse.co.uk/carsim in sim_object.cpp (look for the #if 0 etc)
LilBudyWizer
LilBudyWizer
Seems sort of like a least squares then. Basically what orientation of the old mesh would result in the smallest variance from the new points. That's assuming you can match the points up. Seems, perhaps, that you have TA=B. So maybe solve TAA^T=BA^T where A^T is the transpose of A. That's basically a wild guess, but you could test it by using T to transform the original and draw it over top of the deformed object.
Keys to success: Ability, ambition and opportunity.
haphazardlynamed
haphazardlynamed
Thanks for all the advice everyone.
I think I've found an alternative solution to the problem
MrRowl, it sounds like we were both trying to build the same system, so you might be interested in this:

http://people.ucsc.edu/~asue/orientation.jpg

In figure A we have an arbitrary mesh, that is more complex than the first box example. A red X marks the average of all the verts -call it the centroid -yeah my drawing isnt exactly right, but you get the idea....

in figure B, if we draw vectors from each vert to the centroid, we know that they must always sum to 0

figure C, if we draw any seperating line thru the centroid that does not intersect any verts, thus splitting the verts into 2 distinct groups, we know that all the vectors on one side summed with all on the other must still add up to 0, regardless of what seperating line was chosen
figure D,
Thus the blue group, and the red group must be equal and opposite magnitude. Therefore.... if we negate one of the groups, then add them together, the result will be twice the magnitude of one of them, and is guaranteed to be Non-Zero since none of the verts lie on the seperating line.
This new vector sum (green) can be used to identify the orientation of the object as a whole.
Note that the length and direction of orientation are Unkown relative to the seperating line we used, but are deterministic.
So all you need to do is have a precalculation step for objects to calibrate what the orientation basis will be.(and keep track of what group (red vs blue) each vert belongs to)
Also note, that the verts which are farther from the centroid, will have more leverage on the overall orientation of the object. This is exactly the same as how things work in reality, thus the system is able to represent moment of Inertia, without the use of an Inertia tensor, and it can handle arbitrary models!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.