Real-Time Mandelbrot Computation on Arduino and Display on LCD

EXECUTIVE SUMMARY

Fractals are mathematical objects characterized by self-similarity, where copies of the overall shape of a fractal can be found within it. This report explores the efficient real-time computation of parts of the Mandelbrot set using an FPGA and/or a Microcontroller board as part of the Embedded System Design course.

BACKGROUND AND INTRODUCTION

Fractals exhibit self-similarity, with various degrees of exactness. Some fractals, like those generated by Iterated Function Systems (IFS), display exact self-similarity. IFS involves a set of affine transformations with associated probabilities, which can be applied iteratively to an initial point to generate the fractal.

An example of such an IFS-generated fractal is the Sierpinski's Gasket.

Fractals can be classified by the algorithms used to create them, including IFS, Linden-Mayer Systems (L-Systems), and Escape Time Fractals.

Escape Time Fractals, a significant class of fractals, rely on non-linear algebraic functions on C2* or C3. The algorithm calculates colors for points on the drawing axis by running a feedback system based on the point's value.

Get quality help now

writer-Charlotte

Verified writer

Proficient in: Technology

4.7 (348)

“ Amazing as always, gave her a week to finish a big assignment and came through way ahead of time. ”

+84 relevant experts are online

Hire writer

The system's output escaping a given radius within a certain time determines the point's color. If the output does not escape, the point is colored differently.

The Mandelbrot set, a well-known escape time fractal, features partially similar shapes within its structure upon zooming in. This partial similarity adds to its aesthetic appeal, as opposed to other fractals that remain identical upon zooming, such as the Sierpinski's Triangle or Julia Sets.

The Mandelbrot set is generated using the equation Z_n+1 = Z_n² + C, where C represents the point whose color is being calculated, and Z₀ is initialized as 0 + 0j.

EXPERIMENTAL EQUIPMENT

The experimental equipment used in this project includes the following:

• Arduino Uno: The Arduino Uno is a microcontroller board based on the ATmega328. It is equipped with 14 digital input/output pins, 6 of which can be used as PWM outputs, 6 analog inputs, a 16 MHz ceramic resonator, a USB connection, a power jack, an ICSP header, and a reset button.
• The Processing Environment: Processing is an open-source programming language and integrated development environment (IDE) designed for electronic arts, new media art, and visual design communities. It aims to teach computer programming fundamentals in a visual context and serves as the foundation for electronic sketchbooks. Processing includes a sketchbook and is built upon the PApplet Java class, implementing most of the Processing language's features. It allows for the creation of custom classes within PApplet sketches, enabling the use of complex data types beyond standard data types such as integers, characters, real numbers, and color values.

EXPERIMENTAL PROCEDURE

The experimental procedure involved the use of the following equipment:

1. Arduino Uno
2. A computer

THEORETICAL ANALYSIS

The Computational Problem

Calculating the Mandelbrot set is a highly computationally intensive task. For a screen resolution of 800 × 800 pixels, there are a total of 6.4×10⁵ points that require color computation. Computing the color for one pixel involves transforming it to a point on the complex plane and performing a series of complex plane arithmetic calculations (along with checks) in a loop, which iterates nearly 30 times to achieve satisfactory image density (higher image densities require more than 100 iterations per pixel).

During each loop iteration, approximately 10 floating-point multiplications are performed. Therefore, a total of 1.92×10⁸ floating-point multiplications are required per frame. This method of calculating the Mandelbrot set is highly inefficient and time-consuming, making real-time zooming challenging to achieve.

THE PROPOSED ARCHITECTURE

Workflow

The workflow involved connecting the Arduino Board to the computer using the provided connector. Subsequently, both the Arduino and Processing environments were programmed. The Mandelbrot set calculation algorithm was implemented in Arduino using C, while the coloring, drawing algorithm, and user input handling were developed in Processing using Java. The programs were then executed, and the interactive display was observed on the computer screen.

TECHNIQUES TESTED FOR OPTIMAL COMPUTATION TIME

Fixed Point Calculations

Due to the significant time consumption associated with floating-point calculations, transitioning to fixed-point calculations proved to be a favorable choice. Implementing high-precision fixed-point arithmetic on hardware proved to be more efficient compared to software-based approaches.

Transformations

Instead of selecting a pixel from the screen and then transforming it to the calculation axes (which is computationally intensive), a more efficient approach was adopted. A (dx, dy) variable was introduced to represent the equivalent value for a pixel increment in the calculation axes. This approach significantly reduced the computational load as the next value for C could be determined by simply incrementing by dx or dy as needed.

Calculation Mechanisms

The calculations for the Mandelbrot set, which are time-consuming, were optimized by considering two different approaches:

1. Normal: Calculations are performed in rows of the screen, with each row calculated from left to right, starting from the top row and moving downward.
2. Dynamic Resolution: Calculations are performed in four passes, where rows are processed differently to optimize computation.

TINKERING WITH THE ALGORITHM

In the algorithm, the calculation of Z involves a function with lower computational complexity than the Complex Absolute Function. While this approach may alter the fractal's shape, a compromise between speed and results was achieved by experimentally squaring and adding the complex and real parts.

RESULTS

The total time taken to calculate and draw a full screen of 800 x 800 pixels was as follows:

• With Floats and No optimizations: 80.71 Seconds
• With Fixed Points and No optimizations: 56.6 Seconds
• With Fixed Points and Square Value Function: 49.9 Seconds
• With Fixed Points, Square Value Function, and Inline Functions: 48.694 Seconds

CONCLUSION

We successfully demonstrated the computational capacity of the embedded system (Arduino) by implementing a custom set of algorithms and computational techniques. The only performance limitation encountered was due to the UART protocol baud rate limit (600,000) and the processor clock speed of the Arduino Uno modular board. These limitations could potentially be overcome with a more efficient protocol, such as the USB protocol.