Fast and Exact Fiber Surfaces for Tetrahedral Meshes

Pavol Klacansky (SCI, Leeds), Julien Tierny (CNRS), Hamish Carr (Leeds), and Zhao Geng (Leeds)

Isosurface and Fiber Surface

Domain (3D)
Range (2D)

Terminology

Fiber and Fiber Surface

Domain (2D)
Range (2D)
For simplicity we choose to use 2D domain to explain the concept of fiber and fiber surface. Above on the left we have domain with two fields (e.g. temperature and pressure). On the right is the range.

For given isovalue we get level set, and if we pick two isovalues (point in range), the intersection of the corresponding level sets is a fiber.

Furthermore, we can pick a connected set of points in range, constructing a connected set of fibers in domain - fiber surface.

Approximation using Marching Cubes

Fiber Surfaces: Generalizing Isosurfaces to Bivariate Data, Carr et al.
Domain (2D)
Range (2D)

We note that the original paper presented accurate algorithm for tet-meshes (albeit not the gray cases) for base fiber surface extraction. However it was limited to lines.

Marching cubes is already inaccurate even for an isosurfaces.

Motivation

Original* algorithm (c), (d) and ours (e),
Two problems: a) make it correct, b) make it fast.

We focus on tetrahedral mesh, for trilinear refer to Kui's talk.

FSCP Bends

Top range, bottom domain.

New Algorithm: Base Fiber Surface

Domain (3D)
Range (2D)

New Algorithm: Fiber Clipping

Domain (3D)
Range (2D)

Six Fiber Clipping Cases

Green lines are fibers.

Fiber Surface Example

Domain (3D)
Range (2D)

Acceleration

  • Domain or range space
  • Output sensitive
Parallel scaling.
Similarly to marching tetrahedra, our algorithm is data parallel and has only constant time overhead.

Instead of subdividing the domain, we can think of each cell's prejection in the range. One approach could be to take min-max of both field and think of it as a point in 4D. Instead, we think of it as a bounding box on the range and use a variant of interval tree (BVH).

We allow to tweak arity and number of cells per leaf. Both are trade-off between speed, construction time, and memory usage. We choose 8-nary tree (AVX) with 8 tets per leaf.

Results

Octree
Bounding volume hierarchy

Interactive Application

The ability to extract fiber surface per line segment allows us to use different colors and in most cases we need to extract only two surfaces (as user usually moves one point at the time).

Furthermore, we use glClipPlane for clipping using t line parameter (which is anyway needed for fiber texturing).

Summary (klacansky.com/fsvis16)

Acknowledgements:
  • EPSRC grant EP/J013072/1 (Leeds)
  • LABEX Cal-simlab ANR-11-LABX-0037-01 and DGA DT-SCAT-DA-IDFFD1300034MNRBC (UMPC)
  • University of Utah's SCI Institute

Questions

Quantitative Comparison

Raster ResolutionTime (s)Hausdorff Distance (%)Average Distance (%)
1620.565.270.66
3220.523.000.20
6420.521.750.08
12820.541.260.04
25620.591.210.03
51220.801.030.02
102421.641.010.02
Exact distance3.471.010.02
Comparison of ethanediol fiber surface quality (MT used for both). The percentage is of bounding box diagonal.

Qualitative Comparison

Left FSPC, middle original*, and right ours.

Trilinear Limitation

Multiple fibers in a cube.