Representation Schemes and Impact on Algorithms

This chapter develops formal concepts of complete representation schemes, and explains the two - Constructive Solid Geometry (CSG) and Boundary representation (Brep) - that are used most frequently. Auxiliary representations, computed typically from complete representations, are used to support a variety of applications. The chapter explains the theory of two closely related auxiliary representations - z-buffers and ray-reps - that are used frequently in computer graphics and gometric modeling applications respectively. A case study of a particular parallel hardware architecture - the RayCasting Enginer (RCE) - is presented as a contrast to contemporary polygon-pushing based 3D graphics hardware; the RCE processes CSG of implicit quadratics to produce ray-reps, while polygon-pushers process (loosely) Breps of linear polyedra to produce z-buffers. The chapter concludes with a plethora of applications supported with ray-reps, and two specific case studies - one for Numerical Control (NC) machining and another for molecular modelig in chemistry.