rect::intersection can fail due to floating point precision

[mattwoodrow]

I have a testcase with tiling where we're calling rect::intersection with the following rects:

{20, 280.399994, 200, 256}
{20, 280.399994, 200, 256.000031}

The result ends up returning a width of 256.000031, not 256.

[kvark]

Dupe of #177 🤣

[mattwoodrow]

I tried working around it, and we just hit the exact same issue within webrender::image::tiles. Floats are a pain.

[nical]

So I had a look at Gecko's rect implementation and tried to rewrite euclid's the same way:

        if !self.intersects(other) {
            return None;
        }

        let x = max(self.min_x(), other.min_x());
        let y = max(self.min_y(), other.min_y());

        let w = min(
            self.min_x() - x + self.size.width,
            other.min_x() - x + other.size.width,
        );

        let h = min(
            self.min_y() - y + self.size.height,
            other.min_y() - y + other.size.height,
        );

        Some(rect(x, y, w, h))

The idea of having the exact same precision behavior as gecko is very appealing and it does address this particular test case, but gecko's implementation appears to rely on the number representation being signed. With this implementation self.min_x() - x is either zero or negative and we use unsigned integers with euclid in many places.

[nical]

Dupe of #177 rofl

Yeah that might be enough of a motivation to add the endpoint representation and move some of webrender's code over to it.

[mattwoodrow]

I tried the same thing!

The gecko expression is ordered weirdly, but you can write it more sanely as self.max_x() - x, and that avoids the underflow.

The effective difference is that current code is doing min() on the bottom-right points, and then converting the result to width/height. The gecko version computes the two lengths, and does min() on that.

[nical]

I went back to this and tried a few permutations. Even writing self.min_x() - x + self.size.width as self.max_x() - x exhibits the precision issue. What's happening in gecko's formuation for this particular test case is that self.min_x() and x are equal so the substraction doesn't lose precision.

min_x() - x has 50% chance of not losing precision since x is either self.min_x() or other.min_x() but it also has 50% chance of underflowing. Any other ordering of operations will be more likely to reduce precision but short of adding a branch we can't do it in a way that keeps the likelihood of preserving precisions without risking underflows.

Btw we are currently converting the rect into a box and doing the intersection in the endpoints form instead of the origin+size form of when this issue filed (the test case is still failing).

In my opinion the better solution is to avoid using Rect and use Box2D anywhere this type of precision issue matters. The precesion loss is happening when converting from Rect to Box2D but if the data is stored directly as a box, we only do min/max without addition/substraction so the precision is preserved.