Ray Casting3D RenderingSlide 3Slide 4Slide 5Slide 6Constructing Ray Through a PixelSlide 8Slide 9Ray-Scene IntersectionRay-Sphere IntersectionSlide 12Slide 13Slide 14Ray-Triangle IntersectionRay-Plane IntersectionRay-Triangle Intersection IRay-Triangle Intersection IIOther Ray-Primitive IntersectionsSlide 20Slide 21Bounding VolumesSlide 23Slide 24Slide 25Bounding Volume Hierarchies IBounding Volume HierarchiesBounding Volume Hierarchies IIISlide 29Uniform GridSlide 31Slide 32Slide 33OctreeSlide 35Slide 36Binary Space Partition (BSP) TreeSlide 38Slide 39Slide 40Other AccelerationsAccelerationSummaryHeckbert’s business card ray tracerNext Time is Illumination!Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Ray CastingGreg HumphreysUniversity of VirginiaCS 445, Fall 20033D Rendering•The color of each pixel on the view planedepends on the radiance emanating from visible surfacesView planeEye positionSimplest methodis ray castingSimplest methodis ray castingRays throughview planeRay Casting•For each sample …Construct ray from eye position through view planeFind first surface intersected by ray through pixelCompute color sample based on surface radianceRay Casting•For 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?Ray Casting•Simple 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;}Ray Casting•Simple 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;}Constructing Ray Through a PixelrightbackUp directionP0towardsViewPlanePVRay: P = P0 + tVRay: P = P0 + tVConstructing Ray Through a Pixel•2D 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/width + 0.5) * (P2 - P1) = P1 + (i/width + 0.5) * 2*d*tan ()*rightV = (P - P0) / ||P - P0 ||VRay: P = P0 + tVRay: P = P0 + tVRay Casting•Simple 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 = FindIntersect ion(ray, scene);image[i][j] = GetColor(hit);}}return image;}Ray-Scene Intersection•Intersections with geometric primitivesSphereTriangleGroups of primitives (scene)•Acceleration techniquesBounding volume hierarchiesSpatial partitions»Uniform grids»Octrees»BSP treesRay-Sphere IntersectionRay: P = P0 + tVSphere: |P - C|2 - r 2 = 0 P0VCPrP’Ray-Sphere IntersectionRay: P = P0 + tVSphere: |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 2P0VCPrP’P = P0 + tVIf ray direction is normalized!Ray-Sphere IntersectionP0VCPrN = (P - C) / ||P - C||N•Need normal vector at intersection for lighting calculationsRay-Scene Intersection•Intersections with geometric primitivesSphere»TriangleGroups of primitives (scene)•Acceleration techniquesBounding volume hierarchiesSpatial partitions»Uniform grids»Octrees»BSP treesRay-Triangle Intersection•First, intersect ray with plane•Then, check if point is inside trianglePP0VRay-Plane IntersectionRay: P = P0 + tVPlane: P • N + d = 0Substituting for P, we get:(P0 + tV) • N + d = 0Solution: t = -(P0 • N + d) / (V • N)NPP0VP = P0 + tVRay-Triangle Intersection I•Check if point is inside triangle geometricallyPT1T2T3P’ABCAxB will point in the opposite direction from CxB!SameSide(p1,p2, a,b): cp1 = Cross (b-a, p1-a) cp2 = Cross (b-a, p2-a) return Dot (cp1, cp2) >= 0 PointInTriangle(p, a,b,c): return SameSide(p,a, b,c) and SameSide(p,b, a,c) and SameSide(p,c, a,b)Ray-Triangle Intersection II•Check if point is inside triangle parametricallyPP0Compute P = (T2-T1) + (T3-T1)Check if point inside triangle.0 1 and 0 1VT1T2T3Other Ray-Primitive Intersections•Cone, cylinder, ellipsoid:Similar to sphere•BoxIntersect 3 front-facing planes, return closest•Convex polygonSame as triangle (check point-in-polygon algebraically)•Concave polygonSame plane intersectionMore complex point-in-polygon testRay-Scene Intersection•Find intersection with front-most primitive in groupABCDEFIntersection FindIntersection(Ray ray, Scene scene) {min_t = infinitymin_primitive = NULLFor each primitive in scene {t = Intersect(ray, primitive);if (t > 0 && t < min_t) thenmin_primitive = primitivemin_t = t}}return Intersection(min_t, min_primitive)}Ray-Scene Intersection•Intersections with geometric primitivesSphereTriangleGroups of primitives (scene)»Acceleration
View Full Document
Unlocking...