Ray Casting IILast Time?Explicit vs. Implicit?Assignment 1: Ray CastingObject-Oriented DesignGraphics TextbooksLinear Algebra Review SessionQuestions?Overview of TodayRay-Box IntersectionNaïve Ray-Box IntersectionReducing Total ComputationTest if ParallelFind Intersections Per DimensionMaintain tnear & tfarIs there an Intersection?Is the Box Behind the Eyepoint?Return the Correct IntersectionRay-Box Intersection SummaryEfficiency IssuesSlide 21Slide 22Ray-Polygon IntersectionPoint Inside/Outside PolygonPrecision IssueWinding NumberAlternative DefinitionHow Do We Project into 2D?Slide 29Slide 30Ray-Triangle IntersectionBarycentric Definition of a PlaneBarycentric Definition of a TriangleHow Do We Compute a, b, g ?Intuition Behind Area FormulaSimplifyIntersection with Barycentric TriangleSlide 38Cramer’s RuleAdvantages of Barycentric IntersectionSlide 41Slide 42Triangle Meshes (.obj)Acquiring GeometryPrecisionThe evil eThe evil e: a hint of nightmareConstructive Solid Geometry (CSG)For example:How can we implement CSG?Collect all the intersectionsImplementing CSGEarly CSG Raytraced ImageSlide 54Next week: TransformationsMIT EECS 6.837, Cutler and Durand 1Ray Casting IIMIT EECS 6.837, Cutler and Durand 2Last Time?•Ray Casting / Tracing•Orthographic Camera •Ray Representation –P(t) = origin + t * direction•Ray-Sphere Intersection•Ray-Plane Intersection•Implicit vs. Explicit RepresentationsMIT EECS 6.837, Cutler and Durand 3Explicit vs. Implicit?•Explicit–Parametric–Generates points–Hard to verify that a point is on the object •Implicit–Solution of an equation–Does not generate points–Verifies that a point is on the objectMIT EECS 6.837, Cutler and Durand 4Assignment 1: Ray Casting•Write a basic ray caster–Orthographic camera–Sphere Intersection–Main loop rendering–2 Display modes: color and distance•We provide:–Ray (origin, direction) –Hit (t, Material)–Scene ParsingMIT EECS 6.837, Cutler and Durand 5Object-Oriented Design•We want to be able to add primitives easily–Inheritance and virtual methods•Even the scene is derived from Object3D!Object3Dbool intersect(Ray, Hit, tmin)Planebool intersect(Ray, Hit, tmin)Spherebool intersect(Ray, Hit, tmin)Trianglebool intersect(Ray, Hit, tmin)Groupbool intersect(Ray, Hit, tmin)MIT EECS 6.837, Cutler and Durand 6Graphics Textbooks•Recommended for 6.837:Peter Shirley Fundamentals of Computer GraphicsAK Peters•Ray TracingMIT EECS 6.837, Cutler and Durand 7Linear Algebra Review Session•Monday Sept. 20 (this Monday!)•Room 2-105 (we hope)•7:30 – 9 PMMIT EECS 6.837, Cutler and Durand 8Questions? Image by Henrik Wann JensenMIT EECS 6.837, Cutler and Durand 9Overview of Today•Ray-Box Intersection•Ray-Polygon Intersection •Ray-Triangle Intersection•Ray-Bunny Intersection& extra topics…MIT EECS 6.837, Cutler and Durand 10Ray-Box Intersection•Axis-aligned•Box: (X1, Y1, Z1) → (X2, Y2, Z2)•Ray: P(t) = Ro + tRdy=Y2y=Y1x=X1x=X2RoRdMIT EECS 6.837, Cutler and Durand 11Naïve Ray-Box Intersection•6 plane equations: compute all intersections•Return closest intersection inside the box–Verify intersections are on the correct side of each plane: Ax+By+Cz+D < 0 y=Y2y=Y1x=X1x=X2RoRdMIT EECS 6.837, Cutler and Durand 12Reducing Total Computation•Pairs of planes have the same normal•Normals have only one non-0 component•Do computations one dimension at a timey=Y2y=Y1x=X1x=X2RoRdMIT EECS 6.837, Cutler and Durand 13Test if Parallel•If Rdx = 0 (ray is parallel) AND Rox < X1 or Rox > X2 → no intersectiony=Y2y=Y1x=X1x=X2RoRdMIT EECS 6.837, Cutler and Durand 14Find Intersections Per Dimension•Calculate intersection distance t1 and t2–t1 = (X1 - Rox) / Rdx–t2 = (X2 - Rox) / Rdxt1t2RoRdy=Y2y=Y1x=X1x=X2MIT EECS 6.837, Cutler and Durand 15Maintain tnear & tfar•Closest & farthest intersections on the object–If t1 > tnear, tnear = t1–If t2 < tfar, tfar = t2tneartfary=Y2y=Y1x=X1x=X2t1t2MIT EECS 6.837, Cutler and Durand 16Is there an Intersection?•If tnear > tfar → box is missedtneartfary=Y2y=Y1x=X1x=X2MIT EECS 6.837, Cutler and Durand 17Is the Box Behind the Eyepoint?•If tfar < tmin → box is behindtneartfary=Y2y=Y1x=X1x=X2MIT EECS 6.837, Cutler and Durand 18Return the Correct Intersection•If tnear > tmin → closest intersection at tnear•Else → closest intersection at tfartneartfary=Y2y=Y1x=X1x=X2MIT EECS 6.837, Cutler and Durand 19Ray-Box Intersection Summary•For each dimension, –If Rdx = 0 (ray is parallel) AND Rox < X1 or Rox > X2 → no intersection•For each dimension, calculate intersection distances t1 and t2–t1 = (X1 - Rox) / Rdx t2 = (X2 - Rox) / Rdx–If t1 > t2, swap–Maintain tnear and tfar (closest & farthest intersections so far) –If t1 > tnear, tnear = t1 If t2 < tfar, tfar = t2•If tnear > tfar → box is missed•If tfar < tmin → box is behind•If tnear > tmin → closest intersection at tnear•Else → closest intersection at tfarMIT EECS 6.837, Cutler and Durand 20Efficiency Issues•1/Rdx, 1/Rdy and 1/Rdz can be pre-computed and shared for many boxes•Unroll the loop–Loops are costly (because of termination if)–Avoid the tnear & tfar comparison for first dimensionMIT EECS 6.837, Cutler and Durand 21Questions? Image by Henrik Wann JensenMIT EECS 6.837, Cutler and Durand 22Overview of Today•Ray-Box Intersection•Ray-Polygon Intersection •Ray-Triangle Intersection•Ray-Bunny Intersection & extra topics…MIT EECS 6.837, Cutler and Durand 23Ray-Polygon Intersection•Ray-plane intersection•Test if intersection is in the polygon–Solve in the 2D planeMIT EECS 6.837, Cutler and Durand 24Point Inside/Outside Polygon•Ray intersection definition:–Cast a ray in any direction •(axis-aligned is smarter)–Count intersections–If odd number, point is inside•Works for concave and star-shapedMIT EECS 6.837, Cutler and Durand 25Precision Issue•What if we intersect a vertex?–We might wrongly count an intersection for exactly one adjacent edge•Decide that the vertex is always above the rayMIT EECS 6.837, Cutler and Durand 26Winding Number•To solve problem with star pentagon:–Oriented edges–Signed count of intersections–Outside if 0 intersections+ -+-MIT EECS 6.837, Cutler and Durand 27Alternative Definition•Sum of the signed angles from point to edges±360°, ± 720°, … → point is inside 0° → point is outsideMIT
View Full Document
Unlocking...