Last Time An introduction to global illumination We can t solve the general case so we look to special cases Light paths as a way of classifying rendering algorithms L S D E Raytracing Captures LDS E paths Start at the eye any number of specular bounces before ending at a diffuse surface and going to the light Can also do LSE and LE if light source is not a point 05 02 02 c 2002 University of Wisconsin Today Issues in implementing a ray tracing algorithm How to intersect rays with various objects Texture mapping and other enhancements Area light sources and soft shadows 05 02 02 c 2002 University of Wisconsin Raytracing Implementation Raytracing breaks down into two tasks Constructing the rays to cast Intersecting rays with geometry The former problem is simple vector arithmetic The intersection problem arises in many areas of computer graphics Collision detection Other rendering algorithms Intersection is essentially root finding as we will see Any root finding technique can be applied 05 02 02 c 2002 University of Wisconsin Constructing Rays Define rays by an initial point and a direction x t x0 td Eye rays Rays from the eye through a pixel Construct using the eye location and the pixel s location on the image plane x0 eye Shadow rays Rays from a point on a surface to the light x0 point on surface Reflection rays Rays from a point on a surface in the reflection direction Construct using laws of reflection x0 surface point Transmitted rays Rays from a point on a transparent surface through the surface Construct using laws of refraction x0 surface point 05 02 02 c 2002 University of Wisconsin Ray Object Intersections Aim Find the parameter value ti at which the ray first meets object i Transform the ray into the object s local coordinate system Makes ray object intersections generic ray sphere ray plane Write the surface of the object implicitly f x 0 Unit sphere at the origin is x x 1 0 Plane with normal n passing through origin is n x 0 Put the ray equation in for x Result is an equation of the form f t 0 where we want t Now it s just root finding 05 02 02 c 2002 University of Wisconsin Ray Sphere Intersection Ray x t x0 td Sphere x x 1 0 Substitute x0 td x0 td 1 0 d d t 2 2 x0 d t x0 x0 1 0 Quadratic in t 2 solutions Ray passes through sphere take minimum value that is 0 1 solution Ray is tangent use it if 0 0 solutions Ray does not hit sphere 05 02 02 c 2002 University of Wisconsin Ray Plane Intersections Ray x t x0 td Plane n x 0 Substitute n x0 td 0 n d t n x0 0 n x0 t n d To do polygons intersect with plane then do point inpolygon test 05 02 02 c 2002 University of Wisconsin Point in Polygon Testing Project point and polygon onto a 2D plane Find biggest component of normal vector and just use other two coordinates For example if n 0 2 0 4 0 9 just use x y coordinates which is like projecting down onto the x y plane Cast a ray from the point to infinity and count the number of edges it crosses Odd number means point is inside Edge crossing tests are very fast think clipping 05 02 02 c 2002 University of Wisconsin More complex tests Ray Polygon test reveals a common strategy Intersect with something easy a superset of the actual shape Do a bounds check to make sure you have actually hit the shape Also works for cylinders disks cones CSG is well suited to raytracing Find intersection along ray of all the CSG primitives Break the ray into intervals according to which primitives it is in Do set operations to find the first interval that is actually inside the CSG object 05 02 02 c 2002 University of Wisconsin CSG Intersection Testing Subtract Intersection intervals 05 02 02 c 2002 University of Wisconsin Subtract intervals Ray Patch Intersection Ray x t x0 td Patch x u v 3 3 P B u B v 0 ij i j i 0 j 0 Substitute x0 td 3 3 P B u B v 0 ij i j i 0 j 0 Equation in 3 parameters two for surface and two for ray Solve using Newton s method for root finding Have derivatives from basis functions Starting point from control polygon or random guess or try a whole set of different starting values 05 02 02 c 2002 University of Wisconsin Details Must find first intersection of ray from the eye Find all candidate intersections sort them and take soonest Techniques for avoiding testing all objects Bounding boxes that are cheap to test Octrees for organizing objects in space Take care to eliminate intersections behind the eye Same rules apply for reflection and transmission rays Shadow ray just has to find any intersection shadowing the light source Speedup Keep a cache of shadowing objects test those first 05 02 02 c 2002 University of Wisconsin Transforming Normal Vectors Normal vectors are not transformed the same way points are Ray directions behave like normal vectors Plane equation should still be true with transformed points Transform normal vectors with the inverse transpose of the transformation matrix For rotations matrix is its own inverse transpose 05 02 02 c 2002 University of Wisconsin Plane Eqn nT x 0 Kn T Mx 0 nT K T Mx 0 K T M I M T K I K M T 1 Numerical Issues Shadow reflection and transmission rays have to be sure they don t intersect the surface they are leaving Can t just ignore the object the ray is leaving some objects self shadow Solution Use a tolerance offset the starting point off the surface a little in the normal direction Finding all the intersections with a spline surface patch is difficult CSG can have problems when doing set operations Make sure pieces being subtracted protrude above surfaces Bad 05 02 02 Good c 2002 University of Wisconsin Mapping Techniques Raytracing provides a wealth of information about the visible surface point Position normal texture coordinates illuminants color Raytracing also has great flexibility Every point is computed independently so effects can easily be applied on a per pixel basis Reflection and transmission and shadow rays can be manipulated for various effects Even the intersection point can be modified 05 02 02 c 2002 University of Wisconsin Texture Mapping Define texture parameters over the surface Determine texture parameters at each hit point Use them to look up a texture map just as with OpenGL But Can also use them to look up other things 05 02 02 c 2002 University of Wisconsin Bump Mapping Vary the surface normal vector according to some map Influences shading and reflection and refraction Variation may be random for effects like stucco or structured for effects like tiles 05 02 02 c 2002 University of Wisconsin Bump
View Full Document
Unlocking...