3D geometry reconstruction from orthographic views: A method based on 3D image processing and data fitting

on

3D

image

processing

and

data

fitting

Lapo

Governi

*

,

Rocco

Furferi,

Matteo

Palai,

Yary

Volpe

DepartmentofIndustrialEngineering,UniversityofFlorence,ViadiSantaMarta3,50139Firenze,Italy

1. Introduction

ComputerAidedDesignsystemsaredeemedtobeessentialfor allthephasescharacterizingthedesignandthedevelopmentofa newindustrialproduct.However,especiallyforproducts charac-terizedbyastrongstylisticcontent,handmadedrawingsareoften preferredtoCADsoftwarepackages.

Intheearlystageofthedevelopmentofanewproduct,esthetic designerstypicallyproducearichsetofsketches(usuallyintheform of orthographic projections) todevelop and communicatetheir ideas.Product-managersoftenhavetoselectstylisticalternatives based on a set of hand-drawings depicting possible solutions. However,itismuchmoreeffectivetobasetheselectiononavirtual 3Dmodelwhichconveysfarmoreinformation.Infact,some hand-drawn alternatives are even ‘‘translated’’ into 3D models (and possiblyrenderedmodels)capabletoprovideamorerealisticview oftheobjectandtoallowadeeperanalysisofthedesignintent.

Thetranslationprocess,involvingacloseinteractionofesthetic designersand CADoperatorsin ordertoproducea CADmodel carefully representing the designer’s intent, is known to be

considerablytimeconsuming.Accordingly,thedesignalternatives availableintheformofthree-dimensionalmodelsresulttobea verysmallsubsetofthosedevelopedbythedesigners(usuallyone or,atmost,two).

The common methodology (Fig. 1) used to turn a set of orthographicprojectionsintoa3Dmodelstartsfromarrangingthe scannedimagesofthehand-drawnviewsonthecorrespondent orthogonal planes in a CADsoftware environment. Using such images,theCADoperator(oftenassistedbythedesigner)manually redrawsthestylelinesinordertoobtainthe3Dwireframemodel whichis,eventually,usedasasupportframeforthedefinitionof thefinalsurfaces.

Theautomationofthis process,i.e.the3Dretrieval from2D drawings(knownas‘‘reconstructionproblem’’),isakeytargetfor commercialsoftwarehousesaswellasavigorousfocusfroman academicoutlook.

Recentlyasetofsoftwaretoolshavebeenreleasedbymajor softwarehouses,likeDassaultSystemes1

,Autodesk1

andPTC1

, whichsupporttheCADoperatorsinsomeofthereconstruction process phases. These tools, however, entail a strong user interactionandonlymarginallyspeeduptheprocess.Inaddition, most of them require as an input an ‘‘exact’’ setof 2D vector drawings(e.g.DXForIGESfiles).

Fromtheacademicpointofview,anumberofworkshavebeen proposedsincethefirst‘70s,providingaseriesofmethodologies forsolvingthereconstructionproblemstartingfroman‘‘exact’’set ARTICLE INFO

Articlehistory:

Received31August2012 Accepted1February2013 Availableonline19March2013 Keywords: 3Dreconstruction Orthographicviews Voxelimaging 3Dgeometryfitting Industrialdesign ABSTRACT

Industrial esthetic designers typically produce hand-drawn sketches in the form of orthographic projections. A subsequent translation from 2D-drawings to 3D-models is usually necessary. This involvesaconsiderablytimeconsumingprocess,sothatsomeautomationisadvisable.

Common approaches to this ‘‘reconstruction problem’’ start directly from ‘‘exact’’ 2D vector representationsortrytovectorize2Drasterimagespriortothereconstructionphase.Theseapproaches, however,typicallyfailtodealwithfreeformgeometriesliketheonescommonlyfoundinesthetic industrialdesign.

Thisworkpresentsanewmethodologysuitableforfreeformgeometries,comprisingthegeneration andprocessingofa3Dvoxelimageobtainedfromahanddrawing,thecreationofasetof3Dcurves fittingthevoxelimageandtheautomaticgenerationofsurfacepatchesontheresultingcurvenetwork. Severalcasestudiesarealsopresentedinordertoemphasizeanddiscussstrengthsandweaknessesof theproposedmethod.

ß2013ElsevierB.V.Allrightsreserved.

*Correspondingauthor.Tel.:+390554796396;fax:+390554796400; mobile:+393480198491.

E-mailaddresses:lapo.governi@unifi.it(L.Governi),rocco.furferi@unifi.it

(R.Furferi),matteo.palai@unifi.it(M.Palai),yary.volpe@unifi.it(Y.Volpe). 0166-3615/$–seefrontmatterß2013ElsevierB.V.Allrightsreserved.

of2Dvectordrawings.Adramaticboosttotheresearchonthis topicwasprovidedbyWesleyandMarkowskyintheirstudies[1,2]

whichareprobablythebestknownworksamongtheresearchers workingon3Dreconstruction.WesleyandMarkowskyprovideda comprehensivesetofguidelinesforreconstructing3DCADmodel starting from orthographic projections. Their procedure is, still today,amilestoneforalmosteveryreconstructionstudy.Moving from these guidelines, many works have been developed, particularly referring to the 3D reconstruction from technical (industrialand/or architectural)vectordrawings. Mostof them havebeenconceivedfor retrieving3Dmodelsstartingfrom2D straightedges,arcsor,atmost,conics[3–7].

Inaddition,afewapproacheshavebeendevelopeddealingwith thereconstructionproblembasedeitheron asetof3Dfeatures which can be possibly found in a technical drawing (e.g. revolutions and extrusions) or on information coming from additionalviews, likecross-sections.Theworks which confront the reconstruction problem for curvilinear objects, however, usuallypresent quite‘‘tricky’’approaches,generallyinvolving a considerableamountofuserinteraction[8,9].

Themostsignificantlimitationtotheapproachescitedsofaris that,asalreadymentioned,inallthecasesthereconstructionis basedon‘‘exact’’vectordrawingsandislimitedtospecifickindsof geometries.

Movingfromtheseconsiderations,thisworkismeanttodiscuss amethodologytoperformaquasi-automatic‘‘translation’’starting froma2Dscannedimageofhand-drawnorthographicviews.

Though this workand the onesmentioned above share the same goal (3D reconstruction from planar views), the starting pointiscompletelydifferent,sinceitconsistsofrasterdatafrom inherently inexact drawings like the ones, mentioned at the beginningofthissection,comingfromtheinitialdesignphases. Moreover, as detailed in the methodology description, the presentedapproachisapplicableregardlessofthetypologiesof geometriesrepresentedinthestartingdrawings,and is particu-larlywellsuitedforfreeformgeometriesliketheonescommonly foundinestheticindustrialdesign.

Thepaperisorganizedasfollows.

InSection2thereconstructionmethodologyispresentedwith referencetoanexemplificativecasestudy;inSection3additional reconstructionexamplesarepresentedinordertodemonstratethe robustnessoftheproposedmethod;strengthsandweaknessesof thepresentedapproachdependingonpossibleusagescenariosare alsodiscussed;inSection4afewconcludingconsiderationsare drawnandpossibleoptionsfor futuredevelopmentsarebriefly hintedat.

2. Methodology

AsmentionedinSection1,theproposedmethodologyisbased ontheprocessingofasingle2Drasterimage(e.g.bmporjpgfile) depictingtheorthographicviewsoftheobjectwhose3Dgeometry istoberetrieved.

Themethodisstructuredaccordingtoasetofphaseswhichcan besummarizedinthefollowinglist.

1.Buildingawireframe-likevoxelcloud(3Dimage)representinga rastermodeloftheoriginalobject.

2.Separatingbranches(3Dlabeling)oftheresulting3Dimageby meansofapproximateintersectiondetection.

3.Obtaininga3Dwireframemodelmadeofsplinecurvesstarting fromeachlabeledentityof3Dimageand,successively,refining theobtainedcurvesintheintersectionzones.

4.Buildingasurfacerepresentationoftheobjectbyusingsurface patchesattachedtothesplinecurvenetwork.

Eachofthesemainphaseswillbedetailedintherestofthis section, with reference to an exemplificative case study, by splittingtheminproceduralsteps.

2.1. Buildingawireframe-likevoxelcloud(3Dimage)representinga rastermodeloftheoriginalobject

Step 1 – The Imageof thehand-drawn sheet depictingthe orthographic views is acquired by means of a flatbed scanner (grayscale–8bit).Thescanningresolutionneedstobeselectedso thatseparatelinesinthedrawingremainseparateintheresulting digitalimage(Fig.2).Inpractice,thisrequirestohaveatleast3–4 ‘‘white’’ pixels separating each drawing line. Typically, an indicative resolution value can be 150dpi for a line thickness drawingintherange0.5/1.0mm.

Step 2 – The orthographicviews in the resultingimage are identifiedandthesheetorientationisautomaticallycompensated. Inthisstep,itisassumedthattheviewsarecorrectlyarrangedin theoriginaldrawing(accordingeithertothefirst-angleortothe third-angleprojectionrule)andseparatedbymeansofcontinuous linesrepresentingthemutualintersectionsoftheplanesonwhich theviewsareprojected.

Thesheetorientationiscompensatedbyidentifyingthetwo orthogonallinesintheimagecharacterizedbymaximumlength (reference lines). Thisis done applyingthe well-known Hough transformtothethresholdedimage,wherethethresholdvaluets

must be manually selected in order to obtain a clear binary representationof thedrawing. First,a sloperangeof 108(0.18 step)withrespecttothehorizontaldirectionisselectedandthebest scoringlineisconsidered(slope

a

h);secondarilythebestscoringline

withaslopeintherange

a

n5,where

a

_n¼

a

_hþ90:Theslopeof thisnewlineislabeledas

a

v.Theintersectionpointofthetwolinesis identified and is considered to be the origin O of the set of orthographicviews(Fig.3).Finally,theoriginalgrayscaleimageis rotated around O using bi-cubic resampling, so that the line characterized bythehighestoverallscoreresultstobehorizontal (either

a

hor

a

vissettozero).

Afterwards, the separate views in the rotated image are identified by isolating the four quadrants delimited by the horizontallineandtheoriginO.

Fig.1.Typical2Dto3D‘‘translation’’process. courtesyofItaldesign-Giugiaro

Eachviewislabeledasfrontview(FV),sideview(SV)ortop view(TV)accordingtoitspositionwithrespecttotheoriginOand totheemptyquadrant.

Inthissteptheboundingboxesdimensionsandpositions(in pixel)arealsocomputedforeachorthographicview.Thisisdone bycomputing,foreachview,theboundingboxoftheconnected component characterized by the maximum number of pixels (Fig.4).

Step3–Theimagescontainedineachsingleboundingboxare separatelyconsidered and,sincethedimensionsinthedifferent viewsneedtobecoherent,theyarescaled(bi-cubicresamplingis used) to compensate for possible discrepancies. Once the 2D boundingboxeshavebeenadjusted,itispossibletoidentifythe3D boundingboxoftheobjectrepresentedintheoriginaldrawing.

Thesetofresultingimages,afteranewthresholding,undergoa weighted, iterative dilation process using a 33 structuring element(allvaluessetto1).

Assuming a totalof nsdilation iterations are used,the new

whitepixels,obtainedateachdilationiterationi,aremultipliedby aweightingcoefficientdidefinedasfollows.

Notethatallthedilationiterationsareappliedonthebinary imageobtainedatthepreviousone.Onlyafteralliterationsare performed,theweightsareapplied.

Theresult for anexemplificativevalue ofns=2 is shownin

Fig.5.

The number of iterations to be used in the process is set according to the expected error in correspondence among theprojections(foradditionaldetailsseealsothedescription of Step5).

Step 4 – The new grayscale images obtained in Step 3 are extrudedorthogonallytotheirimageplanetocovertheentire3D boundingboxcomputedinStep2.Asetof3Dimagesis,thereby, obtainedwitheachvoxelhavingarealvaluebetween0and255. Step5 –Theentiresetof 3Dimages, afternormalization,is multipliedelementbyelementsotoobtainafinal3DimageG, wheretheobjectoutlinesarerepresentedbya3Dwireframe-like voxelcloud.Agivenregion ofthe3Dobjectoutlineiscorrectly reproducedinGifsufficientlygoodmatchingisfoundbetweenthe corresponding2Doutlines intheoriginalviews(perfectmatch: G(i,j,k)=1;partialmatch:0<G(i,j,k)<1;no match:G(i,j,k)=0). According to this definition,the amountof acceptable errorin ordertoidentifya3Dregionbymatchingthe2Dviews,isdirectly relatedtothenumberofdilationstepsnswhich,asaconsequence,

needs tobeselectedsuitably. InFig.6a and btheresulting3D images obtained respectivelybysetting ns=0(insufficient)and

ns=2(sufficient)areshown.

Fig.2.Scannedimage(grayscale).

Fig.3.Referencehorizontal(lightblue)andvertical(red)linesandrotationcenter‘‘O’’.(Forinterpretationofthereferencestocolorinthisfigurelegend,thereaderisreferred tothewebversionofthearticle.)

2.2. Separatingbranchesbymeansofapproximateintersection detection

Step6–ImageGisconvertedintoabinaryimageT(T(i,j,k)=1if G(i,j,k)6¼0) which undergoes a morphological closing (with a 333 unitarykernel)toremove possiblesmallcavities.The resultingvoxelcloudistransformedintoatriangularmesh,which iterativelyundergoesaLaplaciansmoothingprocessaccordingto theapproachdescribedin[10].Duetothewaythevoxelmodelis originated,theoneobtainedisaclosedmesh;asaconsequence, thewell-knownproblemof‘‘disappearing’’meshregionsdueto meshshrinkage,doesnotoccur,sothatno particularconstraint needtobeconsideredwhenperformingthesmoothingprocess.

Thesmoothing progress on anexemplificative region of the meshobtainedfromimageTisshowninFig.7.

Step7– Theresultingtriangularmesh ischaracterized bya large number of spikes (situated in the regions far from the intersections) and a few approximately equilateral triangles (situated in the regions where multiple ‘‘wires’’ intersect). In ordertospottheapproximateintersections,triangles’formfactorf (i.e.theratiobetweentheheightrelativetomaximumlengthedge andtheedgeitself)isanalyzedandtriangleswith0.5<f<1are selected.Thecentroidsciofeachconnectedgroupofsuchtriangles

areassumedtobeafirstguessfortheintersectionpoints.InFig.8

the detail of an intersection region is shown; the color map highlightsthedifferencesintriangles’formfactor.

Step8 – For each centroidci,the equationofa sphere Eiis

computedsothatitiscenteredonciandhasaradiusproportional

totheestimated‘‘wire’’thicknessinthedilatedvoxelimage.Inthis workthisparametermust bedirectlyinputandcanberoughly estimatedfromtheknowledgeofthelinethicknessintheoriginal 2Ddrawing,thescanningresolution,andthenumberofdilation stepsnsperformedinStep3.Thespheresareassumedtorepresent

theregionswherethewires’intersectionslie.Accordingly,inorder toseparatethe‘‘branches’’ composingthewireframe-like voxel model,imageTis‘‘cut’’bymeansofspheresEibysettingT(i,j)=0

for allthevoxels lyinginside anyofthespheres. Theresulting image is characterized by the presence of a set of connected componentsrepresentingtheseparated‘‘branches’’ofT.

Insomecases(Fig.9a)twoormorecentroidsmayoriginatein very close positions. If the respective spheres intersect, the centroidsareassumedtorepresentasingleintersectionzone.In suchacase,thevoxelscontainedintheintersectingspheresare analyzedbymeansofPCA(principalcomponentanalysis)andthe principaldirectionsareusedtocomputeasingleellipsoidusedfor ‘‘cutting’’imageTintheplaceofEi.Ellipsoiddimensionissetso

thattheminoraxisequalsEidiameter(Fig.9b).

Step9–Thebinary3DimageresultingfromStep8islabeledby searchingforitsconnectedcomponents.Foreachlabeledregion, thecorrespondingoneisextractedfromimageG(i.e.thesetof voxelsofGcharacterizedbythesamecoordinatesofthelabeled region)andstoredinaseparate3Dimage.

2.3. Obtaininga3Dwireframemodelmadeofsplinecurves,starting fromeachlabeledentityof3Dimage

Step10–Eachseparatebranchisfittedbymeansofaspline curveaccordingtoaprocessbasedontheuseofweightedleast squares.Thefittingneedstobeperformedonanunorderedvoxel cloud,soasuitableapproachhastobeused.Thebasicideaisto: definea3Dpolylineapproximatelyfollowingthevoxelbranch

medialaxis(Fig.10a);

fitthepolylineknotswithaninterpolatingsplinecurve(cubic) used forordering thevoxels by evaluating theorder oftheir projectionontothespline(Fig.10b);

perform a final weighted least square fitting with a new approximating spline curve (cubic) using the voxel order identifiedinthepreviousstep(Fig.10c).

The weight associated to each voxel is assumed to be represented by the voxel value itself; as a consequence, the resultingsplinecurvestendtobewellsuperimposedtothevoxel Fig.4.Boundingboxesforthethreeorthographicviews.

cloudregionswithvoxelvalues1.AsexplainedinStep5,these aretheregionsoriginatedbywellmatching2Dprojections.

The described fitting method is a 3D extension of the one describedbytheauthorsin[11],towhichthereaderisreferredfor adetaileddescription.

Step11–Oncethefittingprocessiscomplete,finalintersection pointsarecomputedbymeansofthefollowingprocedureforeach cuttingregion(sphereorellipsoid).

The(spline)curves,fittingthebrancheswhichwereseparatedby theanalyzedcuttingsurface,areconsidered.

Foreachcurve,thepointwherethecurveintersectsthecutting entityiscomputedandthecurveisextendedfromitalongits tangentdirectioninsuchawaythattheextensionsegmentis delimitedbythecuttingsurface.

Duetotheirdefinition,theextensionsegmentsnevermatchina common point (which would be the intersection one); as a consequence the most likely intersection point must be identified. Since it cannot lie outside of the voxel region delimitedbythecuttingsurface,itispossibletolimitthesearch domain by only considering the centroids of such voxels as candidateintersectionpoints.Thevoxelcentroidwithminimum valueofthesumofsquaredistancesfromextensionsegmentsis consideredtobetheintersectionpoint(Fig.11).

Fig.6.Voxelimagesobtainedwithdifferentvaluesofns(colormapindicatesthevoxelvalue).

Fig.7.Laplaciansmoothingprogress(detailofanintersectionregion).

Notethat theabovedescribed procedureintroduces aslight approximationinconsideringonlyintegercoordinates,butallows toidentifytheintersectionpointbyexaminingafinitenumberof candidates.

Step 12 – Each voxel branch is re-fitted using the same proceduredescribedinStep10withthepreliminaryintroduction ofasetofboundaryconditionssothatthefittingcurveendpoints coincidewiththeintersectionsfoundinStep11.

Step13–Theresultingsetofsplinecurvesisreassembledina singlemodelwhichrepresentsthevectorpseudo-wireframeofthe originalobject.ThemodelcanbetranslatedintoaDXForIGESfile and is ready to be used for surface generation in a 3D CAD environment(Fig.12).

2.4. Buildingasurfacerepresentationoftheobjectbyusingsurface patchesattachedtothesplinecurvenetwork

Step14–Theedgesofthewireframemodelcanbeusedas supportentitiestodefineasetofsurfacepatchesdescribingthe geometryoftheobjectrepresentedintheoriginaldrawing.This phasecanbeperformedeithermanually,importingthevectorfile (e.g.DXFandIGES)inasurfacemodelingsoftwareenvironment and selectingedgecyclesdefining eachsinglesurface patch,or automatically, using an approach based on the analysis of the graphmadeupofcurvesandintersections.Inordertoimplement andtestaprocedurecapableofperforminganautomaticsurface generation, theworkbyBagaliandWaggenspack[12]hasbeen considered. In their studytheydefinea graphrepresentingthe wireframemodelofanobject,wherenodesaretheintersection points and edges are the curves making up the model itself. Accordingly,theproblemofidentifyingthesetofcurvesdelimiting asinglesurfacepatchistranslatedintotheoneofdetermininga cycleintheoriginalgraph.Inthiswork,whilegraphexplorationin ordertoidentifycandidatecycleshasbeenperformedusingBagali andWaggenspack’sapproach(based,initsturnonthewell-known Fig.9.Intersectingcuttingspheres(a)andresultingcuttingellipse(b).

Fig.10.Initialpolyline(a);orderingcurve(b);andfinalcurveapproximatingthevoxels(c).

Fig.11.Identificationoftheintersectionpoint(p).

Fig.12.Finalnetworkofsplinecurvessuperimposedonthevoxelimage(1%of non-zerovoxelsareplotted).

Dijkstra’salgorithm[13]),theidentificationofoptimalcycles(i.e. theonesmorelikelyrepresentinga‘‘correct’’surfacepatchofthe originalobject)hasbeenperformedusingtheapproachrecently describedbyAbbasinejadetal.in[14].

Byusingconsiderationscomingfrombothcycles’topologyand geometry,theapproachdeterminesaweightingfunctionW,which isrepeatedlyevaluatedbyaheuristicsearchalgorithm.Infact,the graphoriginatedbythecurvesmakingupthepseudo-wireframe model is searched and a set of optimal cycles (i.e. the ones characterizedbyhighervaluesofW)areoutput.

Once the cycles enclosing the surface to be created are identified, they can be automatically generated by interfacing thedevelopmentenvironment,wherethesplinedatabasehasbeen built,withaCADsoftware(Fig.13).

In case of complex 3D curves networks,the optimal cycles identificationproceduremayfailandleadtogenerateedgecycles different from the desired ones (Fig. 14a). In such cases the resulting 3D surface model needs to be manually edited in a surface modeling software environment (e.g. Rhinoceros1

). Anyway, since the probability incorrect cycles are generated growsasthenumberof3Dcurvesincreasesinthe3Dmodel,itis possibletodecreasethefrequencyofthisissuesimplybymanually simplifyingthecurvenetwork priortothe cyclesidentification phase.Moreindetail,startingfromthepseudowireframemodel outputbyStep13,itissufficienttodeleteallthecurvesuntilonly the wire frame model remains (Fig. 14b). This simplification procedure proves to be very fast even for relatively complex models.

3. Resultsanddiscussion

Thereconstructionmethodology,implementedusingMatlab1

programminglanguage(withtheexceptionofthesurfacecreation phase, which has been carried out interfacing Matlab1

with

Rhinoceros1

4.0),hasbeenappliedonanumberofcasestudies, otherthantheoneusedtoillustratethewholeprocedure.

In this section, a selection of examples are presented and discussedinordertopointoutstrengthsandweaknessesofthe proposedreconstructionprocedure.

Thefirstexampleconsistsofasimplesetoforthogonalviews depictingacubicobject.Thoughthereconstructionmayappearto betrivial,ithastobenotedthatmatchingamongtheviewsisquite poor(Fig.15a).Inthiscasealowvalueofns(ns=2)generatesa

voxel image characterized by thin outlines, but a number of regionswherethemodelisincompletecanbeobserved(Fig.15b). Tosolvetheproblemitissufficienttosetns=6inordertoobtaina

complete, correct voxel model (Fig. 15c) which leads to the reconstruction of the curve network shown in Fig. 15d and, ultimately,tothesurfacemodelofFig.15e.Generallyspeaking, whentheoutlinesmakinguptheoriginalorthographicviewsare wellseparated,itisusuallypossibletocompensatepoormatching amongtheviewssimplyincreasingnsvalue;conversely,incasethe

outlinesareclosetheonetotheother,ahighvalueofnsproduces

the merging of distinct outlines into a single one, thereby corruptingthewholemodel.

The second example is shown in Fig. 16a; in this case the resultingcurvenetworkfeatures anerroneousregion (topology differenttothe‘‘theoretical’’one)neartheuppervertex(Fig.16b). Thisisduetothefactthatthetangentoutlinesinthesideview originateasinglevoxelwireevenifnsissettotheminimumvalue

necessarytoobtainacompletereconstructionofthevoxelcloud (ns=1).Inthisspecificcase,however,despiteoftheerrorinthe

curve network, a surface model is generated which closely resemblesthetheoreticalone(Fig.16c).

Incase asimilarexampleisconsidered (Fig.17),thoughthe object is slightlymorecomplex, theprocedure succeedsin the completely automatic reconstructionthanksto more separated lines.

Fig.13.Completesurfacemodel(a);anddetailoftheinnersurfaces(b).

Fig.14.Surfacepatch(inred)duetoanincorrectcycledefinition(a);andsimplifiedcurvenetworktobeusedinordertominimizetheprobabilityofwrongcycledefinition (b).(Forinterpretationofthereferencestocolorinthisfigurelegend,thereaderisreferredtothewebversionofthearticle.)

Fig.15.Reconstructionexample1:initialdrawingcharacterizedbypoorcorrespondencebetweentheviews(a);voxelimageobtainedforns=2(b);voxelimageobtainedfor ns=6;finalcurvenetworkwith10%ofthenon-zerovoxels(d);andfinalsurfacemodel(e).

The resultingmodelprovestobecorrectalsoforthefourth example,depictingadrop-shapedobject(Fig.18).Inthiscase,in ordertoavoidtheerroneousreconstructionduetothetangent outlinesintheupperregion,alargevalueofEidiameterhasbeen used(40pixels).Thisisa feasiblesolutiononlyifthereare no otheroutlinesnearthecuttingregionbecause,otherwise,these wouldbeerasedbytheseparationprocessdescribedinSection2

(Step8).

The last example(Fig. 19) providesa casestudysimilarto theoneusedinSection2toillustratethemethodology.Though theobjectappearstoberelativelymorecomplexwithrespectto the previous ones, the reconstruction process produces a completely correct model since a set of favorable conditions can be observed: good matching among the views, well separatedoutlinesandapproximatelyorthogonalintersections

amongthecurves(bothinthe2Ddrawingandinthe3Dvoxel image).

Movingfromtheresultsobtainedsofar,afewconsiderations canbedrawn.

First,thepresentversionoftheproposedmethodologycanbe appliedonlytosimple2Ddrawings(i.e.madeofalimitednumber ofcurves),sincethecomplexityofthepseudowireframevoxel modelrapidlygrowsasthenumberof2Dcurvesincreases.This,in itsturn,generallyleadstothepresenceofanumberofregionsin 3Dspacewherethe3Dwiresareveryclosetheonetotheother,so thattheprocedureforseparatingthevoxelcloudbranchescanfail likeshowninsomeoftheexamplesdiscussedabove.

Thisproblemcouldpossiblybeovercomebyintroducingsome additionaluserinteractioninthefirstphasesofthereconstruction process.Moreinparticularitcouldbepossibletobuildpartial3D Fig.17.Reconstructionexample3:initialdrawing(a);finalcurvenetworkwith5%ofthenon-zerovoxels(b);andfinalsurfacemodel(c).

voxelmodelsstartingfromsub-setsof2Dcurvesselectedbythe userin the original drawing, sothat each corresponding voxel modelwouldbesignificantlysimplified.Eachvoxelmodelcouldbe separatelyprocessedandtheresultingnetworkof3Dsplinecurves couldbesubsequentlyre-assembledinasingle,finalvectormodel. Ascanbeeasily realized,a majordrawback ofthe described approachresidesinthenecessityforeachcurveoftheoriginalobject toberepresentedatleastin3mutuallyorthogonalviewsofthe startinghanddrawing.Thisrequirementcanoftenbeobtainable simplybyusingmoreviews(upto6)thantheconventional3views representation.Infact,thedescribedprocedurecanberepeatedfor anysetof3mutuallyorthogonalviewsoftheoriginaldrawingand, subsequently,theresultingsetsof3Dcurvescanbemergedinafinal, completemodel.In casethis isnotsufficient(e.g. forunder-cut zones)theonlyalternativeistorepresenthiddenlinesinthehand drawings like visible ones, which, de facto means to draw the orthographicrepresentationoftheobjectwireframemodel. 4. Conclusions

Theproposedreconstructionmethodology,despitesome limita-tionsdiscussedinSection3,provedtobequiterobustandtorequire onlya little interactionfrom the operator. Evidently,due to its workingprinciple (basedon voxel cloud elaboration,fitting and surfacegeneration),themethodprovidesaresulting3Dgeometry which can be considered an approximate version of the one achievable by means of a conventional 3D modeling process. However,themanualreconstructionofthevectorwireframeandthe surfacegeneration provestobeconsiderablyspeeded upevenif somereworkingmaybenecessaryforcorrectingpossible recon-structionerrorsand addingsomekindofconstraints amongthe splines(e.g.symmetry,tangency,orthogonality).Futureworkwillbe addressedtodealwiththiskindofissuesand,possibly,tointegrate thedevelopedprocedurewithacommercialCADsoftwarepackage. References

[1]G.Markowsky,M.A.Wesley,Fleshingoutwireframes,IBMJournalofResearchand Development24(5)(1980)582–597.

[2]M.A.Wesley,G.Markowsky,Fleshingoutprojections,IBMJournalofResearchand Development25(6)(1981)934–954.

[3]R.Furferi,L.Governi,M.Palai,Y.Volpe, 3Dmodelretrievalfrommechanical drawingsanalysis,InternationalJournalofMechanics5(2)(2011)91–99. [4]Q.W.Yan,C.L.P.Chen,Z.S.Tang,Efficientalgorithmforthereconstructionof3dobjects

fromorthographicprojections,Computer-AidedDesign26(9)(1994)699–717. [5]M.H.Kuo,Reconstructionofquadricsurfacesolidsfromthree-viewengineering

drawings,Computer-AidedDesign30(7)(1998)517–527.

[6]S.X.Liu,S.M.Hu,Y.J.Chen,J.G.Sun,Reconstructionofcurvedsolidsfrom engineer-ingdrawings,Computer-AidedDesign33(14)(2001)1059–1072.

[7]K.Inoue,K.Shimada,K.Chilaka,SolidmodelreconstructionofwireframeCAD modelsbasedontopologicalembeddingsofplanargraphs,JournalofMechanical Design125(3)(2003)434–442.

[8]P.Company,A.Piquer,M.Contero,F.Naya,Asurveyongeometricalreconstruction asacoretechnologytosketch-basedmodeling,Computers&Graphics29(6) (2005)892–904.

[9]M.A.Fahiem,S.A.Haq,F.Saleemi,Areviewof3Dreconstructiontechniquesfrom 2Dorthographiclinedrawings,in:GMAI2007:GeometricModelingandImaging, Proceedings,2007,pp.60–63.

[10]M.Desbrun,M.Meyer,P.Schroder,A.H.Barr,Implicitfairingofirregularmeshes usingdiffusionandcurvatureflow,ComputerGraphic(1999)317–324. [11]R.Furferi,L.Governi,M.Palai,Y.Volpe,Multipleincidentsplines(MISs)algorithm

fortopologicalreconstructionof2Dunorderedpointclouds,InternationalJournal ofMathematicsandComputersinSimulation5(2)(2011)171–179. [12]S.Bagali,J.Warren,N.Waggenspack,Ashortestpathapproachtowireframeto

solidmodelconversion,in:ProceedingsoftheThirdACMSymposiumonSolid ModelingandApplications,ACM,SaltLakeCity,UT,1995,pp.339–350. [13]T.H.Cormen,C.Stein,R.L.Rivest,C.E.Leiserson, IntroductiontoAlgorithms,

McGraw-HillHigherEducation,Boston,MA,2001.

[14]F.Abbasinejad,P.Joshi,N.Amenta,Surfacepatchesfromunorganizedspace curves,ComputerGraphicsForum30(5)(2011)1379–1387.

Lapo Governi, Ph.D., is assistant professor at the Department of Industrial Engineering, University of Florence,Italy.GraduatedM.Sc.inMechanical Engineer-ingattheUniversityofFlorence(Italy)in1998.In2002 heobtainedthetitleofPh.D.inMachinedesignand Construction.Afterworkingasapost-doctoralresearcher attheDepartmentofMechanicsandIndustrial Technol-ogiesoftheUniversityofFlorence,in2005heassumeda FacultypositionasAssistantProfessorforthecoursesof ‘‘Reverse Engineering and Rapid Prototyping’’ and ‘‘Designand modelingmethods’’.Hismainscientific interestsare:ComputerAidedDesign,computational geometry,reverseengineering,machinevision,toolsand methodsforproduct designanddevelopment.Heis authorofmorethan70scientificpublications.Hismostrecentworkshavedealtwith 3D reconstructionfrom orthographic views, vision-based product and process assessmentandspline-basedapproximationofpointclouds.

Rocco Furferi, Ph.D., is assistant professor at the Department of Industrial Engineering, University of Florence,Italy.GraduatedM.Sc.inMechanical Engi-neeringattheUniversityofFlorence(Italy)in2001.In 2005heobtainedthetitleofPh.D.inMachinedesign andConstruction.Hewasemployedasapost-doctoral researcher at the Department of Mechanics and IndustrialTechnologiesoftheUniversityofFlorence until2008,whenheassumed aFaculty positionas ContractAssistantProfessorforthecourses ‘‘Mechani-calDrafting’’and‘‘ComputationalGraphics’’.Hismain Scientificinterestsare:developmentofartificialvision systems,artificialneuralnetworks,colorimetry,reverse engineering,computationalgeometry.Heisauthorofmorethan60publications. Somelatestworksdescribedmethodsforcolorassessmentoftextiles,algorithms Fig.19.Reconstructionexample5:initialdrawing(a);finalcurvenetworkwith1%ofthenon-zerovoxels(b);andfinalsurfacemodel(c).