js-quadpcd

🌟 High-performance JavaScript QuadTree point cloud filtering and processing library

✅ Published: This package is now available on npm as js-subpcd

Features

• High Performance: Optimized QuadTree implementation for large point clouds
• PCL.js Compatible: Drop-in replacement with PCL.js API compatibility
• Spatial Filtering: Grid-based and depth-based point cloud subsampling
• Nearest Neighbor: Fast k-nearest neighbor search
• Multiple Formats: Support for various point cloud file formats
• Easy to Use: Simple, intuitive API similar to PCL
• Cross-platform: Works in Node.js 14+ environments
• Scalable: Handles datasets from thousands to millions of points

Visual Examples

| Point Cloud Filtering | Nearest Neighbor Search | |:---------------------:|:-----------------------:| | | |

Live demonstrations of js-subpcd in action

Quick Start

Installation

npm install js-subpcd

PCL.js Compatible API (Recommended)

const PCL = require('js-subpcd');

// Initialize PCL.js compatible API
const pcl = await PCL.init();

// Create point cloud
const cloud = new pcl.PointCloud(pcl.PointXYZ);
cloud.addPoint(new pcl.PointXYZ(1.0, 2.0, 3.0));

// Load from PCD data
const loadedCloud = pcl.loadPCDData(pcdArrayBuffer);
console.log(`Loaded ${loadedCloud.size()} points`);

// Save to PCD format
const pcdData = pcl.savePCDDataASCII(cloud);

📖 API Reference

PCL.js Compatible API

Initialization

const pcl = await PCL.init(options);

PointXYZ Class

const point = new pcl.PointXYZ(x, y, z);
// Properties: x, y, z
// Methods: clone(), distanceTo(other)

PointCloud Class

const cloud = new pcl.PointCloud(PointType);
// Methods:
// - addPoint(point)
// - size()
// - getPoint(index)
// - clear()
// Properties: width, height, isOrganized

Global Functions

// Load PCD data
const cloud = pcl.loadPCDData(data); // data: string | ArrayBuffer

// Save PCD data
const pcdData = pcl.savePCDDataASCII(cloud);

Legacy API

QuadTreeFilter

Main class for point cloud filtering operations.

Constructor

const filter = new QuadTreeFilter(minCellSize)

• minCellSize (number): Minimum cell size for QuadTree subdivision

Methods

loadFromFile(filename)

Load point cloud data from file.

filter.loadFromFile('data.txt');

filterPointsByGridSpacing(xCoords, yCoords, zCoords, minSpacing)

Filter points based on minimum lateral spacing.

const filtered = filter.filterPointsByGridSpacing(
    coords.x, coords.y, coords.z, 
    0.05 // 5cm spacing
);

Returns: Array of Point3D objects

filterByDepth(targetDepth)

Filter points using QuadTree depth levels.

const filtered = filter.filterByDepth(7); // 128x128 grid

Depth Levels:

• Depth 1: 2×2 grid (4 cells)
• Depth 2: 4×4 grid (16 cells)
• Depth 3: 8×8 grid (64 cells)
• Depth 6: 64×64 grid (4,096 cells)
• Depth 8: 256×256 grid (65,536 cells)

DataLoader

Utility class for loading point cloud data.

const loader = new DataLoader();
loader.loadFromFile('pointcloud.txt');
const coords = loader.getCoordinateArrays();
const bounds = loader.getBounds();

QuadTreeManager

Low-level QuadTree operations.

const manager = new QuadTreeManager();
manager.buildTreeFromArrays(xCoords, yCoords, zCoords, bounds);

// Spatial queries
const pointsInRegion = manager.queryRegion(minX, minY, maxX, maxY);
const nearestPoints = manager.findNearestNeighbors(x, y, 5); // 5 nearest

Point3D

Basic 3D point representation.

const point = new Point3D(x, y, z, data);
console.log(point.x, point.y, point.z);

Acknowledgments

This project uses point cloud data from various sources. Below are the specific datasets with their sources, owners, and licenses:

Data Sources

| Dataset Name | Source URL | Owner | License | |--------------|------------|-------|---------| | Stanford 3D Scanning Repository | http://graphics.stanford.edu/data/3Dscanrep/ | Stanford University | Non-commercial use | | Open3D Sample Data | https://github.com/isl-org/Open3D/tree/main/examples/test_data | Intel Corporation | MIT License | | KITTI Vision Benchmark Suite | http://www.cvlibs.net/datasets/kitti/ | Karlsruhe Institute of Technology | Creative Commons Attribution-NonCommercial-ShareAlike 3.0 | | Synthetic Point Clouds | Generated internally | js-subpcd project | MIT License |

Usage Notes

• Stanford 3D Scanning Repository: Used for performance benchmarking and algorithm testing
• Open3D Sample Data: Used for unit tests and demonstration examples
• KITTI Vision Benchmark Suite: Used for LiDAR data processing examples
• Synthetic Data: Programmatically generated datasets for testing edge cases and unit testing

Special thanks to the open-source community and research institutions for providing high-quality datasets that enable the development and testing of point cloud processing tools.

Examples

PCL.js Compatible Usage

const PCL = require('js-quadpcd');

// Initialize
const pcl = await PCL.init();

// Create and populate point cloud
const cloud = new pcl.PointCloud(pcl.PointXYZ);
for (let i = 0; i < 1000; i++) {
    const point = new pcl.PointXYZ(
        Math.random() * 10,
        Math.random() * 10, 
        Math.random() * 5
    );
    cloud.addPoint(point);
}

console.log(`Created cloud with ${cloud.size()} points`);

// Save to PCD format
const pcdData = pcl.savePCDDataASCII(cloud);

// Load from PCD data
const loadedCloud = pcl.loadPCDData(pcdData);
console.log(`Loaded ${loadedCloud.size()} points`);

Legacy API Usage

Grid-based Subsampling

const { QuadTreeFilter } = require('js-quadpcd');

const filter = new QuadTreeFilter(0.001);
filter.loadFromFile('dense_pointcloud.txt');

const coords = filter.dataLoader.getCoordinateArrays();
console.log(`Original: ${coords.x.length} points`);

// Subsample with 10cm grid spacing
const subsampled = filter.filterPointsByGridSpacing(
    coords.x, coords.y, coords.z, 0.1
);

// Subsampled points ready for use
console.log(`Reduction: ${(100 * (1 - subsampled.length / coords.x.length)).toFixed(2)}%`);

Nearest Neighbor Search

const { QuadTreeManager } = require('js-quadpcd');

const manager = new QuadTreeManager();
manager.buildTreeFromArrays(xCoords, yCoords, zCoords, bounds);

// Find 10 nearest neighbors to point (5.0, 3.0)
const neighbors = manager.findNearestNeighbors(5.0, 3.0, 10);

neighbors.forEach((neighbor, i) => {
    // Process neighbor: distance and coordinates available
});

Performance Benchmarking

const { QuadTreeFilter } = require('js-quadpcd');

const filter = new QuadTreeFilter(0.001);
filter.loadFromFile('large_dataset.txt');

const coords = filter.dataLoader.getCoordinateArrays();

// Benchmark different grid spacings
const spacings = [0.01, 0.05, 0.1, 0.5, 1.0];

for (const spacing of spacings) {
    const start = performance.now();
    const filtered = filter.filterPointsByGridSpacing(
        coords.x, coords.y, coords.z, spacing
    );
    const time = performance.now() - start;
    
    console.log(`Spacing ${spacing}: ${filtered.length} points, ${time.toFixed(2)}ms`);
}

📊 Performance

Benchmark Results (33K point dataset):

| Operation | Grid Spacing | Points | Time | Reduction | |-----------|--------------|--------|------|----------| | Grid Filter | 0.01m | 4 | ~10ms | 99.99% | | Grid Filter | 0.1m | 4 | ~15ms | 99.99% | | Depth Filter | Level 6 | 3,332 | ~25ms | 89.92% | | Depth Filter | Level 8 | 21,761 | ~45ms | 34.18% | | Nearest Neighbor | k=5 | - | ~2ms | - |

🔧 File Format Support

Supported point cloud formats:

• Text files: Space/tab separated X Y Z coordinates
• Custom formats: Extend DataLoader for additional formats

Example format:

1.234 5.678 0.123
2.345 6.789 0.234
3.456 7.890 0.345

🤝 Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.

🙏 Acknowledgments

• Built with js-quadtree for spatial indexing
• Inspired by PCL (Point Cloud Library)
• Performance optimizations based on spatial data structure research

📞 Support

If you have any questions or need help, please:

• 📖 Check the documentation
• 🐛 Report bugs via GitHub Issues
• 💬 Start a Discussion

Made with ❤️ for the point cloud processing community