PBVH is an accelleration structure blender uses internally to speed up 3d painting operations.
At this moment it is extensively used by sculpt, vertex painting and weight painting.

For the 3d texturing brush we will be using the PBVH for texture painting.
Currently PBVH is organized to work on geometry (vertices, polygons and triangles).
For texture painting this should be extended to use pixels.

Next to PBVH_Leaf there will be an additional node type (PBVH_Pixels)

• PBVH_Pixels is always a subnode of PBVH_Leaf or the PBVH_Leaf node in case the leaf doesn't need to split.

Rasterization process

The rasterization process will generate the PBVH_Pixels for a leaf node. In order to do so every polygon should be uniquely assigned to a leaf node.

For each leaf node
   for each polygon
     If polygon not assigned
       assign polygon to node.

Polygons are too complicated to be used directly we have to split the polygons into triangles.

For each leaf node
  for each polygon
    extract triangles from polygon.

The list of triangles can be stored inside the leaf node. The list of polygons aren't needed anymore.
Each triangle has:

• poly_index.
• vert_indices
• delta barycentric coordinate between x steps.
• factor (factor propogated from automasking/front faces/... functionality, to quickly detect if this triangle actually has influence to the end result).

Each triangle can be rasterized and each row of pixels can be stored in a structure containing

• image position
• barycentric coordinate of the first pixel
• number of pixels
• triangle index inside the leaf node.

Data can be encoded to reduce memory needs.

• Only need to store 2 barycentric components. The third can be calculated from the 2 stored.

Depending on the number of pixels the node will be split.

There are several ways when the pixels should be recalculated:

• Image resolution changes.
• UDIM tiles changes
• UVMap changes
• Geometry changes
• ...

Pixels are ordered by UDIM tiles, image buffer y coordinate, image buffer x coordinate. The range of a pixels per UDIM tile are stored along side the pixels.

Rasterization

During the performed experiments we use a fairly simple rasterization process by finding the UV bounds of an triangle and calculate the barycentric coordinates per pixel inside the bounds.
Even for complex models and huge images this process is normally finished within 0.5 second. It could be that we want to change this algorithm to reduce hickups when nodes are initialized during a stroke.

Testing

For testing purposes an initial implementation of a texturing paint brush will be implemented. This will only be available via an experimental feature flag.

Compression

If needed the list of pixels can be compressed as they are always accessed sequential. We should only do this if there is actually a memory issue we want to solve. For compression
we can think of variable size delta compression. Due to the ordering the image positions could be stored into 4-8 bits for a lot of cases.