playkostudios / octreecsg-ea

Engine-agnostic port of the OctreeCSG library - abandoned in favor of Manifold

NOTICE

This project is abandoned! We've since switched over to Manifold.

Old README:

OctreeCSG-ea

A stripped down engine-agnostic version of the OctreeCSG library, ported to Typescript. This is very work-in-progress.

Note that this project is not affiliated with the OctreeCSG project.

Because this is a stripped down version of the library, some features are missing, such as directly operating with meshes and assigning materials.

Table of Contents

• Usage
• Operations
  • OctreeCSG.union
  • OctreeCSG.subtract
  • OctreeCSG.intersect
  • OctreeCSG.operation
• Array Operations
• Asynchronous Operations
• OctreeCSG Flags
• Limitations
• Resources

Usage

OctreeCSG comes as a Javascript Module and can be imported with the following command:

import { OctreeCSG } from 'octreecsg-ea';

This assumes that the library was installed as a node module. If not, replace octreecsg-ea with a full path to the bundle.

Note that if asynchronous operations are used, then the job dispatcher should be created with:

OctreeCSGJobDispatcher.create('/OctreeCSG-ea.worker.min.js', 2, 1000);

This only has to be done once, and further calls will be ignored. The first argument is the path to the web worker script, the second argument is the size of the worker pool (how many web workers should be created), and the third argument is the timeout in milliseconds for the creation of each worker (if this time is exceeded, then the worker fails to be created). The worker script must be copied to the root of the domain.

If the job dispatcher is not created, or fails to be created, then the library will still work, but asynchronous operations will simply act as synchronous operations wrapped in a promise (operations will not be done in a separate thread), which may introduce stuttering to a game that is using this library.

Operations

OctreeCSG.union:

Merges two Octrees (octreeA and octreeB) to one Octree

Parameter	Description
octreeA	First octree object
octreeB	Second octree object

OctreeCSG.subtract:

Subtracts octreeB from octreeA and returns the result Octree

Parameter	Description
octreeA	First octree object
octreeB	Second octree object

OctreeCSG.intersect:

Returns the intersection of octreeA and octreeB

Parameter	Description
octreeA	First octree object
octreeB	Second octree object

OctreeCSG.operation

CSG Hierarchy of Operations (syntax may change), provides a simple method to combine several CSG operations into one

Parameter	Description
obj	Input object with the CSG hierarchy
returnOctrees	(Optional) Specifies whether to return the Octrees as part of the result or not (true / false). Default: false

Input object structure:

Key	Expected Value
op	Type of operation to perform as string, options: union, subtract and intersect
material	(Optional) Used only in the root level of the object, if a material is provided the returned object will be a three.js mesh instead of an Octree. Value can be a single material or an array of materials
objA	First object, can be a three.js mesh, Octree or a sub-structure of the CSG operation
objB	Second object, can be a three.js mesh, Octree or a sub-structure of the CSG operation

Array Operations

OctreeCSG provides 3 methods to perform CSG operations on an array of meshes / octrees

Parameter	Description
objArr	An array of meshes or octrees to perform the CSG operation on

List of Methods:

• OctreeCSG.unionArray - Union operation on an array of meshes
• OctreeCSG.subtractArray - Subtract operation on an array of meshes
• OctreeCSG.intersectArray - Intersect operation on an array of meshes

Asynchronous Operations

OctreeCSG provides asynchronous CSG methods for all the advanced CSG operations.

List of Methods:

• OctreeCSG.async.union
• OctreeCSG.async.subtract
• OctreeCSG.async.intersect
• OctreeCSG.async.operation
• OctreeCSG.async.unionArray
• OctreeCSG.async.subtractArray
• OctreeCSG.async.intersectArray

OctreeCSG Flags

The following flags and variables control how OctreeCSG operates.

Flag / Variable	Default Value	Description
OctreeCSG.useWindingNumber	false	Determines if to use the ray-triangle intersection algorithm or the Winding number algorithm. The Winding number alogirthm can be more accurate than the ray-triangle algorithm on some occasions at the cost of performance. Options: true, false
OctreeCSG.maxLevel	16	Maximum number of sub-Octree levels in the tree
OctreeCSG.polygonsPerTree	100	Minimum number of polygons (triangles) in a sub-Octree before a split is needed

Limitations

The current worker script size is huge due to browser and esbuild limitations. Ideally, the worker script would share code with the rest of the library, however, esbuild code splitting is only available for ES6 modules, but module workers are not yet supported on Firefox.

As a workaround, the worker is bundled with the library and gl-matrix as an IIFE, which increases the size of the worker script dramatically.

Resources

• The Polygon, Vertex and Plane classes were adapted from THREE-CSGMesh
• The Winding number algorithm is based on this code
• The Möller–Trumbore ray-triangle intersection algorithm is based on this code
• The triangle-triangle intersection logic and algorithm is based on this code
• The ray-box intersection logic and algorithm is based on these 3 articles: part 1, part 2 and part 3
• The triangle-box intersection logic and algorithm is based on this code, which in turn is based on this paper
• The triangulation algorithms are based on the book Computational Geometry: Algorithms and Applications (ISBN 978-3-540-77973-5)