Reaction Diffusion Texture On Surfaces
Wen Su
(http://sourceforge.net/projects/rdtexture)

	This is project is for CS 497 Advanced Graphics Rendering and Appearance Modeling taught by Yizhou Yu in Spring 2003 at the University of Illinois at Urbana Champaign. The idea is based on the Greg Turk's SIGGRAPH 91 paper "Generating Textures on Arbitrary Surfaces Using Reaction-Diffusion". (http://www.gvu.gatech.edu/people/faculty/greg.turk/reaction_diffusion/reaction_diffusion.html)

Abstract:
	I spent more time on it because there are many interesting features mentioned in Turk's paper. It does not only contain reaction diffusion simulation, but also wildly used mesh operations.
	There are basically five steps to generating reaction diffusion texture on a mesh.
1.	Insert random points based the local area.
2.	Relax the point with repulsion so that the points are evenly distributed on the surface.
3.	Create an approximate Voronoi diagram from the points to simulate the cells.
4.	Use mutual tessellation between the cell centers and the original vertices to retile the surface, which is now ready to do the simulations.
5.	Apply several well-known reaction diffusion methods on the cells using the cell neighboring information from the mesh.

2003-03-12 09:37PM

Data structure:
	I used a well-written halfedge data structure called OpenMesh from the Computer Graphics & 
Multimedia Group. (http://openmesh.org/) This helps me maintain the mesh structure and speed up the local neighborhood search.
	The halfedge data structure use directed edges (halfedge) as the basic element. Each halfedge has a pointer to its face, from and to vertex, its next edge on its face, and the opposite halfedge pointing to the opposite direction. There are enough information to get traverse the entire mesh. There are four basic entities in the structure: faces, edges (a pair of opposite halfedges), halfedge, and vertices. OpenMesh allows users to create traits to store basic properties on each entity. This is useful in my application because I need to store the area of the face and the cell IDs in each face. This provide fast linear search algorithm for nearby cell points. For each halfedge, I store the axis and the angle between its two adjacent faces. This is used for rotation of points. Each vertex also has a cell Id, because at step 4, the center of the cells are created as vertices. There are also status bits, normals and other native attributes for each entity.
	For basic mesh traversal OpenMesh provides circulators to do constant time retrieval of neighbors. This is essential for a fast relaxation step. For example, given a vertex, you may traverse its outgoing halfedges, or its faces, etc. I have also written some helper function to find the one ring, two ring and n ring neighbor faces for the relaxation step. This is uses a status bit to mark visited neighbors.

	For the GUI, I used an free toolkit call Fox. (http://fox-toolkit.org/)
	I wrote a inherited class for displaying my mesh. The menu and the input box are a plug-in in the toolkit. I have also added the basic x-y plane and major axis as a class.

Implementation:
	First I started reading Turk's SigGraph 91 paper. As I get deeper into the problem, I found the paper does not give enough detail for implementation. For example, it does not say how to build the Voronoi diagram and retriangulation. I found most of the answers from Turk's dissertation. However, the dissertation covers much more topics that I could implement for this project. So here is what I picked some plausible implementation. I followed the mesh preparation steps closely. Turk suggested many way of putting the texture on the mesh, for example, for real time display, or for high quality rendering. I chose the first option.
	
Step 1: Inserting random points
	First find the area of each face. Find the total surface area of the mesh. Based on the ratio of the area of each face put a weight of what portion of the cells to place on this face. The cells is stored in a global vector. The cell IDs are stored in each face that it belongs to. To random insert a point into a triangle, assume we have a parallelogram. Then we can use two uniform random number generator for its x and y scape along two of its sides. If the point is outside the triangle, we project the point along the diagonal formed by the two base vectors.

Step 2: Relaxation
	Once these cells are randomly placed onto the faces, they are not evenly distributed. To relax these points, we use repulsion between nearby cells. Since we are doing this on the surface, the repulsion force can push other cells off the surface, we want to prevent this. First using the mesh connectivity to find nearby faces. Then rotated these the cells around the edge that its face shares with the current face. This calculate the geodesic distance between cells. The rotation matrix is precomputed for efficiency since we need to do this rotation many times. For points outside of the one ring neighborhood, there is no easy way to find the geodesic distance. I used a projection from the points to the plane of the current face. Once the force for each cell is calculated, I apply them as displacements. This may cause cells to be pushed off its face. I find the intersection of the displacement and the edges of its face. Then apply rotation to the displacement that is left. I also update the face that the cell is not belonged to. Repeat this step until the force is within a tolerance. There are machine number instability in this, could cause a cell may lie on both faces or either. I solved this by pull the point toward the center of the face if it happens. The results is promising. The speed is quite fast compared to the particle repulsion in Witkin-Heckbert floater particle repulsion. This algorithm is linear time because it only consider a small local neighborhood.

Step 3: Create Voronoi diagram
	Turk stated this problem is hard because the cell centers are not on a plane. So even if we project the points like in the relaxation step, there will be errors and the cell boundaries from two cell centers will not meet. Therefore, Turk used an approximation method, and he does not retessellate the mesh with these Voronoi diagram in the next step. I used my own approximation methods for simplicity. I just find the closest six neighbors. Then approximate the edge length of the two faces based on one over the squared distance. This edge is then weighed to guarantee the sum of the edge length is one. The edge length between cells determine how much chemical is transferred between cells.

Step 4: Retesselation
	Turk gives two options for this step. Both are approximation of the Voronoi diagram. The choice Turk uses is to delete the mesh's original vertices. This gives a better approximation of the Voronoi cells, because the original vertices were not considered as cells from the start. This is because we assume the original mesh does not have to have similar face sizes. If the mesh has dense vertices at high detailed areas, that means the cells for the simulation may be biased with small cells at those area. This usually is not desired because the spots should be fairly even over the entire mesh. However, this option changes the original geometry. I implemented this, deleting the original vertices were easy. However, reconnect the manifold with hole is not trivial, because when we added the new cells as vertices, this cause the original vertices have a very high valence. Usually these holes have a star shape. I ameliorate the problem by doing edge flips for edges connecting the original vertices, this is always possible. This is simulate to barycentric subdivision step, where you insert a new vertices at the centroid of a face and flip edges to prevent long skinny faces. However, the picking of possible shortest edge to add is not easy. I have not find a good way to prevent illegal faces when I find new possible edges. Because of the time constraint, I started to do the second option.
	The second option requires no extra work. It only involves inserting the cell centers and do a face split. However, this does not give good simulation results because not all faces correspond to a cell. I had to do interpolation for each non cell faces.

Step 5: Simulation
	There are systems given in Turk's page for two dimensional reaction diffusion. He has a demo system called Cascade. There is not much difference between that and the surface setting. The only part that changes is when calculating the Laplacian, you use the Voronoi neighbors calculated in step 3. And use the edge length to scale how much diffusion occurs. I have used the Turing spots and the Meinhardt spots. I followed the Cascade idea of using two step simulation to get small and large spots. I had trouble finding the right parameters to produce interesting pictures. I have only one good picture showing the diffusion is occurring. Other pictures shows interesting coloring of the models, but does not seems to following the diffusion patterns mentioned in the paper.

Conclusion:
	This paper is more than about rendering and textures. There are many valuable methods for mesh operation. The repulsion on surface are used in many methods. It is a good way of retile a mesh, this has many applications.
	A possible improvement and an idea that could solve my problem of slow simulation rate is to build hierarchical mesh. Then we can apply the multigrid method in two dimension into a surface setting.
	This is a valuable experience for me. I have better understand the halfedge data structure, and more appreciation for the design of the OpenMesh library. I also found that there are many tricks doing seemly basic operation of rotation, projection, in face test when it is applied in a surface setting.
	There are some lessons to be learned from this project. I needed better planning for the project as a whole. Trying to implement an entire dissertation is not possible. Some seemly easy part took a long time to debug for example, the relaxation step is much more involved than I have expected. This took me an entire week, which prevent me to have longer test time for the simulation step.
	
2003-03-20 08:29PM