Authors
Rita Borgo
David Duke
Colin Runciman
Malcolm Wallace
Abstract
‘Marching Cubes’ is but the most well known member of a large family of algorithms that approximate n-dimensional surfaces through substitope approximations with a range of cell geometries. This poster reports on work in which a novel mathematical view of cells is being used to tease out the common basis of these algorithms and capture this as a single instance of a generic programming scheme, from which any member of this family can then be instantiated automatically and on demand. By relating cells and vertex colouring to symmetric and permutation groups, work by Hege [4] and Banks et al. [3] identified an intriguing link between visualization algorithms and results from algebraic combinatorics. We are building on this work in two ways. First, we utilise a combinatorial construction that provides a simple, expressive language for cell geometry and symmetries. Second, using advances in generic programming recently developed within functional programming systems, we are developing an implementation for surface fitting in which the combinatorial model allows us to generate instances of a generic algorithm appropriate to the geometric organization of a given data set.
Index Terms
F.3.3 [Logics and Meaning of Programs]: Studies of Program Constructs—Functional Constructs; I.3.5 [Computational Geometry and Object Modeling]: Curve, surface, solid, and object representations— Geometric algorithms, languages, and systems