AcademySoftwareFoundation / AcademySoftwareFoundation/Imath
OpenTimelineIO needs "exclusive" math for Imath::Box
- Dominant language
- C++
- Stars
- 488
- Forks
- 161
- Avg merge
- 1d 3h
- Merged PRs (30d)
- 3
Description
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
3) `intersects()` be marked deprecated.
4) `has_extent()` be introduced to replace `isEmpty()` and `hasVolume()`, `extent` being preferred because it is a word that also applies to one dimensional entities.
5) `size()` be annotated to indicate that if a box is considered inclusive, it is up to the end user to add an epsilon
6) `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.
Contributor guide
Research direction
Start by reviewing the Imath::Box API, especially isEmpty(), hasVolume(), size(), and intersects(), and compare their documented behavior with the inclusive and exclusive bounds described here. Done would require an agreed design and corresponding API changes, including deprecations and replacements, but no files or tests are identified in the issue.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- computer-graphics
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100