利用者:Nazg-gul/CarveBooleans

Carve library integration project

Abstract

Current boolop library which is used by boolean modifier has got plenty of limitation like stack overflow issues on large meshes and slow speed. This project is aimed to resolve all this limitation by using Carve library istead of boolop.

Even though Carve gives superior results, two crucial conditions for input Meshes are still relevant:

• Things work best when input meshes are manifold volumes.
• Make sure face normals are pointing consistantly and in right direction.

General Information

Carve is a C++ library which performs boolean operations bewteen two meshes. Intersection, Difference and Union operations are supported. It behaves much faster than boolop and it usually produces much nicer topology on result mesh.

No changes to interface are intened with this project, it's just change of deeper core stuff which isn't actually visible. Artists just continue to work with BooleanModifier as they used to do.

Implementation

Carve library was integrated into Blender code in carve_booleans branch andcurrently is preparing for merging into trunk.

It was attached to Boolean Modifier as an alternative interface in boolop library, which has got exactly the same entry point called BOP_performBooleanOperation but instead of doing math in Blender side, it converts Blender CSG mesh to Carve structures and delegates calculation to Carve library. This allowed to achieve two things:

• Boolean Movdifier can be easily switched back to boolop in case if Carve will fail. So, Carve in Blender can be easily disabled setting WITH_BF_CARVE SCons flag to False or setting WITH_CARVE CMake option to OFF.
• This allowed to keep all code needed for custom data layers interpolation without changes and concentrate work on geometry calculation.

Carve interface for boolop is implemented in file BOP_CarveInterface.cpp. Logic in this file isquite straightforward:

• Convert Blender's CSG mesh to Carve's MeshSet object.
• Perform boolean operation between two MeshSet objects using Carve library.
• Convert result MeshSet object to Blender's CSG object.

Vetices conversion is also very straigtforward. It just converts float[3] array to carve::geom::VECTOR and puts all vertices to std::vector so Carve can use them all.

Conversion of faces to Carve representation is a bit more tricky. It's because Carve can't deal with non-planar faces, so non-planar quads are getting split into two triangles using 1-3 diagonal. Also, original's face indices are getting saved as Carve attributes so this triangles can be merged back to quad.

Final creation of MeshSet happens using it's constructor which reeives vector with vertices and faces. Edges are getting calculated automatically.

Coversion of Carve MeshSet object back to Blender's CSG mesh happens in the following way. Vertices are getting convereted from carve::geom::vector to BSP_MVertex by just copying coordinates as-is.

When conversion of faces to BSP_MFace happens, exporting function checks if current face can be merged with orher triangles from the same original face. Two triangles can be merged if they've got the same original face indes and they shares one edge.

After this, result is sending back to bsp where additional things like customdata layers interpolation happens. This stuff wasn't touched by this project so don't think it's needed to describe process from there.

Regressions

There are several cases when Carve library causes regressions in comparsion with boolop library. It's not actually bugs, just different behavior in comparsion with boolop in special cases. Carve can perform boolean operation only if intersection of two meshes is a closed loop of edges.

See the 2.62 boolean release notes for details.

Carve and BMesh

Currently BMesh tesselates mesh before sending it to boolop library. Just after merge of Carve into BMesh mesh would still be tesselating but after some tweaks in that code it might be improved. Currently Carve can deal with planar ngons and tesselation for them wouldn't be needed. For non-planar faces tesselation happens in boolop's Carve interface and then triangles are merging back to quads if it's possible. This merging can be improved to deal with ngons. Probably changes to bsp are also needed, but it's just another story..