book.gif (9074 bytes)

  

Introduction to Implicit Surfaces

(out of print)

 

edited by Jules Bloomenthal, 1997
published by Morgan-Kaufmann

 

 

Authors

Chandrajit Bajaj, Jim Blinn, Jules Bloomenthal, Marie-Paule Cani-Gascuel, Alyn Rockwood, Brian Wyvill, and Geoff Wyvill
Abstract

Implicit surfaces offer special effects animators, graphic designers, CAD engineers, graphics students, and hobbyists a new range of capabilities for the modeling of complex geometric objects. In contrast to traditional parametric surfaces, implicit surfaces can easily describe smooth, intricate, and articulatable shapes. These powerful yet easily understood surfaces are finding use in a growing number of graphics applications.

 

This comprehensive introduction develops the fundamental concepts and techniques of implicit surface modeling, rendering, and animating in terms accessible to anyone with a basic background in computer graphics.

  • provides a thorough overview of implicit surfaces with a focus on their applications in graphics
  • explains the best methods for designing, representing, and visualizing implicit surfaces
  • surveys the latest research

With contributions from seven graphics authorities, this innovative guide establishes implicit surfaces as a powerful and practical tool for animation and rendering.

Table of Contents

Preface
Acknowledgments

1 The Geometry of Implicit Surfaces, by Jules Bloomenthal

1.1 Introduction

1.1.1 Mathematical Foundations
1.1.2 Continuity and Differentiability
1.1.3 Manifolds and Models
1.1.4 Specification and Representation

1.2 Relation to Parametric Surfaces

1.2.1 Conversion between Forms

1.3 Solid Modeling

1.3.1 Specification and Representation

1.4 Algebraic Surfaces

1.4.1 Interpolation
1.4.2 Blends
1.4.3 Unions and Intersections

1.5 Deformations
1.6 Patches
1.7 Procedural Definitions
1.8 Skeletal Design
1.9 Grids
1.10 Visualization

1.10.1 Discrete Volumetric Sets
1.10.2 Mathematical Functions

1.11 Details, Details
1.12 Surface Reconstruction
1.13 Interactivity
1.14 Conclusion

2 The Algebraic Properties of Second-Order Surfaces, by Jim Blinn

2.1 Introduction

2.1.1 Surface Definition Techniques
2.1.2 First-Order Surfaces
2.1.3 Second-Order Surfaces
2.1.4 Homogeneous Representation
2.1.5 General Homogeneous Surfaces

2.2 Geometrical Operations Necessary for Drawing

2.2.1 Representation
2.2.2 Modeling
2.2.3 Transformation
2.2.4 Boundary Checking
2.2.5 Intersections
2.2.6 Surface Normals

2.3 Planar Curves

2.3.1 First-Order Algebraic Curves
2.3.2 Second-Order Algebraic Curves

2.4 Surfaces

2.4.1 First-Order Algebraic Surfaces
2.4.2 Second-Order Algebraic Surfaces

2.5 Rendering Algorithms

2.5.1 Coordinate Systems
2.5.2 General Algorithm
2.5.3 Gross Clipping
2.5.4 Y and X Range Calculation
2.5.5 Pitfalls in Range Calculation
2.5.6 Z Calculation
2.5.7 Normal Vector Calculation
2.5.8 Texture Mapping

2.6 Applications to Higher-Order Curves

2.6.1 Taylor Series
2.6.2 Stationary Points
2.6.3 Level Curves
2.6.4 Inflection Points

2.7 Conclusions

3 Implicit Surface Patches, by Chandrajit L. Bajaj

3.1 Introduction

3.2 Mathematical Preliminaries

            3.2.1 Algebraic Surfaces
            3.2.2 Polynomial Patch Representations
            3.2.3 A-Patch Representation
            3.2.4 Continuity

3.3 Curvilinear Mesh Schemes

            3.3.1 Algorithm Sketch

3.4 Simplex- and Box-Based Schemes

            3.4.1 Smooth Interpolation of a Polyhedron with $C^1$ A-patches
            3.4.2 Smooth Approximation with $C^2$ A-patches
            3.4.3 Smooth Reconstruction of Surfaces and Functions-on-Surfaces from Scattered Data

3.5 Subdivision-Based Schemes

4 Surface Tiling, by Jules Blomenthal

4.1 Introduction

            4.1.1 Classes of Tilers

4.2 Spatial Partitioning

            4.2.1 Subdivision
            4.2.2 Exhaustive Enumeration
            4.2.3 Continuation
            4.2.4 Robustness

4.3 Cell Polygonization

            4.3.1 Surface Vertex Computation
            4.3.2 Table Generation
            4.3.3 Polygon Formats
            4.3.4 Ambiguities
            4.3.5 Tetrahedral Decomposition
            4.3.6 Surface Orientation
            4.3.7 Optimized Polygons

4.4 Adaptive Methods

            4.4.1 Adaptive Criteria
            4.4.2 Cracks and Honeycombs
            4.4.3 Hybrid Continuation
            4.4.4 Iterative Surface Refinement
            4.4.5 Interactive Methods

4.5 Ad Hoc Polygonization

            4.5.1 Nonmanifold Polygonization
            4.5.2 Constructive Solid Geometry Polygonization

4.6 Conclusion

            5 Ray Tracing Implicit Surfaces, by Geoff Wyvill

                        5.1 Introduction

                                    5.1.1 The Basic Process

                        5.2 Intersection Tests

                                    5.2.1 Intersection with a Sphere
                                    5.2.2 Intersection with a Triangle
                                    5.2.3 Intersection with a Blended Implicit Surface
                                    5.2.4 Intersections with Transformed Objects
                                    5.2.5 Intersection with CSG Trees

                        5.3 Efficiency

                                    5.3.1 Bounding Boxes
                                    5.3.2 Ray Sorting
                                    5.3.3 Space Subdivision
                                    5.3.4 Octrees
                                    5.3.5 Creating the Space Division
                                    5.3.6 Space Division of Blended Implicit Surfaces
                                    5.3.7 Signatures and Mailboxes

                        5.4 General Implicit Surfaces

                                    5.4.1 Lipschitz Constants
                                    5.4.2 L-G Surfaces
                                    5.4.3 Sphere Tracing

                        5.5 Conclusion

            6 Blending, by Alyn Rockwood

                        6.1 Introduction
                        6.2 Background

                                    6.2.1 Potential Methods
                                    6.2.2 Design Taxonomy

                        6.3 Algebraic Surfaces
                        6.4 Blending on Blends
                        6.5 The Development of a General Blending Facility
                        6.6 The Displacement Blending Form

                                    6.6.1 Interrogability

                        6.7 Conclusion

            7 Convolution of Skeletons, by Jules Bloomenthal

                        7.1 Introduction
                        7.2 Algebraic Blends
                        7.3 Convolution Surfaces
                        7.4 Branching Objects

                                    7.4.1 Interpolation of Surfaces

                        7.5 Two-Dimensional Skeletal Elements
                        7.6 Three-Dimensional Skeletal Elements
                        7.7 Conclusion and Future Work

            8 Animation and Special Effects, by Brian Wyvill

                        8.1 Introduction
                        8.2 Geometric Motion of Skeletal Elements

                                    8.2.1 Path Following

                        8.3 Changing Skeletal Element Characteristics

                                    8.3.1 Geometry
                                    8.3.2 Weight
                                    8.3.3 Field Function

                        8.4 Metamorphosis

                                    8.4.1 Heuristics for Skeleton Matching in Metamorphosis
                                    8.4.2 Hand Matching
                                    8.4.3 Hierarchical Matching
                                    8.4.4 Cellular Inbetweening
                                    8.4.5 Surface Inbetweening
                                    8.4.6 Example: Metamorhposis Between a Rabbit and a Man
                                    8.4.7 Other Methods

                        8.5 Warping

                                    8.5.1 Squash and Stretch
                                    8.5.2 Warping Space and Time
                                    8.5.3 Using Barr's Deformations
                                    8.5.4 Affine Transformations Implemented as Warps

                        8.6 Unrendered Surfaces

                                    8.6.1 Making Objects Glow
                                    8.6.2 Synthetic Topiary

                        8.7 Conclusion

            9 Implicit Surfaces in Physically Based Animation, by Marie-Paule Cani-Gascuel

                        9.1 Introduction

                                    9.1.1 Deformable Models
                                    9.1.2 Collision Detection and Response

                        9.2 The Use of Implicit Surfaces within a Layered Model

                                    9.2.1 Skeletal and Implicit Components
                                    9.2.2 Benefits for Animation and Collision Processing

                        9.3 Deformation of Surfaces under Collisions

                                    9.3.1 Modeling Contacts between Objects
                                    9.3.2 Response to Collisions
                                    9.3.3 Implementation: The Use of Sampling

                        9.4 Volume Preservation

                                    9.4.1 The Need for Local Control
                                    9.4.2 Local Volume Approximation
                                    9.4.3 Control of Local Volume

                        9.5 An Example: Simulating Soft Substances

                                    9.5.1 Structure Used
                                    9.5.2 Modeling Separations
                                    9.5.3 Modeling Fusion under Compression

                        9.6 Conclusion
          References
          Index