Preface

Overview

In recent years , methods from computational geometry have been widely adopted by the computer graphics community, yielding elegant and efficient algorithms. This book aims at endowing practitioners in the computer graphics field with a working knowledge of a wide range of geometric data structures from computational geometry. It will enable readers to recognize geometric problems and select the most suitable data structure when developing computer graphics algorithms.

The book will focus on algorithms and data structures that have proven to be versatile, efficient, fundamental, and easy to implement. Thus practitioners and researchers will benefit immediately from this book in their everyday work.

Our goal is to familiarize practitioners and researchers in computer graphics with some very versatile and ubiquitous geometric data structures, enable them to readily recognize geometric problems during their work, modify the algorithms to their needs, and hopefully make them curious about further powerful treasures to be discovered in the area of computational geometry.

In order to achieve these goals in an engaging yet sound manner, the general concept throughout the book is to present each geometric data structure in the following way: first, the data strucure will be defined and described in detail; then, some of its fundamental properties will be highlighted; after that, one or more computational geometry algorithms based on the data structure will be presented; and finally, a number of recent, representative, and practically relevant algorithms from computer graphics will be described in detail, showing the utilization of the data structure in a creative and enlightening way.

We do not try to provide an exhaustive survey of the topics touched upon herethis would be far beyond the scope of this book. Neither do we aspire to present the latest and greatest algorithms for a given problem, for two reasons. First, the focus is on geometric data structures, and we do not want to obstruct the view with complicated algorithms. Second, we feel that, for practical purposes, a good trade-off between simplicity and efficiency is important.

The intended audience is practitioners working in 3D computer graphics (VR, CAD/CAM, entertainment, animation, etc.) and students of both computer graphics and computational geometry. Readers should be familiar with the basic principles of computer graphics and the type of problems in the area.

We have arranged the chapters in roughly increasing degree of difficulty. The hierarchical data structures are ordered by increasing flexibility, while the non-hierarchical chapters build on each other. Finally, the last three chapters present generic techniques for making geometric data structures kinetic, robust, and dynamic.

Figure provides an overview of some of the data structures that will be discussed in the following chapters. Chapter 1 presents quadtrees and octrees, which are, arguably, the most popular data structure in computer graphics. Lifting one of the restrictions, thus making the data structure more flexible, we arrive at kd-trees, which are presented in Chapter 2. We can make this even more flexible, yielding BSP trees, discussed in Chapter 3. From kd-trees , we can also derive bounding volume hierarchies, which are described in Chapter 4. Starting with a quadtree (or even a grid), we can store more information about the object(s), thus arriving at distance fields (Chapter 5). In a sense, distance fields are a discretized version of Voronoi diagrams, which are presented in Chapter 6. In Chapter 7, we discuss the general class of geometric proximity graphs, one kind of which, the Delaunay graph, we have already seen in Chapter 6. The general concept of specialized spatial data structures for moving objects is introduced in Chapter 8 and discussed by an example. In Chapter 9, we consider the problems of degeneracy and robustness in geometric computing. finally, in Chapter 10, we introduce a simple generic scheme for dynamization.