Source-linked AI summary
Combinatorial maps for hierarchical splines
Caleb B. Goates, Kendrick M. Shepherd, Derek C. Thomas
TL;DR
Hierarchical spline formulations commonly omit Bézier-mesh topology, limiting scalable adjacency-based operations. This paper constructs hierarchical combinatorial maps for conforming cubical refinement meshes and demonstrates faster level-set extraction, including a 7.5-fold reduction in function evaluations. The approach is most suitable when refinement levels can be represented implicitly.
Problem
Typical hierarchical spline representations store elements without adjacency information, although Bézier-mesh topology is useful for scalable postprocessing and adaptivity.
Method
The paper constructs hierarchical combinatorial maps from implicitly represented maps of nested spline-space Bézier meshes over cubical cells with conforming refinement-level meshes.
Results
7.5 times fewer function evaluations were required for level-set construction with topological information, producing a watertight polygonal surface; local flood took less than one tenth of marching cubes time.
Takeaways & Limitations
The resulting topological information supports faster downstream hierarchical-spline operations, demonstrated through watertight level-set extraction.
Takeaways & Limitations
The algorithm is particularly appropriate when global refinement levels are represented implicitly; explicit refinement levels would increase memory use beyond a globally refined mesh.
Abstract
from arXiv · showhide
Hierarchical splines are an important part of multiscale and adaptive isogeometric analysis formulations. The Bézier meshes of these splines are an essential part of their definition and of several important hierarchical spline algorithms, such as adaptive refinement and Bézier extraction. Topological data associated with the Bézier mesh-such as adjacency information-can be used to improve the performance of many of these algorithms as well as downstream applications of the splines, but typical hierarchical spline formulations do not compute the topological data, storing instead just a list of elements. In this work we present algorithms to build a performant topological data structure, namely the combinatorial map, to represent Bézier meshes of hierarchical splines over cubical cell complexes where the refinement levels have conforming Bézier meshes. This includes hierarchical and truncated hierarchical B-splines, as well as subsets of other hierarchical spline formulations. We show the performance characteristics of the construction algorithms of these hierarchical combinatorial maps, as well as an example use case, showing that the topological information can provide up to an order of magnitude reduction in computation time in downstream applications of the splines.
1 Introduction
Hierarchical spline methods support adaptive isogeometric analysis, but their usual element-only representations omit topology needed for scalable neighborhood operations. This work introduces hierarchical combinatorial-map construction algorithms for conforming Bézier meshes and demonstrates downstream speedups.
- Hierarchical B-spline variants provide adaptive-resolution bases for isogeometric analysis, whose elements form Bézier meshes with associated topology.
- Existing hierarchical spline representations generally store final elements without adjacency information, limiting scalable topological operations for postprocessing and adaptivity.
- Combinatorial maps offer lightweight, navigable topology for oriented n-dimensional domains and support neighborhood traversal in time linear in neighborhood size.
- Prior subdivision-surface, quadtree, and octree combinatorial-map algorithms are not straightforward to apply when hierarchical refinement repeatedly updates spline element meshes.
- The paper proposes construction algorithms for combinatorial maps representing hierarchical-spline Bézier meshes over cubical cells with conforming refinement-level meshes.
- The paper presents low-memory global refinement maps and algorithms for constructing hierarchical maps, then evaluates construction scaling and downstream use.
2 Background
The paper develops the combinatorial-map and B-spline concepts underlying hierarchical spline meshes. It focuses on conforming refinement-level Bézier meshes while exploiting implicit cubical-mesh structure for memory efficiency.
- 2.1 Combinatorial Maps: A combinatorial map represents a mesh with abstract darts, each encoding adjacent cells across dimensions greater than zero and relations for dart traversal.
- 2.1 Combinatorial Maps: The ϕ_i operators navigate a combinatorial map by shifting the originating vertex and the i-dimensional cell while leaving other cells unchanged.
- 2.1 Combinatorial Maps: Combinatorial maps store topology separately from geometry, allowing data associated with cells to be layered onto the map.
- 2.1 Combinatorial Maps: Adjacency and neighborhood traversal can be computed with time linear in the size of the traversed neighborhood.
- 2.1 Combinatorial Maps: The implementation uses implicitly represented combinatorial maps for global quadrilateral and hexahedral refinement levels to reduce storage.
- 2.2 B-Splines: A B-spline basis is defined from a polynomial degree and a non-decreasing knot vector, with higher-dimensional bases formed by tensor products.
- 2.2 B-Splines: The underlying Bézier mesh is formed by non-zero knot intervals, and the hierarchical construction algorithm applies when refinement-level meshes are conforming and have no T-junctions.
- 2.2 B-Splines: Hierarchical and truncated hierarchical B-splines share the same Bézier mesh, while the final hierarchical mesh can contain T-junctions despite conforming meshes at each level.
3 Data Structures
The data-structure approach makes hierarchical combinatorial-map construction feasible by first using implicit maps for the nested spline-space Bézier meshes.
- The proposed construction algorithms build hierarchical combinatorial maps from implicitly represented maps of nested spline-space Bézier meshes.
3.1 Refinement Levels
The paper constructs hierarchical combinatorial maps from low-memory tensor-product maps, representing cubical Bézier meshes and their connectivity across refinement levels and patches.
- Tensor-product construction: Higher-dimensional tensor-product maps are built from one-dimensional maps, with each dart indexed by a base dart, line dart, and orientation parameter.For dimension n, each base-line pair corresponds to 2^n darts arranged by dimension-specific templates.
- Tensor-product construction: The tensor-product templates implicitly represent four two-dimensional darts and twenty-four three-dimensional darts through lower-dimensional representative darts.In three dimensions, four two-dimensional representative darts generate the associated volume darts and encode subsets of the ϕ operations.
- Tensor-product construction: Connectivity operations move between component maps and permute the orientation parameter according to the consistent cell orientation of structured meshes.Algorithms define ϕ2 operations in two dimensions and ϕ3 operations in three dimensions using these component-map operations and permutations.
- Low-memory representation: The resulting refinement-level maps require only one-dimensional map sizes, periodicity flags, and static permutation arrays, rather than full operation arrays.This constant storage with respect to mesh density permits storing the full mesh at each refinement level with substantially lower memory use.
- Hierarchical construction: Hierarchical construction combines refinement-level maps with routines that locate lower-level ancestors and iterate higher-level descendants.These operations support building the hierarchical map over nested spline spaces.
- Multi-patch construction: Multi-patch maps flatten patch-local darts into a common index space and encode inter-patch ϕn connections through boundary projection, permutation, and lifting.Each connection is stored twice for lookup, and the patches must meet along complete parametric sides of conforming quadrilateral or hexahedral regions.
3.2 Hierarchical
The hierarchical combinatorial map Ch is assembled from nested refinement-level maps by selecting leaf-related darts and storing cross-level adjacency operations. Its bitmap-based representation supports construction from leaf elements and incremental adaptive updates.
- Hierarchical C-map: Ch represents hierarchical B-spline Bézier meshes by combining subsets of darts from refinement-level combinatorial maps.It applies to hierarchical and truncated hierarchical B-splines and to conforming quadrilateral or hexahedral Bézier meshes.
- Dart indexing: Non-contiguous dart indexing maps refinement-level darts into a shared hierarchical index space.The mapping uses sorted partial sums and an O(log nℓ) search, which is essentially constant-time with respect to mesh size because nℓ ≪ |Ch|.
- Leaf-dart representation: Bitmaps BL and BU distinguish darts present in Ch from darts belonging to leaf elements.Algorithm 5 adds leaf-element darts, includes relevant neighboring darts, and removes BL entries whose descendants are present.
- Cross-level adjacency: A bidirectional map stores the exceptional ϕ1 and ϕ−1 operations that differ from refinement-level operations.These explicit operations are computed by algorithm 6; other ϕ operations are composed with operations in the underlying refinement level.
- Memory and updates: The full structure uses at most n × np × nℓ one-dimensional combinatorial maps plus offsets, interpatch connections, bitmaps, and a bidirectional map.The bitmaps and bidirectional map typically dominate memory usage, while Roaring Bitmaps can reduce bitmap storage.
- Memory and updates: Adaptive refinement can update algorithms 5 and 6 without rebuilding the hierarchical combinatorial map from scratch.Updates remove obsolete leaf darts and descendants and adjust the stored cross-level operations.
4 Evaluation
The evaluation measures construction scaling and applies the hierarchical combinatorial map to level-set extraction on a refined truncated hierarchical B-spline mesh. Topological adjacency yields watertight surfaces and substantially reduces evaluations and runtime relative to marching cubes.
- 4.1 Scaling: Algorithm 6 scales with the number of hierarchical elements containing darts from multiple refinement levels.Its main work depends on elements not skipped by the algorithm’s short-circuit condition, while algorithm 5 remains constant when |Ch| is fixed.
- 4.1 Scaling: Algorithm 5 scales roughly as O(|Ch|) when the number of leaf elements increases under global refinement.The benchmark varies nℓ from two to 14 levels, with |Ch| scaling from 2^2 to 2^26.
- 4.2 Application to Level Set Extraction: The level-set benchmark uses a three-dimensional truncated hierarchical B-spline basis with a trilinear-per-element approximation and at most one intersection per face.The extracted target is the 0.15 level set, triangulated from edge intersections.
- 4.2 Application to Level Set Extraction: Topological extraction reuses each vertex function value and constructs the surface from intersected edges, adjacent faces, and boundary edges.This handles T-junctions that prevent standard marching-cubes templates from directly producing the hierarchical surface.
- 4.2 Application to Level Set Extraction: The topologically informed surfaces are watertight, whereas marching cubes produces gaps at coarse-to-fine transitions.The surface is unchanged by using local flood optimization rather than checking the entire mesh.
- 4.2 Application to Level Set Extraction: 7.5 times fewer function evaluations and 3.95 times fewer vertex position evaluations are required with topological information than with marching cubes.Local flooding reduces function evaluations by another factor of 6.7, exceeding a 50 times total reduction relative to marching cubes.
- 4.2 Application to Level Set Extraction: The local flood approach takes less than one tenth the time of marching cubes, while global topological extraction takes less than one third.The comparison uses a performant marching-cubes implementation, while the topological algorithm has not had extensive speed optimization.
5 Conclusions
The paper presents construction algorithms for hierarchical combinatorial maps and demonstrates their scaling and use in watertight level-set extraction. The approach is most suitable when refinement levels can be represented implicitly.
- Contributions: The work provides construction algorithms for combinatorial maps representing Bézier meshes of hierarchical and other hierarchical splines.The authors state that a hierarchical-spline combinatorial-map construction routine had not previously been published to their knowledge.
- Contributions: The algorithms operate directly from leaf elements, use implicitly defined refinement levels, and support updates during adaptive refinement.The resulting map was demonstrated for extracting a watertight level set.
- Scope boundary: The method is particularly appropriate when global refinement levels can be represented implicitly.Explicitly representing those levels can make memory use worse than that of a globally refined mesh.
Appendix A Failure of the algorithms on a non-conforming B´ezier mesh
Algorithms 5 and 6 can construct incorrect topology when refinement levels lack conforming Bézier meshes. In the illustrated case, the final combinatorial map contains a hanging vertex absent from the hierarchical Bézier mesh.
- Algorithms 5 and 6 may fail to create the correct topology when the refinement levels have non-conforming Bézier meshes.
- In the example, the first refinement level contains a three-face T-junction, while the second is its dyadic refinement.
- Algorithm 5 marks selected darts from both refinement levels as leaf, then unmarks level-0 darts whose descendants were made leaf.
- The resulting combinatorial map contains a highlighted hanging vertex that represents no vertex in the hierarchical Bézier mesh.