A unified architecture for the computation of b-sp

AUniedArchitectureforthecomputationofB-SplineCurvesandSurfaces1MeenakshisundaramGopiSwamiManoharSupercomputerEducationandResearchCentreIndianInstituteofScienceBangalore560012INDIAKeywords:NURBS,Graphics,GeometricModeling,VLSIarchitecture.AbstractB-Splinesingeneral,andNon-UniformRationalB-Splinesinparticular,havebecomeindispens-ablemodelingprimitivesincomputergraphicsandgeometricmodelingapplications.Inthispaperanovelhigh-performancearchitectureforthecomputationofuniform,non-uniform,rationalandnon-rationalB-Splinecurvesandsurfacesispresented.Thisarchitecturehasbeenderivedthroughasequenceofsteps.First,asystolicarchitectureforthecomputationofthebasisfunctionvalues,thebasisfunctionevaluationarray(theBFEA),isdeveloped.UsingtheBFEAasitscore,anarchitec-tureforthecomputationofnon-uniformrationalB-Splinecurvesisconstructed.ThisarchitectureisthenextendedtocomputeNURBSsurfaces.Finally,thisarchitectureisaugmentedtocomputethesurfacenormalssothattheoutputfromthisarchitecturecanbedirectlyusedforrenderingtheNURBSsurface.Theoveralllinearstructureofthearchitecture,itssmallI/Orequirements,itsnon-dependenceonthesizeoftheproblem(intermsofthenumberofcontrolpointsandthenumberofpointsonthecurve/surfacethathastobecomputed),anditsveryhighthroughputmakethisarchitecturehighlysuitableforintegrationintothestandardgraphicspipelineofhigh-endworkstations.Resultsofthetiminganalysisindicateapotentialthroughputofonetrianglewiththenormalvectorsatitsvertices,everytwoclockcycles.1Anextendedabstractofthispaperappearsin[12]11IntroductionTheexplosivegrowthofcomputergraphicsoverthelasttwodecadeshasbeengreatlyfacilitatedbyimpressivehardwareinnovations:Rastergraphicsbecamepopularduetotheemergenceoflow-costsemiconductormemoriesfortheframebuer.Graphicsco-processorsandgraphicsdisplaycon-trollersdesignedwiththegoalofo-loadingthegraphicscomputationfromtheCPUresultedinthewidespreadavailabilityofqualitygraphicscardsforpersonalcomputers.TheGeometryEngine[3]usheredintheeraofhigh-performancegraphicsworkstations.Successivegenerationsofwork-stationshaveexploitedincreasinglevelsofpipeliningandparallelisminthegraphicspipeline(Seeforexample,theRealityEngine[1]).Thegraphicsapplicationshowever,haveconstantlyincreasedtheirrequirementssoastobecontinuouslybeyondthereachofavailablehardwarecapabilities.Inthisevolution,moreandmorecomplexgraphicsabstractionshavebeenmadeavailabletothemainprocessor:startingfromsimplelines,thecurrenthigh-endsystemssupportanti-aliased,Z-buered,Gourard-shaded,24bitsofcolorperpixeltrianglesinhardware.Webelievethatthenextstepinthisevolutionisthemigrationofparametriccurvesandsurfacesintohardware.Anexampleofthistrendistherecentmicrocodeimplementationofnon-uniformrationalB-Splines(NURBS)inagraphicsworkstation[6].InthispaperwepresentauniedarchitectureforthecomputationofvarioustypesofB-Splinecurvesandsurfaces.Webelievethatthisarchitectureissignicantbecauseofthefollowingfactors:ThisistherstsolutiontohandlealltypesofB-Splinecurvesandsurfaces.Thearchitectureiscapableofveryhighperformance:onetrianglewiththenormalsatitsvertices,everytwoclockcycles.ThearchitecturehasalinearstructurethatminimizesthenumberofpinsrequiredinaVLSIimplementation.Thearchitectureisindependentofthesizeofthecurve/patch(intermsofthenumberofcontrolpoints,aswellasthenumberofpointsonthecurve/patch)tobecomputed.Theabovethreefeaturesmakethisarchitecturehighlysuitableforintegrationintothegraphicspipelineofhigh-endworkstations.WearefocusingonB-Splinesratherthanmanyotherparametriccurvesandsurfacesthathavebeendescribedintheliterature,sinceNURBShasemergedasthemodelingprimitiveofchoiceforthegeometricdesigncommunity.Non-uniformrationalB-SplinecurvesandsurfaceshavebeenanInitial2GraphicsExchangeSpecication(IGES)standardsince1983[14].Manycommercialorin-housemodelingapplicationslikeGeomodandProengineerarebasedonrationalB-Splinerepresentations.ThepopularityofrationalB-Splinesisduetothefollowingfacts:Theyprovideonecommonmathematicalformfortheaccuraterepresentationofstandardanalyticshapes,especiallyconics,aswellasfree-formcurvesandsurfaces.ThusunicationofallformsofcurvesandsurfacesisdonebyNURBS.Theyoeranextradegreeoffreedomintheformofweights,apartfromknotvectorandcontrolpoints,whichcanbeusedindesigningwidevarietyofshapes.Theyareprojectioninvariant:Thatis,theprojectionofthecurveisachievedbyprojectingthecontrolpointsandsuitablymodifyingtheweightsofthecontrolpoints.Introductiontorationalquadraticrepresentationofconicscanbefoundin[15].Furtherinfor-mationabouttheNURBSrepresentationofcirclesisin[21],[24].AfewhardwareimplementationsofB-Splineshavebeenreportedintheliterature.OneoftheearlypapersinthisdirectionistheworkofT.Lietal.[16]whereanarchitecturetogenerateBeziercurvesandpatcheswasproposed.DeRose[7]etal.,proposedatriangulararchitecturetogenerateB-SplinecurvesusingthedeBoor-Coxalgorithm.Mathias[17],hasdevelopedasimilararchitectureforBeziercurvesusingthedeCasteljaualgorithm.HehasalsodevelopedarchitecturesforB-SplineinversionandB-Splinegeneration[18].Recently,Megson[19]hascomeupwithadesigntocalcu