Yesterday I posted a problem to math stack exchange that bothers me for a while now, and right after I've had a few exchanges on Twitter that inspired me to attempt a solution.

Basically, the problem is about a form of refined raytracing where we render a big list of convex 3D brushes (and I decided to start with Ellipsoids, since they're so useful) to the screen, without any precalculated accelleration structure. How does it work? Basically, if we had a way to figure out for a portion of the frustum whether it contained a brush, we could

1. Start with a very low resolution
2. Collect a list of ellipsoids contained in each tile, culling the ones not contained or fully occluded
3. Then subdivide each tile into smaller tiles and repeat
4. Until we hit per-pixel resolution, then we are done.

And this brings us to the problem: we want to solve for a tile on screen

1. Whether an ellipsoid arbitrarily parametrized in world space is overlapping this tile
2. What the near and far depth range of the overlapping portion is (important for culling)
3. Whether the ellipsoid covers the tile fully (occludes its background completely, also important for culling)
4. What the near and far depth range of the portion is that fully covers the tile (so we can also cull overlapping ellipsoids)

You see that the problem is analog to raytracing, but we are frustum tracing: instead of a ray, we extrude and expand a rectangle which forms a 4-sided open-faced pyramid in space, or simpler yet, four planes. The depth values that we are interested in are represented by planes parallel to the screen plane. These planes intersect in each corner of the rectangle to form lines. So the participants in this problem are:

• An ellipsoid
• Four wall planes of our frustum
• Four corner lines of our frustum
• A screen plane - whose positions we want to find (outer near/far, inner near/far)

Now the screen plane and the wall and corner planes are not necessarily arranged symmetrically and orthogonally, but can be skewed due to the position of the screen tile we are interested in. In the beginning, this sounds like an added complication, but it will be helpful that we don't have an invariant here that we might feel must be protected (and instead get another one that we will profit from)

Let's drop from 3D space to 2D space and attempt to solve the problem there. Now our ellipsoid is just an ellipse, and our frustum is simply a wedge formed by two lines originating from an eye point (analog to our four planes or four corner lines - here they collapse to the same thing) and a screen line (analog to our screen plane) arranged semi-orthogonally to the eye point.

The first thing we can do to considerably simplify the problem is to non-uniformly scale and rotate our problem space to turn the ellipsoid into a unit circle (analog to the 3D raytracing solution which does the same thing). This will skew our wedge further, but since it was already skewed to begin with, nothing really changed for us. This was the invariant I talked about earlier. Now we're solving the problem for a unit circle, and our wedge still is a wedge. We'll need to save our skew matrix for later so we can unskew our solution lines.

We end up with four possibly arrangements of circle and wedge:

• A circle that crosses both boundary lines - contained.
• A circle that crosses only one boundary line - contained.
• A circle that crosses no boundary line but is either left or right of both boundary lines - not contained.
• A circle that crosses no boundary line but is left of one line and right of the other - contained.

To resolve all these predicates we need two kinds of analytical equations, which are both readily available:

• A line / circe intersection test that gives us an entry and exit point (usually parametrized as center and width) if there is an intersection, and for any case tells us if the circle's center is left or right of the line.
• Given a line and a circle, compute a line parallel to the original line that bounds the circle.

With these two equations