Generative Modeling for Computer Graphics and Cad

Foreword by James Τ. KajiyaPrefaceAcknowledgmentsIndex of Figures1 Introduction 1.1 User vs. Macliine Shape Representations 1.2 Criteria for Evaluation of a Shape Representation 1.3 Previous Work in Shape Representation 1.3.1 Polyhedra 1.3.2 Piecewise Parametric Polynomial Shapes 1.3.3 Algebraic Shapes 1.3.4 Sweeps 1.3.5 Deformations 1.3.6 Non-Polynomial Parametric Shapes 1.3.7 Non-Polynomial Implicit Shapes 1.4 Areas for Improvement in Shape Representation 1.5 The Generative Modeling Approach 1.6 Generative Modeling: The State of the Art 1.6.1 Previous Work Related to Generative Modeling 1.6.2 New Work Described in this Book 1.6.3 Future Work2 Shape Representation 2.1 Generative Models: A Domain of Shapes 2.1.1 Why Generative Models? 2.2 Specifying Generative Models 2.2.1 Parametric Functions and the Closure Property 2.2.2 Using Symbolic Operators to Specify Parametric Functions 2.2.3 Specific Operators 2.2.4 Operator Metliods 2.3 Development of tlie Generative Modeling Representation 2.3.1 System 1-Nonrecursive Transformations and Generators 2.3.2 System 2-Limited Recursive Transformations 2.3.3 System 3-Fully Recursive Transformations and Generators 2.3.4 System 4-Using a General Purpose Language3 Shape Specification Examples 3.1 GENMOD Preliminaries 3.2 Generative Surfaces 3.2.1 Affine Cross Section Transformations 3.2.2 Non-Affine Cross Section Transformations 3.2.3 Boolean Operations on Planar Cross Sections 3.2.4 Parameterizing Cross Sections 3.3 Other Generative Shapes 3.3.1 Solids 3.3.2 Time-Dependent Shapes 3.3.3 Vector Fields on Surfaces4 Shape Rendering 4.1 Categorizing Generative Models for Rendering 4.1.1 Curves 4.1.2 Surfaces 4.1.3 Solids 4.1.4 Shapes of High Input Dimension 4.1.5 Shapes of High Output Dimension 4.2 Sampling Generative Models 4.2.1 Uniform Sampling 4.2.2 Adaptive Sampling 4.3 Controlling Visualization of Generative Models 4.3.1 Visualization Methods 4.3.2 Fast Visualization 4.3.3 Non-Precomputed Visualization 4.3.4 Non-Uniformly Sampled Visualization 4.3.5 Interactive Rendering Implementation5 Interval Methods for Shape Synthesis and Analysis 5.1 Why Interval Analysis? 5.2 Inclusion Functions 5.2.1 Terminology and Definitions 5.2.2 Inclusion Functions for Arithmetic Operations 5.2.3 Natural Interval Extensions 5.2.4 Inclusion Functions for Relational and Logical Operators 5.2.5 Mean Value and Taylor Forms 5.2.6 An Inclusion Function for the Integration Operator 5.2.7 Inclusion Functions Based on Monotonicity 5.3 Constraint Solution Algorithm 5.3.1 The Problem of Indeterminacy 5.3.2 Subdivision Methods 5.3.3 Solution Aggregation 5.3.4 Termination and Acceptance Criteria for Constraint Solution 5.3.5 Interval Newton Methods 5.3.6 Existence of Solutions 5.3.7 A Constraint Evaluation Enhancement 5.4 Constrained Minimization Algorithm 5.4.1 Termination and Acceptance Criteria for Constrained Minimization 5.4.2 Monotonicity Test6 Applying Interval Methods to Geometric Modeling 6.1 Offset Operations 6.1.1 The B-Offset: A Tighter Representation for the S-Offset Boundary 6.1.2 A Constraint-Based Approach for Computing B-Offsets 6.2 Approximating Implicit Curves 6.2.1 An Implicit Curve Approximation Algorithm 6.2.2 A Robust Test for Global Parameterizability 6.2.3 A Heuristic Test for Global Parameterizability 6.2.4 Relaxing the Approximation Algorithm's Restrictions 6.3 Approximating Parametric Shapes Using Adaptive Criteria 6.3.1 Kd-Trees 6.3.2 Generating a Triangular Mesh 6.4 CSG-Like Operations with Trinuned Surfaces 6.4.1 An Algorithm for Approximating CSG-like Operations 6.4.2 Example Application of the CSG-Like Operation Algorithm 6.4.3 Kd-Tree Algorithms for CSG-like Operations 6.5 Constructive Solid Geometry with Trinuned Surfaces 6.6 Approximating Implicit Surfaces 6.6.1 An Implicit Surface Approximation Algorithm7 ConclusionAppendices: A The GENMOD Language A.1 Language Extensions A. 1.1 New Operators A. 1.2 Overloaded Operators A.2 Language Types A.3 Language Primitive Operators A.3.1 Constants and Parametric Coordinates A.3.2 Arithmetic Operators A.3.3 Elementary Operators A.3.4 Vector Operators A.3.5 Matrix Operators A.3.6 Integral and Derivative Operators A.3.7 Curves and Tables A.3.8 Relational Operators A.3.9 Logical Operators A.3.10 Conditional and Branching Operators A.3.11 Substitution Operators A.3.12 Inverse Operator A.3.13 Constraint Solution and Constrained Minimization Operators A.3.14 ODE Solution Operator A.4 language Extensibility: Building Higher-Level Operators A.4.1 Interpolation Operators A.4.2 Concatenation Operators A.4.3 Reparameterization Operator A.4.4 Closed Offset Operator A.5 Operator Libraries A.5.1 Affine Transformation Library A.5.2 Line/Are Library A.5.3 Physical Properties of Rigid Bodies LibraryΒ GENMOD Code Examples B.1 Sphere/Cylinder Fillet Example B.2 Screwdriver Tip Examples B.3 Bottle Example B.4 Teddy Bear ExampleC Theorems in Interval Analysis C.1 Second Order Convergence of the Mean Value Form C.2 Convergence of the Constraint Solution Algorithm C.3 Convergence of the Minimization Algorithm C.4 Existence of Zeroes C.5 Interval Implicit Function TheoremBibliographyIndex