Graphing Out a Glanville Fritillary with Polar Equations
and in the process pushing Desmos to its limit through automated generation
Introduction
My Honors Precalculus class, taught by Dr. Tong at Concordia International School Shanghai, was assigned a project involving the usage of polar curves to graph out a butterfly.
My experience with using Desmos to create detailed representations of things started out long before the polar project was even announced, as I had a friend who went on a long undertaking to graph out a periodic table in Desmos. This had me thinking about an immediate or text representation of Desmos graphs since such could be easier to work with especially when dealing with long or repetitive graphs and expressions.
The polar project was introduced, but there were still months before it would be formally defined as a project and quite some time before the unit for polar equations, conics, and parametric equations was covered. This gave me a lot of time to brainstorm about it and I came up with a lot of ideas.
First was the idea of using regressions to fit conics to points. I didn’t have much knowledge about polar equations and was quite fascinated at how it seemed just about any kind of graph could possibly be made with enough trigonometric functions (take a look at https://www.desmos.com/calculator/oyl99kqsk7 from the Desmos examples). As such I was considering whether I could have some sort of polar regression to explore the space of possible equations more rigorously. Ultimately, I limited the butterfly to only conics, but these thoughts were what inspired me to use Desmos’ regression capabilities.
Then came getting the points needed for regression from the image itself, which came from an exercise I had done quite a while ago creating image filters, where one would highlight the edges or places where the color changed. Combining the results of a filter like that with all the points of an image as some sort of weighting for a regression could allow it to automatically use the right points to regress. Desmos’s built-in regression doesn’t have any concept of these weights (unless I tried duplicating a point a few times to make it more significant, but that would hit list size limits quickly) so I ultimately ended up with a different process for getting points to regress, although it still involved isolating the edges of an image.
Dr. Tong also mentioned ideas about “making the butterfly fly”, or having the butterfly actually animated and flapping and moving around. I thought of how I could use a set of 3D points being multiplied by a changing transformation matrix combined with a perspective matrix, taking ideas from 3D computer graphics and the matrices unit. At the time I was leaning more towards trying to automate the process as much as possible while sticking closely to Desmos, while this would require figuring out an entire back wing that wasn’t in the image I choose (figure 1), so I didn’t pursue this further, although I could see how these could be used in another one of Dr. Tong’s projects.
Now, onto the actual process of creating the butterfly.
Process
A Text File Representation
I started by trying to get a text file representation of a demos graph working. Using Desmos’s api (https://www.desmos.com/api/v1.7/docs/index.html), I was able to create something where you could type into a textbox and the text would be sent as LaTeX into the api and become actual equations on the graph. Then I added some more features such as more ergonomic names (no more n_{ame} for multi-letter variables, instead just name) and the ability to evaluate JavaScript to generate some of the more repetitive equations more easily.
Loading the Image
Next, I tackled the issue of loading the image into Desmos. Desmos’s built-in image feature wouldn’t work because there is no way to sample the image, so instead I would have to store the information of the image in lists. Since Desmos’s lists can only have up to 10,000 elements, a 1040x643 image simply couldn’t fit in a single list.
The simplest way of storing the image involving lists would be using the format of [red, green, blue, red, green, blue, …]. This would only be able to store 3,333 pixels per list, which meant that hundreds of lists would be needed to store the whole image. Because I wanted to avoid having more image data lists than useful equations, I thought about whether a more compact representation was possible.
The first realization I had was that the RGB color values really only go from 1–255 (take up 8 bits), this meant that each number in a list could store more than 1 value. Trying to figure out how many bits a number in Desmos could represent led me to 53, since JavaScript only supports 64-bit floats which can represent integers up to 53 bits. I figured out that using the entire 1–255 range of values for color wasn’t necessary, and that even with 2-bit values (r, g, and b only going from 0–3), the image still looked good. If I was able to store 2-bit colors as bits of the 53-bit integers in Desmos, each number would be able to store over 8 colors and thus over eight pixels of the image. This would mean only 8 lists would be needed to store the image.
To achieve this, I built out a general buffer where you can check the value of any bit in the buffer (figure 3), then used this buffer in functions that would get the r, g, and b values from a certain position on the image.
Explanation:
- Getf(bit, float) -> gets the `bit`-th bit from `float` as 1 or 0: this is best understood by looking at what happens in binary assuming a float64 is a 53-bit integer.
1 1 1 1 … 1 1 1 1. (binary)
= 1*2⁵² + 1*2⁵¹ + 1*2⁵⁰ + 1*2⁴⁹ + … + 1*2³ + 1*2² + 1*2¹ + 1*2⁰
The first modulus by 2^(54-bit) “gets rid” of the upper portion of the number to the left of the needed bit.
For example, taking the third bit (bit = 3) means modulus by 2⁵¹, which zeros all bits at or above 2⁵¹ (the first 2)
0 0 1 1 … 1 1 1 1. (binary)
= 0*2⁵² + 0*2⁵¹ + 1*2⁵⁰ + 1*2⁴⁹ + … + 1*2³ + 1*2² + 1*2¹ + 1*2⁰
Then the value is divided by 2^(53-bit), moving the decimal point to the wanted 3rd bit (moved to after the third significant bit since it becomes 1*2⁰ = 1)
0 0 1. 1 … 1 1 1 1 (binary)
= 0*2² + 0*2¹ + 1*2⁰ + 1*2^-1 + … + 1*2^-47 + 1*2^-48 + 1*2^-49 + 1*2^-50
Finally, the floor is taken discarding everything past the decimal point, leaving us with the value of the third bit
0 0 1. 0 … 0 0 0 0 (binary)
= 0*2² + 0*2¹ + 1*2⁰ + 0 (discarded by floor)
= 1
- Getl(bit, list) -> gets the `bit`-th bit from a list `list`: this builds on Getf(), for the first 53 bits it calls Getf on the 1st value in the list, and for the next 53 bits it calls Getf on the 2nd value in the list subtracting 53 first from the bit, and so on using modulus to keep the bit passed to Getf in the range of [1, 53] and the ceiling of dividing `bit` by 53 to get the index
- Get(bit) goes further using a piecewise function to switch between lists allowing multiple lists to be involved in one contiguous set of bits, the JavaScript evaluation was very useful for generating this piecewise expression.
Now, with the data stored and accessible, I could display the image as a point cloud, as shown in Figure 4 (it is upside down because in many computer graphics systems including JavaScript’s canvas y decreases as you go up, and I got the image data into Desmos by getting points from a JavaScript canvas with the image drawn on it).
Generating Polar Curves
Next came the step of using the image data to generate polar curves. I came up with processing the image into edges of each color and trying to regress conics in rectangular form to those edges, if the regression was too poor (low r² or joining separate clusters of points together that shouldn’t be joined) the image would be split into four smaller images and the regression attempted for each image. The idea here was that eventually, each subdivided image would only include one edge, making it easy to fit a conic to it. This process would have to be done in 100x100 portions of the image since greater dimensions would hit the 10,000-item list size limit.
To achieve this in Desmos, I had to look at the “advanced features” Desmos had, actions and the ticker. Actions in Desmos allow you to set a variable to something else (action a -> 2 would when run set the variable a to 2), tickers can run an action repeatedly, and these two combined with piecewise functions created a Turing complete system (something being Turing complete essentially means that it is able to do any computation that a computer can do, specifically it can replicate a “Turing Machine”).
I created an action (v_ticker in the Desmos graph), and in it placed a massive piecewise function. The piecewise function checks the value of i which acts similarly to a program counter or instruction pointer. Each branch of the piecewise function would by default increase the value of i allowing a sequence of actions to be run in successive ticker iterations. A subbranch could also set the i value to anything, so by setting it to a previous value I could have loops, and by jumping ahead and skipping branches if a condition was/wasn’t filled I could have a conditional if statement. With sequentially run series of actions along with the ability to create loops and conditionals, what I had was a rudimentary programming language that would run fully in Desmos.
Here is a small snippet showing these capabilities:
The piecewise function (lines 4–8) shows a sequence of actions first doubling `a`, then setting `b` to this value of `a`, then reducing `a` by 1 (the actions towards the right of the image).
The actions near the middle of the image describe the control flow. At i = 0 or i = 1, the system simply progresses to the next action (i -> i + 1), at i = 2, i only progresses if a >= 100, otherwise going back to 0. This shows a do while loop akin to:
To begin creating the system for generating conics I started with some pseudocode.
First, I figured out how to do the regression, as indicated by “do regression” in Figure 7.
Just using the general equation for conics 0 ~ Ax² + Bxy + Cy² + Dx + Ey + F (~ in Desmos indicates a regression) didn’t work. This took a while to solve because it was two problems. I used the lowercase ‘e’ as a variable which Desmos treated as Euler’s number leading to confusing results. Once that was dealt with I found out that having all the regression variables at 0 would regress to any set of points making the results pointless. To fix this, I used capital letters, and I replaced the F term with 1 to prevent all 0s from being a solution. After this another issue arose from very large or small values being needed when the conic wasn’t near the origin. The extremeness of these values messed with the r² calculation, making it so that portions of the image further from the origin would have r² that were biased to values higher than they should be. To solve this, I added a step first normalizing the points the regression was being performed on to [-1, 1] in both x and y, and later de-normalizing the values when graphing them out, which fixed this issue but complicated the equation. Finally, I added a restriction { 4AC -B² ≥ 0 } to prevent hyperbolas from being used.
This worked well so I set out to convert the output of the regression to polar form. This was complicated by also having scale and offset values due to needing to undo the normalization but still was relatively straightforward to work out. By replacing x with r sin(theta) and y with r cos(theta) and then expanding out the expression before factoring down again, I got 0 = (a bunch of values) r² + (a bunch of values) r + (a bunch of values), which I could solve with the quadratic formula to get an equation linear in r that Desmos was willing to graph. The specific values in (a bund of values) were quite lengthy, with Xo (x offset), Yo (y offset), Xs (x scale), Ys (y scale) representing a transformation and As, Bs, Cs, Ds, Es representing the regression results nearly always used each term.
Next, I got enough of the algorithm to process a single color for a single 100x100 square implemented relatively straightforwardly. Although there were challenges where I couldn’t have any variable ever in an invalid state such as a list of “undefined” when it was used as a list of points. Because each run of the ticker still used the entire piecewise function, even if the specific branch determined by `i` worked, if any other branch was in an invalid state the function would fail. This was particularly challenging because a Desmos list comprehension can’t run zero times, so having empty lists would often lead to invalid states forcing workarounds such as using long lists of zeros as starting values and using a variable that could be an empty list without issues as an intermediary when filtering a list that could become empty after the filtering. Another issue was that I was getting a strange error from within Desmos itself, something relating to tree depth being too great. This required tweaking the max tree size in the highly obfuscated code gotten from the api, but once it was increased by a factor of ten things worked smoothly. This issue doesn’t occur when using the calculator at desmos.com and only when using the calculator the api provides, but still can be considered as finally reaching the limits of Desmos.
At this point, I started going a bit off track as I lost sight of the fact that I planned to use the full-resolution image and every color for the butterfly.
I started iterating with many tweaks to the algorithm I had so far, without finishing the very important steps of having multiple colors and the entire image being processed. These iterations did improve how the results looked, but since I was iterating with just one color on a greatly zoomed-in image, I could not be sure these improvements would transfer over to the final large image with all colors. Some didn’t, wasting the rapidly dwindling time I had left.
An example of this was that instead of implementing the processing of the entire image I tried to put a 100x100 scaled-down version of the butterfly in instead (figure 9). This combined with many similar experiments greatly delayed me simply running the entire algorithm. This stalling of progress meant that I was already well past the original deadline when I finally noticed the performance issues, how the already slow process would as it progressed get even slower to the point that it may have taken 4–5 days to fully calculate.
Optimizations
There were two optimizations that I did, which ended up greatly improving the speed of generation. The final generating only took 2 days while the unoptimized version was only able to get to around halfway done in 2 days.
First, was removing the overhead by going through the entire process described in Figure 3 to get any information about the image. The old system would rely on these functions for every single regression or attempt to regression, but by loading the 100x100 portion of the image being worked on into three simple lists functioning as a cache, accessing information became much faster, with the slow Figure 3 functions only needed to generate the cache each time the system moved to a new 100x100 portion of the image.
This improved things, but the process still slowed down quickly after running for a while. I was able to narrow it down to the result lists which stored the values from previous regressions along with some other information like color. As these lists got to the thousands, the time spent copying each value into the join function I used to append to the list became greater and greater slowing the generation. To fix this, I created a new set of lists as a group of staging buffers, which would be added to the main buffer once they each got to 100 items long. This meant that most of the time you would only be dealing with short staging lists and only occasionally adding to the large result lists, saving a lot of time.
Even after these two optimizations, the issue of it slowing down still existed to a lesser extent and it still took 2 days and 1 night to complete, but this represented a great success of having it actually finish without taking an exorbitant amount of time.
Final Result
To create the final result, I moved the graph from the text to Desmos converter I had to the desmos.com website, taking advantage of the Desmos API again. Then I organized the equations better and shifted the butterfly so that it was properly centered. Here is what I got:
Future Improvements
I think the most obvious issue with the current result is that it uses too many equations. While I could try fixing this with a trivial adjustment of parameters (there is a minimum size parameter that could be increased), I think deeper improvements can be made by improving the detection of edges. If you zoom into the butterfly’s wing (figure 14), you will see how messy and seemingly nonsensical some of the conic generated can be, there is a definite lack of fitting edges here. If I’m ever going to improve this, I’d probably have to improve the rate that I can iterate and see results, because needing 10s of minutes to generate a 100x100 piece when there are a lot of colors won’t cut it. Doing this would probably involve leaving Desmos, but having still Desmos be a usable output format would still be great even if the calculations can’t all be done in it. If I were to keep working on this, I would try to clear up the messiness by improving edge detection. To do this I’ll probably need to go beyond simply checking if adjacent colors are different when getting edges, instead sharpening or removing “fuzzy” bits and appreciating how colors can change, although a much simpler filter could also be effective. The ultimate goal would be to have it create images that are far more human-like, with fully closed shapes, while still retaining detail down to small collections of pixels (the current minimum size is 12 so 12x12 square is the smallest detail right now).
