InstitutNationalPolytechniquedeGrenoble Sketching and annotation for the procedural modelling of complex phenomena Jamie WITHER The`sepre´sente´epourl’obtentiondutitredeDocteurdel’INPGrenoble Spe´cialite´ Informatique Arreˆte´ ministe´rieldu5juillet1984etdu30mars1992 Pre´pare´eauseinduLaboratoireJeanKuntzmann. UMR5224. ProjetderechercheEVASION. Soutenuele24Novembre2008 Compositiondujury: Lo¨ıc BARTHE Examinateur Laurent GRISONI Rapporteur John HUGHES Rapporteur Michiel VAN DE PANNE Rapporteur Marie-Paule CANI Directricedethe`se James CROWLEY Presidentdujury 2 TABLE OF CONTENTS Introduction 5 Re´sume´ enFranc¸ais 11 Part I Background 15 1 PerceptionandDepiction 17 1.1 Perception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2 Depiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 StateoftheArt 27 2.1 Sketchprocessingtools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Sketch-basedmodellingofgeneralshapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Complex,specificshapemodellingusingpriorknowledge . . . . . . . . . . . . . . . . . . . 34 Part II Annotationof3Dmodels: Applicationstoclothingandhair 49 Re´sume´ enFranc¸ais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 Sketchingindistancefields: Applicationtogarmentdesign 55 3.1 Expressingpriorknowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Thesketch-basedinterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 Constructionofthegarmentsurfacein3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 Drawingfolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3 4 TABLEOFCONTENTS 4 Incorporatinggeometricproperties: sketch-basedmodellingofdevelopablesurfaces 65 4.1 Expressingpriorknowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 Sketchingseamsanddarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3 Creatingadevelopablesurfaceviaapproximation . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4 Creatingadevelopablesurfacedirectlyfromthe3Dboundarylines. . . . . . . . . . . . . . . 68 4.5 Automaticgenerationoffolds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.6 Positioningourwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5 Sketch-basedinterfaceforaphysically-basedsystem: Hairstyledesignfromasketch 73 5.1 Expressingpriorknowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.2 Thesketch-basedinterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.3 Shapingthehairin3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4 Positioningourwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 SummaryofPartII 85 Re´sume´ enFranc¸ais 87 Part III Structurefromsilhouettes: Applicationstoclouds,treesandterrain 89 Re´sume´ enFranc¸ais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6 Rapidsketch-basedmodellingofclouds 93 6.1 Introductionandpreviouswork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.2 Userscenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.3 Cloudshapesfromsketching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.4 Discussionandfuturework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7 Seamlessmulti-scalesketch-baseddesignoftrees 103 7.1 Knowledgeoftreestructure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.2 GeneralMethodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.3 Inferring2Dstructurefromasilhouette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.4 Sketchrefinementandstyletransfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.5 Positioningorgansin3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.6 Discussionandfuturework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.7 Positioningourwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 8 Extension: Sketchingterrain 125 SummaryofPartIII 129 Re´sume´ enFranc¸ais 131 Conclusion 133 Re´sume´ enFranc¸ais 139 TABLEOFCONTENTS 5 Appendix-Asummaryofthebook’ArtandRepresentation’ 159 6 TABLEOFCONTENTS Introduction Sketch-Aroughdrawingordelineationofsomething,givingtheoutlinesorprominentfeatures withoutthedetail,esp. oneintendedtoserveasthebasisofamorefinishedpicture,ortobeused initscomposition;aroughdraughtordesign. -OxfordEnglishDictionary “Apictureisworthathousandwords”-Proverb What do we mean by sketching? Drawingspre-datewriting[Clo00,Kra88]. Everyonecandrawtosomedegree,thoughmostabandontheprac- tice before adulthood. A drawing no matter how crude can communicate more efficiently than words, and is independentoflanguage. Drawingisthebasicskillunderpinningmostvisualarts,whetherpainting,sculpture, architecture,fashiondesign,productdesignorcomputergeneratedimagery(CGI). Asketchistheprecursortoadrawing,usuallyarapidlycreatedroughversion,usedtostudyandunderstand thethingbeingdrawn, inordertobetterrepresentit. Withrealmedia, whetherthefinaloutputisadrawing, painting or sculpture, many sketches may be made before the final composition is attempted. With virtual media too pencil and paper sketches are made before the artist turns to a specialised modelling package to begincreatingamodel. Until recently computers weren’t powerful enough to harness the use of drawing as a means of input, specifically: they couldn’t interpret a drawing in a useful fashion. An artist could certainly use a tool like photoshop or illustrator to create an image. But the image would then have no further part in the creation process, except to serve as study and inspiration. The problem of interpreting a drawing in general is still too hard for a computer to solve, especially as there are often many interpretations of a drawing (Figure 1). Thereforeevenwhenasketchisusedatthedesignstage,everythingstillhastobemodelledusinggeneral3D modellingsoftware. Inthefilmandgamesindustriesthetimebetweencommencinganddeliveringafinishedproductiscritical. Manyproductionsrequireaconsiderableamountofartist-generatednaturalcontentliketreesandplants(Fig- 7 8 INTRODUCTION Figure1: Reversibleimagesprovideevidencethatweconstructtheworldweperceive. Heretheexamplesare duck/rabbit,faces/vase,saxplayer/womansface,oldlady/youngmaid. ure2),terrain,charactersandclothing,butmodellingsuchthingsrequiresexpertiseandtime. Systemswhich reducethetimeorexperiencerequiredareaboon. Sketchingsystemscanaddressthisneed. Figure2: (left,middle)In-gameimagesfromCrysis[Cry07]. Notethenumberandvarietyoftreesandplants and the interesting terrain. Modelling these elements typically takes hours and one of the goals of this work istoreducethetimeandeffortrequiredofthedesignerthroughtheuseofsketch-basedtechniques. (right)A standardtreemodellinginterface[Gre08]. Thisthesisexplorestheuseofsketchingandannotationformodellingspecificcomplexphenomena,where somepriorknowledgecanbeusedtointerpretasketch. Themethodologyweintroducewillbeillustratedby the design of sketch-based systems for modelling clothing, hair, clouds and trees. We say “sketching” rather than“drawing”becausewetreattheuserinputasroughintentionsofformandplacement-notalwaysfaithfully reproduced but close enough to satisfy the user’s intentions. A sketch is produced quickly, and we want our modelling processes to respond quickly to the user’s input so the process flows smoothly, reducing the time takenbetweeninitialideasandfinalmodels. Automatic shape modelling from a sketch shares many of the problems encountered in the field of com- putervision. Thehumanvisualsystemisextraordinarilygoodatrapidlyrecognisingobjectsandmotionina scene,underawidevarietyoflightingandobscuringconditions. Itissogood,infact,thatwetakethisability for granted. Many years of study have gone into attempting to enable computers to replicate this feat, and yetwehavebarelybeguntounderstandtheprocessessupportingourvisualsystem. Adetaileddiscussionof thistopicisbeyondthescopeofthisthesis,butweshouldatleastplaceourtheoreticalapproachinahuman visualperceptioncontext. ThedominanttheoreticalapproachinincontemporaryvisionresearchisConstruc- tivism[Yan01],whichformedfromtheideasofHermannvonHelmholtz(1821–1894). Constructivismholds that we construct an internal representation of a scene based on the sensory information from the eyes and experience-wehavetolearnourabilitytoperceivethroughexperience. Thusourperceptionofascenecan beviewedascomingfromtwosources: “bottom-up”informationsuppliedbytheeyes,and“top-down”infor- mationsuppliedbymemoryandpriorlearning. Visualillusionssuchasreversibleimages(Figure1)provide INTRODUCTION 9 evidence to support this case. In viewing the young girl/old maid image your visual system gathers enough “bottom-up”localshapecuestomakea“top-down”guessastothenatureoftheobject. Oncealikelycandi- dateischosenyourinterpretationoftheshapecuesintheimageisre-enforcedbythisdecision. Butifyouhad startedyourviewingatsomeotherpositionyoumaywellhavechosentheoppositeinterpretationoftheimage. Ourapproachinmodellingcomplexshapesthroughsketchingisbasedonthistop-downintegrationofprior knowledgeininterpretingshape. Weconcentrateonusingpriorknowledgeofwhatistobemodelledinorder to extract parameters from sketched features, which can then be used to drive procedural or physical models whichgeneratea(potentiallydetailed)shapein3D.Theadvantageofthisapproachisthattheuserneedhave no knowledge of the underlying modelling techniques. The only requirement is the ability to draw and an understandingoftheconstraintsonwhatcanbedrawn. The artist’s approach - from global to local In addition to a perceptual “top-down” approach, we also take as inspiration the traditional global-to-local approaches used by artists. The global features are sketched in first and proportions and composition are decided upon before local detail is added. Figure 3 illustrates the evolution of a drawing of a tree in stages, Figure4illustratesasimilarprocessfordrawingarock;notethatthesamelargescaleoutlinescanhavemany differentinterpretationsdependingonthedetailsaddedatsmallerscales. Figure3:AnIllustrationoftheglobaltolocalapproachusedbyartists(from[Pow98]). Figure4: Theglobaltolocalstagesindrawingarock(from[Ham72]). Noticehowthesameinitialsketchcan berefinedindifferentwaysatthelocalscaletogetdifferentfinalshapes. 10 INTRODUCTION Figure5: Shading can strongly affect our perception of a scene, but it is also ambiguous. Would two people interpreteachoftheseshadedlandscapesinthesameway? (from[Ham72]). Itcanbeseenthatatthefinalstagetheartistmayuseshadingeffectssuchashatchingorstipplingtoadd fine detail. These shading effects can certainly have a strong effect on shape interpretation (for example the finalstagesoftherockconstructioninFigure4),howeverinthisthesiswedon’tattempttointerpretshading effects. This is for a few reasons. First, because many of the shading processes (especially hatching and stippling)aretimeconsuming,thesetechniquesbelongmoretothefinaldetailstagesofproduction,ratherthan theearlierexploratorydesignstages. Second,shadingeffectsarehighlydependentonthelightingconditions of a scene, rather than the being easily predictable from the nature of the shape in question. Finally, not everyone is able to use such techniques effectively, and concentrating on their use would exclude potential users of any resulting systems. Certainly some shading techniques can be done quickly and could enhance a sketch based modelling system, but consider Figure 5. Here the shading is the only thing changing, and it allowsmanydifferentinterpretationsofthescenepresented. Overcomingsuchambiguityisadifficultproblem worthyoffutureresearch.Muchusefulresearchhasbeendoneinapproachingtheproblemofshadingfromthe opposite direction (non-photo realistic rendering), so once the shape has been determined via a sketch-based modellingapproach,detailedshadingcanbeaddedautomatically. ForexampleFigure6illustratesautomatic determinationofhatchinglinesforshading[HZ00]. Figure6: Theautomaticshading(hatching)techniquefrom[HZ00]. Notethatwithouttheshading,occluding contoursalonedonotgiveenoughinformationtodeterminethewholeshape. Contributions We present a methodology for sketch-based modelling of complex phenomena given various levels of prior knowledgeonthephenomenabeingmodelled. Thispriorknowledgecanbeassimpleasrule-of-thumbcon- straintsorascomplexasafullproceduralmodelwhichdescribesthephenomenon.Thisuseofpriorknowledge simplifiesthemodellingprocessandreducestheneedtospecifydesiredshapesfrommultipleviewpoints,of- tenallowingtheconstructionof3Dshapesusingonly2Dinputfromafixedviewpoint. Thismethodologyis demonstrated through a number of example implementations. In Part II via the example cases of modelling garments, foldsandhairstylesfromfixedviewpointsbyannotatingasupportingsurface. Asthechapterpro-