three-bvh-csg

The three-bvh-csg library is designed for high-performance Constructive Solid Geometry (CSG) operations using Bounding Volume Hierarchies (BVH) and half-edge data structures.

Core Design Priorities

• Compact Memory: Uses typed arrays to keep memory utilization low.
• Low Garbage Collection (GC) Impact: Employs data pooling (e.g., triangle instances) and modifies existing geometry buffers in place to minimize temporary data creation. Brushes cache data to speed up subsequent operations.
• High Performance: Uses half-edge structures and BVH to quickly discover and cull triangle intersections.
• Low Mesh Complexity: The BVH approach minimizes the number of triangles that need to be split, reducing the complexity of the resulting mesh.

Key Data Structures

• Half-Edge Structure: Pre-generated per Brush to allow fast traversal of connected triangles.
• BVH: Pre-generated per Brush to accelerate intersection detection between geometries.
• Group Indices: A map of group indices to triangles, allowing resulting triangles to be mapped to their appropriate material indices.

For complex, nested CSG trees, use the Operation class and Evaluator.evaluateHierarchy.

An Operation extends Brush and allows you to define a specific CSGOperation (via the .operation property) that will be applied to its children during a hierarchical evaluation. You can build a tree of operations using OperationGroup (which extends THREE.Group) and then pass the root Operation to evaluator.evaluateHierarchy.

Key Methods for building trees:

• .operation: Sets the CSGOperation to perform on the next brush in the processing chain.
• .insertBefore(brush): Inserts a brush before the operation element in the parent's children list.
• .insertAfter(brush): Inserts a brush after the operation element in the parent's children list.

// Conceptual usage of hierarchy
const root = new Operation( geometry );
root.operation = ADDITION;
root.add( childBrush );

const result = evaluator.evaluateHierarchy( root );

The CSG operation follows these primary steps:

1. Generate Brush Data Structures: The Brush generates its half-edge, BVH, and group indices if they are not already present.
2. Find All Intersections: BVH intersection tests are performed between the two geometries to identify all intersecting triangle indices.
3. Handle Whole Triangles:
   • For triangles with no intersections, one triangle is picked and tested via raycasting to determine if it is "inside" or "outside" the other geometry.
   • Based on the operation (e.g., union, subtract), the triangle is either included or excluded.
   • The algorithm then traverses the half-edge structure to include all connected non-intersecting triangles.
4. Handle Intersecting Triangles:
   • Intersecting triangles are split by all other intersecting triangles.
   • Each resulting sub-triangle is then tested via raycasting to determine inclusion.

To perform Constructive Solid Geometry (CSG) operations, create Brush instances from THREE.BufferGeometry (like SphereGeometry or BoxGeometry), ensure their world matrices are updated, and use an Evaluator to compute the result.

Important Requirements:

• All brush geometry must be two-manifold (water-tight with no triangle interpenetration).
• Once a brush is created, its geometry should not be modified.
• Call .updateMatrixWorld() on brushes before evaluation to ensure correct positioning.

import { SUBTRACTION, Brush, Evaluator } from 'three-bvh-csg';
import { MeshStandardMaterial, Mesh, SphereGeometry, BoxGeometry } from 'three';

const brush1 = new Brush( new SphereGeometry() );
brush1.updateMatrixWorld();

const brush2 = new Brush( new BoxGeometry() );
brush2.position.y = 0.5;
brush2.updateMatrixWorld();

const evaluator = new Evaluator();
const result = evaluator.evaluate( brush1, brush2, SUBTRACTION );

// render the result!

The following files constitute the core of the implementation:

The three-bvh-csg library provides tools for Constructive Solid Geometry (CSG) operations on Three.js meshes using BVH acceleration. The main entrypoint exports the following core modules:

• Brush: The primary building block for CSG; a mesh wrapper that holds geometry and operation data.
• Evaluator: The engine that performs the actual CSG operations between brushes.
• Operation and OperationGroup: Classes used to define how brushes interact (e.g., subtraction, union, intersection).
• GridMaterial: A specialized material for visualizing grids.
• TriangleSplitter (via LegacyTriangleSplitter or CDTTriangleSplitter): Utilities for splitting triangles during operations.

To use the library, you typically import Brush to define your shapes and Evaluator to compute the result.

import { Brush, Evaluator } from 'three-bvh-csg';

// Example workflow:
// 1. Create brushes
// 2. Define operations
// 3. Evaluate with an Evaluator instance