[cairo] Questions about Cairo and _cairo_bentley_ottmann_tessellate_polygon()

Tue Jul 20 18:57:07 UTC 2021

Hi,

On Tue, Jul 20, 2021 at 7:00 PM Michal Sudolsky <sudolskym at gmail.com> wrote:

>
>
> 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?
>

OK.

>
>
>>
>> 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.
>>
>
Once intersections are identified via Bentley-Ottmann, then the original
complex polygon could be transformed into a set of simpler / convex /
monotone polygons which could be triangulated easily (and handed over to
GPU for hw acceleration).
However I couldn't find any trace of the triangulation process in Cairo, so
it looks like (final) rendering would be rather based on tessellated
trapezoids (as outputted by the custom bentley-ottmann code).

I was looking for something in the lines of this research:
https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
, see Figure 3 in page 4 with the triangulated e letter.

>> 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?
>>
>
I'll have a look at pixman. SSE are specialized CPU instructions for SIMD
processing, e.g. suitable for pixel processing and vector math.

Still very much interested in Cairo's design, especially w.r.t. geometry
processing. Please don't hesitate to share any relevant pointers.

Regards,
Ilyes

>> 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
>>
> --
> 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/728084d5/attachment-0001.htm>