Awesome
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
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(ISBN978-3-540-77973-5)