convexhull3d: 3D Convex Hull and Computational Geometry

A Rust implementation of the Quickhull algorithm for computing convex hulls in 3D space. Based on the convhull_3d C library and inspired by the MATLAB Computational Geometry Toolbox.

Features

• 3D Convex Hull Computation: Optimized Quickhull algorithm (Barber et al., 1996)
• Geometric Properties: Calculate volume and surface area of convex hulls
• Export Capabilities:
  • OBJ format for 3D modeling software
  • HTML with interactive Three.js visualization
• Test Data Generation: Built-in functions for generating test datasets
  • Random spherical distributions
  • Fibonacci sphere (uniform distribution)
  • T-Design approximations
  • Platonic solids (tetrahedron, cube, octahedron, icosahedron)
• Comprehensive Testing: Test suite matching the C++ convhull_3d library

Usage

Basic Example

use convexhull3d::{ConvexHull3D, Vertex};

// Define vertices
let vertices = vec![
    Vertex::new(0.0, 0.0, 0.0),
    Vertex::new(1.0, 0.0, 0.0),
    Vertex::new(0.0, 1.0, 0.0),
    Vertex::new(0.0, 0.0, 1.0),
];

// Build convex hull
let hull = ConvexHull3D::build(&vertices).unwrap();

// Get properties
println!("Faces: {}", hull.num_faces());
println!("Volume: {}", hull.volume());
println!("Surface Area: {}", hull.surface_area());

Exporting Results

use convexhull3d::{ConvexHull3D, export_obj, export_html, testdata};

// Generate test data
let vertices = testdata::icosahedron_vertices();

// Compute hull
let hull = ConvexHull3D::build(&vertices).unwrap();

// Export to OBJ
export_obj(&hull, "icosahedron.obj").unwrap();

// Export to interactive HTML
export_html(&hull, "icosahedron.html", "Icosahedron Hull").unwrap();

Generating Test Data

use convexhull3d::testdata;

// Random points on a sphere
let sphere_points = testdata::random_sphere_points(1000, 1.0);

// Fibonacci sphere (uniform distribution)
let uniform_sphere = testdata::fibonacci_sphere_points(500, 1.0);

// T-Design sphere approximations
let tdesign_180 = testdata::tdesign_180_sphere();
let tdesign_840 = testdata::tdesign_840_sphere();
let tdesign_5100 = testdata::tdesign_5100_sphere();

// Platonic solids
let cube = testdata::cube_vertices(2.0);
let octahedron = testdata::octahedron_vertices();
let icosahedron = testdata::icosahedron_vertices();

Algorithm

The implementation uses the Quickhull algorithm for 3D convex hull computation:

1. Initialization: Find an initial simplex (tetrahedron) from extreme points
2. Point Assignment: Assign remaining points to visible faces
3. Iteration:
   • Select furthest point from a face
   • Find all faces visible from that point
   • Determine horizon edges
   • Create new faces connecting the point to the horizon
4. Termination: Continue until no outside points remain

Key Features of the Implementation

• Robust: Handles degenerate cases and numerical precision issues
• Efficient: O(n log n) expected time complexity
• Accurate: Proper face orientation and normal computation
• Well-tested: Comprehensive test suite with diverse datasets

Test Results

The library has been tested against the same test cases as the C++ convhull_3d library:

Note: Face counts may vary slightly due to numerical precision and triangulation choices.

Running Tests

# Run all tests
cargo test --package convexhull3d

# Run specific test
cargo test --package convexhull3d test_tetrahedron

# Run with output
cargo test --package convexhull3d -- --nocapture

Generated Visualizations

Tests automatically generate:

• OBJ files: Located in target/convexhull_test_output/*.obj
• HTML visualizations: Located in target/convexhull_test_output/*.html

Open the HTML files in a browser to see interactive 3D visualizations using Three.js.

Comparison with C++ Implementation

This Rust implementation provides similar functionality to the convhull_3d C library:

Key Advantages of Rust Implementation

1. Memory Safety: No manual memory management required
2. Type Safety: Compile-time error checking
3. Modern Tooling: Cargo, rustdoc, clippy, etc.
4. Interactive Visualization: Built-in Three.js HTML export
5. Comprehensive Error Handling: Result types instead of error codes

API Reference

3D Types

• Vertex: 3D point with x, y, z coordinates
• Face: Triangle defined by 3 vertex indices
• ConvexHull3D: Result of 3D convex hull computation

Main Functions

• ConvexHull3D::build(&[Vertex]): Build 3D convex hull from vertices
• export_obj(&ConvexHull3D, path): Export to OBJ format
• export_html(&ConvexHull3D, path, title): Export to interactive HTML

Test Data Generation

• testdata::random_sphere_points(n, radius): Random sphere distribution
• testdata::fibonacci_sphere_points(n, radius): Uniform sphere distribution
• testdata::tdesign_*_sphere(): T-Design approximations
• testdata::*_vertices(): Platonic solids and other shapes

References

1. Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, 1996.
2. convhull_3d C Library by Leo McCormack
3. MATLAB Computational Geometry Toolbox

License

GPL-3.0-or-later (matching the parent project)

Contributing

This crate is part of the SotF project.