Approximation-of-Variable-Radius-Offset-Curves-and

ApproximationofVariableRadiusOsetCurvesanditsApplicationtoBezierBrushStrokeDesignMyung-SooKimDepartmentofComputerSciencePOSTECHP.O.Box125,Pohang790-600,KoreaEun-JooParkDepartmentofComputerSciencePOSTECHP.O.Box125,Pohang790-600,Korea.Soon-BumLimLBPBusinessDivisionTrigemComputer,Inc.SamjungB/D,237-11NonhyunKangnam,Seoul135-010,Korea.AbstractWepresentanalgorithmtoapproximatethevariableradiusosetcurvesbycubicBeziercurves.TheosetcurveisapproximatedbyacubicBeziercurvewhichinterpolatesthepositionsandderivativesoftheexactosetcurveatbothendpoints.Thus,itapproximatestheexactosetcurveverycloselynearthecurveendpoints,butnotnecessarilyinthemiddleofthecurve.Givenaxedbasecurve,bychangingtheosetradiusanditsderivativeatanendpoint,onecaneasilycontroltheosetcurveshapeneartheendpoint.Tobettercontroltheosetcurveshapeinthemiddleofthecurve,weusetwoglobalshapeparameters(biasandtension)oftheosetcurve(see[16]).Avarietyofvariableradiusosetcurvesareeasilygeneratedbyusingsixshapecontrolparameters(thetwoosetsandtheirderivativesatbothendpoints,andthebiasandtensionparameters).EachbristleofaBezierbrushstrokeisrepresentedbyavariableradiusosetcurve.Evenwithsimplelinearinterpolationsofthesixshapecontrolparameters,thebristlesaregeneratedascubicinterpolationsofthetwoboundarycurves.Thenon-linearinterpolabilitygivesagreatexibilityinmodelingexiblebrushstrokeshapes.Astheshapecontrolparametersarein-terpolated,theassociatedgeometricmeaningsarealsointerpolated,whichmakesthedesignedbrushstrokeshapeslookmorenatural.Thisisanimprovementoverthetwopreviousmethods[4,19]whichisbasedonlinearinterpolationsofthetwoboundarycurves.Byapplyingthesameinterpolationschemetothetimespanaswellastothebrushstrokewidth,itbecomesrelativelyeasytogenerateexibleanimatedmotionsofbrushstrokes.KeyWords:Oset,variableradiusoset,bias,tension,brushstroke,animationToappearinCVGIP:GraphicalModelsandImageProcessing,Vol.55,1993.Computer-AidedDesign,Vol.25,No.11,pp.684{698,1993.ThisresearchwassupportedinpartbyKOSEFandHumanComputers,Inc.11IntroductionOsettingisageometricoperationwhichexpandsagivenobjectintoasimilarobjectbyacertainextent.Ithasvariousimportantapplicationsintoleranceanalysis,cutterpathgenerationforNCmachinetools,collision-freepathplanningforrobotmotions,andforconstant-radiusroundingandlletingofsolids[20].Constantradiusosettingforplanecurveshasattractedextensiveresearchinterestsincomputeraideddesign[7,8,9,13,14,15,18,22].Sinceexactosetcurveshavehighdegreecurveequationswhicharecomputationallyquiteexpensive[8,9,13],manyauthorshaveconsideredapproximatingtheexactosetcurvesbylowdegreeparametriccurves[14,15,18,22].Klass[15]approximatedtheconstantradiusosetcurveforaHermitecubiccurvebyasimilarHermitecubiccurve.TheosetHermitecurveisdeterminedbyosettingthetwocurveendpointsandcomputingthederivativesoftheosetcurveatbothendpoints.TillerandHanson[22]approximatedthe2DosetforaNURBcurvebyasimilarNURBcurve.ThecontrolpolygonfortheapproximatedosetNURBcurveiscomputedbyosettingeachlinesegmentofthecontrolpolygon.Coquillart[5]presentedadierentmethodtocomputethecontrolpolygonfortheosetNURBcurve.Hermethodisgoodforthe3Dosetaswellasforthe2Doset.Pham[18]presentedasimplemethodtoapproximatetheosetcurvebyaB-splinecurvewhichinterpolatesasequenceofosetpointsforasetofcontrolknotsonauniformcubicB-spline.Hoschek[14]suggestedamethodtoapproximatethederivativesofanosetcurveatbothendpointsbyusingtheleastsquaresmethodtoasetofevenlydistributedosetcurvepoints.Theaboveosetcurveapproximationmethodsestimatetheapproximationerrorbyevaluatingthedierencesbetweentheexactandtheapproximatedosetcurvepointsonlyatnitelymanydiscretesamplepoints.ElberandCohen[7]over-estimatetheglobalerrorboundbyapolynomialfunctionandrecursivelysubdividethecurve(neartheparametervalueforthemaximumerror)untiltheoverallapproximationerrorbecomeslessthanagivenerrorbound.FaroukiandNe[8,9]giveadetaileddiscussionontheanalyticandalgebraicpropertiesoftheplaneosetcurves.ThedegreecomplexityoftheexactplaneosetcurveforasimpleintegralpolynomialcurveC(t)=(x(t);y(t))is4d22,wheredisthemaximumdegreeofx(t)andy(t),andisthedegreeofgcd(x0(t);y0(t))[9].Thismeansthattheexactosetcurveforacubicplanecurvemayhavedegree10.Planecurveswithdegreeshigherthan3arecomputationaltooexpensivetobeusefulinpractice.Homann[12,13]suggestedanosetcurvegenerationmethod,withoutderivinganyhighdegreecurveequation,simplybydoingadirectnumericalcurvetracingalongtheintersectioncurveofhigh-dimensionalhyper-surfacesdeninganosetcurve,however,thecurvetracingitselfinvolvesmanycomplexintermediatestepswhichmakeitrunslow.Thus,forthetimebeing,weshouldrelyonsimpleapproximationtechniquesfortheosetcurves.Consideringvariousnicegeometricpropertiesandimportantengineeringapplicationsoftheconstantradiusosetting,onecouldexpectthatthevariableradiusosetting{ageneralizationoftheconstantradiusosetting{wouldhaveevenmoreinterestingmathematicalpropertiesandpracticalapplications.Inthispaper,thevariableradiusosetcurveisshowntohavemanymath-ematicalpropertiessimilartothose