[css-shapes] Specify algorithms for computing line-box intrusion into float's margin box.

[bfgeek]

If we want interop on css-shapes the specification needs to define given an exclusion with shape-outside defined, how far can a line-box intrude into that float. E.g. something like:

shape.intrusionSize(line_position_relative_to_shape, line_height, left_or_right);

[astearns]

@bfgeek CSS2 just says that "line boxes are shortened" - you're looking for a more precise definition of this?

You mentioned on today's call that you looked at Gecko's code and saw that it pretty much matched Blink's. I'm assuming whatever we define should be useful for both regular floats and floats with shape-outside.

Right now, the shapes spec says "line boxes next to a float are shortened as necessary to avoid intersections with the float area" - is this wrong, or just imprecise? How would you change this?

[bfgeek]

Basically because of subtle implementation differences, we'll end up with implementations that mostly match, but that get edges cases wrong. (see history of CSS2 :P).

This is mozilla's entry point for the above algorithm:
https://dxr.mozilla.org/mozilla-central/source/layout/generic/nsFloatManager.cpp?q=%2Bfunction%3A%22nsFloatManager%3A%3AShapeInfo%3A%3ALineEdge%28const+nsTArray%3CnsRect%3E+%26%2C+const+nscoord%2C+const+nscoord%2C+bool%29%22&redirect_type=single#541
... and this is blink's
https://cs.chromium.org/chromium/src/third_party/blink/renderer/core/layout/shapes/shape.h?sq=package:chromium&g=0&l=92

This algorithm I'm after is you have some float, for a given line-box, how far into that shape can I go?

The algorithms in the implementations are similar, but not exactly the same. E.g. they apply shape-margins at different stages (probably leading to different results), testing intersection with images looks like they'll behave differently, etc.

I realize this is a lot of work to write down, and make sure all the edge cases work correctly, but this will mean that implementations can work towards what's in the specification, and another implementation will be able to easily implement without spending many engineering hours coming up with similar (but perhaps subtlety different algorithms).

If we write down these algorithms, it'll be easy to find answers to the questions on the call such as what happens when polygons create -ve area, etc, and easy for implementations to implement the desired behaviour.

[astearns]

you have some float, for a given line-box, how far into that shape can I go?

My naive answer is "you can't" - the line box and the float area cannot intersect.

We will definitely need to spec how the shape and shape-margin build up the float area in point, line and inverted area cases. I'm not clear what we need to spec for a particular float area and line box beyond "don't intersect."

[bfgeek]

Sorry that sentence should be "how far into the float's margin box can I go, e.g. based on the shape area".

If we don't have an algorithm for this then different implementations will add/subtract things at different stages, causing different behaviour when things saturate. Additionally "don't intersect" isn't enough; a valid implementation then would be to simply position line-boxes based on a bounding-rect of the shape area. Defining an algorithm for above, while a lot of work, will ensure that implementations have exactly the same behaviour, and less work for future/current implementations looking to implement the spec correctly.

[tabatkins]

What Ian's trying to say is that the precise algorithm for computing an inflated/deflated shape (due to shape-margin) aren't written into the spec, and they're non-trivial to figure out correctly. It would help a lot to produce these.

(For example, is it correct to handle ellipse() by just growing/shrinking the axises? That does not produce the same thing as "the shape obtained by adding all points X distance away from the edge", which isn't an ellipse any longer.)

[astearns]

I don't see how one could conclude from the spec that growing/shrinking the axes of an ellipse would be an appropriate way to apply shape-margin. The shape-margin definition doesn't allow it. And there's an example of applying positive shape-margin to a polygon that shows that the resulting shape is no longer a polygon.

We can definitely add more precise wording than "don't intersect," but I don't think we're going to be able to get precise enough to (for instance) guarantee that implementations are going to achieve the same line breaks.

[tabatkins]

Why not, tho? I don't see a particular reason why we need to allow differences in the result here, beyond trivial things like rounding?

SVG implementations already have solutions for computing the desired shapes (just take the implementation of the stroking algorithm, with round linejoins), which we can specify with more detail in the spec.

What's still needed beyond that is an explanation of how to find how far into the shape's bounding rect a linebox can penetrate without intersecting the shape. There are algorithms in the literature for doing this sort of line-sweep collision-finding for physics engines, but saying "it's defined in the literature, good luck!" isn't a very nice thing to do to implementors. (I tried that with something for gradients, and @SimonSapin made me actually define it. ^_^)

A naive approach that doesn't work, for example, is to find where the top and bottom edges of the linebox would hit the shape, and use the one that's further out - this ignores the possibility of a "spike" between the two edges that should push the linebox even further. The actual efficient algorithm isn't particularly easy to puzzle out!

[AmeliaBR]

To summarize:

There are two algorithms that are imprecise:

• How to expand a shape by a given margin. For definitions, you may want to look at the SVG stroke-shape algorithms, but beware that this is an "outside" stroke which isn't yet explicitly defined in SVG (although it's an outside stroke on an always-closed shape, so that helps). See https://svgwg.org/specs/strokes/

  That said, shape-outside also needs to apply to shapes generated by the opacity threshold on an image, so the definition needs to work even if you don't have a crisp mathematical definition of the shape.

• Given a final shape (with margin included), how do you trim line boxes to fit up against it? E.g., in the diagram in Example 7 in the spec, it looks like the corners of the 1em-high basic line boxes are fitted tight against the final float shape, but expansions of the line box from line leading is ignored. Now, that's probably just a matter of making a nice diagram rather than a conscious choice. But when writing the code, you need to know whether you need to leave space for the half-leading on either side of the line of text.

  And as Tab points out, then there's the question of how to find the intersection point of a rectangle and an arbitrary shape (which may not have a mathematical definition) in an algorithmically efficient way. Especially when you factor in that each rectangle has a minimum content width associated with it, and that you may need to slide the rectangle down until you find a place where it can fit.

Given that neither of these calculations have crisp, clear algorithms for finding the optimal solution, I'd be hesitant about baking a full algorithm into the spec. But I do agree that there should probably be some clarifications.

[astearns]

We definitely should be able to get to the point where implementations agree on the available geometry for line boxes.

What they do within those line boxes isn't well-specified enough to guarantee identical line breaks, though (we don't guarantee identical line breaks within simple rectangles!). And as @AmeliaBR points out part of the algorithm for determining where line boxes go depends on the content width, so if there are different line breaks then it's possible implementations will differ in line box placement next to floats.

But I'm all for adding more details on how implementations should process float areas and line boxes so we can get as close as we can.

[tabatkins]

Oh yeah, actual line-breaking within the boxes is an unrelated thing we don't have to worry about.

Given that neither of these calculations have crisp, clear algorithms for finding the optimal solution, I'd be hesitant about baking a full algorithm into the spec.

If we bake an algo into the spec, and later find a more optimal version that gives slightly different results, we can either decide the compat isn't bad and update the spec, or decide the compat is too bad and stick with our old algo.

If we don't bake an algo into the spec, implementations will still choose some algorithm for now. If they later find a more optimal version, they'll also either decide they can or can't update, based on compat pain.

So the two situations are identical here, and there's no existing platform compat or similar UA-varying constraints making it more attractive to leave it up to quality-of-implementation, so there's no reason to not specify an algorithm.

[SimonSapin]

There is precedent in box-shadow of mentioning an algorithm in the spec, not to require it but to require something "close enough" to it:

https://drafts.csswg.org/css-backgrounds/#shadow-blur

The exact algorithm is not defined; however the resulting shadow must approximate (with each pixel being within 5% of its expected value) the image that would be generated by applying to the shadow a Gaussian blur with a standard deviation equal to half the blur radius

[tabatkins]

That one was because there is legit visible differences between blur implementations, but also significant cost differences, but aside from looking slightly prettier/uglier the different algos didn't affect the rest of the page, so it was okay to just give reasonable bounds and let UAs do whatever.

That's not the case here, as the algo you use affect the geometry of the element, and can have significant effects in how things are laid out - whether a line is allowed to go between two parts of a disjoint shape from an image (especially when the gap approaches the size of the linebox), for example, is a pretty big and significant difference that authors will care about.

[astearns]

On @AmeliaBR's first point, I think there's enough in the spec to go by. It defines the result, not the algorithm to achieve it, but the result is well-defined and testable.

The shape-margin property adds a margin to a shape-outside. This defines a new shape that is the smallest contour (in the shrink-wrap sense) that includes all the points that are the shape-margin distance outward in the perpendicular direction from a point on the underlying shape. Note that at points where a perpendicular is not defined (e.g. sharp points) take all points on the circle centered at the point and with a radius of shape-margin.

All implementations appear to be interoperable with the "circle around the sharp point" definition in this test: https://codepen.io/astearns/pen/abbmLPv

I do need to add how you need to determine the shape (including shape-margin) first, then deal with box intersections. So I'm leaving this issue open until I've gotten that done.