DOC PREVIEW
UCSD CSE 168 - Lecture

This preview shows page 1-2-3-4-28-29-30-31-58-59-60-61 out of 61 pages.

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

Unformatted text preview:

CSE168Computer Graphics II, RenderingSpring 2006Matthias ZwickerPractical details• Assignment 1 due Monday April 17, noon• Lab hours Thursday 11am – 12 30pm• Office hours Friday 3pm – 4pm, EBU3B 4114• Handout of assignment 2 in class MondayLast time•Reflection•Refraction•ShadowsMirror reflectionRefraction• At interface between dielectric materials (insulators)• Diamond, glass, water,air• Light travels at differentspeeds• Light is bent at theinterfaceRefraction• Fermat’s principle“The actual path between two points taken by a beam of light is the one which is traversed in the least time. “• Snell’s lawDispersion• Index of refraction varies with wavelengthSpecular refractionHow much light is reflected and refracted?Ideal dielectric, smooth surfaceLight waves• Electromagnetic waves[http://en.wikipedia.org/wiki/Image:Light-wave.png]Polarization• Electric wave vector[http://en.wikipedia.org/wiki/Polarization]Linear polarizationCircularpolarizationEllipticalpolarizationtttFresnel equations• Reflection of light polarized parallel and perpendicular to the plane of refractionGlass sphere• No Fresnel reflectionGlass sphere• With Fresnel reflectionShadow raysOccluderShadow rayShadow raysOnly accept intersections if[Jensen]Shading so farcolor shade( hit ) {c = blackfor all lights L[k] {if( L[k] visible) {c += diffuse( hit, L[k] )c += specular( hit, L[k] )}}c += ambient( hit ) trace( reflected ray, &reflected_hit)c += shade( reflected_hit )trace( refracted ray, &refracted_hit)c += shade( refracted_hit )return c}Today• Triangle meshes• Aggregate objects• Acceleration structures• Bounding volume hierarchiesTriangle meshesTriangle meshesclass mesh : object {triangle t[N]}class triangle : object {vector3 v1, v2, v3 // verticesvector3 n1, n2, n3 // normals... // other attributes}Triangle meshesclass mesh {triangle t[N]vertex v[NV]}class vertex {vector3 p // verticesvector3 n // normals... // other attributes}class triangle : object {int i1, i2, i3mesh *m}class aggregate : object {bool intersect( ray, &hit )bounding_volume get_bv()object children[]bounding_volume bv}class bounding_volume {bool hit( ray )}• Aggregate objects represent groups of objects• Derived from object classAggregate objectsAggregate objectsbool aggregate::intersect( ray, &hit ) {if( bv.hit( ray ) ) {bool hit_child = falsefor all children k {if( children[k].intersect( ray, &hit ) ) {hit_child = trueif( hit.t < closest_hit.t ) {closest_hit = hit}}}return hit_child} else {return false}Aggregate objects• Object hierarchies•Instancing• E.g., triangle meshesinstance->aggregate->triangle[]Acceleration structures• How long does your ray tracer take to compute images?Acceleration structures• How long does your ray tracer take to compute images?• Where does it spend most of its computation time?for all pixels {computeprimary( &ray )for all objects {intersect( ray, &hit )if hit is closer than firsthit {firsthit = hit}}shade( firsthit )}Ray tracing pseudocodeCost• For each ray, the cost is linear in the number of objects in the scene• Complexity per ray• Total cost: objects*raysExample• 1024x1024 image, 1000 triangles• 10^9 ray triangle intersectionsCost• 6320 trianglesCost• 6320 triangles per rayAcceleration structures• Goal: “sub-linear” complexity• Don’t touch every single objectAcceleration structuresAcceleration structuresTwo fundamental approaches• Hierarchies of groups of objects“object subdivision”• Space partitioning“spatial subdivision”Acceleration structures• Hierarchies of groups of objectsAcceleration structures• Hierarchies of groups of objectsAcceleration structures• Hierarchies of groups of objectsAcceleration structures• Groups are represented by aggregate objects with bounding volumes• “Bounding volume hierarchies”, BVH• Logarithmic complexityBounding volume hierarchies• Tree structure• Each internal node is an aggregate object with a bounding volume• Leave nodes are objectsaggregate objectBounding volume hierarchies• All objects in a subtree are within the bounds of its root• Not all objects within the bounding volume of a node need to be in its subtree• Subtrees can overlap spatially• Subtrees are not ordered in any wayBounding volume hierarchies• If a node is not intersected by a ray, none of the objects in its subtree are• The subtree can be pruned during intersection testing• If a node is intersected, all children have to be tested for intersectionsclass aggregate : object {bool intersect( ray, &hit )boundary_volume get_bv()object children[]bounding_volume bv}class bounding_volume {bool hit( ray )}Bounding volume hierarchies• Build upon aggregate class• Can construct n-ary or binary treesBounding volume hierarchiesbool aggregate::intersect( ray, &hit ) {if( bv.hit( ray ) ) {bool hit_child = falsefor all children k {if( children[k].intersect( ray, &hit ) ) {hit_child = trueif( hit.t < closest_hit.t ) {closest_hit = hit}}}return hit_child} else {return false}• Recursive intersectionBounding volume hierarchies• Bounding volumes– Bounding boxes– Bounding spheres– Bounding anythingAxis aligned bounding boxesclass object {...bounding_volume get_bv()}aggregate::get_bv() {bv = combined bounding volumes of all childrenreturn bv}instance::get_bv() {bv = transform bounding volume to world coordinatesreturn bv}Axis aligned bounding boxes•Fast intersection• Intersection with axis aligned slabsAxis aligned bounding boxesAxis aligned bounding boxes• Intersection testif( t_xmin>t_ymax ) or ( t_ymin>t_xmax ) {return false} else {return true}Axis aligned bounding boxes• Ray-plane intersection–Ray–Plane– Intersection• Axis aligned planeAxis aligned bounding boxes•Careful…• If d_x < 0, ray hits x_max intersection first, then x_min• Additional testif( x_d >= 0 ) {t_xmin = ( x_min – e_x ) / d_xt_xmax = ( x_max – e_x ) / d_x} else {t_xmin = ( x_max – e_x ) / d_xt_xmax = ( x_min – e_x ) / d_x}Axis aligned bounding boxes• What happens if a ray is parallel to a coordinate axis?•E.g.,• Division by zero!Axis aligned bounding boxes• Three possibilities1. No hit2. Hit3. No hit1. 2. 3.Axis aligned bounding boxes• Rely on IEEE floating point arithmetic1.2.3.1. 2. 3.BVH construction• Partitioning objects along coordinate axes (Shirley section 9.2.2)•Binary treeBVH constructionBVH constructionBVH


View Full Document

UCSD CSE 168 - Lecture

Download Lecture
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 Lecture 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 Lecture 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?