Faceted Geometry Kernel – Mesh Boolean Technology
CCTech's research and development focused for past several year is in the area of mesh processing or discrete geometry processing. The key technological research outcomes are integrated into our mesh processing kernel named Faceted Geometry Kernel (FGK).
One of the core technology we developed in FGK is ability to perform Boolean operations on Faceted/Tessellated/Triangulated/Discrete/Mesh Geometries (all these words used interchangeable here) .
Some of the salient feature of Mesh Boolean technologies are as follow :
- Mesh objects can be multiple connected solids, multi-body solids, non-manifold solids, solid with internal void holes, solid X surface, surface x surface, non-manifold surfaces
- Ability to handle point contacts, line contacts, plane contact
- High floating point accuracy for intersections
- Tolerant modeling to reduce the failure rate
- Ability to retain original shape
- Crisp intersection curves
- Assembly models processing
- If input is Faceted BREP Model ie Facet Information + BREP topology, the output solid after Boolean is Faceted BREP
- Output Boolean Solid retains the Surface Parametrization
- Surface - Solid combination can perform Punching, Slicing, Shelling operations
Boolean Operations on Triangulated Solids :
Algorithm to perform 3D Boolean operations on CAD model are being developed from last 30 years. The successful implementation of Boolean operations on BREP made it one of the most popular underlying geometric modeling technology. However these Boolean operations are mainly used in NURBS base solid models.
Mesh objects as modeling representation is not very popular in Mechanical CAD (MCAD) industry. Industrial Design applications such as 3D Max, Maya used mesh object and they have various feature to process mesh objects.
CCTech is currently using mesh processing technology in various innovative applications in Mechanical CAD, Civil CAD, manufacturing simulation, CFD model preparation, oil and gas domain extraction, biomedical modeling and other. We believe mesh processing technology can be greatly leveraged on new Mobile, Cloud and internet applications for CAx vertical. Since it has very small memory and computation footprint as compared to NURBS base modeling.
Mesh Boolean Types :
Boolean on mesh objects can be performed in two ways :
- Standard Boolean algorithm used in BREP
- Using Level Set Method to create approximate but quick Boolean
We have developed both these meshing Boolean technologies for different CAx applications. We found that in engineering application where the precise Boolean are essential one must use standard BREP based algorithm. However for various upfront simulations eg in manufacturing simulation for 3Axis or 5 Axis Milling simulation, going for exact Boolean would be a overkill. Here LSM based Boolean works wonderfully.
The rest of this article will elaborate first approach in detail.
Mesh Boolean Basics :
1) Target and tool : The operands of a Boolean are called the target and the tool. The target of a Boolean is the body you begin with, and the tool is the body you operate on it with. The target is modified by the tool, and the tool is deleted at the end of the operation. Following figure illustrate target, tool and possible Boolean output.
The following diagram shows the faceted Boolean perform on triangulated Cube and Cylinder.
2) Non-Manifold or cellular Solids : In simple word, A manifold is a mathematical term for a object that locally resembles a line, a plane, or a space whereas Non-manifold Object is with point or line or plane contact between the solids. Single Solid body with multiple zone separated by face is called as cellular solid. Mesh Boolean can perform general body Boolean i.e. non-manifold boolean as shown in below figures.
3) Type of Boolean :
Global Booleans : Global Boolean perform Boolean operations on whole bodies, taking a single target body, and multiple tool bodies, and applying the specified Boolean operation to the target. Because the operation is performed at the body level (by comparing all pairs of faces in the target and tool), the resulting body is guaranteed to be topologically consistent. Global Boolean, because of the nature of the face pair comparison, can be computationally expensive.
Local Booleans : Local Boolean (sometimes known as partial Boolean), tend to be very quick to perform compared to global Boolean. Rather than working at the body level, local Boolean use a set of faces from a target body, and a set of faces from a single tool body. User specifies these faces himself, and only the faces user specify are used in the Boolean operation. Restricting the scope of the Boolean operation in this way can drastically improve performance.
Sheet Booleans : When we use target or tool as surface and solid combination, the boolean are called as Sheet Boolean. If booleans in subtract operation target is solid and tool is sheet then one can perform trimming operation whereas target is sheet and tool is solid produces punching operation. Sheet Boolean can be subdivided in following types
4) Trimming :
When target body is solid body and tool is surface body and boolean option is subtraction, the output solid bodies can be trim solids as shown below figure. Trimming in particular is highly useful in trimming unwanted features or removing components during CAD Repair operations in downward applications such as CFD and CAE analysis geometry preparation.
Trimming Mesh Solid - Sheet Boolean
4) Punching :
In Punching a effect like in sheet metal can created using sheet boolean. Here target is surface body whereas tool is solid body. Boolean option used here is addition. This adds part of surface from solid body into surface body and creates Punched surfaces as shown in below figure.
Punching Mesh Surface - Sheet Boolean
Mesh Boolean Algorithm :
A Boolean operation may be a union, subtraction or intersection. Generally the input parameters are passed through option structure to create appropriate Boolean is created. By default union operation is performed. Faceted Boolean has four main important steps, those are intersection, imprinting, gluing, and selection:
Steps in Boolean Algorithm
1) Intersection :
First step of a Boolean operation is to find the intersection between the target and tool entities. Since our underlying geometric entities are triangulated solids and surfaces, you have to perform polygon X polygon intersection over large set of entities in short time. The high level floating point accurate algorithms are used to make the intersections robust. The expected output at the end of Intersection is set points, set of curves. In geometries with curved overlapping surfaces one can get infinite number of intersections. Therefore obtaining correct intersection curved in this case is tricky task.
2) Imprinting :
New geometric entities created in intersection operations need to be embedded in topological structure of target and tool bodies. This processing of topological embedding is called Imprinting. Once can expect new imprint edges and vertices at location of intersection. These imprinted edges and vertices form the boundaries of intersection between target and tool entities. These edges divide the faces of each body into face sets which are either inside, outside, or on the boundary of, the other bodies.
3) Gluing and Selection :
The output of Imprinting process is new topological entities such as Faces, Edge and vertex. One need to stitch or glue these topological entities to create new shells. Such gluing of resulting sets of Faces can create multiple shells. Topological Shells gives new bounded regions.
4) Result :
Newly form regions in above steps compartmentalize the physical space. The parts of physical space of the model which are to be kept or rejected are selected, according to the type of Boolean being performed. For example in case of Boolean addition operations one keep all the regions. If there is duplication region then those are deleted. Depending on expected result type such as manifold or Non-manifold, these regions are also required to be merged to form a cohesive physical space. In case of Boolean subtract operation, target-tool common regions are not added in final body. It is also possible that new target bodies might have lot more new faces due to imprinting operation. In this step those new faces are also merged whenever possible.
Mesh Boolean Implementation :
Implementation of Mesh Boolean algorithms expands above four steps into many micro algorithms. To handle the Boolean on assembly models, Non-manifold model further steps are added in main Boolean algorithm. Following flow chart shows important steps of mesh Boolean implementation. In next blog article we would discuss them in details. Do leave your valuable comment and feedback in comment section.
Mesh Boolean Algorithm - Implementation Flow Chart