To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

RAYINTERPOLANTSFORFASTRAY-TRACINGREFLECTIONS

ANDREFRACTIONS1

FatmaBetulAtalay

DavidM.Mount

DepartmentofComputerScienceUniversityofMaryland,CollegePark

betul,mount@cs.umd.edu

ABSTRACT

Torenderanobjectbyraytracing,oneormoreraysareshotfromtheviewpointthrougheverypixeloftheimageplane.Forre ectiveandrefractiveobjects,especiallyformultiplelevelsofre ectionsand/orrefractions,thisrequiresmanyexpensiveintersectioncalculations.Thispaperpresentsanewmethodforacceleratingray-tracingofre ectiveandrefractiveobjectsbysubstitutingaccurate-but-slowintersectioncalculationswithapproximate-but-fastinterpolationcomputations.Ourapproachisbasedonmodelingthere ective/refractiveobjectasafunctionthatmapsinputraysenteringtheobjecttooutputraysexitingtheobject.Weareinterestedincomputingtheoutputraywithoutactuallytracingtheinputraythroughtheobject.Thisisachievedbyadaptivelysamplingraysfrommultipleviewpointsinvariousdirections,asapreprocessingphase,andtheninterpolatingthecollectionofnearbysamplestocomputeanapproximateoutputrayforanyinputray.Inmostcases,objectboundariesandotherdiscontinuitiesarehandledbyap-plyingvariousheuristics.Incaseswherewecannot ndsuf cientevidencetointerpolate,weperformraytracingasalastresort.Weprovideperformancestudiestodemonstratetheef ciencyofthismethod.Keywords:raytracing,renderingre ectionsandrefractions,interpolation1

INTRODUCTION

Highquality,physicallyaccuraterenderingofcomplexilluminationeffectssuchasre ection,refraction,andspecularhighlightsishighlydesirableincomputer-generatedimagery.Themostpopulartechniqueforgeneratingtheseeffectsisraytracing[Whitt80].However,raytracingremainsacomputa-tionallyexpensivetechnique.Theprimaryexpenseinraytracingliesinintersectioncalculations,especiallyforscenesthatcontaincomplexobjects,suchasBezierorNURBSsurfaces,andincaseofmultiplelevelsofre ectionsand/orrefractions.

Inthispaper,wepresentamethodtoaccelerateraytracingofre ectiveandrefractiveobjectsbyelimi-natingintersectioncalculations.Ouralgorithmfacil-itatesfast,approximaterenderingoftheobjectfromanyviewpoint,andwouldbemostusefulwhenthesameobjectisrenderedfrommultipleviewpointsinasequenceofframes.Thekeyinsighttoourmethodisthatarayintersectingare ectiveorrefractiveobjectgoesthroughasetofre ectionsand/orrefractions,and nallyexitstheobjectasanoutputray.There-fore,wecanmodeltheobjectasafunctionthatmapsinputraystooutputrays.Formanyrealworld

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

tion3,weexplaintheconstructionofourdatastruc-ture.Section4outlinestherenderingphaseandtheheuristicsusedforhandlingdiscontinuities.InSec-tion5,wedescribecomputinglocalillumination.TheexperimentsarepresentedinSection6.Finally,weconcludewithSection7.2

PREVIOUSWORK

Earlyresearchconcentratedonacceleratingraytrac-ingbyreducingthecostofintersectioncomputationsusingboundingvolumehierarchies[Rubin80],spacepartitioningstructures[Glass84,Kapla85],andmeth-odsexploitingraycoherence[Arvo87,Heckb84].Recentresearchhasfocusedonfastgenerationofray-tracedimagesfrommultipleviewpoints.Thesesys-temsexploitframe-to-framecoherenceandreusepix-elsfromthepreviousframebyreprojectionandonlyrecomputeorpossiblyre nethepotentiallyincorrectpixels[Adels95,Walte99].

TheInterpolantRayTracersystemdescribedbyBala,DorseyandTellerintroducedtheradianceinterpolanttoaccelerateshadingbyquadrilinearlyinterpolatingradiancesamplescachedinanadaptive4Ddatastruc-turewhileconservativelyboundingtheerror[Bala99].Wedifferinthatweareprimarilyinterestedinfastrenderingofre ectiveandrefractiveobjects.Ourdatastructuremapsraystoraysratherthanraystoradiance,andweinterpolateamongrays.Bythismethod,wedecouplelocalgeometryoftheobjectfromtheenvironment,andmuchlesssamplingofraysissuf cientthansamplingofradiancetorenderre ec-tive/refractiveobjects.Torenderre ectedtextures,theInterpolantRayTracersystemshootsadditionalre ectionrays,whichisexpensive,especiallyformul-tiplere ections.Theirinterpolationrequiresthattheraytreesofallsamplesusedforinterpolationbeiden-ticaltoconstituteavalidinterpolant.Forre ec-tive/refractiveobjectsthisstrongrequirementsignif-icantlyreducesthecaseswhereinterpolationcouldbesubstitutedforraytracing.Instead,weapplyheuris-ticsthatwouldallowustouseinterpolationsinmorecaseswhiletradingoffqualitytosomeextent.Image-BasedRenderingmethodsconstituteanotherlineofresearchtosupportfastrenderingofscenes.Amongthem,themostrelevanttoourworkistheLumigraph[Gortl96]andLightFieldRendering[Levoy96]techniques.Botharebasedondensesam-plingoftheplenopticfunction[Adels91].Thesesys-temshaveapreprocessingphasewherethe4Dplenop-ticfunctionissampledbyuniformlysubdividinginallfourdimensions.Theradiancealonganyrayfromanyviewpointcanthenbeapproximatedbyquadri-linearlyinterpolatingtheradiancevaluesforthenear-estsixteenraysamples.Tohavereasonablequalityofcomplexeffectssuchasre ection,refractionandspecularhighlights,thesemethodsshouldsampleverydensely.Schirmacher,etal.[Schir99]andSloan,etal.[Sloan97]proposedextensionstotheLumigraph.

Thereexistapproachesotherthanraytracingtoren-derfastapproximationsofre ective/refractiveob-jects.Theoldestsuchmethodisenvironmentmap-ping[Blinn76].Itassumesthattheenvironmentissuf- cientlyfarawayfromthere ectiveobject.Anothermethodexplainedin[Ofek98]isbasedonmirroringthesceneobjectswithrespecttoare ector.Itworksforcurvedre ectorsrelyingonhighresolutiontessel-lationofboththere ectorandthere ectedobjectsandfocusesonasinglelevelofre ection.Heidrich,etal.proposedalight eldmethodforrenderingrefractiveobjects[Heidr99].Theirmethodissimilartooursinthattheyinterpolateraysratherthanradiance.How-ever,sincetheirsystemisbuiltonalight eldstruc-ture,itreliesondensesamplingofraysforcaptur-ingclearobjectboundariesandhandlingdiscontinu-ities.Thus,theirstoragerequirementsarehigh.Ourmethod,ontheotherhand,samplesraysadaptivelyandappliesvariousheuristicstoachievehighqualitydiscontinuityrenderingatlowersamplingrates.3SAMPLINGPHASE3.1

RepresentationofRaysas5DPointsInraytracingimplementations,acommonwaytorep-resentarayisbyitsoriginanddirectionvector.However,sinceweneedarepresentationthatwillallowustosubdividethedirectionspaceeasily,weemploythedirectioncuberepresentationasdescribedby[Arvo87]mappingthe3Ddirectionvectorofanygivenrayto2Dcoordinates.Supposethatisen-closedbyanaxisalignedcubeofsidelength2cen-teredat.Itwillhitoneofthesixfacesofthecubedependingonitsdominantaxis.Onceitisdeterminedwhichfacetherayintersects,canbemappedtoa2Dpoint,,whichistheintersec-tionpointonthatcubeface.Bythismethod,therayspaceispartitionedintosixdirectionalgroups,andaone-to-onemappingisestablishedbetweeneachpar-titionand.Consequently,arayisrep-resentedbyitsorigin,,itsdirectiongroup,,anditsdirectioncoordinates.Fora xednumberofdi-rectiongroups,thiscanbethoughtofasa5Dpoint.

3.2TheRI-Tree

Inthissection,weintroduceourtwo-leveldatastruc-ture,theRI-TreewhichstandsforRayInterpolantTree.Theideaistoencloseourre ectiveortrans-parentobjectwithinaboundingbox,andsampleraysoriginatingfromviewpointslocatedontheboundingboxinvariousdirections.

The rstleveloftheRI-Treecorrespondstotheview-pointspace.Itconsistsofsixseparatequadtreescor-respondingtothefacesoftheboundingbox.Theyre-cursivelydecomposethespaceofviewpoints.Were-fertothesesixquadtreesastheviewpointtree.Thislevelisuniformlysubdividedandthefourcornersofeachleafcellconstitutetheviewpointsamplesasde-pictedinFig.1(a).

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

11000011

direction samples

(a)

(b)

(c)

Figure1:(a)Viewpointtree(oneface)

(b)DirectionhemicubefromVP(c)RI-TreeThesecondlevelcorrespondstothedirectionalspace.Fromeachviewpointsampleintheviewpointtree,raysaresampledinvariousdirections.Thespaceofallpossibledirectionsfromanyviewpointtowardstheobjectconstitutesahemisphereofdirections.Thehemispherecanbereplacedbyadirectionhemicubecreating veseparateviewingfrustums.Independentdirectionhemicubesfornearbyviewpointsareabletobettercapturethevariationsinraysthatareviewpointspeci c.Weimpose vequadtreesonthe vefacesofthehemicube.These vetreesarereferredtoasthedirectiontree.EachviewpointsampleVPhasadirec-tiontree.The2Dcoordinatesofthefourcornersofeachleafcellinthedirectiontreerepresentsthedirec-tionsoftherayswesampleasshowninFig.1(b).Foreachdirectionsample,thecorrespondingray—whichisreferredtoastheinputray—istracedthroughtheobjectandthe nalraythatcomesoutoftheobject—whichisreferredtoastheoutputray—isstoredintheleafcellassociatedwiththatdirectionsample.Raysneedtobesampledmoredenselyinsomere-gionsthanothers.Thesearetheregionswherestrongdiscontinuitiesexist,causingthere ection/refractionpatternsofthenearbyinputraysdiffersubstantially.Forthisreason,thesubdivisionatthedirectionalleveliscarriedoutadaptively,basedonoutputraydistance.However,weimposeanupperlimitonitsdepthtopre-ventthetreefromgrowingexcessively.4RENDERINGPHASE

4.1

SimpleTwo-levelInterpolation

Ourgoalistocomputetheoutputrayforanyinputray

withouttracingtheinputraythroughtheobject.In-stead,wetry

toutilizethecoherenceofrays,andcom-puteanapproximateoutputraybyinterpolationusingsampledrays.SincetheRI-Treestorestheoriginsandthedirectioncoordinatesoftheraysontwoseparatelevels,weapplyatwo-levelinterpolationscheme.Considerthecaseofcomputinganapproximateout-putrayforaninputray,

ontotheboundingboxenclosing.ourFirst,objectweprojectinor-dertosetitsorigintoapointinourviewpointspace.Assumeforthesakeofconcretenessthat,intersectstheboxatpoint.Now,ourqueryrayisrepresentedas.Next,welocatetheleafcelloftheviewpointtreeinwhichlies.LetQNodedenotethis

RR

SW

SE

Figure2:TheleafcellscontainingQand(u,v)leafcell.Then,weconverttothe2Ddirectionco-ordinates,.ForeachviewpointVPcorrespond-ingtothefourcornersofQNode,wetraverseitsdirec-tiontreeandlocatetheleafcellinwhichlies.LetdenotetheleafcellindirectiontreeofVP.AsshowninFig.2,atthispoint,wehavefourdirec-tionalleafcellsassociatedwiththefourVPsofQN-ode.Thesefourcellsprovideussixteencandidateraystobeusedininterpolation:outputraysforthesixteensampledraysoriginatingfromthefourview-pointssurroundingtheoriginofthequeryray,infourdirectionssurroundingthedirectionof.

(a) DQ

VP

(b) QNode

Figure3:Twolevelinterpolation

The rstsetofinterpolationsaredoneatthedirection

treelevel.Foreach,wecomputeanapproxi-mateoutputrayfortheraylabeledasinFig.3(a).

istherayoriginatingfromVPandhasthedirec-tioncoordinates,,whicharethedirectioncoor-dinatesofthequeryray.Itservesasanintermediatequeryray.Theapproximateoutputrayfor,de-noted,iscomputedbybilinearof

andinterpolation

.Afterwecomputeaninterpolatedoutputray,

foreach,wepropagatethese

intermediateoutputraystotheviewpointtreelevel.AsshowninFig.3(b),sareparallelraysinthedirectionofouroriginalqueryray,,andoriginatingfromthefourviewpointssurroundingtheoriginof.Wecomputetheoutputrayfors.Consequently,,bybilinearinterpolationofanapproximateoutputrayforiscomputedbytheinterpolationofsixteenoutputraysamples.

4.2AdvancedInterpolationforDiscontinuities

Thesimpleinterpolationmethodmakesnoassump-tionsaboutthestructureoftheobject,andappliesthesameinterpolationprocedureeverywhere.When

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

therearenostrongdiscontinuitiesinthescene,thesimpleinterpolationmethodperformswellevenwhentheRI-Treeisnotdeep.Ontheotherhand,iftherayinput-outputfunctioncontainsdiscontinuities,asmayoccurattheedgesandtheouterboundaryoftheob-ject,thenwewillobservebleedingofcolorsacrosstheedges.Thiscouldberemediedbybuildingadeepertree,whichwouldinvolvesamplingofraysatpixelresolutioninthediscontinuityregions,butthiswouldresultinunacceptablyhighmemoryrequirements.Anothersolutionmightbetofollowaconservativeap-proachasBala,etal.[Bala99].Ifadiscontinuityisdetected,theydonotinterpolatebutray-trace.Thismethodreducesthecasesonecanbene tfrominter-polation.Ourapproach,however,istoapplyinter-polationmuchmoreaggressively.Weassumethatatlowerlevelsofthetree,discontinuitiescrossingacellwillbeofasimplenatureandcanbetreatedasalinesegment.So,we ndamodelofthediscontinuityandwhileavoidinginterpolationacrossthediscontinuityboundary,westillinterpolateoneitherside.PatchesandEquivalenceClasses:Inordertoex-plainhowthediscontinuitiesarehandled,wewillde-scribethestructureofourobjects.Ouralgorithmisdesignedtohandletheobjectsthatarespeci edasacollectionofsmoothsurfaces,referredtoas“patches”.Thepatchesthatshareacommonedgemayormaynotbejoinedwithsuf cientlyhighcontinuitytopermitinterpolationacrosstheboundary.Forex-ample,inFig.4(a),wecaninterpolatebetweenpatchesAandB,butnotbetweenpatchesCandD.Topro-videthisinformation,weuseasimplemethod.Wegroupthepatchesintoequivalenceclasses.Twoad-jacentpatchesinthesameequivalenceclassareas-sumedtobeconnectedcontinuously.Eachpatchisas-signedapatch-identi erandeachpatch-identi erisassociatedwithaclass-identi erdenotingitsequiv-alenceclass.Associatedwitheachsampledray,westorethepatch-identi erofthe rstpatchithits.

D

A

B

C

(a) (b)

Figure4:Two-patchcase

Two-patchCondition:Intheadvancedinterpola-tionmethod,allthesixteenraysmightnotbeusedforinterpolation.Moreover,theinterpolationmethodmightnotbeappliedatall.Todeterminewhethertocomputetheoutputraybyinterpolationorbytracingtheray,weintroducetheconceptofatwo-patchcon-dition.Let,,...,denotethepatch-identi ersassociatedwiththesixteencandidaterays.If,,...,

aregroupedinatmosttwoequivalenceclasses,the

two-patchconditionissatis ed,implyingthatthereiseithernoneorasinglediscontinuitycrossingthere-gionsurroundedbythesixteenrayhits.Inthiscase,wecanmodelthediscontinuityandinterpolateonei-thersideofit.ThiscaseisshowninFig.4(b).Inthe gure,eachcornerislabeledwiththeclass-identi erofthepatchhitbytheraycorrespondingtothatcorner.Iftwo-patchconditionisnotsatis ed,weassumethatmultiplediscontinuityboundariesexistintheregion,andsoweray-traceratherthaninterpolate.

1

1

1

1

1

1

1

1

2

(a)

21

(b)

11

(c)

22

(d)

2

Figure5:(a)-(b)Badcases(c)-(d)GoodcasesBeforewecontinue,letusmentionafewproblem-aticcasesthatcouldarise.Sincetheknowledgeofthe“numberofdifferentequivalenceclassesoverlapped”isbasedontheinformationobtainedfromthever-tices,wemightbemistaken.Considerthecasesde-pictedinFig.5(a)and(b).Forexample,inFig.5(a),justbylookingatthefourcorners,wewoulddecidethatthecellisoverlappedbytwoequivalenceclassesandoverlookthethirdoneinbetween.Similarlyforpart(b).Wedonotdetectthesecases,andassumethattheyariseveryrarely.Fromthispointon,wewillassumethatifthepatchesaregroupedintwoequivalenceclasses,onlythe“good”casesdepictedinFig.5(c)and(d)couldarise.

Letdenotethepatchthequeryrayhits rst.Inatwo-patchcase,amongthesixteencandidaterays,weuseonlytheonesthathitapatchinthesameequiv-alenceclassas.Sucharayisreferredtoasaus-ableray.Weavoidusingtherayshittingtheothersideofthediscontinuityboundarysincethosewouldpossi-blyhaveverydifferentre ection/refractiondirections.However,sincethequeryrayisnotactuallytraced,wedonotknow.But,weassumethatshouldhitoneofthepatchesin,andwecomputetheexact rstintersectionofwiththeobjectcheckingintersectionsonlywiththepatchesin.Thisisnotasexpensiveasageneralray-tracingoftheray,sincetypicallyonlyafewpatchesarein-volved,andonlythe rstlevelintersectionsofaraytracingprocedureiscomputed.Besides,thiscompu-tationisrequiredonlyinthetwo-patchcases.

Notethat,inordertocatchdiscontinuities,wetakeintoaccount rsthitsonly,howeveritispossibletohavediscontinuitieswithintherestoftheraytree.Cur-rently,thesediscontinuitiesarehandledbynotinter-polatingoutputrayswhichare“distant”fromeachother,asexplainedinSection4.4.

Sinceatleastthreeinterpolantsarerequiredtoper-formaninterpolation,somecellscannotbeusedforinterpolationduetounusablecandidaterays.Theal-

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

gorithmgiveninFig.6summarizestheadvancedin-terpolationmethod.

each(numberofthefourofusableDQsdorays

3)then

(NumberOfUsableDQs

3)then

else

;

failure;tracetheray

Figure6:AdvancedinterpolationalgorithmForthethree-interpolantcases,ifthepointforwhichweattempttoestimatetheoutputrayliesoutsidethetriangularregionformedbythepointscorrespondingtotheusablecandidaterays,thisisnotaninterpola-tionanymore—itbecomesanextrapolation.Sinceex-trapolatedvaluesarelessreliable,theuserisgrantedtheoptionoftuningtheextrapolation.Ifthepointtobeextrapolatedisfartherfromthetriangularregion—intermsofitsbarycentriccoordinates—thanagiventhreshold,extrapolationisdisabledandthecellcan-notbeusedforinterpolation.4.3

ExtraSampling

Wecanreducethenumberofraysray-tracedifwecanusetheDQswithlessthanthreeinterpolantsinsteadofeliminatingthem.Thesecellsaremadeusableby ndingamodelofthediscontinuityandsamplingex-traraysatoneorbothsidesofthediscontinuitytosat-isfythethree-interpolantrequirement.

Duringpreprocessing,ifaleafcellwillnotbesplitanyfurther,buttherayscorrespondingtothefourcor-nershitpatchesthatareintwodifferentequivalenceclasses,two“good”casesmightarise.The rstoneiswhenoneofthecornersisinoneequivalenceclassbyitselfwhereastheotherthreeareinanotherclass.Thesecondcaseiswhentwoofthemareinoneequiv-alenceclasswhiletheothertwoareinanotherclass.

(a)(b)(c)

Figure7:One-andtwo-interpolantcasesWecallthe rstcasetheone-interpolantcase.Con-sidertheexampleinFig.7(a).Thecornersarelabeledwiththeclass-identi erofthepatchhitbytheraycor-respondingtothatcorner.Letdenotetheequiva-lenceclassofpatch.Incasethisnodeisneededforrendering,andif,thentwomoresampled

raysarerequiredonthesamesideofthediscontinu-ityastheNWcornertoperformtheinterpolation.Thedashedcurveinthe guredepictstheactualdisconti-nuity,andthelinesegmentlabeledasistheapproxi-mationwecomputetomodelthediscontinuity.Inor-dertode ne,we ndthetwopointslabeledasand.Bybinarysearchontheupperedgeofthecell,welocatethepointfarthestfromtheNWcornerandthecorrespondingrayofwhichhitsapatch,where

.Thisispoint.Wecomputesimilarly.

Then,wesampletherayscorrespondingtoand.

Thesecondcaseiscalledthetwo-interpolantcase.AnexampleisshowninFig.7(b).Duringtherenderingphase,ifwewanttousethisnodeforinterpolation,ineitherthecaseofor,atleastonemorepointisrequiredtodotheinterpolation.Inthe gure,thedashedcurverepresentstheactualdis-continuity.Weapproximateitbyalinesegmentononesideofthecurveandanotherlinesegmentontheotherside.Tode neand,welocatepoints,,andbybinarysearchsimilartotheone-interpolantcase.Then,wesampleextrarayscorre-spondingtothesepoints.Toillustratetheinterpola-tioninatwo-interpolantcase,considerFig.7(c).Thecellissubdividedintothreeregions(denotedRegion1,2and3).Supposethat.IfisinRegion1,rayscorrespondingtoNWandNEcornersandareusedtointerpolatetheoutputray.If

isinRegion2,NEcorner,andareused.And,if

isinRegion3,thenwehavetheoptionofusingextrapolationusingbarycentriccoordinatescomputedwithrespecttotheNEcorner,and.

4.4HandlingHighCurvature

Normally,weassumethattheusableraysassociated

withthesamecellarelocalizedtoasmallareaandtheirre ection/refractionpatternswouldbesimilar.However,theremightbecaseswherewehavetwoinputraysthatareclosetoeachother,butthecorre-spondingoutputraysaredistantfromeachother.Thiscaseariseswhentheinputrayshitatareasofhighcurvature—ormoregenerallyunderanycircumstanceinwhichthesurfacenormalsvaryrapidlyfornearbyinputrayscausingthemtobere ected/refractedinverydifferentdirections.Inthatcase,wedonotinter-polateamongthoserays.Asameasuretodeterminethedistancebetweentwooutputrays,weusetheangu-lardistancebetweenthedirectionvectorsoftherays.Ifthedistanceisgreaterthanagiventhreshold,thoseraysarenotusableasinterpolants.5LOCALILLUMINATION

The nalcolorisdeterminedbyblendingthelocalilluminationwiththere ected/refractedcolor.Wecomputethere ected/refractedcolorbyshootingtheoutputraythroughtherestoftheenvironment.Sinceweneedintersectionpointsandnormalstocomputelocalillumination,westorethe rstintersectionpoint

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

andthenormalalongwitheachraysample.Thesearethenusedtointerpolatetheintersectionpointandthenormalforthequeryrayapplyingthesameinterpola-tionmethodusedforinterpolatingoutputrays.Onlytheintersectionpointsandnormalsthatareassociatedwithusableraysareusedasinterpolants.6

RESULTS

Inthissection,wepresentpreliminaryresultsofouralgorithm.Theimagesaregeneratedona400MHzSparcprocessor.Oursystemisbuiltonaraytracerwhichisutilizedwhenraysaresampledduringpre-processing,andwheninterpolationcannotbedoneduringrendering.OurmodelsareconstructedfrombicubicBezierpatches.

Aray-tracedimageisgeneratedbytracingeachinputraythroughtheobjecttocomputetheoutputray.Inourexampleimages,an“interesting”objectisplacedinarelativelysimpleenvironment.Aninterpolatedimageisgeneratedbycomputingtheoutputraybyourinterpolationmethod.Wecomparethenumberof oatingpointoperations(FLOPs)andtheCPUtimeforthegenerationoftheoutputraysandthecomputa-tionofthelocalilluminationoftheobject,sincethatisthepartacceleratedbyouralgorithm.Thesearela-beledas“object-only”inthetablesgivenbelow.WealsoprovidethetotalnumberofFLOPsandCPUtimefortheentireimage.Sincetheoutputrayistracedthroughtheenvironment,thetotalFLOPsandCPUtimearenotimprovedasmuchasthosefortheobject-onlyones.Ifwehadusedtheoutputraytoindexanen-vironmentmapinstead,theimprovementratiofortheentireimagewouldbeclosetotheobject-onlyratios.Forourexampleimages,theviewpointtreehasadepthof5.Thedirectiontreesareadaptivelydivided,andtheirdepthsvarybetween1and6.Allimagesare

of

resolution,andasingleinputrayisshotthrougheachpixel.Foreachimage,weprovidetheray-tracedimage,theimagegeneratedbyourinter-polationmethod,andacorrespondingimageshowingwhichpartsaresuccessfullyinterpolatedandwhichpartswereray-tracedduetounusableinterpolants.Thewhitepixelscorrespondtotheray-tracedregions.

Fig.9showsare ectivebowlonaprocedurallytex-turedtableplacedinaroom.Thewallsareshadedindifferentgradientcolors,ortextures.Part(a)showstheinterpolatedimageduringwhosegenerationnodistancethresholdsareimposedamonginterpolants(seesection4.4).Theimageinpart(b)isgeneratedbyimposingananglethreshold,resultinginmoreray-tracedpixels,butabetterqualityimage.Theartifactsaroundtheknobofthebowlwhicharevisiblein(a)areremediedin(b)byray-tracingcorrectregions.Thus,theusercanadjustthedistancethresholdsaccordingtothedesiredaccuracy.Table1givestheperformanceresultsfortheimagesinFig.9.OuralgorithmistwiceasfastintermsofthenumberofFLOPs.Sincethisisaclosed,re ectiveobject,theactualraytracerdoes

notperformmultiplere ections/refractionsforasin-gleray.Theperformancegainishigherinthecaseofrefractiveobjects,becausetheraytracerdoesmoreworkforeachray,whereasouralgorithmperformsthesamesetofinterpolations.Fig.10showsarefrac-tivevaseplacedinasimilarenvironment.Table2givesthecorrespondingperformanceresults.Oural-gorithmisatleastthreetimesfasterintermsofnumberofFLOPs.Iftheangularthresholdislower,thearti-factsaroundthecurvedinteriorofthevasearereme-diedtradingoffperformance.

Forthere ectivebowl,thepreprocessingtakes1hour,andthesizeofthedatastructure(forasinglefaceoftheboundingbox)is189MB.Fortherefractivevase,ittakes2.5hourstobuildadatastructureof191MB.Inourcurrentimplementation,thedatastructurehasnotbeenoptimizedforspaceorpreprocessingtime.Recallthat,theinterpolationmethodproposedbyBala,etal.[Bala99]requiresthatallsixteeninter-polantshaveidenticalraytrees,whereasourmethodappliesinterpolationmuchmoreaggressively.Todemonstratetheadvantageofourmethod,wehavesimulatedthecasewheninterpolationisnotallowedunlesstheraytreesofallsixteeninterpolantsarenotidentical.InFig.9(e),whitepixelsshowthear-easwhereinterpolationcannotbedone.Forre ec-tive/refractiveobjects,veryfewpixelscouldbeinter-polatedwiththismethod.Obviously,sincetheysam-pleadaptivelywithrespecttoradiancein[Bala99],theywouldhavesampledmoredenselyaroundradi-ancediscontinuities,thereforethewhiteregionwouldbethinner.But,thewhiteregionwouldstillexistaroundradiancediscontinuities,whereasinouralgo-rithmtheseregionsarehandledbyrayinterpolationandnotconsideredas

discontinuities.

Figure8:VisualizationofoutputraydistanceDistancebetweentheray-tracedandtheinterpo-latedimages:ThemethodofBala,etal.[Bala99]providesguaranteesonmaximumerrorsinradiance,butoursdoesnot.Sinceourmethodisbasedones-timatingoutputrays,theappropriatequalitymeasurewouldbethedistancebetweentheactualoutputrayandtheinterpolatedoutputray.Fig.8ispresentedtovisualizethedistancebetweenthecorrectoutputrayandtheinterpolatedoutputraycorrespondingtoeachpixeloftheimageshowninFig.9.Theredpixelscor-

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

respondtotheray-tracedareas.Theanglebetweenthecorrectandtheinterpolatedoutputrayscorrespond-ingtothegreenpixelsisgreaterthan.Fortherestofthepixels,theangulardistancebetweenthecor-rectandtheinterpolatedoutputraysvariesbetweento.Thesearedepictedingrayscale:lighterpix-elscorrespondtosmallerangulardistances.Thean-gulardistancediagramontheleftisforaviewpointtreeofdepth5,therightoneisforaviewpointtreeofdepth6.Asexpected,sincetherightdiagramisgen-eratedfromamoredenselysampledtree,theinterpo-latedoutputraysareclosertothecorrectoutputrays.Ifwehadbuiltdeepertrees,wewouldhavegeneratedbetterqualityimageswithahigherperformance.

Theexampleimagesgivenaregeneratedwiththeex-trapolationoff.Enablingextrapolationincreasesthenumberofcaseswecaninterpolate.Thus,theperfor-mancegainishigher,butattheexpenseofquality.7

CONCLUSION

Inthispaper,wedescribedarayinterpolationmethodthatacceleratesraytracingofre ectiveorrefractiveobjects.WehaveintroducedtheRI-Treedatastruc-turestoringadaptively-sampledrayinterpolantsthatareusedtointerpolateanapproximateoutputrayforanyinputraythathitstheobject,insteadoftracingtheinputraythroughtheobject.TheRI-Treeallowstheobjecttoberenderedfromanyviewpointinanydi-rection.Moreover,thesameRI-Treecouldbeusedtorendertheobjectunderchangingilluminationand/orgeometryoftheenvironment.

Accordingtothepreliminaryresults,ouralgorithmspeedsupraytracingforrelativelycomplexobjects.Theperformancegainissigni cant,especiallyifaninputraygoesthroughmultiplelevelsofre ec-tions/refractionsbeforeescapingtheobject,sinceouralgorithmperformsa xedsetofinterpolationsinde-pendentofthenumberofre ections/refractions.Ourinterpolationsareopentofurtheroptimizationssuchasapplyingincrementalcalculationstakingadvan-tageofspatialcoherence.Theperformancegainisachievedatthepotentialexpenseofquality.How-ever,slightartifactsinre ected/refractedimagesareoftentolerable.Besides,oursystemdetectsanddealswiththeobjectboundariesandotherstrongdisconti-nuitieswheretheartifactsaremorelikelytobeno-ticed.Moreover,theuserisgrantedtheoptiontoim-prove/reducequalitybytuningafewparameters.Sincetheentiredatastructureisbuilttofacilitateren-deringfromanyarbitraryviewpoint,thepreprocess-ingtimesarehigh.Forthecurrentversion,weas-sumethatthepreprocessingcostwillbeamortizedovermanyrenderingsinananimation.However,forthefuture,weplantoaddressreducingboththepre-processingtimeandspacerequirement,by llingthedatastructureondemand—wewillgeneratesamplesonlywhenneededasinterpolants.Wewanttoincor-porateacachingmechanisminordertousepreviously

generatedsamplesforthenewviewingposition.Wealsoplantoextendthismethodbysupportingobjectsthatarebothre ectiveandrefractive.REFERENCES

[Adels91]http://www.77cn.com.cnputationalModelsofVisualProcessing,pages1–20,1991.[Adels95]S.J.AdelsonandL.F.Hodges.Generatingexact

ray-tracedanimationframesbyreprojection.IEEEComp.Graph.andAppl.,15(3):43–52,May1995.[Arvo87]J.ArvoandD.Kirk.Fastraytracingbyrayclas-si cation.Proc.ofSIGGRAPH87,21(4):196–205,1987.[Bala99]K.Bala,J.Dorsey,andS.Teller.Radiancein-terpolantsforacceleratedbounded-errorraytracing.ACMTrans.onGraph.,18(3),August1999.[Blinn76]J.F.BlinnandM.E.Newell.Textureandre- http://www.77cn.com.cnmun.ofACM,19:542–546,1976.[Glass84]A.S.Glassner.Spacesubdivisionforfastray

tracing.IEEEComp.Graph.andAppl.,4(10):15–22,October1984.[Gortl96]S.J.Gortler,R.Grzeszczuk,R.Szeliski,and

M.F.Cohen.Thelumigraph.Proc.ofSIGGRAPH96,pages43–54,August1996.[Heckb84]P.S.HeckbertandP.Hanrahan.Beamtrac-ingpolygonalobjects.Proc.ofSIGGRAPH84,18(3):119–127,July1984.[Heidr99]W.Heidrich,H.Lensch,M.Cohen,andH.Sei-del.Light eldtechniquesforre ectionsandrefrac-tions.In10thEurographicsRenderingWorkshop,June1999.[Kapla85]M.R.Kaplan.Spacetracingaconstanttime

raytracer.StateoftheArtinImageSynthesis(SIG-GRAPH85CourseNotes),11,July1985.[Levoy96]M.LevoyandP.Hanrahan.Light eldrender-ing.Proc.ofSIGGRAPH96,pages31–42,1996.[Ofek98]E.OfekandA.Rappoport.Interactivere ec-tionsoncurvedobjects.Proc.ofSIGGRAPH98,14(3):333–342,July1998.[Rubin80]S.RubinandT.Whitted.Athree-dimensional

representationforfastrenderingofcomplexscenes.Proc.ofSIGGRAPH80,14(3):110–116,July1980.[Schir99]H.Schirmacher,W.Heidrich,andH.P.Seidel.

http://www.77cn.com.cnputerGraphicsForum(Eurographics’99),18(3):151–160,September1999.[Sloan97]P.P.Sloan,M.F.Cohen,andS.J.Gortler.Time

criticallumigraphrendering.InProc.of1997Symp.onInteractive3DGraphics,pages17–24,1997.[Walte99]B.Walter,G.Drettakis,andS.Parker.Interac-tiverenderingusingtherendercache.In10thEuro-graphicsWorkshoponRendering,June1999.[Whitt80]T.Whitted.Animprovedilluminationmodelfor

http://www.77cn.com.cnmun.ofACM,23(6):343–349,June1980.

To render an object by ray tracing, one or more rays are shot from the viewpoint through every pixel of the image plane. For reflective and refractive objects, especially for multiple levels of reflections and/or refractions, this requires many expensive i

(a)

(b)

(c)

(d)(e)

Figure9:(a)Interpolatedimage(noanglethreshold)&correspondingcolor-codedimage,whiteareasshowray-tracedrays(b)Interpolatedimage(anglethresholdimposed)&correspondingcolor-codedimage(c)Ray-tracedimage(d)Theroomasviewedwhenlookingintothefrontofthebowl(samedirectionasin(a)(b)and(c))andfrombehindthebowl(e)Interpolationbyourimplementationoftheraytreeapproach[Bala99].

FLOPS

68441271657781

(object-only)37.55719.48526.70736.211

FLOPS

(total)73.89852.20659.45271.281

Table1:Performanceresultsforthere ective

bowl

(a)(b)

Figure10:(a)Ray-tracedimage(b)Interpolatedimage&correspondingcolor-codedimage.

FLOPS

14237

(object-only)118.04739.649

FLOPS

(total)191.99497.309

Table2:Performanceresultsfortherefractivevase