- Forward


Computational Geometry
An Introduction (in 3D)


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • In General:
    • We need to perform a variety of calculations involving 3D shapes like points, lines, line segments, triangles, polygons, and spheres
  • The Focus of This Lecture:
    • Spheres
    • Triangles
Ray-Sphere Intersection
Back Forward
  • Recall:
    • The implicit form of the boundary of a sphere is \(\{ \bs{p} \in \mathbb{R}^{3}: (\bs{p} - \bs{c}) \cdot (\bs{p} - \bs{c}) - r^2 = 0\}\)
    • The parametric form of a ray is \(\bs{p}(t) = \bs{o} + t \bs{d}\)
  • So:
    • The values of \(t\) that that yield points on the sphere satisfy \((\bs{o} + t \bs{d} - \bs{c}) \cdot (\bs{o} + t \bs{d} - \bs{c}) - r^2 = 0\)
Ray-Sphere Intersection (cont.)
Back Forward
  • Collecting Terms:
    • \([(\bs{d} \cdot \bs{d})t^2] + [2 \bs{d} \cdot (\bs{o} - \bs{c}) t] + [(\bs{o} - \bs{c}) \cdot (\bs{o} - \bs{c}) - r^2] = 0\)
  • An Observation:
    • This is a quadratic equation in \(t\)
Ray-Sphere Intersection (cont.)
Back Forward
  • Solving:
    • \( t = \frac{-\bs{d} \cdot (\bs{o} - \bs{c}) \pm \sqrt{[\bs{d} \cdot (\bs{o} - \bs{c})]^2 - (\bs{d} \cdot \bs{d}) [(\bs{o} - \bs{c}) \cdot (\bs{o} - \bs{c}) -r^2]}} {\bs{d} \cdot \bs{d}}\)
  • Interpretation:
    • If the discriminant (the term under the square root) is positive there are two intersections, if it is 0 there is one tangency, and if it is negative there are no intersections
  • The Normal:
    • \(2(\bs{p} - \bs{c})\)
Ray-Triangle Intersection
Back Forward
  • Recall:
    • The three (not colinear) vertices of a triangle \(\bs{r}, \bs{s}, \bs{r} \in \mathbb{R}^3\) define a plane with barycentric coordinates \(\bs{p}(\rho, \sigma, \tau) = \rho \bs{r} + \sigma \bs{s} + \tau \bs{t}\) in which \(\rho + \sigma + \tau = 1\)
  • Using the Paramters:
    • The point is in the interior if and only if all three parameters are in \((0, 1)\)
    • The point is on an edge if and only if two parameters are in \((0, 1)\) and one is 0
    • The point is a vertex if and only if one parameter is in \((0, 1)\) and two are 0
Ray-Triangle Intersection (cont.)
Back Forward
  • Simplifying:
    • Letting \(\rho = 1 - \sigma - \tau\)
      \(\bs{p}(\sigma, \tau) = \bs{r} + \sigma (\bs{s} - \bs{r}) + \tau (\bs{t} - \bs{r})\)
  • Intersection of the Ray and the Plane:
    • Substituting the parametric form of the ray, \(\bs{o} + t \bs{d}\), for \(\bs{p}\) yields:
      \(\bs{o} + t \bs{d} = \bs{r} + \sigma (\bs{s} - \bs{r}) + \tau (\bs{t} - \bs{r})\)
  • Using the Paramters:
    • The point is in the interior if and only if \(\sigma > 0\), \(\tau > 0\), and \((\sigma + \tau) \lt 1\)
Ray-Triangle Intersection (cont.)
Back Forward
  • Solving:
    • This is three linear equations in three unknowns (\(\sigma\), \(\tau\), and \(t\))
  • The Normal:
    • \((\bs{s} - \bs{r}) \times (\bs{t} - \bs{r})\)
Ray-Triangle Intersection (cont.)
Back Forward
  • Let:
    • \( \bs{M} = \begin{bmatrix} r_1 - s_1 & r_1 - t_1 & d_1 \\ r_2 - s_2 & r_2 - t_2 & d_2 \\ r_3 - s_3 & r_3 - t_3 & d_3 \\ \end{bmatrix} \)
  • The Solution:
    • \( \sigma = \frac{\left| \begin{bmatrix} r_1 - o_1 & r_1 - t_1 & d_1 \\ r_2 - o_2 & r_2 - t_2 & d_2 \\ r_3 - o_3 & r_3 - t_3 & d_3 \end{bmatrix} \right|}{|\bs{M}|} \)
    • \( \tau = \frac{\left| \begin{bmatrix} r_1 - s_1 & r_1 - o_1 & d_1 \\ r_2 - s_2 & r_2 - o_2 & d_2 \\ r_3 - s_3 & r_3 - o_3 & d_3 \end{bmatrix} \right|}{|\bs{M}|} \)
    • \( t = \frac{\left| \begin{bmatrix} r_1 - s_1 & r_1 - t_1 & r_1 - o_1 \\ r_2 - s_2 & r_2 - t_2 & r_2 - o_2\\ r_3 - s_3 & r_3 - t_3 & r_3 - o_3 \end{bmatrix} \right|}{|\bs{M}|} \)
  • An Observation:
    • There are many common subterms that only need to be calculated once
There's Always More to Learn
Back -