<p>It could be that you have to overcome a different bottleneck first.</p>

<p>Have you ever read Jim Blinn's "The Truth About Texture Mapping"? (I had a quick search to see if I could find a non-paywalled version but you may have better luck than me. Alternatively you might find a dead tree version of "Jim Blinn's Corner" in a library). Though this article is old and describes paging of texture data, it is still very relevant today.</p>

<p>Essentially, if your textures are large (i.e. too large to fit in the cache), in scan order, and they have been rotated when displayed on the polygons, you are very likely to be thrashing your cache and, as memory is an order or two of magnitude slower than the CPU, this will hurt performance.</p>

<p>To avoid the cache thrashing, textures are often stored in twiddled-order (that's what we called it in the early 90s but, more correctly, it'll be some variant of Morton order) or in a block order, which is what Blinn describes. This then makes texel/memory accesses far more coherent and the cache more effective.</p>

CC BY-SA 3.0
2017-07-20T13:26:09.640Z
Mip mapping is also a good strategy to improve cache coherence in texture mapping.
Stefan Werner
CC BY-SA 3.0
2017-07-21T08:42:05.620Z
@Stefan Indeed. Texture aliasing is painful in multiple ways :-).

There's a bit more on the subject here: https://computergraphics.stackexchange.com/questions/357/is-using-many-texture-maps-bad-for-caching/419#419
Simon F
CC BY-SA 3.0
2017-07-20T08:49:58.067Z
2017-07-21T08:45:34.500Z
2017-07-21T08:45:34.500Z
Simon F
<p>This is rather general programming question but parallelizing for loop (most common usage) in c++ is easy with openMP library. Basic example for parallelizing outer loop:</p>

<pre><code>#pragma omp parallel for schedule(static, 1) num_threads(omp_get_num_procs())
for (int i = 0; i &lt; size1; ++i)
{
    for (int j = 0; j &lt; size2; ++j)
    {
        buffer[i*size1 + j] = ...
    }
}
</code></pre>

<p>But because of thread race situation below (incrementing array index) which would work in single thread wouldn't work in parallel:</p>

<pre><code>int it = 0;
#pragma omp parallel for schedule(static, 1) num_threads(omp_get_num_procs())
for (int i = 0; i &lt; size1; ++i)
{
    for (int j = 0; j &lt; size2; ++j)
    {
        buffer[it++] = ...
    }
}
</code></pre>

<p>Also thing to consider is using SIMD instructions (Single Instruction Multiple Data) which optimize multiple operations to single CPU instruction:</p>

<pre><code>#pragma omp parallel for simd schedule(static,10) 
for (i=0; i&lt;N; i++) 
{ 
    a[i] = b[i] * c[i]; 
}
</code></pre>

<p>Some further info:</p>

<p><a href="http://bisqwit.iki.fi/story/howto/openmp/" rel="nofollow noreferrer">http://bisqwit.iki.fi/story/howto/openmp/</a></p>

<p><a href="https://www.youtube.com/watch?v=Pc8DfEyAxzg" rel="nofollow noreferrer">https://www.youtube.com/watch?v=Pc8DfEyAxzg</a></p>

CC BY-SA 3.0
2017-07-20T08:34:24.757Z
2017-07-20T08:34:24.757Z
mdkdy
<p>The biggest bottleneck of my code is fetching texture RGB values from memory.</p>

<p>My code looks something like this:</p>

<pre><code>game loop{
    for every mesh{
        perform clipping;
        for every 3 verticies in mesh {
            draw triangle {
                interpolate texture coordinates;
                fetch texture RGB and place value in backbuffer;
            }
        }
    }
}
</code></pre>

<p>Fetching the texture RGB value from memory takes up so much time!!</p>

<p>I am not familiar with multithreading but I'm assuming there is some way to apply it here. Let me know what suggestions you have and how I should go about doing this!</p>

CC BY-SA 3.0
2017-07-20T03:58:55.177Z
How are you currently accessing memory? Can you share code for that?
aces
CC BY-SA 3.0
2017-07-20T08:21:47.120Z
This topic is big enough that books have been written on it. To get a good answer, you need to [edit] your question and make it more specific. But your software rasterizer will always be orders of magnitude slower than using OpenGL or DirectX.
Dan Hulme
CC BY-SA 3.0
2017-07-20T16:05:47.067Z
@aces The backbuffer I write to is the buffer of the screen. It is represented as 3 chars for RGB in sequential order. I call it "ibuffer". The texture RGB values are stored in an integer array where each integer is the chars RGBA.

[code]
*ibuffer = mesh->texture->intbuffer[(int)textureX + mesh->texture->width * (int)textureY];
[\code]

The integer I copy from the texture to the backbuffer overwrites the R value of the next pixel in the back buffer. I do this so as to not use bitwise operations used to extract the RGB values from texture memory and store in backbuffer.
Benjamin Loisch
CC BY-SA 3.0
2017-07-21T03:55:40.950Z
A minor optimisation would be to use powers of 2 for your texture size, so you can compute the offset using a logical shift. E.g. if you have a 256 pix wide texture you can compute the texel offset with "U + V << 8". Also pad your RGB structure to 4 bytes instead of 3 so the compiler can apply a similar optimisation to the array indirection. You can also apply texture wrapping trivially if power of 2 size e.g.  (U & 255) + (V & 255) << 8
PaulHK
CC BY-SA 3.0
2017-07-21T16:42:22.820Z
@PaulHK I will try that Paul. Compared to my original statement, I found if I access the same texel for all interpolated pixels (*ibuffer = mesh->texture->intbuffer[10000]), the program framerate increases by 3 to 4 times. Do you have any idea why?
Benjamin Loisch
CC BY-SA 3.0
2017-07-22T10:12:09.687Z
Using a constant index makes the address calculation a lot simpler, the compiler will calculate 1 pointer outside of your loops as opposed to recalculating it each pixel because it is using a none-constant index. Also accessing the same memory location will ensure it's in the CPU cache so you will get massive performance boost from that.
PaulHK
CC BY-SA 3.0
2017-07-24T22:41:16.973Z
@PaulHK In my innermost for loop I am iterating over the pixels in the triangle and fetching the appropriate texels in a 1D array and storing in the back buffer:
for all pixels in triangle
     *ibuffer = mesh.texture.intbuffer[texcoord];

If my texture is allocated on the heap, and the texture is being accessed vertically... I do not understand how the cache is filling up with unecessary values. I suppose if I tiled my texture, the cache would guess the next values and store them in registers and since it's tiled, those values would more likely be the correct ones to use.
Benjamin Loisch
<texture><3d><c++><rasterizer><multithreading>
How to use multithreading in 3D software renderer to speed up fetching texture values
Benjamin Loisch
# How to use multithreading in 3D software renderer to speed up fetching texture values

(Asked by: username_0 on 2017-07-19)

The biggest bottleneck of my code is fetching texture RGB values from memory.

My code looks something like this:

```
game loop{
    for every mesh{
        perform clipping;
        for every 3 verticies in mesh {
            draw triangle {
                interpolate texture coordinates;
                fetch texture RGB and place value in backbuffer;
            }
        }
    }
}

```

Fetching the texture RGB value from memory takes up so much time!!

I am not familiar with multithreading but I'm assuming there is some way to apply it here. Let me know what suggestions you have and how I should go about doing this!

**Tags:** texture, 3d, c++, rasterizer, multithreading

> **Comments:**
> **username_1**: How are you currently accessing memory? Can you share code for that?  
> **username_2**: This topic is big enough that books have been written on it. To get a good answer, you need to [edit] your question and make it more specific. But your software rasterizer will always be orders of magnitude slower than using OpenGL or DirectX.  
> **username_0**: @username_1 The backbuffer I write to is the buffer of the screen. It is represented as 3 chars for RGB in sequential order. I call it "ibuffer". The texture RGB values are stored in an integer array where each integer is the chars RGBA.  [code] *ibuffer = mesh->texture->intbuffer[(int)textureX + mesh->texture->width * (int)textureY]; [\code]  The integer I copy from the texture to the backbuffer overwrites the R value of the next pixel in the back buffer. I do this so as to not use bitwise operations used to extract the RGB values from texture memory and store in backbuffer.  
> **username_3**: A minor optimisation would be to use powers of 2 for your texture size, so you can compute the offset using a logical shift. E.g. if you have a 256 pix wide texture you can compute the texel offset with "U + V << 8". Also pad your RGB structure to 4 bytes instead of 3 so the compiler can apply a similar optimisation to the array indirection. You can also apply texture wrapping trivially if power of 2 size e.g.  (U & 255) + (V & 255) << 8  
> **username_0**: @username_3 I will try that Paul. Compared to my original statement, I found if I access the same texel for all interpolated pixels (*ibuffer = mesh->texture->intbuffer[10000]), the program framerate increases by 3 to 4 times. Do you have any idea why?  
> **username_3**: Using a constant index makes the address calculation a lot simpler, the compiler will calculate 1 pointer outside of your loops as opposed to recalculating it each pixel because it is using a none-constant index. Also accessing the same memory location will ensure it's in the CPU cache so you will get massive performance boost from that.  
> **username_0**: @username_3 In my innermost for loop I am iterating over the pixels in the triangle and fetching the appropriate texels in a 1D array and storing in the back buffer: for all pixels in triangle      *ibuffer = mesh.texture.intbuffer[texcoord];  If my texture is allocated on the heap, and the texture is being accessed vertically... I do not understand how the cache is filling up with unecessary values. I suppose if I tiled my texture, the cache would guess the next values and store them in registers and since it's tiled, those values would more likely be the correct ones to use.  

---

## 2 answers

### Answer by username_4 on 2017-07-20. Score: 5

It could be that you have to overcome a different bottleneck first.

Have you ever read Jim Blinn's "The Truth About Texture Mapping"? (I had a quick search to see if I could find a non-paywalled version but you may have better luck than me. Alternatively you might find a dead tree version of "Jim Blinn's Corner" in a library). Though this article is old and describes paging of texture data, it is still very relevant today.

Essentially, if your textures are large (i.e. too large to fit in the cache), in scan order, and they have been rotated when displayed on the polygons, you are very likely to be thrashing your cache and, as memory is an order or two of magnitude slower than the CPU, this will hurt performance.

To avoid the cache thrashing, textures are often stored in twiddled-order (that's what we called it in the early 90s but, more correctly, it'll be some variant of Morton order) or in a block order, which is what Blinn describes. This then makes texel/memory accesses far more coherent and the cache more effective.

> **Comments:**
> **username_5**: Mip mapping is also a good strategy to improve cache coherence in texture mapping.  
> **username_4**: @username_5 Indeed. Texture aliasing is painful in multiple ways :-).  There's a bit more on the subject here: https://computergraphics.stackexchange.com/questions/357/is-using-many-texture-maps-bad-for-caching/419#419  

---

### Answer by username_6 on 2017-07-20. Score: 2

This is rather general programming question but parallelizing for loop (most common usage) in c++ is easy with openMP library. Basic example for parallelizing outer loop:

```
#pragma omp parallel for schedule(static, 1) num_threads(omp_get_num_procs())
for (int i = 0; i < size1; ++i)
{
    for (int j = 0; j < size2; ++j)
    {
        buffer[i*size1 + j] = ...
    }
}

```

But because of thread race situation below (incrementing array index) which would work in single thread wouldn't work in parallel:

```
int it = 0;
#pragma omp parallel for schedule(static, 1) num_threads(omp_get_num_procs())
for (int i = 0; i < size1; ++i)
{
    for (int j = 0; j < size2; ++j)
    {
        buffer[it++] = ...
    }
}

```

Also thing to consider is using SIMD instructions (Single Instruction Multiple Data) which optimize multiple operations to single CPU instruction:

```
#pragma omp parallel for simd schedule(static,10) 
for (i=0; i<N; i++) 
{ 
    a[i] = b[i] * c[i]; 
}

```

Some further info:

<http://bisqwit.iki.fi/story/howto/openmp/>

<https://www.youtube.com/watch?v=Pc8DfEyAxzg>


---

