On Tue, 11 Sep 2012 17:02:05 +0300 Pekka Paalanen <[email protected]> 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 _______________________________________________ wayland-devel mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/wayland-devel
