CSCE 441 Lecture 25

« previous | Friday, March 21, 2014 | next »

Intersecting Simple Surfaces

Infinite Planes

Defined by a normal vector $\overrightarrow{n}$ and a point $o$ on the plane.

$\overrightarrow{n}\cdot (x-o)=0$

Given a ray $L(t)=p+\overrightarrow{v}t$, the intersection of the ray and the plane can be found by plugging in $x=L(t)$, solving for $t$, and plugging that solution back into $L$

$\overrightarrow{n}\cdot (p+\overrightarrow{v}t-o)\to t=\frac{n\cdot (o-p)}{n\cdot v}$

Note: if $n\cdot v=0$, then the ray and plane are parallel.

In raytracing, we only need the $t$ parameter and the normal at that intersection since only the smallest positive value of $t$ will be rendered, and the normal is used to calculate lighting/reflection, etc.

Polygons

• Intersect infinite plane containing polygon
• Determine if ponit is inside polygon

Point inside a convex polygon

Check if point is on same side of all planes formed from the edges.

$\left|\begin{array}{c}{N}^T\\ (P_i-X{)}^T(P_{i+1}-X{)}^T\end{array}\right|$

where $P_i$ and $P_{i+1}$ are consecutive points on the polygon.

Must be same sign

Ray Casting

Fire a ray from the point and count the number of intersections

• If the number of intersections is odd, then the point is inside the polygon
• If the number of intersections is even, then the point is outsie the polygon

Problems:

• Ray through vertex
• Ray parallel to (along) edge

Solution:

• Shoot a bunch of rays, and use them to "vote" whether you're inside or outside.

Better solution:

Winding numbers

Professor's dog's name is ALMONDS. Like all dogs, Almonds will run around a closed polygon, and if Dr. Schaefer is wrapped in the leash, then he is inside the polygon.

Requires oriented edges

Can be computed in any order.

Given unit normal $\overrightarrow{n}$

• Start with $\theta =0$
• For each edge $(p_1,p_2)$: $\theta =\theta +\frac{n\cdot ((p_1-x)\times (p_2-x))}{|(p_1-x)\times (p_2-x)|}{\cos }^{-1}\left(\frac{(p_1-x)\cdot (p_2-x)}{|p_1-x||p_2-x|}\right)$
• If $\left|\theta \right|>\pi$, then we are inside the polygon.

Advantages:

• Extends to 3D
• Numerically stable
• Even works on models with holes (sort of)
• No ray casting (or infinite amount of ray casting, depending on how you look at it)

Spheres

Three possible cases:

• no intersections: miss sphere entirely
• one intersection: tangent ray
• two intersections: hit sphere on front and back sides

How do we distinguish these cases?

Plug line definition into sphere definition, rearrange into quadratic equation $a{t}^2+bt+c=0$:

$\begin{array}{rl}a& =\overrightarrow{v}\cdot \overrightarrow{v}\\ b& =2\overrightarrow{v}\cdot (p-c)\\ c& =(p-c)\cdot (p-c)r^2\end{array}$

• if $b^2-4ac<0$, no intersection
• if $b^2-4ac=0$, one intersection
• if $b^2-4ac>0$, two intersections

Infinite Cylinders

Defined by center ponit $C$, a unit axis direction $\overrightarrow{A}$, and radius $r$

Given ray $L(t)$,

Perform orthogonal projection to plane defined by $C,\overrightarrow{A}$ on the line $L(t)$ and intersect with the circle of radius $r$ in 2D

Normal is radially outward from center (normal of circle) at intersection point.