#14: Ray Tracing II &AntialiasingCSE167: Computer GraphicsInstructor: Ronen BarzelUCSD, Winter 20061Outline for todaySpeeding up Ray Tracing Antialiasing Stochastic Ray Tracing2Where we are now Ray tracing: cast primary rays from eye through pixels intersect with objects cast rays towards lights to determine shadowing recursively cast reflection and refraction rays3Need for acceleration structures Lots of rays: Scenes can contain millions or billions of primitives Ray tracers need to trace millions of rays This means zillions of potential ray-object intersections Infeasible to test every object for intersection Just looping through all objects*rays would take days Not even counting time to do the intersection testing or illumination Acceleration structures Major goal: minimize number of intersection tests• Tests that would return false (no intersection)• Tests that would return an intersection that’s not closest to origin Core approach: Hierarchical subdivision of space• Can reduce O(N) tests to O(log(N)) tests (Other acceleration techniques too… beam tracing, cone tracing, photon maps, …)4Bounding Volume Hierarchies Enclose objects with hierarchy of simple shapes Same idea as for frustum culling Test ray against outermost bounding volume• If ray misses bounding volume, can reject entire object• If ray intersects volume, recurse to child bounding volumes• When reaching the leaves of the hierarchy, intersect with primitives Can keep track of current nearest intersection along ray• If bounding volume is farther away that, no need to test intersection5 Culling complex objects or groups If an object is big and complex, it’ s possible that only partsof it will be in view. Or if we have groups of objects, it’s possible that entiregroups will be out of view. Want to be able to cull the whole group quickly But if the group is partly in and partly out, want to be able to cullindividual objects.6E.g. Sphere Hierarchy Test for intersection against outermost sphere7E.g. Sphere Hierarchy Outer sphere hits: test children ignore child spheres that don’t intersect8E.g. Sphere Hierarchy Test contents of bottom-most spheres (Actually, hierachy would probably go down a few more levels)9Bounding Volume Hierarchies Spheres good example of the concept Spheres not used much in practice: No great techniques to automatically construct a good sphere hierarchy Spheres tend to overlap, so we would do redundant intersection tests Other bounding volumes Axis-aligned bounding boxes (AABBs) Oriented bounding boxes (OBBs) Can be good individual models Not great for organizing entire scenes10Octrees Start by placing a cube around the entire scene If the cube contains “too many” primitives (say, 10) split equally into 8 nested cubes recursively test and possibly subdivide each of those cubes More regular structure than the sphere tree Provides a clear rule for subdivision and no overlap between cells This makes it a better choice than sphere usually But still not ideal; lots of empty cubes11Octree(2D illustration is a quadtree)12KD Trees Place a box (not necessarily a cube) around the entire scene If the box contains too many primitives: Split into two boxes Boxes need not be equal Split in the x, y, or z direction, at some arbitrary position within the box Heuristics to choose the split direction & position Adapts to irregular geometry Tighter fit than octree Pretty good for ray tracing Main drawback: tree can get deep Lots of time traversing the tree itself (called “KD” because it works the same in any number of dimensions)13KD Tree14BSP TreesBinary Space Partitioning (BSP) tree Start with all of space If there are too many objects, split into two subspaces: choose a plane to divide the space in two the plane can be placed anywhere and oriented any direction heuristics to choose a good plane recurse to children Similar to KD tree: recursively splits space into two (unequal) parts Potential to more tightly bound objects Harder to choose splitting plane Harder to work with arbitrary-shaped regions In practice, BSP trees tend to perform well for ray tracing15BSP Tree16Uniform Grids Divide space into a uniform grid, instead of hierarchically Use ray marching to test the cells Don’t need to test intersection against each grid cell Find cell where ray enters grid Test all objects in current cell• If intersected an object, we’re done• Else, move to the next cell the ray passes through Uniform grids can be very fast, or can be slow and a waste of memory Depends on distribution of objects into cells Need to choose grid size properly No good distribution if scene has large variation in object size and location Uniform grids not a practical general-purpose solution17Uniform Grid18Ray Marching1 2 34 5 619Hierarchical Grids Start with a uniform grid If any cell has too many primitives subdivide that cell into a grid subgrid can have any number of cells recurse if needed (Octree: a hierarchical grid limited to 2x2x2 subdivision Hierarchical grids can perform very well20Acceleration Structures Ray tracers always use acceleration structures to make the algorithm feasible No one “best” structure Ongoing research into new structures and new ways of using existing structures Considerations include: Memory overhead of data structure Preprocessing time to construct data structure Ability to optimize well, given machine architecture For animation: Ability to update data structure as objects move21Outline for today Speeding up Ray TracingAntialiasing Stochastic Ray Tracing22Texture Minification Remember texture minification Texture mapped triangle triangle small or far away many texels land in a single pixel Point-sample the texture? i.e. take the texel at the center misses lots of detail causes “shimmering” or “buzzing” especially noticeable of objector view moves Solution was to filter Texture buzzing is an example of aliasing Filtering the texture is an example of antialiasing23Small Triangles Aliasing when triangles very small About the size of a pixel, or smaller Scan conversion: point sampling Pixel color due to triangle that
View Full Document