[cairo] Tessellator performance patch

[Carl Worth]

On Mon, 11 Dec 2006 15:05:50 -0700, "chris nuernberger" wrote:
> if a collision is possible.  This means that if you know the
> intersection point should lie below you, then you check the sign of
> the subtraction of the end x points at the lower y.  Or reverse this
> logic.

I'm afraid I'm really not sure what's being proposed this deep in this
thread.

What we have in the code right now is the following functionality:

_intersect_lines

	Given two line segments, compute the point (approximated to
	our sub-pixel grid) of the intersection of the two lines
	containing those segments, or a PARALLEL result if there is no
	intersection.

_cairo_bo_edge_intersect

	Given two edges, compute the point of intersection of the line
	segements, (or PARALLEL or NO_INTERSECTION results). This is
	built on top of _intersect_lines.

_cairo_bo_event_queue_insert_if_intersect_below_current_y

	Here, we're also looking for the intersection of two line
	segments, but we must also reject any intersections that occur
	before the current sweep line. To do this, we first call
	_slope_compare to reject any edge pairs whose slopes are such
	that any intersection must be above the sweep line, not
	after. If the slope comparison rejection fails, we call into
	_cairo_bo_edge_intersect.

What I hope is evident in the above, is that this is basically the
minimal code needed to be correct. There isn't really much
optimization here at all, (if any). The slope comparison thing looks a
little bit like an optimization, (it can reject some cases without
ever calling into _intersect_lines), but really it's just the easiest
way to reject intersections that occur "before" the sweepline, (trying
to examine the rounded intersection point's Y value and comparing it
to the sweepline's Y value just isn't as robust).

So, anyone looking at this code should regard this code as totally
unoptimized. Any cheap way to reject line segments that are guaranteed
to not intersect would definitely be useful. And the best place to do
that would be before the slope comparison. Also, cheaper ways than the
current slope comparison code to detect "intersection, if any, occurs
before sweepline" might also be useful.

Finally, there are currently some redundant calculations in the slope
comparison and intersection code that could be eliminated. These
aren't nearly as important, (it's _much_ more common for edges to not
intersect than to intersect---so that's the important case to make
cheap). But if someone wants to work on that, it will probably show up
as a speedup for the "tessellate" case in the perf. suite. That test
case is random and has an unrealistically large percentage of
intersections among its edge pairs. So it shows near-worst-case
performance behavior (that likely won't happen in common real-world
use) and similarly often shows best-case performance improvement to
certain optimizations (that also likely won't happen in common
real-world use).

For anyone that does have a good optimization to any of this code,
please start a new thread with the patch, and please make sure to run
"make test" before submitting it. Thanks.

-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/20061211/aeaf012b/attachment-0001.pgp