Ray Casting3D RenderingSlide 3Slide 4Ray casting != Ray tracingCompare to “real-time” graphicsRendered without raytracingRendered with raytracingSlide 9Slide 10Slide 11Slide 12Slide 13Constructing Ray Through a PixelSlide 15Slide 16Ray-Scene IntersectionRay-Sphere IntersectionSlide 19Slide 20Slide 21Ray-Triangle IntersectionRay-Plane IntersectionRay-Triangle Intersection IRay-Triangle Intersection IIRay-Triangle Intersection IIIOther Ray-Primitive IntersectionsSlide 28Slide 29Bounding VolumesBounding Volume Hierarchies IBounding Volume HierarchiesBounding Volume Hierarchies IIISlide 34Uniform GridSlide 36Slide 37Slide 38OctreeSlide 40Slide 41Binary Space Partition (BSP) TreeSlide 43Slide 44BSP DemoFirst game-based use of BSP treesOther AccelerationsAccelerationSummaryHeckbert’s business card ray tracerNext Time is Illumination!Ray CastingAaron BloomfieldCS 445: Introduction to GraphicsFall 200623D RenderingThe color of each pixel on the view planedepends on the radiance emanating from visible surfacesView planeEye positionSimplest methodis ray castingSimplest methodis ray castingRays throughview plane3Ray CastingFor each sample …Construct ray from eye position through view planeFind first surface intersected by ray through pixelCompute color sample based on surface radiance4Ray CastingFor each sample …Construct ray from eye position through view planeFind first surface intersected by ray through pixelCompute color sample based on surface radianceSamples on view planeEye positionRays throughview planeWHY?5Ray casting != Ray tracingRay casting does not handle reflectionsThese can be “faked” by environment mapsThis speeds up the algorithmRay tracing doesAnd is thus much slowerWe will generally be vague about the difference6Compare to “real-time” graphicsThe 3-D scene is “flattened” into a 2-D view planeRay tracing is MUCH slowerBut can handle reflections much betterSome examples on the next few slidesView planeEye position(focal point)7Rendered without raytracing8Rendered with raytracing9101112Ray CastingSimple implementation:Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = ConstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection(ray, scene);image[i][j] = GetColor(hit);}}return image;}Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = ConstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection(ray, scene);image[i][j] = GetColor(hit);}}return image;}13Ray CastingSimple implementation:Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = Co nstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection(ray, scene);image[i][j] = GetColor(hit);}}return image;}Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = Co nstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection(ray, scene);image[i][j] = GetColor(hit);}}return image;}14Constructing Ray Through a PixelrightbackUp directionP0towardsViewPlanePVRay: P = P0 + tVRay: P = P0 + tV15Constructing Ray Through a Pixel2D ExampledtowardsP0rightright = towards x up = frustum half-angled = distance to view planeP1 = P0 + d*towards – d*tan()*rightP2 = P0 + d*towards + d*tan()*rightP1P22*d*tan(PP = P1 + (i+ 0.5) /width * (P2 - P1) = P1 + (i+ 0.5) /width * 2*d*tan ()*rightV = (P - P0) / | P - P0 |VRay: P = P0 + tVRay: P = P0 + tV16Ray CastingSimple implementation:Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = ConstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection (ray, scene);image[i][j] = GetColor(hit);}}return image;}Image RayCast(Camera camera, Scene scene, int width, int height){Image image = new Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { Ray ray = ConstructRayThroughPixel(camera, i, j);Intersection hit = FindIntersection (ray, scene);image[i][j] = GetColor(hit);}}return image;}17Ray-Scene IntersectionIntersections with geometric primitivesSphereTriangleGroups of primitives (scene)Acceleration techniquesBounding volume hierarchiesSpatial partitionsUniform gridsOctreesBSP trees18Ray-Sphere IntersectionRay: P = P0 + tVSphere: |P - C|2 - r 2 = 0 P0VCPrP’19Ray-Sphere IntersectionRay: P = P0 + tVSphere: (x - cx)2 + (y - cy)2 + (z - cz)2 = r 2 |P - C|2 - r 2 = 0 Substituting for P, we get:|P0 + tV - C|2 - r 2 = 0 Solve quadratic equation: at2 + bt + c = 0where:a = |V|2 = 1b = 2 V • (P0 - C) c = |P0 - C|2 - r 2P = P0 + tVP0VCPrP’If ray direction is normalized!20Ray-Sphere IntersectionP0VCPrN = (P - C) / |P - C|NNeed normal vector at intersection for lighting calculations21Ray-Scene IntersectionIntersections with geometric primitivesSphere»TriangleGroups of primitives (scene)Acceleration techniquesBounding volume hierarchiesSpatial partitionsUniform gridsOctreesBSP trees22Ray-Triangle IntersectionFirst, intersect ray with planeThen, check if point is inside trianglePP0V23Ray-Plane IntersectionRay: P = P0 + tVPlane: ax + by + cz + d = 0 P • N + d = 0Substituting for P, we get:(P0 + tV) • N + d = 0Solution: t = -(P0 • N + d) / (V • N)P = P0 + tVNPP0V24Ray-Triangle Intersection ICheck if point is inside triangle geometricallyFirst, find ray intersection point on plane defined by triangleAxB will point in the opposite direction from CxBPT1T2T3P’ABCSameSide(p1,p2, a,b): cp1 = Cross (b-a, p1-a) cp2 = Cross (b-a, p2-a) return Dot (cp1, cp2) >= 0 PointInTriangle(p, t1, t2, t3): return SameSide(p, t1, t2, t3) and SameSide(p, t2, t1, t3) and SameSide(p, t3, t1, t2)25SameSide(p1,p2, a,b): cp1 = Cross (b-a, p1-a) cp2 = Cross (b-a, p2-a) return Dot (cp1, cp2) >= 0 PointInTriangle(p, t1, t2, t3): return SameSide(p,
View Full Document
Unlocking...