EMBER: Exact Mesh Booleans via Efficient & Robust Local Arrangements

Philip Trettner, Julius Nehring-Wirxel, Leif Kobbelt

Boolean operators are an essential tool in a wide range of geometry processing and CAD/CAM tasks. We present a novel method, EMBER, to compute Boolean operations on polygon meshes which is exact, reliable, and highly performant at the same time. Exactness is guaranteed by using a plane-based representation for the input meshes along with recently introduced homogeneous integer coordinates. Reliability and robustness emerge from a formulation of the algorithm via generalized winding numbers and mesh arrangements. High performance is achieved by avoiding the (pre-)construction of a global acceleration structure. Instead, our algorithm performs an adaptive recursive subdivision of the scene’s bounding box while generating and tracking all required data on the fly. By leveraging a number of early-out termination criteria, we can avoid the generation and inspection of regions that do not contribute to the output. With a careful implementation and a work-stealing multi-threading architecture, we are able to compute Boolean operations between meshes with millions of triangles at interactive rates. We run an extensive evaluation on the Thingi10K dataset to demonstrate that our method outperforms state-of-the-art algorithms, even inexact ones like QuickCSG, by orders of magnitude.

If you are interested in a binary implementation including various additional features, please contact the authors.

Contact: trettner@shapedcode.com
» Show Videos

Scan2FEM: From Point Clouds to Structured 3D Models Suitable for Simulation

Zain Selman, Juan Musto, Leif Kobbelt
EUROGRAPHICS Workshop on Graphics and Cultural Heritage

Preservation of cultural heritage is important to prevent singular objects or sites of cultural importance to decay. One aspect of preservation is the creation of a digital twin. In case of a catastrophic event, this twin can be used to support repairs or reconstruction, in order to stay faithful to the original object or site. Certain activities in prolongation of such an objects lifetime may involve adding or replacing structural support elements to prevent a collapse. We propose an automatic method that is capable of transforming a point cloud into a geometric representation that is suitable for structural analysis. We robustly find cuboids and their connections in a point cloud to approximate the wooden beam structure contained inside. We export the necessary information to perform structural analysis, on the example of the timber attic of the UNESCO World Heritage Aachen Cathedral. We provide evaluation of the resulting cuboids’ quality and show how a user can interactively refine the cuboids in order to improve the approximated model, and consequently the simulation results.

» Show BibTeX

@inproceedings {10.2312:gch.20221215,
booktitle = {Eurographics Workshop on Graphics and Cultural Heritage},
editor = {Ponchio, Federico and Pintus, Ruggero},
title = {{Scan2FEM: From Point Clouds to Structured 3D Models Suitable for Simulation}},
author = {Selman, Zain and Musto, Juan and Kobbelt, Leif},
year = {2022},
publisher = {The Eurographics Association},
ISSN = {2312-6124},
ISBN = {978-3-03868-178-6},
DOI = {10.2312/gch.20221215}

TinyAD: Automatic Differentiation in Geometry Processing Made Simple

Patrick Schmidt, Janis Born, David Bommes, Marcel Campen, Leif Kobbelt
Eurographics Symposium on Geometry Processing 2022

Non-linear optimization is essential to many areas of geometry processing research. However, when experimenting with different problem formulations or when prototyping new algorithms, a major practical obstacle is the need to figure out derivatives of objective functions, especially when second-order derivatives are required. Deriving and manually implementing gradients and Hessians is both time-consuming and error-prone. Automatic differentiation techniques address this problem, but can introduce a diverse set of obstacles themselves, e.g. limiting the set of supported language features, imposing restrictions on a program's control flow, incurring a significant run time overhead, or making it hard to exploit sparsity patterns common in geometry processing. We show that for many geometric problems, in particular on meshes, the simplest form of forward-mode automatic differentiation is not only the most flexible, but also actually the most efficient choice. We introduce TinyAD: a lightweight C++ library that automatically computes gradients and Hessians, in particular of sparse problems, by differentiating small (tiny) sub-problems. Its simplicity enables easy integration; no restrictions on, e.g., looping and branching are imposed. TinyAD provides the basic ingredients to quickly implement first and second order Newton-style solvers, allowing for flexible adjustment of both problem formulations and solver details. By showcasing compact implementations of methods from parametrization, deformation, and direction field design, we demonstrate how TinyAD lowers the barrier to exploring non-linear optimization techniques. This enables not only fast prototyping of new research ideas, but also improves replicability of existing algorithms in geometry processing. TinyAD is available to the community as an open source library.

» Show Videos
» Show BibTeX

title={{TinyAD}: Automatic Differentiation in Geometry Processing Made Simple},
author={Schmidt, Patrick and Born, Janis and Bommes, David and Campen, Marcel and Kobbelt, Leif},
journal={Computer Graphics Forum},

Pseudodynamic analysis of heart tube formation in the mouse reveals strong regional variability and early left–right asymmetry

Isaac Esteban, Patrick Schmidt, Audrey Desgrange, Morena Raiola, Susana Temiño, Sigolène Meilhac, Leif Kobbelt, Miguel Torres
Nature Cardiovascular Research

Understanding organ morphogenesis requires a precise geometrical description of the tissues involved in the process. The high morphological variability in mammalian embryos hinders the quantitative analysis of organogenesis. In particular, the study of early heart development in mammals remains a challenging problem due to imaging limitations and complexity. Here, we provide a complete morphological description of mammalian heart tube formation based on detailed imaging of a temporally dense collection of mouse embryonic hearts. We develop strategies for morphometric staging and quantification of local morphological variations between specimens. We identify hot spots of regionalized variability and identify Nodal-controlled left–right asymmetry of the inflow tracts as the earliest signs of organ left–right asymmetry in the mammalian embryo. Finally, we generate a three-dimensional+t digital model that allows co-representation of data from different sources and provides a framework for the computer modeling of heart tube formation.

» Show Videos
» Show BibTeX

author = {Esteban, Isaac and Schmidt, Patrick and Desgrange, Audrey and Raiola, Morena and Temi{\~n}o, Susana and Meilhac, Sigol\`{e}ne M. and Kobbelt, Leif and Torres, Miguel},
title = {Pseudo-dynamic analysis of heart tube formation in the mouse reveals strong regional variability and early left-right asymmetry},
year = {2022},
journal = {Nature Cardiovascular Research},
volume = 1,
number = 5

Interactive Segmentation of Textured Point Clouds

Patric Schmitz, Sebastian Suder, Kersten Schuster, Leif Kobbelt
International Symposium on Vision, Modeling, and Visualization 2022

We present a method for the interactive segmentation of textured 3D point clouds. The problem is formulated as a minimum graph cut on a k-nearest neighbor graph and leverages the rich information contained in high-resolution photographs as the discriminative feature. We demonstrate that the achievable segmentation accuracy is significantly improved compared to using an average color per point as in prior work. The method is designed to work efficiently on large datasets and yields results at interactive rates. This way, an interactive workflow can be realized in an immersive virtual environment, which supports the segmentation task by improved depth perception and the use of tracked 3D input devices. Our method enables to create high-quality segmentations of textured point clouds fast and conveniently.

» Show Videos
» Show BibTeX

@inproceedings {10.2312:vmv.20221200,
booktitle = {Vision, Modeling, and Visualization},
editor = {Bender, Jan and Botsch, Mario and Keim, Daniel A.},
title = {{Interactive Segmentation of Textured Point Clouds}},
author = {Schmitz, Patric and Suder, Sebastian and Schuster, Kersten and Kobbelt, Leif},
year = {2022},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-189-2},
DOI = {10.2312/vmv.20221200}

Automatic region-growing system for the segmentation of large point clouds

Florent Poux, Christian Mattes, Zain Selman, Leif Kobbelt
Automation in Construction

This article describes a complete unsupervised system for the segmentation of massive 3D point clouds. Our system bridges the missing components that permit to go from 99% automation to 100% automation for the construction industry. It scales up to billions of 3D points and targets a generic low-level grouping of planar regions usable by a wide range of applications. Furthermore, we introduce a hierarchical multi-level segment definition to cope with potential variations in high-level object definitions. The approach first leverages planar predominance in scenes through a normal-based region growing. Then, for usability and simplicity, we designed an automatic heuristic to determine without user supervision three RANSAC-inspired parameters. These are the distance threshold for the region growing, the threshold for the minimum number of points needed to form a valid planar region, and the decision criterion for adding points to a region. Our experiments are conducted on 3D scans of complex buildings to test the robustness of the “one-click” method in varying scenarios. Labelled and instantiated point clouds from different sensors and platforms (depth sensor, terrestrial laser scanner, hand-held laser scanner, mobile mapping system), in different environments (indoor, outdoor, buildings) and with different objects of interests (AEC-related, BIM-related, navigation-related) are provided as a new extensive test-bench. The current implementation processes ten million points per minutes on a single thread CPU configuration. Moreover, the resulting segments are tested for the high-level task of semantic segmentation over 14 classes, to achieve an F1-score of 90+ averaged over all datasets while reducing the training phase to a fraction of state of the art point-based deep learning methods. We provide this baseline along with six new open-access datasets with 300+ million hand-labelled and instantiated 3D points at: https://www.graphics.rwth-aachen.de/project/ 45/.

» Show BibTeX

title = {Automatic region-growing system for the segmentation of large point clouds},
journal = {Automation in Construction},
volume = {138},
pages = {104250},
year = {2022},
issn = {0926-5805},
doi = {https://doi.org/10.1016/j.autcon.2022.104250},
url = {https://www.sciencedirect.com/science/article/pii/S0926580522001236},
author = {F. Poux and C. Mattes and Z. Selman and L. Kobbelt},
keywords = {3D point cloud, Segmentation, Region-growing, RANSAC, Unsupervised clustering}

Previous Year (2021)
Disclaimer Home Visual Computing institute RWTH Aachen University