[cairo] Questions about Cairo and _cairo_bentley_ottmann_tessellate_polygon()

[Michal Sudolsky]

On Tue, Jul 20, 2021 at 5:21 PM Uli Schlachter <psychon at znc.in> wrote:

> Hi,
>
> Am 19.07.21 um 23:47 schrieb Ilyes Gouta:
> > Hi Cairo devs,
> >
> > I'm reading Cairo's source code and trying to figure out its inner
> design,
> > and it seems a Bentely-Ottmann implementation is heavily referenced, so
> via
> > symbols like _cairo_bentley_ottmann_tessellate_polygon()
> > and _cairo_bentley_ottmann_tessellate_traps().
> >
> > Would it be possible to explain these functions, what's their input, what
> > they do and what's the output?
>
> Okay, well, the prototypes are:
>
> cairo_status_t
> _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps, const
> cairo_polygon_t *polygon, cairo_fill_rule_t fill_rule)
>
> This looks a lot (due to "const") like the polygon is the input and the
> output are traps. That also matches the name of the function.
>
> _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
> cairo_fill_rule_t fill_rule)
>
> Uhm. This tessellates traps into traps? From the implementation I can
> see that the traps are first transformed into a polygon and then that
> first function is called.
>
>
> Now, what is a trap? I honestly don't know, but I found
> _cairo_debug_print_traps(). I'd say a trap is something I once saw in
> XRender.
>

Maybe short for trapezoid?


>
> You have two lines. One of them is the left border and the other is the
> right border. The area between the two lines is to be filled.
>
> Additionally, you have a top and bottom. These are just y positions.
> Only the area between the top and bottom are to be filled.
>
> This representation avoids some rounding errors when producing it. At
> least I think I read that somewhere.
>
>
> I also guess that these functions turn something that might be
> self-intersecting into non-intersected "pieces". I mostly guess this
> because of the cairo_fill_rule_t argument.
>
> Random example I found on the web page for fill rules: [1]
> https://www.cairographics.org/samples/fill_style/
>
> In this example, the drawing commands that one can see in the code
> describe a polygon. A bunch of lines (and curves). By tesselating, this
> is then turned into "just the area that is to be filled".
>
> > AFAIK, the Bentley-Ottmann algorithm is mostly for computing
> intersections
> > between segments, in the case of Cairo, is it also used for polygon
> > triangulations? If yes, is it possible to explain (referencing cairo
> source
> > code)?
>
> Yeah, well, the points of self-intersections of a polygon are where
> "something interesting" happens. The rest is just straight lines.
>
> Note that I do not really know what I am talking about and am just
> guessing (based on some prior experience from staring at cairo's source
> code and having no one to explain me things).
>
> > What primitive does Cairo use internally for (final) rendering? Is it a
> > span-based rendering or does Cairo build triangles / quads out of the
> > tessellated shapes and submit these to e.g. GPUs for HW accelerated
> > rendering?
>
> It depends. I'll assume you mean the image backend. In this case, the
> final rendering is done by the pixman library. It is entirely done on
> the CPU. AFAIK, GPUs are not well suited for immediate rendering and
> e.g. cairo-opengl does not really provide nice benefits.
>
> > Finally, is there a document describing the architecture and
> implementation
> > of Cairo, in detail, such as covering the entire processing flow, from
> the
> > high level API, Bézier curves flattening, to tessellation, triangulation,
> > rasterization and HW acceleration?
>
> I don't know any such document, sorry. It also depends a lot on the
> cairo backend in use. And on properties of the path (for example, a
> simple pixel-aligned rectangle is a lot simpler than everything else).
>
> HW acceleration: Well, pixman can use things like SSE. Does that count?
>
> Cheers,
> Uli
> --
> "Do you know that books smell like nutmeg or some spice from a foreign
> land?"
>                                               -- Faber in Fahrenheit 451
> --
> cairo mailing list
> cairo at cairographics.org
> https://lists.cairographics.org/mailman/listinfo/cairo
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cairographics.org/archives/cairo/attachments/20210720/d355e898/attachment.htm>