== Gezira: a deep dive === wip
This is going to be about a piece of historical software called Gezira.
I first found out about it from, I think, somewhere on link(https://worrydream.com/)[worrydream.com] many years ago. I didn’t think much of it at the time. Very recently, for no real reason, I got interested in it and started to take a closer look.
I’m going to talk about the environment Gezira was created in, the people who were involved, and their goals. And then I’m going to do a deep dive of the source code: what it says, why it says it, and my opinions.
In 2001 Alan Kay co-founded the Viewpoints Research Institute, or VPRI. It started as an outreach organization for Squeak, but around 2006 it shifted focus to research. The research project they started was called STEPS.
It was a typical Alan Kay endeavor: reenvision computing in the image of whatever has been on his mind recently. This time it’s source code size. In my own words, I’d say the problem statement is “can we make a computing system that has 95% of the functionality, 95% of the ease of use, but 1/10000th of the lines of code of systems today?”, where “today” meant 2005. He often mentioned a target of 20kLOC for the whole computing stack.
Their primary output were research papers and NSF progress reports. These are listed link(https://tinlizzie.org/IA/index.php/Papers_from_Viewpoints_Research_Institute)[here].
The main vehicle by which they worked towards their goal is a program they created called Frank. Frank is one of those document-centric computing models. Documents could embed text, images, programs, etc. I don’t think the source code to Frank was ever released. I’ve seen multiple people online talk about running Frank, but I don’t know where they found the source.
The VPRI’s link(https://www.nsf.gov/awardsearch/showAward?AWD_ID=0639876)[5-year NSF grant] concluded in 2012. After that the VPRI slowed down significantly. Their website lists 2018 as the official end of the institute, but Alan Kay is listed as an author to only 2 papers after 2013, down from multiple papers a year. In 2016 the VPRI joined Y-Combinator’s HARC, during which not as much is known publicly.
In all the annual NSF progress reports, a big deal is made about the rendering system. That’s what I want to talk about.
The goal was to come up with a way to do all of the 2D graphics necessary to power Frank. It would need to render text and shapes and such in as few lines of code as possible. They would do this by creating language that could efficiently describe how to render, and compilers that could translate this description into a runnable artifact.
This was spearheaded by a man named Daniel Amelang. He was a contributor to the Cairo graphics library in 2006 and 2007. He joined the VPRI to work on the graphics problem. The goal was to create a graphics system that would support all of the major features of Cairo, but in much less code.
It started as a regular software renderer written in C. He rewrote it, reduced it, and eventually wrote a DSL that could effectively describe the entire renderer.
The end result was Gezira, a renderer written in just a couple hundred lines. It supports beziers, fills, strokes, antialiasing, some limited texture filtering, many compositors, different caps and joins. It was written in a custom DSL made for the task. It was run in Nile, a custom stream processor also made for the task. There were other things in the mix, like a grammar parser called OMeta, and scheme variant called Maru. But in practice, Nile and Gezira was ported several times to multiple languages. The Gezira algorithms and the stream processor were the important things.
In principle Nile is supposed to be a more general tool, one that can run Gezira as well as other things. In practice, Nile and Gezira are closely interrelated. So to make matters simpler I’m going to be referring to them both just as Gezira. That might be controversial, so I’m sorry.
Gezira would take in a stream of shapes, a pipeline description, and output a stream of pixel colors.
People like Alan Kay like to promote the idea that we should be chasing “the Maxwell’s equations of ___.” The Maxwell’s equations of rendering would be a short formula, only a couple lines long, which would encompass all of 2D rendering, all edge cases included.
And so that’s what they did.
Here is their “rendering formula”. For a pixel with opposite corners (x, y) and (x+1, y+1), the “coverage” of a single line segment AB is:
\[\begin{aligned} s(P,Q) & = (Q_y - P_y) \left( x + 1 - \frac{Q_x + P_x}{2} \right) \\ g(P) & = \min(x+1, \max(x, P_x)), \min(y+1, \max(y, P_y)) \\ o(P) & = \frac{1}{m} (g(P)_y - P_y) + P_x, m (g(P)_x - P_x) + P_y \\ \text{coverage}(AB) & = s(g(A), g(o(A))) + s(g(o(A)), g(o(B))) + s(g(o(B)), g(B)) \end{aligned}\]To compute the combined coverage of multiple line segments for a given pixel, you sum them:
\[\min( | \sum{coverage(AB_i)} | , 1)\]This is how it is written on all of Gezira’s materials. As far as I can tell, the formula is always presented as-is, and is rarely explained.
Personally, I think this form is unnecessarily opaque. Here’s my version:
For a line $AB$ and a a pixel with opposite corners (x, y) and (x+1, y+1), the coverage of that line for that pixel is
\[\begin{aligned} m = & \frac{B_y - A_y}{B_x - A_x} \\ \text{trapezoid}(P,Q) = & (Q_y - P_y) \left( x + 1 - \frac{Q_x + P_x}{2} \right) \\ \text{snap}(P) = & \min(x+1, \max(x, P_x)), \min(y+1, \max(y, P_y)) \\ \text{clip}(P) = & \text{snap} \left( \frac{1}{m} (\text{snap}(P)_y - P_y) + P_x, m (\text{snap}(P)_x - P_x) + P_y \right) \\ \text{coverage} = & \text{trapezoid}(\text{snap}(A), \text{clip}(A)) + \\ & \text{trapezoid}(\text{clip}(A), \text{clip}(B)) + \\ & \text{trapezoid}(\text{clip}(B), \text{snap}(B)) \end{aligned}\]imgcmp(rendering_formula_simple.svg)The “coverage” of a line segment for a pixel is the intersection of the area sweeped to the right, and the area of the pixel.[If parts of the line segment lie outside the pixel, the coverage is broken up into pieces and summed together.]
trapezoid(P,Q) computes the area of a trapezoid formed by P, Q, and the projections of P and Q on the right edge of the pixel. snap(P) and clip(P) are used to compute which portion of the line is inside the pixel, if any. These are then put together to compute the area of the intersection of the pixel square and the line, if the line were swept right.
The area is signed as well, thanks to the $(Q_y - P_y)$ term in trapezoid. So if we were computing the total coverage of a closed polygon, any extra coverage for a line segment will get undone by a later line segment that closes the loop.
| The total coverage has that extra $\min( | … | , 1)$ term to not enforce a particular winding direction, and to handle multiple overlapping shapes. |
This should remind you of other polygon area and winding rule algorithms. Pretty standard technique. It naturally supports the CW/CCW winding rule.
It does NOT support additional filtering, though since traditional filters are also linear it’s not out of the question. It also ONLY supports closed polygons, though it does allow holes by winding them in the opposite direction.
img(shutter.svg)[A square wave pattern realized with rectangles. It has a frequency of 7/8 = 0.875]
img(alias.svg)[Pixel coverage of this pattern as reported by Gezira. Note that the 7/8 frequency has aliased to a frequency of 1/8, and attenuated down to a peak-to-peak amplitude of $145 - 109 = 36 \approx 255 \, \text{sinc}(7/8)$]
Why does trapezoid(P,Q) sweep the area out to the right instead of left? I won’t get into it now, but it’s because Gezira renders scanlines from left to right. If you sort the line segments you can render an entire scanline by updating an accumulator.
It’s important to note that the Gezira source code does NOT use the formula as described. For reasons we’ll get into later, Gezira actually pre-clips line segments. The line segments passed into the coverage computation code are already entirely contained in their given pixel. So there’s no need for clip() and snap().
The rendering formula that’s actually being used looks like:
\[\text{coverage}(AB) = (B_y - A_y) \left( x + 1 - \frac{Bx + Ax}{2} \right)\]So if this rendering formula is supposed to be the basis of all rendering that powers this computing system, how does that work? There’s more you might want to render than filled polygons. How does stroking work? Or texturing?
Stroking works by offsetting the curve in both directions and rendering as a closed shape. More on this later.
Texturing works by taking a point sample of the texture at the center of a pixel and weighting it by the coverage to blend. More on this later as well.
The Nile and Gezira source are published link(https://github.com/damelang/nile)[here] and link(https://github.com/damelang/gezira)[here] respectively. From what Dan Amelang has said, it isn’t in build-able condition. Significant work will have to be done to get it working link(https://github.com/damelang/nile/issues/3#issuecomment-517508949)[apparently].
Luckily, the output from some of the build stages are checked in to the repo, so we can still observe a lot. For example, you can see the Gezira’s .c files.
Despite the fact that there’s an “official” repo, there are a few versions of the source out there.
There are also several reimplementations in other languages, but we’re not looking at those here.
We’re going to be looking at the Gezira source shortly, but I’m torn between which version to show. The “official” source is the most obvious one. When someone wants to see the source code to Gezira they’d go to the Gezira repo and look under nl/.
However, I like the js demo code the most for its stylistic choices. From the file modified dates it also seems like the latest edition. And most importantly, of all of the Gezira versions, this is the only one that actually runs!
Unfortunately, it’s not perfect. There are some stylistic changes that were made to get the js demo working. For example, in the “official”, source operators get applied elementwise over vectors implicitly, which is nice. I guess they never implemented that in the js demo.
Whatever. We’re going to be looking at the js demo source code. From now on I’m calling this the “latest” source.
What I’m trying to get at is that this project, though dead and abandonded, is very much a work-in-progress.
If we’re not building it, then what are we doing? Well, the main way I think anyone understands Gezira these days is from link(https://tinlizzie.org/dbjr/high_contrast.html)[Bret Victor’s demo site].
Yup! The famous Bret Victor made a little demo site for Gezira in 2012, explorable-explanations style. You can mouse over pixels, beziers, samples, and see how the data flows through the pipeline. You can click the stages to expand and see the sub-stages! Next to each stage is that stage’s source code, and as you hover over the elements you see the branches that element took in the source. Very cool!
img(bret.png)[A screenshot of the demo site.]
And there’s actually more to the site than you see. If you open up the console and paste document.getElementById("mySidebar").style.display="block"; document.getElementById("mySidebar").style.position="relative"; you get a menu where you can pick different prepared scenerios.
This site is a huge help in understanding Gezira.
The site does have two small, pretty inconsequential bugs: PadGradient should be Real >> Real and not Point >> Point, and Texture should take in SpanCoverage not EdgeSpan.
It’s important to mention that the demo site is NOT interpretting Gezira code. The source listings on the side are Gezira source code, but the interactive stuff is rewritten by hand in javascript. So syntax errors like these don’t affect the demo.
Also, the way that highlighting works on the site can be confusing. The way that CombineEdgeSamples works makes it seem like there’s a bunch of off-by-one error, even though there aren’t.
The rest of this post is going to be a breakdown of the Gezira source, specifically the part shown on the demo site. I’ll be going through each stage, explaining the code, and giving my thoughts and opinions.
Earlier you may have been saying “the rendering formulas are nice, but they’re only for line segments? What about curves? They’re pretty important for 2D rendering.” And you’d be right.
Gezira actually operates exclusively on beziers, which it then deconstructs into line segments at the last moment. Surprisingly, it uses quadratic beziers instead of cubic. This is presumably because due to the focus on text, and because TrueType only supports quadratic beziers?
(Interestingly, in link(https://www.youtube.com/watch?v=HAT4iewOHDs&t=1025s)[this talk] given by Dan Amelang, he explicitly says that the beziers are cubic. However none of the versions of the Gezira source I’ve seen support cubic beziers.)
The first major stage of rasterization takes in a stream of quadratic beziers and output CoverageSpans.
Rasterize () : Bezier >> SpanCoverage
→ DecomposeBeziers () → SortBy (1) → SortBy (2) → CombineEdgeSamples ()
The pipeline here is self-explanatory.
There’s actually a difference here between the “latest” source and the “official” source. The “official” source lists this:
Rasterize : Bezier >> CoverageSpan
⇒ DecomposeBeziers → SortBy (@x) → SortBy (@y) → CombineEdgeSamples
The eagle-eyed might notice two different operators here: ⇒ and →. In my editor they look very similar. The ⇒ operator seemed to be used when beginning a new pipeline, and → continued it. I’m glad this was changed.
The other differences aren’t important. In the “official” source DecomposeBeziers and CombineEdgeSamples don’t have parameter lists, but that’s just a syntax change.
Like I’ve mentioned already, the source listed on the demo site actually comes from Nile js compiler demo. So the source listed here is mostly the same, but sometimes won’t match up exactly with the demo site.
Anyways, here’s the first stage:
type EdgeSample = (x:Number, y:Number, area:Number, height:Number)
DecomposeBeziers () : Bezier >> EdgeSample
ϵ = 0.1
∀ (A, B, C)
P = ⌊A⌋ ◁ ⌊C⌋
if ∧(P ≤ A ≤ P + 1 ∧ P ≤ C ≤ P + 1)
(x, y) = P
(w, _) = P + 1 - (A ~ C)
(_, h) = C - A
>> (x + 0.5, y + 0.5, wh, h)
else
M = (A ~ B) ~ (B ~ C)
( min, max) = (⌊M⌋, ⌈M⌉)
(Δmin, Δmax) = (M - min, M - max)
N = { min, if |Δmin| < ϵ
max, if |Δmax| < ϵ
M, otherwise }
<< (N, B ~ C, C) << (A, A ~ B, N)
This step does a lot of work. It takes each bezier, recursively breaks it apart into smaller beziers until it’s “small enough” and fits inside a single pixel square, then applies the simplified rendering formula from above, to finally output the contribution of THAT bezier piece in THAT pixel.
Let’s take it a bit at a time.
It first tests whether the bezier is fully contained in a single pixel by checking its two endpoints. There’s an obvious problem with this, but I’ll get to that later.
The formula it uses for this is:
P = ⌊A⌋ ◁ ⌊C⌋
if ∧(P ≤ A ≤ P + 1 ∧ P ≤ C ≤ P + 1)
...
Being a streaming language, Gezira takes after APL. So we’re going to be seeing lots of funny symbols everywhere. Maxwell’s equations and all that.
floor and ceil are very common and useful in graphics, so they’re given their own operators. In Gezira, these operators are applied elementwise.
We also see the and operator, ∧, being applied once elementwise (Bool², Bool²) >> Bool², and then again across elements Bool² >> Bool.
The ◁ operator computes the min of two numbers. It was chosen because it kinda looks like a < sign. Similarly the ▷ operator computes max. Because min is commutative, it’s envisioned here as an infix operator. So you can chain them together like A ◁ B ◁ C! Same with max.
And actually, min and max associate (but don’t commute) with each other. So statements like min ▷ A ◁ max make sense. This is used to clamp numbers in a couple places in Gezira. Very cool! This is a nice demonstration of the STEPS conceit.
This is slightly different from the source on the demo site:
inside = (⌊ A ⌋ = ⌊ C ⌋ ∨ ⌈ A ⌉ = ⌈ C ⌉)
if inside.x ∧ inside.y
This isn’t used in the “latest” source because it has a small bug:
img(pixel_inclusion.svg)[Is the line contained inside a pixel? A bunch of test cases.]
In the image above, example line segments 1, 5, 6, and 7 are entirely contained in a pixel boundary. Number 6 looks wrong because, while it’s not contained in the blue pixel square, it is entirely contained in the next pixel to the right. Remember, in this stage pixels aren’t asking which beziers they contain. The beziers themselves are asking if they are contained inside of a pixel.
It’s an elegant formulation, and handles the case where one of the endpoints lie on a pixel boundary. If they do that, they’ll have integer coordinates, and so ⌊A⌋ = ⌈A⌉. See image above.
This works nicely in all cases but one: the case where the endpoints lie on opposite edges of a pixel square. This is the example number 7 above.
This is actually link(https://github.com/damelang/gezira/blob/9f3e6846f4a1732c344a3b99e5d670deac618b17/TODO#L37)[mentioned in one of the TODO files] in the Gezira git repo.
- optimization: how often do we get tiny beziers with
endpoints on opposite sides of the pixel square? We currently split
these, but could try not doing it (with effects on visual quality)
The “latest” source fixes this by directly calculating the box that the bezier should be in.
I liked the old version though! It was simple and clever. So here’s a version I came up with that preserves the spirit of the old version:
if ∧(⌈A⌉ - 1 <= C <= ⌊A⌋ + 1)
...
img(pixel_inclusion_corrected.svg)[My version. Given A, it finds the square that C can be in to be considered in the same pixel.]
Anyways, let’s tackle the else branch next.
M = (A ~ B) ~ (B ~ C)
Again, cool use of a DSL. The ~ operator calculates (A + B)/2. This one is used all the time. Here, the beziers are always split at the t=0.5 point.
( min, max) = (⌊M⌋, ⌈M⌉)
(Δmin, Δmax) = (M - min, M - max)
N = { min, if |Δmin| < ϵ
max, if |Δmax| < ϵ
M, otherwise }
This is a little messy. See, if you always split beziers at the midpoint, there are too many situations where this will recurse forever, generating smaller and smaller beziers that cross pixel boundaries. So you need to clamp the endpoints when they get “close enough.”
Note that even the inline if statement is being computed element-wise! |Δmin| and |Δmax| are both computing absolute values elementwise. To compute a vector norm, you’d have to do ‖ A ‖, with the double bars. I suppose not even Gezira can get away from these sorts of problems.
There’s actually another function in the Gezira source which seems to do something very similar, ClipBeziers, which is never used.
Note here also the unicode characters in the variable names Δmin and Δmax. Also, |x|, and most other operators you see in the source are user-defined. They’re all defined at the top of the source.
...
|a:Number| : Number
{ -a, if a < 0
a, otherwise }
a:Number ≈ b:Number : Boolean
|(a - b)| < 0.0001
...
The Gezira syntax seems incredible and expressive, but the syntax is more restrictive than it looks.
While it’s true that you can use non-latin characters in your variable names, those non-latin characters can ONLY be from the greek/coptic unicode block U+0370 - U+03FF. And operators CAN’T be latin characters or greek/coptic characters. For example, if you wanted to define an operator Δf(x) to be defined as f(x+1) - f(x) or ∇ ∙ ∇ or whatever, it couldn’t exist at the same time as a variable named Δmin, even if you changed the grammar.
That’s because OMeta, the parser used to parse Gezira code, doesn’t include a symbol table as part of its grammar. So it can’t backtrack on “this variable/operator name isn’t bound.” When the parser consumes a Δ it can’t know if that’s the first character of an identifier or a prefix operator, unless there’s a symbol table or a restricted grammar.
And actually the whole operator parsing situation is fragile. For example, M - min above is valid syntax, but M-min is not. M-min parses as (M-) min, with a postfix - being applied to M, and a null infix operator being applied between M- and min.
Similar with the |x| operator. If the above |Δmin| had been written as the seemingly equivalent |M - min|, it would cause a compile error. The Gezira grammar parses |M - min| as (|M) - (min|), where | is interpreted as a prefix operator in the first and a postfix operator in the second.
I’m not so sure how fundamental this last problem is. It seems to me that outfix operators should always take precedence over infix, like parenthesis. I’m not a PLT guy, so maybe there’s some reason why that can’t be made to work.
<< (N, B ~ C, C) << (A, A ~ B, N)
This then recurses twice, once for each bezier half.
As I’ve said, Gezira is a stream processing language. It takes in an input stream and outputs an output stream. The ∀ block will run until the input stream is empty.
Gezira supports recursion by pushing values back onto the head of the input stream. In this case, after this line runs and the ∀ loops again, (A, A ~ B, N) will get processed instead of whatever was next.
Now for the if branch.
(x, y) = P
(w, _) = P + 1 - (A ~ C)
(_, h) = C - A
>> (x + 0.5, y + 0.5, wh, h)
This is just the simplified rendering equation from above. The beziers, now hopefully small, are treated as if they’re line segments for the purposes of rendering.
In addition to this bezier’s resident pixel, other pixels in its scanline will need to know how much this bezier contributes to them. This is the 4th parameter of EdgeSample.
We see that the pixel coordinates are chosen to be 0.5 offset.
Multiplication happens by just concatenating variables. I don’t know how I feel about that.
In the “official” source, the × operator is used for multiplication. I do know how I feel about that. Not a fan. I admire his commitment to the bit, though!
The ∧(P ≤ A ≤ P + 1 ∧ P ≤ C ≤ P + 1) test is not great. Unlike the other approximation, this one can be arbitrarily wrong.
img(bezier_problem.svg)[A bezier that passes the test, but is NOT contained in a single pixel.]
In this picture we have a bezier whose two endpoints are inside a single pixel, but whose peak extends outside. Because the endpoints are horizontal, the algorithm as described will NOT split, and will compute a coverage of 0 for this bezier. In actuality it should be close to 1, and furthermore the pixel above should be seeing some additional coverage as well.
We’re trying to measure the coverage of a bezier, but we only have the formula for the coverage of a line segment. We’re trying to find a good time to stop subdividing, which happens when the coverage of the bezier is approximately equal to the coverage of the line segment.
The fundamental problem is that Gezira’s algorithm tries to determine when the coverages are close enough by measuring length. We need to measure area instead.
I propose instead measuring the area of the triangle ABC, formed by the two endpoints and the handle. Stop subdividing when the area goes under ϵ.
This metric is good for two reasons:
First, this metric makes constant geometric forward progress. If the triangle represented by the bezier ABC gets subdivided, both triangles of the sub-beziers A(A~B)M and M(B~C)C will measure exactly 1/8th the area of the original triangle ABC.
Second, it directly measures what you’re looking for. The smaller the are of the triangle ABC, the more colinear the points are, and the straighter the bezier. Also, the internal area of a bezier ABC is directly proportional to the area of the triangle ABC, with a ratio of 2/3. So this metric is directly measuring the coverage error per bezier.
Unfortunately there are no cross products or wedge products or determinants already implemented in the Gezira source, so this looks a bit messy. It might look something like this:
DecomposeBeziers () : Bezier >> EdgeSample
ϵ2 = 0.5
∀ (A, B, C)
(a, b) = B - A
(c, d) = C - A
if ∧(⌈A⌉ - 1 <= B <= ⌊A⌋ + 1) ∧ (|(ad - bc)| < ϵ2)
...
And actually, I think the endpoint clamping can be made better too.
Since I’m already talking about approximating beziers with lines, how about cementing this idea? Turn DecomposeBeziers into a function Bezier >> Line, and then have another function that goes Line >> EdgeSample.
Maybe something like this:
type Line = (A:Point, B:Point)
DecomposeBeziers () : Bezier >> Line
ϵ = 0.5
∀ (A, B, C)
(a, b) = B - A
(c, d) = C - A
if |(ad - bc)| < ϵ
>> (A, C)
else
M = (A ~ B) ~ (B ~ C)
<< (M, B ~ C, C) << (A, A ~ B, M)
GenerateEdgeSamples () : Line >> EdgeSample
∀ (A, B)
(w, h) = B - A
(insidex, insidey) = (⌈A⌉ - 1 ≤ B ≤ ⌊A⌋ + 1)
if insidex ∧ insidey
P = ⌊A⌋ ◁ ⌊B⌋
(x, y) = P
(g, _) = P + 1 - (A ~ B)
>> (x + 0.5, y + 0.5, gh, h)
else
(Ax, Ay) = A
(midx, midy) = ⌊((A ~ B) + 0.5)⌋
M = { (midx, (midx - Ax) h / w + Ay), if insidey
((midy - Ay) w / h + Ax, midy), otherwise }
<< (A, M) << (M, B)
That’s 9 additional lines in exchange for some subjective consistency. The rendering formula that is supposedly the basis for this software is expressed in terms of lines. Here’s a function that computes the coverage of lines. The “rendering formula” defines snap and clip, and now the code implements something similar.
There’s also the problem of introducing a new concept, Line. But you could fix that by removing the pointless distinction between Point and Vector.
The other idea that keeps with the spirit of the original source is to subdivide each bezier by the pixel boundaries, instead of at t=0.5. This caps the maximum coverage error per initial bezier at 0.666 per pixel intersected. It’s easy too, since quadratic beziers are just parabolas. It does take more code, though. Enough that you’d probably want to add a new quadratic equation operator.
We want to compute pixel coverages for all pixels in a scanline, but we only have coverage information about the edges in their resident pixel. So some kind of prefix sum or integral or whatever is unavoidable. If we want to do this prefix sum without touching pixels multiple times, the data has to be sorted.
This step sorts the EdgeSamples into scanline order. There will often be multiple EdgeSamples per pixel, but also large gaps between pixels with no EdgeSamples.
I’ll save my commentary about this for the next section.
type SpanCoverage = (x:Number, y:Number, coverage:Number, length:Number)
CombineEdgeSamples () : EdgeSample >> SpanCoverage
(x, y, A, H) = (0, 0, 0, 0)
∀ (x', y', a, h)
if y' = y
if x' = x
(A', H') = (A + a, H + h)
else
(A', H') = (H + a, H + h)
>> (x, y, |A| ◁ 1, 1)
>> (x + 1, y, |H| ◁ 1, x' - x - 1)
else
(A', H') = (a, h)
>> (x, y, |A| ◁ 1, 1)
>> (x, y, |A| ◁ 1, 1)
At this point some EdgeSamples might occupy the same pixel, and some interior pixels will have no coverage computed for them.
This one will merge EdgeSamples that lie in the same pixel, and will also group together “spans” of interior pixels. These interior “spans” will have coverage 0.0 or 1.0, unless I guess your shape isn’t closed? But then again, this whole algorithm won’t work if the shape isn’t closed.
(x, y, A, H) = (0, 0, 0, 0)
Usually you’d start these sorts of loops with a x = min(edge sample xs) or something. But since all xs and ys are always at 0.5 offsets, setting x = 0 works.
∀ (x', y', a, h)
...
>> (x, y, |A| ◁ 1, 1)
You can see here that ∀ is a general looping keyword. In the previous examples, ∀ could have maybe meant map or map | flatten or something. But here it pretty explicitly means for. There’s a prologue and epilogue to the loop, and the loop is meant to run sequentially.
if y' = y
if x' = x
(A', H') = (A + a, H + h)
else
(A', H') = (H + a, H + h)
>> (x, y, |A| ◁ 1, 1)
>> (x + 1, y, |H| ◁ 1, x' - x - 1)
else
(A', H') = (a, h)
>> (x, y, |A| ◁ 1, 1)
This loop body will run in scanline order, thanks to the SortBys last stage.
Same x coordinates accumulate coverage. New x coordinates output twice, once for the old accumulator and once for the span between the old x and new x (which can have 0 length). New y coordinates mark the end of a scanline, so output and reset state.
This is just a prefix sum over each scanline.
At the end of this loop, every pixel inside or on the border of the shape will be covered by one SpanCoverage.
You might notice that the variables A and H aren’t being set. In Gezira, variables are all immutable. To update variables in a loop, Gezira uses the special syntax of appending a ' to it, like in (A', H') = (a, h).
I’m not very familiar with this sort of 2D rendering, so I did a little bit of reading on the subject.
It turns out that this general algorithm, breaking apart curves, sorting, and prefix summing, is actuall pretty common. There are CPU implementations and GPU implementations. This general algorithm is being used to render lots of very big serious projects like link(https://docs.gtk.org/gdk4/cairo.html)[GTK] and link(https://wiki.openstreetmap.org/wiki/Mapnik)[OpenStreetMap] and the major browsers.
This technique wasn’t new when Dan Amelang was writing Gezira. I’ve found code doing something similar link(http://ftp.xfree86.org/pub/XFree86/2.1/2.1-source/)[from the early 90s].
And man, this stuff gets intense. I’m not qualified to talk about what could be improved about this part of Gezira, or what lessons the 2D rendering community has learned in the intervening years. I’ll instead talk very broadly.
There is only one instance of SortBy in the Gezira source. This isn’t necessarily a bad thing, it just gives me pause. All other parts of the rendering algorithm are pretty trivially parallelizable. I just think that an algorithm that requires less sorting would be good.
Dan Amelang talks about this in link(https://fonc.vpri.narkive.com/rtIMYQdk/nile-gezira-was-re-1-ftw)[this email] on the VPRI mailing list. Though, his concerns are a little dated. In the 15 years since, GPGPU programming has made many of his concerns moot.
Personally, but I think that triangles would make things easier. Triangles are a more direct measure of coverage than curves. With triangles there’s no need to do an integral across scanlines. Each one contains its own boundary information.
I can understand why the decision was made to go with curves, but it’s probably not the one I would have gone with. I think triangles are more in line with the mission. For me, a big part of low-LOC and “reinventing computing” for “simplicity” is choosing good primitives. A good primitive is one whose essence answers the question being asked. You’re trying to measure area. The most fundamental structure that embodies area is the rectangle. Rectangles have some issues when they’re not axis-aligned, so the next best is the triangle.
Some of the usual issues with triangles, like issues with small triangles and shared edges, aren’t a problem in Gezira. You just render them together like it’s doing now, and the coverage will always come out correct.
This curve vs triangle critique isn’t a big deal. There are problems involved that I don’t know how to solve. I just think that triangle binning is better than sorting and integrating.
Part of the conceit of DSLs, from a low-LOC point of view, is similar to that of optimizing compilers. You can match patterns in the source code and replace them with larger optimized versions. In terms of LOC, it converts a A*B problem into A+B.
I bring this up because the sum = 0; ∀ x; sum' = x pattern is only used three times in Gezira. Once in CalculateBounds, which just does a running min/max. Once in SumWeightedColors to downsample and filter. And once in CombineEdgeSamples, summing coverage in scanlines.
(Unrelated, but CalculateBounds is weird. I have no idea why it’s written to ignore horizontal lines.)
Gezira currently doesn’t attempt to do any sort of optimization for this. Multithreading is supported in the C runtime, but it’s only pipeline level parallelism. OpenCL ports were planned but never implemented.
Simple pattern matchers live and die on the richness of the source. If the source code can express more intent, the compiler can be much simpler. Gezira currently detects this scenario by link(https://github.com/damelang/nile/blob/8c7690313642652c7361dded5464279929fa7412/compilers/js/nile-ast-eval.js#L99)[looking for ' symbols on variable names].
Dan Amelang has said that the desired parallelism model is both parallelism across elements of a stream AND across pipeline stages.
However, to parallelize a prefix sum you need to isolate the parts of your calculation that are associative. That simply can’t happen with the current syntax. You need to be explicit about this.
This is actually mentioned by Dan Amelang in link(https://fonc.vpri.narkive.com/rtIMYQdk/nile-gezira-was-re-1-ftw)[this email] in the VPRI mailing list:
I suggest ditching the ∀ keyword on these 3 functions and replacing them with another primitive, one that means “prefix sum”.
Just spitballing here, maybe an operator ∫ that takes in an initial value, a variable to bind the “previous” value to, a variable to bind the “current” value to, and a loop body. This loop will bind “current” to the top of the input stream, and “previous” to the bottom of the output stream (in other words, the last value that was output). You can >> zero, one, or two values on any given loop iteration. If you >> two values, it will replace the value at the bottom of the output stream with the first, and then push the second. If you >> only one value, it will just replace the bottom of the output stream. The loop body, expressed as (previous, current) -> (_, new_previous) is required to be associative.
The ∀ operator is able to implement map, filter, as well as certain limited foldr applications. The ∫ operator just described is able to implement reduce, prefix sum, as well as certain limited foldl operations.
CalculateMinBounds () : Bezier >> Point
∫ ∞ min (A, B, C)
>> min ◁ A ◁ B ◁ C
CombineEdgeSamples () : EdgeSample >> SpanCoverage
∫ (0, 0, 0, 0, 0) (cx cy ca ch chh cl) (x y a h)
if y = cy
if x = cx
>> (x, y, a + ca, h + ch, chh, cl)
else
>> (cx cy ca ch chh cl)
>> (x, y, a, h, ch, x - cx - 1)
else
>> (cx cy ca ch chh cl)
>> (x, y, a, h, 0, 0)
Texturing is meant to happen directly after Rasterize. In fact ApplyTexturer and ExpandSpans are the only functions in Gezira that can take in SpanCoverage as input.
ApplyTexturer (t:Texturer) : SpanCoverage >> (Color, PointCoverage)
→ ExpandSpans () → DupZip (→ ExtractSamplePoints () → t,
→ PassThrough ())
Pretty straightforward. SpanCoverages get destructed, and then passed to a “texturer”, which ends up binding pixel position, coverage, and color together.
A Texturer is just an alias of Point >> Color. So a pretty standard fragment-shader-like setup.
PassThrough is a special built-in function, it’s just the identity function. Its output stream is the same as its input stream. It is sometimes written with the special syntax (→). It’s not used much.
The version listed on the demo site is similar. Instead of passing in a Texturer the pipeline is just hardcoded. In the “latest” source there are a couple functions that do the work of making the texturing pipeline for you.
All preprogrammed “textures” in Gezira are gradients. Linear and radial are your two options.
There’s no reason why this has to be the case, it’s just e.g. bitmapped texture functionality isn’t present in the Gezira source. All that’s required is the ability to do single point lookups. So texture UV coordinates would have to be carried in a parallel stream during rasterization.
ProjectLinearGradient (A:Point, B:Point) : Point >> Number
v = B - A
Δs = v / (v ∙ v)
s00 = A ∙ Δs
∀ P
>> P ∙ Δs - s00
This function shows off how parameters work in Nile. They’re a way to pass in values that are constant for the entire input stream.
In the demo source, this is typed as PointCoverage >> Real, to make the pipeline easier.
In the “official” source, this function is called just LinearGradient. I don’t know where the “Project” part came from.
Not much more to say about this one. Nice and succinct.
PadGradient () : Real >> Real
∀ s
>> 0 ▷ s ◁ 1
Here’s that clamping syntax I was talking about!
On the demo page, the source listing is wrong. It should be typed Real >> Real. Transcription error?
I also don’t know why this is called “padding” a gradient. But this terminology is also used in SVG, so what do I know?
This one is split off from LinearGradient because, in the source, there are 2 other gradient manipulation functions: RepeatGradient and ReflectGradient. PadGradient is meant to be useful for both LinearGradient and RadialGradient. I don’t know what situation you’d ever want your linear gradient to go outside of [0,1], but whatever.
Funnily, there’s also a PadTexture, RepeatTexture, and ReflectTexture in the full source. These could be used instead. You can manipulate the incoming Point as opposed to manipulating the outgoing Real. That would have saved 10 lines.
GradientSpan (A:Color, a:Number, B:Color, b:Number) : (Number, Color) >> (Number, Color)
∀ (s, C)
α = (b - s) / (b - a)
D = { αA + (1 - α)B, if a ≤ s ≤ b
C, otherwise }
>> (s, D)
In the demo source, this is written a bit different:
GradientSpan (A:Color, B:Color) : Real >> Color
∀ s
>> sA + (1 - s)B
Not sure why that was changed. In any event, this one is pretty simple too.
ZipPixels () : (PointCoverage, Color) >> Pixel
∀ ((x, y, coverage), (r, g, b, a))
>> ((x, y), (r, g, b, a * coverage))
This one is listed on the demo site but isn’t present in the “latest” source. I’m showing this one because the rest of the source also uses premultiplied alpha. Functions for doing the final composite link(https://github.com/damelang/gezira/blob/9f3e6846f4a1732c344a3b99e5d670deac618b17/TODO#L54)[were planned], but never written. I gather there’s supposed to be some user-provided code to do the final composite and get rid of the alphas?
Not shown are how multiple shapes with different textures are supposed to get composited together. Different versions of Gezira have different ideas about this. In the source we’re using this seems to be missing. In any event, Pixels get blended together Porter-Duff style.
But then you run into the shared-edge problem! If two shapes share an edge, and that edge splits a pixel 50-50, then both shapes will eventually render out to a color value with an alpha of 0.5 for that pixel. When they’re composited together using the usual “Over” strategy, you get a pixel with an alpha of 0.75, letting a bit of background show through. This is a very classic computer graphics problem, whose classic solution is multisampling.
Stroking is done by offsetting a curve in both directions, capping the ends, and then using the rendering functions above to render the stroke as a solid shape.
When I first looked into Gezira, I thought the choice of beziers as the drawing primitive was a little odd. Stroking is one of Gezira’s main features, and it’s well-known that the offset shape of a quadratic bezier is NOT a quadratic bezier.
But that’s actually not a problem. The OffsetBezier function will first subdivide the shape into piecewise nearly linear pieces before stroking.
After learning that, I thought “ah, I see. Beziers are chosen as the base primitive because they come with tangent information at the ends. This makes stroking easier, since there’s no need to join connected curves, which would be hard using this streaming language.”
But no, it does join connected curves. This is interesting because to join curves you need to look at pairs of connected curves to get the angle right.
img(stroke.svg)[A stroked bezier with round caps and mitered joins. The red curve is the original curve. The green is the stroke outline. The black interior fill is what the normal Gezira winding order fill looks like.]
Note the self-intersected geometry in the “elbow” of this curve. This doesn’t affect the visual look of the filled curve. That’s because the winding direction of the self-intersection is the same as the winding order of the rest of the stroke geometry. I think this is fine, and not a big deal.
The functions we’ve looked at so far operate on one item at a time, so we’re about to see something different.
Before I continue, it’s important to note that the hidden stroke demo on Bret Victor’s demo site doesn’t do anything even close to what the source on in the sidebar is claiming that it does. There’s no hope trying to read the page source to figure it out.
Stroking works by duplicating the input stream, stroking one side of the path, reversing, and then stroking the other.
StrokeBezierPath (width:Number, limit:Number, cap:Number) : Bezier >> Bezier
→ SanitizeBezierPath () →
DupCat (→ StrokeOneSide (width, limit, cap),
→ Reverse () → ReverseBeziers () → StrokeOneSide (width, limit, cap))
DupCat and Reverse here are built-in. They does what they say on the tin. Notice that DupCat takes pipelines as arguments.
StrokeOneSide always strokes the left side of a curve (in the normal x-right y-up coordinate system), and on non-closed curves always caps the final curve. Reversing and stroking creates a full closed shape that can be passed to Rasterize. The closed path comes out in the right order too, with a caveat that I’ll mention later.
I won’t list SanitizeBezierPath. It just checks if the control point is roughly colinear with the endpoints, and if so replaces the bezier with one or more that are less pathological.
ReverseBeziers also does what it says on the tin. I won’t list that either.
StrokeOneSide is where it gets weird.
OffsetAndJoin (Zi:Bezier, Z1:Bezier, o:Number, l:Number, c:Number) : Bezier >> Bezier
∀ Zj
→ OffsetAndJoin (Zj, Z1, o, l, c) →
JoinBeziers (Zi, Zj, o, l) → OffsetBezier (Zi, o)
if Zi.C = Z1.A
→ JoinBeziers (Zi, Z1, o, l) → OffsetBezier (Zi, o)
else
→ CapBezier (Zi, o, c) → OffsetBezier (Zi, o)
StrokeOneSide (width:Number, limit:Number, cap:Number) : Bezier >> Bezier
∀ Z1
→ OffsetAndJoin (Z1, Z1, width / 2, limit, cap)
The width parameter is the width of the stroke, obviously. limit is the miter limit, which can be set negative to choose round joins. cap is set positive or negative to choose between rounded or square caps.
If you squint at it, you can see the shape of the pipeline. JoinBeziers emits geometry to join two beziers. OffsetBezier offsets beziers to the left. And there’s some kind of recursion going on. Then at the end, either CapBezier the last curve or JoinBeziers the first and last curve.
But the closer you look at it, the more confusing it is, I think. The new syntax of ∀ x; → Self (x) is very non-obvious in its mechanics. The switch from << style recursion to this more traditional style is also confusing.
Since this snippet is a bit noisy, here’s a simplified version of this pattern:
Stage3 (a: Number, b: Number) : Number >> Number
t = 10
>> (ta + b)
Stage2 (a: Number) : Number >> Number
∀ b
→ Stage2 (b) → Stage3 (a, b)
Stage1 () : Number >> Number
∀ a
→ Stage2 (a)
You do this weird double ∀ thing across two different stages, where the second stage starts with a recursion. Then stage 3 gets adjacent pairs as arguments that you can do what you want with!
Here, feeding the stream (1, 2, 3, 4, 5, 6, 7, 8, 9) into the pipeline → Stage1 () gives back the stream (12, 23, 34, 45, 56, 67, 78, 89), as expected.
So what’s the deal with this new syntax? It seems like a weird hack that depends on the specific way that streams in Nile work. Nile’s pseudocode might look something like this:
handle_function(env, proc) {
// Handle loop prologue.
// This is where pipeline statements would normally go.
// Handle loop.
while (env.input_stream.non_empty()) {
input = env.input_stream.consume();
// Evaluate/deconstruct/whatever the input, bind it to the loop variable, add it to the env's symbol table.
bind(env, proc.loop.vars, input);
// Do whatever the loop body says.
// Normally that involves pushing onto the output_stream or back onto the top of the input_stream.
// Any pipeline statements are run, with the current input_stream.
eval(env, proc.loop.body);
}
// Handle loop epilogue.
}
There are 3 weird things that go into this.
First, the loop ∀ x; → StageN () will consume one item from the input stream before running StageN. This means that StageN will see one less item than StageN-1. So if Stage1 gets run on the input stream (1, 2, 3, 4), Stage2 will get run with (2, 3, 4).
Second, ∀ x; → StageN () will break after StageN runs. This is because a pipeline will link its input and output stream to its parent function’s streams. StageN will run with whatever is left in its parent’s input stream. And after it returns, its parent’s input stream will be empty, so the ∀ will only loop once.
The end result is that the ∀ x; → StageN () pattern has the effect of removing the top item from the input stream before running StageN.
You may have noticed that Stage2 is written as → Stage2 (b) → Stage3 (a, b) and not → Stage3 (a, b) → Stage2 (b). Wouldn’t that mean that the the pairs will come out in reverse order?
Nope. The third weird thing is the handling of processes that don’t consume all the input with a ∀ loop. At the end of their execution, they’re assumed to have an implicit PassThrough stage at the very end.
So if you were to call Stage3 (9, 9) on (1, 2, 3), the output will be (99, 1, 2, 3).
The final call to Stage2 ends with a pipeline in a backwards order like Stage3(8, 9) → Stage3(7, 8) → Stage3(6, 7) ... → Stage3(2, 3) → Stage3(1, 2). Regardless the output will be in the correct order because each Stage3 inserts its own item into the first position.
Also, this means that ∀ b; → Stage3 (a, b) → Stage2 (b) wouldn’t even work; it would infinitely recurse since ∀ b will keep taking one item off and Stage3 will keep putting one back on.
That’s also what’s going on with the weird order of → JoinBeziers (...) → OffsetBezier (...).
The backwards order thing is clearly confusing, because RoundJoin has a bug:
RoundJoin (P:Point, u:Vector, v:Vector, o:Number) : Bezier >> Bezier
ϵ = 0.1
(A, C) = (P + ou, P + ov)
w = (A ⟂ C) ? u
if u ∙ w ≥ 1 - ϵ
N = P + ow
B = N + (N - (A ~ C))
>> (A, B, C)
else
→ RoundJoin (P, u, w, o) → RoundJoin (P, w, v, o)
The last line should be → RoundJoin (P, w, v, o) → RoundJoin (P, u, w, o), not the other way around.
My commentary on this is that it’s all very weird. Like, what a strange syntax for what’s essentially a peek operation.
I’m pretty sure I’ve written pipelines that work like this. But to my credit I also haven’t published that code to the world saying “this is the official way to implement peek in my streaming language, and also this is the Maxwell’s equations of rendering.”
Maybe that was a little harsh. As far as I’ve seen, Dan Amelang has never said the Maxwell line.
Interestingly, there was a peek operator in the language, but it was removed! Here’s a function from an old version of the Gezira stroking system:
PrepareBeziersForJoin : Bezier >> (Bezier, Bezier)
& (A, B, C)
first = 1
D = 0 : Point
E = 0 : Point
F = 0 : Point
∀ (D', E', F')
if first
first' = 0
else
>> ((D, E, F), (D', E', F')) >> ((F', E', D'), (F, E, D))
if A = F ∧ first = 0
>> ((D, E, F), (A, B, C)) >> ((C, B, A), (F, E, D))
Here the & operator is peek, binding to (A,B,C). Presumably & was chosen because Dan didn’t have time to pour over the unicode table to find something else, and so he begrudgingly using a character already on his keyboard. Whincing with every keystroke. Maybe that was a little harsh too.
Personally, I don’t see what’s wrong with peek. It’s a very normal thing to do with streams. It’s the most obvious way to implement join/cap.
Another thing to note is the different kind of recursion. In the rasterization code, recursion was done with the << operator.
OffsetBezier (Z:Bezier, o:Number) : Bezier >> Bezier
ϵ = 0.1
(A, B, C) = Z
(u, v) = (A ⟂ B, B ⟂ C)
M = (A ~ B) ~ (B ~ C)
if u ∙ v ≥ 1 - ϵ
w = (A ~ B) ⟂ (B ~ C)
D = A + ou
F = C + ov
N = M + ow
E = N + (N - (D ~ F))
>> (D, E, F)
else if A ≠ B ≠ C
→ OffsetBezier ((M, B ~ C, C), o) → OffsetBezier ((A, A ~ B, M), o)
Here, the job of OffsetBezier is to emit beziers that are offset to the left. If the bezier isn’t straight enough, split and recurse.
In the rendering code, this would have been implemented with >> and <<. But here it can’t. Because it can’t have a ∀ loop in its body. Because its input stream isn’t being fed raw beziers, only already-offset beziers. Because the raw beziers aren’t being stored in the input stream, they’re being stored in the call stack. Because of this weird way of writing peek.
The ∀ x; → syntax has weird semantics. You gain the ability to write cursed functions like this:
Cursed () : Number >> Number
-- Discard the first number >= 10, leaves the rest.
∀ x
if x < 10 = 0
>> x
else
→ (→)
I think the semantics of ∀ should be “the following block gets run for every item in the input stream”. Why else name it ∀?
I think the stroking system begs the question of why there are two versions of recursion. The ∀ x; → Self concept can do everything the << concept can and more. So why have both?
Surprisingly, my suggestion for all this would be to not change much.
First, the thing about the backwards function application doesn’t bother me. It’s the same order for the <<, so it’s consistent. I just find it funny.
The stroking system is the only place in Gezira that does this. So we just need to replace this pattern in the stroking system with something else.
I don’t suggest trying to disallow the ∀ x; → syntax or even changing how it works. I think that’s a lot effort for no real gain. If the only instance is removed, I think that’s fine.
Part of the reason for structuring the stroking system like this is to gain the ability to use functions in Gezira like functions in other languages. Dan structured the Gezira code so that miter join generation happens in MiterJoin, etc.
But if you have a syntax for calling functions, you’re one step away from recursion. And now you’re back to having 2 kinds of recursion in your language.
We already have something like regular functions in Gezira. They’re called operators. If you want to keep the code for the different caps and joins separate, I suggest turning them into operators.
It would be nice if there was a way to call Gezira functions like functions in a normal language, one input. Like if OffsetBezier was a function that OffsetAndJoin could use, but also a was a standalone function that could be called in user code to offset beziers.
Note that CapBezier and friends are NOT that currently. Despite looking like a function Bezier >> Bezier, they don’t operate on any items in its input stream. So turning them into operators doesn’t lose you any functionality.
Finally, I think the addition of a RotateOne function would let you get rid of the ∀ x; → peeking pattern. It would take the element on top of the input stream and put it on the bottom. You can implement RotateOne using the current syntax like this:
AppendEnd (end: Number) : Number >> Number
∀ x
>> x
>> end
RotateOne () : Number >> Number
∀ x
→ AppendEnd (x)
Now you could zip pairs together:
StrokeBezierPath_2 (width:Number, limit:Number, cap:Number) : Bezier >> Bezier
→ SanitizeBezierPath () →
DupCat (→ (→),
→ Reverse () → ReverseBeziers ()) →
OffsetBezier_2 (width) →
DupZip (→ (→),
→ RotateOne ()) →
OffsetAndJoin_2 (width, limit, cap)
OffsetBezier_2 is like OffsetBezier, only now it’s a properly operating on its input stream. A modified OffsetAndJoin_2 receives adjacent (Bezier, Bezier) pairs in its input stream, along with 2 (start, end) and (end, start) pairs in the appropriate spots in the stream.
In the original code, caps were only ever added to curve ends, and joins were always applied between adjacent no matter what. But what if the stream contains just 2 beziers that aren’t connected? The join will be messed up, and there won’t be enough caps.
I suggest instead making the determination just based on bezier pairs. If adjacent pairs are touching, emit a join. If they aren’t touching, emit a cap.
OffsetAndJoin_2 (o:Number, l:Number, c:Number) : (Bezier, Bezier) >> Bezier
∀ ((A, B, C), (D, E, F))
-- offset (A, B, C)
if C = D
-- endpoints are touching, this is a join
else
-- endpoints are not touching, this is a cap
Interestingly, Gezira used to have Mix and Interleave builtin functions that solved this with a slightly different approach. But they were removed at some point, and I don’t know why.
I think I really scraped the bottom of the barrel on everything interesting to say about Gezira. Here are some extra things for looking into if I ever find myself wanting more.
I didn’t really look at the filtering code in Gezira. I’m not too interested in it at the moment, but it’s there.
There’s a tons and tons of code link(https://tinlizzie.org/updates/)[here], and I have no idea what any of it does. It’s almost certainly an interesting dive into the history of Squeak (of which I know little), VPRI, and Alan Kay’s projects.
I want to mention link(https://github.com/Twinside/Rasterific)[Rasterific], if only because of how much work was put into it. It’s a Haskell reimplementation of Gezira. It emulates the Gezira algorithm, but all in Haskell. It also significantly expands the set of operations. There are cubic beziers, dashed strokes, and more!. It was started back in 2013.
I said at the beginning that Frank was never released. However, there is a build for iPad link(https://tinlizzie.org/~bert/frank4ipad/)[sitting on the tinlizzie server]. I don’t have an old 2011 jailbroken iPad sitting around, but I think it’d be super cool if someone installed it showed it off.
Learn more about HARC? Why did the funding go away? link(https://web.archive.org/web/20240314183910/https://harc.ycr.org/)[Here] is the last archived copy of HARC’s website.
What are the main people up to these days?
Alan Kay is getting up there in age. He still makes public appearances, but I haven’t seen any evidence of him doing any more research or development. He’s 85 years old now.
That mustache he rocked for the last 50 years has now turned into a full Santa Claus beard. Why? That’s probably what this post should have been about. No one gives a fuck about this Gezira shit. What happened to the ‘stache? The people need to know!
Alex Warth: still active, still doing much the same sort of research. I saw the talk he gave at at (with?) the Ink & Switch people last year.
Dan Amelang: who knows? He’s very much the main character of this post, but outside of this work I don’t know much about him. He’s still alive. As for what he’s working on? No idea.
Professor Ian Piumarta: still active, still doing much the same sort of research.
Vanessa Freudenberg: still active, still working on lots of Smalltalk and Squeak stuff.
Yoshiki Ohshima: still quite active. Tons of projects. He updates link(https://tinlizzie.org/ohshima/)[https://tinlizzie.org/ohshima/] often with his new projects and accomplishments.
I definitely think there’s directions to take the base Gezira, if someone wanted to take up the mantle.
In my opinion, edge sharing is the single biggest problem in Gezira at the moment. If two polygons share an edge, there should be no visible gap.
The other obvious next steps are analytic temporal AA, support for animation, and a 3D version.
I made a couple changes that allows me to do subpixel rendering:
img3(letter_g.svg)What is a subpixel rendering demo without text? This is Liberation Serif’s g.Subpixel coverage.[Simulation of what this looks like rendered.]
I think the Compositor subsystem is too much. I think with enough work it can be made drastically simpler.
I’m not clued in to the advances in 2D rendering over the last couple decades. Are there any appropriate order-independent transparency techniques?
Alan Kay once wrote, in link(https://www.quora.com/Why-do-many-projects-done-by-computer-researchers-eg-Bret-Victor-or-the-VPRI-remain-closed-source-even-though-papers-get-published-about-them)[a post on Quora] about releasing some more VPRI artifacts:
people cannot resist “interpreting” the work of others (and usually forget they can only do this in their own contexts, which if the researcher is in a different context, will lead to nonsensical garbage, which nonetheless will be put out on the web to join the rest of the garbage).
Harsh, but point taken. I hope that my shitty opinions rise above the level of garbage.
It’s true that my context and Amelang’s are different. My context for Gezira is that of a historical curiosity, a completed product, and some unexplained mysteries. But none of the keystrokes Amelang made while writing Gezira where made with any of those contexts. It’s likely that the final keystroke was made to Gezira with the intent to revisit it again soon.
Hopefully I didn’t get anything too egregiously wrong, or take things too far out of context. I tried.
I feel I aught to address my opinions on this whole thing.
The whole conceit, the practicality and beauty and rightness of a computing stack redone through radical simplicity, is a siren song to me. Distressing, impossible to ignore, and dangerous.
I also think that such an endeavor is doomed to fail. I have so many thoughts on this, from so many different angles, I couldn’t possibly write them all down here. If you asked on a hundred different days why I think this, I would give you a hundred different answers.
That being said I try to follow the call in my own way. I’m writing this post in a homemade text editor, building the site with a homemade static site generator, on one of those build-your-own linux systems called Guix. I have tons of homemade tools that I use every day, on my computers, my phone, my watch, my home. Every time I use a piece of software someone else wrote my first thought is “I could definitely make my own version.”
If I were running Fedora, I’d alias yum to yuck.
Let’s elide any discussion of what these behaviors mean about me, and if they’ve affected my life in a positive or negative way.
I read a lot about weird computing systems and computing models and other big theory-of-everything projects like the STEPS. Probably far more than is healthy. Ranking the VPRI among them all, I’d give them a thumbs up. Pretty cool.
The first couple years saw tons of progress. If that velocity had been maintained through the years, that would have been incredible.
The progress reports are nice, but they aren’t that detailed. The more traditional papers were nice, and I would have loved to see more of those! The irony here is that Alan Kay has probably said more words on camera than I’ve said in my life, and written more words for interviews and magazines and promotions that I’ve written in my life. But I don’t want to keep hearing your Maxwell’s equations metaphor! I want teardowns!
I feel I’ve been spoiled when it comes to this. I tune in monthly to read 100 rabbit’s progress reports. The entirety of Dynamicland’s archives are an incredible read. I get to live vicariously through these, and others.
They are a safe way of engaging with projects and ideas that enamor me. I don’t have to deal with the messy, human part of these projects. I don’t have to deal with my own emotions about messing up something others depend on/find joy in, or about publicly falling short.
Most of all I don’t have to be in the thick of it, see all the gory details and compromises, and see the magic fade away.
Speaking of fading magic, that brings me to my next question: did Gezira accomplish its goals?
Did Gezira accomplish the goal of being Frank’s rendering system with a small LOC footprint? It’s undeniably very small for its capabilities, and it successfully powered Frank. So yes.
Gezira may have accomplished LOC its goal, but I don’t know about all of the surrounding infrastructure. The Nile C runtime clocks around 2000 lines of C. The Maru source is around 10kLOC of C, and another 10kLOC of lisp.
In an email conversation that I had with Alan Kay, he said:
I was interested in the much more compact expression of the semantics, and looked around for people of similar interest. (…) The initial versions of Gezeira ran surprisingly well, and this tempted me away from the original goal, towards wanting to give demos and talks using it. Similarly, with Frank.
I’d say that seems right. For example, the Nile C runtime uses a good bit of its line count doing tons of MPMC threaded job system stuff. There’s a work-stealing system in there. That’s definitely going against the stated goals in order to appear impressive in a demo.
Does Gezira succeed at being the Maxwell’s Equations of Rendering? Or does it succeed at being “runnable math” (another of Alan Kay’s favorite phrases)?
I say no. You can’t manipulate Gezira functions to discover new facts about rendering. The standard I’m using for true “runnable math” would be the link(https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/9580/9580.pdf)[work of Gerald Sussman].
Does it succeed at being inspirational? Is it more that the sum of its parts? I say yes.
Now finally, my overall opinion: I like Gezira. I wouldn’t have written all this if I didn’t.
I like almost everything about it. I like the goal, I like the execution. I like how much was done with so little. I even like the goofy parsing behavior! I think it’s endearing.
I like how I’m drawn to write my own version.
I think the current state of it is a little sad. There was clearly so much effort put in. How many different complete reimplementations were written by Dan in different languages? And of them, how many even run today?
I also think the internet discourse around it is lacking. Too much mystique. I’m the only one allowed to uncritically venerate things!
I’m glad that something like this exists.
