tessellation

Tessellation is a library for 3d tessellation, e.g. it will create a set of triangles from any implicit function of volume. Tessellation implements Manifold Dual Contouring.

Examples

Create a unit sphere and tessellate it:

use nalgebra as na;
//!
struct UnitSphere {
  bbox : tessellation::BoundingBox<f64>
}
//!
impl UnitSphere {
  fn new() -> UnitSphere {
    UnitSphere {
      bbox: tessellation::BoundingBox::new(&na::Point3::new(-1., -1., -1.),
                                           &na::Point3::new( 1.,  1.,  1.)) }
  }
}

impl tessellation::ImplicitFunction<f64> for UnitSphere {
   fn bbox(&self) -> &tessellation::BoundingBox<f64> {
     &self.bbox
   }
  fn value(&self, p: &na::Point3<f64>) -> f64 {
    na::Vector3::new(p.x, p.y, p.z).norm() - 1.0
  }
  fn normal(&self, p: &na::Point3<f64>) -> na::Vector3<f64> {
    na::Vector3::new(p.x, p.y, p.z).normalize()
  }
}

let sphere = UnitSphere::new();
let mut mdc =  tessellation::ManifoldDualContouring::new(&sphere, 0.2, 0.1);
let triangles = mdc.tessellate().unwrap();

Algorithm

The implementation follows Manifold Dual Contouring in roughly these steps:

1. Sample value grid — The grid is not sampled densely. Instead the bounding box is recursively subdivided octree-style, starting at the next power-of-two size that covers the bbox. At each level the implicit function is evaluated at the 8 sub-cube corners. Because the function is required to satisfy |value| >= distance_to_surface, a sub-cube can be skipped entirely when |value| > diagonal_of_sub_cube — the surface cannot possibly pass through it. Only when a sub-cube cannot be skipped and has reached unit size (one grid cell) is the value stored. This means only the cells near the surface are sampled at full resolution; the rest of space is never visited.

2. Compact value grid — Drop all grid corners that have no sign-change neighbor. This reduces memory by ~10× while keeping all corners adjacent to the surface.

3. Generate edge grid — For each grid edge whose two endpoints have opposite signs, binary-search for the exact zero crossing and record the surface position and normal as a tangent plane.

4. Generate leaf vertices — For each grid cell that contains at least one active edge, create one leaf vertex and accumulate the tangent planes from all crossing edges into a Quadratic Error Function (QEF).

5. Build octree — Repeatedly subsample the leaf layer: connected vertices that map to the same parent cell are merged by summing their QEFs. This continues until the layer size stabilises. A manifold check (Euler characteristic + per-face edge-count) decides whether a group may be merged.

6. Solve QEFs top-down — Starting from the coarsest octree layer, solve each merged QEF to find the vertex position that minimises squared distance to all contributing tangent planes. If the error is below the threshold the coarse vertex is used; otherwise the algorithm recurses into the children.

7. Generate quads — For each active edge, look up the four dual cells that share it and connect their solved vertices into a quad (two triangles), forming the final mesh.

License

^{Licensed under either of Apache License, Version 2.0 or MIT license at your option.}
_{Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.}