Sketch-based Interfaces and Modeling (eBook)

Sketch-based Interfaces and Modeling 2
Foreword 4
Preface 7
Contents 9
Introduction 11
Sketch-based Interfaces 11
Sketching Issues and Research Topics in HCI 13
Recognition 14
Modes 15
Sketch-based Applications 16
Creation and Modification of 3D Models 17
Suggestive Systems 18
Constructive Systems 19
Augmentation 21
Deformation 22
Modeling Applications 23
References 24
Sketch-based Interfaces 26
Multi-domain Hierarchical Free-Sketch Recognition Using Graphical Models 27
Introduction 27
The Challenges of Free-Sketch Recognition 29
Knowledge Representation 31
Hierarchical Shape Descriptions 32
Handling Noise in the Drawing 34
Signal-Level Noise: Objective vs. Subjective Measures 34
Description-Level Variation: Optional Components and Constraints 35
Strengths and Limitations 36
Recognition Overview 37
Hypothesis Evaluation 38
Dynamically Constructed Graphical Models 39
Shape Fragments: Evaluating a Single Hypothesis 40
Network Structure 41
Conditional Probability Distributions 43
Observing Evidence from Stroke Data 44
Recognizing a Complete Sketch 44
Linking Shape Fragments 47
Missing Nodes 47
Implementation and Bayesian Inference 48
Hypothesis Generation 49
Selecting an Interpretation 51
Application and Results 52
Remaining Challenges and Extensions 56
Using Single-Stroke Classification to Improve Grouping 57
Conclusion 59
References 60
Minimizing Modes for Smart Selection in Sketching/Drawing Interfaces 63
Introduction 63
The Cost of Modes 65
The Temporal Cost of Modes 65
Mode Errors: The Mode Problem 66
Overloaded Loop Selection: UI Design to Infer Selection Mode 68
The Inferred Mode Protocol for Stylus Drawing and Selection with a Pen 70
The Mode Problem in Electronic Whiteboard Programs 70
Analytical Tool: The Interaction Flow Diagram 72
Interaction Flow Analysis of Mode-Based Selection and Drawing 74
Inferred Mode Protocol: Inferring Draw/Select Mode 77
Sloppy Selection: Inferring Intended Content of an Ambiguous Selection 80
Cycle Tap Selection: Exploiting Structure Recognition 81
Conclusion 87
References 87
Mathematical Sketching: An Approach to Making Dynamic Illustrations 89
Introduction 89
Mathematical Sketching 90
Philosophical Considerations 91
Generalizing Mathematical Sketching as a Paradigm 93
Observations on Mathematical Sketching 94
The MathPad2 Prototype 95
MathPad2 Architecture 95
The Gestural UI 97
Writing, Recognizing, and Correcting Mathematics 98
Making Drawings 100
Nailing Diagram Components 100
Grouping Diagram Components 101
Associations 101
Implicit Associations 101
Explicit Associations 102
Supporting Mathematical Toolset 102
Graphing Equations 103
Solving Equations 103
Evaluating Expressions 104
Mathematical Expression Recognition 104
Mathematical Symbol Recognition 105
Mathematical Expression Parsing 106
Preparing Mathematical Sketches 108
Association Inferencing 108
Drawing Dimension Analysis 109
Drawing Rectification 110
Angle Rectification 111
Location Rectification 111
Size Rectification 113
Translating and Visualizing Mathematical Sketches 115
Moving Forward with Mathematical Sketching 118
The Computational and Symbolic Toolset 118
Functions and Macros 119
Moving to 3D 120
Interactivity 121
Generating Mathematics from Drawings 121
Adding Specific Underlying Mathematical Engines 122
Alternate Forms of Dynamic Illustration 123
Evaluation 124
Conclusion 125
References 125
Pen-based Interfaces for Engineering and Education 127
Introduction 127
Sketch Parsing 128
Mark-Group-Recognize 129
Enumerate-Recognize-Prune 132
Parsing Step 1: Enumerating Candidate Symbols 133
Ink Density Locator: 134
Segment Difference Locator: 135
Parsing Step 2: Pruning Using Domain Knowledge 136
Automated Error Correction 137
Recognition 138
Graph-based Recognizer 139
Representation 139
Measuring Similarity 141
Primitive Count Error: 142
Primitive Type Error: 142
Relative Length Error: 143
Number of Intersections Error: 143
Intersection Angle Error: 143
Intersection Location Error: 144
Graph Matching 144
Stochastic Matching 145
Greedy Matching 145
Hybrid Matching 146
Training 146
Feature-based Recognizer 146
Image-based Recognizer 148
Representation 149
Template Matching with Multiple Classifiers 149
Hausdorff Distance: 150
Modified Hausdorff Distance: 151
Tanimoto Coefficient: 151
Yule Coefficient: 152
Combining Classifiers: 153
Handling Rotations 153
Educational Applications 155
Conclusion 157
References 159
Flexible Parts-based Sketch Recognition 161
Introduction 161
Algorithm Design Issues 162
Image-based vs. Stroke-based 163
Use of Timing Information 163
Top-Down vs. Bottom-Up 163
Object Template Representation 164
Degree of Supported Variation 164
Search Algorithm 164
Recognition as Search 164
Related Work 165
Hierarchy-of-Parts Models 167
Recognition Algorithm 169
Template Construction 169
Template Matching 171
Curve Matching 172
Template Hierarchy 173
Application to 3D Model Construction 174
Results and Discussion 175
Failure Modes 177
Comparison with Template Editing 177
Scalability 178
Constellation of Parts Models 178
Learning the Model 179
Labeling Likelihood 180
Recognition Algorithm 181
Results and Discussion 182
Conclusions 186
References 186
Sketch-based Retrieval of Vector Drawings 188
Introduction 188
Feature Extraction from Sketches and Drawings 189
Topology 190
Topological Relationships 190
Topology Graph 191
From Topology Graphs to Descriptors 192
Multilevel Description 193
Spatial Proximity 194
Geometry 196
Application Examples for 2D Drawings 198
Toward 3D Modeling Using Implicit Retrieval 200
Modeling 3D Technical Objects 201
Overview of the Modeling Tool 201
3D Object Description 201
Query Formulation and Execution 202
Modeling Lego Scenes 204
Part Library 204
Retrieval Mechanism 205
Results Presentation 205
Conclusions 206
References 206
Sketch-based Modeling 209
A Sketching Interface for Freeform 3D Modeling 210
Introduction 210
Related Work 212
User Interface 212
Modeling Operations 213
Overview 213
Creating a New Object 215
Painting and Erasing on the Surface 216
Extrusion 216
Cutting 217
Smoothing 218
Transformation 218
Algorithm 219
Creating a New Object 220
Painting on the Surface 221
Extrusion 222
Cutting 223
Smoothing 223
Implementation 224
User Experience 225
Conclusions 226
References 226
The Creation and Modification of 3D Models Using Sketches and Curves 229
Introduction 229
FiberMesh: Designing Freeform Surfaces with 3D Curves 230
User Interface 231
Sketching Tool 232
Deformation Tool 233
Rubbing Tool 233
Erasing Tool and Type Change Tool 234
Algorithm 234
Curve Deformation 235
Surface Optimization 237
Meshing Implementations 240
Results 241
Discussion 243
SilSketch: Automated Sketch-based Editing of Surface Meshes 244
Interface 247
Image-Space Silhouettes 247
Silhouette Detection 248
Silhouette Extraction 248
Handle Estimation 250
Finding Handle/Target Correspondences 252
ROI Estimation 253
Results 254
Discussion 254
Conclusion 255
References 256
Sketch-based Modeling and Assembling with Few Strokes 258
Introduction 258
Related Work 261
Stroke Capture 263
Creation Phase 265
Rotational Blending Surface 265
Cross-Sectional Blending Surfaces 268
Editing Phase 269
Orthogonal Deformation Stroke 271
Cross-Sectional Oversketch 273
Transformation Stroke 274
Stroke Interpretation 275
Translation 276
Active Model 276
Rotation 278
Scaling 279
Results and Discussion 280
Gestural Modeling 280
Transformation Stroke 282
Conclusions 283
References 288
ShapeShop: Free-Form 3D Design with Implicit Solid Modeling 290
Introduction 290
The ShapeShop Interface 292
Pencil-based Interaction 292
Sketching Assistance 294
Sketch-based Modeling Operations 296
Blobby Inflation 296
Sweep Surfaces 297
Cutting 297
Blending 297
Surface Drawing 298
Selection and Transformation 299
Technical Details 301
Hierarchical Implicit Volume Modeling 301
BlobTree Visualization 303
Sketchable Implicit Sweep Primitives 305
Hierarchical Spatial Caching 308
The ShapeShop System 310
Discussion 311
References 313
Inferring 3D Free-Form Shapes from Complex Contour Drawings 316
Introduction 316
Overview and Background 318
Related Work 321
Shape from Drawings. 321
Contour Completion. 321
Sketching Interfaces. 322
Notation and Problem Formulation 322
Figural Completion for Smooth Surfaces 324
Preprocessing an Input Stroke and Guessing T-points and Cusps 325
Pairwise Completion 325
Computing the Completion for a Tee/Cusp Pairing 327
Greedy Search for the Best Configuration 328
Checking the Consistency of the Pairing 330
Gluing Segments and Assigning Huffman's Labels 330
Results and Limitations of the Figural Completion Algorithm 331
From Drawing to Williams' Abstract Topological Manifold 333
Triangulating the Panels The Issue of Two Distinct Points Having the Same 2D Location
Paneling Construction 334
Creating Multiple Copies of Each Panel 334
Establishing Correspondences Between Edges of the Panels 335
Ordering the Clusters. 336
Extra Vertices. 336
Constructing a Topological Embedding 337
Embedding Vertices. 337
Embedding edges. 338
Embedding faces. 338
Smoothing the Embedding Using the Mass-Spring System 339
Editing Gestures 340
Limitations and Conclusions 341
References 342
The Creation and Modification of 3D Models Using Sketches and Curves 344
Introduction 344
Sketch-based Creation and Modification of 3D Shapes 346
Constructing the 3D Wireframe 347
Modifying the Wireframe 349
Curve Modification in the Image Plane 350
Unprojection to 3D 352
Surface Creation and Modification 353
Initial Surface Creation 353
Surface Modification 355
Surface Modification Using Pressure Force 355
Surface Modification Using V-Spring Method 356
Examples 358
Creating 3D Shape Templates from Sketches for Automotive Styling Design 359
Overview 361
Template Alignment 363
Template Deformation Based on Fiducial Points 363
Edge Representation and Manipulation 364
Surface Representation and Manipulation 366
Examples 366
Conclusions 367
References 368
Dressing and Hair-Styling Virtual Characters from a Sketch 371
Introduction 371
Sketching in Distance Fields: Application to Garment Design 373
Expressing Prior Knowledge 374
The Sketch-based Interface 374
Typical Garment Design Session 374
Contour Mode 375
Front/Back Modes 375
Vertical Symmetry. 376
Gestural Interface Components. 376
Construction of the Garment Surface in 3D 376
Distance Field 377
Converting the 2D Contours into 3D 378
Surface Generation from 3D Contours 378
Mimicking Cloth Tension. 379
Drawing Folds 379
Folding Mode. 380
Incorporating Geometric Properties: Sketch-based Modeling of Developable Surfaces 381
Expressing Prior Knowledge 382
Sketching Seams and Darts 383
Creating a Developable Surface via Approximation 383
Creating a Developable Surface Directly from the 3D Boundary Lines 384
Automatic Generation of Folds 387
Physically-based Simulation of Folds 387
Procedural Generation of Folds 387
Sketch-based Interface for a Physically-based System: Hairstyle Design from a Sketch 387
Expressing Prior Knowledge 389
The Sketch-based Interface 389
Hairline 390
Example Strands 390
Volume and Cut 390
Shaping the Hair in 3D 390
Determining Helical Parameters 391
Generalizing to a Full Head of Hair 392
Setting the Volume, Adjusting the Cut 393
Discussion and Concluding Remarks 395
Mapping to a Procedural Model 395
Simplifying Assumptions 396
Non-intrusive Sketching Interface 396
Sketching vs. Annotation 396
References 396
Index 398