1Ray CastingTom FunkhouserPrinceton UniversityCOS 426, Spring 20063D 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 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 planeRay 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 = 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;}2Constructing Ray Through a PixelrightbackUp directionP0towardsViewPlanePVRay: P = P0+ tVRay: 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)V = (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 = 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 - O|2- r 2 = 0 P0VOPrP’Ray-Sphere Intersection IRay: P = P0+ tVSphere: |P - O|2- r 2 = 0 Substituting for P, we get:|P0+ tV - O|2- r 2 = 0 Solve quadratic equation: at2+ bt + c = 0where:a = 1b = 2 V • (P0- O) c = |P0- C|2- r 2 = 0 P0VOPrP’Algebraic MethodAlgebraic MethodP = P0+ tV3Ray-Sphere Intersection IIRay: P = P0+ tVSphere: |P - O|2- r 2 = 0 L = O - P0tca= L • Vif (tca< 0) return 0d2= L • L - tca2if (d2> r2) return 0thc= sqrt(r2- d2)t = tca- thc and tca+ thcP0VOPrP’rdthctcaLGeometric MethodGeometric MethodP = P0+ tVRay-Sphere IntersectionP0VOPrN = (P - O) / ||P - O||N• Need normal vector at intersection for 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)NPP0VAlgebraic MethodAlgebraic MethodP = P0+ tVRay-Triangle Intersection I• Check if point is inside triangle algebraicallyPP0N1T1T2T3V2V1For each side of triangleV1 = T1 - PV2 = T2 - PN1 = V2 x V1Normalize N1if ((P - P0) • N1< 0)return FALSE;end4Ray-Triangle Intersection II• Check if point is inside triangle parametricallyPP0Compute “barycentric coordinates” α, β:α = Area(T1T2P) / Area(T1T2T3)β = Area(T1PT3) / Area(T1T2T3)Area(T1T2T3) = 1/2(T2-T1) x (T3-T1)Check if point inside triangle.0 ≤ α ≤ 1 and 0 ≤ β ≤ 1α + β ≤ 1VαβT1T2T31−α−βOther 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 first5Bounding Volumes• Check for intersection with simple shape first If ray doesn’t intersect bounding volume, then it doesn’t intersect its contentsBounding Volumes• Check for intersection with simple shape first If ray doesn’t intersect bounding volume, then it doesn’t intersect its contents If found another hit closer than
View Full Document
Unlocking...