Polymender

Tao Ju

Introduction
PolyMender is based on the algorithm presented in my paper Robust Repair of Polygonal Models appeared in the Proceedings of SIGGRAPH 2004. The program reads in a polygonal model (i.e., a bag of polygons, such as figure 1 left) and produces a closed surface (such as figure 1 right) that approximates the original model. PolyMender consumes a small amount of time and memory space, and can accurately reproduce the sharp features in the original geometry. PolyMender is suitable for repairing CAD models and gigantic polygonal models. Alternatively, PolyMender can also be used to generate a signed volume from any polygonal models.


Figure 1

Algorithm
The algorithm generates a closed surface by computing and contouring an intermediate volumetric grid denoting the inside/outside space of the input model. Specifically, the algorithm works in three steps:


Figure 2

  • Scan-conversion: Embed the input model (figure 2 (a)) in a uniformly spaced grid, and mark edges on the grid that intersect the polygons as intersection edges. For efficiency, cells containing intersection edges are stored in an octree (figure 2 (b)).
  • Sign generation: At the grid points, generate signs that are consistent with the intersection edges, so that each cell edge intersecting the model should exhibit a sign change (figure 2 (c)).
  • Surface reconstruction: Reconstruct a closed surface on the signed grid by contouring. Dual contouring can be used to reproduce sharp features when Hermite data is stored on the intersection edges (figure 2 (d)).
Sign generation is the central step, which results in a partitioning of space that is essential to the construction of a closed surface. Our approach relies on the grid edges intersected with the input polygons, which can be robustly obtained for any type of model (even non-orientable surfaces). By adding or removing intersection edges at appropriate locations, we can always generate consistent signs at the grid points.


Figure 3

The addition or removal of intersection edges are guided by the Dual Surface, defined as the set of quads that are dual to the intersection edges. It can be shown that, consistent signs exist on the primal grid if and only if every edge on the dual surface is shared by even number of quads. The algorithm thus only needs to remove edges with odd valences on the dual surface, which can be done by a simple divide-and-conquer patching algorithm. In figure 3, the input model with an open top is shown in (a), and edges intersected with the model and the corresponding dual surface is shown in (b) (odd-valence edges are highlighted). The patched dual surface is shown in (c) with corresponding intersection edges, and the repaired model based on the consistent signs is displayed in (d).


Figure 4


Figure 5

The examples above demonstrate the algorithm on a mechanic model with hanging edges (figure 4) and a gigantic polygonal model created from range scans (figure 5) containing numerous holes. Using dual contouring, our method is able to reproduce sharp features in the original model (figure 4 (d)). The David model contains 56 million triangles and takes up over 1 Gigabyte of disk space. The model is repaired at octree depth 13 within an hour on a consumer level PC using less than 500 megabytes of memory.

Downloads
(Lastest Version: 1.7 Updated: May 20, 2011)
  • Windows/Linux(with "wine") executables package 32-bit, 64-bit (README included)
  • Some test models for PolyMender.
  • PDF version of the SIGGRAPH04 paper.
  • Source code (in C++): available for research purposes upon request.
Polymender reads .PLY (ASCII or Binary), .STL (Binary) or .ASC format, and writes in .PLY (Big-endian Binary) or .SOF/SOG (Signed Octree) format. If you want to use it for rasterization and obtaining a signed volume, follow these instructions.

Release Notes
Version 1.7:
  • Add an extra argument to allow controlled removal of disconnected components.
  • Bug fixed in generating manifold surfaces.
  • Add option to specify a bounding box.
Version 1.6:
  • Removes disconnected components.
  • Topologically manifold dual contouring.
  • Outputs signed octree with geometry.
Version 1.5:
  • Adds the option to remove disconnected surface components (i.e., islands or cavities), which maybe artifacts of the repair.
  • Modified Dual Contouring that generates meshes without non-manifold vertices.
  • Adds a new output format: signed octree with representative vertex per octree cell for geometry reconstruction.
Version 1.02:
  • Bugs in SOF format output are fixed.
Version 1.01:
  • A bug in the PLY output routine is fixed. In Version 1.00, the binary PLY files output by the program can not be parsed by some 3D viewers (e.g., Quick3D and Scanalyzer). The problem is fixed in Version 1.01, which has been tested in the following viewers: Deep Exploration, Quick3D, Plyview, Scanalyzer.

Special thanks
  • (4 Sep, 2007) Eric Voth points out a bug in generating manifold Dual Contouring meshes.
  • (1 Oct, 2004) Patrick Min points out that the executables of PolyMender runs fine under Linux with "wine" (a windows emulator) installed.
  • (8 Sep, 2004) Pendli found the bug in version 1.00 where binary PLY files are not accessible to some 3D viewers.

Comments or suggestions: taoju at wustl.edu