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 https://www.youtube.com/watch?v=UxGxsGnbyJ4&t=80s
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?
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 https://www.youtube.com/watch?v=UxGxsGnbyJ4&t=80s
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?