website articles
working with ellipses
Planar ellipses (I add "planar" to make it clear it's not a 3D ellipsoid) are constructed by a 3D position C in space and two perpendicular orientation vectors U and V that define both the plane where the ellipse lays and the size of the axes. So you can store a 3D ellipse in just 8 floats. In the case of the ellipse being degenerated to a disk, then a single orientation vector is needed (perpendicular to the plane containing the disk) and a radious (so, 6 floats). Planar ellipses can become very usefull for computer graphics. For example, they appear when you cut a cylinder with a plane. They also appear when rendering point clouds with a splatting algorithm, or when raytracing point clouds. They can also help in realtime ambient occlussion and indirect lighting computations, where occluders can be approximated by a pointcloud.

Here I will show how to do two of the most basic operations on planar ellipses: bounding box calculation and ray intersection (sounds like this is what you need for a fast kd-tree based raytracer, uh?). Let's see the bounding box first:

Bounding Box:

As we know any point in the ellipse boundary is described by the following parametric equation:

The bounding box of the ellipse has to be tangent to this boundary. This tangential points will be the maximun and minimun x, y and z coordinates of the boundary equation. So, we just have to find the minima/maxima of the equation. From elementary school we know that we can get them by finding where the derivative anulates. So,

must equal zero for each of the three coordinates. Let's rename first and solve for the x coordinate:

to get

meaning that

Sumarizing, we can calculate our bounding box corners like this:

Note that this is quite SIMD (SSE/Altivec) friendly, so you can do a single square root for the complete bounding box. Ready for building your acceleration kd-tree for point clouds?

Ray-ellipse intersection:

Similarly to the ellipse border, the interior can be defined by


where the equallity holds for the border. Now, if we define the ray with the equation

where ro is the ray origin and rd is the (not necessarilly normalized) ray direction, then we must make both expressions equal in order to get the intersection point, thus we must solve the equation that actually is a system of three equations (one for each of the x, y and z coordinates) with three unknowns. Re-arranging these three equations we get the following system:

We can solve this by Cremer's law:

Note that de will be zero when the ray is parallel to the plane containing the ellipse, so that needs special care. Of course, t corresponds to the ray-plane intersection distance. Finally, to test that the intersection point is in the ellipse, check for

As side effect, one can calculate exact bounding boxes for arbitrary finite cylinders by noting that the bounding box a a cylinder must contain and be tangent to the bounding boxes of it's caps, what is not a trivial thing to do a prori (see image below)...

I hope all this is helpful for somebody :)