Ray TracingRay CastingTraditional (Backwards) Ray TracingSceneScene GraphScene GraphRay CastingRay CastingRay CastingConstructing Ray Through a PixelConstructing Ray Through a PixelRay CastingRay CastingRay CastingRay IntersectionRay IntersectionRay-Sphere IntersectionRay-Sphere IntersectionRay-Sphere Intersection IRay-Sphere Intersection IIRay-Sphere IntersectionRay IntersectionRay-Triangle IntersectionRay-Triangle IntersectionRay-Plane IntersectionRay-Triangle Intersection IRay-Triangle Intersection IIRay-Triangle Intersection IIRay-Triangle Intersection IIIRay IntersectionRay-Box IntersectionRay-Box IntersectionRay-Box IntersectionRay-Box IntersectionOther Ray-Primitive IntersectionsRay IntersectionRay-Scene IntersectionRay-Scene IntersectionRay-Scene Intersection IRay-Scene IntersectionRay-Scene IntersectionRay-Scene Intersection IIRay-Scene Intersection IIRay IntersectionRay Intersection AccelerationBounding VolumesBounding VolumesBounding VolumesBounding VolumesBounding Volume HierarchiesBounding Volume HierarchiesBounding Volume HierarchiesSort Bounding Volume IntersectionsCache Node IntersectionsRay IntersectionUniform GridUniform GridUniform GridRay IntersectionOctreeOctreeOctreeRay IntersectionBinary Space Partition (BSP) TreeBinary Space Partition (BSP) TreeBinary Space Partition (BSP) TreeOther AccelerationsAccelerationSummaryHeckbert’s business card ray tracerNext Time is Illumination!Ray TracingCOS 426Ray Casting• Primitive operation for one class of renderers: Given a ray (origin, direction) Find point of first intersection with scene• May return: Whether intersection occurs Point of intersection (x,y,z) Parameters of intersection on object• Used for: Camera (primary) rays: backwards ray tracing Accumulate brightness from lights: forwards ray tracing Shadow rays Indirect illumination (path tracing)Traditional (Backwards) Ray Tracing• The color of each pixel on the view planedepends on the radiance emanating along rays from visible surfaces in sceneCameraLightSurfacesScene• Scene has: Scene graph with surface primitives Set of lights CameraCameraLightSurfacesstruct R3Scene {R3Node *root;vector<R3Light *> lights;R3Camera camera;R3Box bbox;R3Rgb background;R3Rgb ambient;};Scene Graph• Scene graph is hierarchy of nodes, each with: Bounding box (in node’s coordinate system) Transformation (4x4 matrix) Shape (mesh, sphere, … or null) Material (more on this later)Base[M1]Upper Arm[M2]Lower Arm[M3]• Simple scene graph implementation:Scene Graphstruct R3Node {struct R3Node *parent;vector<struct R3Node *> children;R3Shape *shape;R3Matrix transformation;R3Material *material;R3Box bbox;};struct R3Shape {R3ShapeType type;R3Box *box;R3Sphere *sphere;R3Cylinder *cylinder;R3Cone *cone;R3Mesh *mesh;};Ray Casting• For each sample (pixel) … Construct ray from eye position through view plane Compute radiance leaving first point of intersection between ray and sceneCameraLightSurfacesRay Casting• Simple implementation:R2Image *RayCast(R3Scene *scene, int width, int height){R2Image *image = new R2Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { R3Ray ray = ConstructRayThroughPixel(scene->camera, i, j);R3Rgb radiance = ComputeRadiance(scene, &ray);image->SetPixel(i, j, radiance);}}return image;}Ray Casting• Simple implementation:R2Image *RayCast(R3Scene *scene, int width, int height){R2Image *image = new R2Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { R3Ray ray = ConstructRayThroughPixel(scene->camera, i, j);R3Rgb radiance = ComputeRadiance(scene, &ray);image->SetPixel(i, j, radiance);}}return image;}Constructing Ray Through a PixelrightbackUp directionP0ViewPlanePVRay: 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 Casting• Simple implementation:R2Image *RayCast(R3Scene *scene, int width, int height){R2Image *image = new R2Image(width, height);for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { R3Ray ray = ConstructRayThroughPixel(scene->camera, i, j);R3Rgb radiance = ComputeRadiance(scene, &ray);image->SetPixel(i, j, radiance);}}return image;}Ray Casting• Simple implementation:R3Rgb ComputeRadiance(R3Scene *scene, R3Ray *ray){R3Intersection intersection = ComputeIntersection(scene, ray);return ComputeRadiance(scene, ray, intersection);}struct R3Intersection {bool hit;R3Node *node;R3Point position;R3Vector normal;double t;};CameraLightSurfacesRay Casting• Simple implementation:R3Rgb ComputeRadiance(R3Scene *scene, R3Ray *ray){R3Intersection intersection = ComputeIntersection(scene, ray);return ComputeRadiance(scene, ray, intersection);}struct R3Intersection {bool hit;R3Node *node;R3Point position;R3Vector normal;double t;};CameraLightSurfacesRay Intersection• Ray Intersection Sphere Triangle Box Scene• Ray Intersection Acceleration Bounding volumes Uniform grids Octrees BSP treesRay Intersection• Ray Intersection Sphere Triangle Box Scene• Ray Intersection Acceleration Bounding volumes Uniform grids Octrees BSP treesRay-Sphere IntersectionP0VOPrP’Ray-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 MethodP = P0+ tVRay-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 MethodP = P0+ tVRay-Sphere IntersectionP0VOPrN = (P - O) / ||P - O||N• Need normal vector at intersection for lighting calculationsRay Intersection• Ray Intersection Sphere Triangle Box Scene• Ray Intersection Acceleration Bounding volumes Uniform grids Octrees BSP treesRay-Triangle IntersectionPP0VRay-Triangle Intersection• First, intersect ray with plane• Then, check if intersection point is inside trianglePP0VRay-Plane IntersectionRay: P = P0+ tVPlane: P • N + d
View Full Document
Unlocking...