Module voxelization

Voxelization of a 2D polyline or 3D triangle mesh. Voxelization of 2D and 3D shapes.

What is Voxelization?

Voxelization is the process of converting a continuous geometric shape (like a triangle mesh in 3D or a polyline in 2D) into a discrete grid of cubic cells called voxels. Think of voxels as 3D pixels - just like pixels make up 2D images, voxels make up 3D volumes. In 2D, voxels are actually square cells (sometimes called “pixels” in other contexts).

This is similar to how a photograph discretizes a continuous scene into pixels, except voxelization works in 3D space (or 2D for 2D shapes).

When Should You Use Voxelization?

Voxelization is useful when you need to:

• Approximate complex shapes with a simpler grid-based representation
• Compute volume of complex meshes (by counting filled voxels)
• Perform spatial queries efficiently using a regular grid structure
• Generate collision proxies for physics simulations (using the V-HACD algorithm)
• Simplify mesh operations like boolean operations or distance field computation
• Analyze shape properties like connectivity, cavities, or internal structure

Key Concepts

Voxel Grid

A voxel grid divides space into a regular array of cubic (or square in 2D) cells. Each cell is identified by integer coordinates (i, j) in 2D or (i, j, k) in 3D. The physical size of each voxel is controlled by the scale parameter.

Resolution vs Voxel Size

You can control the granularity of voxelization in two ways:

• By resolution: Specify how many subdivisions to make along the longest axis. The voxel size is automatically computed to maintain cubic voxels.
• By voxel size: Directly specify the physical size of each voxel. The resolution is automatically computed based on the shape’s bounding box.

Higher resolution (or smaller voxel size) gives more accurate approximation but uses more memory.

Fill Modes

The FillMode enum controls which voxels are considered “filled”:

• SurfaceOnly: Only voxels that intersect the surface boundary are marked as filled. This gives you a hollow shell representation.

• FloodFill: Fills voxels on the surface AND all voxels inside the volume. This uses a flood-fill algorithm starting from outside the shape. Options include:

  • detect_cavities: Properly handles internal holes/cavities
  • detect_self_intersections (2D only): Attempts to handle self-intersecting boundaries

Main Types

• VoxelSet: A sparse set containing only filled voxels (memory-efficient output format)
• VoxelizedVolume: A dense 3D grid of all voxels (intermediate format used during voxelization)
• Voxel: A single voxel with its grid coordinates and metadata
• FillMode: Configuration for how to determine filled vs empty voxels
• VoxelValue: The state of a voxel (inside, outside, or on surface)

Examples

Basic 3D Voxelization (Surface Only)

use parry3d::transformation::voxelization::{FillMode, VoxelSet};
use parry3d::shape::Cuboid;
use nalgebra::{Point3, Vector3};

// Create a simple cuboid and convert it to a triangle mesh
let cuboid = Cuboid::new(Vector3::new(1.0, 0.5, 0.3));
let (vertices, indices) = cuboid.to_trimesh();

// Voxelize with resolution of 10 voxels along the longest axis
let voxels = VoxelSet::voxelize(
    &vertices,
    &indices,
    10,                          // resolution
    FillMode::SurfaceOnly,       // only surface voxels
    false,                       // don't track voxel-to-triangle mapping
);

println!("Created {} surface voxels", voxels.len());
println!("Each voxel has volume: {}", voxels.voxel_volume());

// Access individual voxels
for voxel in voxels.voxels() {
    println!("Voxel at grid position: {:?}", voxel.coords);
    println!("  World position: {:?}", voxels.get_voxel_point(voxel));
    println!("  On surface: {}", voxel.is_on_surface);
}

3D Voxelization with Interior Fill

use parry3d::transformation::voxelization::{FillMode, VoxelSet};
use parry3d::shape::Ball;
use nalgebra::Point3;

// Create a sphere mesh
let ball = Ball::new(1.0);
let (vertices, indices) = ball.to_trimesh(20, 20); // subdivisions for sphere

// Voxelize with flood-fill to get solid interior
let voxels = VoxelSet::voxelize(
    &vertices,
    &indices,
    15,                                              // resolution
    FillMode::FloodFill {
        detect_cavities: false,                      // simple solid shape, no cavities
    },
    false,
);

// Compute the approximate volume
let volume = voxels.compute_volume();
let expected_volume = 4.0 / 3.0 * std::f32::consts::PI * 1.0_f32.powi(3);
println!("Voxel volume: {}, Expected: {}", volume, expected_volume);

// Count surface vs interior voxels
let surface_count = voxels.voxels().iter().filter(|v| v.is_on_surface).count();
let interior_count = voxels.voxels().iter().filter(|v| !v.is_on_surface).count();
println!("Surface voxels: {}, Interior voxels: {}", surface_count, interior_count);

2D Voxelization of a Polygon

use parry2d::transformation::voxelization::{FillMode, VoxelSet};
use nalgebra::Point2;

// Define a simple square as a polyline (boundary)
let vertices = vec![
    Point2::origin(),
    Point2::new(2.0, 0.0),
    Point2::new(2.0, 2.0),
    Point2::new(0.0, 2.0),
];

// Create index buffer for the polyline segments (closed loop)
let indices = vec![
    [0, 1],  // bottom edge
    [1, 2],  // right edge
    [2, 3],  // top edge
    [3, 0],  // left edge
];

// Voxelize with specific voxel size
let voxels = VoxelSet::with_voxel_size(
    &vertices,
    &indices,
    0.2,                                             // voxel size
    FillMode::FloodFill {
        detect_cavities: false,
        detect_self_intersections: false,
    },
    false,
);

println!("2D voxel area: {}", voxels.compute_volume());

Computing Convex Hull from Voxels

use parry3d::transformation::voxelization::{FillMode, VoxelSet};
use parry3d::shape::Cuboid;
use nalgebra::Vector3;

let cuboid = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let (vertices, indices) = cuboid.to_trimesh();

let voxels = VoxelSet::voxelize(
    &vertices,
    &indices,
    8,
    FillMode::SurfaceOnly,
    false,
);

// Compute convex hull from the voxel centers
// sampling=1 means use every voxel, higher values skip voxels for performance
let (hull_vertices, hull_indices) = voxels.compute_convex_hull(1);

println!("Convex hull has {} vertices and {} triangles",
         hull_vertices.len(), hull_indices.len());

Tracking Which Triangles Intersect Each Voxel

use parry3d::transformation::voxelization::{FillMode, VoxelSet};
use parry3d::shape::Cuboid;
use nalgebra::Vector3;

let cuboid = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let (vertices, indices) = cuboid.to_trimesh();

// Enable voxel-to-primitives mapping
let voxels = VoxelSet::voxelize(
    &vertices,
    &indices,
    10,
    FillMode::SurfaceOnly,
    true,  // keep_voxel_to_primitives_map = true
);

// Now we can compute exact intersections between voxels and triangles
let intersection_points = voxels.compute_primitive_intersections(&vertices, &indices);
println!("Generated {} intersection points", intersection_points.len());

// Or compute a more accurate convex hull using the triangle intersections
let (hull_verts, hull_indices) = voxels.compute_exact_convex_hull(&vertices, &indices);
println!("Exact convex hull: {} vertices", hull_verts.len());

Performance Considerations

• Resolution: Doubling the resolution increases memory usage by 4× in 2D or 8× in 3D
• VoxelSet vs VoxelizedVolume: VoxelSet is sparse (only stores filled voxels), while VoxelizedVolume is dense (stores all grid cells). For sparse shapes, VoxelSet is much more memory-efficient.
• Voxel-to-primitives map: Setting keep_voxel_to_primitives_map = true adds memory overhead but enables more precise operations like compute_exact_convex_hull()
• Flood-fill: Using FloodFill mode is more expensive than SurfaceOnly but gives you solid volumes instead of hollow shells

Use in Convex Decomposition

The voxelization system is used internally by Parry’s V-HACD implementation for approximate convex decomposition. See the vhacd module for details.

Structs

Voxel

A single voxel in a voxel grid.

VoxelSet

A sparse set of filled voxels resulting from voxelization.

VoxelizedVolume

A dense voxel grid storing the state of every voxel in a cubic volume.

Enums

FillMode

Controls how voxelization determines which voxels are filled vs empty.

VoxelValue

The state of a voxel during and after voxelization.