---
tags: Texturing, 2023
---
# Texturing: Fix seam bleeding.

* [x] Move mipmapping to its own doc.
* [x] Add pictures indicating the issues we want to solve.
* [ ] Refer to blender manual for functionality/reasoning.
* [ ] Document should be understandable for a developer who wants to know how our system works.
* [ ] Add references to code (where can this be found in the source-tree)
* [ ] Explain manifold seam bleeding.

## What are seams?

During the UV unwrapping task a 3d model is unwrapped to uv space. The U,V coordinate of an UV map is adjusted.
face corner The goal of this task is to deIn order to make sure that each face has the user can cut the model into In this process the model can be cut into one or more UV islands for multiple reasons.

## What is seam bleeding?

During rendering artifacts can appear at the edges of uv islands. These artifacts are called seam bleeding.

Causes when these artifacts appear:
* pixels are read from different areas of the texture as result of the unwrapping process.
* pixels are read from neighbouring pixels, that are not evaluated during painting. This happens as due as brushes are often evaluated with higher precision as stored inside the texture.


## How to solve seam bleeding?

Seam bleeding is solved evaluating pixels near the seam, even if they are not part of the face being painted on.

## Solution

During initial design we expected that copying of neighboring pixels would be good enough for the final solution. But unfortunately it wasn't and a second, more precise algorithm, had to be developed. This second algorithm couldn't handle non-manifold parts of the mesh. For non-manifold parts of the mesh copying of neighboring pixels is still used.

The final solution uses both algoritms.

- Manifold parts of a mesh can be done in higher quality than non-manifold sections. For this reason the solution is separated in 2 stages.

## Fixing manifold parts (extending in UV space)

### Extending UV islands

The main idea is to extend the UV islands of the model to cover more pixels and thereby solve the issue of seam bleeding. Adjacent geometry are used to extend the UV islands.

The proces works on the primitives of the mesh. What are primitives? Primitives are the triangles that form the polygons of a mesh. Polygons are often to complex to with or render and are breaked down into triangles, those triangles are called primitives.

#### Overview of the algorithm

Locate the UV vertex on the border of the UV island with the sharpest corner. 

Find the vertex in the mesh. 

Construct a fan with the connected primitives in the mesh.

Find the primitives that are not connected around the UV vertex found in step 1.

Generate primitives to fill the gab of the sharpest corner. For this UV vertex 2 new primitives are generate.

There are multiple cases, that require a different solution to generate the new primitives. In this doc we won't cover them all as it requires more work to keep it up to date with the actual implementation.
- Corner between 2 edges in uv space are actually the same edge in 3d space. 

This process will be repeated until all UV vertices have been extended. The colored primitives in the image below indicate the primitives that have been generated in order to fix the seam bleeding.


### Source-code
:::info
Source files implementing this is
- `source/blender/blenkernel/intern/pbvh_uv_islands.hh`
- `source/blender/blenkernel/intern/pbvh_uv_islands.cc`
:::

### Mask UV island areas

## Fixing non manifold parts (copy and mix pixels)

As manifold parts are already handled, the pixel copy-ing solution can be very straight forward.
- Pixels are copied from the same tile. So we don't need a mechanism that copies and merges pixels from other tiles.
- Pixels are copied from the closest pixel that is being painted on. We don't need to consider that that pixel can be in different areas of the tile.

When we copy a pixel, we find the closest pixel in UV space that is being directly influenced by a paint brush. We also look for the second closest pixel, which is still a neighbor from the closest pixel. We can mix both pixels together and store it in the destination. A mix factor is calculated using the closest non manifold edge as a guidance.

The result of this step is a list of copy and mix commands that can be executed to fix the seam bleeding for non-manifold sections of the mesh.

| Destination | Source 1 | Source 2 | Mix factor |
| ----------- | -------- | -------- | -----------|
| 1780,1811 | 1780,1810 | 1779,1810 | 0.000000 |
| 1781,1811 | 1781,1810 | 1782,1811 | 0.168627 |
| 1828,1811 | 1828,1810 | 1827,1811 | 0.156863 |
| 1829,1811 | 1829,1810 | 1828,1810 | 0.188235 |
| 1830,1811 | 1830,1810 | 1829,1810 | 0.188235 |
| 1831,1811 | 1831,1810 | 1830,1810 | 0.188235 |
| 1832,1811 | 1832,1810 | 1831,1810 | 0.188235 |
| 1833,1811 | 1832,1810 | 1832,1810 | 0.000000 |

In the end we go over this list mix the sources and store the result at the destination.

tile_buffer[destination] = mix(tile_buffer[source_1], tile_buffer[source_2], mix_factor);

### Encoding

When using a large textures or large seam margins this table can grow large and reduce performance as data retrieval is slower, than the operations it has to perform. To improve the performance we encode the
table so less data retrieval needs to be done.

namespace blender::kernel::pbvh::pixels {
    class CopyPixelCommand {
        destination: int2
        source_1: int2
        source_2: int2
        mix_factor: float
        ---
        CopyPixelCommand(group: PixelCopyGroup)
        apply(item PixelCopyItem)
        mix_source_and_write_destination(tile_buffer)
    }
    
    class CopyPixelTile {
        tile_number: TileNumber
        ---
        copy_pixels(tile_buffer: ImBuf)
    }
    
    class CopyPixelGroup {
        start_destination: int2
        start_source_1: int2
        start_delta_index: int64_t
        num_deltas: int
    }
    class DeltaCopyPixelCommand {
        // delta of source_1 with the previous iteration.
        delta_source_1: blender::char2
        
        // delta_source_2 is delta from source_1 as
        // it is always one of its neighbouring pixels.
        delta_source_2: blender::char2
        
        // Mixfactor to mix source_1 and source_2 colors.
        // Encoded to a uint8_t [0..=255]
        factor: uint8_t
    }
    class CopyPixelTiles {
        ---
        CopyPixelTile find_tile(tile_number: TileNumber)
    }
    CopyPixelTiles *--> CopyPixelTile: tiles
    CopyPixelTile *-> CopyPixelGroup: groups
    CopyPixelTile*--> DeltaCopyPixelCommand: command_deltas
}

- first `DeltaCopyPixelCommand` is delta encoded from `CopyPixelGroup#start_destination` and `start_source_1`. The others are delta encoded from the previous `DeltaCopyPixelCommand`.
- For performance reasons `PixelCopyGroup#pixels` are ordered from destination (left to right)
- for each row a new group would be created as the delta encoding most likely doesn't fit.
- When pixels cannot be delta encoded a new group will also be created.

### Compression rate
When using Suzanne the compression rate is around 36% when using a seam margin of 4 pixels. The compression rate may vary depending on seam margin and model. For Suzanne the compression rate was around 365 for various resolutions.

| Texture resolution | Seam margin | Decoded size (bytes) | Encoded size (bytes)| Compression rate |
| ------------------ | ----------- | ------------ | ------------ | ---------------- |
| 2048x2048 | 4 px | 353.052 | 128.101 | 36% |
| 4096x4096 | 4 px | 700.140 | 255.137 | 36% |
| 8192x8192 | 4 px | 1.419.320 | 513.802 | 36% |
| 2048x2048 | 8 px | 721.084 | 193.629 | 26% |
| 4096x4096 | 8 px | 1.444.968 | 388.110 | 26% |