[cairo] Polygon clipping problem

[Chris Wilson]

On Sat, 2009-02-14 at 09:19 -0500, cu wrote:
> Thank you for your reply in the bugzilla. I understand the problem now.
> 
> I decided to play a bit with cairo code and upped all appropriate sizes
> (i.e. 32 bit to 64 bit). This required a lot of busywork in tessellator.
> However, as I did it, I realized it won't help (and it did not) unless a
> few determinants calculated in tessellator are upped to 128 bit or more.
> Since for very wide polygons (with few vertices, like a giant rectangle)
> it is likely that two dimensions would be multiplied, we are talking
> potentially 10^14 or more.

There are very few people crazy enough to tackle the tessellator --
welcome!

> I am not sure 128 bit calculations are natively supported anywhere, and
> in any case this did not seem like a great solution anyway.

If you were to take a step in widening the precision of the internal
fixed-point arithmetic, you should spend a considerable amount of effort
ensuring that we used the narrowest integral types that afforded no
precision loss at each stage. (i.e for small shapes you might be able to
compute the entire tessellation using no more than 32 bit arithmetic
etc.)

> So, with that, I have a question:
> - It looks like polygons are tessellated fully, not clipped to surface
> size, right?
> - If I am correct - why? If not - would you point me towards polygon
> clipping code?

Simply because the work has not been completed yet. In order for it to a
make a difference whilst tessellating requires substantial changes to
the data types -- which has been completed. However, the goal of that
branch is to eliminate the artefacts due to self-intersecting polygons
and before I push that, it must not cause severe performance
regressions. As it happens, stroke-to-path is a viable panacea and by
carefully generating a minimal set edges and avoiding introducing extra
intersections, we can run the tessellator on self-intersecting strokes
with no performance regression compared to the current code. (In quite a
few cases, it is actually faster since we dramatically reduce the number
of trapezoids used to generate the stroke mask, and the speed-up from
not walking so many edges and writing so many pixels (by the rasterizer)
more than compensates the extra overhead in running the tessellator.)

Not only that but stroke-to-shaper (a subtle variation on the
stroke-to-path theme) is an important step for writing low quality h/w
based tessellators and is a requirement for stroking spans.

Please take a look at
http://cgit.freedesktop.org/~ickle/cairo/log/?h=self-intersecting.

Have fun with cairo!
-ickle