[PATCH weston 3/3] compositor: new intersection algorithm

[Pekka Paalanen]

On Tue, 11 Sep 2012 17:02:05 +0300
Pekka Paalanen <ppaalanen at gmail.com> wrote:

> The existing algorithm had some corner cases (pun!), where it failed to
> produce correct vertices in the right order. This appeared only when the
> surface was transformed (rotated). It also produced degenerate polygons
> (3 or more vertices with zero polygon area) for non-transformed cases
> where the clipping and surface rectangles were adjacent but not
> overlapping.
> 
> Introduce a new algorithm for finding the boundary vertices of the
> intersection of a coordinate axis aligned rectangle and an arbitrary
> polygon (here a quadrilateral). The code is based on the
> Sutherland-Hodgman algorithm, where a polygon is clipped by infinite
> lines one at a time.
> 
> This new algorithm should always produce the correct vertices in the
> clockwise winding order, and discard duplicate vertices and degenerate
> polygons. It retains the fast paths of the existing algorithm for the
> no-hit and non-transformed cases.
> 
> Benchmarking with earlier versions showed that the new algorithm is
> a little slower (56 vs. 68 us/call) than the existing algorithm, for
> the transformed case.  The 'cliptest f' command before and after this
> commit can be used to compare the speed of the transformed case only.

Thank you for merging :-)

Looks like I made a slight typo in the numbers there. They are not 56
vs. 68 us/call, they should be 0.56 vs. 0.68 us/call. Oh well, a factor
of 100 here or there, the ratio is still the same. :-D


Cheers,
pq