Jorge / Samavati Sketch-based Interfaces and Modeling

1. Auflage 2010
ISBN: 978-1-84882-812-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 402 Seiten

The field of sketch-based interfaces and modeling (SBIM) is concerned with developing methods and techniques to enable users to interact with a computer through sketching - a simple, yet highly expressive medium. SBIM blends concepts from computer graphics, human-computer interaction, artificial intelligence, and machine learning. Recent improvements in hardware, coupled with new machine learning techniques for more accurate recognition, and more robust depth inferencing techniques for sketch-based modeling, have resulted in an explosion of both sketch-based interfaces and pen-based computing devices. Presenting the first coherent, unified overview of SBIM, this unique text/reference bridges the two complementary research areas of user interaction (sketch-based interfaces), and graphical modeling and construction (sketch-based modeling). The book discusses the state of the art of this rapidly evolving field, with contributions from an international selection of experts. Also covered are sketch-based systems that allow the user to manipulate and edit existing data - from text, images, 3D shapes, and video - as opposed to modeling from scratch. Topics and features: reviews pen/stylus interfaces to graphical applications that avoid reliance on user interface modes; describes systems for diagrammatic sketch recognition, mathematical sketching, and sketch-based retrieval of vector drawings; examines pen-based user interfaces for engineering and educational applications; presents a set of techniques for sketch recognition that rely strictly on spatial information; introduces the Teddy system; a pioneering sketching interface for designing free-form 3D models; investigates a range of advanced sketch-based systems for modeling and designing 3D objects, including complex contours, clothing, and hair-styles; explores methods for modeling from just a single sketch or using only a few strokes. This text is an essential resource for researchers, practitioners and graduate students involved in human-factors and user interfaces, interactive computer graphics, and intelligent user interfaces and AI.

Autoren/Hrsg.

Jorge, Joaquim

Samavati, Faramarz

Inhaltsverzeichnis

1;Sketch-based Interfaces and Modeling;2
1.1;Foreword;4
1.2;Preface;7
1.3;Contents;9
2;Introduction;11
2.1;Sketch-based Interfaces;11
2.1.1;Sketching Issues and Research Topics in HCI;13
2.1.2;Recognition;14
2.1.3;Modes;15
2.1.4;Sketch-based Applications;16
2.2;Creation and Modification of 3D Models;17
2.2.1;Suggestive Systems;18
2.2.2;Constructive Systems;19
2.2.3;Augmentation;21
2.2.4;Deformation;22
2.2.5;Modeling Applications;23
2.3;References;24
3;Sketch-based Interfaces;26
3.1;Multi-domain Hierarchical Free-Sketch Recognition Using Graphical Models;27
3.1.1;Introduction;27
3.1.2;The Challenges of Free-Sketch Recognition;29
3.1.3;Knowledge Representation;31
3.1.3.1;Hierarchical Shape Descriptions;32
3.1.3.2;Handling Noise in the Drawing;34
3.1.3.2.1;Signal-Level Noise: Objective vs. Subjective Measures;34
3.1.3.2.2;Description-Level Variation: Optional Components and Constraints;35
3.1.3.3;Strengths and Limitations;36
3.1.4;Recognition Overview;37
3.1.5;Hypothesis Evaluation;38
3.1.5.1;Dynamically Constructed Graphical Models;39
3.1.5.2;Shape Fragments: Evaluating a Single Hypothesis;40
3.1.5.2.1;Network Structure;41
3.1.5.2.2;Conditional Probability Distributions;43
3.1.5.2.3;Observing Evidence from Stroke Data;44
3.1.5.3;Recognizing a Complete Sketch;44
3.1.5.3.1;Linking Shape Fragments;47
3.1.5.3.2;Missing Nodes;47
3.1.5.4;Implementation and Bayesian Inference;48
3.1.6;Hypothesis Generation;49
3.1.6.1;Selecting an Interpretation;51
3.1.7;Application and Results;52
3.1.8;Remaining Challenges and Extensions;56
3.1.8.1;Using Single-Stroke Classification to Improve Grouping;57
3.1.9;Conclusion;59
3.1.10;References;60
3.2;Minimizing Modes for Smart Selection in Sketching/Drawing Interfaces;63
3.2.1;Introduction;63
3.2.2;The Cost of Modes;65
3.2.2.1;The Temporal Cost of Modes;65
3.2.2.2;Mode Errors: The Mode Problem;66
3.2.3;Overloaded Loop Selection: UI Design to Infer Selection Mode;68
3.2.4;The Inferred Mode Protocol for Stylus Drawing and Selection with a Pen;70
3.2.4.1;The Mode Problem in Electronic Whiteboard Programs;70
3.2.4.2;Analytical Tool: The Interaction Flow Diagram;72
3.2.4.3;Interaction Flow Analysis of Mode-Based Selection and Drawing;74
3.2.4.4;Inferred Mode Protocol: Inferring Draw/Select Mode;77
3.2.5;Sloppy Selection: Inferring Intended Content of an Ambiguous Selection;80
3.2.6;Cycle Tap Selection: Exploiting Structure Recognition;81
3.2.7;Conclusion;87
3.2.8;References;87
3.3;Mathematical Sketching: An Approach to Making Dynamic Illustrations;89
3.3.1;Introduction;89
3.3.1.1;Mathematical Sketching;90
3.3.2;Philosophical Considerations;91
3.3.2.1;Generalizing Mathematical Sketching as a Paradigm;93
3.3.2.2;Observations on Mathematical Sketching;94
3.3.3;The MathPad2 Prototype;95
3.3.3.1;MathPad2 Architecture;95
3.3.3.2;The Gestural UI;97
3.3.3.2.1;Writing, Recognizing, and Correcting Mathematics;98
3.3.3.2.2;Making Drawings;100
3.3.3.2.3;Nailing Diagram Components;100
3.3.3.2.4;Grouping Diagram Components;101
3.3.3.2.5;Associations;101
3.3.3.2.5.1;Implicit Associations;101
3.3.3.2.5.2;Explicit Associations;102
3.3.3.2.6;Supporting Mathematical Toolset;102
3.3.3.2.6.1;Graphing Equations;103
3.3.3.2.6.2;Solving Equations;103
3.3.3.2.6.3;Evaluating Expressions;104
3.3.3.3;Mathematical Expression Recognition;104
3.3.3.3.1;Mathematical Symbol Recognition;105
3.3.3.3.2;Mathematical Expression Parsing;106
3.3.4;Preparing Mathematical Sketches;108
3.3.4.1;Association Inferencing;108
3.3.4.2;Drawing Dimension Analysis;109
3.3.4.3;Drawing Rectification;110
3.3.4.3.1;Angle Rectification;111
3.3.4.3.2;Location Rectification;111
3.3.4.3.3;Size Rectification;113
3.3.4.4;Translating and Visualizing Mathematical Sketches;115
3.3.5;Moving Forward with Mathematical Sketching;118
3.3.5.1;The Computational and Symbolic Toolset;118
3.3.5.2;Functions and Macros;119
3.3.5.3;Moving to 3D;120
3.3.5.4;Interactivity;121
3.3.5.5;Generating Mathematics from Drawings;121
3.3.5.6;Adding Specific Underlying Mathematical Engines;122
3.3.5.7;Alternate Forms of Dynamic Illustration;123
3.3.5.8;Evaluation;124
3.3.6;Conclusion;125
3.3.7;References;125
3.4;Pen-based Interfaces for Engineering and Education;127
3.4.1;Introduction;127
3.4.2;Sketch Parsing;128
3.4.2.1;Mark-Group-Recognize;129
3.4.2.2;Enumerate-Recognize-Prune;132
3.4.2.2.1;Parsing Step 1: Enumerating Candidate Symbols;133
3.4.2.2.1.1;Ink Density Locator:;134
3.4.2.2.1.2;Segment Difference Locator:;135
3.4.2.2.2;Parsing Step 2: Pruning Using Domain Knowledge;136
3.4.2.2.3;Automated Error Correction;137
3.4.3;Recognition;138
3.4.3.1;Graph-based Recognizer;139
3.4.3.1.1;Representation;139
3.4.3.1.2;Measuring Similarity;141
3.4.3.1.2.1;Primitive Count Error:;142
3.4.3.1.2.2;Primitive Type Error:;142
3.4.3.1.2.3;Relative Length Error:;143
3.4.3.1.2.4;Number of Intersections Error:;143
3.4.3.1.2.5;Intersection Angle Error:;143
3.4.3.1.2.6;Intersection Location Error:;144
3.4.3.1.3;Graph Matching;144
3.4.3.1.3.1;Stochastic Matching;145
3.4.3.1.3.2;Greedy Matching;145
3.4.3.1.3.3;Hybrid Matching;146
3.4.3.1.4;Training;146
3.4.3.2;Feature-based Recognizer;146
3.4.3.3;Image-based Recognizer;148
3.4.3.3.1;Representation;149
3.4.3.3.2;Template Matching with Multiple Classifiers;149
3.4.3.3.2.1;Hausdorff Distance:;150
3.4.3.3.2.2;Modified Hausdorff Distance:;151
3.4.3.3.2.3;Tanimoto Coefficient:;151
3.4.3.3.2.4;Yule Coefficient:;152
3.4.3.3.2.5;Combining Classifiers:;153
3.4.3.3.3;Handling Rotations;153
3.4.4;Educational Applications;155
3.4.5;Conclusion;157
3.4.6;References;159
3.5;Flexible Parts-based Sketch Recognition;161
3.5.1;Introduction;161
3.5.1.1;Algorithm Design Issues;162
3.5.1.2;Image-based vs. Stroke-based;163
3.5.1.3;Use of Timing Information;163
3.5.1.4;Top-Down vs. Bottom-Up;163
3.5.1.5;Object Template Representation;164
3.5.1.6;Degree of Supported Variation;164
3.5.1.7;Search Algorithm;164
3.5.1.8;Recognition as Search;164
3.5.2;Related Work;165
3.5.3;Hierarchy-of-Parts Models;167
3.5.3.1;Recognition Algorithm;169
3.5.3.2;Template Construction;169
3.5.3.3;Template Matching;171
3.5.3.4;Curve Matching;172
3.5.3.5;Template Hierarchy;173
3.5.3.6;Application to 3D Model Construction;174
3.5.3.7;Results and Discussion;175
3.5.3.8;Failure Modes;177
3.5.3.9;Comparison with Template Editing;177
3.5.3.10;Scalability;178
3.5.4;Constellation of Parts Models;178
3.5.4.1;Learning the Model;179
3.5.4.2;Labeling Likelihood;180
3.5.4.3;Recognition Algorithm;181
3.5.4.4;Results and Discussion;182
3.5.5;Conclusions;186
3.5.6;References;186
3.6;Sketch-based Retrieval of Vector Drawings;188
3.6.1;Introduction;188
3.6.2;Feature Extraction from Sketches and Drawings;189
3.6.2.1;Topology;190
3.6.2.1.1;Topological Relationships;190
3.6.2.1.2;Topology Graph;191
3.6.2.1.3;From Topology Graphs to Descriptors;192
3.6.2.1.4;Multilevel Description;193
3.6.2.1.5;Spatial Proximity;194
3.6.2.2;Geometry;196
3.6.3;Application Examples for 2D Drawings;198
3.6.4;Toward 3D Modeling Using Implicit Retrieval;200
3.6.4.1;Modeling 3D Technical Objects;201
3.6.4.1.1;Overview of the Modeling Tool;201
3.6.4.1.2;3D Object Description;201
3.6.4.1.3;Query Formulation and Execution;202
3.6.4.2;Modeling Lego Scenes;204
3.6.4.2.1;Part Library;204
3.6.4.2.2;Retrieval Mechanism;205
3.6.4.2.3;Results Presentation;205
3.6.5;Conclusions;206
3.6.6;References;206
4;Sketch-based Modeling;209
4.1;A Sketching Interface for Freeform 3D Modeling;210
4.1.1;Introduction;210
4.1.2;Related Work;212
4.1.3;User Interface;212
4.1.4;Modeling Operations;213
4.1.4.1;Overview;213
4.1.4.2;Creating a New Object;215
4.1.4.3;Painting and Erasing on the Surface;216
4.1.4.4;Extrusion;216
4.1.4.5;Cutting;217
4.1.4.6;Smoothing;218
4.1.4.7;Transformation;218
4.1.5;Algorithm;219
4.1.5.1;Creating a New Object;220
4.1.5.2;Painting on the Surface;221
4.1.5.3;Extrusion;222
4.1.5.4;Cutting;223
4.1.5.5;Smoothing;223
4.1.6;Implementation;224
4.1.7;User Experience;225
4.1.8;Conclusions;226
4.1.9;References;226
4.2;The Creation and Modification of 3D Models Using Sketches and Curves;229
4.2.1;Introduction;229
4.2.2;FiberMesh: Designing Freeform Surfaces with 3D Curves;230
4.2.2.1;User Interface;231
4.2.2.1.1;Sketching Tool;232
4.2.2.1.2;Deformation Tool;233
4.2.2.1.3;Rubbing Tool;233
4.2.2.1.4;Erasing Tool and Type Change Tool;234
4.2.2.2;Algorithm;234
4.2.2.2.1;Curve Deformation;235
4.2.2.2.2;Surface Optimization;237
4.2.2.2.3;Meshing Implementations;240
4.2.2.3;Results;241
4.2.2.4;Discussion;243
4.2.3;SilSketch: Automated Sketch-based Editing of Surface Meshes;244
4.2.3.1;Interface;247
4.2.3.2;Image-Space Silhouettes;247
4.2.3.2.1;Silhouette Detection;248
4.2.3.2.2;Silhouette Extraction;248
4.2.3.3;Handle Estimation;250
4.2.3.4;Finding Handle/Target Correspondences;252
4.2.3.5;ROI Estimation;253
4.2.3.6;Results;254
4.2.3.7;Discussion;254
4.2.4;Conclusion;255
4.2.5;References;256
4.3;Sketch-based Modeling and Assembling with Few Strokes;258
4.3.1;Introduction;258
4.3.2;Related Work;261
4.3.3;Stroke Capture;263
4.3.4;Creation Phase;265
4.3.4.1;Rotational Blending Surface;265
4.3.4.2;Cross-Sectional Blending Surfaces;268
4.3.5;Editing Phase;269
4.3.5.1;Orthogonal Deformation Stroke;271
4.3.5.2;Cross-Sectional Oversketch;273
4.3.6;Transformation Stroke;274
4.3.6.1;Stroke Interpretation;275
4.3.6.2;Translation;276
4.3.6.2.1;Active Model;276
4.3.6.3;Rotation;278
4.3.6.4;Scaling;279
4.3.7;Results and Discussion;280
4.3.7.1;Gestural Modeling;280
4.3.7.2;Transformation Stroke;282
4.3.8;Conclusions;283
4.3.9;References;288
4.4;ShapeShop: Free-Form 3D Design with Implicit Solid Modeling;290
4.4.1;Introduction;290
4.4.2;The ShapeShop Interface;292
4.4.2.1;Pencil-based Interaction;292
4.4.2.2;Sketching Assistance;294
4.4.2.3;Sketch-based Modeling Operations;296
4.4.2.3.1;Blobby Inflation;296
4.4.2.3.2;Sweep Surfaces;297
4.4.2.3.3;Cutting;297
4.4.2.3.4;Blending;297
4.4.2.3.5;Surface Drawing;298
4.4.2.4;Selection and Transformation;299
4.4.3;Technical Details;301
4.4.3.1;Hierarchical Implicit Volume Modeling;301
4.4.3.2;BlobTree Visualization;303
4.4.3.3;Sketchable Implicit Sweep Primitives;305
4.4.3.4;Hierarchical Spatial Caching;308
4.4.4;The ShapeShop System;310
4.4.5;Discussion;311
4.4.6;References;313
4.5;Inferring 3D Free-Form Shapes from Complex Contour Drawings;316
4.5.1;Introduction;316
4.5.2;Overview and Background;318
4.5.3;Related Work;321
4.5.3.1;Shape from Drawings.;321
4.5.3.2;Contour Completion.;321
4.5.3.3;Sketching Interfaces.;322
4.5.4;Notation and Problem Formulation;322
4.5.5;Figural Completion for Smooth Surfaces;324
4.5.5.1;Preprocessing an Input Stroke and Guessing T-points and Cusps;325
4.5.5.2;Pairwise Completion;325
4.5.5.2.1;Computing the Completion for a Tee/Cusp Pairing;327
4.5.5.2.2;Greedy Search for the Best Configuration;328
4.5.5.2.3;Checking the Consistency of the Pairing;330
4.5.5.3;Gluing Segments and Assigning Huffman's Labels;330
4.5.5.4;Results and Limitations of the Figural Completion Algorithm;331
4.5.6;From Drawing to Williams' Abstract Topological Manifold;333
4.5.6.1;Triangulating the Panels; The Issue of Two Distinct Points Having the Same 2D Location;333
4.5.6.2;Paneling Construction;334
4.5.6.2.1;Creating Multiple Copies of Each Panel;334
4.5.6.2.2;Establishing Correspondences Between Edges of the Panels;335
4.5.6.2.2.1;Ordering the Clusters.;336
4.5.6.2.2.2;Extra Vertices.;336
4.5.7;Constructing a Topological Embedding;337
4.5.7.1;Embedding Vertices.;337
4.5.7.2;Embedding edges.;338
4.5.7.3;Embedding faces.;338
4.5.8;Smoothing the Embedding Using the Mass-Spring System;339
4.5.9;Editing Gestures;340
4.5.10;Limitations and Conclusions;341
4.5.11;References;342
4.6;The Creation and Modification of 3D Models Using Sketches and Curves;344
4.6.1;Introduction;344
4.6.2;Sketch-based Creation and Modification of 3D Shapes;346
4.6.2.1;Constructing the 3D Wireframe;347
4.6.2.2;Modifying the Wireframe;349
4.6.2.2.1;Curve Modification in the Image Plane;350
4.6.2.2.2;Unprojection to 3D;352
4.6.2.3;Surface Creation and Modification;353
4.6.2.3.1;Initial Surface Creation;353
4.6.2.3.2;Surface Modification;355
4.6.2.3.2.1;Surface Modification Using Pressure Force;355
4.6.2.3.2.2;Surface Modification Using V-Spring Method;356
4.6.2.4;Examples;358
4.6.3;Creating 3D Shape Templates from Sketches for Automotive Styling Design;359
4.6.3.1;Overview;361
4.6.3.2;Template Alignment;363
4.6.3.3;Template Deformation Based on Fiducial Points;363
4.6.3.4;Edge Representation and Manipulation;364
4.6.3.5;Surface Representation and Manipulation;366
4.6.3.6;Examples;366
4.6.4;Conclusions;367
4.6.5;References;368
4.7;Dressing and Hair-Styling Virtual Characters from a Sketch;371
4.7.1;Introduction;371
4.7.2;Sketching in Distance Fields: Application to Garment Design;373
4.7.2.1;Expressing Prior Knowledge;374
4.7.2.2;The Sketch-based Interface;374
4.7.2.2.1;Typical Garment Design Session;374
4.7.2.2.1.1;Contour Mode;375
4.7.2.2.1.2;Front/Back Modes;375
4.7.2.2.1.3;Vertical Symmetry.;376
4.7.2.2.1.4;Gestural Interface Components.;376
4.7.2.3;Construction of the Garment Surface in 3D;376
4.7.2.3.1;Distance Field;377
4.7.2.3.2;Converting the 2D Contours into 3D;378
4.7.2.3.3;Surface Generation from 3D Contours;378
4.7.2.3.3.1;Mimicking Cloth Tension.;379
4.7.2.4;Drawing Folds;379
4.7.2.4.1;Folding Mode.;380
4.7.3;Incorporating Geometric Properties: Sketch-based Modeling of Developable Surfaces;381
4.7.3.1;Expressing Prior Knowledge;382
4.7.3.2;Sketching Seams and Darts;383
4.7.3.3;Creating a Developable Surface via Approximation;383
4.7.3.4;Creating a Developable Surface Directly from the 3D Boundary Lines;384
4.7.3.5;Automatic Generation of Folds;387
4.7.3.5.1;Physically-based Simulation of Folds;387
4.7.3.5.2;Procedural Generation of Folds;387
4.7.4;Sketch-based Interface for a Physically-based System: Hairstyle Design from a Sketch;387
4.7.4.1;Expressing Prior Knowledge;389
4.7.4.2;The Sketch-based Interface;389
4.7.4.2.1;Hairline;390
4.7.4.2.2;Example Strands;390
4.7.4.2.3;Volume and Cut;390
4.7.4.3;Shaping the Hair in 3D;390
4.7.4.3.1;Determining Helical Parameters;391
4.7.4.3.2;Generalizing to a Full Head of Hair;392
4.7.4.3.3;Setting the Volume, Adjusting the Cut;393
4.7.5;Discussion and Concluding Remarks;395
4.7.5.1;Mapping to a Procedural Model;395
4.7.5.2;Simplifying Assumptions;396
4.7.5.3;Non-intrusive Sketching Interface;396
4.7.5.4;Sketching vs. Annotation;396
4.7.6;References;396
5;Index;398