High Performance Digital Geometry Processing

Leader of the group: Dr. Rhaleb Zayer

Vision and Research Strategy

The thrust behind our research effort is to rethink solution development with parallelism built-in from the ground up as opposed to the current trend of looking at parallelization as a mere post processing step left for “Ninja coders” or automatic optimization software. We examine the whole solution development pipeline (problem abstraction, data structures, mathematical modeling, and implementation), with the goal of producing simple yet streamlined solutions capable of unleashing the computational power afforded by modern hardware. Our efforts are guided by parsimonious memory usage, improved memory access patterns, and cache performance. To avoid data redundancy, we target seamless transition between data traversal and numerics as it is a valuable asset for coding convenience and enhanced performance. In view of the rapidly growing field of machine learning, particular attention is paid to data-driven modeling.

Research Areas and Achievements

The research within the group targets three complementary areas: data structures, numerical kernels, and applications.

Data structures. A key idea behind our research strategy is to channel parallelism through linear algebra kernels. For unstructured data representations, e.g. meshes, we seek lean sparse matrix representations which can be endowed with specialized functions, aka, action maps, which symbolically augment standard sparse linear algebra kernels to perform both traversal and numerical computations. We have readily demonstrated the potential of these representations on the Graphics Processing Unit (GPU) and our current focus is on multicore systems and on tailoring specialized versions for handling localized dynamic changes efficiently.

Numerical kernels. Although efficient sparse matrix linear algebra kernels exist for different hardware architectures, e.g., Intel MKL and Nvidia cuSPARSE, these closed source libraries focus on standard algebra primitives. In our formalization, high performance digital geometry processing tasks require a sequence of matrix operations, often operate locally on data, and introduce connectivity changes. These operations pose new challenges and prompt us to develop specialized sparse matrix linear algebra formulations which can account, among other things, for the fusion of successive matrix operations, cache locality and fast on-chip memory when performing localized operations.

Applications. We target and re-abstract some of the most commonly used and far reaching applications across various fields. All of which are believed to be hard to parallelize.
In computer graphics, we addressed the problem of subdivision surfaces, a widely used modeling paradigm where an extremely simple polygonal shape representation is enriched throughout a combination of vertex insertions and smoothing iterations, yielding visually pleasant meshes suitable for use in production. Our solution largely outperform OpenSubdiv, commonly recognized as the industry standard.
In meshing, we have targeted the generation of Voronoi diagrams on surfaces. Voronoi Diagrams are a common theme across several disciplines and are arguably one the most studied problems in computational geometry. Their extension to the surface setting further complicates vectorization as metric estimation poses serious challenges. We continue our research in this direction by further exploring anisotropy and density control.
In numerical simulation, we focus on the whole pipeline from finite elements assembly to numerical solution strategies. Numerical evidence suggests that the assembly problem weighs heavily on performance and impedes scalability. Across all these application, we broke the high performance deadlock throughout novel geometric and numerical abstractions and we have shown that it is possible to eliminate the unpleasant idle-time modelers and engineers spend waiting before seeing the outcome of their modeling and simulation efforts.
In additive manufacturing, We believe that design is mostly driven by aesthetics and is influenced by the designer’s inspiration, which is not always easily amenable to a mathematical formulation, as for instance, in topology optimization. Therefore we seek to provide designers and practitioners with interactive modeling tools such as our modular approach for creating and editing Voronoi-like cellular structures on surfaces. We are currently developing surface based topology optimization techniques that allow the designer to freely control the overall shape whereas the optimization figures out where to cut corners for optimal cost.