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:
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:
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?
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 :)