[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.
> 
> Signed-off-by: Pekka Paalanen <ppaalanen at gmail.com>
> Cc: Rob Clark <rob.clark at linaro.org>

Agh!

I always meant to mention in the commit message the names of the people
who helped me test this, and I forgot, sorry!

Thank you to Darxus and Birin Sanchez for testing :-)
- pq