particle simulation using fast multiple method

[happyjack27]

i'm tempted to just apply a xtheta matrix ala sin and cosine, followed by a ytheta matrix. simple and effective. but i'm curiuos how much the order matters...they'd be dragging their mouse to rotate on x and y simultationsly.

You shouldn't think of it as sequential rotations. Infinitesimal rotations commute, finite rotations do not. One display-update cycle is as "infinitesimal" as your code can get. You should think of it as rotation about some axis contained in the x-y plane of the screen, passing through the projected (onto the 2-D screen) center of your particle cloud.

so i could take xtheta and ytheta, and convert that into an axis (y = -xtheta/ytheta) and a magnitude (theta = sqrt(xtheta*xtheta+ytheta*ytheta), and then just rotate about that axis. and that would give me smooth rotation.

so: http://en.wikipedia.org/wiki/Rotation_m ... _and_angle

problem solved!
thanks for your help!

[DeltaV]

It's been a decade since I wrote that code... my memory of it is fuzzy.

First, I was using OpenGL with hardware acceleration. Good interactivity for up to about a million triangles, on that era's hardware.

I allowed mouse control of rotation, pan and zoom. Integrating those three with mouse-motion scale factors and some empirical functions to get a smooth, 'natural' motion was the time-consuming part (after the OpenGL basics had been worked out).

The mouse rotated the observer position vector, not the millions of data points.

So, I think you are on the right track. Treat the hypotenuse length of the x and y mouse-motion triangle as your commanded rotation angle for the update cycle, scaled as needed. Your rotation axis for that update is on a line perpendicular to the hypotenuse (right-hand rule, non-thumbs in direction of theta increase along hypotenuse).

In 3-D, you assume the axis lies in a plane perpendicular to the observer position vector and passes through the center of rotation. Then use the similarity transform above after defining a 3-D axis unit vector.

I don't remember the details of how I handled the interplay of panning and the apparent rotation center.

[happyjack27]

Note sure if i have this transposed, i suppose we shall see. I probably do.

Code: Select all

float ux = 1;
float uy = -thetax/thetay;
float uz = 0;
float theta = Math.sqrt(thetax*thetax+thetay*thetay);
float ct = Math.cos(theta);
float st = Math.sin(theta);
ux /= theta;
uy /= theta;

float[] xv = new float[]{
  (ux*ux*(1-ct)+ 1*ct),
  (ux*uy*(1-ct)-uz*st),
  (ux*uz*(1-ct)+uy*st),
};
float[] yv = new float[]{
  (uy*ux*(1-ct)+uz*st),
  (uy*uy*(1-ct)+ 1*ct),
  (uy*uz*(1-ct)-ux*st),
};
float[] zv = new float[]{
  (uz*ux*(1-ct)-uy*st),
  (uz*uy*(1-ct)+ux*st),
  (uz*uz*(1-ct)+ 1*ct),
};

for( Particle p : particles) {
  float xt = p.x*xv[0] + p.y*xv[0] + p.z*xv[0];
  float yt = p.x*yv[0] + p.y*yv[0] + p.z*yv[0];
  float yt = p.x*zv[0] + p.y*zv[0] + p.z*zv[0];
}

panning aka translation there are basically 2 options:

1) translate, then rotate. - this means you're rotating the camera
2) rotate, then translate. - this means you're spinning the object in place

i suppose there's actually a third option - have 2 <s>translation</s> rotation vectors, 1 before and 1 after, and allow the user to choose which one they want to adjust. then you'd probably want to give them the option to reset either one to 0,0,0.

EDIT: i said 2 translation vectors. that should have been 2 rotation vectors.

[DeltaV]

Does your 3D graphics library allow changing the observer position vector? Just one transform vs. millions.
Are you using OpenGL?

[happyjack27]

I allowed mouse control of rotation, pan and zoom. Integrating those three with mouse-motion scale factors and some empirical functions to get a smooth, 'natural' motion was the time-consuming part (after the OpenGL basics had been worked out).

i can think of three methods for a natural motion:

1.) "easing":

Code: Select all

x += (target_x - x)*easing_factor

2.) "throwing":

Code: Select all

dx = x at mouse button release - x at 1 time unit before mouse button release

every time unit after mouse button release:
x += dx;
dx *= friction_factor;

3.) 1st-order lag compensation:

Code: Select all

x_predicted = x + (x at mouse button release - x at 1 time unit before mouse button release)*lag;

they can be combined. you'd probably want to put 1) after 3) if you're doing 3), otherwise it could seem jerky.

[happyjack27]

Does your 3D graphics library allow changing the observer position vector? Just one transform vs. millions.
Are you using OpenGL?

I'm not using a 3d graphics library. just doing the 3-d stuff myself. i just need to put this rotation code in place and then add depth sorting (i suppose i could just do a quicksort on the particles' final z, and then render back to front, but then there goes multi-threaded rendering...) and them i'm all set.

i'm using java. for hardware accellerated graphics i was thinking maybe jCuda. not sure what 3-d graphics libraries are out there for java. maybe there's an openGL one.

[happyjack27]

sure enough! http://en.wikipedia.org/wiki/Java_OpenGL

i'm working on the user interface now.
after that i'm going to do some testing.
then probably some tweaking.
then i can focus on porting the drawing code over to use opengl, and give the user the option to choose openGl or old code.

[happyjack27]

here's an interesting natural motion idea: force and friction:

Code: Select all

force = (target_x-x)*force_multiplier;

dx = friction_factor*(dx + force*sign(target_x-x));
x = x + dx;

would be kind of bouncy, though. maybe instead something like:

Code: Select all

if( mouse_button_down) {
  target_speed = (target_x-x)*speed_multiplier;
  dx = dx + speed_easing*[target_speed*sign(target_x-x)-dx];
} else {
  dx = dx + speed_easing*[0-dx];
}

x = x + dx;

fun ideas to try.

[DeltaV]

I was able to get very intuitive rotational response using scale factors determined by empirical functions. Don't remember what all the function inputs were. Zoom factor was one (less "gain" as you zoom in). If the mouse was moving at button release, the observer (camera) vector continued orbiting at a corresponding speed. Did not have a spin-damping option, but it was on the upgrade list. No lags or other transfer functions used. Now that I think about it, since I was rotating the observer, not the object(s), I reversed signs on the axis vector.

[happyjack27]

Roadmap:

*put this roadmap into the repository as "roadmap.txt"
*add ui instantiation of sliders, for in-situ control.
**add grouping of sliders into frames.
*add ui menu, for saving, loading, etc.
**add option to export more detailed json file, including stats.
*add basic rotation of object

------test & debug--------

*add rotation of camera - means have to rotate translations relative to camera before adding to translation vector.
*add instructions on how to build it and run it from a command line (basically, export a jar, then type "java -jar <jarname>")

------test, debug, tweak--------

*publish it on a web page, so people can use it online. -- first release candidate!
*add natural motion fun stuff like easing, throwing, etc.
*integrate opengl via java opengl aka jogl
**make opengl renderer via

------test, debug, tweak--------

*integrate opencl via java opencl aka jocl
**move what engine code i can to jocl (java open compute, for gpgpus)

------test, debug, tweak--------

*add networking functionality for compute clusters.
**add load-balancing amongst computers in cluster.

------test, debug, tweak--------

*i'm sure there'll be more, if i ever get this far...

[happyjack27]

ok, i have it displaying, panning, zooming, etc. (hold down the left button and use the scroll wheel to zoom on the z axis. zoom back on the z-axis for the sample.json file to see the points.)

but rotation's not working right, nor is scaling, and it's not redrawing continuously when you pan/rotate/whatever. only when you release the mouse button.

[happyjack27]

panning/rotating/etc is now smooth/continuos. (i'm using a frame rate of only 4 fps for testing)

i don' get why rotation and scaling is not working.

any help would be appreciated:

https://sourceforge.net/p/octreemethodf ... ngCPU.java

[happyjack27]

screenshot attached.

not the most exciting, but a sturdy foundation.

file options currently are: open, save, exit.

i fixed scaling - i just had to put it _after_ the parallex projection, because the parallax from scaling on the z axis canceled out the scaling on the x and y axis. and rotation actually works and always worked - it was just the parrallax at extreme closeup causing a fish-eye effect that make it look messed-up.

i think next thing i'm going to do is get the user interface part of the sliders up, and test particle sinks and sources.

by the way, i'm thinking i might be able to re-purpose the engine for a game.

[happyjack27]

* added rotation & translation menu. also means was able to test camera rotation, translatio, and object rotation together. works fine.
* some multi-threading fixes. i forgot java threads are one-time use, had to switch to an "ExecutorService". also collections were throwing concurrency exceptions, fixed that too.
* tested particle sources. worked perfect out-of-the-box, (except for the multi-threading issue, above) (the blue particles are the ones generated from the particle source)
* wasn't able to test sinks, because it doesn't look like the particle-particle interactions are working, that or they are too weak to be noticeable -- in any case the particles aren't moving or are moving too slowly to validate. i will have to add some debugging output to get a closer look.
* changed the zooming logic to zoom to the next zoom level if the last zoom improved the accuracy by over a certain threshold (currently 0.1%, for testing purposes), or the particle being interacted with is within the current box ("octet"). part of the beauty of this method is it mimics what really happens in the processor due to the fact that the data is ultimately finite-precision. e.g. when you add two floating point numbers, with a 10 bit mantissa, one of them 2^10 larger than the other one, the smaller number will have absolutely no effect on the result, since none of its digits reach the minimum level of significance. this is equivalent to setting the "threshold" to 2^(-10). So the "threshold" is essentially how many digits you particle positions and velocities will be accurate to; i.e. the precision.

[happyjack27]

it's alive!

particle interactions appear to be running smoothly now!

i had forgotten to assign new particles to processing threads.

then they were suddenly exploding. after observing for a while, i figured it was probably magnetic force. i checked and i had left my magnetic force multiplier at 1, instead of 1/c^2, so i set it to 1/c^2, and then viola! fluid particle motion with particle sources and sinks, etc!