Crystallographic lattices are nature's way to partition space into uniform cells with high symmetry. The equilateral triangulation of the plane, the face-centered and the body-centered cubic lattice in 3D and the lattice based on the 24-cell in 4D, all partition space more isotropically than the commonly-used Cartesian grid. Higher isotropy means higher efficiency, in that sparser data allows reproducing the same functions as data on the Cartesian grid. To take advantage of this increased efficiency, for material, medical, biological and even algebraic computations, we need to explore and make practically accessible multi-variate `crystallographic' splines that honor the structure of the crystallographic lattices.

With emphasis on dimensions 3 through 8, where the number of spline coefficients is still manageable, this research seeks to derive efficient analogues of the computational tools, data structures and algorithms that are currently available only for tensor-product splines on Cartesian grids. This includes algorithms and data structures to support quasi-interpolation for reconstruction, evaluation of functionals, refinement and adaptive subdivision, multi-resolution in the presence of singularities, conversion to localized polynomial form, and treatment of structural singularities. As proof of concept and extensions in their own right, these tools will be tested on multi-variate algebraic real-root finding, error-bounded approximation of level-sets, generalized subdivision and the computational formulation of partial differential equations.

Dissemination of the underlying theory, algorithms and coded examples will lower the barrier for the use of crystallographic splines and thereby enable more efficient computing for simulation and modeling. Progress in real root finding will benefit applications from geometric constraint solving to charting molecular conformation spaces. Finite elements based on crystallographic splines will honor boundary data when solving differential equations on crystallographic lattices. The impressive structure of crystallographic lattices will engage undergraduate and graduate students in digital arts and computer graphics classes; and videos of volumetric fly-throughs and projections from higher dimensions will make this research accessible to the wider public.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1117695
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2011-09-01
Budget End
2014-08-31
Support Year
Fiscal Year
2011
Total Cost
$439,121
Indirect Cost
Name
University of Florida
Department
Type
DUNS #
City
Gainesville
State
FL
Country
United States
Zip Code
32611