INTERACTIVE CURVE MODELING
CONTENTS 1 INTRODUCTION 1 1 1 STRATEGY IN THE CONSTRUCTION OF THEORY 1 1 2 OVERVIEW 2 1 2 1 SPLINES 2 1 2 2 SHAPE PRESERVING INTERPOLATION 3 1 2 3 FUNCTIONAL APPROXIMATION 3 1 2 4 SPIRAL CURVES 4 1 2 5 CORNER DETECTION AND CURVE SEGMENTATION 4 1 2 6 VECTORIZING PLANAR SHAPES 5 1 2 7 REVERSE ENGINEERING 5 1 2 8 MULTIRESOLUTION FRAMEWORK 6 1 3 NOTATION AND CONVENTIONS 6 1 4 REVIEW OF SOME SPLINE METHODS 7 1 4 1 CUBIC SPLINE 7 1 4 2 SPLINE UNDER TENSION 8 1 4 3 WEIGHTED SPLINE 8 1 4 4 NU SPLINE 8 1 4 5 WEIGHTED NU SPLINE 9 1 4 6 BETA SPLINES 9 1 4 7 SIGMA SPLINES 10 1 4 8 B SPLINES 10 1 4 9 B EZIER SPLINES 11 1 4 10 HERMITE SPLINES 11 1 5 SUMMARY 13 1 6 EXERCISES 13 2 WEIGHTED NU SPLINES 21 2 1 INTRODUCTION 21 2 2 SOME SPLINE METHODS 23 2 2 1 CUBIC SPLINES 24 2 2 2 WEIGHTED SPLINES 24 2 2 3 NU SPLINES 26 2 2 4 WEIGHTED NU SPLINES 27 2 2 5 DEMONSTRATION 28 2 3 FREEFORM WEIGHTED NU SPLINE 28 2 3 1 LOCAL SUPPORT BASIS 29 2 3 2 DESIGN CURVE 31 2 3 3 SHAPE CONTROL 32 2 3 4 DEMONSTRATION 34 2 3 5 ADVANTAGES AND FEATURES 37 2 4 SURFACES 37 2 5 SUMMARY 38 2 6 EXERCISES 38 3 RATIONAL CUBIC SPLINE WITH SHAPE CONTROL 41 3 1 INTRODUCTION 41 3 2 C1 PIECEWISE RATIONAL CUBIC HERMITE INTERPOLANT 42 3 3 ONE PARAMETER RATIONAL CUBIC SPLINE 44 3 4 TWO PARAMETER RATIONAL CUBIC SPLINE 49 3 5 DEMONSTRATION 51 3 6 FREEFORM CURVES 55 3 7 LOCAL SUPPORT BASIS 56 3 8 DESIGN CURVE 58 3 9 SHAPE PROPERTIES 60 3 10 DEMONSTRATION 64 3 11 NURBS 64 3 12 SURFACES 70 3 13 SUMMARY 71 3 14 EXERCISES 71 4 RATIONAL SIGMA SPLINES 75 4 1 INTRODUCTION 75 4 2 GENERALIZED RATIONAL CUBIC INTERPOLANT 76 4 3 INTERPOLATORY RATIONAL SPLINES 77 4 3 1 SHAPE CONTROL 77 4 3 2 SOME SPECIAL CASES 78 4 3 3 EXAMPLES 78 4 4 FREEFORM RATIONAL SPLINES 81 4 4 1 SHAPE CONTROL 84 4 4 2 SOME SPECIAL CASES 85 4 4 3 EXAMPLES 87 4 5 EXERCISES 91 5 LINEAR CONIC AND RATIONAL CUBIC SPLINES 93 5 1 INTRODUCTION 93 5 2 THE RATIONAL CUBIC SPLINE 95 5 2 1 ESTIMATION OF TANGENT VECTORS 97 5 3 DESIGN CURVE ANALYSIS 99 5 4 ESTIMATION OF END TANGENT VECTORS 101 5 5 CONIC SPLINES AND STRAIGHT LINE 101 5 5 1 CONIC ARC IN CUBIC SPLINE 103 5 5 2 CIRCULAR SPLINE 103 5 5 3 CIRCULAR ARC 105 5 5 3 1 CIRCULAR ARC FOR GIVEN RADIUS 106 5 5 3 2 CIRCULAR ARC FOR A GIVEN CENTER 106 5 5 4 ELLIPTIC ARC 107 5 5 5 INTERMEDIATE POINT INTERPOLATION 109 5 5 6 STRAIGHT LINE SEGMENT 110 5 6 EXAMPLES 110 5 7 SUMMARY 113 5 8 EXERCISES 113 6 SHAPE PRESERVING RATIONAL INTERPOLATION FOR PLANAR CURVES 117 6 1 INTRODUCTION 117 6 2 THE RATIONAL CUBIC INTERPOLANT 118 6 3 INTERPOLATION OF CONVEX DATA 119 6 4 INTERPOLATION OF MONOTONIC DATA 120 6 5 INTERPOLATION OF CONVEX AND MONOTONIC DATA 123 6 6 CHOICE OF TANGENT VECTORS 123 6 7 EXAMPLES 124 6 8 SUMMARY 126 6 9 EXERCISES 126 7 VISUALIZATION OF SHAPED DATA BY A RATIONAL CUBIC SPLINE 129 7 1 INTRODUCTION 129 7 2 RATIONAL CUBIC SPLINE WITH SHAPE CONTROL 133 7 2 1 SHAPE CONTROL ANALYSIS 134 7 2 2 DETERMINATION OF DERIVATIVES 135 7 2 2 1 DERIVATIVE METHOD I 135 7 2 2 2 DERIVATIVE METHOD II 135 7 2 2 3 DERIVATIVE METHOD III 136 7 2 3 EXAMPLES AND DISCUSSION 136 7 3 POSITIVE SPLINE INTERPOLATION 139 7 3 1 EXAMPLES AND DISCUSSION 142 7 4 MONOTONE SPLINE INTERPOLATION 145 7 4 1 EXAMPLES AND DISCUSSION 148 7 5 CONVEX SPLINE INTERPOLATION 148 7 5 1 DEMONSTRATION 153 7 6 SUMMARY 154 7 7 EXERCISES 154 8 VISUALIZATION OF SHAPED DATA BY CUBIC SPLINE INTERPOLATION 157 8 1 INTRODUCTION 157 8 2 CUBIC INTERPOLANT 158 8 2 1 DEMONSTRATION 159 8 3 SHAPE PRESERVING INTERPOLATION 160 8 4 CONVEX CUBIC SPLINE 160 8 4 1 DEMONSTRATION 162 8 5 MONOTONE CUBIC SPLINE 162 8 5 1 DEMONSTRATION 164 8 6 POSITIVE CUBIC SPLINE 164 8 6 1 DEMONSTRATION 166 8 7 EXTENSION OF POSITIVE CUBIC SPLINE 167 8 7 1 DEMONSTRATION 170 8 8 SUMMARY 171 8 9 EXERCISES 171 9 APPROXIMATION WITH B SPLINES CURVES 173 9 1 INTRODUCTION 173 9 2 B SPLINES 174 9 3 DETERMINISTIC APPROACH 174 9 3 1 APPROXIMATION TECHNIQUE 175 9 3 1 1 INITIAL DATA POINTS STEP 1 175 9 3 1 2 KNOT INSERTION STEP 2 177 9 3 1 3 ERROR MINIMIZATION STEP 3 178 9 3 2 DEMONSTRATION 178 9 4 NONDETERMINISTIC APPROACH 180 9 4 1 A BRIEF OVERVIEW OF GAS 181 9 4 2 IMPLEMENTATION SUMMARY 181 9 4 3 DEMONSTRATION 183 9 5 SUMMARY 193 9 6 EXERCISES 193 10 SPIRALS 195 10 1 INTRODUCTION 195 10 2 THE RATIONAL QUADRATIC B EZIER CURVE 196 10 3 THE CONIC SPIRAL 197 10 4 COMPARISON OF CONIC AND T CUBIC SPIRALS 200 10 5 THE ARC CONIC SPIRAL 201 10 6 EXAMPLES 205 10 7 LIMITATIONS 206 10 8 SUMMARY 206 10 9 EXERCISES 206 11 CORNER DETECTION FOR CURVE SEGMENTATION 209 11 1 INTRODUCTION 209 11 2 BASIC FORMULATION 210 11 3 SUMMARY OF COMMONLY REFERRED CORNER DETECTORS 212 11 3 1 ROSENFELD AND JOHNSTON RJ73 ALGORITHM 212 11 3 2 ROSENFELD AND WESZKA RW75 ALGORITHM 213 11 3 3 FREEMAN AND DAVIS FD77 ALGORITHM 213 11 3 4 BEUS AND TIU BT87 ALGORITHM 214 11 4 CHETVERIKOV AND SZABO CS99 ALGORITHM 215 11 4 1 FIRST PASS 215 11 4 2 SECOND PASS 216 11 4 3 DEMONSTRATION 216 11 4 4 PERFORMANCE EVALUATION 218 11 5 SARFRAZ ASIM AND MASOOD SAM06 ALGORITHM 219 11 5 1 FIRST PASS 219 11 5 2 SECOND PASS 220 11 5 3 PARAMETERS 221 11 5 4 DEMONSTRATION 221 11 6 MASOOD AND SARFRAZ MS06 ALGORITHM 226 11 6 1 PERFORMANCE CRITERIA 230 11 6 2 DEMONSTRATION 231 11 7 OVERALL ANALYSIS 235 11 8 PIECING BOUNDARIES 236 11 9 SUMMARY 237 11 10 EXERCISES 238 12 LINEAR CAPTURE OF DIGITAL CURVES 241 12 1 INTRODUCTION 241 12 2 SOME IMPORTANT ISSUES 243 12 2 1 INPUT PARAMETERS 243 12 2 2 REGION OF SUPPORT 244 12 2 3 ERROR MEASUREMENT 244 12 2 4 MIN AND MIN PROBLEMS 245 12 2 5 TEST SHAPES 245 12 3 APPROXIMATION TECHNIQUES 246 12 3 1 TEH AND CHIN ALGORITHM 247 12 3 2 MARJI AND SIY ALGORITHM 248 12 3 3 WU ALGORITHM 249 12 3 4 SOME OTHER ALGORITHMS 250 12 4 PIECEWISE POLYGONAL APPROXIMATION 251 12 4 1 PREPROCESSING STAGE 251 12 4 2 SAMAPA ALGORITHM 252 12 5 EXPERIMENTAL RESULTS 256 12 6 OPTIMAL ALGORITHMS 259 12 6 1 DYNAMIC PROGRAMMING 259 12 6 2 PEREZ AND VIDAL ALGORITHM 260 12 6 3 SOME REMARKS ON OPTIMAL ALGORITHMS 261 12 7 SUMMARY 262 12 8 EXERCISES 262