[cairo] Culling geometry outside the target surface

[Carl Worth]

Ian McIntosh has been doing some great work with roadster[*] and it is
providing some excellent performance tests for cairo.

One thing that Ian has run into is that roadster is often drawing
large objects, much of which are off the target surface. And cairo
spends a lot of time on the off-surface portions of these objects. We
recently fixed libpixman to avoid rasterizing off-surface trapezoids,
which helps quite a lot, but only eliminates 1/2 the time spent on
off-surface objects.

So, it makes sense to do some higher-level rejection here.

It's easier to think about fills than strokes, so let's start
there. Just prior to tessellation, the object to be filled has been
converted to a compound polygon, which is a simple thing to reason
about:

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.

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.

This optimization is also easily extended by determining "outside"
based on the clip region of the target surface rather than its bounds.

As for strokes, instead of fills, I'm already planning to convert the
stroking code to construct a polygon, then fill it. (It currently
generates trapezoids directly while stroking, which yields the wrong
answer for self-intersecting paths since their are intersections
between the resulting trapezoids.) So once that change is in place,
strokes will benefit from the same optimization.

The actual construction of the bounding polygon from a stroke will
likely not need a similar outside-rejection optimization since it is
linear in path length, (whereas tessellating a polygon is between
O(NlogN) and O(N**2) in the number of line segments, depending on the
number of intersections).

This optimization shouldn't be hard to implement, so might make a good
project for someone wanting to start playing within the cairo code. It
should be almost entirely contained within
cairo_polygon.c:_cairo_polygon_add_edge.

-Carl

[*] http://linuxadvocate.org/projects/roadster/
-------------- 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/20050305/c49d0058/attachment.pgp