Computational methods for algebraic spline surfaces : ESF exploratory workshop

This volume contains revised papers that were presented at the international workshop entitled Computational Methods for Algebraic Spline Surfaces (“COMPASS”), which was held from September 29 to October 3, 2003, at Schloß Weinberg, Kefermarkt (A- tria). The workshop was mainly devoted to approximate algebraic geometry and its - plications. The organizers wanted to emphasize the novel idea of approximate implici- zation, that has strengthened the existing link between CAD / CAGD (Computer Aided Geometric Design) and classical algebraic geometry. The existing methods for exact implicitization (i. e. , for conversion from the parametric to an implicit representation of a curve or surface) require exact arithmetic and are too slow and too expensive for industrial use. Thus the duality of an implicit representation and a parametric repres- tation is only used for low degree algebraic surfaces such as planes, spheres, cylinders, cones and toroidal surfaces. On the other hand, this duality is a very useful tool for - veloping ef?cient algorithms. Approximate implicitization makes this duality available for general curves and surfaces. The traditional exact implicitization of parametric surfaces produce global rep- sentations, which are exact everywhere. The surface patches used in CAD, however, are always de?ned within a small box only; they are obtained for a bounded parameter domain (typically a rectangle, or – in the case of “trimmed” surface patches – a subset of a rectangle). Consequently, a globally exact representation is not really needed in practice. Cover......Page 1 S Title......Page 2 Title......Page 3 ISBN 3-540-23274-5......Page 4 Preface......Page 6 Table of Contents......Page 8 1.1 Passive Observation Systems......Page 9 1.3 Measurement Error of the POS......Page 10 1.4 Confidence Sets......Page 11 2.1 Intersection of Quadric Surfaces of Revolution......Page 12 2.2 Example......Page 13 3.2 Implicit Representation......Page 14 3.4 Symbolic Computation of the Taylor Expansion......Page 15 3.5 Example......Page 16 4 Conclusion......Page 17 References......Page 18 1 Introduction......Page 19 3 Surface-Surface Intersections......Page 20 4 Recursive Subdivision......Page 23 5 Intersections Between one Parametric and one AlgebraicSurface......Page 24 6 Approximate Implicitization......Page 25 7 Interception Testing......Page 26 8 Simple case Situations......Page 27 9 Singular Surface-Surface Intersections......Page 28 10 Partial Coincidences and Tangential Intersections......Page 30 11 Conclusion......Page 32 References......Page 34 1 Introduction......Page 35 2.1 Resultant and Projection......Page 36 3 Topology of Algebraic Curves......Page 38 3.1 Critical Points and Generic Position......Page 39 3.2 The Projected Curves......Page 40 3.3 Lifting a Point of C′......Page 41 3.4 Computing Points of C at Critical Values......Page 42 3.5 Connecting the Branches......Page 44 4 Implementation and Experiments......Page 47 4.2 Examples of 3D Curves......Page 49 References......Page 51 1 Introduction......Page 53 2 Basic Notions and Preliminary Results......Page 55 3 ǫ–Roots......Page 60 4 ǫ–Points on Curves......Page 63 References......Page 69 1 Introduction and Background......Page 71 2 Distance Maps and Projected Distance Maps......Page 73 3 Examples......Page 75 4 Refining the IFA Tests......Page 78 References......Page 81 Appendix A: The Distance Functions for Two B ́ezier Curves......Page 82 1 Introduction......Page 85 2 Projective Varieties, Degree, and Projection......Page 86 3 Varieties of Minimal Degree......Page 88 4 Curves of Almost Minimal Degree......Page 89 5 Surfaces of Almost Minimal Degree......Page 90 6 Classification of Del Pezzo Surfaces......Page 93 7 Del Pezzo Surfaces of Degree 2 and 1......Page 95 8 Real Del Pezzo Surfaces......Page 99 References......Page 101 2 Tangent Developables......Page 103 3 Local Properties of a Real Tangent Developable......Page 104 4 Illustrations......Page 106 References......Page 113 1 Introduction......Page 115 2.1 The Companion Resultant Matrix......Page 116 2.2 The Sylvester Resultant Matrix......Page 117 2.3 The B ́ezout Resultant Matrix......Page 119 3 The Numerical Condition of a Resultant Matrix......Page 120 4 The Transformation of a Resultant Matrix Between the Powerand Bernstein Bases......Page 123 5 Summary......Page 125 References......Page 126 1 Introduction......Page 127 2 M-patches and their tensor-border......Page 128 2.1 Definition of M-Patches......Page 129 2.2 Tensor-border Structure......Page 130 2.3 Reparametrizations to Form a Tensor-Border......Page 131 3.1 Outline of the Construction......Page 132 3.2 The C2 Transition Between the Reparametrizations ρ2;s and a Bicubic C2Reparametrization......Page 133 3.3 Subsequent Annuli of Bidegree (5,5)......Page 134 3.4 Annuli of B ́ezier Patches......Page 135 4 A Spline Cap of Bidegree (11,11)......Page 136 4.1 The 135-Reparametrizations ̃γs......Page 137 4.2 A Total Degree 7 C2 Approximation of the Geometry......Page 139 4.3 Capping Patches of Bidegree (11, 11)......Page 140 References......Page 142 1 Introduction......Page 143 2 The Subdivision Algorithm......Page 145 3 Taylor Method for Bounds......Page 146 4 Finding Bounds on Derivatives......Page 148 5.1 Algebraic Curves......Page 149 5.2 Algebraic Surfaces......Page 153 6 Why use Order Two Taylor Expansion?......Page 157 7 Theoretical Connection Between Taylor Method and MAA......Page 160 References......Page 161 1 Introduction......Page 163 2 Implicitization......Page 166 3 Finding Self-Intersections......Page 167 4 Surfaces......Page 169 5 Approximate Implicitization......Page 171 6 Two Open Problems......Page 172 6.2 How do we Find Self-Intersection Curves (as Opposed to Points)?......Page 173 References......Page 177 1 Introduction......Page 179 2 Numerical Characters of a Projected Surface......Page 180 3 The Veronese Surfaces......Page 181 4 The Segre Surfaces......Page 184 5 Del Pezzo Surfaces......Page 185 6 Rational Scrolls......Page 186 7 Monoid Surfaces......Page 188 References......Page 189 1 Introduction and Preliminaries......Page 191 2 Parabolic Loci......Page 192 3 Minimal Loci......Page 193 4 On the Influence of the Extrema of the Weight Function of theFree Control Point......Page 194 5 Numerical Experimentation with NURBS......Page 196 5.1 Cylinder......Page 197 5.2 Ellipsoid......Page 198 5.3 Torus......Page 199 References......Page 200 1 Introduction......Page 201 2 Invariants on Surfaces......Page 202 3 The Generators......Page 203 4 The Syzygies......Page 206 5 The Structure of the Invariant Ring......Page 209 6 Implicit Surfaces......Page 212 7 Applications......Page 213 7.1 Fairing......Page 215 7.2 Ridges and the Subparabolic Curve......Page 217 7.3 Darboux’s Classification of Umbilical Points......Page 218 References......Page 219 1 Introduction......Page 221 2.1 Examples of Universal Rational Parametrizations......Page 222 2.2 Complex Toric Surfaces......Page 224 2.3 Singular Case and Desingularization......Page 225 3 URP Theorem......Page 226 4.1 Real Structures on Quadrics......Page 228 4.3 The Torus Surface is Almost Toric!......Page 229 5.1 Interpolation on the Projective Line CP1......Page 231 5.2 Splines on CP1 and RP1......Page 232 5.4 Splines on Hirzebruch Surfaces......Page 234 5.5 Splines on a Hexagonal Toric B ́ezier patch......Page 235 6 Application: Blending Natural Quadrics......Page 236 7 Conclusions......Page 238 References......Page 239 Panel Discussion......Page 241

the Papers Included In This Volume Provide An Overview Of The State Of The Art In Approximative Implicitization And Various Related Topics, Including Both The Theoretical Basis And The Existing Computational Techniques. The Novel Idea Of Approximate Implicitization Has Strengthened The Existing Link Between Computer Aided Geometric Design And Classical Algebraic Geometry. There Is A Growing Interest From Researchers And Professionals Both In Cagd And Algebraic Geometry, To Meet And Combine Knowledge And Ideas, With The Aim To Improve The Solving Of Industrial-type Challenges, As Well As To Initiate New Directions For Basic Research. This Volume Will Support This Exchange Of Ideas Between The Various Communities.

"The papers included in this volume provide an overview about the state-of-the-art in approximative implicitization and various related topics, including both the theoretical basis and the existing computational techniques. The novel idea of approximate implicitization has strengthened the existing link between Computer Aided Geometric Design and classical algebraic geometry. There is a growing interest from researchers and professionals both in CAGD and algebraic geometry, to meet and combine knowledge and ideas, in order to better solve industrial-type challenges, as well as to initiate new directions for basic research. This volume will support this exchange of ideas between the various communities."--BOOK JACKET This volume contains revised papers that were presented at the international workshop entitled Computational Methods for Algebraic Spline Surfaces ("COMPASS"), which was held from September 29 to October 3, 2003, at Schloss Weinberg, Kefermarkt (A- tria). Our research was motivated by concrete problem of the analysis and the visualization of the errors of so called Passive Observation Systems (POS).