[cairo] [PATCH 0/4] Several bug fixes related to clipping and unbounded ops

[Taekyun Kim]

On 07/06/2011 04:36 PM, Chris Wilson wrote:
> Thanks for the test cases. Can I incorporate them and variants thereof
> into the test suite? For which, I need you to give me an appropriate
> licence... The no-name MIT license is the preferred choice for test cases,
> for example see tests/arc-infinite-loop.c
I re-send files with licence added at the top of each file.


> You found the sore point in the clipping code, in that it really wants to
> segregate boxes from polygons and the current implementation thereof is
> very incomplete. The rationale being that we can uses the boxes to
> pre-clip the geometry very cheaply. And then we chose to either convert
> the remaining polygon to a mask, or implement polygon clipping. (Or
> Bezier clipping if someone can demonstrate that to be beneficial...)
> And as always, different backends will have different requirements and
> need to make their own decisions as to which to use.
IMO, polygon clipping is better choice both for CPU and GPU backends.
It can reduce the number of total pixels being processed by avoiding
composition of temporary mask images. The performance will be bounded
by the number of total pixels actually plotted not by the extent area.

We can do clipping and rasterization in single pass by counting in/out
count for both filling polygon and clip polygon. Similarly, we can do
clipping and tessellation in single pass. Even boolean operations
between polygons is possible (Operator AND to do clipping).

I prefer scan-rasterizer for image and tessellator for GL backend.
Scan-rasterizer can give us good memory access patterns of increasing
address order and tessellator can give us convex polygons which are
easy to render using OpenGL.

IIRC I've seen bezier clipping in zack rusin's blog about several
years ago. I think it is not easy to overcome numerical errors and
degenerate cases. Instead I tried tessellation into some new basic
building blocks called "curved trapezoid" of which left and right
edges are vertically monotonic bezier curves. It's possible to render
them using OpenGL by giving convex hull and doing pixel in/out test
in fragment shader. Even anti-aliasing is possible by approximating
signed distance. But this is also a hard problem. Numerical error and
degeneracy are the source of evil. Indeed, this is a variant of Jim
Blinn's method which can be found in GPU Gems 3. Although it has some
limitations, I'm interested in this kind of approach.


> So I'm looking at refining the clipping code to cleanly perform the
> segregation. The idea now being that I actually have a good idea what
> functionality the image surface wants from the clipper.
I'm glad to hear that. Thanks!!


> The remaining bugs look like the trivial type of box-to-rect conversion
> errors, I shall have to review carefully to see if we are catching the
> root cause.
One more thing... I suspect that _composite_unalgiend_boxes() is
missing unbounded fixup and I couldn't find earlier rejection.
I will make a test case for this and send it if fails.

--
Best Regards,
Taekyun Kim

-------------- next part --------------
A non-text attachment was scrubbed...
Name: clip_bug.c
Type: text/x-csrc
Size: 2841 bytes
Desc: not available
URL: <http://lists.cairographics.org/archives/cairo/attachments/20110706/56196ea0/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: paint_bug.c
Type: text/x-csrc
Size: 2815 bytes
Desc: not available
URL: <http://lists.cairographics.org/archives/cairo/attachments/20110706/56196ea0/attachment-0001.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: unaligned_unbounded_bug.c
Type: text/x-csrc
Size: 1884 bytes
Desc: not available
URL: <http://lists.cairographics.org/archives/cairo/attachments/20110706/56196ea0/attachment-0002.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: unbounded_boxes_bug.c
Type: text/x-csrc
Size: 1963 bytes
Desc: not available
URL: <http://lists.cairographics.org/archives/cairo/attachments/20110706/56196ea0/attachment-0003.c>