DOC PREVIEW
UVA CS 445 - Ray Tracing 2- Acceleration

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Ray Tracing 2: AccelerationRay Tracing Acceleration TechniquesUniform GridsSlide 4Slide 5Slide 6Slide 7Caveat: OverlapSpatial HierarchiesSlide 10VariationsCreating Spatial HierarchiesMedian-CutSurface Area and RaysSlide 15Ray Traversal AlgorithmsHierarchical GridsHierarchical Bounding VolumesComparisonCS 445Greg Humphreys, Spring 2003Ray Tracing 2:AccelerationGreg Humphreys, Spring 2003Intro Graphics Raytracing StufRay Tracing Acceleration TechniquesToo Slow!Uniform gridsSpatial hierarchies•K-D•Octtree•BSPHierarchical gridsHierarchical bounding volumes (HBV)Tighter boundsFaster intersectorEarly ray terminationAdaptive samplingBeam tracingCone tracingPencil tracingFaster intersectionN 1Fewer rays Generalized raysGreg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding boxGreg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3. Place object in cell if its bounding box overlaps the cell3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess scene1. Find bounding box2. Determine grid resolution3. Place object in cell if its bounding box overlaps the cell4. Check that object overlaps cell (expensive!)3| |n d O=Greg Humphreys, Spring 2003Intro Graphics Raytracing StufUniform GridsPreprocess sceneTraverse grid3D line = 3D-DDA6-connected lineGreg Humphreys, Spring 2003Intro Graphics Raytracing StufCaveat: OverlapOptimize objects that overlap multiple cellsCaveat 1 (correctness):Intersection must lie within current cellCaveat 2 (eficiency):Redundant intersection tests“Mailboxes”Assign each ray a numberObject intersection cache (“mailbox”)•Store ray number, intersection informationGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSpatial HierarchiesABCDABCDLeaf nodes correspond to unique regions in spaceGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSpatial HierarchiesABCDABCDPoint location by recursive searchGreg Humphreys, Spring 2003Intro Graphics Raytracing StufVariationsKD treeocttree BSP treeGreg Humphreys, Spring 2003Intro Graphics Raytracing StufCreating Spatial Hierarchiesinsert(node,prim) {if( overlap(node->bound,prim) )if( leaf(node) ) {if( node->nprims > MAXPRIMS && node->depth < MAXDEPTH ) {subdivide(node);foreach child in nodeinsert(child,prim)}else list_insert(node->prims,prim);}elseforeach child in nodeinsert(child,prim)}// Typically MAXDEPTH=16, MAXPRIMS=2-8Greg Humphreys, Spring 2003Intro Graphics Raytracing StufMedian-CutBuild hierarchy bottom-upChose direction and position carefullySurface-area heuristicGreg Humphreys, Spring 2003Intro Graphics Raytracing StufSurface Area and RaysNumber of rays in a given direction that hit an object is proportional to its projected areaThe total number of rays hitting an object is Crofton’s theorem:For a convex body: Example: SphereprojA4 Ap4SA =2 24 S r A rp p= =Greg Humphreys, Spring 2003Intro Graphics Raytracing StufSurface Area and RaysProbability of a ray hitting an object that is completely inside a cell is:cSoS[ ]ProcSr OS� =Greg Humphreys, Spring 2003Intro Graphics Raytracing StufRay Traversal AlgorithmsRecursive inorder traversalKaplan, Arvo, Jansenmintmaxt*t*maxt t<Intersect(L,tmin,tmax)mintmaxt*t*min maxt t t< <Intersect(L,tmin,t*)Intersect(R,t*,tmax)maxtmint*t*mint t<Intersect(R,tmin,tmax)Greg Humphreys, Spring 2003Intro Graphics Raytracing StufHierarchical GridsGood compromise preferred by many practitionersIMAGEIMAGEIMAGEGreg Humphreys, Spring 2003Intro Graphics Raytracing StufHierarchical Bounding VolumesCreate tree of bounding volumesChildren are contained within parentCreation preprocessFrom model hierarchyAutomatic clusteringSearchintersect(node,ray,hits) {if( intersectp(node->bound,ray)if( leaf(node) )intersect(node->prims,ray,hits)elsefor each childinter sect(child,ray,hits)}Greg Humphreys, Spring 2003Intro Graphics Raytracing StufComparisonScheme SpheresRingsTreeUniform grid D=1 244 129 1517D=2038 83 781Hierarchical grid34 116 34Vlastimil Havran, Best Efficiency Scheme


View Full Document

UVA CS 445 - Ray Tracing 2- Acceleration

Documents in this Course
Lighting

Lighting

49 pages

Color

Color

20 pages

Clipping

Clipping

10 pages

Shadows

Shadows

95 pages

Color

Color

37 pages

Radiosity

Radiosity

49 pages

Clipping

Clipping

59 pages

Assign 3

Assign 3

28 pages

Splines

Splines

17 pages

Color

Color

17 pages

Load more
Download Ray Tracing 2- Acceleration
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Ray Tracing 2- Acceleration and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Ray Tracing 2- Acceleration 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?