Skip to content

A modern, high-performance spatial querying library.

License

Notifications You must be signed in to change notification settings

jgphilpott/polytree

Repository files navigation

Polytree Icon

Polytree Testsnpm versionLicense: MIT

Polytree

Intro

Polytree is a modern, high-performance spatial querying and Constructive Solid Geometry (CSG) library for JavaScript and Node.js Built on an efficient Octree data structure, it is designed for advanced 3D modeling, mesh analysis, geometric search, and seamless integration with three.js.

Polytree goes beyond traditional CSG libraries by providing a comprehensive suite of spatial query functions—such as closest point, distance field, intersection testing, layer slicing, and volume analysis—making it ideal for 3D printing, CAD, simulation, and mesh analysis applications.

▶️View the Polytree Demo Site with GitHub Pages

📦 View the Polytree npm Package

Features

  • Advanced Spatial Queries: Closest point search, distance calculations, intersection testing, layer slicing, and volume analysis—optimized for mesh analysis, 3D printing, and simulation workflows.
  • Complete CSG Operations: Union, subtraction, and intersection with full test coverage.
  • 3D Printing & CAD Support: Layer slicing, cross-section analysis, and spatial operations for manufacturing and design applications.
  • High Performance: Octree-based spatial partitioning for fast queries and operations on large meshes.
  • Dual API: Both synchronous and asynchronous operation modes for flexible integration.
  • Multi-Input Support: Works directly with Three.js meshes, BufferGeometry, and Polytree instances.
  • Lightweight: Minimal dependencies with efficient memory usage.
  • Three.js Integration: Direct mesh-to-mesh operations and spatial queries with material preservation.
  • Well Documented: Comprehensive API documentation and interactive examples.
  • Robust Testing: 500+ tests ensuring reliability across edge cases.

Table of Contents

Getting Started

Node.js

Install

npm install polytree

Import

import*asTHREEfrom'three';import{Polytree}from'polytree';

Browser

For browser usage, use the ES module-compatible bundle:

<scripttype="importmap">{"imports": {"three": "./path/to/three.module.min.js","polytree": "./path/to/polytree.bundle.browser.js"}}</script><scripttype="module">import*asTHREEfrom'three';importPolytreefrom'polytree';</script>

The browser bundle (polytree.bundle.browser.js) is specifically designed for ES module imports in browsers, while the main bundle (polytree.bundle.js) is for Node.js environments.

Usage

Utility Functions

Polytree provides utility functions for geometry analysis and calculations:

Surface Area Calculation

Calculate the surface area of Three.js meshes or geometries:

// Calculate surface area from a mesh:constboxGeometry=newTHREE.BoxGeometry(2,3,4);constboxMesh=newTHREE.Mesh(boxGeometry,newTHREE.MeshBasicMaterial());constsurfaceArea=Polytree.getSurface(boxMesh);console.log(`Surface area: ${surfaceArea}`);// Output: 52// Calculate surface area directly from geometry:constsphereGeometry=newTHREE.SphereGeometry(1);constsphereSurfaceArea=Polytree.getSurface(sphereGeometry);console.log(`Sphere surface area: ${sphereSurfaceArea}`);// Output: ~12.47

The getSurface() method:

  • Accepts either Three.js Mesh objects or BufferGeometry objects.
  • Returns the total surface area as a number.
  • Works by summing the areas of all triangular faces.
  • Handles both indexed and non-indexed geometries.

Volume Calculation

Calculate the volume of Three.js meshes or geometries:

// Calculate volume from a mesh:constboxGeometry=newTHREE.BoxGeometry(2,2,2);constboxMesh=newTHREE.Mesh(boxGeometry,newTHREE.MeshBasicMaterial());constvolume=Polytree.getVolume(boxMesh);console.log(`Volume: ${volume}`);// Output: 8// Calculate volume directly from geometry:constsphereGeometry=newTHREE.SphereGeometry(1);constsphereVolume=Polytree.getVolume(sphereGeometry);console.log(`Sphere volume: ${sphereVolume}`);// Output: ~4.19 (approx 4/3 * π)

The getVolume() method:

  • Accepts either Three.js Mesh objects or BufferGeometry objects.
  • Returns the total volume as a number.
  • Uses the divergence theorem with signed tetrahedron volumes.
  • Handles both indexed and non-indexed geometries.
  • Automatically handles edge cases like empty geometries.

Basic CSG Operations

Polytree provides three core CSG operations that work directly with Three.js meshes:

Unite (Join)

Join two 3D objects into a single merged object:

// Create two identical boxes.constgeometry1=newTHREE.BoxGeometry(2,2,2);constgeometry2=newTHREE.BoxGeometry(2,2,2);constmesh1=newTHREE.Mesh(geometry1,newTHREE.MeshBasicMaterial());constmesh2=newTHREE.Mesh(geometry2,newTHREE.MeshBasicMaterial());// Offset the position of one box.mesh1.position.set(1,1,1);// Join the boxes together.constresult=awaitPolytree.unite(mesh1,mesh2);scene.add(result);

Subtract (Remove)

Remove one object's volume from another:

// Create a box and a sphere.constboxGeometry=newTHREE.BoxGeometry(2,2,2);constsphereGeometry=newTHREE.SphereGeometry(1.5);constboxMesh=newTHREE.Mesh(boxGeometry,newTHREE.MeshBasicMaterial());constsphereMesh=newTHREE.Mesh(sphereGeometry,newTHREE.MeshBasicMaterial());// Remove the sphere from the box (creates a cavity).constresult=awaitPolytree.subtract(boxMesh,sphereMesh);scene.add(result);

Intersect (Overlap)

Keep only the overlapping volume of two objects:

// Create two overlapping spheres.constsphere1=newTHREE.Mesh(newTHREE.SphereGeometry(1),newTHREE.MeshBasicMaterial());constsphere2=newTHREE.Mesh(newTHREE.SphereGeometry(1),newTHREE.MeshBasicMaterial());// Offset the position of one sphere.sphere1.position.set(1,0,0);// Keep only the overlapping volume.constresult=awaitPolytree.intersect(sphere1,sphere2);scene.add(result);

Async CSG Operations

For better performance in web applications, use async operations to prevent UI blocking:

// Async union with Promise.constunionPromise=Polytree.unite(mesh1,mesh2);unionPromise.then(result=>{scene.add(result);});// Async with await.constunionResult=awaitPolytree.unite(mesh1,mesh2);scene.add(unionResult);

Async Array Operations

Process multiple objects efficiently:

// Unite multiple objects asynchronously.constmeshArray=[mesh1,mesh2,mesh3,mesh4...meshX];constpolytreeArray=meshArray.map(mesh=>Polytree.fromMesh(mesh));Polytree.async.uniteArray(polytreeArray).then(result=>{constfinalMesh=Polytree.toMesh(result);scene.add(finalMesh);// Clean up.polytreeArray.forEach(polytree=>{polytree.delete()});result.delete();});

Spatial Query Functions

Polytree now includes advanced spatial query capabilities inspired by the three-mesh-bvh library, transforming it from a pure CSG library into a comprehensive spatial querying tool optimized for 3D printing applications.

Point-based Queries

Find the closest points and calculate distances for collision detection and mesh analysis:

constgeometry=newTHREE.BoxGeometry(2,2,2);constmesh=newTHREE.Mesh(geometry,material);consttestPoint=newTHREE.Vector3(5,0,0);// Find closest point on surface - works with Mesh, BufferGeometry, or Polytree.constclosestPoint=Polytree.closestPointToPoint(mesh,testPoint);console.log(`Closest point: (${closestPoint.x}, ${closestPoint.y}, ${closestPoint.z})`);// Calculate distance to surface.constdistance=Polytree.distanceToPoint(mesh,testPoint);console.log(`Distance: ${distance} units`);

Volume Analysis

Perform both exact and statistical volume calculations:

// Exact volume calculation.constexactVolume=Polytree.getVolume(mesh);// Monte Carlo volume estimation for complex geometries.constestimatedVolume=Polytree.estimateVolumeViaSampling(mesh,50000);console.log(`Exact: ${exactVolume}, Estimated: ${estimatedVolume}`);

Intersection Testing

Test intersections with bounding volumes for collision detection:

// Test sphere intersection.constsphere=newTHREE.Sphere(newTHREE.Vector3(0,0,0),2);constintersectsSphere=Polytree.intersectsSphere(mesh,sphere);// Test bounding box intersection.constbox=newTHREE.Box3(min,max);constintersectsBox=Polytree.intersectsBox(mesh,box);

3D Printing Layer Slicing

Generate layer slices for 3D printing applications:

// Slice geometry into horizontal layers.constlayers=Polytree.sliceIntoLayers(mesh,// Input geometry0.2,// Layer height (0.2mm)-10,// Minimum Z10,// Maximum ZnewTHREE.Vector3(0,0,1)// Optional normal (default: Z-up));console.log(`Generated ${layers.length} layers for 3D printing`);// Single plane intersection for cross-section analysis.constplane=newTHREE.Plane(newTHREE.Vector3(0,0,1),0);constcrossSection=Polytree.intersectPlane(mesh,plane);

Advanced Spatial Operations

Custom spatial queries and triangle-based operations:

// Get triangles near a specific point.constnearbyTriangles=Polytree.getTrianglesNearPoint(mesh,point,2.0);// Custom spatial query with callback.constresults=Polytree.shapecast(mesh,(triangle)=>{// Custom query logic - return true to collect triangle.returntriangle.normal.y>0.8;// Find upward-facing triangles.},(triangle)=>{// Optional collection callback for processing results.return{ triangle,area: triangle.getArea()};});

Multi-Input Support

All spatial query functions accept Three.js meshes, BufferGeometry, or Polytree instances:

constgeometry=newTHREE.BoxGeometry(2,2,2);constmesh=newTHREE.Mesh(geometry,material);constpolytree=Polytree.fromMesh(mesh);// All of these work identically.constresult1=Polytree.closestPointToPoint(mesh,testPoint);// Meshconstresult2=Polytree.closestPointToPoint(geometry,testPoint);// BufferGeometryconstresult3=Polytree.closestPointToPoint(polytree,testPoint);// Polytree

Advanced Polytree-to-Polytree Operations

For maximum performance when chaining operations, work directly with Polytree objects:

// Convert meshes to polytrees once.constpolytree1=Polytree.fromMesh(mesh1);constpolytree2=Polytree.fromMesh(mesh2);constpolytree3=Polytree.fromMesh(mesh3);// Chain operations efficiently.constintermediate=awaitPolytree.unite(polytree1,polytree2);constfinal=awaitPolytree.subtract(intermediate,polytree3);// Convert back to mesh for rendering.constfinalMesh=Polytree.toMesh(final);scene.add(finalMesh);// Clean up resources.polytree1.delete();polytree2.delete();polytree3.delete();intermediate.delete();final.delete();

Performance

Polytree is designed for high-performance CSG operations:

  • Octree Optimization: Spatial partitioning reduces computational complexity for both CSG and spatial query operations.
  • Memory Efficient: Smart resource management with cleanup methods and automatic temporary object disposal.
  • Unified Architecture: CSG operations + spatial queries in one optimized library, eliminating the need for multiple tools.
  • Multi-Input Support: Functions work directly with Three.js meshes, geometries, and Polytree instances without manual conversion.
  • Comprehensive Testing: 500+ test cases ensuring reliability and performance across all operations.
  • Async Support: Non-blocking operations for smooth user experiences.
  • Minimal Dependencies: Only Three.js as a dependency for lightweight integration.

Applications

  • 3D Modeling: Professional-grade boolean operations for CAD applications.
  • Game Development: Runtime mesh manipulation and procedural geometry.
  • 3D Printing & Manufacturing: Complete slicing pipeline with layer generation, support analysis, and volume calculations.
  • Collision Detection: Fast spatial queries for physics engines and interactive applications.
  • Mesh Analysis & Repair: Distance field calculations, closest point queries, and geometric validation.
  • Architectural Visualization: Complex building geometry operations with spatial analysis.
  • Educational Tools: Interactive 3D geometry learning applications with real-time feedback.
  • Integration with Polyslice: Advanced FDM slicing workflows and manufacturing optimization.

Contributing

Contributions, issues, and feature requests are welcome! Please open an issue or submit a pull request.


Polytree is developed and maintained by @jgphilpott.

Sponsor this project

  •  
  •  
  •  

Contributors 4

  •  
  •  
  •  
  •