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.
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:
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.
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
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)).
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).
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)
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.
Windows/Linux(with "wine") executables package
test models for PolyMender.
PDF version of the SIGGRAPH04 paper.
Source code (in C++): available for research purposes upon request.
- Add an extra argument to allow controlled removal of disconnected components.
- Bug fixed in generating manifold surfaces.
- Add option to specify a bounding box.
- Removes disconnected components.
- Topologically manifold dual contouring.
- Outputs signed octree with geometry.
- 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.
Bugs in SOF format output are fixed.
A bug in the PLY output routine is fixed. In Version 1.00, the binary PLY files output by the
program can not
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.
- (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