Computational geometry involves the development of algorithms and data structures for computing geometric objects and their attributes. Our focus in this area includes the closely related fields of curve and surface fitting, triangulation, Voronoi diagrams, and grid generation. Computations involving complex geometries are becoming an increasingly important aspect of NIST efforts in metrology
ARPA supports several projects producing advanced distributed simulations of battlefields for training and orientation. Christoph Witzgall, Javier Bernal, and Marjorie McClain, in collaboration with Douglas Shier of Clemson University and ACMD, are providing crucial surface representations for the simulation systems. Their work emphasizes the rendering of surface features, such as drain lines, lake shores, and roadbeds. The capability to perform the necessary surface representation is the result of several years of research; it is based on a feature-preserving variant of Delaunay triangulation developed by Bernal.
There are more than 20,000 coordinate measuring machines (CMMs) in U.S. industry today, and their use is rapidly growing. A CMM is basically a robotic machine that measures the dimensions of a part using a three-dimensional coordinate system. Currently there is no rigorous methodology to derive the accuracy and precision of a measurement from a CMM. Developing such a calibration methodology would promote improvements in quality and productivity through better determination of part dimensions. As part of a NIST competency project, Marjorie McClain and Christoph Witzgall are playing an active role in an inter-laboratory group that is making significant progress on the problem.
Efficient large-scale numerical simulations require suitable nonuniform grids. William Mitchell has developed an adaptive grid generation method as part of his multigrid code, MGGHAT (MultiGrid Galerkin Hierarchical Adaptive Triangles). This general-purpose code is now in widespread use and is available via netlib; a parallel version is under development. Bonita Saunders has developed a curvilinear coordinate system defined by a tensor-product grid mapping using cubic B-splines. She is applying this work to produce an adaptive mesh system for a directional solidification problem.