<div dir="ltr">The "traps" are shapes with four sides, the top and bottom are horizontal, and I think must also be between pixels (though it is unclear how a horizontal antialiased edge is made).<div><br></div><div>At the time this was designed this was considered one of the faster shapes to fill in correctly with antialiasing. I think though the work needed to convert a path or stroke to a non-overlapping set of these was way underestimated, compared to other shapes like triangles with one antialiased side. In addition the practicality of using large memory buffers to render the shape as opaque and aliased and then downsampling to get an anti-aliased and transparent shape has increased by orders of magnitude since then.</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jul 20, 2021 at 11:57 AM Ilyes Gouta <<a href="mailto:ilyes.gouta@gmail.com">ilyes.gouta@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">Hi,</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jul 20, 2021 at 7:00 PM Michal Sudolsky <<a href="mailto:sudolskym@gmail.com" target="_blank">sudolskym@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><br></div><br><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" target="_blank">psychon@znc.in</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
Am 19.07.21 um 23:47 schrieb Ilyes Gouta:<br>
> Hi Cairo devs,<br>
> <br>
> I'm reading Cairo's source code and trying to figure out its inner design,<br>
> and it seems a Bentely-Ottmann implementation is heavily referenced, so via<br>
> symbols like _cairo_bentley_ottmann_tessellate_polygon()<br>
> and _cairo_bentley_ottmann_tessellate_traps().<br>
> <br>
> Would it be possible to explain these functions, what's their input, what<br>
> they do and what's the output?<br>
<br>
Okay, well, the prototypes are:<br>
<br>
cairo_status_t<br>
_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps, const<br>
cairo_polygon_t *polygon, cairo_fill_rule_t fill_rule)<br>
<br>
This looks a lot (due to "const") like the polygon is the input and the<br>
output are traps. That also matches the name of the function.<br>
<br>
_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,<br>
cairo_fill_rule_t fill_rule)<br>
<br>
Uhm. This tessellates traps into traps? From the implementation I can<br>
see that the traps are first transformed into a polygon and then that<br>
first function is called.<br>
<br>
<br>
Now, what is a trap? I honestly don't know, but I found<br>
_cairo_debug_print_traps(). I'd say a trap is something I once saw in<br>
XRender.<br></blockquote><div><br></div><div>Maybe short for trapezoid?</div></div></div></blockquote><div><br></div><div>OK.</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"><div dir="ltr"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
You have two lines. One of them is the left border and the other is the<br>
right border. The area between the two lines is to be filled.<br>
<br>
Additionally, you have a top and bottom. These are just y positions.<br>
Only the area between the top and bottom are to be filled.<br>
<br>
This representation avoids some rounding errors when producing it. At<br>
least I think I read that somewhere.<br>
<br>
<br>
I also guess that these functions turn something that might be<br>
self-intersecting into non-intersected "pieces". I mostly guess this<br>
because of the cairo_fill_rule_t argument.<br>
<br>
Random example I found on the web page for fill rules: [1]<br>
<a href="https://www.cairographics.org/samples/fill_style/" rel="noreferrer" target="_blank">https://www.cairographics.org/samples/fill_style/</a><br>
<br>
In this example, the drawing commands that one can see in the code<br>
describe a polygon. A bunch of lines (and curves). By tesselating, this<br>
is then turned into "just the area that is to be filled".<br>
<br>
> AFAIK, the Bentley-Ottmann algorithm is mostly for computing intersections<br>
> between segments, in the case of Cairo, is it also used for polygon<br>
> triangulations? If yes, is it possible to explain (referencing cairo source<br>
> code)?<br>
<br>
Yeah, well, the points of self-intersections of a polygon are where<br>
"something interesting" happens. The rest is just straight lines.<br></blockquote></div></div></blockquote><div><br></div><div>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).</div><div>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).</div><div> </div><div>I was looking for something in the lines of this research: <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf" target="_blank">https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf</a> , see Figure 3 in page 4 with the triangulated e letter.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Note that I do not really know what I am talking about and am just<br>
guessing (based on some prior experience from staring at cairo's source<br>
code and having no one to explain me things).<br>
<br>
> What primitive does Cairo use internally for (final) rendering? Is it a<br>
> span-based rendering or does Cairo build triangles / quads out of the<br>
> tessellated shapes and submit these to e.g. GPUs for HW accelerated<br>
> rendering?<br>
<br>
It depends. I'll assume you mean the image backend. In this case, the<br>
final rendering is done by the pixman library. It is entirely done on<br>
the CPU. AFAIK, GPUs are not well suited for immediate rendering and<br>
e.g. cairo-opengl does not really provide nice benefits.<br>
<br>
> Finally, is there a document describing the architecture and implementation<br>
> of Cairo, in detail, such as covering the entire processing flow, from the<br>
> high level API, Bézier curves flattening, to tessellation, triangulation,<br>
> rasterization and HW acceleration?<br>
<br>
I don't know any such document, sorry. It also depends a lot on the<br>
cairo backend in use. And on properties of the path (for example, a<br>
simple pixel-aligned rectangle is a lot simpler than everything else).<br>
<br>
HW acceleration: Well, pixman can use things like SSE. Does that count?<br></blockquote></div></div></blockquote><div><br></div><div>I'll have a look at pixman. SSE are specialized CPU instructions for SIMD processing, e.g. suitable for pixel processing and vector math.</div><div><br></div><div>Still very much interested in Cairo's design, especially w.r.t. geometry processing. Please don't hesitate to share any relevant pointers.</div><div><br></div><div>Regards,</div><div>Ilyes</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Cheers,<br>
Uli<br>
-- <br>
"Do you know that books smell like nutmeg or some spice from a foreign<br>
land?"<br>
                                              -- Faber in Fahrenheit 451<br>
-- <br>
cairo mailing list<br>
<a href="mailto:cairo@cairographics.org" target="_blank">cairo@cairographics.org</a><br>
<a href="https://lists.cairographics.org/mailman/listinfo/cairo" rel="noreferrer" target="_blank">https://lists.cairographics.org/mailman/listinfo/cairo</a><br>
</blockquote></div></div>
-- <br>
cairo mailing list<br>
<a href="mailto:cairo@cairographics.org" target="_blank">cairo@cairographics.org</a><br>
<a href="https://lists.cairographics.org/mailman/listinfo/cairo" rel="noreferrer" target="_blank">https://lists.cairographics.org/mailman/listinfo/cairo</a><br>
</blockquote></div></div>
-- <br>
cairo mailing list<br>
<a href="mailto:cairo@cairographics.org" target="_blank">cairo@cairographics.org</a><br>
<a href="https://lists.cairographics.org/mailman/listinfo/cairo" rel="noreferrer" target="_blank">https://lists.cairographics.org/mailman/listinfo/cairo</a><br>
</blockquote></div>