QuickCSG project page

QuickCSG is a generic multiple polyhedra CSG algorithm.

This page provides the binary executable, link to the source, and the exact experimental protocol and data used in the report QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids

QuickCSG was developed in the context of the Kinovis project.

QuickCSG source code

New! The source code for QuickCSG and compilation instructions are available on the following page: https://gitlab.inria.fr/quickcsg/quickcsg.
The code is available under the Free software license agreement for non-commercial purposes.

QuickCSG executable

QuickCSG is also available as command-line executables (v2.1) that don't require compilation: Older version: v1.

QuickCSG usage

The main command-line arguments are: the filenames of the input meshes, the name of the output (with -o) and the CSG operation to execute (like -union, -inter or -min2). Many other options exist, call with -h to list.

Mesh I/O is done in the simplistic OFF file format by default. It can be read/manipulated/converted by eg. Meshlab.

By default mesh_csg is not verbose. Logging is controlled via the -v option. Most often -v 1111111 gives a pretty good idea of what is going on. Verbosity can be increased for some stage by replacing one of the '1's with a higher number. Setting verbosity to the maximum can easily generate hundreds of megabytes of text.

This executable is limited to 63 input meshes (this is a compile-time option). By default the generalized polygons output by the algorithm are not tesselized: all vertex loops are returned as polygons in the OFF file, even when they correspond to holes. Most viewers will not display the OFF correctly (in fact it is an invalid OFF file). The -tess3 uses the GLU tesselizer to produce only triangles on ouput, and -tess produces convex polygons.

The facets of the ouput OFF file are colored according to the input mesh they came from. A useful option is -combined xxx.off that stores the input meshes in a single ouput file with the correct face colors and vertex/face indices that correspond to the ones listed in the logs.

Do not hesitate to give us feedback on the usage performance, bugs, etc. of QuickCSG. The exectuable is provided only for research and testing purposes. If you want to see the source, use it in products, etc. contact us. There is also a version of QuickCSG that supports self-intersecting meshes. Contact us if you are interested.

Degenerate cases and error handling

QuickCSG relies on the hypotheses on the input meshes (non-degeneracy and watertightness), and on their configuration (non-coincidence of the faces of different meshes). Simple meshes modeled by humans tend to have degenerate configurations (tangent faces, aligned edges, etc.). Also, many large meshes just happen to have local errors: missing triangles, small self-intersections, etc.

The approach in QuickCSG is to record the errors that are encountered during processing and report them, while still producing a possibly incomplete output mesh.

Most errors belong to the following classes:

The examples below sometimes include these random transformations.

Known bugs

Examples from the paper

We provide input meshes and mesh_csg command lines for most of the experiments in the paper, as well as some comments and images that did not fit in the paper. For most images, a larger version can be seen by opening it in a page of its own. Most images are snapshots of Meshlab. For some meshes we also provide a link for visualization with X3D-enabled browsers.

Note that the hierachy and OpenSCAD experiments rely on QuickCSG's Python wrapper. We do not provide this interface, so the corresponding experiments are not reproduced here.

Most complex meshes originally come from the The Stanford 3D Scanning Repository. When a lower resolution of a mesh was required for comparison with other experiments, we used Meshlab's "Quadric Edge Decimation" tool to reduce the facet count.

T1, T2, H

These are the main test cases of the paper. They were chosen to have many meshes that intersect very often, to stress the algorithm.

The corresponding OFF files are here: T1.tgz T2.tgz H.tgz

T1: a set of 50 random toruses. We compute difference between the union of the 25 first toruses with the union of the 25 next ones. This is a typical CSG case, where there are many intersecting facets, but the geometry is regular (small compact facets). Input and output for T1. Many intersecting facets are tesselated to triangles because they are non-convex:

T2: a set of 50 concentric narrow random toruses. The toruses follow the great circles on a sphere, so each torus intersects each other torus in two locations. We compute the volumes where at least 2 of the toruses are present. In this case, most facets intersect another. This generates many disconnected components with many more facets than there are on input. Input and output for T2 (see also the X3D version):

H: a set of 42 visual hulls (projected silhouettes of the object) of a piece of rope seen from 42 cameras. The facets are very elongated, and there are no primary vertices in the output mesh. By intersecting these silhouettes the object (a knot) is reconstructed. The data comes from the original EPVH paper and the original model from Surface reconstruction from unorganized points paper. Input and output for H:

The Max-script for 3DS Max that (attempts to) computes T1: compute_T1.ms. The input meshes should be convertes to .obj for it to work.

Examples from [Wang 2011]

The meshworks exectuable from the webpage runs on Windows. Here we reproduce some big experiments from the paper, see its Figure 17. The lion-vase mesh was sent via personal communication, thanks Charlie!

Note that both meshes produce errors. They are due to non-watertight input meshes.

Here are the input meshes: cmp_meshworks.tgz.

Dragon - Bunny input and output:

Buddha U lion example. Notice that there is a hole in the mesh.

Debugging the CSG error. a: The hole comes from a KD-tree node. Notice the tiny triangle(s) on the left of the green mesh. b: this is the parent node. The triangle comes from an extremity of the red mesh. (c) zoom on the extremity showing the normals. There is a degeneracy on this small detail, that was used to decide if the KD-tree node should be cancelled.

(a) (b) (c)

Examples from [Feito 2013]

We reproduced the experiments from the paper as best as we could. The dragon input mesh is the standard version from the Stanford repository. The armadillo is a version reduced to 150k triangles. Each one is transformed so that, between the original and transformed versions, "The overlapping between meshes has been maximized, in order to achieve a high number of triangle intersections. " We attempted to reproduce this behaviour in our tests.

Input data: feito2013_input.tgz

Armadillo results

Union, diff, and closeup on diff where non-primary faces are painted in blue:

We did not attempt to exactly reproduce the transformation used in the original paper.

Results for the dragon example

The original model contains many small holes, that are cause errors in the reconstruction. However, the reconstruction result still looks ok.

Result for intersection:

Result for difference, and leaves of the KD-tree (reddish = suppressed nodes, cyan = copied without processing, yellow = where QuickCSG searched for double and triple vertices)

Other viewpoint (result, kdtree, only yellow nodes of kdtree):

Examples from [Pavic 2010]

The examples were sent to us via personal communication. Thank you Marcel!

Sprocket

The data is available here: sprocket.tgz.

Input and output:

X3D view

Organic

This is a 6-mesh dataset where 3 boxes are subtracted from 3 meshes (a dragon, a bunny and a head), and the cropped meshes are merged into one result. The meshes are available here: organic.tgz.

The input data was put together with the help of Marcel Campen. Thanks Marcel!

Inputs (without the cropping boxes, that would clutter the image):

Output + close-up that shows the intersecting area between the ears and the head. There is no additional geometry due to tesselization (QuickCSG only tesselizes non-convex output polygons):

X3D view

EPVH

Like the example H, kino68 is a visual hull-based reconstruction. However, in this case, it is possible to reconstuct the result more efficiently by not creating and processing the basis of the cones, so we start at a root node that contains cropped polygons. Note that the examples below are computed on 60 out of the 68 available silhouettes because the executable supports a limited nb of inputs.

Data: epvh_input.tgz

Root kdtree node:

kdtree node somewhere in the middle of the reconstruction:

Collision detection

Data: octopus_input.tgz

2 octopuses and 4 rings.

Extreme CSG

Here we are pushing the limits of what can be done with CSG operations.

Real-time CSG

Video capture of a real-time CSG application, where a 3 series of boxes are used as input for several CSG operations:

.

Same idea: 3 bumpy spheres rotate indpendently:

.

The 6 Buddhas

It combines six instances of the "Happy Buddha" the largest mesh from the Stanford repository. We intersect these with the union of 100,000 random spheres. The spheres were labeled with a greedy graph coloring algorithm to group them into 37 disjoint subsets, so there are a total of 43 input meshes.

The models are here: huge.tgz (206 MB)

One of the input meshes that contains many spheres, output mesh and closeup on output:

Serpent

The models are here: serpent.tgz (273 MB)

Dithering

The models are here: dither.tgz (16 MB)

Dark star

This example is built by subtracting random spheres from a large one until there is a hollow path between the two sides of the large sphere. We generate an animation by following the path with a camera and a light source.

Blender source file dark_star.blend.gz.

Generated videos (seems to be readable only in Google Chrome):

Additional material

Here we reproduce a few images and some details that did not fit in the paper.

Viewing the KD-tree

On a simple example, it is possible to visualize the kdtree. We compute operation Pf = P1 \ (P2 U P3) applied to three simple meshes (f.l.t.r: input, kdtree, output):

On the graph below, each box represents a node, whose width is proportional to its number of polygons. When space allows, text in the box indicates node's indicator vector and the number of polygons. Color code: ■ = node that was split, ■ = leaf where vertices were found with CSGVertices, ■ = facets were just copied to the output, ■ = nodewas found completely inside or outside the mesh. Each dashed box represents a parallel task.

Finding the orientation of a kdtree node

This document complements Section 6.3 of the paper, by giving some details of how the polyhedron's orientation w.r.t one direction can be computed in a single pass over its faces:

orienting_split.pdf

Authors, copyright, contact

mesh_csg is copyright (c) INRIA 2013-2015. It was written by Matthijs Douze.

Comments, inquiries and even bug reports are welcome to jean-sebastien.franco@inria.fr (jean dash sebastien dot franco at inria dot fr).