Computational Geometry

Computational Geometry
An Introduction (in 3D)

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

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

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.)

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.)

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

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.)

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.)

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.)

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