Point-Based Graphics

Markus Gross, Hanspeter Pfister

• Publisher: Morgan Kaufmann
• Year: 2011
• Print ISBN: 9780123706041
• eBook ISBN: 9780080548821
• Topic: Computer Science
• Subtopic: Computer Graphics
• Index: Computer Science

The polygon-mesh approach to 3D modeling was a huge advance, but today its limitations are clear. Longer render times for increasingly complex images effectively cap image complexity, or else stretch budgets and schedules to the breaking point. Comprised of contributions from leaders in the development and application of this technology, Point-Based Graphics examines it from all angles, beginning with the way in which the latest photographic and scanning devices have enabled modeling based on true geometry, rather than appearance. From there, it's on to the methods themselves. Even though point-based graphics is in its infancy, practitioners have already established many effective, economical techniques for achieving all the major effects associated with traditional 3D Modeling and rendering. You'll learn to apply these techniques, and you'll also learn how to create your own. The final chapter demonstrates how to do this using Pointshop3D, an open-source tool for developing new point-based algorithms. - The first book on a major development in computer graphics by the pioneers in the field - Shows how 3D images can be manipulated as easily as 2D images are with Photoshop

1

INTRODUCTION

Gross Markus, Computer Graphics Laboratory, ETH Zürich, Haldeneggsteig4/Weinbergstrasse, CH - 8092 Zürich, Tel: [phone], Fax: [phone]. E-mail address: [email protected]

Pfister Hanspeter, MERL - Mitsubishi Electric Research Laboratories, 201 Broadway, Cambridge, MA 02139, USA, Tel: [phone], Fax: [phone]. E-mail address: [email protected]

1.1

OVERVIEW

Markus Gross and Hanspeter Pfister

Point primitives have experienced a major renaissance in recent years, and considerable research has been devoted to the efficient representation, modeling, processing, and rendering of point-sampled geometry. There are two main reasons for this new interest in points: on one hand, we have witnessed a dramatic increase in the polygonal complexity of computer graphics models. The overhead of managing, processing, and manipulating very large polygonal-mesh connectivity information has led many researchers to question the future utility of polygons as the fundamental graphics primitive. On the other hand, modern three-dimensional (3D) digital photography and 3D scanning systems acquire both geometry and appearance of complex, real-world objects. These techniques generate huge volumes of point samples, which constitute the discrete building blocks of 3D object geometry and appearance—much as pixels are the digital elements for images.

Over the past five years, point-based graphics has seen an amazing growth. By the time of publication of this book, three symposia on point-based graphics will have concluded, the first of which was started in Zürich, Switzerland, in 2004. The large number of submissions to these conferences shows the huge interest in this young and exciting field and its potential for research and teaching.

This interest in combination with the huge success of various tutorials on this topic and thousands of downloads of Pointshop3D, a freeware software package for point-based graphics, have motivated us to create this textbook. It presents a comprehensive collection of both fundamental and more advanced topics in point-based computer graphics. The book is based on a series of courses that we and some of the authors taught over the past five years at major graphics conferences. We have extended our material significantly and we have invited numerous prolific authors in the field to contribute to this publication.

The book assumes familiarity with the standard computer graphics techniques for surface representation, modeling, and rendering. No previous knowledge about point-based methods is required. The book is suitable for both classroom and professional use. The comprehensive coverage of the topic makes the book a reference and teaching tool, and the in-depth coverage of algorithms as well as the inclusion of the Pointshop3D open-source system makes it very attractive for developers.

The book is intended for researchers and developers with a background in traditional (polygon-based) computer graphics. They will obtain a state-of-the-art overview of the use of points to solve fundamental computer graphics problems such as surface data acquisition, representation, processing, modeling, and rendering. With this book, we hope to stimulate research and development of point-based methods in games, entertainment, special effects, visualization, digital content creation, and other areas. For instance, game developers will learn how to use point-based graphics for game characters and special effects (physics, water, etc.) employing real-time rendering on graphics processing units (GPUs). Developers in the movies and special effects industry will learn how to use points for offline, high-quality global illumination, character rendering, and physics. Engineers will learn how to process huge point clouds that naturally arise during object scanning. Architects of current GPUs (e.g., at NVIDIA and ATI) will learn what operations need to be implemented or accelerated to facilitate point-based graphics. Digital content creators and artists will use Pointshop3D for the creation of very complex models.

We believe that point-based graphics bear a huge potential for future research and development and might influence the way we will do computer graphics in the future. We hope that this book will stimulate new ideas in this rapidly moving field and that it will convince more graphics researchers and developers of the utility of point-based graphics.

1.2

BOOK ORGANIZATION

The book organization follows essentially the 3D content creation pipeline, as outlined in Figure 1.1.

Figure 1.1 The 3D graphics content-creation pipeline serves as a model for the book’s organization.

Historically, points have received relatively little attention in computer graphics. Yet, there has been fundamental work that laid ground for the more recent developments. In Chapter 2, Marc Levoy will present an historical perspective on the topic. He will highlight early work on point-based modeling and rendering, and will point out how this work provided a basis for the subsequent chapters of this book.

The first stage in Figure 1.1 involves the acquisition of point clouds from real-world models through means of 3D scanning and reconstruction. Chapter 3 will give a comprehensive overview over the state-of-the-art in 3D acquisition and scanning methods for point-sampled models. The authors focus both on geometry and appearance acquisition. The discussed algorithms and systems will make the reader familiar with the essentials of scanning technology, including a practical guide to build a low-cost 3D scanning system. The final topic of this chapter is devoted to sophisticated appearance acquisition using 3D photography.

The next stage in the content creation pipeline includes mathematical methods to reconstruct surfaces from point clouds and to deal with the discrete nature of point sets. Chapter 4 acquaints the reader with the mathematical and algorithmic fundamentals of point-based surface representations. It describes the basic concepts of discrete differential geometry and topology as well as specific representations, such as the famous moving least squares (MLS) method. Other topics of the chapter are discretization and sampling and an overview over the most important data structures for point-based representations. The chapter concludes with a presentation of real-time, iterative refinement methods.

Once the surface representations are in place, the next step in the content creation pipeline is the digital processing, filtering, modeling, and editing of point models. Chapter 5 is devoted to the digital processing of point-sampled models. It demonstrates the versatility of point-sampled representations that combine the simplicity of conventional image editing operations with the power of advanced 3D modeling methods. The chapter includes a variety of preprocessing methods, such as model cleaning, filtering, and feature extraction, as well as photo editing operations. More advanced shape modeling operations, like deformations and constructive solid geometry (CSG), will also be discussed. The chapter is closely related to the core functions of Pointshop3D, the software accompanying the book.

The final stage in our content creation pipeline is high-quality and efficient display of the point model. Novel rendering pipelines and concepts had to be devised for point-based models. Chapter 6 presents a comprehensive overview of high-quality rendering methods for point-sampled geometry. It starts with a review of the fundamentals of surface splatting, one of the most widely used techniques for point rendering. More advanced and hardware-accelerated methods for point splatting will be discussed next. Finally, we explain ray-tracing methods for point-sampled geometry and acceleration structures for high-performance point rendering.

Very often, graphics models have to be animated; i.e., their shape and attributes have to be controlled and altered over time. Due to the complexity of the topic, animation cannot be treated comprehensively. But Chapter 7 will describe physically based animation using point-sampled representations. This topic has emerged recently as a promising alternative to conventional finite element simulation. It is inspired by so-called meshless methods, where the continuum is discretized using unstructured point samples. We will demonstrate that such methods allow for a wide spectrum of material simulations, including brittle fracture, elastic and plastic deformations, and fluids. Such physical point representations are combined with high-resolution point-sampled surface geometry.

The concluding Chapter 8 contains a collection of select topics related to point-based computer graphics. One such method is the dynamic representation, compression, and display of 3D video. A second one is the modeling and analysis of uncertainty in point clouds. A further topic discusses point-based visualization of attributed datasets. Another contribution addresses the computation of global illumination in point-sampled scenes and shows how such methods are used in a production environment. The chapter demonstrates the versatility and application potential of point-based methods.

1.3

COMMON ISSUES AND REOCCURRING PATTERNS

Points are clearly the simplest of all graphics primitives. Throughout the book, there are reoccurring issues inherent to point-based graphics that can be summarized as follows.

Points generalize pixels and voxels toward irregular samples of geometry and appearance. The conceptually most significant difference to triangles is that points—much as voxels or pixels—carry all attributes needed for processing and rendering. There is no distinction between vertex and fragment anymore.

As a sampled representation including geometry and (prefiltered) appearance, point representations allow one to carry over some of the computationally expensive fragment processing, such as filtering, to the preprocessing stage. Their very “sameness” of geometry and appearance creates the potential of designing leaner graphics pipelines. Of course, this simplified processing comes at a price. Straightforward framebuffer projection leaves holes in the image that have to be filled for close-up views. Point models also require a denser sampling compared to triangle meshes. The higher resolution of the representation potentially leads to increased bandwidth requirements between the computer processing unit (CPU) and GPU. In some sense, bandwidth has to be traded with processing speed.

Points, in their purest form, do not store any connectivity or topology. Since many 3D acquisition algorithms generate point clouds as output, points naturally serve as the canonical representation for 3D acquisition systems. In contrast, triangle meshes are the result of 3D reconstruction algorithms and require prior assumptions on topology and sampling. The lack of topology and connectivity, however, is strength and weakness at the same time. The atomic nature of a point sample gives the representation a built-in level of detail (LOD), making it possible, for instance, to stream and render point clouds progressively.

Points have proven their ability to model complex geom...

Table of contents

• Cover image
• Title page
• Table of Contents
• Inside Front Cover
• The Morgan Kaufmann Series in Computer Graphics
• Copyright
• Dedication
• About the Editors
• Foreword
• Chapter 1: INTRODUCTION
• Chapter 2: THE EARLY HISTORY OF POINT-BASED GRAPHICS
• Chapter 3: ACQUISITION
• Chapter 4: FOUNDATIONS AND REPRESENTATIONS
• Chapter 5: DIGITAL PROCESSING
• Chapter 6: RENDERING
• Chapter 7: PHYSICS-BASED ANIMATION
• Chapter 8: SELECTED TOPICS
• BIBLIOGRAPHY
• Index
• About the CD-ROM