OpenTimelineIO needs "exclusive" math for Imath::Box

[meshula]

OpenTimelineIO is moving to use Imath for it's math computations and math representations. OTIO has a requirement to be able to specify a covering for the plane that is unique in a continuous domain. In other words, given a bound from (0, 1), and another from (1, 2), OTIO requires that a sample at the value 1 falls strictly into one bound or the other, in particular, it should fall into the bound (1,2) and not into (0, 1).

Alvy Ray Smith, in the influential “A Pixel is not a Little Square” (http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf) defines a pixel bound as {(x, y) | 0. ≤ x ≤ W/H, 0 .≤ y ≤ 1.} Throughout this work he is referring to a sampling bound, not a spatial bound. Furthermore, in the section entitled "What is a Discrete to Continuous Mapping that Works?" he propagates this usage to state that any region is inclusive on all edges.

Imath continues in this vein, treating boxes as sampling domains, with inclusive boundaries. This makes sense, from a certain point of view.

In Ray-Smith's convention, a region that is 640x480 pixels would be described by the box, ((0,0), (639, 479)). Imath routines, such as intersects in fact expect this, as they involve equality in the tests. Several routines within Imath::Box are nonetheless inconsistent with this interpretation.

For example, size() returns max - min. In the case of (639. 479), inclusive, discretized for a pixel domain, size is (640, 480), which is not what the routine will return. In the case of (639. 479), with an exclusive edge in the increasing dimensions, size will return the expected value of (639, 479).

Another routine affected by this confusion is isEmpty which tests if max is less than min. This is an opinionated interpretation, that suggests implicitly that boxes are malformed, or possibly special signaling values if the bounds are ordered in a decreasing magnitude. This interpretation does not derive from Ray-Smith, but most likely reflects a pragmatic test related to some interval representation in Zeno (ILM's proprietary DCC). isEmpty() does not in fact test if a box is empty, which one might interpret intuitively on its name as being a box with nothing in it. In the exclusive and inclusive cases, a bound of ((639, 479), (639, 479)) should be considered empty.

This conclusion is in fact embodied at hasVolume() which was clearly introduced to support the strange nature of isEmpty().

On inspection, the rest of the API works properly in both inclusive and exclusive cases. I propose the following:

1. isEmpty() be marked deprecated 2) hasVolume() be marked deprecated
2. intersects() be marked deprecated.
3. has_extent() be introduced to replace isEmpty() and hasVolume(), extent being preferred because it is a word that also applies to one dimensional entities.
4. size() be annotated to indicate that if a box is considered inclusive, it is up to the end user to add an epsilon
5. intersects_inclusive() and intersects_exclsuive() be introduced to replace intersects(), the only difference between the two being whether a less than check is required at some places where currently a less than or equal check exists.

[lgritz]

Is your domain 1D or 2D? You say "covering for the plane" but all your examples are 1D.

The semantics of Box<> are inherently for discrete regions like labeled pixels, a little dicey for continuous domains, because of its notation that is unfortunately inclusive of the maximum.

Have you looked at Imath::Interval<>?

[meshula]

Thanks for reminding me of Interval, as the code is a minor variant of Box, the same issues are there. Interval has the same labeled pixel semantics.

We're using Box for a 2d domain, that's why I used Alvy's 640x480 examples to illustrate the point that Box (and Interval) are not consistently inclusive or exclusively bound.

An example of how we would use it in OpenTimelineIO would be:

there is a frame on a continuous domain, extending from (0, 0) to (1, 1). Within the frame there is a timed editorial effect, A, bounded by region (0.25, 0.25) to (0.5, 0.5), and another adjoining, B, from (0.5, 0.25) to (0.75, 0.5). Given a continuous domain, we wish to know if a position at (0.5, 0.3) belongs to A, or B. If the continuous region is open in the increasing dimension, the position unambiguously belongs to B. If the contiguous region is closed, it belongs to both. This isn't Alvy's "a pixel is not a square" problem, this is the continuous geometric problem before we get to the sampling theorem.

I realize that Box and Interval are written with discrete labeled pixels in mind. Nonetheless, nearly all of the code is valid for continuous intervals, aside from the functions I specifically name. My initial proposal therefore is to deprecate the few small cases that are explicitly named inclusive or exclusive, and replace them with explicitly inclusive or exclusive named variants.

Bear in mind that the goal here is to allow OTIO to eliminate its own math library in favor of Imath, and some clean up of Box and Interval are necessary for that, or we can't accomplish calculations we already do with our own types. Or, we could with extra functions on our side, and tell people to ignore the tempting functions in Box and Interval, because they don't satisfy our semantics, but that's basically gross.

As an alternative, I'd be happy to instead introduce a new class, perhaps named BoundingInterval<T> with new semantics and leave Box and Interval alone, although I think the proposal here is a lighter touch, since it doesn't change long standing behavior, just adds a little functionality, and renames some existing functionality so there's no hidden semantics.

A new class might be the better answer though, since it wouldn't carry the evolutionary baggage that led to the "inside out" empty function, and the hasVolume method, which exists on Interval as well. It would also allow us to migrate our algebraic formalisms around intervals to the new class, without needing to be concerned about the existing Box/Interval semantic.

A further advantage of a new class is that we could use modern C++ features to specialize BoundingInterval<T> on both scalar and vector values, as the language constraints that led to needing both a Box and an Interval have been resolved.

[lgritz]

I've always wished that Box used exclusive maximum. Maybe we need to make a better one.

[cary-ilm]

FWIW, I believe Box3f came first, and Box2i was modeled off of it, which is probably where the confusion set in. As a means of defining a region in 3D space, Box3f makes sense as is. I'd recommend a new class.