Subdivision as a Fundamental Building Block of Digital Geometry Processing Algorithms

Abstract

Multi media data types such as digital sound, images, and video are now ubiquitous in all areas of computing and daily life. This wide impact was made possible by a number of factors. A key factor in the wide use of a given data type is the ease and economy of acquiring it. Using a rough time line one can observe that this was true for sound in the 70s, images in the 80s, and finally video in the 90s, roughly following the development of computing hardware with its ever increasing cpu and memory resources (Figure 1). Another key factor in the wide use of a given data type is the existence of efficient algorithms for creation, storage, transmission, editing and other manipulations of the data. The mathematical foundation for these algorithms has for a very long time rested on sampling and associated Fourier techniques. Even more recent developments, such as the use of wavelets for image and video compression still rest upon the foundation laid by Fourier analysis. As such, these methods now codified as “Digital Signal Processing” (DSP) have been extraordinarily successful impacting areas ranging from cheap consumer devices such as cell phones and MP3 players to high end scientific computing applications solving some of today’s most demanding PDEs, for example.