IntJAdvManufTechnol(2000)16:6356422000Springer-VerlagLondonLimitedThePre-ProcessingofDataPointsforCurveFittinginReverseEngineeringMing-ChihHuangandChing-ChihTaiDepartmentofMechanicalEngineering,TatungUniversity,Taipei,TaiwanReverseengineeringhasbecomeanimportanttoolforCADmodelconstructionfromthedatapoints,measuredbyacoordi-natemeasuringmachine(CMM),ofanexistingpart.Amajorprobleminreverseengineeringisthatthemeasuredpointshavinganirregularformatandunequaldistributionarediffi-culttofitintoaB-splinecurveorsurface.Thepaperpresentsamethodforpre-processingdatapointsforcurvefittinginreverseengineering.TheproposedmethodhasbeendevelopedtoprocessthemeasureddatapointsbeforefittingintoaB-splineform.TheformatofthenewdatapointsregeneratedbytheproposedmethodissuitablefortherequirementsforfittingintoasmoothB-splinecurvewithagoodshape.Theentireprocedureofthismethodinvolvesfiltering,curvatureanalysis,segmentation,regressing,andregeneratingsteps.Themethodisimplementedandusedforapracticalapplicationinreverseengineering.TheresultofthereconstructionprovestheviabilityoftheproposedmethodforintegrationwithcurrentcommercialCADsystems.Keywords:Curvefitting；Pre-processingofdatapoints；Reverseengineering1.IntroductionWiththeprogressinthedevelopmentofcomputerhardwareandsoftwaretechnology,theconceptofcomputer-aidedtech-nologyforproductdevelopmenthasbecomemorewidelyacceptedbyindustry.Thegapbetweendesignandmanufactur-ingisnowbeinggraduallynarrowedthroughthedevelopmentofnewCADtechnology.Inanormalautomatedmanufacturingenvironment,theoperationsequenceusuallystartsfromproductdesignviageometricmodelscreatedinCADsystems,andendswiththegenerationofmachininginstructionsrequiredtoconvertrawmaterialintoafinishedproduct,basedonthegeometricmodel.Torealisetheadvantagesofmoderncom-Correspondenceandoffprintrequeststo:Ming-ChihHuang,Depart-mentofMechanicalEngineering,TatungUniversity,40ChungshanNRoad,3rdSection,Taipei104,Taiwan.E-mail:mindyK.twputer-aidedtechnologyintheproductdevelopmentandmanu-facturingprocess,ageometricmodeloftheparttobecreatedintheCADsystemisrequired.However,therearesomesituationsinproductdevelopmentinwhichaphysicalmodelorsampleisproducedbeforecreatingtheCADmodel:1.Whereaclaymodel,forexample,indesigningautomobilebodypanels,ismadebythedesignerorartistbasedonconceptualsketchesofwhatthepanelshouldlooklike.2.Whereasampleexistswithouttheoriginaldrawingordocumentationdefinition.3.WheretheCADmodelrepresentingtheparthastoberevisedowingtodesignchangeduringmanufacturing.Inallofthesesituations,thephysicalmodelorsamplemustbereverseengineeredtocreateorrefinetheCADmodel.Incontrasttothisconventionalmanufacturingsequence,reverseengineeringtypicallystartswithmeasuringanexistingphysicalobjectsothataCADmodelcanbededucedinordertoexploittheadvantagesofCADtechnologies.Theprocessofreverseengineeringcanusuallybesubdividedintothreestages,i.e.datacapture,datasegmentationandCADmodellingand/orupdating1,2.Aphysicalmock-uporprototypeisfirstmeasuredbyacoordinatemeasuringmachineoralaserscannertoacquirethegeometricinformationintheformof3Dpoints.Themeasuredresultsarethensegmentedintotopologicalregionsforfurtherprocessing.Eachregionrepresentsasinglegeometricfeaturethatcanberepresentedmathematicallybyasimplesurfaceinthecaseofmodelreconstruction.CADmodellingreconstructsthesurfaceofaregionandcombinesthesesurfacesintoacompletemodelrepresentingthemeasuredpartorprototype3.Inpracticalmeasuringcases,however,therearemanysitu-ationswherethegeometricinformationofaphysicalprototypeorsamplecannotbemeasuredcompletelyandaccuratelytoreconstructagoodCADmodel.Somedatapointsofthemeasuredsurfacemaybeirregular,havemeasurementerrors,orcannotbeacquired.AsshowninFig.1,themainsurfaceofmeasuredobjectmayhavefeaturessuchasholes,islands,orroughnesscausedbymanufacturinginaccuracy,consequentlytheCMMprobecannotcapturethecompletesetofdatapointstoreconstructtheentiresurface.636M.-C.HuangandC.-C.TaiFig.1.Thegeneralproblemsinapracticalmeasuringcase.Measurementofanexistingobjectsurfaceinreverseengin-eeringcanbeachievedbyusingeithercontactprobingornon-contactsensingprobingtechniques.Whatevertechniqueisapplied,therearemanypracticalproblemswithacquiringdatapoints,forexamples,noise,andincompletedata.Withoutextensiveprocessingtoadjustthedatapoints,theseproblemswillcausetheCADmodeltobereconstructedwithanunde-siredshape.InordertorebuildtheCADmodelcorrectlyandsatisfactorily,thispaperpresentsausefulandeffectivemethodtopre-processthedatapointsforcurvefitting.Usingtheproposedmethod,thedatapointsareregeneratedinaspecifiedformat,whichissuitableforfittingintoacurverepresentedinB-splineformwithouttheproblemspreviouslymentioned.Afterfittingallofthecurves,thesurfacemodelcanbecompletedbyconnectingthecurves.2.TheTheoryofB-splineMostofthesurface-basedCADsystemsexpressshapesrequiredformodellingbyparametricequations,suchasinBezierorB-splineforms.ThemostusedistheB-splineform.B-splinesarethestandardforrepresentingfreeformcurvesandsurfacesincurrentcommercialCADsystems.B-splinecurvesandBeziercurveshavemanyadvantagesincommon4.Controlpointsinfluencethecurveshapeinapredictable,naturalway,makingthemgoodcandidatesforuseinaninteractiveenvironment.Bothtypesofcurvearevariationdiminishing,axisindependent,andmultivalued,andbothexhi-bittheconvexhullproperty.However,itisthelocalcontrolofcurveshapewhichispossiblewithB-splinesthatgivesthetechniqueanadvantageovertheBeziertechnique,asdoestheabilitytoaddcontrolpointswithoutincreasingthedegreeofthecurve.Consideringthereal-worldapplicationsrequirement,theB-splinetechniqueisusedtorepresentcurvesandsurfacesinthisresearch.AB-splinecurveisasetofbasisfunctionswhichcombinestheeffectsofn+1controlpoints.AparametricB-splinecurveisgivenbyp(u)=Oni=0piNi,k(u)(0#u#1)(1)Pi=controlpointsn+1=numberofcontrolpointsNi,k(u)=theB-splinebasisfunctionsu=parameterForB-splinecurves,thedegreeofthesepolynomialsiscontrolledbyaparameterkandisusuallyindependentofthenumberofcontrolpoints,andtheB-splinebasisfunctionsaredefinedbythefollowingexpression:Ni,1(u)=H1ifui#u#ui+10otherwise(2)andNi,k(u)=u-uiui+k-uiNi,k-1(u)+ui+k+1-uui+k+1-ui+1Ni+1,k-1(u)(3)Wherekcontrolsthedegree(k-1)oftheresultingpoly-nomialsinuandthusalsocontrolsthecontinuityofthecurve.AB-splinesurfaceisdefinedinasimilarwaytoatensorproductinaB-splinecurve.ItisalsopossibletodefineaB-splinesurfacehavingdifferentdegreesintheu-andv-direc-tions:S(u,v)=Oni=0Omj=0pijNi,p(u)Ni,q(v)(0#u#1)(4)3.CurveFittingGivenasetofdatapointsmeasuredfromexistingobject,curvefittingisrequiredtopassthroughthedatapoints.Theleast-squaresfittingtechniqueisthemostusedalgorithmwhichaimsatapproximating,basedonaniterativemethod,asetofdatapointstoformaB-spline57.GivenasetofdatapointsQk,k=0,1,2,.,n,thatlieonanunknowncurvePforcertainparametervaluesuk,k=0,1,2,.,n；itisnecessarytodetermineanexactinterp-olationorbestfittingcurve,P.Tosolvethisproblem,theparametervalues(uk)foreachofthedatapointsmustbeassumed.Theknotvectorandthedegreeofthecurvearealsodetermined.Thedegreeinpracticalapplicationsisgenerally3(order=4).Theparametervaluescanbedeterminedbythechordlengthmethod:QkP(uk)=Oni=0piNi,p(uk)(k=0,1,.,n)(5)u0=0,ui=Oij=1uQj-Qj-1u.Onj-1uQj-Qj-1u.(6)Giventheparametervalues,aknotvectorthatreflectsthedistributionoftheseparametershasthefollowingform:U=0,0,.,0,V1,V2,.,Vn,1,1,.,1p+1p+1Vj=1pOj+p-1i=jui(j=1,2,.,n-p)(7)Pre-ProcessingofDataPointsforCurveFitting637Fig.2.Curvefittingwithunequaldistributionofdatapoints.Itcanbeprovedthatthecoefficientmatrixistotallypositiveandbandedwithabandwidthoflessthanp,therefore,thelinearsystemcanbesolvedsafelybyGaussianeliminationwithoutpivoting.Ni,p(uk)ui,k=0,.,nEquation(5)canbewritteninamatrixform:QNP(8)whereQisan(m+1)1matrix,Nisan(m+1)(n+1)matrix,andPisan(n+1)1matrix.Sincem.n,thisequationisover-determined.ThesolutionisP*=(NTN)-1NTQ(9)4.TheRequirementforFittingaSetofDataintoaB-SplineCurveInordertoproduceaB-splinecurvewitha“goodshape”,somecharacteristicsarerequiredtofitthedatapointsetintoacurvepresentedinB-splineform.First,thedatapointsmustbeinawell-orderedsequence.WhenapplyingtheprogramtofitasetofdatapointsintoaB-splinecurve,thedatapointsmustbereadonebyoneinaspecifiedorder.Ifthedatapointsarenotinorder,thiswillcauseanundesiredtwistoranout-of-controlshapeoftheB-splinecurve.Secondly,anevendispersionofthedatapointsisbetterforcurvefitting.Inthemeasuringprocedure,somefactors,suchasthevibrationofthemachine,thenoiseinthesystem,andtheroughnessofthesurfaceofthemeasuredobjectwillinfluencetheresultofthemeasurement.Allofthesephenom-enawillcauselocalshakesinthecurvewhichpassesthroughtheproblempoints.Therefore,asmoothgradationofthelocationofthedatapointsisnecessaryforgeneratinga“highquality”B-splinecurve.HavingthedatapointsequallydistributedisimportantforimprovingtheresultofparameterisationforfittingaB-splinecurve.AsthemathematicalpresentationshowsinEq.(9),thecontrolpointsmatrixPisdeterminedbythebasisfunctionsNanddatapointsQ,wherethebasisfunctionsNaredeterminedbytheparametersuiwhicharecorrespondtothedistributionofthedatapoints.Ifthedatapointsaredistributedunequally,thecontrolpointswillalsobedistributedunequallyandwillcausealackofsmoothnessofthefittingcurve.Asmentionedabove,inpracticalmeasuringcases,themainsurfaceFig.3.Curvefittingwithequaldistributionofdatapoints.Fig.4.Theprocedureofdatapointspre-processing.ofaphysicalsampleoftenhassomefeaturessuchasholes,islands,andradiusfillets,whichpreventtheCMMprobefromcapturingdatapointswithequaldistribution.Ifacurveisrebuiltbyfittingdatapointswithanunequaldistribution,asshowninFig.2,thegeneratedcurvemaydifferfromtherealshapeofthemeasuredobject.Figure3illustratesthatasmootherandmoreaccuratereconstructionmaybeobtainedbyfittinganequallyspacedsetofdatapoints.5.ThePre-ProcessingofDataPointsToachievetherequirementsforfittingasetofdatapointsintoaB-splinecurveasmentionedabove,itisveryimportantandnecessarythatthedatapointsmustbepre-processedbeforecurvefitting.Inthefollowingdescription,ausefulandeffectivemethodforpre-processingthedatapointsforcurvefittingispresented.Theconceptofthismethodistoregressasetofmeasuringdatapointsintoanon-parametricequationinimplicitorexplicitform,andthisequationmustalsosatisfytheconti-nuityofthecurvature.Foraplanecurve,theexplicitnon-parametricequationtakesthegeneralform:y=f(x).Figure4638M.-C.HuangandC.-C.TaiFig.5.Curvatureiscalculatedbythreediscretepointsonacircle.illustratesanoverviewoftheproceduretopre-processthedatapointsforreverseengineering.Datapointfilteringisthefirststepindisplacingtheunwantedpointsandthenoisypoints.TheoriginaldatapointsmeasuredfromaphysicalprototypeoranexistingsamplebyaCMMareindiscreteformat.Whenthemeasuredpointsareplottedinadiagram,thenoisypointswhichobviouslydeviatefromtheoriginalcurvecanbeselectedandremovedbyavisualsearchbythedesignerforextensiveprocessing.Inaddition,thedistinctdiscontinuouspointswhichapparentlyrelatetoasharpchangeinshapemayalsobeseparatedeasilyforfurtherprocessing.ManyapproacheshavebeendevelopedforgeneratingaCADmodelfrommeasuredpointsinreverseengineering.Acomplexmodelisusuallyconstructedbysubdividingthecom-pletemodelintoindividualsimplesurfaces8,9.EachoftheindividualsurfacesdefinesasinglefeatureinaCADsystemandacompleteCADmodelisobtainedbyfurthertrimming,blendingandfilleting,orusingothersurface-processingtools.Whenthedesignerisgivenasetofunorganiseddatapointsmeasuredfromanexistingobject,datapointsegmentationisrequiredtoreconstructacompletemodelbydefiningindividualsimplesurfaces.Therefore,curvatureanalysisforthedatapointsisusedforsubdividingthedatapointsintoindividualgroups.InordertoextracttheprofilecurvesforCADmodelrecon-struction,inthisstep,datapointsaredividedintodifferentgroupsdependingupontheresultofcurvaturecalculationandanalysisofthedatapoints.Foreach2Dcurve,y=f(x),thecurvatureisdefinedas:k=d2ydx2F1+SdydxD2G3/2=f1+(f)23/2(10)Ifthedataisexpressedindiscreteform,foranythreeconsecutivepointsinthesameplane(X1,Y1)(X2,Y2)(X3,Y3),thethreepointsformacircleandthecentre(X0,Y0)canbecalculatedas(seeFig.5):X0=a-b+cdY0=e-f+g-dwherea=(X1+X2)(X2-X1)(Y3-Y2)b=(X2+X3)(X3-X2)(Y2-Y1)c=(Y1-Y3)(Y2-Y1)(Y3-Y2)d=2(X2-X1)(Y3-Y2)-(X3-X2)(Y2-Y1)Fig.6.Thefilletofthemodel.Fig.7.Thecurvaturechangeofthefillet.e=(Y1+Y2)(Y2-Y1)(X3-X2)f=(Y2+Y3)(Y3-Y2)(X2-X1)g=(X1-X3)(X2-X1)(X3-X2)And,thecurvaturekof(X2,Y2)canbedefinedas:k=1r=1(X0-X2)2+(Y0-Y2)2)(11)Figure6illustratesanexampleinwhichthecurvaturesofaplanecurveconsistingofadatapointsetarecalculatedusingthepreviousmethod.Thecurvatureofthecurvedeterminedbythedatapointsetchangesfrom0to0.0333,assh