Bézier AwardTitle SMAA. A. G. Requicha and H. Voelcker

bezier-award-pic-2007-1bezier-award-pic-2007-2A. A. G. Requicha and H. Voelcker, the 2007 Pierre Bézier Award Recipients

Requicha and Voelcker co-led the Production Automation Project (PAP) at the University of Rochester from the early 1970s to the mid 1980s. The PAP was the premier academic group working in what became known as solid modeling. They established most of the theoretical foundations for the field, by using point-set and algebraic topology and introducing a simple but effective formulation that gave precise mathematical meaning to such notions as validity of representations and correctness of algorithms for solid modeling. They showed that the topological concepts of set regularity and neighborhoods could be used to design algorithms that did not suffer from the “pathologies” encountered in earlier work.

These algorithms were embodied in the PADL-1 system developed at the PAP in the early 1970s, which was the first to demonstrate correct handling of Boolean operations for objects with overlapping boundaries. Set membership classification emerged as an important concept, which generalized such operations as point inclusion and clipping, and proved to be relevant to many geometrical computations. Other interesting and general concepts were those of structural and spatial locality, which led to many algorithm simplifications and speed-ups.

The PAP group developed a host of algorithms and techniques for solid modeling and its applications, which included: set membership classification; Boolean operations; conversion of CSG representations to octrees; piecewise circular approximations for surface intersections; solid offsetting, Minkowski and blending operations; mass property calculation; null-object detection and interference analysis; efficient ray casting; and direct generation of shaded displays from CSG by depth buffering. The group implemented these algorithms in their PADL-1 and PADL-2 systems. PADL-2 was a production-grade core modeler that pioneered representations for “generic objects”, i.e., parameterized part families with parameters constrained through symbolic expressions. The PADL systems were disseminated widely, especially to other university groups. PADL-2 became the core of several early commercial systems. The PAP was also the first group to look carefully at the semantics of tolerancing specifications, and proposed a theory based on notions of offsetting and Minkowski operations to capture mathematically the concepts embodied in tolerancing standards. This work was influential and impacted not only theory and algorithm development but also the new versions of the standards themselves.

In the mid 1980s the PAP group split (amicably), with Requicha becoming a Professor of Computer Science at USC and Voelcker a Professor of Mechanical Engineering at Cornell. Requicha led the Programmable Automation Laboratory (PAL) at USC until recently. PAL focused on applications of solid modeling to automation of manufacturing and inspection operations, and also worked on the difficult problem of robust geometrical computation. In a series of student theses, the lab attacked the problems of recognition of (possibly interacting) machinable features, automatic fixturing, and CMM (Coordinate Measuring Machine) inspection. This work culminated in Steven Spitz’s elegant thesis on automatic inspection, which cleverly used computer graphics hardware for accessibility analysis. In the mid 1990s Requicha launched new research on nanorobotics that is not related to solid modeling. However, very recently he has been working on the construction of arbitrary shapes by robotic self-assembly. This is ambitious and futuristic work, but it may prove important when nano or micro robots will become widely available. In a sense, it is a return to solid modeling but from a very different perspective. Requicha is listed in Thomson’s ISI Web of Knowledge (2006) as a highly cited researcher for the years 1981-1999. (Out of a total of 280 in Computer Science, worldwide.)

Requicha and Voelcker’s contribution to solid modeling education has been large and important. Through regular courses (at Rochester, USC and Cornell), tutorials (at many conferences), a series of papers, and web material, they have set forth the basic concepts of solid modeling as we know them today. Perhaps even more important has been the training of a cadre of graduate students, several of whom have become leaders in the solid modeling field. This is a major and lasting contribution to solid modeling. In short, Requicha and Voelcker are true solid modeling pioneers, who shaped the field. Their research and education efforts will be felt for years to come.

INTERIA Web Design & Development