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 useful 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 occlusion 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 maximum and minimum 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 annulates. So,


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

to get

meaning that


Summarizing, 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

and

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


where ro is the ray origin and rd is the (not necessarily 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 Cramer'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


I hope all this is helpful for somebody :)