2D FEA “Goo” Comments

I have ceased work on the 2D finite element system using the grid-based optimized searching. My last work has been with generating springs between close elements so they “stick” to one another (and can also break apart). This required a pretty nifty spring management system (they are created and deleted on-the-fly cleaning themselves up). I again achieve real-time performance (although it drops below 60 fps if more points are added). The following images are from a simulation (thanks to ImageShack.us for the hosting) in order. Blue dots are elements, green lines springs.

At first a grid is generated which begins to fall. Because the grid is perfectly aligned, the points will not move along the x-axis unless nudged, so I sent a free element flying into the base of the “mass”.

It begins to settle, though the original top corners can still be made out as it deforms to fill the simulation area.

All signs of an original shape are gone, and the simulation has reached a low energy state where there is little to no movement.

To make sure to demonstrate the re-attachment ability, I add a some elements to the center of the “mass” with an initial positive y velocity, sending pieces everywhere.

Finally, the simulation reaches a low energy state again after being mixed up.

For any practical application, this would have to run with orders of magnitude more elements and in 3D. I began work on a 3D version, however it ran far too slow using the FPU to do anything reasonable in real-time and SSE optimizations were causing alignment errors. Given SSE and multi-threading, a theoretical 16x performance may be achieved, however I am ending this as this was only done to prove the grid-based method, which it has done with flying colors. The spacial sorting system remains an efficient way for distance-from-point lookups in n-dimensions with the grid size limitation. Other methods such as KD-tree and OCT-tree are most likely able to achieve greater performance and do so without the grid size limitation.

Particle Collision Optimization

This is just something that I had in the back of my head. I assumed it would speed things up and, well, it definitely did.

The problem is a bunch of particles which are supposed to repel only at a close distance, usually for something like fluid approximation, maybe just basic physics, I don’t know. I just wanted to do it. Anyway, it was all I did today (given my wonderful strep throat), and the results are promising:

The red line is is the number of frames per second (peaks at 175, after first five seconds only drops down to 109) and the blue line is the number of particles in the system. The method used is done by solving the new velocity of all particles (given any close interactions), repelling them, solving the new velocity at that position then going back to the original position and using an average of the two new accelerations/velocities, so this is with four system passes (now that I think about it, I could probably combine two…); however, this is not the purpose of it all.

If every point were checked with every other point, the number of distance checks would be N*N, or at 1,500 particles, 2.25 million. My system seems to only have to perform at most 8 per particle (though it could be anywhere from 0 to infinity). The system is divided into a grid and only adjacent grid blocks are tested for distance.

And finally, it working:

The blue dots are particles, the red blocks grid sections. The grid blocks get more red the more particles that are in them (I probably should have disabled grid rendering before benchmarking this… d’oh). Eventually the screen would fill and the ones that leave would be deleted (quite efficiently, I might add). As you can see, each particle testing only adjacent grid blocks probably averages… what, 6? Awesomeness, if you ask me. The grid size is also a parameter, including the grid location. The particle processing functions are callbacks. IE I set the first function, iterate the system, set the second function to move the particles, iterate, etc.

My only sadness comes from the fact that if the repel distance (AKA interaction distance) is greater that the size of one grid block, nothing outside the adjacent 9 cells will be considered. This might be useful for a RTS game engine. It is fast and makes it easy to find objects near one another (though it is limited).

This was done using a quad-core Q6600 CPU at 3.1 GHz, though because it is only single-threaded for now it utilizes 25% of that and the memory use peaked at no greater than 11mb. Double precision was used.

Oh man sneezing with strep throat sucks.

Mesh Optimization Pt. 1

I am going to test out two methods for optimizing complex mesh rendering.

Primarily, I am going to work on a method I have used in the past involving storing multiple polygon lists given the angle the model is viewed from. Essentially the model is stored as size separate versions: top, bottom, left, right, front, rear. If the camera is behind the object, the rear list is called et cetera. This is a crude methods but it is simple and from experience works somewhat well (75% of mesh rendered at a time using 4.5x the memory footprint). The effect is almost linear optimization (dot products are fixed CPU cost).

The second method has two branches. IE, optimization via polygon subtraction and addition with groups based on their dot product with stochastic vectors which are pre-processed and depending on how effective they are (IE how many polygons belong to them) possibly eliminated. Polygons belonging to no group will be added to a list which is rendered every time.

These methods assume the camera at no point enters the bounding volume, in this case AABB, of the object. If the camera does enter that close, a list containing all polygons will be called.

There is also possibility for SSE optimization.