Shape modeling is extensively used in computer graphics. Boolean operation is one of the fundamental shape modeling tools to create complex geometries which are usually presented by mesh representation due to its simplicity and high fidelity. In many applications, like industrial design and virtual prototyping, CAD models are always the Boolean models involved with a large number of high density meshes. Downstream applications like rapid prototyping, always require 2-manifold and watertight meshes as their input. However when performing Boolean operations directly on meshes the major difficulties are efficiency and robustness. Intersections between mesh elements make the process very time consuming and error prone especially when the degeneracies (e.g., overlapping surfaces) are occurre...[ Read more ]

Shape modeling is extensively used in computer graphics. Boolean operation is one of the fundamental shape modeling tools to create complex geometries which are usually presented by mesh representation due to its simplicity and high fidelity. In many applications, like industrial design and virtual prototyping, CAD models are always the Boolean models involved with a large number of high density meshes. Downstream applications like rapid prototyping, always require 2-manifold and watertight meshes as their input. However when performing Boolean operations directly on meshes the major difficulties are efficiency and robustness. Intersections between mesh elements make the process very time consuming and error prone especially when the degeneracies (e.g., overlapping surfaces) are occurred. This can lead to invalid topology in the resulting models. These issues can become even serious when a large number of high density mesh components are involved.

The objective of this thesis is to design a modeling scheme which can perform efficient and robust Boolean operation on complex geometric models and guarantee the result is a 2-manifold model.

In this thesis, a new point-neighborhood representation, OFN Surfel-Mesh, is proposed. Consists of OFN surfels, i.e., surfels embedded with oriented Four-Neighborhood (OFN), OFN Surfel-Mesh inherently adapts to parallel computation. The entire Boolean operations can be evaluated based on each OFN surfel in parallel and the topological validity of the Boolean result can be guaranteed even when degenerate intersections are involved. Moreover the embedded OFN can also facilitate parallel mesh construction and the generated mesh is ensured to be a 2-manifold model. Boolean models containing hundreds of mesh components can be computed less than one second on GPU using this method.

OFN Surfel-Mesh can also find applications in slicing and surface manipulation by utilizing the surfel traversal and topological operators derived from OFN.

To demonstrate the main strength of the proposed Boolean method, comparisons with the state-of-art platforms based on the given Boolean models, are given at last.