CSCE 441 Lecture 25

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

Intersecting Simple Surfaces

Infinite Planes

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

${\vec {n}}\cdot \left(x-o\right)=0$

Given a ray $L(t)=p+{\vec {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$

${\vec {n}}\cdot \left(p+{\vec {v}}\,t-o\right)\rightarrow t={\frac {n\cdot \left(o-p\right)}{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.

${\begin{vmatrix}N^{T}\\(P_{i}-X)^{T}(P_{i+1}-X)^{T}\end{vmatrix}}$

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 ${\vec {n}}$

• Start with $\theta =0$
• For each edge $(p_{1},p_{2})$: $\theta =\theta +{\frac {n\cdot \left((p_{1}-x)\times (p_{2}-x)\right)}{\left|(p_{1}-x)\times (p_{2}-x)\right|}}\,\cos ^{-1}{\left({\frac {\left(p_{1}-x\right)\cdot \left(p_{2}-x\right)}{\left|p_{1}-x\right|\,\left|p_{2}-x\right|}}\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}+b\,t+c=0$:

${\begin{aligned}a&={\vec {v}}\cdot {\vec {v}}\\b&=2{\vec {v}}\cdot \left(p-c\right)\\c&=\left(p-c\right)\cdot \left(p-c\right)\,r^{2}\end{aligned}}$

• 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 ${\vec {A}}$, and radius $r$

Given ray $L(t)$,

Perform orthogonal projection to plane defined by $C,{\vec {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.