Robust Computation of Implicit Surface Networks for Piecewise Linear Functions

Xingyi Du, Qingnan Zhou, Nathan Carr, Tao Ju
ACM Transaction on Graphics (Proceedings of SIGGRAPH 2022)

Project Page

Build

Use the following commands to build on Mac.

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

Program impl_arrangement and material_interface will be generated in the build subdirectory.

Usage

impl_arrangement

The program creates a polygonal mesh discretization of the implicit arrangement of a collection of implicit functions on a given tetrahedron grid.

Usage:

./impl_arrangement [OPTIONS] config_file

Options:

• -h,--help: Print help message and exit.
• -T,--timing-only: When set, the program only records timing without saving results.
• -R,--robust-test: When set, the program performs robustness test. The program will run twice with different ordering of input functions, and check if the results are consistent.

Positionals:

• config_file (REQUIRED): Configuration file, specifying input/output paths and algorithm parameters.

The config_file should be a JSON file with the following named parameters:

• tetMeshFile: Path to the file storing input tetrahedral grid. It is a JSON file storing vertex coordinates and tetrahedrons. See examples/tet_mesh/tet5_grid_10k.json for a concrete example.
• funcFile: Path to the file storing input implicit functions. See this repo for details about the file format.
• outputDir: Path to the directory to store output files.
• useLookup: Whether to use look-up tables to accelerate tetrahedron processing (section 6 of our paper). Default value is "true".
• useSecondaryLookup: Whether to use look-up tables for tetrahedral with two active functions (section 6 of our paper). Default value is "true".
• useTopoRayShooting: Whether to use topological ray shooting to compute the spatial decomposition induced by the arrangement (section 7 of our paper). Default value is "true".

Note that tetMeshFile, funcFile and outputDir can be either absolute or relative paths. In the case of relative paths, they are relative with respect to the directory containing the configuration file.

An example config file is examples/implicit_arrangement/config.json.

Test:

compute implicit arrangement

./impl_arrangement ../examples/implicit_arrangement/config.json

record timing without saving results

./impl_arrangement -T ../examples/implicit_arrangement/config.json

perform robustness test

./impl_arrangement -R ../examples/implicit_arrangement/config.json

material_interface

The program creates a polygonal mesh discretization of the material interfaces of a collection of material functions on a given tetrahedron grid.

Usage:

./material_interface [OPTIONS] config_file

Options:

• -h,--help: Print help message and exit.
• -T,--timing-only: When set, the program only records timing without saving results.
• -R,--robust-test: When set, the program performs robustness test. The program will run twice with different ordering of input functions, and check if the results are consistent.

Positionals:

• config_file (REQUIRED): Configuration file, specifying input/output paths and algorithm parameters.

The config_file should be a JSON file with the following named parameters:

• tetMeshFile: Path to the file storing input tetrahedral grid. It is a JSON file storing vertex coordinates and tetrahedrons. See examples/tet_mesh/tet5_grid_10k.json for a concrete example.
• funcFile: Path to the file storing input material functions. See this repo for details about the file format.
• outputDir: Path to the directory to store output files.
• useLookup: Whether to use look-up tables to accelerate tetrahedron processing (section 6 of our paper). Default value is "true".
• useSecondaryLookup: Whether to use look-up tables for tetrahedral with three active functions (section 6 of our paper). Default value is "true".
• useTopoRayShooting: Whether to use topological ray shooting to compute the spatial decomposition induced by the material interfaces (section 7 of our paper). Default value is "true".

Note that tetMeshFile, funcFile and outputDir can be either absolute or relative paths. In the case of relative paths, they are relative with respect to the directory containing the configuration file.

An example config file is examples/material_interface/config.json.

Test:

compute material interface

./material_interface ../examples/material_interface/config.json

record timing without saving results

./material_interface -T ../examples/material_interface/config.json

perform robustness test

./material_interface -R ../examples/material_interface/config.json

Output

The complete set of output files include data files (mesh.json, mesh_patches.msh, mesh_chains.msh and mesh_cells.msh) and information files (timings.json and stats.json). In timing-only mode (-T), the program only generates information files. In robustness test mode (-R), no output files are generated. The result of the robustness test is in command line output.

data files

mesh.json: JSON file storing the following key-value pairs

key	value	description
points	#Vx3 matrix of double numbers	Vertex coordinates of the surface network mesh.
faces	vector of vector of integers	Polygonal faces of the surface network mesh. Each face is encoded by a vector of indices of face boundary vertices.
edges	#Ex2 matrix of integers	Edges of the surface network mesh. Each edge is encoded by a pair of vertex indices.
chains	vector of vector of integers	Chains of non-manifold edges. Each chain is encoded by a vector of edge indices.
corners	vector of integers	Indices of non-manifold vertices.
patches	vector of vector of integers	A patch is a connected component of faces bounded by non-manifold edges. Each patch is encoded by a vector of face indices.
shells	vector of vector of integers	A shell is a connected component of the boundary of a 3D region partitioned by the surface network. Each shell is encoded by a vector of oriented patch indices. The positive side of patch i has index 2i. The negative side of patch i has index 2i+1.
cells	vector of vector of integers	A cell is a 3D region partitioned by the surface network. Each cell is encoded by a vector of shell indices.

Note: all indices start from 0.

mesh_patches.msh, mesh_chains.msh and mesh_cells.msh store the same data as chains, patches and cells in mesh.json, but in MSH format. We can view these MSH files using Gmsh.

information files

timing.json: timing of different stages of our pipeline.

stats.json: statistics of intermediate data in our pipeline, e.g., number of surface network mesh vertices.