Home

Awesome

Boundingmesh

Contributors: Andre Gaschler, Quirin Fischer, Philipp Gergen

License: 2-clause BSD, a permissive license, see LICENSE file; see License for details of linked libraries. Several features require more restrictive licenses.

Boundingmesh is a library and tool set for generating bounding meshes and bounding convex decompositions. A bounding mesh encloses a given mesh and has fewer vertices; it is single-sided approximate mesh. A bounding convex decomposition is a set of convex hulls of few vertices that enclose a given mesh.

Table of Contents

Overview

Features

Bounding convex decomposition:

Publications

Feel free to cite our publications:

Contribute

Please verify your change builds and tests successfully by running the docker build:

docker build -f ubuntu18.Dockerfile .

Then, format syntax with clang-format -style=Google -i src/**/**.cpp src/**/**.h and create a pull request.

Screenshots

GUI

The GUI interface.

After some simplification.

Bounding Convex Decomposition

Original model: Original teapot model

Convex hull: Convex hull

Voxel set: Voxelized model

Bounding convex decomposition: Bounding convex decomposition

Example Models

Multiple example meshes can be found in the directory /examples/. Simplified output files are named with a suffix _decimated.

The model in /examples/bunny/ originates from The Stanford 3D Scanning Repository.

Usage

License

Boundingmesh itself is under the permissive 2-clause BSD license. However, it may use the following open source software libraries, which have other licenses: Eigen, EigenQP, Coin3D, Qt, SOLID, SoQt, CGAL. Please find their source code and licenses on their respective websites. By default, EigenQP is compiled into Boundingmesh and LGPL applies unless you deactivate the option USE_EIGENQUADPROG. For instance, if you compile convex decomposition, CGAL components are linked whose GPL license applies to the rest of the code.

Installation

Dependencies

We rely on the linear algebra library Eigen for most computations.
If you perform loading of .wrl files, you also need the Coin3D toolkit.
The included GUI application also requires QT4 and SoQT4.
The modules involving convex bodies rely on QHull and CGAL.

Building from Source

We provide a CMake build file. We recommend building by

mkdir Release
cd Release
cmake ..
make

Binaries

Windows binaries may be included in the releases.

Command-Line Tools

Bounding Mesh Simplification

Bounding meshes can be generated with a command-line executable. The interface is as follows:

./boundingmesh [options] FilenameIn [FilenameOut]

Bounding Convex Decomposition

Bounding convex decompositions can be generated with the following command-line executable:

./bounding-convex-decomposition [options] filename [filename_out.wrl]

GUI Application

The application providing the graphical user interface is built from the files located insrc/boundingmesh-gui/. The filenames of the binaries are respectively

./boundingmesh-gui

or boundingmesh-gui.exe

Building the boundingmesh software including the GUI requires the additional dependencies Coin3, QT4, and SoQT4 to be installed.

The GUI enables easy selection of the various decimation configurations. It shows the current mesh detail and allows interactive simplification. Contraction can be started for a single edge or batches of 100 or 5000 edges at a time. Furthermore, simplification down to a certain vertex count or error limit can be started.

Linux Build

Most build dependencies are available with the most common distributions. In Ubuntu, you can install them with the command

sudo apt-get install build-essentials cmake-curses-gui libcoin60-dev libeigen3-dev libqt4-dev libqt4-opengl-dev libsoqt4-dev libqhull6 libqhull-dev

Windows Build

For Windows, we recommend to find the required libraries on the Robotics Library Website. Boundingmesh requires a subset of the dependencies the Robotics Library requires, so the build instructions from there apply to large extent.

Static Library

Boundingmesh provides a static C++ library that can be used from other software.

We provide a central header:

#include <boundingmesh.h>

The build process will create the static library libboundingmesh.a to be linked against your program.

A minimal example that loads a mesh from an .off file, simplifies it until it has 1000 or less vertices, and saves the result:

#include <boundingmesh.h> 
int main(int argc, char** argv)
{
    boundingmesh::Mesh mesh;
    mesh.loadOff("mesh.off");
    boundingmesh::Decimator decimator;
    decimator.setDirection(boundingmesh::Outward);
    decimator.setTargetVertices(1000);
    decimator.setMesh(mesh);
    std::shared_ptr<boundingmesh::Mesh> result = decimator.compute();
    result->writeOff("mesh_simplified.off");
    return 0;
};

The following documentation describes the complete library and gives brief explanations of the provided functionality.

Code Guide

The following is a rough textual description of the control flow of the programs and algorithms. Hopefully it eases the familiarization with the codebase.

Data Structures

The primitives to represent 3D geometry are declared in boundingmesh/Primitives.h. Vertices, edges and triangles all store their local neighbourhood. Referencing is always done through Indices that are valid within the mesh.
For example, assume you want to iterate through the adjacent vertices of one vertex. This is done by iterating over the adjacent triangles (their indices) and retrieving the triangle data to get the vertex indices.
Meshes can be loaded from a few file formats, which all extract vertex and triangle data encoded in some way. The vertices are added to the Mesh object and connected to form triangles. Vertex insertion is done through a proxy class VertexPositionSet which unifies vertices with equal coordinates (by checking if a vertex with the same coordinates exists).
Removal of vertices, triangles... is deferred, marking the deleted objects until a call to Mesh::cleanAndRenumber() is made.

Mesh Decimation

Mesh decimation begins with the configuration of a Decimator. Besides setting parameters to select the error metric or the stopping criterion this also includes the selection of the mesh to process. This configuration prepares the decimation queue for the main algorithm by evaluating all edges of the mesh.
The core decimation algorithm is located in Decimator::compute() and just repeatedly picks the best modification.
The modification of the mesh is done in Decimator::executeEdgeContraction(). This method uses information about which parts have to be removed or reconnected collected in Decimator::collectRemovalData().
The scoring of contractions (and simultaneously the selection of inserted points) is done in Decimator::computeEdgeContraction() by minimizing cost functions. A cost function is represented by a matrix, which is computed in the MetricGenerator class depending on the settings.

Convex Decomposition

The convex decomposition algorithm starts by rasterizing the mesh into a voxel model or VoxelSet.
The voxel set is then repeatedly divided by collecting the voxels on the two sides of a plane into different subsets (methods SegmenterSimple::compute() and VoxelSubset::partition()). The resulting subsets of voxels are then used to generate convex bodies, by collecting the points of the mesh that produced the voxels (method VoxelSubset::calculateConvexHull()).

Documentation

The whole library is contained in the namespace boundingmesh. Add it to your program by including boundingmesh.h and linking against libboundingmesh.a.
The source code is written mostly conforming to the Google C++ Style Guide.

Command-line tool

####boundingmesh-bin/main.cpp

int main(int argc, char** argv)
Reads the given arguments and adds default arguments if needed. Then the used file formats are determined and the input file loaded. The mesh is simplified and finally the results are written to the specified file.

FileFormat getFileFormat(std::string filename)
Determines the file format by extracting and matching the file extension.

enum FileFormat
Representation of a parsed file format.

option::ArgStatus checkDirection(const option::Option& option, bool msg)
option::ArgStatus checkInt(const option::Option& option, bool msg)
option::ArgStatus checkFloat(const option::Option& option, bool msg)
Callback functions for the option parser.

Graphical User Interface

boundingmesh-gui/gui.h

class MainWindow

The main window of the application, implemented using Qt. Keeps all the stateful GUI fields and declares callback functions for active components.

class CustomLineEdit

Modified LineEdit that inserts a default value when empty.

boundingmesh-gui/ViewerMesh.h

class ViewerMesh

Converts the data of a boundingmesh::Mesh into a Coin scene graph for display.

Core Library

boundingmesh/boundingmesh.h

Main header file of the library. Collects the other top-level headers.

boundingmesh/Primitives.h

Definition of the geometric primitives used to construct meshes. The linear algebra library Eigen is used to represent mathematical objects and perform computations.

The geometric primitives provide no writing access to ensure the consistency of mesh data.

typedef ... Real
Representation of a real number.

typedef ... Vector3
A three dimensional vector.

typedef ... Vector4
A 4D-vector used for homogeneous coordinates.

typedef ... Matrix44
A 4x4 matrix.

typedef ... Index
An index referencing another geometric object. The type of the object and the underlying collection always depend on the context.

class Plane

Representation of a plane in 3D space.

class Vertex

A vertex of a mesh. Contains references to all neighbouring triangles and edges.

class Edge

An edge of a mesh. Contains references to it's endpoints and the triangles it is part of. The references to the endpoints are always stored ordered to satisfy vertex_1 < vertex_2.

class Triangle

A triangle of a mesh. Keeps references of it's vertices and edges. Also provides the plane containing the triangle in space.

boundingmesh/Mesh.h

class VertexPosition

Helper class to efficiently find indices of vertices that were added to the mesh.

class VertexPositionSet

Helper class to add vertices to a mesh by position. Efficiently finds the index if a vertex with the given position already exists.

class Mesh

A triangle mesh. Stores it's vertices, edges and triangles. Meshes can be changed by adding and removing vertices or triangles. Load/Save methods for some file formats are provided.

Construction
Getter
Modification

Removal methods keep the mesh consistent, removing all references to the deleted object and deleting empty objects (i.e. edges whose triangles were removed). Be careful when accessing the mesh data after removal as they leave the mesh in a dirty state.

Helper Methods (internal)

These methods are only used internally.

Static methods

boundingmesh/ContractionUtils.h

Data structures used in the edge contraction algorithm.

class EdgeContraction

Stores information for the contraction of an edge.

class ContractionIndex

Helper class to access contractions in the ContractionQueue by edge index.

class ContractionQueue

Container to efficiently add/remove contractions and retrieve the cheapest contraction.

boundingmesh/Decimator.h

Contains all functionality for mesh simplification through edge contraction.

class Decimator

Performs mesh simplification by edge decimation.

Setup/Configuration
Execution
Submethods (internal)
Decimation Computation (internal)

boundingmesh/MetricGenerator.h

enum Metric

List of available metric generation algorithms provided by the MetricGenerator. Currently we support the following algorithms:

class MetricGenerator

Produces quadratic error metrices for use by the Decimator. Allows selection of the desired metric.

Initialization
Interface to Decimator
General Internal Methods
ClassicQEM
ModifiedQEM
Merging Based Algorithms

boundingmesh/VoxelSet.h

enum Metric

List of possible voxel types.

class Voxel

Stores data for one voxel, currently position, type and triangles that created the voxel.

Creation
Getter Methods
class VoxelSet

A set of voxels, the equivalent of a mesh.

Creation
Getters
Others
Internal data structures

boundingmesh/SegmenterSimple.h

Classes for the segmentation of a model into disjoint parts, especially for convex decomposition.

class Split

A splitting plane, currently axis aligned and at a voxel boundary.

class AppliedSplit

Information attached to a set after splitting. Stores the splitting plane and the side of this part.

class VoxelSubset

A subset of a voxelized mesh. Keeps a list of the voxels part of this subset and information about the splits made. A subset generates one convex body.

Creation
Further partition
Getter
class SegmenterSimple
Configuration
Main algorithm
Results

####### Internal methods