1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2004Ray Casting3D Rendering• The color of each pixel on the view planedepends on the radiance emanating fromvisible surfacesView planeEye positionSimplest methodis ray castingRays throughview planeRay Casting• For each sample … Construct ray from eye position through view plane Find first surface intersected by ray through pixel Compute color sample based on surface radianceRay Casting• For each sample … Construct ray from eye position through view plane Find first surface intersected by ray through pixel Compute 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;}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;}2Constructing Ray Through a PixelrightbackUp directionP0towardsViewPlanePVRay: P = P0 + tVConstructing Ray Through a Pixel• 2D ExampledΘtowardsP0rightright = 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 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;}Ray-Scene Intersection• Intersections with geometric primitives Sphere Triangle Groups of primitives (scene)• Acceleration techniques Bounding volume hierarchies Spatial 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!3Ray-Sphere IntersectionP0VCPrN = (P - C) / ||P - C||N• Need normal vector at intersectionfor lighting calculationsRay-Scene Intersection• Intersections with geometric primitives Sphere» Triangle Groups of primitives (scene)• Acceleration techniques Bounding volume hierarchies Spatial 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 theopposite direction from CxB!SameSide(p1,p2, a,b): cp1 = Cross (b-a, p1-a) cp2 = Cross (b-a, p2-a) return Dot (cp1, cp2) >= 0PointInTriangle(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 ≤ β ≤ 1α + β ≤ 1VαβT1T2T34Other Ray-Primitive Intersections• Cone, cylinder, ellipsoid: Similar to sphere• Box Intersect 3 front-facing planes, return closest• Convex polygon Same as triangle (check point-in-polygon algebraically)• Concave polygon Same plane intersection More 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 primitives Sphere Triangle Groups of primitives (scene)» Acceleration techniques Bounding volume hierarchies Spatial partitions» Uniform grids» Octrees» BSP treesBounding Volumes• Check for intersection with simple shape firstBounding Volumes• Check for intersection with simple shape firstBounding Volumes• Check for intersection with simple shape first If ray doesn’t intersect bounding volume,then it doesn’t intersect its contents5Bounding Volumes• Check for intersection with simple shape first If ray doesn’t intersect bounding volume,then it doesn’t intersect its contentsStill need to check forintersections with shape.Bounding Volume Hierarchies I• Build hierarchy of bounding volumes Bounding volume of interior node contains all children12 3ABCDEF321A BE FDCBounding Volume Hierarchies• Use hierarchy to accelerate ray intersections Intersect node contents only if hit bounding volume12 3CA BE FDABCDEF32112A BC3Bounding Volume Hierarchies IIIFindIntersection(Ray ray, Node node){// Find intersections with child node bounding volumes...// Sort intersections front to back...// Process intersections (checking for early termination)min_t = infinity;for each intersected child i {if (min_t < bv_t[i]) break;shape_t = FindIntersection(ray, child);if (shape_t < min_t) { min_t = shape_t;}}return min_t;}• Sort hits & detect early terminationRay-Scene Intersection• Intersections with geometric primitives Sphere Triangle Groups of primitives (scene)» Acceleration techniques Bounding volume hierarchies Spatial partitions» Uniform grids» Octrees» BSP treesUniform Grid• Construct uniform grid over scene Index primitives according to overlaps with grid cellsABCDEF6Uniform Grid• Trace rays through grid cells Fast
View Full Document
Unlocking...