Add configurable render chunk allocation modes

5 files changed, 95 insertions, 47 deletions

diff --git a/index.html b/index.html
index 3d3db08..0e2ab2f 100644
--- a/index.html
+++ b/index.html
@@ -63,12 +63,6 @@
               <span>Performance options</span>
               <div class="form-group">
                 <label class="form-switch">
-                  <input id="buffer-draw" type="checkbox" checked>
-                  <i class="form-icon"></i> Buffer draw calls
-                </label>
-              </div>
-              <div class="form-group">
-                <label class="form-switch">
                   <input id="direct-transfer" type="checkbox" checked>
                   <i class="form-icon"></i> Zero-copy array transfer
                 </label>
@@ -87,6 +81,17 @@
                   <span id="threads-value" class="input-group-addon">4</span>
                 </div>
               </div>
+              <div class="form-group">
+                <label class="form-group">
+                  <label id="chunk-allocation-mode-label" class="form-label label-sm" for="res">Chunk allocation mode</label>
+                  <select id="chunk-allocation-mode" class="form-select select-sm">
+                    <option value="SEQUENTIAL" selected>Sequential</option>
+                    <option value="RANDOM">Random</option>
+                    <option value="CENTER_TO_EDGE">Center to edge</option>
+                    <option value="EDGE_TO_CENTER">Edge to center</option>
+                  </select>
+                </label>
+              </div>
             </div>
             <div class="column col-4">
               <div class="form-group">
diff --git a/src/RaytraceDispatcher.ts b/src/RaytraceDispatcher.ts
index 6d1bbd7..b8b5e6a 100644
--- a/src/RaytraceDispatcher.ts
+++ b/src/RaytraceDispatcher.ts
@@ -1,5 +1,5 @@
 import {Framebuffer} from './Framebuffer';
-import {RaytraceContext} from './models/RaytraceContext';
+import {ChunkAllocationMode, RaytraceContext} from './models/RaytraceContext';
 import {instanceToPlain} from 'class-transformer';
 import 'reflect-metadata';
 import {Logger} from './Logger';
@@ -9,9 +9,8 @@ import {Colour} from "./models/Colour";
 export class RaytraceDispatcher {
   private readonly renderStartMs: number;
   private readonly contextJson: String;
-  private readonly chunks: FrameChunk[];
+  private readonly chunkQueue: FrameChunk[];
   private readonly raytraceWorkers: Worker[];
-  private nextChunkIndex = 0;
   private completedWorkers = 0;
   private chunkBorderWidth = 1;
 
@@ -23,7 +22,7 @@ export class RaytraceDispatcher {
   ) {
     this.renderStartMs = new Date().getTime();
     this.contextJson = JSON.stringify(instanceToPlain(context))
-    this.chunks = [];
+    this.chunkQueue = [];
     this.raytraceWorkers = [];
   }
 
@@ -43,15 +42,15 @@ export class RaytraceDispatcher {
     // 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.chunkQueue.push(new FrameChunk(x, y, chunkWidth, chunkHeight));
       }
     }
-    this.logger.log(`Scene split into ${this.chunks.length} chunks of ${chunkWidth}x${chunkHeight}`);
+    this.logger.log(`Scene split into ${this.chunkQueue.length} chunks of ${chunkWidth}x${chunkHeight}`);
 
     // 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) };
+      worker.onmessage = (event) => { this.processRaytraceWorkerResult(worker, event) };
       this.raytraceWorkers.push(worker);
     }
     this.logger.log(`Spawned ${this.context.options.numThreads} render threads`);
@@ -63,24 +62,33 @@ export class RaytraceDispatcher {
   }
 
   private raytraceNextChunk(worker: Worker) {
-    const chunkIndex = this.nextChunkIndex++;
-    let chunk = this.chunks[chunkIndex];
+    const chunk = this.getNextChunk();
     this.drawChunkBorder(chunk, this.chunkBorderWidth);
     worker.postMessage({
       type: 'raytraceStart',
       chunk: chunk,
-      chunkIndex: chunkIndex,
       context: this.contextJson,
     });
   }
 
-  private onMessageHandler(worker: Worker, message: MessageEvent) {
-    if (message.data.type === 'raytraceComplete') {
-      this.writeChunkToFramebuffer(message.data.chunkIndex, message.data.resultBuffer);
+  private getNextChunk(): FrameChunk {
+    switch(this.context.options.chunkAllocationMode) {
+      case ChunkAllocationMode.SEQUENTIAL:
+        return this.getNextChunkSequential();
+      case ChunkAllocationMode.RANDOM:
+        return this.getNextChunkRandom();
+      case ChunkAllocationMode.CENTER_TO_EDGE:
+        return this.getNextChunkCenterToEdge();
+      case ChunkAllocationMode.EDGE_TO_CENTER:
+        return this.getNextChunkEdgeToCenter();
     }
+  }
+
+  private processRaytraceWorkerResult(worker: Worker, message: MessageEvent) {
+    this.writeChunkToFramebuffer(message.data.chunk, message.data.resultBuffer);
 
     // Queue next work if available
-    if (this.nextChunkIndex < this.chunks.length) {
+    if (this.chunkQueue.length > 0) {
       this.raytraceNextChunk(worker);
     } else {
       worker.terminate();
@@ -93,9 +101,34 @@ export class RaytraceDispatcher {
     }
   }
 
-  private writeChunkToFramebuffer(chunkIndex: number, data: ArrayBuffer) {
+  private getNextChunkSequential(): FrameChunk {
+    return this.chunkQueue.shift()!;
+  }
+
+  private getNextChunkRandom(): FrameChunk {
+    const index = Math.floor(Math.random() * this.chunkQueue.length);
+    const chunk = this.chunkQueue[index];
+    this.chunkQueue.splice(index, 1);
+    return chunk
+  }
+
+  private getNextChunkCenterToEdge(): FrameChunk {
+    const index = Math.floor((this.chunkQueue.length - 1) / 2);
+    const chunk = this.chunkQueue[index];
+    this.chunkQueue.splice(index, 1);
+    return chunk;
+  }
+
+  private getNextChunkEdgeToCenter(): FrameChunk {
+    if (this.chunkQueue.length % 2 == 0) {
+      return this.chunkQueue.shift()!;
+    } else {
+      return this.chunkQueue.pop()!;
+    }
+  }
+
+  private writeChunkToFramebuffer(chunk: FrameChunk, 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++) {
diff --git a/src/Raytracer.ts b/src/Raytracer.ts
index f59e8f0..86d368e 100644
--- a/src/Raytracer.ts
+++ b/src/Raytracer.ts
@@ -6,20 +6,14 @@ import {Vector} from './models/Vector';
 
 import {plainToInstance} from 'class-transformer';
 import 'reflect-metadata';
+import {FrameChunk} from "./models/FrameChunk";
 
 self.onmessage = ({data}) => {
   if (data.type === 'raytraceStart') {
     const serialisedContext: Object = JSON.parse(data.context);
     const context = plainToInstance(RaytraceContext, serialisedContext);
 
-    const raytracer = new Raytracer(
-      data.chunkIndex,
-      data.chunk.xStart,
-      data.chunk.yStart,
-      data.chunk.width,
-      data.chunk.height,
-      context
-    );
+    const raytracer = new Raytracer(data.chunk, context);
 
     raytracer.process();
   }
@@ -44,22 +38,18 @@ class RayIntersectionResult {
 
 class Raytracer {
   constructor(
-    readonly chunkIndex: number,
-    readonly xStart: number,
-    readonly yStart: number,
-    readonly width: number,
-    readonly height: number,
+    readonly chunk: FrameChunk,
     readonly context: RaytraceContext
   ) {}
 
   process() {
-    const resultBuffer = new Uint8ClampedArray(3 * this.width * this.height);
+    const resultBuffer = new Uint8ClampedArray(3 * this.chunk.width * this.chunk.height);
 
-    for (let y = 0; y < this.height; y++) {
-      for (let x = 0; x < this.width; x++) {
+    for (let y = 0; y < this.chunk.height; y++) {
+      for (let x = 0; x < this.chunk.width; x++) {
 
-        const rayX = x + this.xStart + 0.5 - this.context.width / 2;
-        const rayY = -(y+this.yStart + 100) + this.context.height / 2;
+        const rayX = x + this.chunk.xStart + 0.5 - this.context.width / 2;
+        const rayY = -(y+this.chunk.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();
@@ -67,7 +57,7 @@ class Raytracer {
 
         const pixelValue = this.raytrace(ray);
 
-        const buffIdx = (x * 3) + ((this.width *3) * y);
+        const buffIdx = (x * 3) + ((this.chunk.width *3) * y);
         resultBuffer[buffIdx] = pixelValue.r;
         resultBuffer[buffIdx + 1] = pixelValue.g;
         resultBuffer[buffIdx + 2] = pixelValue.b;
@@ -78,11 +68,10 @@ class Raytracer {
       // 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]);
+      self.postMessage({chunk: this.chunk, resultBuffer: resultBuffer.buffer}, [resultBuffer.buffer]);
     } else {
       self.postMessage({
-        type: 'raytraceComplete',
-        chunkIndex: this.chunkIndex,
+        chunk: this.chunk,
         resultBuffer: resultBuffer.buffer
       });
     }
diff --git a/src/index.ts b/src/index.ts
index c19edfc..f58cc5b 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -4,7 +4,7 @@ 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 './models/RaytraceContext';
+import {ChunkAllocationMode, RaytraceContext, RaytracerOptions} from './models/RaytraceContext';
 import {Vector} from './models/Vector';
 import {Logger} from './Logger';
 
@@ -109,8 +109,8 @@ function parseOptions(): RaytracerOptions {
     refractions: getInputElement('refractions-toggle').checked,
     maxRecurseDepth: 5,
     maxDrawDistance: 1000,
-    bufferDrawCalls: getInputElement('buffer-draw').checked,
     directMemoryTransfer: getInputElement('direct-transfer').checked,
+    chunkAllocationMode: getChunkAllocationMode()
   };
 }
 
@@ -132,6 +132,20 @@ function parseResolution(): {width: number; height: number} {
   }
 }
 
+function getChunkAllocationMode(): ChunkAllocationMode {
+  switch (getInputElement('chunk-allocation-mode').value) {
+    case 'SEQUENTIAL':
+    default:
+      return ChunkAllocationMode.SEQUENTIAL;
+    case 'RANDOM':
+      return ChunkAllocationMode.RANDOM
+    case 'CENTER_TO_EDGE':
+      return ChunkAllocationMode.CENTER_TO_EDGE
+    case 'EDGE_TO_CENTER':
+      return ChunkAllocationMode.EDGE_TO_CENTER
+  }
+}
+
 function registerEventListeners() {
   getRenderButton().addEventListener('click', render);
 
diff --git a/src/models/RaytraceContext.ts b/src/models/RaytraceContext.ts
index acd4336..d028c1a 100644
--- a/src/models/RaytraceContext.ts
+++ b/src/models/RaytraceContext.ts
@@ -38,6 +38,13 @@ export interface RaytracerOptions {
   refractions: boolean;
   maxRecurseDepth: number;
   maxDrawDistance: number;
-  bufferDrawCalls: boolean;
   directMemoryTransfer: boolean;
+  chunkAllocationMode: ChunkAllocationMode;
 }
+
+export enum ChunkAllocationMode {
+  SEQUENTIAL,
+  RANDOM,
+  CENTER_TO_EDGE,
+  EDGE_TO_CENTER
+}
\ No newline at end of file