CSC-570Q
Final Project - Particle Fitter
Michal Fouquette

My final project reads in a triangle mesh from a .m file, determines the center points of each face, and then uses a particle system to fit particles to the mesh. Each particle is positioned along the normal of the face, and moves according to several forces: attraction to the face closest to it, repulsion from other particles within its "influence", and minor drag forces. Each particle also contains an "orientation" set initially to be the same as the face used to position the particle, and finally set to be the same as the normal of the face the particle ends up fitting.

The mesh faces are held in a uniform grid structure that can quickly return all faces contained in any one grid or set of grids, and can be set to any number of deepness levels. With each deepness level comes a performance gain (as particles compare themselves to a smaller number of faces) but sometimes an accuracy tradeoff can be noted as well. Particles only compare themselves to faces that are in nearby grids, and with a large enough deepness level particles can often find no "face neighbors," and so move only with a generic force towards the world center and repulsion forces (plus, of course, velocity left from previous forces).

The particle system currently uses a modified Euler's method that takes into account the second derivative when computing a new location for each particle. A particle is considered "fit" to the mesh when it has reached an distance with epsilon from the plane described by the closest face and the center of that face is within the influence of the particle, where epsilon is a programmed constant and the influence of a particle grows slowly with time. The particle influence continues to grow until another particle is contained in the sphere with radius influence.

Six meshes are provided and can be switched through, some are better approximated than others by the system. If desired, the particles can be randomly positioned about the mesh (with no help from mesh faces/normals) and the system will still fit the mesh, though often the number of particles that get "lost" is significantly higher. Also, while I had at first assumed more particles would result in a better approximation, the opposite tends to be the case: with more particles each face becomes approximated by several particles, which causes the influence of each one to be small. Since particles generally congregate near the center of a face, this results in many faces having very bad representations, especially the larger faces.

Surprisingly enough, meshes with a higher number of faces (and often higher curvature) are often approximated with more accuracy than low face-count meshes. This is because low face-count meshes tend to have larger triangles, resulting in either fewer particles used to fit the mesh (if normal positioning "cheating" is used) or more particles glomming together at the center of each large face (if random particle positioning is used).

Possible Extensions:
It should be fairly straight forward to convert the system to use some kind of hermite data or range data, though more preprocessing would be required. Additionally, the uniform grid could be expanded to keep track of not only the mesh faces but also the particle positions. This would allow for a faster particle neighbor check, and would also make checking for particle/face collisions faster.

Known Issues:
Automatic particle splitting causes the program to crash. I spent a significant amount of time trying to track down this bug but have been unable to find the cause. It only seems to occur when a significant number of particles need to be split at nearly the same time, and I have been unable to cause the bug to occur during manual splitting of particles.

Controls:
'1': draw particles and influence
'2': draw particle visualization
'3': draw particle orientation
'4': draw mesh
'5': draw mesh face centers
'6': draw mesh vertices
'7': draw mesh face normals
'8': draw the lowest level of the grid
'9': toggle automatic splitting (NOTE: often causes program to crash)
'0': toggle particle visualization between filled disks and neighbor triangulation
'z': restart fitting process
'x': switch to next mesh and restart fitting process
'm': change to random particle positioning mode
'.': select the next particle.
'/': split the selected particle.

Source:
download

Screens:

Fitting a baseball bat (shown with filled disks)

Same bat, but with the grid drawn.

Fitting a nuke mesh, with particles and influence drawn.

Fitting the same nuke, with neighbor triangulation drawn.

You can see here how even the sharp fins were captured.

Here the problems with neighbor triangulation are shown (fins are more pyramid shaped in fitting than in the mesh).