[edit] Boolean Development

[edit] 1. Design

[edit] 1.1 Idea

For simplicity and robustness boolean union (OR) and difference (DIFF) are implemented in terms of intersection (AND) and negation (NOT):

 obA AND* obB = and( obA, obB )  obA OR* obB = not( and( not( obA), not( obB ) ) )  obA DIFF* obB = and( obA, not( obB ) )

Negation operation consists in flip normals and invert vertex order of all mesh faces.

[edit] 1.2 Methodology

The pipeline of boolean operations has 3 main phases (see Figure 1): Building input meshes*: here the input blender objects are converted into an internal format (mesh), taking into account the type of the boolean operation. Boolean intersection*: it is the implementation of the intersect (AND) boolean operation over two meshes. Build output object*: this phase converts the resulting mesh into the final blender object.

Figure 1: Boolean Operation Algorithm Pipeline.

[edit] 1.2.1 Conversion module

In order to simplify the boolean operation, the models used are triangle meshes. For this reason, there are one module to convert the blender objects to an internal mesh that has all the information and operations to perform the intersection. This module is used in the first and the last phases of the previous pipeline (see Figure 1).

[edit] 1.2.2 Boolean operation module

The result of an AND boolean operation is a set of triangles that determines the boundary of the intersection between two meshes. These triangles could be not one of the original ones. To calculate this new ones, this module search pairs of triangles that intersect and lie on the boundary. The intersection determines how to subdivide these two triangles to obtains the needed ones.

This module has to receive 2 meshes that must be solids, to generate correct results.

This module has 3 phases (see Figure 2): Build BSP Tree*: this phase constructs a both BSPs trees used to classify resulting triangles, to determine those that generate the intersection. The BSP is constructed using the face's planes. Each mesh have its BSP tree. Face to Face*: this process tests all the faces of one mesh to the other to determine the intersections between them and calculate the corresponding tesselations of the both triangles. Triangle Classification*: the objective is to divide the mesh in two triangles sets, IN & OUT. A triangle is classified IN when it is in both input meshes. To determine this, the BSP created in the first face is used. Triangle Post-Process*: The objective is to obtain a clean mesh. This phase merge triangles, when it is possible, and the result is triangles or quads.

Figure 2: Boolean Operation Module Pipeline.

[edit] 2. Implementation

[edit] New files

The new implementation is hosted in a new directory named _boolop_. The new files added until now are:

_intern/boolop/extern/BOP_Interface.h_ : Module interface.
_intern/boolop/intern/BOP_Interface.cpp_
_intern/boolop/intern/BOP_BSPTree.cpp/.h_ : BSP tree used for classify (IN or OUT) faces of both meshes.
_intern/boolop/intern/BOP_BSPNode.cpp/.h_ : BSP internal node.
_intern/boolop/intern/BOP_BBox.cpp/.h_ : Boundind box.
_intern/boolop/intern/BOP_Mesh.cpp/.h_ : Mesh data with acces function useful for boolop.
_intern/boolop/intern/BOP_Face.cpp/.h_ : Mesh face.
_intern/boolop/intern/BOP_Edge.cpp/.h_ : Mesh edge.
_intern/boolop/intern/BOP_Vertex.cpp/.h_ : Mesh vertex.
_intern/boolop/intern/BOP_Face2Face.cpp/.h_ : Core code.
_intern/boolop/intern/BOP_Merge.cpp/.h_ : Merge face with same face parent.
_intern/boolop/intern/BOP_Segment.cpp/.h_ : Collision region between two faces.
_intern/boolop/intern/BOP_Splitter.cpp/.h_ : Functions to split faces and edges.
_intern/boolop/intern/BOP_Triangulator.cpp/.h_ : Face triangulator using segments.
_intern/boolop/intern/BOP_Indexs.h_ : Useful index struct.
_intern/boolop/intern/BOP_Material.cpp/.h_ : Face material container.
_intern/boolop/intern/BOP_MaterialContainer.cpp/.h_ : Mesh materials container. Used to reconstruct original material.
_intern/boolop/intern/BOP_MathUtils.cpp/.h_ : Matematic functions.
_intern/boolop/intern/BOP_Tag.cpp/.h_ : Flag, with values IN, OUT ...

[edit] Modified files

_intern/bsp/intern/CSG_BooleanOps.cpp_ : Used to connect blender kernel with new boolean ops. When the implementation will be finished, the connection between blender kernel and new bool ops will be direct.
_intern/bsp/intern/BSP_CSGMesh_CFIterator.h_ : To allow quads.
_source/blender/src/booleanops.c_ : To allow quads.

[edit] Dependences

_intern/bsp_ : Mesh, export functions and main entry point. This dependence can be skipped if the code is directly connected from booleanops.c.
_intern/csg_ : Interpolate function, used to calcule UV coords.

[edit] 3. Interaction

The user will interact with the system in the same way as now, because only the internal implementation of boolean set operations is being changed.

[edit] 4. Tasks

Testing (in progress)
Direct connection with booleanops.c
Check for non-manifold / non-closed input meshes (currently produces a crash)

[edit] 5. Screenshots

Old Version	New Version	Megabool script

Union of two cubes. Some vertices coincide with edges, the result not is a solid mesh.	Union of two cubes. The result is well sewed.	Union of two cubes. The result is well sewed.
No solid mesh.

Intersection of two spheres, too many triangles.	Intersection of two spheres,preserving original quads.	Intersection of two spheres,preserving original quads. No material.
piramide.blend (union operation)

Wrong coincidences detection	Correct coincidences detection.	Wrong union operation.
cube_sphere.blend (union operation)

Too many triangles and no solid mesh.	Clean result.	Clean mesh but with some holes.
sphere_cube.blend (difference operation)

Too many triangles and no solid mesh.	Correct mesh.	Spectacular result with really good merging.