Axis-aligned bounds of implicit formula ellipses

The original paper on Elliptical Weighted Averaging (EWA), named “Creating Raster Omnimax Images from Multiple Perspective Views Using the Elliptical Weighted Average Filter”, contrary to its title, is compact thanks to its straightforward pseudocode.

It leaves one particularly relevant detail out: How do you calculate the axis-aligned bounding box from the implicit equation for an ellipse?

The equation in question:
Ax^2 + Bxy + Cy^2 = F^2

Here’s an interactive graph illustrating the sphere and the bounds:

Since this yields a continuous curve, the bounds will be where derivatives are 0 with respect to your free variable of choice (x or y).

Differentiating over x yields: 2Ax + By = 0
Which can be rewritten as: x=-By/(2A)

This produces a line through the origin that intersects the Y extremes of the ellipse. We can solve that intersection for y by substituting our definition of x from above:

A(-By/(2A))^2 + B(-By/(2A))y + Cy^2 = F^2

Solving for y yields: y = +-sqrt(F^2/(C-B^2/(4A)))

Since the implicit equation is symmetric it suffices to swap x with y and A with C to yield:
x =+=sqrt(F^2/(A-B^2/(4C)))

This gives us our desired bounds.

In the paper values A, B, C, and F are themselves computed from a Jacobian matrix. Unfortunately the radicals encompass the meat of the bounds formulas which makes it difficult to simplify them away. However, if you’re dealing with modern x86 architectures and MSVC compilers sqrt() can be performed fairly cheaply. (And don’t forget to enable AVX or AVX2 support!)

Leave a Reply

Your email address will not be published. Required fields are marked *