Tutorial part 4 – bonus: learning how to write a 3D software engine in C#, TS or JS – Optimizing & Parallelism

In the previous tutorial, learning how to write a 3D software engine in C#, TS or JS – Rasterization & Z-Buffering, we’ve learned how to fill our triangles. As we’re CPU based with our 3D software engine, it really starts to cost a lot of CPU time. The good news is that today’s CPUs are multi-cores. We could then imagine using parallelism to boost the performance. We’re going to do that in C# only and I’ll explain why we won’t do it in HTML5. We’re also going to see some simple tips that could boost the performance in such rendering loop code. Indeed, we’re going to move from 5 FPS to 50 FPS, a 10X performance boost!

This tutorial is part of the following series:

1 – Writing the core logic for camera, mesh & device object
2 – Drawing lines and triangles to obtain a wireframe rendering
3 – Loading meshes exported from Blender in a JSON format
4 – Filling the triangle with rasterization and using a Z-Buffer
4b – Bonus: using tips & parallelism to boost the performance (this article)
5 – Handling light with Flat Shading & Gouraud Shading
6 – Applying textures, back-face culling and WebGL

Compute the FPS

First step is to compute the FPS to be able to check if we’re going to gain some performance by modifying our algorithm. You can do that either in C# or TypeScript/JavaScript of course.

We need to know the delta time between two frames rendered. We then simply need to capture the current time, draw a new frame (requestAnimationFrame in HTML5 or CompositionTarget.Rendering in XAML), capture again the current time and compare it to the previous time saved. You will have a result in milliseconds. To obtain, the FPS, simply divide 1000 by this result. For instance if it’s 16,66 ms, the optimal delta time, you will have 60 FPS.

You can do that after each frame rendered to have a very precise FPS or compute the average FPS on 60 samples for instance. David and I already worked on this topic through this series: Benchmarking a HTML5 game: HTML5 Potatoes Gaming Bench

In conclusion, in C#, add a new TextBlock XAML control, named it “fps” and use this code to compute the FPS:

DateTime previousDate;

void CompositionTarget_Rendering(object sender, object e)
{
    // Fps
    var now = DateTime.Now;
    var currentFps = 1000.0 / (now - previousDate).TotalMilliseconds;
    previousDate = now;

    fps.Text = string.Format("{0:0.00} fps", currentFps);

    // Rendering loop
    device.Clear(0, 0, 0, 255);

    foreach (var mesh in meshes)
    {
        mesh.Rotation = new Vector3(mesh.Rotation.X, mesh.Rotation.Y + 0.01f, mesh.Rotation.Z);
        device.Render(mera, mesh);
    }

    device.Present();
}

 

Using this code, using the native resolution of my Lenovo Carbon X1 Touch (1600×900), I’m running an average of 5 FPS with the C# solution shared in the previous article. My Lenovo embeds an Intel Core i7-3667U with a HD4000 GPU. It’s a hyper-threaded dual-core CPU. It then shows 4 logical CPUs.

Optimization & Parallelization strategies

WinRT applications are using the .NET Framework 4.5 which includes the Task Parallel Library by default (TPL). If you pay attention in the way you’re writing your algorithm and if your algorithm can be parallelized, making it parallel becomes very easy thanks to TPL. If you don’t know this concept yet, have a look to Parallel Programming in .NET Framework 4: Getting Started

Avoid touching UI controls

The first rule for multi-threading/multi-tasking is to have 0 code touching the UI in the threads spawn. Only the UI thread can touch/manipulate graphic controls. In our case, we had piece of code accessing to bmp.PixelWidth or bmp.PixelHeight where bmp is of type WriteableBitmap. WriteableBitmap is considered as a UI element and is not thread-safe. That’s why, we first need to change these blocks of code to make them “parallelizable”. In the previous tutorial, we started by doing so. You simply need to save those values at the beginning. We’ve done that in renderWidth and renderHeight. Use these values in your code instead of accessing to bmp. Change all references to bmp.PixelWidth to renderWidth and to bmp.PixelHeight to renderHeight.

By the way, this rule is not only important for parallelization. It’s also for performance optimization in general. Thus, by simply removing accesses to the WriteableBitmap properties in my code, I’m switching from an average of 5 FPS to more than 45 FPS on the same machine!

The same rule is very important (even maybe more) in HTML5. You should absolutely avoid to test DOM elements properties directly. DOM operations are very slow. So it’s really not a good idea to access them every 16ms if it’s not necessary. Always cache the values you need to test later on. We’ve already done so in the previous tutorials for the HTML5 version of the 3D engine.

Be self-sufficient

A second rule is that the block of code that will be launched on the several available cores need to be self-sufficient. Your code doesn’t have to wait too long for the result of other block of code to continue otherwise it will lower the interest of parallelism. In our case, you’re lucky as I’ve managed to give you the code in previous tutorials to already respect this rule.

You may have seen that we have several areas where we could switch our classical For loop by a Parallel.For loop.

The first case is in the DrawTriangle method. We’re then going to draw several lines on a triangle in parallel. You can then easily convert the 2 normal For loop by 2 Parallel.For loop:

if (dP1P2 > dP1P3)
{
    Parallel.For((int)p1.Y, (int)p3.Y + 1, y =>
        {
            if (y < p2.Y)
            {
                ProcessScanLine(y, p1, p3, p1, p2, color);
            }
            else
            {
                ProcessScanLine(y, p1, p3, p2, p3, color);
            }
        });
}
else
{
    Parallel.For((int)p1.Y, (int)p3.Y + 1, y =>
        {
            if (y < p2.Y)
            {
                ProcessScanLine(y, p1, p2, p1, p3, color);
            }
            else
            {
                ProcessScanLine(y, p2, p3, p1, p3, color);
            }
        });
}

 

But in my case, the output is a bit surprising. I’m lowering the performance switching back from 45 FPS to 40 FPS! So what could be the reason of this performance drawback?

Well, in this case, drawing several lines in parallel is not feeding the cores enough. We’re then spending more time in context switching and moving from one core to another than doing some real processing. You can check that with the embedded profiling tools of Visual Studio 2012 : Concurrency Visualizer for Visual Studio 2012

Here is the Cores utilization map with this first parallelization approach:

image

The various colors are associated to worker threads. It’s really non-efficient. Look at the difference with the non-parallelized version:

image

We’re only have 1 thread working (the green one) which is dispatched on the several cores by the OS itself. Even if we’re not using the multi-cores capabilities of the CPU in this case, we’re finally more efficient globally. We’re generating too much switching in our first parallelization approach.

Protect with lock and choose the right loop to parallelize

Well, I guess you came to the same conclusion than I. Parallelizing the loops in the drawTriangle method doesn’t seem to be a good option. We need to find something that will take more time to execute and will be more efficient in the cores switching. Rather than drawing a triangle in parallel, we’re going to draw several triangles in parallel. In conclusion, each core will handle the drawing of a complete triangle.

The problem by using this approach lives in the PutPixel method. Now that we want to draw several faces in parallel, we may fall into cases where 2 cores/threads will try to access the same pixel in concurrency. We then need to protect access to a pixel before working on it. We need also to find an efficient way to lock access to the pixels buffers. Indeed, if we’re spending more time protecting the data than working on it, the parallelization will be once more useless.

The solution is to use an array containing fake objects we will lock on.

private object[] lockBuffer;

public Device(WriteableBitmap bmp)
{
    this.bmp = bmp;
    renderWidth = bmp.PixelWidth;
    renderHeight = bmp.PixelHeight;

    // the back buffer size is equal to the number of pixels to draw
    // on screen (width*height) * 4 (R,G,B & Alpha values). 
    backBuffer = new byte[renderWidth * renderHeight * 4];
    depthBuffer = new float[renderWidth * renderHeight];
    lockBuffer = new object[renderWidth * renderHeight];
    for (var i = 0; i < lockBuffer.Length; i++)
    {
        lockBuffer[i] = new object();
    }
}

// Called to put a pixel on screen at a specific X,Y coordinates
public void PutPixel(int x, int y, float z, Color4 color)
{
    // As we have a 1-D Array for our back buffer
    // we need to know the equivalent cell in 1-D based
    // on the 2D coordinates on screen
    var index = (x + y * renderWidth);
    var index4 = index * 4;

    // Protecting our buffer against threads concurrencies
    lock (lockBuffer[index])
    {
        if (depthBuffer[index] < z)
        {
            return; // Discard
        }

        depthBuffer[index] = z;

        backBuffer[index4] = (byte)(color.Blue * 255);
        backBuffer[index4 + 1] = (byte)(color.Green * 255);
        backBuffer[index4 + 2] = (byte)(color.Red * 255);
        backBuffer[index4 + 3] = (byte)(color.Alpha * 255);
    }
}

 

Using with this second approach, I’m moving from an average of 45 FPS to 53 FPS. You may think that the performance boost is not that impressive. But in the next tutorial, the drawTriangle method will be much more complex to handle shadows & lighting. For instance, using this approach with the Gouraud Shading, parallelization will almost double the performance.

We can also analyze the new Cores view with this second parallelization approach:

image

Compare it to the previous Cores view and you’ll see why this is much more efficient.

You can download the C# solution containing this optimized version here:

C# : SoftEngineCSharpPart4Bonus.zip

So, what’s wrong with HTML5/JavaScript in this case?

HTML5 offers a new API for JavaScript developers to handle similar approaches. It’s named Web Workers and it can address multi-cores usage in specific scenarios.

David Catuhe & I have already covered this topic several times in these 3 articles:

Introduction to the HTML5 Web Workers: the JavaScript multithreading approach : you should first read this article if you don’t know Web Workers yet

Using Web Workers to improve performance of image manipulation : a very interesting article where we’re gaining performance with workers on pixels manipulations

Tutorial Series: using WinJS & WinRT to build a fun HTML5 Camera Application for Windows 8 (4/4) : the fourth part of a tutorials series where I’m using web workers to apply some filters on images taken with the WebCam.

Communications with workers are done via messages. This means that most of the time the data are sent by copy from the UI Thread to the workers. Very few types are sent by reference. If you’re a C++ developer by the way, don’t see that really as a reference. Indeed, with Transferable Objects, the original object is cleared from the caller context (UI Thread) when transfered to the worker. And almost only the ArrayBuffer falls into this category today anyway and we would need to send an ImageData type rather.

But this not our main problem to try to speed up our 3D engine in HTML5. In case of a copy, the data are sent via a memcpy() operation which is very fast. The real problem is when the workers will have finished their processing job. You need to send back the results to the main thread and this UI thread need to iterate through each arrays sent back to rebuild the main pixels arrays. This operation will simply kills any performance gain we could have in the workers unfortunately.

In conclusion, I haven’t find a way to implement a parallelism approach in HTML5 with our 3D software engine. But I may have missed something. If you manage to workaround the current web workers limitations to obtain a significant performance boost, I’m open to suggestions! 🙂

Next tutorial will talk about flat shading and gouraud shading. Our objects will start to really shine! 🙂

12 thoughts on “Tutorial part 4 – bonus: learning how to write a 3D software engine in C#, TS or JS – Optimizing & Parallelism

  1. In part 1 –   how modern 3D works with our GPUs.

    I think you meant "without GPU's" —

    Please explain why you are doing graphics without using the GPU??  

    Could you extend these examples to Directx, Webgl, Opengl etc using the GPU and measure the speed up

  2. Hi Jet,

     I'm doing graphics without the GPU for educational purposes. The idea is to really understand the story of 3D since the beginning and why GPUs are so important today to leverage very powerfull Realtime 3D. If you want to go deeper with GPU, please of a look to the BabylonJS WebGL engine David Catuhe has built: http://www.babylonjs.com

    Cheers,

    David

  3. > And almost only the ArrayBuffer falls into this category today anyway and we would need to send an ImageData type rather.

    ImageData.data is a Uint8ArrayBuffer, which you can write in directly (in fact, in tutorial 2 of this series you do exactly that). You can do all your physics on Uint32ArrayBuffers in one WebWorker, pass that to the render thread, and pass the final Uint8 backbuffer to the main thread to blit to the canvas.

  4. hi david

    1- nice articles i learned a lot from your articles than most of the web cr*p. learning by a READABLE EXAMPLE is just the best and fast way, many thanks for that :).
    2- there is the “SharedArrayBuffer” which IMO is not the best way for this engine or any 2d/3d engine, the problem with it you need to allocate a new memory for it so this way you will create two buffer one for the canvas and the other for the “SharedArrayBuffer”, here is a link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer
    3- new to the javascript is the “webassembly” here is a link https://en.wikipedia.org/wiki/WebAssembly

    i started learning javascript last month so i can write one code to target most of the platform, then webassembly throw that idea down to the toilet 🙂 , now i need to do C language or other language too.

    lastly, i really had fun reading your articles and doing the 3d engine, i did it using barycentric because i didn’t wanna simply copy paste your work, i wanted to learn these stuff, also sorry my english is not that good.

    cheers

  5. hi david

    after reading a lot of resources, it turns out transferable-objects is the right way at least at the moment without the need to copy back the ArrayBuffer to the main ui here is a link : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays

    qoute from the link above “JavaScript typed arrays split the implementation into buffers and views.” now that’s very clever i must say good job. i made a basic example to check that, well it seems that i cannot copy the example here will.

    how can i send you the example ?

      1. hi david

        don’t waste your time, or sorry i wasted your time, parallelism without structure copy is not possible, and your conclusion in the article still stands after all these years 🙂 now that’s magic 🙂

        i will delete the above link it is useless.

        sorry again.

Leave a Reply