Sign in to follow this  
h4tt3n

Orientation and angular velocity of particle cloud

Recommended Posts

Hello folks,

 

For a cloud or group of particles it is possible to find the global linear state (average position and velocity "as if" the particles were one body) by summing up particle position and velocity multiplied by particle mass and then dividing the sums with global mass. Something like this:

for each particle p
    global_position += p->position * p->mass
    global_Velocity += p->velocity * p->mass
next p

global_position *= global_inverse_mass
global_velocity *= global_inverse_mass

Is there a similar unambiguous way to determine rotational or angular state for a group of particles? I have managed to determine angular velocity by summing up angular momentum and dividing by global moment of inertia, but I still miss a good way to determine orientation. Simply computing angle as 

angle += angular_velocity * time_step

 will quickly drift away from the correct value. Thanks in advance!

 

Cheers,

Mike

Edited by h4tt3n

Share this post


Link to post
Share on other sites

This seems related to "shape matching"; this recent paper should have lots of useful references (and itself presents a method to extract rotation from a point cloud): http://matthias-mueller-fischer.ch/publications/stablePolarDecomp.pdf

Note that AFAICT you'll need some sort of "rest pose" defined for the points or the concept of orientation doesn't make a lot of sense.

Share this post


Link to post
Share on other sites

Thanks, I'll take a look at it. Like you suggest, I have implemented a method, where each particle has a "rest position" which is translated and rotated like a regular rigid body with explicit angular properties. What I'm looking for is a method that works without the hidden points.

 

Cheers, Mike

Share this post


Link to post
Share on other sites
What do "forward" or "right" or "up" mean for your point cloud? What are you going to use those values for after you've found them? If you can describe what you want, we can think about a method to produce it.

If each particle is allowed to move in arbitrary ways, then you could have one half moving clockwise around an axis, and the other moving counter-clockwise around that axis. You could have some particles which aren't moving. You could have some particles which are yo-yoing along a line. Orientation doesn't make sense for those cases. Edited by Nypyren

Share this post


Link to post
Share on other sites

So you're just trying to track orientation? Can the particles drift from their original positions relative to the reference frame of the particles? Have you heard of principal component analysis?

Share this post


Link to post
Share on other sites

What do "forward" or "right" or "up" mean for your point cloud? What are you going to use those values for after you've found them? If you can describe what you want, we can think about a method to produce it.

If each particle is allowed to move in arbitrary ways, then you could have one half moving clockwise around an axis, and the other moving counter-clockwise around that axis. You could have some particles which aren't moving. You could have some particles which are yo-yoing along a line. Orientation doesn't make sense for those cases.

 

In the linear motion case, any particle can move freely relative to the rest of the particles, including "yo-yoing". Still, the global position and velocity are incredibly useful for analyzing the behavior and properties of the cloud as a whole. For instance, this is used in orbital mechanics to analyze anything from asteroid belts over gas clouds to entire clusters of galaxies. The same goes for the rotational properties of a body of particles. The linguistic terms of "forward" and "up" have no meaning here, it's an entirely abstract mathematical description. 


So you're just trying to track orientation? Can the particles drift from their original positions relative to the reference frame of the particles? Have you heard of principal component analysis?

 

I am trying to keep track of angular orientation and velocity. Yes, the individual particles can in principle move freely relative to the body of particles as a whole. Haven't heard of principal component analysis, will take a look at it.

Edited by h4tt3n

Share this post


Link to post
Share on other sites

It is possible to use PCA to find a basis that represents the "orientation" of the cloud. However as particles deviate from their past positions PCA can possibly yield a wildly different basis. However, this is unlikely if timesteps are small enough. Just thinking about it, it seems some kind of iterative refinement would work pretty well given an initial basis found with PCA, then after each timestep the frame can be nudged to find a minimum fit with the new positions. Anyways, that's all I know, so I can't give any more advice.

Share this post


Link to post
Share on other sites
Just a random idea: If you've found the global average angular velocity, that means you should have an average axis of rotation. From there, take one easy-identifiable particle in the cloud which is orbiting individually as close to that average as possible and compare its current position to a fixed point in its orbit (perhaps one of its maxima along a specific axis) and that average axis of rotation. As long as that one particle is a good representative for the cloud's overall rotation, that should give you noise-free orientation information for a 'representative' case in your cloud and you can just ignore the erratic particles.

Though this wouldn't even work for orbits if different particles orbit at different distances from the center, because angular velocity is lower the further you are from the barycenter (making your "years" longer). If the Earth is your representative particle, that has nothing to do with the angle that any of the other planets are at.

If you are interested in the overall "bulge" direction(s) of your cloud, then PCA will be a better bet. Edited by Nypyren

Share this post


Link to post
Share on other sites
Another idea would be to do a least square fit to find the average line representing the cloud,
then project all particles to the plane normal to that line and repeat the process go get a second line orthonormal to the first.
Like any other method this will be unstable, but may suffice and is easy to implement.

Share this post


Link to post
Share on other sites
Do the particles themselves rotate, or just translate which gives rise to a rotation of the cloud?

Once you know the centre of mass, you could apply the linear velocity of each particle as a linear impulse upon the imaginary global body, which will create a torque. Integrate all those and you can get an angular velocity for the global body. If you start the body off with any arbitrary orientation, but apply these angular velocities over time, you could keep track of the changing orientation over time. So the plain linear motion of the particles would rotate the global body.

Share this post


Link to post
Share on other sites
Initally i wanted to make the same sugestion than Hodgman, but you say it 'will quickly drift away from the correct value.'

Now i need to ask how do you determinate this drift, what is the correct value, or what's the problem?
 

I have managed to determine angular velocity by summing up angular momentum and dividing by global moment of inertia


There may be an error with this: I assume you calculate inertia over the global coordinate system axis,
but this gives a somehow bad approximization because:
1. The global axis may be a bad fit to represent inertia reasonable well
2. Finding a better set of orthonormal axis leads to the same problem you already have: Finding a good orientation.
3. It's not possible to represent inertia using 3 numbers for arbitary bodies anyways. (This is often ignored but true, 3 numbers are good for a cube or a ellipsoid, but for something like a duck it's just an approximization. For the duck we can only calculate exact inertia for a given axis)


So i think you should first rethink your way to calculate average angular velocity like Hodgman said.

I've had a similar problem: From multiple bodies calculate a single virtual body conserving momentum.
This worked even all bodies have their own inertia, mass, angular and linear velocities,
But the resulting virtual body has no orientation or inertia matrix, it just knows its mass and velocities.
Inertia needs to be found on a given axis when required by iteratin over all unique bodies.


Edit:
I think you can find average angular velocity without a need to care for torque or inertia somehow like this:
COM = sum up all particle positions * particle mass / total mass of all particles
AVavel = sum up for all particles: (particle.pos - COM).cross(particle.velocity)

... but i'm not into physics right now so not sure.



Edit2:

Oh, i did not notice you work in 2D, so most things i've said about inertia do not apply because in 2D there is only one axis of rotiation possible :) Edited by JoeJ

Share this post


Link to post
Share on other sites

Do the particles themselves rotate, or just translate which gives rise to a rotation of the cloud?

Once you know the centre of mass, you could apply the linear velocity of each particle as a linear impulse upon the imaginary global body, which will create a torque. Integrate all those and you can get an angular velocity for the global body. If you start the body off with any arbitrary orientation, but apply these angular velocities over time, you could keep track of the changing orientation over time. So the plain linear motion of the particles would rotate the global body.

 

This is exactly what I have been doing so far, getting usable but not quite accurate enough results. The clouds linear position and velocity, moment of inertia, and angular velocity can be determined accurately. Angle is then determined by integrating with time, and this tends to drift, especially when the cloud experiences sudden changes in shape and orientation. 

Edited by h4tt3n

Share this post


Link to post
Share on other sites

Do the particles themselves rotate, or just translate which gives rise to a rotation of the cloud?

Once you know the centre of mass, you could apply the linear velocity of each particle as a linear impulse upon the imaginary global body, which will create a torque. Integrate all those and you can get an angular velocity for the global body. If you start the body off with any arbitrary orientation, but apply these angular velocities over time, you could keep track of the changing orientation over time. So the plain linear motion of the particles would rotate the global body.

 
This is exactly what I have been doing so far, getting usable but not quite accurate enough results. The clouds linear position and velocity, moment of inertia, and angular velocity can be determined accurately. Angle is then determined by integrating with time, and this tends to drift, especially when the cloud experiences sudden changes in shape and orientation.


What are you comparing against to measure the accuracy?

Share this post


Link to post
Share on other sites

 

What are you comparing against to measure the accuracy?

 

 

I am using this method to analyze and control deformable soft bodies in a physics engine. When creating an object of a particular, well defined shape, like for instance a truss or girder with the orientation vector pointing along the length of the body, I can see on screen how the orientation (visualized by a point and a line) drifts away from the physical shape. This happens slowly by simply adding angular velocity and letting it rotate unconstrained by external forces. When influencing it through collision or by constraining it to other bodies, the orientation quickly drifts away from the correct value.

Share this post


Link to post
Share on other sites
You"re working with set of particles I think you should find center of gravity of this set then apply forces on this obbject or even better you could sum and divide by amount

Anyway I would reauire more details on actually what are you trying to calculate

Share this post


Link to post
Share on other sites

Sounds like you're doing some pretty interesting fluid dynamics. I recalled reading a book on this topic. It might be a bit wasteful to concider every particle in this manner as the solution develops,  you could very easily have infinitely many particles in one point at any given time if you are trying to go for a physically based reaction in a non-vacuum medium.

You might want to try using a vector field of some resolution if you are trying to simulate a medium. This can give you an amount of history for curent forces, and can help you simulate interacting particle clouds and clusters. This will also give you information pretty cheaply to rotate the cloud if necessary.

Edited by Tangletail

Share this post


Link to post
Share on other sites

 

 

What are you comparing against to measure the accuracy?

 

 

I am using this method to analyze and control deformable soft bodies in a physics engine. When creating an object of a particular, well defined shape, like for instance a truss or girder with the orientation vector pointing along the length of the body, I can see on screen how the orientation (visualized by a point and a line) drifts away from the physical shape. This happens slowly by simply adding angular velocity and letting it rotate unconstrained by external forces. When influencing it through collision or by constraining it to other bodies, the orientation quickly drifts away from the correct value.

 

This seems like the exact use-case for shape matching -- i.e you start with a particular arrangement of particles. Why exactly do you want to avoid having to define a "rest pose"?

Share this post


Link to post
Share on other sites
I agree with above, if you take an initial shape and convert it to a cloud, you already have a rest pose.

If you keep track of particle IDs in any manner (i.e. whatever key you use to store the particles in the first place - array index, etc), you can quickly compare them.

Let's say you've got your truss/girder. Keep track of two points at the opposite ends, and BAM! You have a simple orientation by forming the line between them. If you want 3 dimensions, add a third point which is significantly non-colinear vs. the first two points (pick three points which make a triangle that isn't skinny).

You don't need to check every single particle against its rest position. You only need enough for whatever you're going to use the orientation info for later. Edited by Nypyren

Share this post


Link to post
Share on other sites

 

 

 

What are you comparing against to measure the accuracy?

 

 

I am using this method to analyze and control deformable soft bodies in a physics engine. When creating an object of a particular, well defined shape, like for instance a truss or girder with the orientation vector pointing along the length of the body, I can see on screen how the orientation (visualized by a point and a line) drifts away from the physical shape. This happens slowly by simply adding angular velocity and letting it rotate unconstrained by external forces. When influencing it through collision or by constraining it to other bodies, the orientation quickly drifts away from the correct value.

 

This seems like the exact use-case for shape matching -- i.e you start with a particular arrangement of particles. Why exactly do you want to avoid having to define a "rest pose"?

 

 

I am among other things using it for shape matching. I don't necessarily want to avoid a method based on a rest pose, I have already implemented this. It's just that I am almost completely sure it can be done without it. If a particle cloud's linear state, moment of inertia, angular momentum, velocity, and energy can be computed accurately from particle state, then so can the angle. I just haven't figured out how yet...

 

I agree with above, if you take an initial shape and convert it to a cloud, you already have a rest pose.

If you keep track of particle IDs in any manner (i.e. whatever key you use to store the particles in the first place - array index, etc), you can quickly compare them.

Let's say you've got your truss/girder. Keep track of two points at the opposite ends, and BAM! You have a simple orientation by forming the line between them. If you want 3 dimensions, add a third point which is significantly non-colinear vs. the first two points (pick three points which make a triangle that isn't skinny).

You don't need to check every single particle against its rest position. You only need enough for whatever you're going to use the orientation info for later.

 

I store all particles in a global std::vector like array. All objects store a similar array of member particle ptr's. This way, particles can be added and removed from objects at run-time without too much trouble, and a particle can be a member of more than one body at a time. The hack orientation vector you suggest will only have an apparent, superficial connection with the body's actual angular state. I am looking for an unambiguous, exact method that conserves energy and momentum like the method of keeping track of linear state mentioned in the OP. If I use your suggestion, I will either add or remove energy from the system when the bodies interact in a way that depends on angular state.

Share this post


Link to post
Share on other sites
"I am among other things using it for shape matching. I don't necessarily want to avoid a method based on a rest pose, I have already implemented this. It's just that I am almost completely sure it can be done without it. If a particle cloud's linear state, moment of inertia, angular momentum, velocity, and energy can be computed accurately from particle state, then so can the angle. I just haven't figured out how yet..."

 

I'm not an expert but I don't think that your conclusion necessarily follows.

It just doesn't make sense to me: particles only have a defined position, not an orientation. You can aggregate their positions to get a COM, which helps you define all the other properties you listed (eg angular momentum doesn't make sense for a particle in isolation, but does relative to the COM), but AFAICT the COM doesn't help define an orientation.

I'm struggling to see how you could define orientation without some sort of frame of reference similar to that provided by a rest pose.

Share this post


Link to post
Share on other sites

If you are looking to determine the inertia tensor of a rigid body object by summing up different masses/components, then there is a way. It is called the parallel axis theorem (I believe, It has been several years since I last looked into it) The idea is to find the inertia of a complex shape by breaking it down into simpler shapes with known properties (cubes, spheres, cones, etc) and then summing them up in a way analogous to summing up the different CoGs.

 A good book that covers it is the O'Reilly Phyisics for Game developers, specifically the flight simulator section.

Share this post


Link to post
Share on other sites

 

AFAICT this still requires some idea of a "rest pose"/starting configuration (the a_i unit vectors in the stackexchange reply). (Thanks so much btw, I hadn't realized there were approaches to this besides Muller's! Very interesting.)

The OP wanted to know if there are any approaches that *don't* require some sort of initial state/rest pose.

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