Anti-aliased and accelerated ray tracingReadingAliasing in renderingAnti-aliasingPolygon anti-aliasingAntialiasing in a ray tracerSpeeding it upAntialiasing by adaptive samplingFaster ray-polyhedron intersectionRay Tracing Acceleration TechniquesUniform spatial subdivisionUniform GridsSlide 13Slide 14Slide 15Slide 16Caveat: OverlapNon-uniform spatial subdivisionSlide 19Kd-tree - BuildKd-treeSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Surface Area and RaysSlide 31Surface Area HeuristicSlide 33Ray Traversal KernelKd-tree - TraversalSlide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45VariationsHierarchical bounding volumesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don FussellAnti-aliased and accelerated ray tracingUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 2ReadingRequired:Watt, sections 12.5.3 – 12.5.4, 14.7Further reading:A. Glassner. An Introduction to Ray Tracing. Academic Press, 1989. [In the lab.]University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 3Aliasing in renderingOne of the most common rendering artifacts is the “jaggies”. Consider rendering a white polygon against a black background:We would instead like to get a smoother transition:University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 4Anti-aliasingQ: How do we avoid aliasing artifacts?1. Sampling:2. Pre-filtering:3. Combination:Example - polygon:University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 5Polygon anti-aliasingUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 6Antialiasing in a ray tracerWe would like to compute the average intensity in the neighborhood of each pixel. When casting one ray per pixel, we are likely to have aliasing artifacts.To improve matters, we can cast more than one ray per pixel and average the result.A.k.a., super-sampling and averaging down.University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 7Speeding it upVanilla ray tracing is really slow!Consider: m x m pixels, k x k supersampling, and n primitives, average ray path length of d, with 2 rays cast recursively per intersection.Complexity = For m=1,000,000, k = 5, n = 100,000, d=8…very expensive!!In practice, some acceleration technique is almost always used.We’ve already looked at reducing d with adaptive ray termination. Now we look at reducing the effect of the k and n terms.University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 8Antialiasing by adaptive samplingCasting many rays per pixel can be unnecessarily costly. For example, if there are no rapid changes in intensity at the pixel, maybe only a few samples are needed.Solution: adaptive sampling.Q: When do we decide to cast more rays in a particular area?University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 9Let’s say you were intersecting a ray with a polyhedron:Straightforward method intersect the ray with each trianglereturn the intersection with the smallest t-value.Q: How might you speed this up?Faster ray-polyhedron intersectionUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 10Ray Tracing Acceleration Techniques1NFaster IntersectionFewer RaysGeneralized RaysApproachesTighter boundsFaster intersectorUniform gridsSpatial hierarchies k-d, oct-tree, bsp hierarchical gridsHierarchical bounding volumes (HBV)Early ray terminationAdaptive samplingBeam tracingCone tracingPencil tracingUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 11Uniform spatial subdivisionAnother approach is uniform spatial subdivision.Idea:Partition space into cells (voxels)Associate each primitive with the cells it overlapsTrace ray through voxel array using fast incremental arithmetic to step from cell to cellUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 12Uniform GridsPreprocess sceneFind bounding boxUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 13Uniform GridsPreprocess sceneFind bounding boxDetermine resolutionv x y z on n n n n= µ3max( , , )x y z on n n d n=University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 14Uniform GridsPreprocess sceneFind bounding boxDetermine resolutionPlace object in cell, if object overlaps cell3max( , , )x y z on n n d n=University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 15Uniform GridsPreprocess sceneFind bounding boxDetermine resolutionPlace object in cell, if object overlaps cellCheck that object intersects cell3max( , , )x y z on n n d n=University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 16Uniform GridsPreprocess sceneTraverse grid3D line – 3D-DDA6-connected lineUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 17Caveat: OverlapOptimize for objects that overlap multiple cellsTraverse until tmin(cell) > tmax(ray)Problem: Redundant intersection tests:Solution: MailboxesAssign each ray an increasing numberPrimitive intersection cache (mailbox)Store last ray number tested in mailboxOnly intersect if ray number is greaterUniversity of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 18Non-uniform spatial subdivisionStill another approach is non-uniform spatial subdivision.Other variants include k-d trees and BSP trees.Various combinations of these ray intersections techniques are also possible. See Glassner and pointers at bottom of project web page for more.University of Texas at Austin CS384G - Computer Graphics Fall 2010 Don Fussell 19Non-uniform spatial subdivisionBest partitioning approach - k-d trees or perhaps BSP treesMore adaptive to actual scene structureBSP vs. k-d tradeoff between speed from simplicity and better adaptabilityNon-partitioning approachHierarchical bounding volumesBuild similar to k-d tree buildThe University of Texas at Austin Department of Computer Science Don Fussell 20Kd-tree - BuildThe University
View Full Document
Unlocking...