<div dir="ltr"><div dir="ltr"> </div> <div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jul 20, 2021 at 5:21 PM Uli Schlachter <<a href="mailto:psychon@znc.in">psychon@znc.in</a>> wrote: </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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. </blockquote><div> </div><div>Maybe short for trapezoid?</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> 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] <a href="https://www.cairographics.org/samples/fill_style/" rel="noreferrer" target="_blank">https://www.cairographics.org/samples/fill_style/</a> 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 <a href="mailto:cairo@cairographics.org" target="_blank">cairo@cairographics.org</a> <a href="https://lists.cairographics.org/mailman/listinfo/cairo" rel="noreferrer" target="_blank">https://lists.cairographics.org/mailman/listinfo/cairo</a> </blockquote></div></div>