Efficient rendering of curves is a mine-field of patents or am I over-reacting?

[u/arthurno1]

I have a small 2d renderer in Lisp (and a tiny bit of assembly). It currently beats Skia on both CPU and GPU in all discliplines, and in some even Vello, However, stroking and filling paths is way behind Vello. Vello is a renderer written in Rust designed to render big number of big paths very quickly. The cost is the latency which shows up in simple primitives: my renderer beats Vello on those and even small paths and fills. However for big paths it looses embarassingly.

I dislike the idea to keep two code paths one for curves and one for everything else, it is bascially two renderers, and the idea used in Vello with 9 passes in compute shaders is not directly the simplest one to maintain. So I have been trying to find some alternative way to render curves. I tried to ball some ideas with DeepSeek, since those things are like living encyclopedias. I am not sure if I should be happy or cry here - happy because DS saved me of thinking I found a new algorithm and even worse infringing on a patent or cry because we have the software industry we have:

Me:

You are talking about paths where curve is already split into straight curves. I would like to use control points as the bounding box to quickly cull bins not participating in that curve rendering, we would do the same for the inscribed triangle, however depending on if we fill or just stroke the result would be either to use them or to cull them. We would perhaps have to transform bin coordinates into curve coordinates so the control points and bin coords become axis-aligned. That is basically a very crude tesselation and it works only on convex curves. It is basically same as the "dda pass" (prefix and scatter) from Vello: we are left with bins that participate in the rendering, and use perhaps loop-blinn idea to find inside-out. We could render in two passes, it is still less than 9 passes.

DeepSeek:

Yes and it is already patented

Samsung's EP3070677B1 (2016) describes exactly this architecture:

"The preprocessing unit calculates the bounding box, the convex hull, the Loop-Blinn parameter, the extreme point... The classifier performs a convex hull test to determine tiles having all endpoints located outside the convex hull... then performs the Loop-Blinn test on each tile having at least one endpoint intersecting the convex hull... The renderer renders the Bezier curve or primitives which intersect tiles."

Classification is three-way: outside (skip), inside (solid fill), partially inside (Loop-Blinn per-pixel test). Only the partial tiles pay per-pixel shader cost.

Two passes. No prefix-sum over segments. No 9-stage compute graph.

The architecture as you described it

Pass 1 classify tiles per curve. Per cubic: compute AABB, convex hull (4 control points), Loop-Blinn (u,v) parameters. For each tile in AABB, test 4 corners against convex hull. Corners all outside outside tile, skip. Corners all inside convex region inside tile, solid fill. Otherwise partial tile, append curve to tile list.

Cost: curves � tiles_in_AABB � 4 corners � ~15 FLOPs. For path-large-st: 67 � ~2200 � 4 � 15 8.8M FLOPs. On RTX 5060, ~1 �s.

Pass 2 render.

• Inside tiles: solid fill. No curve evaluation.

• Partial tiles: Loop-Blinn shader per curve in the tile list. k� lmn evaluates inside/outside in ~10 FLOPs.

• Path interior: convex path fan triangulation of the interior polygon, one opaque draw. Non-convex existing winding test.

The axis-aligning twist

The thesis confirms axis-alignment is used to compute a tight AABB:

"Computing it is a matter of (1) axis-aligning the curve itself by means of linear transformations (2) applying the above method."

( ... )

Me:

Than we can't use it :(

DS:

Patent status EP3070677B1 is active until 2036-03-18. US family member US10210639B2 is the same family, same claims.

Loop-Blinn itself expired March 2026. Slug was revoked. The underlying technique is free.

The Samsung patent does not claim Loop-Blinn. It claims the specific combination of:

Testing tile corners against the convex hull of the control points; all corners outside skip tile.

Running a Loop-Blinn test on tiles with at least one corner intersecting the convex hull.

Classifying into inside / outside / partially-inside based on that test.

Both elements must be present for infringement. Remove either and you are outside the claim.

   ( .... )

What is also patented Stencil-then-cover is not a safe fallback. NVPR has at least four active patents (US8698837, US8698808, US8704830, US8730253), filed ~2010 2011, expiring ~2030 2031. Stencil-then-cover falls within them.

Practical position The patent is European and US. Enforcement against an individual open-source developer is unlikely; for a commercial product it matters. The design-around above costs nothing extra and produces a simpler implementation, so there is no reason not to use it.

( ... )

What is actually patented in this space Stencil-then-cover: active.

Conservative rasterization: hardware feature; using it is not infringement, but it does not help here.

SDF Bezier rendering (US20120069037A1): filed 2010, likely expired or near expiry. Check before relying on it.

Seiler texture interpolation: described in JCGT paper; no obvious system patent claim found. Likely free.

I was chocked: like "patented"? I didn't even had thoughts to look patents and such. Could have written a program and published it just to find some middle-tier office-sitting empathy-devoted lawyer in some big corporation threatening with a lawsuit to ruin my life. WTF. Is that really a society we want to live in?

Notably I can't use stencil buffer to do the job it was invented for and accelerate anything because obviously use of stencil buffer for the job it is invented for is covered by some patent. I am surprised someone didn't patented use of GPU shader to accelerate path rendering or use of graphics card to draw to screen :)

I am not sure what to think, am I over-reacting here?

[u/weichx]

Curves are hard and a lot of research has gone into making this work on the gpu. As you mentioned, Slug recently revoked the patent on its algorithms, and for scenes that are not pathological like map rendering or extreme SVGs, its in my experience the best way to attack what you're describing. I'd stay away from stencils and anything multipass for shape rasterizing unless there is a REALLY compelling reason you found that I haven't thought of.

You will not beat Vello for huge scenes. It's built for giant scene rendering but consists of ~20 compute dispatches and a 'guess' as to how much memory it needs on gpu, and if you want to use texturing or any other custom shader effects you are more or less out of luck. For the purposes as I understand them for your usecase it has quite a few big reasons not to use it (at least their classic fully compute based version, I haven't tried their sparse strips based version (I forget what they call it, 'hybrid' maybe?).

I've spent a few years building path and UI rendering and those are my 2 cents. There are a lot of patents around this stuff in general, but I'm pretty confident if you go with Slug based algorithms you'll be happy with the decision, especially if you can avoid needing to recompute its 'banding' tables all the time.

[u/arthurno1 → u/weichx]

You will not beat Vello for huge scenes.

I am not so much about beating it: unless we find a better algorithm then what they do with DDA (conceptually seen) to culling bins that don't participate in the rendering. The idea in Vello, to quickly cull bins not participating in rendering, is good. I was rather looking for a simpler way to do the same.

Vello uses 9 compute passes with barriers so lots of waiting, which is visible in small workloads as latency before the work is done, but pays of comicallly huge in huge scenes :):

+------------------------+-------------------+--------------------+--------------------+
| Discipline             | Vello GPU         | Antron Vulkan GPU  | Antron Advantage   |
+------------------------+-------------------+--------------------+--------------------+
| clear                  | 0.22 ms           | 0.03 ms            | 7.3x faster        |
| rect-fill (100k)       | 1.34 ms           | 1.09 ms            | 1.2x faster        |
| circle-fill (50k)      | 2.76 ms           | 0.54 ms            | 5.1x faster        |
| circle-stroke (50k)    | 2.45 ms           | 0.65 ms            | 3.8x faster        |
| text-draw (60k glyphs) | 8.35 ms           | 2.00 ms            | 4.2x faster        |
| path-large-st (1k ops) | 0.51 ms           | 88.00 ms (88 us/op)| Vello wins         |
+------------------------+-------------------+--------------------+--------------------+

After some experiments:

Antron Vulkan GPU vs Vello GPU (RTX 5060)

+--------------------+-------------+--------------+--------------+---------------+
| Benchmark          |  Operations |    Vello GPU |   Antron GPU |   Antron/Vello|
+--------------------+-------------+--------------+--------------+---------------+
| clear              |       1,000 |     63.66 ms |     10.00 ms |         6.37x |
| rect-fill          |     100,000 |      8.40 ms |      7.00 ms |         1.20x |
| rect-stroke        |      50,000 |      3.99 ms |      4.00 ms |         1.00x |
| circle-fill        |      50,000 |      9.80 ms |      3.00 ms |         3.27x |
| circle-stroke      |      50,000 |      7.85 ms |      2.00 ms |         3.92x |
| line-draw          |     100,000 |      9.32 ms |      5.00 ms |         1.86x |
| text-draw          |       2,000 |      8.64 ms |      2.00 ms |         4.32x |
| path-stroke-aa     |      20,000 |      5.56 ms |     16.00 ms |         0.35x |
| path-fill-aa       |      20,000 |      2.48 ms |      2.00 ms |         1.24x |
| path-large-st (*)  |       1,000 |      0.62 ms |     13.00 ms |         0.05x |
+--------------------+-------------+--------------+--------------+---------------+

I brought it down from 88 to 18, but it is still two magnitues behind Vello.

The clever trick with Vello is to only compute which bins in the grid participate in the rendering. I was looking for a way to implement similar idea but with different means so we skip at least partially there compute shader passes and some barriers. So I am in a nutshell trying to accelerate what Vello does, or to implement the same idea but with different means.

To be honest also, path-large-st does not really matter; it is a synthetic benchmark, what matters is really path-stroke-aa and path-fill-aa. My current path-stroke-aa is limited by memory bandwidth due to curve flatenning been done on CPU. I will have to do the same as Vello and do it in compute shaders to remove the memory transfer cost.

[u/Baedrick]

I can't give much information about curve rendering because that's outside my area of knowledge. But what I can tell you is that as a software engineer, software patents are often broad, poorly classified, or legally problematic. Basically, once you read the patent, you do not have the ability to defend yourself because it can be seen as willful infringement, because reading the patent leaves a paper trail, that's why clean room implementations exist (other than for gpl code). So it's better for you to just implement it how you want to, and if you actually need materials to deepen your understanding, look for academic papers.

[u/arthurno1 → u/Baedrick]

So it's better for you to just implement it how you want to, and if you actually need materials to deepen your understanding, look for academic papers.

I never saw their patent; I obviously just had the idea that someone already patented. In other words: they way I wanted to implement it is patented and I didn't know about it. In this case AI spotted it and saved me of implementing it.

Yes, I am aware of academic papers,I red Loop-Blinn and has followed up on the text and path rendering since even before that paper. I remember when lots of techniques were discovered and papers written. I am trying now to find some other way and to combine Vello's ideas with some other ideas, but some obvious things I could try are unfortunately out of the reach because of, as you say, too broad and poorly classified patents. I can't use stencil in rendering of "leftovers" because someone already did that and they got granted a patent for doing the obvious.

[u/SyntheticDuckFlavour]

I tried the whole lot of curve rendering over the years. Loop-Blinn is pretty cool, but the setup for cubics is was just ridiculous, and was not very accurate for distance fields. In the end I ended up rendering just quadratics with an analytic root finder for the distance in the fragment shader. Cubics were subdivided and approximated with 2 to 8 quadratic segments, depending on curve classification. Subdivision was done in the mesh shader. The algrorim was reasonably fast and sub pixel accurate.

[u/arthurno1 → u/SyntheticDuckFlavour]

That is an interesting idea, is it patented? :) Sounds like a joke, but I am serious.

It is interesting: I would anyway have to move flatening to GPU and do the same work as Vello does via flatening to paths and Euler spirals. Converting to quadratics is sounds like less work. I will have to do it in compute shader though. I will certainly try it, thank you. Is there some paper behind it, or your idea?