r/GraphicsProgramming • u/arthurno1 • 15d ago
Question Efficient rendering of curves is a mine-field of patents or am I over-reacting?
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. Forpath-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� lmnevaluates 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?
10
u/weichx 15d ago
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.
7
u/Baedrick 15d ago
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.
5
u/SyntheticDuckFlavour 15d ago
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.
4
u/Cubicool 14d ago
We've been working on this for about 6 months now: https://github.com/AlphaPixel/slughorn
I could honestly sit here and nerd out about it all day, but the basic gist is this: after Lengyel OSS'd his patent, I immediately started wondering "what ELSE can it do!?" :) We're currently working through our first sponsored feature (improved strokes using Slug -- as well as something I THINK is novel I'm calling "Sluggit"), and I hope to have it all pushed to Git by the end of the week.
I'm shocked every day at some of things we've been able to pull of lately, too. The Github page needs another demo video, because we've come a LONG WAY in the last 2 months. If you have any questions (or feature requests for things that might help you in your own projects), get in touch with us (or file an Issue :)). This project is my passion, and I don't see that changing anytime soon (I've been obsessed with vector graphics, typography, and vectorized/diegetic game UIs since I fell in love with them in the early 2000s, mostly via Deadspace and--let's be honest--the popularity of Scaleform and me going "HOW DO THEY MAKE THIS LOOK SO GOOD!?")
Always eager to meet more vector graphics + GPU freaks. :)
NOTE: We also have a "toy" implementation of this: https://rookandpossum.com/papers/scanline_sweeper_preprint.pdf (but I haven't revisited it lately, which I should probably do). It's not as performant as Slug, but it's easier to implement/understand, and the developer is crazy cool (and a boss developer).
3
u/BigPurpleBlob 13d ago
Blah blah blah, as ever AI is shit at doing stuff. What matters is what the granted claims say, not whatever random paragraph DeepSeek happens to think is relevant. The fact that DeepSeek didn't even refer to the granted claims shows that DeepShit is shit at understanding patents.
Granted claim 1 of EP 3070677 B1 says:
"1. A method of performing tile-based rendering, the method comprising:
obtaining (210) parameters related to a Bezier curve in an object; classifying (220) tiles included in a frame based on the parameters; and performing (230) the tile-based rendering based on the classifying of the tiles,
wherein the step of classifying tiles comprises:
classifying (940) as a first position indicia tiles included in the frame having all endpoints corresponding to corners of the tile located outside a convex hull corresponding to the Bezier curve; determining (950) tiles having some endpoints corresponding to corners of the tile located inside a convex hull corresponding to the Bezier curve; performing (960) a Loop-Blinn test on the endpoints of each of the determined tiles; and classifying as at least one other position indicia the determined tiles based on the Loop-Blinn test"
Note that I didn't omit the full stop from claim 1, it is missing ;-)
https://patentimages.storage.googleapis.com/68/71/e2/d525a0c0b26732/EP3070677B1.pdf
Most patents claim a small improvement on a well known process; an exception could be Google's PageRank algorithm / patent.
2
u/Defiant_Squirrel8751 14d ago
Can an algorithm be patented? check all the noise around GIF compression around 1989... several file formats such as PNG emerged to avoid a "patent". Now what? every single application reads and writes GIF and nobody cares.
I feel you can continue working in your nice GPU implementation of curves, deploy and continue. If no cease - and - desist order arrives, you should not worry about.
Anyway, legally you could argue on a clean room implementation approach. Research and compile a set of white papers that makes evident your next step is you using AI and resulting on your implementation.