Mesh Processing Library

Overview

This GitHub package contains a C++ library and several application programs that demonstrate mesh processing technologies published in research papers at ACM SIGGRAPH in 1992–1998:

• surface reconstruction (from unorganized, unoriented points)
• mesh optimization
• subdivision surface fitting
• mesh simplification
• progressive meshes (level-of-detail representation)
• geomorphs (smooth transitions across LOD meshes)
• view-dependent mesh refinement
• smooth terrain LOD
• progressive simplicial complexes

The source code follows modern C++11 style and is designed for cross-platform use.

Version history

2016-04-28 — initial release.

Requirements / dependencies

The source code can be compiled with Microsoft Visual Studio 2015 from the included solution (*.sln) and project (*.vcxproj) files, using either the Integrated Development Environment (IDE) or the msbuild command.

On Unix-based platforms (including Linux, Mac OS, and Cygwin), the code can also be compiled using gcc and clang compilers (and Visual Studio cl compiler) using Makefiles designed for GNU make.

Reading/writing of images and videos is enabled using several options. If available, image I/O can use libpng/libjpeg or Windows Imaging Component (WIC). Video I/O can use Windows Media Foundation (WMF). Across all platforms, if the command ffmpeg is present in the PATH, it is spawned in a piped subprocess for both image and video I/O.

On Mac OS X, it is necessary to install XQuartz for X11 support and ffmpeg for image/video I/O.

Code compilation

Compiling using the Microsoft Visual Studio IDE

Open the distrib.sln file and build the solution (typically using the "ReleaseMD - x64" build configuration). Executables are placed in the bin, bin/debug, bin/Win32, or bin/Win32/debug directory, depending on the build configuration (64-bit versus 32-bit, and release versus debug).

Compiling using msbuild

Set the appropriate environment variables and run msbuild, e.g.:

(Some alternatives are to set platform to Win32, or configuration to DebugMD, Release, or Debug; here MD stands for multithreaded DLL.) Executables are placed in the same target directory as in the IDE.

Compiling using GNU make

The CONFIG environment variable determines which make/Makefile_config_* definition file is loaded. On Windows, CONFIG can be chosen among {win, w32, cygwin, mingw, mingw32, clang}, defaulting to win if undefined. On Unix-derived platforms (including Linux and Mac OS), CONFIG=unix is the unique and default setting.

For example, to build using the Microsoft cl compiler (Debug, with 8 parallel processes, placing *.exe into directory bin/win):

To build all programs (into either bin/unix or bin/win) and run all unit tests:

To build on Unix, forcing the use of the gcc compiler (the alternative is clang):

To build just the main library using the mingw gcc compiler on Windows:

To build the Filtermesh program (into bin/clang) using the clang compiler on Windows:

To build all programs (into bin/cygwin) and run all demos using the gcc compiler under Cygwin:

To clean up all files in all configurations:

Note that additional options such as debug/release, 32-bit/64-bit, and compiler tool paths/parameters are set in the various make/Makefile_* files. These need to be adjusted depending on the versions and installation paths of the tools. For instance, the line "rel ?= 0" in make/Makefile_config_win specifies a debug (non-release) build, and "$(call prepend_PATH,...)" in make/Makefile_base_vc sets the compiler directory.

Publications and associated programs/demos

	Surface reconstruction from unorganized points. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle. ACM SIGGRAPH 1992 Proceedings, 71-78. Signed-distance field estimated from a set of unoriented noisy points. programs: Recon demos: create_recon_*.{sh,bat}, view_recon_*.{sh,bat}
	Mesh optimization. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle. ACM SIGGRAPH 1993 Proceedings, 19-26. Traversing the space of triangle meshes to optimize model fidelity and conciseness. programs: Meshfit demos: create_recon_*, view_recon_*, create_simplified_using_meshopt, view_simplified_using_meshopt
	Piecewise Smooth Surface Reconstruction. Hugues Hoppe, Tony DeRose, Tom Duchamp, Michael Halstead, Hubert Jin, John McDonald, Jean Schweitzer, Werner Stuetzle. ACM SIGGRAPH 1994 Proceedings, 295-302. Subdivision surfaces with sharp features, and their automatic creation by data fitting. programs: Subdivfit demos: create_recon_cactus, view_recon_cactus
	Progressive meshes. Hugues Hoppe. ACM SIGGRAPH 1996 Proceedings, 99-108. Efficient, lossless, continuous-resolution representation of surface triangulations. programs: MeshSimplify, reverselines, Filterprog demos: create_geomorphs, view_geomorphs
	Efficient implementation of progressive meshes. Hugues Hoppe. Computers & Graphics, 22(1), 1998, 27-36. Progressive mesh data structures compatible with GPU vertex buffers. programs: FilterPM, G3dOGL demos: create_pm_club, view_pm_club, determine_approximation_error
	View-dependent refinement of progressive meshes. Hugues Hoppe. ACM SIGGRAPH 1997 Proceedings, 189-198. Lossless multiresolution structure for incremental local refinement/coarsening. programs: FilterPM, G3dOGL demos: create_sr_office, view_sr_office
	Smooth view-dependent level-of-detail control and its application to terrain rendering. Hugues Hoppe. IEEE Visualization 1998 Conference, 35-42. Visually smooth adaptation of mesh refinement using cascaded temporal geomorphs. programs: StitchPM, G3dOGL demos: create_terrain_hierarchy, view_terrain_hierarchy, create_sr_terrain, view_sr_terrain, view_gcanyon_*
	Progressive simplicial complexes. Jovan Popovic, Hugues Hoppe. ACM SIGGRAPH 1997 Proceedings, 217-224. Progressive encoding of both topology and geometry. programs: G3dOGL demos: view_psc_drumset

Demos

After the code is compiled, the demos can be run as follows.

In Windows, create, view, and clean up all the results using the batch scripts

On Unix-based systems (e.g. Linux, Mac OS, Cygwin), either run the bash scripts

or alternatively (and faster), invoke make to create all results in parallel and then view them sequentially:

Note that pressing the Esc key closes any open program window.

Filter programs

All programs recognize the argument --help (or -?) to show their many options.

The programs Filterimage, Filtermesh, Filtervideo, FilterPM, and Filterframe are all designed to:

• read media from std::cin (or from files or procedures specified as initial arguments),
• perform operations specified by arguments, and
• write media to std::cout (unless -nooutput is specified).

For example, the command

• reads the specified image,
• rotates it 20 degrees counterclockwise (with the default reflection boundary rule),
• crops its left and right sides by 100 pixels,
• scales it uniformly to a horizontal resolution of 100 pixels using a 6×6 Lanczos filter,
• adds a 20-pixel blue border on all sides,
• creates an undefined (alpha=0) rectangular region in the image center,
• fills this region using gradient-domain smoothing,
• outputs some statistics on pixel colors (to std::cerr), and
• writes the result to a file under a different encoding.

As another example, the command

• reads a progressive mesh stream to construct a mesh with 1000 faces,
• reports statistics on the mesh geometry,
• remeshes the surface as the zero isocontour of its signed-distance function on a 60³ grid,
• reports the new mesh genus, and
• shows the result in an interactive viewer using the specified view parameters,
• simulating keypresses Dm to enable flat shading and De to make mesh edges visible.

The command

• reads a 2000-face mesh, marks all edges with dihedral angle greater than 35 degrees as sharp,
• applies two steps of adaptive subdivision near these sharp edges, and
• shows the result flat-shaded (Dm), with edges (De), without backface culling (Db), spinning (J) somewhat slowly (----),
• starting from the view parameters stored in the spheretext.s3d file.

The command

• reads the video (entirely into memory),
• uniformly scales the two spatial dimensions by a factor 1.5 using the Keys bicubic filter, and
• saves the new video.

The command

• reads the video (entirely into memory),
• reports statistics on the color channels,
• trims off 4 frames at the beginning,
• adds repeated copies of the last frames (with length 20% of the video),
• temporally scales the content by a factor of 1.5 and adjusts the framerate accordingly,
• spatially crops a centered rectangle with width 400 pixels and height 240 pixels,
• adjusts the color gamma,
• sets the output bitrate to 10 megabits/sec, and
• shows the result (- for std::cin) together with the original video in an interactive viewer,
• with keypress = to scale the window size by 2, a to loop all (two) videos, and n to initially select the next (second) video.

Surface reconstruction

Recon

This program reads a list of 3D (x, y, z) points assumed to be sampled near some unknown manifold surface, and reconstructs an approximating triangle mesh. For example,

• reads the text file of points,
• reconstructs a triangle mesh assuming a maximum sample spacing (δ+ρ in paper) of 2% of the bounding volume,
• reports the genus of this initial mesh,
• removes all connected components with fewer than 100 triangle faces,
• fills and triangulates any hole bounded by 30 or fewer mesh edges,
• reports the genus of the modified mesh,
• saves it to a file, and
• displays it interactively starting from a specified viewpoint, with flat-shaded faces (Dm) and mesh edges (De).

To show the progression of the Marching Cubes algorithm,

• selects the 'c' (cubes) output stream,
• forces a frame refresh every 30 polygon primitive, and
• shows the result without display-list caching (DC) and without backface culling (Db).

To show a similar streaming reconstruction of the surface mesh,

• selects the default 'm' (mesh) output stream,
• converts the mesh to a stream of polygons, and
• shows the points and streamed reconstruction with a slow (_) automatic rotation (J) about the object frame (o).

The same program can also read a list of 2D (y, z) points to reconstruct an approximating curve:

Meshfit

Given an initial mesh and a list of 3D points, this program optimizes both the mesh connectivity and geometry to improve the fit, i.e. minimizing the squared distances from the points to the surface. For example,

• reads the previously reconstructed mesh and the original list of points,
• applies an optimized sequence of perturbations to improve both the mesh connectivity and geometry,
• using a specified tradeoff between mesh conciseness and fidelity (c_rep=1e-4 yields a coarser mesh),
• saves the result to a file, and displays it interactively.

The input points can also be sampled from an existing surface, e.g.:

To view the real-time fitting optimization,

• writes both the initial mesh and the stream of mesh modifications, and
• displays the changing mesh asynchronously with display-list caching disabled (DC).

Polyfit

This related program performs a similar optimization of a 1D polyline (either open or closed) to fit a set of 2D points. For example,

• reads the previously reconstructed polyline and the original list of points,
• optimizes vertex positions and simplifies the number of line segments according to some representation cost, and
• displays the result together with the original points.

Subdivfit

In a subdivision surface representation, a coarse base mesh tagged with sharp edges defines a piecewise smooth surface as the limit of a subdivision process. Such a representation both improves geometric fidelity and leads to a more concise description.

• reads the previously optimized mesh and tags all edges with dihedral angle greater than 52 degrees as sharp,
• loads this tagged mesh and the original list of points,
• optimizes the mesh connectivity, geometry, and assignment of sharp edges to fit a subdivision surface to the points,
• with a representation cost of 1e-5 per vertex and .2e-5 per sharp edge, and
• saves the resulting optimized base mesh to a file. (The overall process takes a few minutes.)

To view the result,

• reads the base mesh together with a second mesh obtained by applying two iterations of subdivision,
• shows the first mesh (N) with flat-shaded faces and edges (DmDe),
• waits for 5 seconds, and displays the second mesh (N) as a smooth surface without edges.

MeshDistance

This program computes measures of differences between two meshes. It samples a dense set of points from a first mesh and computes the projections of each point onto the closest point on a second mesh.

• MeshDistance loads the earlier results of mesh reconstruction and mesh optimization,
• computes correspondences from points sampled on each mesh to the other mesh (in both directions), and
• reports differences in geometric distance, color, and surface normals, using both L² (rms) and L^∞ (max) norms.

Mesh simplification

Given a mesh, MeshSimplify applies a sequence of edge collapse operations to simplify it to a coarse base mesh while trying to best preserve the appearance of the original model. It supports many different simplification criteria, as well as face properties, edges tagged as sharp, and vertex and corner attributes (n_x,n_y,n_z normals, r,g,b colors, and u,v texture coordinates).

For example,

• reads the original mesh and randomly samples points over its surface,
• progressively simplifies it by examining point residual distances, while recording changes to a *.prog file, and
• writes the resulting base mesh.

The next step is to reverse the sequence of stored edge collapses, i.e. forming a progressive sequence of vertex splits:

We construct a concise progressive mesh by encoding the base mesh together with the sequence of vertex splits that exactly recover the original mesh:

The complete process from the original mesh to the progressive mesh is implemented by the script call

Given a progressive mesh, we can interactively traverse its continuous levels of detail:

• by dragging the left vertical slider using the left or right mouse button, and
• toggling mesh edges using the De key sequence.

We can also define geomorphs between discrete levels of detail, e.g.

• creates a geomorph between 2000 and 3300 faces, another between 3300 and 5000 faces, and similarly one more,
• shows these in a viewer with the level-of-detail slider enabled (S),
• selects all three geomorph meshes (P), enables mesh edges (De), selects the first mesh (N),
• records a video of 101 frames while moving the LOD slider, and
• shows the resulting video with mirror looping enabled (m).

This example displays a progressive mesh after truncating all detail below 300 faces and above 10000 faces:

As an example of simplifying meshes with appearance attributes,

• forms a planar grid mesh whose 200×200 vertices have colors sampled from a downsampled image,
• simplifies the mesh to 4000 faces while minimizing color differences,
• shows the result with mesh edges (De) and only ambient lighting.

Selective view-dependent mesh refinement

Within demos/create_sr_office, the script call

creates a progressive mesh in which the simplified vertices are constrained to lie at their original positions (-vsgeom). This enables selective refinement, demonstrated by

The mesh is adaptively refined within the view frustum, shown as the inset rectangle (key Do) or in the top view (key Dr). Drag the mouse buttons to rotate, pan, and dolly the object.

Terrain level-of-detail control

Within demos/create_sr_terrain.{sh,bat},

• converts an elevation image to a smoothed terrain grid mesh, and
• simplifies it to create a selectively refinable mesh.

Then, within demos/view_sr_terrain.sh,

• opens two synchronized side-by-side windows of the same texture mapped terrain,
• in which the first windows shows the temporal pops resulting from instantaneous mesh operations,
• whereas the second window shows the smooth appearance provided by runtime geomorphs (Dg).

For large terrain meshes, we form a hierarchical progressive mesh by partitioning the terrain mesh into tiles, simplifying each tile independently to form a progressive mesh, stitching the progressive meshes together 2-by-2, and recursively simplifying and merging at coarser pyramid levels.

An example is presented in demos/create_terrain_hierarchy. It makes use of

to assemble each 2-by-2 set of progressive mesh tiles terrain.level0.x{0,1}.y{0,1}.pm at the finest level.

The script demos/view_gcanyon_interactive launches an interactive flythrough over a Grand Canyon terrain model, using a progressive mesh precomputed from an original 4096×2048 height field.

Alternatively, demos/view_gcanyon_frames shows a real-time flythrough using a pre-recorded flight path, whereby keystroke commands embedded within the input stream automatically change viewing modes.

Topology simplification

The program MinCycles removes topological noise from a mesh by iteratively pinching off the smallest nonseparating cycle of edges until a specified criterion (cycle length, number of cycle edges, number of cycles, or mesh genus) is reached.

For example, within demos/create_topologically_simplified.{sh,bat},

• extracts a mesh of 200000 faces from a progressive mesh,
• closes 46 topological handles to reduce the mesh genus from 50 to 4,
• where the final remaining handle would require a nonseparating cycle of length greater than .10
• speeding up the process by identifying approximately shortest nonseparating cycles within a factor 1.2 of optimal, and
• shows the resulting closed edge cycles (tagged as sharp) in blue.

Geometry viewer

The G3dOGL program shows interactive rasterized renderings of 3D (and 2D) geometry, represented as

• streams of polygons/polylines/points (*.a3d format),
• triangle meshes including geomorphs (*.m),
• progressive meshes (*.pm),
• encoded selectively refinable meshes (*.srm),
• progressive simplicial complexes (*.psc), or
• simple *.ply files.

Please see the many examples presented earlier. The viewer can also read *.frame elements to position the viewer and the objects in world space. Elements of *.a3d, *.m, and *.frame streams can all be interleaved in a single input stream.

The viewer can take image snapshots (see demos/create_rendered_mechpart_image) and record videos (see demos/create_rendered_mechpart_video).

The mouse/keyboard UI controls include:

   Mouse movements:
   left mouse:          rotate
   middle mouse:        pan
   right mouse:         dolly
   shift-left:          pan
   shift-middle mouse:  roll
   shift-right mouse:   zoom
   (mouse movements are with respect to current object; see '0-9' below)
   
   Important key strokes:
   ? : print complete list of keys
   D?: print list of keys prefixed by 'D'
   De: toggle edges
   Ds: toggle shading of faces
   Db: toggle backface culling
   Dm: toggle Gouraud/flat shading
   DP: save current window as an image file
   DS: toggle show some sliders
   S : toggle show some other sliders
   j : jump to a default viewpoint
   J : automatically rotate object
   D/: edit viewpoint filename
   , : read the viewpoint
   . : save the viewpoint
   0-9: select object (0=eye_frame, 1=first object, 2=second object...)
   u : display/hide current object
   N : select next object
   P : select previous object
   -=: decrease/increase the magnitude of all movements
   f : toggle flying (usually with '0' eye selected)
  

To record a 6-second (360-frame) video of a rotating mesh and then view the resulting video:

The related program G3dVec shows wireframe hidden-line-removed renderings of *.a3d streams and *.m meshes. It can write vector-based Postscript figures (see demos/view_hidden_line_removed).

In both programs, the keys ? and D? show a list of available keyboard commands.

Image/video viewer

The VideoViewer program enables interactive viewing and simple editing of both images and videos. Again, the key ? shows a list of available keyboard commands. Press pageup/pagedown to quickly browse through the videos and/or images in a directory. Audio is not currently supported.

File formats

Mesh (*.m)

See the documentation at the end of libHh/GMesh.h

A mesh is a set of vertices and faces. These in turn also define edges and corners. Arbitrary string tuples can be associated with vertices, faces, edges, and corners. Examples of string tuples: {normal=(.1 .2 .3) rgb=(1 1 1) matid=5 material="string"}. See the several demos/data/*.m files for examples of the mesh format. Note that the indices of vertices and faces start at 1 instead of 0; in hindsight that was a poor choice.

Geometry stream (*.a3d, *.pts)

See the documentation at the end of libHh/A3dStream.h

The stream contains polygons, polylines, points, and control codes (like end-of-frame, end-of-input, change-of-object). Unlike in a mesh, these primitives do not share vertices. The stream can be either text or binary.

Frame stream (*.frame, *.s3d)

See the documentation at the end of libHh/FrameIO.h

This text or binary format encodes a 4×3 affine transformation (plus an object id and a scalar field-of-view zoom). It is used to record default viewing configurations, and sequences of frames for flythroughs. It usually represents the linear transform from object space (or eye space) to world space. The stream can be either text or binary.

Progressive mesh (*.pm)

This is a binary representation that consists of a coarse base mesh and a sequence of vertex split records.

Edge collapse / vertex split records (*.prog, *.rprog)

These are temporary text files containing verbose information for a sequence of edge collapse / vertex split records used by MeshSimplify / reverselines / Filterprog to create a progressive mesh.

Libraries

The library libHh contains the main reusable classes. All files include Hh.h which sets up a common cross-platform environment.

The libraries libHWin and libHWX define different implementations of a simple windowing interface (class HW), under Win32 and X Windows, respectively. Both implementations support OpenGL rendering.

Code details

The include file libHh/RangeOp.h defines many functions that act on ranges, which are containers or views for which begin() and end() are defined. For example, the function call hh::fill(ar, 1.f) assigns the value 1.f to all elements in the array named ar, and the function call hh::mean(matrix) computes the average value of all entries in the named matrix.

The debugging macro SHOW(expr) outputs expr = ... on std::cerr and also returns expr. It also accepts multiple arguments in which case it returns void. For example, SHOW(min(1, 2), "hello", 3*2) outputs the line min(1, 2)=1 hello 3*2=6. Note the special treatment of literal string values.

Unicode strings are stored using UTF-8 encoding into ordinary std::string variables. The functions hh::widen() and hh::narrow() convert to and from the std::wstring UTF-16 encodings used in Win32 system calls.

All files use end-of-line encodings based on Unix '\n' LF (rather than DOS '\r\n' CR+LF). All streams are opened in binary mode. This allows text and binary to coexist in the same file.

License

See the file ./license.txt.

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.