REGEO
Sketch-Based Modelling Group
| REGEO
Sketch-Based Modelling Group |
Sketch-Based Modelling |
|
Sketching is an established part of engineering culture. Sketches assist product designers during the creative stages of design and help them to develop inventions. However, paper-and-pencil sketching is disconnected from the rest of the (Computer-Aided) design process. We desire Computer-Aided Sketching (CAS) tools which furnish users with the sketching environment they require to make full use of their conceptual design and innovation talents, while providing full integration with the subsequent phases of the design processes (CAD, CAE, CAM, etc.)
In creating such tools, we make use of ideas from the field of Sketch-based interfaces and modeling (SBIM). SBIM is an emerging research field which aims to create the computer tools required to shift to a new paradigm: sketches should be used as input to create digital engineering models in a true computer-aided ideation environment. In such an environment, informal and unstructured ideation processes could flow freely, and final 3D shapes would be automatically derived from such ideation processes.
We consider SBIM to be divided into three main spheres of work:
Sketch understanding
3D Modelling
Knowledge-based interpretationIn turn, those spheres of work are divided in different sectors, which have different states-of-the-art. So, to gain more insight on SBIM, we next survey most of the sectors and mention some of their most relevant references:
The importance of sketching in engineering design
In parallel with the Sutherlad's Sketchpad, which was the first program that allowed the user to create graphical images directly on the computer screen by means of a light pen, Johson’s Sketchpad III added three-dimensional modeling to Sutherland’s system. But it was Roberts who first tryied to automatically perceive 3D shapes from 2D line-drawings:
Sutherland IE. (1963) Sketchpad, a man-machine graphical communication system. Ph.D. thesis, M.I.T., Cambridge, MA USA
Johnson TE. (1963) Sketchpad III, three dimensional graphical communication with a digital computer. PhD Thesis. M.I.T., Cambridge, MA USA
Roberts LG. (1963) Machine perception of three-dimensional solids. Ph.D. thesis, MIT Dep. of Electrical Engineering
The pioneer work of Perkins, as part of the "Project Zero", analysed how people perceive drawings as representing objects, which geometrical relationships must be obeyed, and the circumstances in which geometrical relationships can be ignored:
Perkins D.N. (1968) Cubic Corners, Quarterly Progress Report 89, 207-214, MIT Research Laboratory of Electronics
Perkins D.N. (1971) Cubic Corners, Oblique Views of Pictures, the Perception of Line Drawings of Simple Space Forms. Geometry and the Perception of Pictures: Three Studies. Harvard Project Zero. Technical Report No. 5.
The importance of sketching in engineering design
Not all designers use sketches. And some design strategies avoid using sketches at all. But sketches are useful for most designers, as there is a lot of evidence that engineering sketches enhance creativity. To cite but a few selected references:
Negroponte N. (1975) Sketching: A Computational Paradigm for Personalized Searching. JAE, Vol. 29, No. 2, pp. 26-29.
Ullman D., Wood S., Craig D. (1990) The Importance of Drawing in the Mechanical Design Process, Computers and Graphics 14(2):263-274
Cugini U. (1991) The problem of user interface in geometric modeling. Computers in Industry; 17(4): 335-339
Ferguson E.S. Engineering and the Mind's Eye. Cambridge, MA: The MIT Press, 1994
Dori D., Tombre K. (1995) From engineering drawings to 3D CAD models: are we ready now?. Computer-Aided Design; 27(4): 243-254
Ullman D.G. (2002) Toward the ideal mechanical engineering design support system. Research in Engineering Design, 13(2): 55-64
Sugihara published the first comprehensive review. He was is still more concerned with geometry than with perception. Hence, he was very interested in the "realizability" of the drawings as projections of 3D physically plausible models:
Sugihara K. Machine interpretation of line drawings. Cambridge, MA: The MIT Press, 1986
Nagenda and Gujar published a comment on eleven papers published between 1973 and 1984 on this topic, including a categorization tree. Wang and Grinstein updated the categorization, and obtained a taxonomy of 3D objects reconstruction from line drawings in two-dimensional projection:
Nagendra I.V., Gujar U.G.(1988) 3-D objects from 2-D orthographic views - A survey. Computers & Graphics; 12(1): 111-114
Wang W., Grinstein G. (1993) A survey of 3D solid reconstruction from 2D projection line drawings. Computer Graphics Forum; 12(2): 137-158
The most recent comprehensive review, by Martin Cooper, is still geometry centric:
Cooper M. Line drawing interpretation. Springer, 2008.
A theoretical study by Goel considers the problem of understanding and making explicit the mental processes behind, and the messages conveyed by, engineering sketches:
Goel. V.(1995) Sketches of Thought. The MIT Press
Finally, the most recent surveys can be found here:
Company P., Piquer A., Contero M., Naya F. (2005) A Survey on Geometrical Reconstruction as a Core Technology to Sketch-Based Modeling. Computers & Graphics 29 (6) 892-904
Olsen L., Samavati F.F., Costa Sousa M., Jorge J.A. (2009) Sketch-based modeling: A survey. Computers and Graphics 33 (1) 85-103
Johnson G., Gross M.D., Hong J. and Do E.Y. (2009), "Computational support for sketching in design: A review". Foundations and Trends in Human–Computer Interaction. Vol. 2, No. 1, 1–93
Pen-based input (also named as Pen-driven Computing, or simply Pen Computing), is the method where a pen on a sensitive screen (i.e. a tablet) substitutes keyboard and mouse as user interface. Typing is substituted by handwriting, and menus are replaced by gestures. Hence, recognition of both handwriting and gestures are the main tasks linked to those devices. Some commercial libraries may recognize handwriting and/or gestures. Tablet PC Platform SDK by Microsoft (c) is one of them:
Jarret R. and Su P. Building Tablet PC applications. Microsoft Press, 2002.
Unfortunately, those commercial solutions neither solve all the aspects of handwriting and gestures recognition, nor cope with the particular problems of input and interpretation of drawings. The task that goes from engineering drawings to a symbolic description of those drawings has been named as "Sketch Based Interface":
Sezgin T.M., Stahovich T., Davis R. (2001) Sketch Based Interfaces: Early Processing for Sketch Understanding. Proceeding SIGGRAPH '06 ACM SIGGRAPH
If the original drawing is made on actual paper, the input may be done by scanning the drawing and producing a raster image, which, in turn, must be vectorised to produce strokes. So, converting sketched input into discrete strokes is itself non-trivial:
Hilaire X. and Tombre K. (2006) Robust and accurate vectorization of line drawings. IEEE Trans. Pattern Analysis and Machine Intelligence, 28 (6), pp. 890-904
This old goal of extracting full information from buelprints (i.e archaeological recovery of know-how) is still alive in architecture:
Xuetao Y., Wonka, P., Razdan, A. (2009) Generating 3D Building Models from Architectural Drawings: A Survey . IEEE Computer Graphics and Applications, 29 (1), 20-30
The next step is converting strokes into lines. Here, some practical application are available as public libraries, as the Jorge and Fonseca's CALI:
Jorge J.A. and Fonseca M.J. (1999) A Simple Approach to Recognize Geometric Shapes Interactively GREC
Yet, the basic problem is detecting those strokes that convey straight or curved lines, and obtain them. The most popular academic contributions are still based on Sparse Pixel Vectorisation (SPV) algorithm, but Bartolo et al.’s recent work is interesting as it describes the particular problem of extracting lines from scribbled drawings:
Dori, D. and Wenyin Liu. (1999) Sparse pixel vectorization: an algorithm and its performance evaluation, Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.21, no.3, pp.202-215
Bartolo A. Camilleri K.P. Fabri S.G. Borg J.C. (2008) "Line tracking algorithm for scribbled drawings," Communications, Control and Signal Processing, 2008. ISCCSP 2008. 3rd International Symposium on , vol., no., pp.554-559, 12-14
To get a suitable conversion of strokes into lines, strokes must be previously grouped and/or broken down in the same way as humans do. Those tasks, that are perception-based, are named as overtracing and segmentation; although interspersing is also important for those approaches that rely on drawing sequence. The common strategy to solve segmentation is finding corners:
Ku D.C., Qin S.F. and Wright D.K. (2006) Interpretation of Overtracing Freehand Sketching for Geometric Shapes. WSCG’2006
Sezgin, T.M., Davis, R. (2008) Sketch recognition in interspersed drawings using time-based graphical models. Computers and Graphics 32 (5), pp. 500-510
Xiong, Y. and LaViola J. (2010) A ShortStraw-Based Algorithm for Corner Finding in Sketch-Based Interfaces, Computers and Graphics, 34(5):513-527
Note that interpreting overtracing in freehand sketches is a solved problem only for sketches that contain no auxiliary lines. We distinguish different kinds of overtracing: decoration (introducing shadows, textures and so on), thinking over the line (thinking about the design without stopping the inking process) and auto-correction (perceiving that the line is being drawn with error and trying to correct it on the fly). Overtracing for decoration conveys extra information (e.g. curvatures), while thinking and auto-correction overtracing should be interpreted as simple lines:
Company P. and Varley P.A.C. (2009) Operating modes in actual versus virtual paper-and-pencil design scenarios. Intelligent User Interfaces (IUI) Workshop on Sketch Recognition, 2009.
Inflation or "fleshing out" freeform shapes
Takeo Igarashi is one of the best-known contributors. His program TEDDY has found many uses (and imitators):
Igarashi T., Matsuoka S., Tanaka H. (1999) Teddy: a sketching interface for 3D freeform design. Proceedings of ACM SIGGRAPH ’99, Los Angeles, California 8-13, 409-416
Andre's CrossSketch makes use of Perkins's Cubic Corners method, which had previously only been used in interpreting drawings of analytical shapes. Liu and Lee have made a few minor improvements to the idea:
Alexis A., Suguru S. and Masayuki N. (2007) CrossSketch: freeform surface modeling with details SBIM '07 Proceedings of the 4th Eurographics workshop on Sketch-based interfaces and modeling
Liu Y. and Lee Y.T. (2010) 3D reconstruction of freeform shapes from 2D line drawings VRCAI '10 Proceedings of the 9th ACM SIGGRAPH Conference on Virtual-Reality Continuum and its Applications in Industry
The current state of the art of input of engineering objects with functional curves is probably Wang et al, while Roth-Koch and Westkaemper give some insight on their usefulness for engineering design purposes:
Wang Y., Chen Y., Liu J. and Tang X. (2009) 3D Reconstruction of Curved Objects from Single 2D Line Drawings IEEE Conference on Computer Vision and Pattern Recognition CVPR 2009, pp. 1834-1841
Roth-Koch S. and Westkaemper E. (2010) The implementation of a sketch-based virtual product development. Prod. Eng. Res. Devel. 4:175–183
There are two different research lines, which consider wireframe vs. natural line drawings.
In wireframe, Marill was first in using the optimization approaches for inflation purposes. Later, Leclerc and Fischler introduced analitical formulation of some regularities detected in the input drawing. Lipson and Shpitalni improved the approach and gave consistent formulations for a set of regularities:
Marill T. (1991) Emulating the human interpretation of line-drawings as three-dimensional objects. Int. J. of Computer Vision; 6(2): 147-161.
Leclerc Y, Fischler M. (1992) An optimization-based approach to the interpretation of single line drawings as 3D wire frames. Int. J. of Computer Vision; 9(2): 113-136
Lipson H, Shpitalni M. (1996) Optimization-based reconstruction of a 3D object from a single freehand line drawing. Computer-Aided Design; 28(8): 651-663
As was already noted by Leclerc and Fischer, and by Lipson and Shpitalni, optimization-based inflation does not alwas produce the desired model. Hence, some kind of pre and post inflation, or some "refinements", may be necessary:
Company P, Contero M, Conesa J, Piquer A. (2004) An optimisation-based reconstruction engine for 3D modeling by sketching. Computers & Graphics; 28(6): 955-979
Clowes-Huffman line labelling (catalogue labelling) is a well-established technique. The original purpose of line labelling was as a method of identifying and rejecting impossible drawings. But line labelling also has many other uses. For instance, Labelling is a useful input to inflation. Departing from labelling approaches, Varley has obtained some practical solutions for natural line-drawing interpretation by recreating a complete wireframe. In an alternative approach, Suh models the object as unions and intersections of extrusions:
Cloves M.B. (1971). On seeing things. Artificial Intelligence, 2, 76-116
Huffman D.A. (1971). Impossible objects as nonsense sentences. Machine Intelligence, 6, pages 295-323.
Varley P.A.C. Automatic Creation of Boundary-Representation Models from Single Line Drawings PhD Thesis, Department of Computer Science, Cardiff University, 2003.
Varley P.A.C., Martin R.R. and SuzukiH. (2005) Frontal Geometry from Sketches of Engineering Objects: Is Line Labelling Necessary? Computer Aided Design 37(12), 1285-1307
Suh Y.S.(2007) Reconstructing 3D Feature-Based CAD Models By Recognizing Extrusions From A Single-View Drawing, Proc. IDETC/CIE 2007)
Design Intent and CAD have been linked for many time. Back in 1989 Design Intent was associated with design constraints and the methods of manipulating design constraints during product design activities (Kimura and Suzuki):
Kimura F. and Suzuki H. (1989) A CAD System for Efficient Product Design Based on Design Intent. CIRP Annals - Manufacturing Technology , 38 (1), 149-152.
When CAD people use the word “design”, they usually mean “model”, hence Design intent equates to Design for Change. However, we understand design intent as a mix of geometry, psychology and engineering (or shape, perception and function).
Consequently, we define Design Intent as the set of intentions in sketches conveyed though cues, which, when perceived, reveal regularities or features of the object:Company P. and Varley P.A.C. “Sketch Input of Engineering Solid Models” Eurographics 2011. Tutorial 2. Llandudno, April 11th 2011. Part 1 Part 2 Part 3 Part 4
When geometry dominates, design intent is mainly conveyed through geometrical features, which have already been studied as “regularities":
Lipson H, Shpitalni M. (1996) Optimization-based reconstruction of a 3D object from a single freehand line drawing. Computer-Aided Design; 28(8): 651-663
Yuan S., Tsui L.Y., Jie S. (2008). Regularity selection for effective 3D objects reconstruction from a single line drawing. Pattern Recognition Letters 29 (10), 1486-1495
Li M., Langbein F.C. and Martin R.R.(2010) Detecting design intent in approximate CAD models using symmetry. Computer-Aided Design 42 (3) 183-201
We note, in passing, that even well studied problems, like the classic detection of faces in wireframes of polyhedral objects, are not yet fully solved:
Markowsky G. and Wesley M.A. (1980). Fleshing Out Wire Frames, IBM Journal of Research and Development, 24(5) 582–597.]
Shpitalni M. and Lipson H. (1996). Identification of Faces in a 2D Line Drawing Projection of a Wireframe Object, IEEE Transactions on Pattern Analysis and Machine Intelligence 18(10), 1000–1012.
Liu J. and Tang X. (2005). Evolutionary Search for Faces from Line Drawings, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(6), 861–872.
Varley P.A.C. and Company P. (2010) A new algorithm for finding faces in wireframes. Computer-Aided Design 42 (4), 279-309
When psychology dominates, replicating human perception strategies becomes a challenging tasks, as we hardly understand how humans perceive. Information not explicitly included in the drawings is perceived through “perceptual cues” (sometimes clues). Fundamentals of perceptual cues have been studied by psychologists. The work by Tversky may give some light and break some false myths. People interested in the foundations of the human perception should also read the book by Palmer (more comprehensive), or the one by Hoffmman (more aimed at an "algorithmic" application) :
Palmer S.E. Vision Science, Photons to Phenomenology, Cambridge, MA: The MIT Press, 1999
Hoffmann D. Visual Intelligence. How we create what we see, New York: WW Norton & Company, 2000
When engineering dominates, design intent is mainly conveyed through “engineering features”. People interested in this ambit, could start by reading the term "feature recognition" in Wikipedia. In short, this means that we should perceive drills, instead of cylindrical holes; or rounds, instead of blendings surfaces :
Company P. and Varley P.A.C. (2010) A Method for Reconstructing Sketched Polyhedral Shapes with Rounds and Fillets. R. Taylor et al. (Eds.). Lecture Notes in Computer Science. Smart Graphics 2010 Proceedings. Volume 6133. 2010, pp 152-155
Producing 3D models from annotated engineering drawings is an open problem. Although some attempts have been done in interpreting engineering drawings mixed with annotations (i.e. Company et al.), the state of the art in sketched annotations may be traced through the "classical" Ladder, by Hammond and Davis, and the recent MathPad by LaViola :
Company P., Aleixos N., Naya F., Varley P.A.C., Contero M. and Fernandez-Pacheco D.G. (2008) A New Sketch-Based Computer Aided Engineering Pre-Processor. Proc. Sixth Int. Conf. on Engineering Computational Technology. Civil comp Ltd. Paper-149.
Hammond T., and Davis R. 2003. Ladder: A language to describe drawing, display, and editing in sketch recognition. Proc. of the 2003 Int. Joint Conference on Artificial Intelligence (IJCAI).
LaViola J. (2007) Advances in Mathematical Sketching: Moving Toward the Paradigm's Full Potential, IEEE Computer Graphics and Applications, 27(1):38-48
Sketch-Based Modelling (SBM) tools have been developed to some extent. But, DESIGNERS do not yet use SBM tools! User studies assert that current SBM tools are still less usable than paper and pencil sketches, and do not possess significantly improved functionality. User interfaces aimed at Sketch-Based Modelling have been developed at some extent, but more work is required:
Johnson G., Gross M.D., Hong J. and Do E.Y. (2009) Computational Support for Sketching in Design: A Review. Foundations and Trends in Human–Computer Interaction. 2 (1), pp. 1–93
Perhaps, Sculptris by “Dr Petter” is a successful example of what we should be looking for. But we are far from the ideal interface. Some of the main problems are summarized here:
Company P. and Varley P.A.C. (2009) Operating modes in actual versus virtual paper-and-pencil design scenarios. Intelligent User Interfaces (IUI) Workshop on Sketch Recognition, 2009.
We implement our propossals in C++. At this end, we do recomend the book by Eckel. Besides, we use Microsoft Foundation Classes (Yes, a wysiwyg interface!) to experiment our ideas. For that, we have found very useful the book by Jones:
Eckel B. Thinking in C++. Volume one: introduction to standard C++. Prentice Hall. second edition, 2000.
Jones R.M. Introduction to MFC Programming with Visual C++. Prentice Hall, 2000.
Legal warning: Pedro Company, responsible of this assigned web space (
http://www.regeo.uji.es), communicates to the visitors that he assumes
responsibility for veracity, exactness and updating of contents here
provided. In no case can take responsibility to the Universitat Jaume I
for possible damages than may derive.
Back to presentation
|
05.05.2011
Send any comments to: Webmaster |