[cairo] Questions about Cairo and _cairo_bentley_ottmann_tessellate_polygon()

[Uli Schlachter]

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.

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