Implicit Surfaces & Independent Research

For a given (x, y), you color the pixel black if you're outside of a shape, and color the pixel white if you're inside the shape. The math formula is a way to describe the contour of the shape. To tell if you're inside or outside of a shape, you plug in your (x, y) coordinate into the math formula, and if the output is > 0, then you're outside. If the output is < 0, then you're inside. I think they call it a signed distance field. You should watch his talk that explain it. It's really great. ▶ this video

I'm thinking that we can parse the input into an expression tree, and then for each x coordinate, have each node in the tree tell us which intervals of y coordinates it would return a value < 0 (or <= 0 without loss of generality). Since we're basically dealing with real numbers we can pretend true 0 doesn't exist. Composing these intervals is trivial for all operations except addition/subtraction. (For example, `mul` is less than 0 if exactly one of its arguments is less than 0, `neg` is less than 0 if its argument is not less than 0, `min` less than 0 if either of its arguments is less than 0, etc.). And then we define add(a, b) as sub(a, neg(b)). So then we only need to work out which y values sub(a, b) will return a negative result for. sub(a,b) is negative when a<b. We can have the sub() node asks its 2 child nodes which values they would return a negative result for. Every y coordinate where a gives a negative result and b gives a positive result is a y coordinate where sub(a,b) is negative. Every y coordinate where a is positive and b is negative is positive. For the remaining y values I think we have to actually evaluate the children and find out which ones give a negative result. Obviously memoise the evaluation so that we don't repeat any work, and turn the expression tree into a DAG by combining any identical nodes. Some subtrees won't contain var-x, so the memoisation of those nodes can persist across different x coordinates. And then for each x coordinate we ask the expression tree to tell us which y coordinates give negative outputs, and plot those. It's possible that the idea would generalise to 2-dimensional intervals, not sure. I haven't implemented this yet but I'm planning to try it out, but to be honest I don't expect it to be faster than Matt's GPU version based on recursive subdivision with interval arithmetic. Btw his talk is great ▶ this video And, a second fun challenge would be to reverse engineer the input file to extract the font! I expect the file is basically a union of x/y translations of functions that plot individual letters, so it shouldn't be crazy hard to split out the top-level union, then split-out the x/y translations, and then collect the letters. It's possible that it's more complicated though. In particular, is each character translated in x/y individually, or is each character translated only in x to form each line of text, and then the line as a whole is translated in y? Or something weirder?

> What are the practical implications of this kind of assembly language? Surely there’s more efficient means of describing 2D SDFs? By analogy, you wouldn't program in LLVM IR, but it's a useful intermediate representation for a bunch of higher-level languages. Higher-level tools can target this representation, and then they all get to use a standard set of optimizations and algorithms (fast evaluation, rendering, etc). (I gave a recent talk that's a broad overview of this research: ▶ this video) > My next thought would be to evaluate the program at a low resolution to create a low res SDF texture for the shader to draw at a higher resolution. Glad you're enjoying the challenge! You may also be interested in link