--- title: "Iterated Function Systems" description: "An interactive IFS fractal renderer that started in Three.js, followed by a GPU-accelerated Python version using Taichi." tags: - "Computer Graphics" - "Fractals" - "Python" - "Taichi" canonical: "https://portfolio.rospo.dev/projects/ifs" html: "https://portfolio.rospo.dev/projects/ifs" --- # Iterated Function Systems Iterated Function Systems (IFS) are a mathematical framework for generating fractals using a set of affine transformations. In other words, we have some matrices that may rotate, scale, and translate points in a plane. By applying these transformations repeatedly to an initial point, we can create complex and beautiful fractal patterns. One important condition for the transformation is that they must be contractive. You can think of this as the transformation "pulling" points closer together, which is essential for the fractal to converge to a well-defined shape. [Open the browser demo](https://portfolio.rospo.dev/demos/ifs-js/index.html) The Chaos Game is a popular method for visualizing IFS. It involves randomly applying the transformations to a point and plotting the resulting points on a graph. Over time, as more points are plotted, the fractal pattern emerges. That is, for each point, it randomly selects one of the transformations and applies it to the point, then plots the new point. This process is repeated many times, and the resulting points form the fractal pattern. ### Starting with Three.js I came across IFS from a [YouTube video by Acerola](https://www.youtube.com/watch?v=1L-x_DH3Uvg), who demonstrated the concept. The first time I attempted this, I implemented a very simple IFS implementation in Three.JS. [Open the interactive demo](https://portfolio.rospo.dev/demos/ifs-js) (Note: this is not the original implementation, but a version that integrates changes from the later Taichi implementation.) While this version was functional, it was not very efficient or good-looking. The rendering was relatively slow, which limited the number of points I could plot and resulted in a "thin" looking fractal. The transition between transforms was not smooth, which made the fractal seem to "jump" around rather than smoothly transitioning between points. ### Trying it in Python Overall, while the Three.JS implementation was a good starting point for understanding the basics of IFS, it had significant limitations in terms of performance and visual quality. A few years after I first implemented the Three.JS version, I decided to create a more efficient and visually appealing implementation using Python, specifically using the [Taichi](https://www.taichi-lang.org/) library. Taichi is a high-performance programming language that is designed for graphics and numerical computations. It allows for efficient parallel processing, which is crucial for rendering large numbers of points in an IFS. ### Why was it still slow? When I first implemented the Taichi version, it was not significantly faster than the Three.JS version. At first, I was okay with this, as I was more interested in trying to enhance the visual quality of the fractal. However, I soon realized that the performance was still a bottleneck, and I needed to optimize the code further to achieve the desired results. I'd been using Github Copilot to help me write code, and I decided to ask it for help in optimizing the code. Copilot suggested several optimizations, but none of them were significant. When I finally used `nsys` (NVIDIA's profiling tool) to analyze the performance of the code, I found that the kernels, or code that actually runs on the GPU, were taking up only 0.1% of the total execution time. The remaining _99.9%_ of the time was spent on memory transfers between the CPU and GPU. This was a significant bottleneck, and I realized that I needed to optimize the memory usage of the code to reduce the amount of data being transferred between the CPU and GPU. For context, over 20 seconds, 60GB of data was being transferred between the CPU and GPU, which is a huge amount of data and explains why the performance was so poor. However, there really wasn't a whole lot I could do to optimize the memory usage of the code. Each point is just 6 floats (x, y, z, r, g, b). I was already using standard 32-bit floats, as 16 bit floats start to lose precision and have a noticeable impact on the visual quality of the fractal. I was kind of stumped as to how to improve the performance of the code, as the memory usage was already quite low. ### Keeping the points on the GPU But think back to the problem: **memory transfers between the CPU and GPU are the bottleneck**. This means that the issue is not necessarily with the amount of data being transferred, but rather with the frequency of the transfers. If I can reduce the number of times data is transferred between the CPU and GPU, I can significantly improve performance. To achieve this, I made as much of the data as possible reside on the GPU, and I minimized the amount of data that needed to be transferred back to the CPU. Because nearly all of the calculations are very standard GPU-friendly operations (matrix multiplications, trigonometric functions, etc.), all of the transformations and point updates can be done on the GPU without needing to transfer data back to the CPU. This still didn't solve the problem entirely, as I still needed to transfer the final points back to the CPU for rendering. Shockingly, I remembered that a Graphics Processing Unit (GPU) is, in fact, designed to process graphics and not just do matrix multiplications, and could probably render the million points directly on the GPU. This was one of the times that Copilot was extremely helpful, as when I told it to implement a GPU-side particle renderer in Taichi, it was able to generate a working implementation that rendered the points directly on the GPU without needing to transfer them back to the CPU. This was a massive improvement in performance. Before the optimization, the code was transferring data between the CPU and GPU every frame, which was a significant bottleneck. After the optimization, the code only needed to transfer data once at the beginning to initialize the points, and then all subsequent calculations and rendering were done on the GPU without needing to transfer data back to the CPU. The only data that needed to be transferred back to the CPU was the final rendered image, which is a much smaller amount of data compared to transferring all of the points every frame. ### How much difference did it make? From some back-of-the-envelope calculations: - The image is 720x1280 pixels, which is 921,600 pixels in total. - Each pixel is represented by 3 bytes (RGB), so the total amount of data for the final image is 921,600 pixels \* 3 bytes/pixel = 2,764,800 bytes, or approximately 2.76 MB. - In contrast, transferring 1 million points with 6 floats each (x, y, z, r, g, b) would require transferring 1 million points _ 6 floats/point _ 4 bytes/float = 24,000,000 bytes, or approximately 24 MB. This 10x reduction in data transfer led to a corresponding **~10x improvement in performance**. Before optimization, my 3090 was able to render 1 million points at around 10-20 FPS. After optimization, it was around 100-200 FPS. It can now easily render 10 million points at around 30-60 FPS, which is a significant improvement in performance and allows for much more complex and detailed fractal patterns to be rendered in real-time. ### Smoothing out the motion I improved the transform interpolation by using quartic bezier curves instead of smoothstep. This allowed for much smoother transitions between transforms, as the points would now follow a more natural curve rather than a jerky, speeding and slowing interpolation. The result was a much more visually appealing fractal, as the points would smoothly transition between different areas of the fractal rather than jumping around. ### Making it react to music I also implemented a version that uses [Cava](https://github.com/karlstav/cava), which is a terminal-based audio visualizer. This version uses the audio playing on the user's computer to influence the transformations being applied to the points, creating a dynamic and interactive fractal that responds to the music. The audio data is processed in real-time, and the transformations are updated accordingly, resulting in a visually stunning fractal that changes and evolves with the music. For now, the source code is not publicly available, but I may release it in the future. If you're interested in learning more about the implementation details or want to see the code, feel free to [reach out to me](mailto:erik@rospo.dev)!