## The Halo Problem

I'd like to share with you an interesting problem I ran across when working a project for my graphics class.

In the class, we've been coding simple object rendering. We started with 2D, drawing simple colored polygons:

and then we allowed the user to clip said polygons:

And then we moved onto 3D! This started out with rendering simple wireframes, for instance of this torus:

We then implemented an improvement called "backface elimination" which improves rendering of some shapes, including this torus ...

... but only from certain angles ...

Then we actually filled in the polygons instead of just painting their wireframes:

Actually, I'm not sure where exactly this came in the timeline. It's not important.

Then we added lighting!

This is actually a slight lie: I accounted for intersections *before* doing lighting. But this order works better for the blog post.

The problem of how to allow for intersections like this is actually a bit subtle.

See, the naive rendering implementation is just to render objects back-to-front. Take a list of objects, sort it by distance to observer, and draw the objects, farthest-to-closest. In order to do the sort, we would call `qsort`

with a `comparator`

function which compares two object and tells `qsort`

which one should come before the other in the list.

This `comparator`

would look

... except written in C, not pseudo-JS.

```
function comparator(object1, object2) {
// Order by distance
let distance1 = distance_to_observer(object1);
let distance2 = distance_to_observer(object2);
if (distance1 > distance2) return PAINT_OBJECT1_FIRST;
if (distance2 > distance1) return PAINT_OBJECT2_FIRST;
return PAINT_EITHER_FIRST;
}
```

However, this cannot render any intersections, since each objects is rendered wholesale, one-at-a-time.

Instead, a better approach is to decompose all objects into their constituent polygons, collect them all in an aggregate list, sort *this* by distance to observer, and paint each *polygon* one-at-a-time. So that's what I did. The comparator looked the same as the previous one, but as a function of polygons instead of objects:

```
function comparator(poly1, poly2) {
// Order by distance
let distance1 = distance_to_observer(poly1);
let distance2 = distance_to_observer(poly2);
if (distance1 > distance2) return PAINT_POLY1_FIRST;
if (distance2 > distance1) return PAINT_POLY2_FIRST;
return PAINT_EITHER_FIRST;
}
```

And it worked great! (As is evident by the existence of the photo in which clipping is working correctly)

Now is where things start getting funky. See, the user was able to manipulate one object at a time with the keyboard. I visually cued which object was selected by changing the color of its wireframe:

but I wasn't happy with this (for a few reasons). Instead, I wanted to do something cooler: I wanted to draw a halo around whichever object was selected:

Looking at the above images, you may think I succeeded in doing so. And I did! Kind of. With those specific objects in those specific positions with those specific angles, the halos render correctly. In general, however, they don't. As it turns out, the problem of how to render these halos is quite tricky...

So how did I render the halos?

The pieces of the algorithm relevant to halo rendering are creating and sorting the list of polygons. Firstly, besides adding each polygon into an aggregate list like we were before, we also add extra polygons:

Another option is to dilate the object as a whole around its center; however, this has some issues. It would work perfectly on a sphere but wouldn't work as well on a torus: the inside of the torus would get no halo.

The question, then, is how *exactly* to sort the list of polygons. We want red behind purple, of course, but code demands we be more precise.

Another option is to paint all red polygons before all purple polygons, and otherwise paint by distance:

```
function comparator(poly1, poly2) {
// Place red before purple
if (is_red(poly1) && !is_red(poly2)) return PAINT_POLY1_FIRST;
if (is_red(poly2) && !is_red(poly1)) return PAINT_POLY2_FIRST;
// Otherwise, order by distance
let distance1 = distance_to_observer(poly1);
let distance2 = distance_to_observer(poly2);
if (distance1 > distance2) return PAINT_POLY1_FIRST;
if (distance2 > distance1) return PAINT_POLY2_FIRST;
return PAINT_EITHER_FIRST;
}
```

The issue with this is that it means that the halo is *never* painted on top of anything else. However, it is sometimes appropriate to paint the halo on top of other things. For instance, if a selected torus is entirely in front of a sphere, it would make sense for the halo to be painted on top of the sphere.

```
function comparator(poly1, poly2) {
// Order by distance
let distance1 = distance_to_observer(poly1);
let distance2 = distance_to_observer(poly2);
if (distance1 > distance2) return PAINT_POLY1_FIRST;
if (distance2 > distance1) return PAINT_POLY2_FIRST;
// If the same distance, for instance in the case of a pair
// of buddy red and purple polygons, paint the red polygon first
if (is_red(poly1) && !is_red(poly2)) return PAINT_POLY1_FIRST;
if (is_red(poly2) && !is_red(poly1)) return PAINT_POLY2_FIRST;
return PAINT_EITHER_FIRST;
}
```

...unfortunately, this doesn't work so well:

The issue is that since each red polygon is enlarged, it obscures all the purple polygons behind it. Thus, the only purple polygon you're able to see is the one in the very front.

Okay, let's try again. In order to avoid the previous problem, we'll place each red polygon behind *all* polygons from the focused model. Otherwise, we'll paint in order of decreasing distance, just as before:

```
function comparator(poly1, poly2) {
// If both polygons are from the focused model
/// (they can be either red or purple)
if (is_in_focused_polygon(poly1) && is_in_focused_polygon(poly2)) {
// Paint red polygons first
if (is_red(poly1) && !is_red(poly2)) return PAINT_POLY1_FIRST;
if (is_red(poly2) && !is_red(poly1)) return PAINT_POLY2_FIRST;
}
// Otherwise, order by distance
let distance1 = distance_to_observer(poly1);
let distance2 = distance_to_observer(poly2);
if (distance1 > distance2) return PAINT_POLY1_FIRST;
if (distance2 > distance1) return PAINT_POLY2_FIRST;
return PAINT_EITHER_FIRST;
}
```

Deviously, this one

In fact, it's the comparator function I used to generate the original "correct" halo images.

For instance, sometimes polygons render out-of-order or don't render at all, causing glitchy holes and red blotches on the torus:

Even weirder, I found a setup with a torus and a sphere in which the torus would render differently based on how the sphere was rotated:

So what the hell is going on?

Consider more weird behavior in which the apparent overlapping of two objects will depend on which object is selected:

In actuality, the sphere is clipping into the torus (as can be seen by the first image, where nothing is selected). However, I claim that the way `comparator`

is defined, I can prove that when the torus is selected, the leftmost polygon of the torus should be painted on top of the closest polygon of the sphere, despite it being further

Why is this so? The proof goes something like this:

- Assume the torus is selected.
- Note that
`comparator`

tells us to paint the rightmost red torus polygon before we paint the leftmost purple torus polygon—because they are in the same object,`comparator`

paints the red polygon before the purple polygon. - Now note that
`comparator`

tells us to paint the closest sphere polygon before we paint the rightmost red torus polygon—since they are from different objects,`comparator`

compares their distances, and the sphere polygon is further than the torus polygon. - Thus,
`comparator`

has told us that (1) the sphere polygon should be painted before the red torus polygon, and (2) the red torus polygon should be painted before the purple torus polygon. We conclude, then, that the sphere polygon should be painted before the purple torus polygon.

In this manner, we can show that, according to `comparator`

, if the torus is selected, then the leftmost purple torus polygon *is*, visually, in front of the sphere. We can repeat a similar proof for *all* the polygons on the left side of the torus, and thus show that, visually, the torus is entirely in front of the sphere.

Likewise, when the sphere is selected, we are able to do similar proofs for its polygons, showing that the sphere is visually on top of the torus.

I conjecture that `qsort`

is doing

Note we can also prove that the sphere polygon should be painted before the purple polygon, since they are from different polygons and the sphere polygon is further than the purple polygon. Thus, the sphere polygon should be painted before the torus polygon, but also, as we have already shown, the torus polygon should be painted before the sphere polygon. Impossible!

I think (but have not proven) that you can (constructively, without use of LEM) prove, for any two polygons $a$ and $b$, that $a$ should be painted before $b$.

The issue is that we're treating `comparator`

as something it isn't. In particular, in our proof we assume the transitivity of `comparator`

—that if it places $a$ before $b$ in the paint order, and placed $b$ before $c$, then it will also place $a$ before $c$. But this simply isn't true! (as shown by the fact that using transitivity leads to contradictions)

This corresponds to the `qsort`

expects `comparator`

to represent a total ordering—i.e., be sufficiently nice and sufficiently self-consistent in certain ways, such as transitivity—but the `comparator`

we wrote does not represent a total ordering.

I actually haven't verified this, but I can't imagine that it isn't true.

So how did I fix `comparator`

? Well, I didn't! I'm still not sure about a good solution to this issue. If you have any ideas, let me know! I hope you thought this was as interesting as I did!