[cairo] Culling geometry outside the target surface

[Carl Worth]

On 05 Mar 2005 23:39:49 +0100, Soeren Sandmann wrote:
> Only if the replacement segment is itself outside the target, which
> may not be the case. Consider a sequence of line segments going around
> a corner of the target surface. All segments are outside the target,
> but the segment connecting the two terminal points is inside.

Thanks for catching this bug, Soeren. I'm glad I have this list as
such a great resource for fixing my mistakes.

I had an earlier formulation of the algorithm which I believe does not
have the bug, (which I introduced when rewriting it to make it simpler
to understand, and to match the current cairo_polygon interface). The
previous version was:

	When adding a new point to a polygon, consider it together
	with the previous two points in the polygon. If the bounding
	box of the three points is "outside" the target region, then
	the middle point can be discarded before the new point is
	added.

Additionally, I noticed another corner case that affects either
formulation. When considering whether a bounding box is "outside" of
the target region, (for the purpose of guaranteeing that enclosed
segments are outside the region), it is not sufficient that the box
does not intersect the region. It must also be the case that the box
does not entirely contain the target region.

> To fix that the algorithm could be modified so that each added segment
> was first converted to a number of segments, all of which are either
> completely inside or completely outside. That way, the optimization
> can throw away many more segments.

That would certainly allow the algorithm to throw away more, but the
extra intersection tests would add more overhead to the cases where we
don't actually discard anything. So, it would be important to measure
that.

>                                    I think in the worst case, the
> resulting polygon would be the convex hull for the clip region.

Not quite. Consider the case where the path completely encloses
contains the clip region without intersecting it, (eg. when zoomed way
in on an object). Even with your refinement, nothing will be
discarded, yet the path can still be arbitrarily large.

But I don't think this really matters. This is a pre-tessellation
optimization, so the area of the object doesn't matter, but the number
of segments does. A giant rectangle isn't any harder to tessellate
than a small one, for example.

And the rasterization stage shouldn't have any trouble avoiding extra
work for extra-large trapezoids generated this way, (though we still
need to put a fix into the X server similar to what we just did to
libpixman for this).

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050307/16b07389/attachment.pgp