Abstract A Freehand Sketching Interface for Progre

AFreehandSketchingInterfaceforProgressiveConstructionof3DObjectsM.Masry,D.KangandH.Lipson1{mark.masry,hod.lipson}@cornell.eduSibelySchoolofMechanicalandAerospaceEngineeringCornellUniversity,Ithaca,USA,14853AbstractThispaperpresentsanintuitive,freehandsketchingapplicationforComputedAidedDe-sign(CAD)thatcanreconstructa3Dobjectfromasingle,flat,freehandsketch.Apenisusedtodrawtwodimensionalsketchesconsistingofstraightandcurvedstrokesconnectedatvertices.Thesketchesareprocessedbyareconstructionalgorithmthatusestheangulardistributionofthestrokes,andtheirconnectivity,todetermineanorthogonal3Daxissys-temwhoseprojectioncorrelateswiththeobservedstrokeorientations.Theaxissystemisusedtodetermineaplausibledepthforeachvertex.Thisapproachworkswellfordrawingsofobjectswhoseedgespredominantlyconformtosomeoverallorthogonalaxissystem.Asecond,independentoptimizationprocedureisthenusedtoreconstructeachcurvedstrokeintheoriginalsketch,assumingthatthecurveisplanar.Newstrokescanbeattachedtothe3Dobject,ordrawndirectlyontotheobject’sfaces.Animplementationoftherecon-structionalgorithmbasedonLevenberg-Marquardtoptimizationallowsobjectswithover50strokestobereconstructedininteractivetime.Keywords:3Dsketching,pen-basedcomputing,optimization,human-computerinteractionPACS:computergraphics,human-computerinteraction1IntroductionVisualmethodsofcommunicationareoftenthesimplestandmostefficientwayofconveyinginformationabouttheshape,compositionandrelationshipsofanob-1ThisresearchhasbeensupportedinpartbyaMicrosoftUniversityRelationsresearchgrantforTabletComputingPreprintsubmittedtoElsevierScience7March2005Fig.1.Ausercreating,renderingandrotatingashapewithaseethroughholeusingtheproposedsystemonaTabletPCject’scomponents.Furthermore,visualinformationoftentranscendsthelimitationsimposedbyspokenorwrittenlanguages,directlyaddressingapartofthebraincapableofentirelydifferentmodesofthought.Visualthinkingisnecessaryinen-gineering:amajorportionofengineeringinformationisconceived,recordedandtransmittedinavisual,non-verballanguage.Inspiteofthis,littleworkhasbeendonetocreatefast,intuitiveComputerAidedDesign(CAD)interfacesforengi-neersanddesigners.ConventionalCADuserinterfacesaretypicallycumbersometouseandhampercreativeflow.Freehandsketching,theinformaldrawingofshapesusingfreeformlinesandcurves,hasremainedoneofthemostpowerfulandintuitivetoolsusedattheconceptualdesignstage.Sketches,incontrasttotypicalCADdesigns,canquicklyandeas-2ilybecreatedtoconveyshapeinformation.InasurveyoftheadequacyofCADtoolsforconceptualdesign,anindustrialdesignerstates“Theinterfaceisjustnotforus.Icandothirtysketchesonpaperbythetimeittakesmetodotwoonthecomputer”(Puttre,1993).Simplepaper-basedsketchingalsohasmanydrawbacks:theviewpointisfixedandcannotbechangedinmiddrawing;thesketchispas-siveandcannotbedirectlysimulatedoranalyzedusingcomputationalengineeringtools(e.g.structuralanalysisorkinematicsimulation);thesketchistentativeandifafinal,accuratemodelisdesired,itmustberecreatedfromscratch.Theidealsolutionfromadesigner’spointofviewshouldcombineboththespeedandeaseoffreehandsketchingwiththeflexibilityandanalyticalabilitiesofCADtools.Thispaperpresentsanintuitive,pen-basedsketchingtoolthatcanreconstructa3Dobjectfromasingle,flat,freehandsketchwithoutrelyingonadatabaseofexistingmodels.AsshowninFigure1,ausercanmakeaninitialsketch,reconstructit,andadddetailusingaconsistentsketchinginterface.Theproposedsystemcanreconstructsketchesconsistingofbothstraightlinesandplanarcurves.Aseriesofoptimization-basedreconstructionalgorithmsareusedtoachievethisgoal.Theoptimizationalgorithmsrunininteractivetimeoncomplexsketches,providingaseamlessinterfacefortheconstructionandrefinementof3Dobjects.2PreviousworkSystemsthatusesketch-basedinputhavebeenthefocusofmuchresearch.Sta-hovichetal.(1998)demonstratedasystemthatcouldinterpretthecausalfunction-alitiesofatwodimensionalmechanismdepictedinasketch,andgeneratealter-nativedesigns.Davis(2002)recentlyshowedasystemthatsimulatedrigid-bodydynamicsofasketchedtwo-dimensionalmechanism.Thesesystemsaremostly3Fig.2.Asketchprovidesonlytwoofthecoordinates(x,y)ofobjectvertices.A3Drecon-structionmustrecovertheunknowndepthcoordinatez.Inparallelprojections,thisdegreeoffreedomisperpendiculartothesketchplane;thereareaninfinitenumberofcandidateobjects–theproblemisindeterminate.EachcandidateobjectisrepresentedbyauniquesetofZcoordinates,e.g.sets{Z1},{Z2}and{Z3}twodimensional,andthefewthatare3Drequireadditionalstepsthatbreaktheflowofsketching.Figure2outlinesthereconstructionofa3Dobjectfroma2Dsketch,inwhichanyarbitrarysetofdepths{Z}thatareassignedtotheverticesinthesketchconstitutesa3Dconfigurationwhoseprojectionwillmatchthegivensketchexactly.Inprinci-ple,eachsuchassignmentyieldsavalidcandidate3Dreconstruction.Aconsider-ableamountofresearchhasfocusedonthereconstructionofpolyhedralobjectsfromstraight-linesketches.Linelabelingapproaches(Huffman,1971;Clowes,1971)classifyeachlineasconvex,concaveoroccludingedgewithoutexplicitlyre-constructing3Dshapes.Severalmethodsconstructrelationshipsbetweentheslopeofsketchlinesandth