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