Raycasting

Raycasting

Raycasting is used in computational geometry and is much simpler than Raytracing.

Raycasting in 2D shoots a ray from a point to see which edges it intersects.

Similar to in Raytracing, we have a ray of origin $o\in {\mathbb{R}}^2$ with a direction $d\in {\mathbb{R}}^2$ (which has parametric form $r(t)=o+td$).

We cast rays because they help us answer geometric questions like:

• Does a point lie inside a polygon
• Does a shape intersect the polygon edge
• Where does the ray hit the polygon boundary
• What are the interior spans of a polygon?

The Algorithm

In general, given a ray $r(t)$, and a list of polygon edges. We want to know which segments the ray intersects.

1. Solve the intersection between the ray and line segment for each polygon edge
2. Discard intersections behind the ray origin and intersections outside the segment bounds
3. Collect valid intersection points
4. Sort by distance from ray origin Now we would have a list of boundary crossings.

Point-in-Polygon

The fundamental rule here is…

• If a ray crosses the polygon boundary an odd amount of times, it is inside the polygon
• If a ray crosses the polygon boundary an even amount of times, it is outside the polygon

For example if we have a polygon…

y=1:     ######  
y=2:     #    #
y=3:     #    #
y=4:     ######  

and we drop a ray into x=5…

y=0:   |
y=1:   | hits boundary (top edge)
y=2:   | inside
y=3:   | inside
y=4:   | hits boundary (bottom edge)
y=5:   | outside

Mathematically, we are looking for t such that $R(t)=S(u)$ or such that a ray intersects a segment. A segment is defined as $S(u)=A+u(B-A)$ where $A=(x_1,y_1)$ and $B=(x_2,y_2)$.

• $r_x+t{d}_x=x_1+u(x_2-x_1)$
• $r_y+t{d}_y=y_1+u(y_2-y_1)$ We solve for t and u, if there is no solution, there is no intersection. If $u$ is not between $[0,1]$ there the ray intersects beyond the segment. We typically in most cases only care if a solution exists.

Double counting

If a vertical ray exactly hits a vertex where two horizontal edges or a horizontal and vertical edge meet, its easy to count that crossing twice. To fix this, we make the interval half-open on one side. $min(x_1,x_2)\le x_r<max(x_1,x_2)$

Interior Spans

We can expand this idea beyond a single point to as if a continuous interval is inside a polygon.
From here, we will know the valid x and y coordinates for row y, and column x.

We now know the interior span for column x=6 is $y=[1,4]$ or $minY[6]=1$ and $maxY[6]=4$.
We drop a ray at every column in the polygon to get the rest of our ranges.

This works because each column x is a slice of the polygon where the polygon interior is continuous inside the range.

Now that we have interior spans, we can take an arbitrary axis-aligned bounding box and check if that bounding box is within the polygon.

AABB

If we choose two arbitrary

A = (5,2)
B = (14,3)

and snag the bounds…

xmin = 5
xmax = 14
ymin = 2
ymax = 3

We want to check that for every x in our range…
$y_{min}\ge minY[x]\text{ AND }{y}_{max}\le ma{x}_y[x]$ which we know from our interior spans in the previous step. If this is always true, the entire rectangle is inside the polygon.