[cairo] Culling geometry outside the target surface

[Soeren Sandmann]

Carl Worth <cworth at cworth.org> writes:

> Any point in the polygon is easily classified as outside the target
> surface or not.
> 
> Any line segment can be classified as outside if it meets the
> following two criteria:
> 
> 	1. Both end points are outside.
> 
> 	2. The line segment does not intersect the bounds of the
> 	   target surface.
> 
> 	   For the purpose of this optimization, a cheaper version of
> 	   this criteria would be to check that the bounding box of
> 	   the line segment does not intersect the bounds of the
> 	   target surface.
> 
> Given this classification, it is apparent that any sequence of
> "outside" line segments may be replaced by a single line segment
> connecting the terminal points.

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.

> And this should all be fairly simple to implement by adding a new test
> at the point when a new line segment is to be added to the polygon.

The algorithm would work as long as you never add a replacement
segment that intersects the target surface. This algorithm can still
produce polygons that are arbitrarily bigger than the clip region,
though.

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. I think in the worst case, the
resulting polygon would be the convex hull for the clip region.


Søren