Rework multithreaded rendering

Render worker tasks are now split into chunks rather than row blocks for better thread utilisation

12 files changed, 161 insertions, 97 deletions

diff --git a/index.html b/index.html
index a240714..3d3db08 100644
--- a/index.html
+++ b/index.html
@@ -70,7 +70,7 @@
               <div class="form-group">
                 <label class="form-switch">
                   <input id="direct-transfer" type="checkbox" checked>
-                  <i class="form-icon"></i> Direct memory transfer
+                  <i class="form-icon"></i> Zero-copy array transfer
                 </label>
               </div>
               <div class="form-group">
@@ -83,7 +83,7 @@
                 <label class="form-label label-sm" for="threads">Render threads</label>
                 <!-- TODO style -->
                 <div class="input-group"> 
-                  <input id="threads" class="slider" type="range" min="2" max="12" value="4" step="2">
+                  <input id="threads" class="slider" type="range" min="2" max="32" value="4" step="2">
                   <span id="threads-value" class="input-group-addon">4</span>
                 </div>
               </div>
diff --git a/src/Framebuffer.ts b/src/Framebuffer.ts
index a6ad5fc..63881ae 100644
--- a/src/Framebuffer.ts
+++ b/src/Framebuffer.ts
@@ -1,3 +1,5 @@
+import {Colour} from "./models/Colour";
+
 export class Framebuffer {
   readonly width: number;
   readonly height: number;
@@ -22,11 +24,11 @@ export class Framebuffer {
     );
   }
 
-  writePixelAt(x: number, y: number, r: number, g: number, b: number) {
+  writePixelAt(x: number, y: number, colour: Colour) {
     const startIdx = (y * this.width + x) * 4;
-    this.canvasImageData.data[startIdx] = r;
-    this.canvasImageData.data[startIdx + 1] = g;
-    this.canvasImageData.data[startIdx + 2] = b;
+    this.canvasImageData.data[startIdx] = colour.r;
+    this.canvasImageData.data[startIdx + 1] = colour.g;
+    this.canvasImageData.data[startIdx + 2] = colour.b;
     this.canvasImageData.data[startIdx + 3] = 255; // No A
   }
 
diff --git a/src/RaytraceDispatcher.ts b/src/RaytraceDispatcher.ts
index be36bb1..6d1bbd7 100644
--- a/src/RaytraceDispatcher.ts
+++ b/src/RaytraceDispatcher.ts
@@ -1,13 +1,20 @@
 import {Framebuffer} from './Framebuffer';
-import {RaytraceContext} from './RaytraceContext';
+import {RaytraceContext} from './models/RaytraceContext';
 import {instanceToPlain} from 'class-transformer';
 import 'reflect-metadata';
 import {Logger} from './Logger';
+import {FrameChunk} from "./models/FrameChunk";
+import {Colour} from "./models/Colour";
 
 export class RaytraceDispatcher {
-  private renderStartMs: number;
-  private completedThreads = 0;
-  private processedResponses = 0;
+  private readonly renderStartMs: number;
+  private readonly contextJson: String;
+  private readonly chunks: FrameChunk[];
+  private readonly raytraceWorkers: Worker[];
+  private nextChunkIndex = 0;
+  private completedWorkers = 0;
+  private chunkBorderWidth = 1;
+
   constructor(
     readonly framebuffer: Framebuffer,
     readonly context: RaytraceContext,
@@ -15,74 +22,115 @@ export class RaytraceDispatcher {
     readonly onComplete: Function
   ) {
     this.renderStartMs = new Date().getTime();
+    this.contextJson = JSON.stringify(instanceToPlain(context))
+    this.chunks = [];
+    this.raytraceWorkers = [];
   }
 
   requestRender() {
-    // Assumes height%threads = 0
-    const rowBatchSize = this.context.height / this.context.options.numThreads;
+    let chunkHeight, chunkWidth;
 
-    for (let y = 0; y < this.context.height; y += rowBatchSize) {
-      const rowStartIndex = y;
-      const rowEndIndex = y + rowBatchSize - 1;
-      this.dispatchRaytraceWorker(rowStartIndex, rowEndIndex, this.context);
+    if (this.context.height <= 720) {
+      chunkHeight = 64;
+      chunkWidth = 64;
+      this.chunkBorderWidth = 2;
+    } else {
+      chunkHeight = 128;
+      chunkWidth = 128;
+      this.chunkBorderWidth = 5;
     }
-  }
 
-  private dispatchRaytraceWorker(
-    rowStartIndex: number,
-    rowEndIndex: number,
-    context: RaytraceContext
-  ) {
-    this.logger.log(`Dispatching worker: rows ${rowStartIndex}-${rowEndIndex}`);
+    // Process scene into chunks
+    for (let y = 0; y < this.context.height; y+= chunkHeight) {
+      for (let x = 0 ; x < this.context.width; x+= chunkWidth) {
+        this.chunks.push(new FrameChunk(x, y, chunkWidth, chunkHeight));
+      }
+    }
+    this.logger.log(`Scene split into ${this.chunks.length} chunks of ${chunkWidth}x${chunkHeight}`);
 
-    const raytracer = new Worker(new URL('./Raytracer.ts', import.meta.url));
+    // Spawn worker threads
+    for (let n = 0; n < this.context.options.numThreads; n++) {
+      const worker = new Worker(new URL('./Raytracer.ts', import.meta.url));
+      worker.onmessage = (event) => { this.onMessageHandler(worker, event) };
+      this.raytraceWorkers.push(worker);
+    }
+    this.logger.log(`Spawned ${this.context.options.numThreads} render threads`);
 
-    raytracer.postMessage({
+    // Start raytrace
+    for (let worker of this.raytraceWorkers) {
+      this.raytraceNextChunk(worker);
+    }
+  }
+
+  private raytraceNextChunk(worker: Worker) {
+    const chunkIndex = this.nextChunkIndex++;
+    let chunk = this.chunks[chunkIndex];
+    this.drawChunkBorder(chunk, this.chunkBorderWidth);
+    worker.postMessage({
       type: 'raytraceStart',
-      rowStartIndex: rowStartIndex,
-      rowEndIndex: rowEndIndex,
-      context: JSON.stringify(instanceToPlain(context)),
+      chunk: chunk,
+      chunkIndex: chunkIndex,
+      context: this.contextJson,
     });
-
-    raytracer.onmessage = ({data}) => {
-      if (data.type === 'raytraceResultRow') {
-        this.processResponse(data.rowIndex, data.resultBuffer);
-      }
-      if (data.type === 'raytraceComplete') {
-        this.handleWorkerComplete();
-      }
-    };
   }
 
-  private handleWorkerComplete() {
-    if (++this.completedThreads === this.context.options.numThreads) {
-      this.framebuffer.flush();
-      this.logger.log(
-        `Raytrace completed in ${new Date().getTime() - this.renderStartMs}ms`
-      );
+  private onMessageHandler(worker: Worker, message: MessageEvent) {
+    if (message.data.type === 'raytraceComplete') {
+      this.writeChunkToFramebuffer(message.data.chunkIndex, message.data.resultBuffer);
+    }
+
+    // Queue next work if available
+    if (this.nextChunkIndex < this.chunks.length) {
+      this.raytraceNextChunk(worker);
+    } else {
+      worker.terminate();
+      this.completedWorkers++;
+    }
+
+    if (this.completedWorkers == this.context.options.numThreads) {
       this.onComplete();
+      this.logger.log(`Raytrace completed in ${new Date().getTime() - this.renderStartMs}ms\n`);
     }
   }
 
-  private processResponse(rowIndex: number, rowData: ArrayBuffer) {
-    const clampedRowData = new Uint8ClampedArray(rowData);
+  private writeChunkToFramebuffer(chunkIndex: number, data: ArrayBuffer) {
+    const clampedRowData = new Uint8ClampedArray(data);
+    const chunk = this.chunks[chunkIndex];
+
+    for (let y = 0; y < chunk.height; y++) {
+      for (let x = 0; x < chunk.width; x++) {
+        const idx = (x * 3) + ((chunk.width * 3) * y);
+        const r = clampedRowData[idx];
+        const g = clampedRowData[idx + 1];
+        const b = clampedRowData[idx + 2];
+        const colour = new Colour(r, g, b);
 
-    for (let x = 0; x < this.context.width; x++) {
-      const idx = x * 3;
-      const r = clampedRowData[idx];
-      const g = clampedRowData[idx + 1];
-      const b = clampedRowData[idx + 2];
-      this.framebuffer.writePixelAt(x, rowIndex, r, g, b);
+        this.framebuffer.writePixelAt( (x+chunk.xStart), (y+chunk.yStart), colour);
+      }
     }
 
-    if (
-      this.context.options.bufferDrawCalls &&
-      ++this.processedResponses >= this.context.height * 0.05
-    ) {
-      this.framebuffer.flush();
-      this.processedResponses = 0;
-    } else if (!this.context.options.bufferDrawCalls) {
-      this.framebuffer.flush();
+    this.framebuffer.flush();
+  }
+
+  private drawChunkBorder(chunk: FrameChunk, borderWidth: number) {
+    const width = chunk.width;
+    const height = chunk.height;
+
+    const borderColour = new Colour(220, 128, 128);
+    const unrenderedAreaColour = new Colour(160, 160, 160);
+
+    for (let y = 0; y < height; y++) {
+      for (let x = 0; x < width; x++) {
+
+        if (y < borderWidth || y >= (height-borderWidth) || x < borderWidth || x >= (width-borderWidth)) {
+          this.framebuffer.writePixelAt(chunk.xStart+x, chunk.yStart+y, borderColour);
+        } else {
+          this.framebuffer.writePixelAt(chunk.xStart+x, chunk.yStart+y, unrenderedAreaColour);
+        }
+
+      }
     }
+
+    this.framebuffer.flush();
   }
 }
diff --git a/src/Raytracer.ts b/src/Raytracer.ts
index 34cbe00..f59e8f0 100644
--- a/src/Raytracer.ts
+++ b/src/Raytracer.ts
@@ -1,8 +1,8 @@
-import {Colour} from './Colour';
-import {Plane, Sphere} from './Geometry';
-import {Albedo, Material} from './Material';
-import {RaytraceContext} from './RaytraceContext';
-import {Vector} from './Vector';
+import {Colour} from './models/Colour';
+import {Plane, Sphere} from './models/Geometry';
+import {Albedo, Material} from './models/Material';
+import {RaytraceContext} from './models/RaytraceContext';
+import {Vector} from './models/Vector';
 
 import {plainToInstance} from 'class-transformer';
 import 'reflect-metadata';
@@ -13,13 +13,15 @@ self.onmessage = ({data}) => {
     const context = plainToInstance(RaytraceContext, serialisedContext);
 
     const raytracer = new Raytracer(
-      data.rowStartIndex,
-      data.rowEndIndex,
+      data.chunkIndex,
+      data.chunk.xStart,
+      data.chunk.yStart,
+      data.chunk.width,
+      data.chunk.height,
       context
     );
 
     raytracer.process();
-    self.close();
   }
 };
 
@@ -42,18 +44,22 @@ class RayIntersectionResult {
 
 class Raytracer {
   constructor(
-    readonly rowStartIndex: number,
-    readonly rowEndIndex: number,
+    readonly chunkIndex: number,
+    readonly xStart: number,
+    readonly yStart: number,
+    readonly width: number,
+    readonly height: number,
     readonly context: RaytraceContext
   ) {}
 
   process() {
-    for (let y = this.rowStartIndex; y <= this.rowEndIndex; y++) {
-      const resultBuffer = new Uint8ClampedArray(3 * this.context.width);
+    const resultBuffer = new Uint8ClampedArray(3 * this.width * this.height);
 
-      for (let x = 0; x < this.context.width; x++) {
-        const rayX = x + 0.5 - this.context.width / 2;
-        const rayY = -(y + 100) + this.context.height / 2;
+    for (let y = 0; y < this.height; y++) {
+      for (let x = 0; x < this.width; x++) {
+
+        const rayX = x + this.xStart + 0.5 - this.context.width / 2;
+        const rayY = -(y+this.yStart + 100) + this.context.height / 2;
         const rayZ =
           -this.context.height / (2 * Math.tan(this.context.fov / 2));
         const rayDirection = new Vector(rayX, rayY, rayZ).normalise();
@@ -61,27 +67,25 @@ class Raytracer {
 
         const pixelValue = this.raytrace(ray);
 
-        const buffIdx = x * 3;
+        const buffIdx = (x * 3) + ((this.width *3) * y);
         resultBuffer[buffIdx] = pixelValue.r;
         resultBuffer[buffIdx + 1] = pixelValue.g;
         resultBuffer[buffIdx + 2] = pixelValue.b;
       }
-
-      if (this.context.options.directMemoryTransfer) {
-        // prettier-ignore
-        // eslint-disable-next-line @typescript-eslint/ban-ts-comment
-        // @ts-ignore
-        self.postMessage({type: 'raytraceResultRow', rowIndex: y, resultBuffer: resultBuffer.buffer}, [resultBuffer.buffer]);
-      } else {
-        self.postMessage({
-          type: 'raytraceResultRow',
-          resultBuffer: resultBuffer.buffer,
-          rowIndex: y,
-        });
-      }
     }
 
-    self.postMessage({type: 'raytraceComplete'});
+    if (this.context.options.directMemoryTransfer) {
+      // prettier-ignore
+      // eslint-disable-next-line @typescript-eslint/ban-ts-comment
+      // @ts-ignore
+      self.postMessage({type: 'raytraceComplete', chunkIndex: this.chunkIndex, resultBuffer: resultBuffer.buffer}, [resultBuffer.buffer]);
+    } else {
+      self.postMessage({
+        type: 'raytraceComplete',
+        chunkIndex: this.chunkIndex,
+        resultBuffer: resultBuffer.buffer
+      });
+    }
   }
 
   private raytrace(ray: Ray, recursionDepth = 0): Colour {
diff --git a/src/index.ts b/src/index.ts
index df4d988..c19edfc 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -1,11 +1,11 @@
-import {Colour} from './Colour';
+import {Colour} from './models/Colour';
 import {Framebuffer} from './Framebuffer';
-import {Plane, Sphere} from './Geometry';
-import {Light} from './Light';
-import {Albedo, Material} from './Material';
+import {Plane, Sphere} from './models/Geometry';
+import {Light} from './models/Light';
+import {Albedo, Material} from './models/Material';
 import {RaytraceDispatcher} from './RaytraceDispatcher';
-import {RaytraceContext, RaytracerOptions} from './RaytraceContext';
-import {Vector} from './Vector';
+import {RaytraceContext, RaytracerOptions} from './models/RaytraceContext';
+import {Vector} from './models/Vector';
 import {Logger} from './Logger';
 
 function render() {
@@ -41,7 +41,7 @@ function initDispatcher(options: RaytracerOptions): RaytraceDispatcher {
     new Sphere(1, new Vector(-10, -3, -25), matteMaterial(0, 146, 178)),
     new Sphere(1, new Vector(-10, -3, -20), matteMaterial(185, 18, 27)),
     new Sphere(1, new Vector(-2.5, -3, -20), matteMaterial(115, 45, 217)),
-    new Sphere(1.5, new Vector(-10.5, -2.5, -16), materialMirror),
+    new Sphere(2, new Vector(-10.5, -2, -16), materialMirror),
     new Sphere(1, new Vector(-3, -3, -16), matteMaterial(247, 178, 173)),
     new Sphere(1, new Vector(-6, -3, -18), matteMaterial(154, 188, 167)),
     new Sphere(1, new Vector(-6, -3, -12), matteMaterial(96, 125, 139)),
@@ -119,7 +119,7 @@ function parseResolution(): {width: number; height: number} {
     case '360p':
       return {width: 640, height: 360};
     case '480p':
-      return {width: 854, height: 480};
+      return {width: 832, height: 480};
     case '720p':
     default:
       return {width: 1280, height: 720};
diff --git a/src/Colour.ts b/src/models/Colour.ts
index 3c9d8da..3c9d8da 100644
--- a/src/Colour.ts
+++ b/src/models/Colour.ts
diff --git a/src/models/FrameChunk.ts b/src/models/FrameChunk.ts
new file mode 100644
index 0000000..f05fd88
--- /dev/null
+++ b/src/models/FrameChunk.ts
@@ -0,0 +1,10 @@
+export class FrameChunk {
+    constructor(
+      readonly xStart: number,
+      readonly yStart: number,
+      readonly width: number,
+      readonly height: number
+    ) {
+
+    }
+}
\ No newline at end of file
diff --git a/src/Geometry.ts b/src/models/Geometry.ts
index 556c7ea..556c7ea 100644
--- a/src/Geometry.ts
+++ b/src/models/Geometry.ts
diff --git a/src/Light.ts b/src/models/Light.ts
index 58e4185..58e4185 100644
--- a/src/Light.ts
+++ b/src/models/Light.ts
diff --git a/src/Material.ts b/src/models/Material.ts
index f0af5e2..f0af5e2 100644
--- a/src/Material.ts
+++ b/src/models/Material.ts
diff --git a/src/RaytraceContext.ts b/src/models/RaytraceContext.ts
index acd4336..acd4336 100644
--- a/src/RaytraceContext.ts
+++ b/src/models/RaytraceContext.ts
diff --git a/src/Vector.ts b/src/models/Vector.ts
index 2be8e57..2be8e57 100644
--- a/src/Vector.ts
+++ b/src/models/Vector.ts