<p>I have a rendering engine that has CPU path tracing support, as well as GPU (Vulkan) rasterization and path tracing support.  It uses a rasterization pre-processing step to identify the resolution of geometry that needs to be loaded prior to running the path tracing.  We now need to support this functionality on CPU in addition to GPU.  I have a basic rasterizer built on the CPU now, but its not parallelized.</p>
<p>The naive solution to rasterization is to simply loop over all triangles, projecting each to the image space and then determining which pixels lie inside the triangle.  The issue is, this process cannot be parallelized as stated.  If you simply try to process multiple triangles in parallel you could very easily end up with two triangles trying to write to the same pixels in the frame/color buffers.</p>
<p>The &quot;easiest&quot; solution I could think of is to duplicate the render targets (color/depth buffer).  Parallelize over the triangles but have each thread write to its own copy of the color/depth buffer.  Then once all threads are completed, merge everything together.</p>
<p>Another solution I can think of is to &quot;tile&quot; the frames such that, if I have N logical cores available, I create N tiles of the final image.  Each tile then gets its own frustrum and use that to identify what subset of the triangles appear in each tile, then simply run the rasterization on each (clipped) triangle in each tile in parallel.</p>
<p>Both of these options feel a bit clunky.  The first would require a ton of additional memory overhead needing to duplicate the render targets for every available logical core, and then requires an additional merging step.  The second option requires a list of the triangles that may appear in it's tile.  I'm loosely aware of the existence of tiled rendering for mobile devices, but I have never explicitly done that.  Is this how that process works, and why it would be used?  To allow parallelization of rasterizing many triangles?</p>
<p>Is there a better way of approaching this, or is creating a tile for every parallel thread the correct solution?</p>

CC BY-SA 4.0
2023-03-14T18:37:39.800Z
I think tiling is the way to go here. There are two major reasons: memory usage (which you already know) and performance (lower resolution per core and completely skipping triangles that does not intersect the tile of the screen). But why raster? If you use ray tracing together with an acceleration structure (ex: just a simple 3D grid), each pixel only have to iterate over a subset of your triangles.
Mathis
CC BY-SA 4.0
2023-03-14T18:41:46.367Z
The rasterization is a pre-processing step to identify the LoD that needs to be loaded as, this is for a planetary science application where our source geometry can be TB is size.  So not everything can fit in memory. We use rasterization to identify the ground sample distance of each portion of the terrain so we can load from disk the appropriate LoD.  Then update the BLAS for that portion (keeping the TLAS intact).  Its much faster this way than using the ray tracing itself, as we can then ensure the acceleration structure is constant once ray tracing starts
Chris Gnam
CC BY-SA 4.0
2023-03-15T07:55:13.973Z
I would change the CPU implementation of the framebuffer object. Each pixel could have an additional mutex that can be used when processing the corresponding pixel: getMutex, check depth value, change color and depth value, release mutex. No tiling is required and the memory does not need to be copied multiple times.
Thomas
CC BY-SA 4.0
2023-03-16T14:27:03.903Z
@Thomas I am currently entertaining both what you described, as well as a two-stage tiled approach, where the projection step is done in parallel (storing the projected positions of all vertices into a new vec2 buffer, while also adding their index to a list owned by the tile in which they fall in.  Then the tiles are rasterized in parallel using the triangle list they contain and the projected points.  A bit of memory overhead requiring a whole new vec2 buffer for the projected vertices, but for my use case this isn't a huge issue.  I haven't yet implemented either, but will try both soon
Chris Gnam
CC BY-SA 4.0
2023-03-17T11:42:21.863Z
Instead of a mutex, you can use a list, where each processed fragment (pixel) can push back the final result. One framebuffer thread would iterate through this lists and store the  closest fragment to the final image. This causes no interruption (wait for mutex)
Thomas
<rasterizer><tile-based-rendering>
I need to implement a CPU Rasterizer but am unsure how to parallelize rasterization
Chris Gnam
# I need to implement a CPU Rasterizer but am unsure how to parallelize rasterization

(Asked by: username_0 on 2023-03-14)

I have a rendering engine that has CPU path tracing support, as well as GPU (Vulkan) rasterization and path tracing support. It uses a rasterization pre-processing step to identify the resolution of geometry that needs to be loaded prior to running the path tracing. We now need to support this functionality on CPU in addition to GPU. I have a basic rasterizer built on the CPU now, but its not parallelized.

The naive solution to rasterization is to simply loop over all triangles, projecting each to the image space and then determining which pixels lie inside the triangle. The issue is, this process cannot be parallelized as stated. If you simply try to process multiple triangles in parallel you could very easily end up with two triangles trying to write to the same pixels in the frame/color buffers.

The "easiest" solution I could think of is to duplicate the render targets (color/depth buffer). Parallelize over the triangles but have each thread write to its own copy of the color/depth buffer. Then once all threads are completed, merge everything together.

Another solution I can think of is to "tile" the frames such that, if I have N logical cores available, I create N tiles of the final image. Each tile then gets its own frustrum and use that to identify what subset of the triangles appear in each tile, then simply run the rasterization on each (clipped) triangle in each tile in parallel.

Both of these options feel a bit clunky. The first would require a ton of additional memory overhead needing to duplicate the render targets for every available logical core, and then requires an additional merging step. The second option requires a list of the triangles that may appear in it's tile. I'm loosely aware of the existence of tiled rendering for mobile devices, but I have never explicitly done that. Is this how that process works, and why it would be used? To allow parallelization of rasterizing many triangles?

Is there a better way of approaching this, or is creating a tile for every parallel thread the correct solution?

**Tags:** rasterizer, tile-based-rendering

> **Comments:**
> **username_1**: I think tiling is the way to go here. There are two major reasons: memory usage (which you already know) and performance (lower resolution per core and completely skipping triangles that does not intersect the tile of the screen). But why raster? If you use ray tracing together with an acceleration structure (ex: just a simple 3D grid), each pixel only have to iterate over a subset of your triangles.  
> **username_0**: The rasterization is a pre-processing step to identify the LoD that needs to be loaded as, this is for a planetary science application where our source geometry can be TB is size.  So not everything can fit in memory. We use rasterization to identify the ground sample distance of each portion of the terrain so we can load from disk the appropriate LoD.  Then update the BLAS for that portion (keeping the TLAS intact).  Its much faster this way than using the ray tracing itself, as we can then ensure the acceleration structure is constant once ray tracing starts  
> **username_2**: I would change the CPU implementation of the framebuffer object. Each pixel could have an additional mutex that can be used when processing the corresponding pixel: getMutex, check depth value, change color and depth value, release mutex. No tiling is required and the memory does not need to be copied multiple times.  
> **username_0**: @username_2 I am currently entertaining both what you described, as well as a two-stage tiled approach, where the projection step is done in parallel (storing the projected positions of all vertices into a new vec2 buffer, while also adding their index to a list owned by the tile in which they fall in.  Then the tiles are rasterized in parallel using the triangle list they contain and the projected points.  A bit of memory overhead requiring a whole new vec2 buffer for the projected vertices, but for my use case this isn't a huge issue.  I haven't yet implemented either, but will try both soon  
> **username_2**: Instead of a mutex, you can use a list, where each processed fragment (pixel) can push back the final result. One framebuffer thread would iterate through this lists and store the  closest fragment to the final image. This causes no interruption (wait for mutex)  

---

## 0 answers

