CSE546T - Computational Geometry
Final Project
Goal: Partition a 3D mesh into equal regions using LLoyd's algorithm on Voronoi diagram.
Preprocessing: Randomly place centroids on mesh: O(n)
Step 1: Build Voronoi diagram:
Grow regions out from each centroid until it meets with another region.
Each vertex is entered into a priority queue keyed on its distances to the nearest centroid. This distance is calculated using Djikstra's algorithm on graph. The vertex with shortest distance to a centroid is assigned to the region with that centroid. Edge length can be set to either the actual edge length or 1 (which is equivalent to building Voronoi regions using edge number).
Runtime: Each vertex is added to and removed from queue only once: O(n)
Refine Voronoi diagram: If a region is cylinder-like, insert a new centroid nearby to break it into two new disk-like regions. Runtime: O(n)
Step 2: Relax Voronoi regions: Two approaches:
Approach 1: For each region, calculate the average point of all vertices in 3D and assign the closest vertex to be the new centroid. Runtime: O(n)
Approach 2: For each region, map it to a plane using Desbrun's natural parameterization. Then calculate the average point of all vertices in 2D and find the closest vertex a in 2D. Finally assign the correspondent vertex b in 3D to be the new centroid. Runtime: O(n^3)
Pseudocode with time complexity analysis
SeedCentroids() - O(n)
Randomly place k centroids on mesh
GrowRegions() - O(n^2)
While PQ (primary queue) is not empty
For each region
For each neighbor of each vertex on the boundary of the current region
If it is not assigned to a region
Calculate minimum distance to the region's centroid
If vertex is not in queue, enter into queue
Else compare and update vertex's key in PQ if necessary
EndIf
EndFor
EndFor
Remove the first vertex from PQ and assign to associated region
EndWhile
Each vertex is entered and remove from queue once, but might be updated upto n times
SplitRegions() - O(n^2)
For each region
Trace around the boundary until completing a loop
If there are unvisited vertices on the boundary
Divide boundary vertices into two groups
Calculate maximum shortest distance to each group and correspondent vertex
Add a new centroid at the midpoint between these two vertices
EndIf
EndFor
Each vertex is visited at most a constant number of times
Relax1() - O(n)
Calculate the average point of all vertices within each region in 3D
Find a vertex in this region that is closest to the average point
Assign it as the new centroid
Each vertex is visited at most a constant number of times
Relax2() - O(n^3)
Parameterize each region onto the plane using Desbrun's Natural Parameterization
This involves solving a linear system using LAPACK library, hence O(n^3)
Calculate the average point of all vertices within the region in 2D
Find a vertex in this 2D region that is closest to the average point
Assign the correspondent 3D vertex to be the new centroid
Total runtime O(n^3)
Implementation details
The project is written in C, the main class is implemented in ~1500 lines of code
Design issues:
How to find new centroid for each 3D region accurately
Growing regions on anisotropic mesh (varied edge length)
Challenge:
Debugging special cases is always a challenge
Data structure from Cindy's code database:
PMeshLite to store and perform calculations on mesh
Visualization routines from Cindy's code database:
MeshViewer
Initial results and conclusions
Growing regions using Geodesic distance with actual edge length gives better result
Relaxing using average points in 3D without parameterizing the regions yields better runtime and improves the partitions faster, but relaxing with parameterization step converges better, especially when regions are larger with higher curvature.
Initial regions
Approach 1 Approach 2
After 6 iterations