Lifted Surfacing of Generalized Sweep Volumes

This code implements the ACM SIGGRAPH ASIA 2025 paper: Lifted Surfacing of Generalized Sweep Volumes

Top: A wire-like ball rolls forward while offsetting, changing its genus from 41 to 29. Bottom: The time-colored sweep boundary and sharp creases (2nd row), in transparency (3rd row, creases hidden for clarity), and a cut-away view (bottom row).

Given any sweep represented as a smooth time-varying implicit function satisfying a genericity assumption, this algorithm produces a watertight and intersection-free surface that faithfully approximates the geometric and topological features.

Build

Dependencies

All third-party libraries are open-source and automatically fetched using CMake.

C++ Build

Use the following command to build:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make

The C++ library libsweep and the command line tool generalized_sweep will be generated in the build directory.

Python Bindings

We also provide a Python binding for easy integration with Python workflows:

# Install the Python package
pip install .

Usage

C++ API

The C++ API consists of two simple functions, generalized_sweep and generalized_sweep_from_config defined in include/sweep/generalized_sweep.h. For complete API documentation, please see generalized_sweep.h.

generalized_sweep

The generalized_sweep function provides the most general API. It takes the following inputs:

• a user-provided space-time function for pointwise function and gradient evaluation,
• (optional) a simple initial grid specification (doc), and
• (optional) customized sweep parameters (doc)

and generates the following outputs:

• Sweep surface (final output)
• Sweep envelope
• Envelope arrangement

In addition to the sweep surface, our code also provides the sweep envelope and envelope arrangement for advanced users. Please see our paper for their definitions.

Here is a simple example:

#include <sweep/generalized_sweep.h>
#include <lagrange/io/save_mesh.h> // For IO only

// Define implicit space-time function
// Sweeping a ball of radius `r` along the X axis by a distance `d`.
sweep::SpaceTimeFunc f = [](EigenRowVector4d p) {
    constexpr double r = 0.2;
    constexpr double d = 0.5;

    double x = p[0];
    double y = p[1];
    double z = p[2];
    double t = p[3];

    double val = (x + d * t) * (x + d * t) + y * y + z * z - r * r;
    Eigen::RowVector4d grad {
        2 * (x + d * t),
        2 * y,
        2 * z,
        2 * d * (x + d * t)
    };
    return {val, grad};
};

// Define an initial coarse grid
sweep::GridSpec grid;
grid.bbox_min = {-0.3, -0.3, -0.3};
grid.bbox_max = {0.8, 0.8, 0.8};

// Compute the sweep surface
auto r = sweep::generalized_sweep(f, grid);
lagrange::io::save_mesh("sweep_surface.obj", r.sweep_surface);

generalized_sweep_from_config

The generalized_sweep_from_config function loads two configuration files:

• function_file defines the space-time function
• config_file defines the initial grid spec and sweep parameters

It outputs the same set of meshes as generalized_sweep. Both function_file and config_file are in YAML format.

The function file is a YAML file that defines a space-time function supported by the space-time-functions library. Here is a simple function file that sweeps a ball along the X axis. Please see the spec for a complete set of supported transforms and shapes.

type: sweep
dimension: 3

# The base shape
primitive:
  type: ball
  center: [0.0, 0.0, 0.0]
  radius: 0.2
  degree: 2

# Sweeping trajectory
transform:
  type: polyline
  points:
  - [-0.5, 0.0, 0.0]
  - [0.5, 0.0, 0.0]

The config_file is used to specify the initial grid and the sweep options. Here is an example:

grid:
  resolution: [4, 4, 4]
  bbox_min: [-1, -1, -1]
  bbox_max: [1, 1, 1]

parameters:
  epsilon_env: 5e-4
  epsilon_sil: 5e-4
  with_snapping: false
  with_insideness_check: true

The parameters section will be used to construct the sweep::SweepOptions.

Here is an example:

#include <sweep/generalized_sweep.h>
#include <lagrange/io/save_mesh.h> // For IO only

auto r = sweep::generalized_sweep_from_config(
    "example/simple/sweep.yaml",
    "example/simple/config.yaml"
);
lagrange::io::save_mesh("sweep_surface.obj", r.sweep_surface);

Please see more config-files-based examples in the example folder.

Python API

import numpy as np
import sweep3d
import lagrange # For IO only

# Space-time function
def my_space_time_function(point_4d):
    """Space-time implicit function.
    
    :param point_4d: 4D point [x, y, z, t] where t ∈ [0, 1]
    :type point_4d: numpy.ndarray
    :return: Tuple of (value, gradient)
    :rtype: tuple(float, numpy.ndarray)
    """
    x, y, z, t = point_4d
    r = 0.2
    d = 0.5
    value = (x - t * d)**2 + y**2 + z**2 - r**2
    gradient = np.array([2 * (x - t * d), 2 * y, 2 * z, -2 * d * (x - t * d)])
    return (value, gradient)

# Initial grid
grid_spec = sweep3d.GridSpec()
grid_spec.bbox_min = [-0.3, -0.3, -0.3]
grid_spec.bbox_max = [0.8, 0.8, 0.8]

# Compute sweep surface
result = sweep3d.generalized_sweep(my_space_time_function, grid_spec)

# Extract mesh data
V = result.sweep_surface.vertices
F = result.sweep_surface.facets
print(f"#Vertices: {len(V)}, #Faces: {len(F)}")

# Save mesh
lagrange.io.save_mesh("out.msh", result.sweep_surface)

Please see help(sweep3d) for more details.

Grid Parameters

The GridSpec struct defines the initial spatial grid used for sweep computation. The grid represents the 3D spatial domain (the time dimension is handled separately).

Parameters

Note: The bounding box should be large enough to fully enclose the swept volume throughout the entire trajectory (t ∈ [0, 1]).

Sweep Options

The SweepOptions struct provides fine-grained control over the sweep computation. All parameters are optional and have sensible defaults.

Refinement Parameters

Quality Control Parameters

Surface Extraction Parameters

Advanced Parameters

Configuration Examples

The following examples show how to configure both grid parameters and sweep options together:

#include <sweep/generalized_sweep.h>

// Configure grid
sweep::GridSpec grid;
grid.resolution = {8, 8, 8};
grid.bbox_min = {-0.5, -0.5, -0.5};
grid.bbox_max = {1.5, 1.5, 1.5};

// Configure sweep options
sweep::SweepOptions options;
options.epsilon_env = 1e-3;
options.epsilon_sil = 1e-3;
options.with_insideness_check = false;
options.max_split = 1000000;

// Compute sweep
auto result = sweep::generalized_sweep(f, grid, options);

import sweep3d

# Configure grid
grid_spec = sweep3d.GridSpec()
grid_spec.resolution = [8, 8, 8]
grid_spec.bbox_min = [-0.5, -0.5, -0.5]
grid_spec.bbox_max = [1.5, 1.5, 1.5]

# Configure sweep options
options = sweep3d.SweepOptions()
options.epsilon_env = 1e-3
options.epsilon_sil = 1e-3
options.with_insideness_check = False
options.max_split = 1000000

# Compute sweep
result = sweep3d.generalized_sweep(my_function, grid_spec, options)

grid:
    resolution: [8, 8, 8]
    bbox_min: [-0.5, -0.5, -0.5]
    bbox_max: [1.5, 1.5, 1.5]

parameters:
    epsilon_env: 1e-3
    epsilon_sil: 1e-3
    with_insideness_check: false
    max_split: 1000000