> For the complete documentation index, see [llms.txt](https://42-guide.gitbook.io/42-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://42-guide.gitbook.io/42-guide/core-curriculum/rank-02/fdf/bresenham.md).

# Bresenham

#### Before starting working on it, please watch video below, where was explained bresenham algorithm and math behind it, so you will have base understandings about what is slope and what is Decision paramether. [Here is youtube video](https://youtu.be/RGB-wlatStc?si=MjBZgtWzwwBjQ8TO)

#### Step 1: Overview of the Bresenham’s Line Algorithm

Bresenham’s Line Algorithm is an efficient way of drawing a line on a grid or pixel-based canvas. It works by using an iterative decision-making process to determine the next pixel to plot. The core idea is to minimize the computational cost of evaluating floating-point operations by using integer calculations.

#### Key Concepts:

* **dx**: Difference between the x-coordinates of the start and end points.
* **dy**: Difference between the y-coordinates of the start and end points.
* **Decision Parameter (p)**: A value used to decide whether to move horizontally or diagonally.

The algorithm handles two cases:

1. **Negative Slope (dx > dy)** – When the line is shallow (closer to horizontal).
2. **Positive Slope (dy > dx)** – When the line is steep (closer to vertical).

#### Step 2: The `negative_slope` Function

The function `negative_slope` is used to plot lines where the absolute value of `dx` is greater than `dy` and the line slopes downward (negative slope). The goal here is to iterate through the horizontal direction, adjusting the y-coordinate when necessary based on the decision parameter `p`.

**Detailed Code Explanation for `negative_slope`:**

```c
void negative_slope(int x1, int y1, fdf *data)
{
    int i;
    int p;

    // Calculate the initial decision parameter (p) based on the slope.
    // The formula is: p = 2 * |dy| - |dx|, where dx and dy are the differences in the x and y coordinates.
    p = (2 * abs(data->side.dy)) - abs(data->side.dx);
    i = -1;
```

* **Initialization of `p`**:
  * `p = (2 * |dy|) - |dx|`: This equation helps to determine how the error accumulates while plotting. `dy` controls the vertical movement, and `dx` controls the horizontal movement.
* **Variable `i`**: We start iterating with `i = -1` to make sure the first iteration begins correctly.

Now we move to the plotting loop where we increment the `x` coordinate and adjust `y` based on the decision parameter.

```c
while (++i < abs(data->side.dx))
    {
        // Move horizontally (adjust x-coordinate based on dx sign)
        if (data->side.dx > 0)
            x1++;  // Move right if dx is positive
        else
            x1--;  // Move left if dx is negative
```

* **Adjusting `x1`**:
  * If `dx` is positive, increment the x-coordinate. If `dx` is negative, decrement the x-coordinate.

Next, we check the decision parameter `p`. If `p < 0`, we move horizontally only (no vertical adjustment). Otherwise, we also need to move vertically.

```c
        if (p < 0)
            p = p + (2 * abs(data->side.dy));  // Continue moving horizontally
        else
        {
            // Move vertically as well if p >= 0
            if (data->side.dy > 0)
                y1++;  // Move down if dy is positive
            else
                y1--;  // Move up if dy is negative

            // Update the decision parameter for the next iteration
            p = p + (2 * abs(data->side.dy)) - (2 * abs(data->side.dx));
        }
```

* **When `p < 0`**:
  * We continue moving horizontally without changing `y`. We adjust `p` by adding `2 * abs(dy)` to keep moving horizontally.
* **When `p >= 0`**:
  * Move both `x1` and `y1`. Depending on the sign of `dy`, we either increment or decrement `y1`.

Finally, after each iteration, we call the function to plot the pixel at `(x1, y1)`.

```c
put_pixel_less(data, x1, y1);  // Plot the pixel at the new coordinates (x1, y1)
    }
}
```

* **Plotting the Pixel**:
  * The function `put_pixel_less()` will handle rendering the pixel at the current coordinates `(x1, y1)`.

#### Step 3: The `positive_slope` Function

For **positive slopes** where the absolute value of `dy` is greater than `dx` (the line is steep), the algorithm follows a similar process but we focus on adjusting the vertical direction first (y-coordinate). When necessary, we adjust the horizontal direction (x-coordinate).

**Detailed Code Explanation for `positive_slope`:**

```c
void positive_slope(int x1, int y1, fdf *data)
{
    int i;
    int p;

    // Calculate the initial decision parameter for the positive slope.
    p = (2 * abs(data->side.dy)) - abs(data->side.dx);
    i = -1;
```

* **Initialization of `p`**:
  * Same formula is used as in the `negative_slope`, but it handles the vertical adjustment first because `dy > dx`.

Now, we iterate over the pixels just like we did in the negative slope case but prioritize vertical movement.

```c
    while (++i < abs(data->side.dy))
    {
        // Move vertically (adjust y-coordinate based on dy sign)
        if (data->side.dy > 0)
            y1++;  // Move down if dy is positive
        else
            y1--;  // Move up if dy is negative
```

* **Adjusting `y1`**:
  * If `dy` is positive, we move the `y1` coordinate down. If `dy` is negative, we move `y1` up.

Next, we check the decision parameter `p`. If `p < 0`, we continue moving vertically. Otherwise, we also need to adjust `x1`.

```c
        if (p < 0)
            p = p + (2 * abs(data->side.dx));  // Continue moving vertically
        else
        {
            // Move horizontally as well if p >= 0
            if (data->side.dx > 0)
                x1++;  // Move right if dx is positive
            else
                x1--;  // Move left if dx is negative

            // Update the decision parameter for the next iteration
            p = p + (2 * abs(data->side.dx)) - (2 * abs(data->side.dy));
        }
```

* **When `p < 0`**:
  * We continue moving vertically and adjust `p` by adding `2 * abs(dx)` to favor vertical movement.
* **When `p >= 0`**:
  * We move both `x1` and `y1`. Depending on the sign of `dx`, we either increment or decrement `x1`.

Finally, we plot the pixel after each iteration.

```c
       put_pixel_big(data, x1, y1);  // Plot the pixel at the new coordinates (x1, y1)
    }
}
```

#### Step 4: Plotting the Pixels

The `put_pixel_big()` and `put_pixel_less()` functions are used to render the pixels with the calculated coordinates, applying color based on the depth (`z1`, `z2`) of the points on the map.

**Detailed Code for Plotting the Pixel:**

```c
void put_pixel_big(fdf *data, int x, int y)
{
    char *addr;
    int pixel;

    addr = NULL;
    // Check if the coordinates are within the screen boundaries
    if (x > 0 && x < WIN_WIDTH && y > 0 && y < WIN_HEIGHT)
    {
        addr = data->address_data;  // Get the address of the pixel buffer
        pixel = y * data->size_line + x * 4;  // Calculate the position of the pixel in the buffer

        // Set the color based on the z-values (depth) of the points
        data->color = get_color(data->side.z1, data->side.z2);

        // Set the individual RGB components of the pixel
        addr[pixel + 0] = (data->color >> 0) & 255;  // Blue component
        addr[pixel + 1] = (data->color >> 8) & 255;  // Green component
        addr[pixel + 2] = (data->color >> 16) & 255;  // Red component
        addr[pixel + 3] = (data->color >> 24) & 255;  // Alpha component (transparency)
    }
}
```

#### Step 5: `put_pixel_less` Function

The `put_pixel_less` function is used to plot a pixel at the calculated coordinates `(x, y)` with the correct color. This function is called in the **negative slope case** (when the line is shallow and closer to horizontal) in the Bresenham's algorithm.

**Code Explanation for `put_pixel_less`:**

```c
void put_pixel_less(fdf *data, int x, int y)
{
    char *addr;
    int pixel;

    addr = NULL;
    // Check if the coordinates are within the valid screen bounds
    if (x > 0 && x < WIN_WIDTH && y > 0 && y < WIN_HEIGHT)
    {
        addr = data->address_data;  // Get the pointer to the pixel data in memory

        // Calculate the position of the pixel in the buffer based on (x, y)
        pixel = y * data->size_line + x * 4;  // 4 bytes per pixel (for RGBA)

        // Get the color based on the depth (z1, z2) of the points
        data->color = get_color(data->side.z1, data->side.z2);

        // Set the color components (Blue, Green, Red, Alpha) for the pixel
        addr[pixel + 0] = (data->color >> 0) & 255;    // Blue channel
        addr[pixel + 1] = (data->color >> 8) & 255;    // Green channel
        addr[pixel + 2] = (data->color >> 16) & 255;   // Red channel
        addr[pixel + 3] = (data->color >> 24) & 255;   // Alpha channel (transparency)
    }
}
```

**Key Points:**

* **Check screen bounds**: We first make sure that the pixel lies within the screen dimensions (`WIN_WIDTH` and `WIN_HEIGHT`). If it's outside, we don't plot it.
* **Pixel address calculation**: Using `pixel = y * data->size_line + x * 4`, we find the exact location of the pixel in the memory buffer. This is because each pixel consists of 4 bytes (for Red, Green, Blue, and Alpha channels).
* **Set color for the pixel**: The function `get_color` returns a color value based on the depth values (`z1` and `z2`) of the points, and we extract the individual Red, Green, Blue, and Alpha channels from the color value and store them in the corresponding locations in the memory buffer.

***

#### Step 6: `get_color` Function

The `get_color` function is responsible for calculating the color of a pixel based on its depth (`z1`, `z2`). The depth values represent the "height" or "altitude" at that point, and the color is blended based on these values. The deeper the point (higher altitude), the color changes.

**Code Explanation for `get_color`:**

```c
unsigned int get_color(int z1, int z2)
{
    float blended;
    int red;
    int green;

    // Blend the color based on the average of z1 and z2, plus a fixed value (30), and normalize by 110
    blended = (((z1 + z2) / 2.0) + 30.0) / 110.0;

    // Calculate the red component based on the blended value
    red = (int)(blended * 255);

    // Calculate the green component by subtracting the blended value from 1 and then scaling it
    green = (int)((1 - blended) * 255);

    // Return the color in 32-bit format (ARGB), with blue fixed to 150
    return ((red << 16) | (green << 8) | 150);  // 150 is the blue value (fixed)
}
```

**Key Points:**

* **Blended color**: The function first averages the depth values `z1` and `z2`, adds a small constant value (30), and then normalizes the result by dividing by 110. This blending helps generate a smoother transition between colors based on depth.
* **Red and Green components**: The red and green components are calculated from the blended value. The red component is directly proportional to the blend, and the green component is inversely proportional to the blend (so as red increases, green decreases).
* **Blue channel**: The blue value is fixed at `150` (hardcoded), providing a constant color saturation. You can modify this to make the blue component dynamic as well if needed.
* **Returning the color**: The function returns the color in **32-bit ARGB format**, where:
  * **Red** is stored in the upper 8 bits (shifted left by 16).
  * **Green** is stored in the middle 8 bits (shifted left by 8).
  * **Blue** is stored in the lower 8 bits.
  * **Alpha** is set to `255` (fully opaque) by default.

**Example:**

If `z1 = 50` and `z2 = 100`, the blended value would be:

```scss
blended = (((50 + 100) / 2.0) + 30.0) / 110.0 = (75 + 30) / 110 = 105 / 110 ≈ 0.9545
```

Then the red component will be approximately `0.9545 * 255 ≈ 243` and the green component will be `((1 - 0.9545) * 255 ≈ 12)`.

Thus, the final color might look like this: **Red = 243**, **Green = 12**, **Blue = 150**.

#### Step 7: Drawing the Map

The `draw_map()` function is responsible for connecting adjacent points and drawing the entire map by calling the `line()` function.

```c
void draw_map(fdf *data)
{
    int y;
    int x;

    if (!data || !data->map.render_map)
        return;

    x = 0;
    while (x < data->map.width)
    {
        y = 0;
        while (y < data->map.height)
        {
            if (x < data->map.width - 1)
                line(x, y, x + 1, y, data);  // Draw horizontal lines
            if (y < data->map.height - 1)
                line(x, y, x, y + 1, data);  // Draw vertical lines
            y++;
        }
        x++;
    }
}
```

#### Conclusion:

In summary, we:

1. **Initialize the decision parameter `p`** based on the slope of the line.
2. **Iterate** through each pixel along the line and decide whether to move horizontally or vertically.
3. **Plot the pixels** on the screen using the `put_pixel_less()` or `put_pixel_big()` functions.
4. **Connect adjacent points** to draw the full map.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://42-guide.gitbook.io/42-guide/core-curriculum/rank-02/fdf/bresenham.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.