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