Overview of algorithm

•  Input: Each file represents a 2D curve networks. The format is a simple format that represents topology, vertices, and border colors. A very simple input file describing a square would be:
2 4 4 - header (#colors, #verts, #segments)
1 0 0 - color (rgb)
0 0 1
0 0 -verts (x,y)
0 16
16 16
16 0
0 1 0 1 (vert#1,vert#1,left side color,right side color)
1 2 0 1
2 3 0 1
3 0 0 1
Here is a more complex input file of two section's of a mouse brain. mouse1 mouse2

•  Projection and Intersection: Project the 2D curve networks from each plane orthogonally onto a common plane. For the purpose of our application, each plane will be considered a top or bottom plane.

 

Projection of both planes is needed in order to compute the intersections. Each curve network is defined by its geometry and topology based on an input file. The topology of these planes consists of a list of edges. After the projection of the top and bottom planes, edge-edge intersections of the 2D curve networks are computed. New vertices at the intersection points are then added back into each of the planes. Doing this will allow polygons generated between the planes to share common vertices.

•  Loop Finding : Loops are closed, non-intersecting boundary cycles in the combined 2D curve network. Below shows two loops outlined in green. The algorithm is discussed in the paper.

•  Region Finding : Regions are then identified on the common plane by using a scan-line algorithm. Regions may be bounded by multiple loop cycles as shown below. Regions correspond to space between the two planes that project onto the region. Since each region contains an inside loop (counterclockwise orientation), there are inside loops + 1 regions. Regions are found from a simple algorithm.

• Color Finding + Triangulation: After finding each region, it is necessary to compute the top and bottom colors. Color finding is simply projecting each region onto the top and bottom planes and finding their respective color. After this is completed, triangulation is done with regions that have Different top and bottom colors. Shown is an example of the triangulation algorithm correctly handling regions with holes, and the correct triangulation for this example.

     

 

• Lifting + Laplace : For regions with different top and bottom plane colors, for every triangle T that exists in the Triangulation list, find corresponding vertex's and lift accordingly. As you can see above, the triangles have been split in order to create a middle vertex that will allow us to lift in 3d.

The Laplace formula is then applied and images (before and after Laplace) show the result.

 

Before Laplacian:

After Laplacian:

Please read the final paper for a more detailed process.