Towards Accurate and Efficient Volume Rendering

TOWARDSACCURATEANDEFFICIENTVOLUMERENDERINGADissertationPresentedtotheFacultyoftheGraduateSchoolofCornellUniversityinPartialFulllmentoftheRequirementsfortheDegreeofDoctorofPhilosophybyKevinLawrenceNovinsJanuary1994cKevinLawrenceNovins1994ALLRIGHTSRESERVEDTOWARDSACCURATEANDEFFICIENTVOLUMERENDERINGKevinLawrenceNovins,Ph.D.CornellUniversity1994Thisthesisisconcernedwithimprovementstoalgorithmsforvolumerendering;atechniquethatprovidesscientistswiththemeansforvisualexplorationofthree-dimensionaldata.Despiteitsnumeroussuccesses,anditsincreasingusewithinthescienticcommunity,state-of-the-artvolumerenderingalgorithmshavemanyshortcomings.Dicultiesinclude:ensuringtheaccuracyoftherenderedimages,producingimageswithmodestcomputationalresources,andrenderingthediversetypesofdatathatarecurrentlybeingproduced.Theworkinthisthesiswasmotivatedbythedemandsofanongoingvisu-alizationprojectinfour-dimensionalcardiacvisualization.Wepresentsolutionstosomekeyproblemsinensuringaccuracyandinproducingalgorithmsthatcanscaletohandlelargedatasets.Althoughthetheoreticalworkinthisthesisappliestoarbitrarydatatopologies,ourimplementationshaveassumedthatthedataisdenedbysamplepointsonaregularrectilineargrid.Intheareaofaccuracy,wefocusontheerrorthatisintroducedduringvolumeprojection.Thisphaseofthevolumerenderingprocessinvolvestheevaluationoftheemission-absorptionvolumerenderinglineintegral.Thisthesispresentsfourtechniquesforcontrolledprecisionvolumeintegration.Theseschemadepartfromexistingapproachesinthattheyprovideerrorboundsalongwiththesolutionstheygenerate.Ineachcase,theerroranalysisleadstoanalgorithmforevaluatingtheintegraltoanyspeciedtolerance.Ourinvestigationsintoeciencyissueshaveresultedintwoadvances.First,anadaptiveerrorbracketingschemeispresentedthatbuildsonthecontrolledprecisionvolumeintegrationmethods.Usingadaptiveerrorbracketing,thesolutionforaviewingrayiscontinuallyreneduntilauser-speciederrortoleranceismet.Thealgorithmallowsprocessingofthedatawithoutimposingastrictfront-to-backorback-to-frontevaluationorder.Second,asuiteoftoolsarepresentedthatcanbeusedtoecientlycomputeperspectiveprojectionsofvolumedata.TheseincludeapagingstrategythatisusefulwhenadatasetistoolargetotintoRAMmemoryandaraysplittingtechniqueforadaptivesupersampling.Thelattertechniqueensuresthatalldatafeaturescontributetothenalimagewhileavoidingovercomputationinregionsclosetotheeyepoint.BIOGRAPHICALSKETCHKevinL.NovinswasbornonDecember2,1963.HeattendedpublicschoolsinWestchesterCounty,NewYorkandgraduatedfromArdsleyHighSchoolin1981.HestudiedcomputerscienceatHarvardUniversity,andreceivedtheBachelorofArtsdegreein1985.AftergraduationfromcollegeheperformedresearchinmedicalimagingattheNorthCarolinaMemorialHospital.HeenteredCornellUniversityinthefallof1987andreceivedtheMasterofSciencedegreein1990andtheDoctorofPhilosophydegreein1994.iiiACKNOWLEDGEMENTSFirst,IwouldliketothanktheChairofmythesiscommittee,DonaldP.Greenberg,formakingthisworkpossible.Hehelpedmetosetmygoalsandworkedtoestablishandmaintaintheresearchcollaborationsthatwerenecessaryforcarryingthemthrough.Iappreciatedhisguidance,enthusiasm,dedicationtoquality,andunwaveringsupport.Ialsoappreciatedhisteachingmehowtopresentmyresearchproperly.Iamgladforallthetimesthatweworkedcloselytogether.DonhascreatedawonderfulenvironmentattheProgramofComputerGraphicsandIamgratefulthathegavemetheopportunitytoworkandstudythere.MuchofthisresearchcouldnothavebeenperformedwithoutthehelpofJimArvo,whowasanadvisorandafriendthroughouttheprocess.ItwasJimwhorststimulatedmyinterestinperforminganerroranalysisofvolumerendering.Heassistedinhigh-levelplanning,inworkingoutimplementationissues,andinsettlingsomeofthenalproductiondetails.JimalsohelpedmetosortoutmythoughtswhenIgotfrustrated,andprovidedencouragementduringresearchslowdowns.IamgratefultoJimforhiscontributionstothisthesisandforallthathehastaughtme.ivAnotherfriendandadvisorwasFrancoisSillion.Francoiswasinstrumentalinteachingmehowtoperformgraduate-levelresearch,andhelpedtogetmestartedonthisdissertation.Iwouldliketothankhimforhelpingmetobecomemoreofascientistandlessofahacker.IwouldalsoliketothankDavidSalesin,whowasacolleagueindevelopingtheadaptiveerrorbracketingalgorithm.Hisenthusiasmwaskeytothesuccessofthatproject,andhehelpedagreatdealtomovemealongtowardsgraduation.ThecollaborativeresearchprojectincardiacvisualizationthatIdiscussinChapter6wastheimpetusforthisresearch.ItwasapleasuretoworkwithDr.RichardDevereuxoftheCornellMedicalCenter,Dr.RiccardoPinioftheUniversityofFirenze,andStevenLeavittofHewlett-Packard.TheyconvincedmeoftheimportanceoftheprojectandprovidedmewiththeeducationthatIneededinthemedicalandengineeringaspectsofultrasonicimaging.IwouldliketothankDanielHuttenlocherandAnthonyReevesforservingonmythesiscommittee.Severaloftheresultspresentedherehavebeenpublishedintheformofresearchpapers.Iamgratefultomyco-authorsfortheircontributions,particularlysincesectionsoftextandgureshavebeenincorporatedintothisthesis.Specically,Iwouldliketothank:FrancoisSillionandDonaldGreenberg,myco-authorsfor\