DOC PREVIEW
UCSD CSE 167 - Ray Tracing II & Antialiasing

This preview shows page 1-2-3-4-5-32-33-34-35-64-65-66-67-68 out of 68 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 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 68 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 68 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

#14: Ray Tracing II &AntialiasingCSE167: Computer GraphicsInstructor: Ronen BarzelUCSD, Winter 20061Outline for todaySpeeding 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 TreesBinary 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 TracingAntialiasing 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

UCSD CSE 167 - Ray Tracing II & Antialiasing

Documents in this Course
Lighting

Lighting

38 pages

Review

Review

59 pages

Surfaces

Surfaces

22 pages

Review

Review

110 pages

Midterm

Midterm

4 pages

Lighting

Lighting

38 pages

Lighting

Lighting

71 pages

Review

Review

110 pages

Lighting

Lighting

71 pages

Load more
Download Ray Tracing II & Antialiasing
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 II & Antialiasing 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 II & Antialiasing 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?