3.10

1 files changed, 175 insertions, 13 deletions

diff --git a/src/main.zig b/src/main.zig
index e615e8b..0979ca9 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -242,18 +242,30 @@ const HittableTag = enum {
     sphere,
     movingSphere,
     list,
+    bvhNode,
 };
 
 const Hittable = union(HittableTag) {
     sphere: Sphere,
     movingSphere: MovingSphere,
     list: HittableList,
+    bvhNode: BvhNode,
 
-    fn hit(h: Hittable, r: Ray, t_min: f64, t_max: f64, record: *HitRecord) bool {
+    fn hit(h: Hittable, r: Ray, tMin: f64, tMax: f64, record: *HitRecord) bool {
         return switch (h) {
-            HittableTag.sphere => |sphere| sphere.hit(r, t_min, t_max, record),
-            HittableTag.movingSphere => |movingSphere| movingSphere.hit(r, t_min, t_max, record),
-            HittableTag.list => |list| list.hit(r, t_min, t_max, record),
+            HittableTag.sphere => |sphere| sphere.hit(r, tMin, tMax, record),
+            HittableTag.movingSphere => |movingSphere| movingSphere.hit(r, tMin, tMax, record),
+            HittableTag.list => |list| list.hit(r, tMin, tMax, record),
+            HittableTag.bvhNode => |node| node.hit(r, tMin, tMax, record),
+        };
+    }
+
+    fn boudingBox(h: Hittable, time0: f64, time1: f64, outputBox: *Aabb) bool {
+        return switch (h.*) {
+            HittableTag.sphere => |sphere| sphere.boudingBox(time0, time1, outputBox),
+            HittableTag.movingSphere => |movingSphere| movingSphere.boudingBox(time0, time1, outputBox),
+            HittableTag.list => |list| list.boudingBox(time0, time1, outputBox),
+            HittableTag.bvhNode => |node| node.boudingBox(time0, time1, outputBox),
         };
     }
 
@@ -262,6 +274,7 @@ const Hittable = union(HittableTag) {
             HittableTag.sphere => |sphere| sphere.deinit(allocator),
             HittableTag.movingSphere => |movingSphere| movingSphere.deinit(allocator),
             HittableTag.list => |list| list.deinit(allocator),
+            HittableTag.bvhNode => |node| node.deinit(allocator),
         };
     }
 };
@@ -271,7 +284,7 @@ const Sphere = struct {
     radius: f64,
     material: *const Material,
 
-    fn hit(sphere: Sphere, r: Ray, t_min: f64, t_max: f64, record: *HitRecord) bool {
+    fn hit(sphere: Sphere, r: Ray, tMin: f64, tMax: f64, record: *HitRecord) bool {
         const oc = r.origin.sub(sphere.center);
         const a = r.dir.normSquared();
         const half_b = Vec3.dot(oc, r.dir);
@@ -286,9 +299,9 @@ const Sphere = struct {
 
         // Find the nearest root that lies in the acceptable range.
         var root = (-half_b - sqrtd) / a;
-        if (root < t_min or t_max < root) {
+        if (root < tMin or tMax < root) {
             root = (-half_b + sqrtd) / a;
-            if (root < t_min or t_max < root) {
+            if (root < tMin or tMax < root) {
                 // out of range
                 return false;
             }
@@ -308,6 +321,18 @@ const Sphere = struct {
         return true;
     }
 
+    fn boudingBox(sphere: Sphere, time0: f64, time1: f64, outputBox: *Aabb) bool {
+        _ = time0;
+        _ = time1;
+        const o = sphere.center;
+        const r = sphere.radius;
+        outputBox.* = .{
+            .min = o.sub(.{ .x = r, .y = r, .z = r }),
+            .max = o.add(.{ .x = r, .y = r, .z = r }),
+        };
+        return true;
+    }
+
     fn deinit(sphere: *const Sphere, allocator: anytype) void {
         allocator.destroy(sphere.material);
     }
@@ -321,7 +346,7 @@ const MovingSphere = struct {
     radius: f64,
     material: *const Material,
 
-    fn hit(sphere: MovingSphere, r: Ray, t_min: f64, t_max: f64, record: *HitRecord) bool {
+    fn hit(sphere: MovingSphere, r: Ray, tMin: f64, tMax: f64, record: *HitRecord) bool {
         const center_ = sphere.center(r.time);
         const oc = r.origin.sub(center_);
         const a = r.dir.normSquared();
@@ -337,9 +362,9 @@ const MovingSphere = struct {
 
         // Find the nearest root that lies in the acceptable range.
         var root = (-half_b - sqrtd) / a;
-        if (root < t_min or t_max < root) {
+        if (root < tMin or tMax < root) {
             root = (-half_b + sqrtd) / a;
-            if (root < t_min or t_max < root) {
+            if (root < tMin or tMax < root) {
                 // out of range
                 return false;
             }
@@ -359,6 +384,22 @@ const MovingSphere = struct {
         return true;
     }
 
+    fn boudingBox(sphere: MovingSphere, time0: f64, time1: f64, outputBox: *Aabb) bool {
+        const o0 = sphere.center(time0);
+        const o1 = sphere.center(time1);
+        const r = sphere.radius;
+        const box0 = .{
+            .min = o0.sub(.{ .x = r, .y = r, .z = r }),
+            .max = o0.add(.{ .x = r, .y = r, .z = r }),
+        };
+        const box1 = .{
+            .min = o1.sub(.{ .x = r, .y = r, .z = r }),
+            .max = o1.add(.{ .x = r, .y = r, .z = r }),
+        };
+        outputBox.* = surroundingBox(box0, box1);
+        return true;
+    }
+
     fn center(sphere: MovingSphere, t: f64) Point3 {
         return sphere.center0.add(sphere.center1.sub(sphere.center0).mul((t - sphere.time0) / (sphere.time1 - sphere.time0)));
     }
@@ -381,13 +422,13 @@ fn makeSphere(center: Point3, radius: f64, material: *const Material) Hittable {
 const HittableList = struct {
     objects: ArrayList(Hittable),
 
-    fn hit(list: HittableList, r: Ray, t_min: f64, t_max: f64, record: *HitRecord) bool {
+    fn hit(list: HittableList, r: Ray, tMin: f64, tMax: f64, record: *HitRecord) bool {
         var hit_anything = false;
-        var closest_so_far = t_max;
+        var closest_so_far = tMax;
 
         for (list.objects.items) |object| {
             var rec: HitRecord = undefined;
-            if (object.hit(r, t_min, closest_so_far, &rec)) {
+            if (object.hit(r, tMin, closest_so_far, &rec)) {
                 hit_anything = true;
                 closest_so_far = rec.t;
                 record.* = rec;
@@ -396,6 +437,22 @@ const HittableList = struct {
         return hit_anything;
     }
 
+    fn boudingBox(list: HittableList, time0: f64, time1: f64, outputBox: *Aabb) bool {
+        if (list.objects.items.len == 0) {
+            return false;
+        }
+        var firstBox = true;
+        var tmpBox: Aabb = undefined;
+        for (list.objects.items) |object| {
+            if (!object.boudingBox(time0, time1, tmpBox)) {
+                return false;
+            }
+            outputBox = if (firstBox) tmpBox else surroundingBox(outputBox, tmpBox);
+            firstBox = false;
+        }
+        return true;
+    }
+
     fn deinit(list: *const HittableList, allocator: anytype) void {
         for (list.objects.items) |object| {
             object.deinit(allocator);
@@ -411,6 +468,11 @@ fn deg2rad(degree: f64) f64 {
     return degree * pi / 180.0;
 }
 
+// [min, max)
+fn randomInt(comptime T: type, rand: std.rand.Random, min: T, max: T) T {
+    return rand.intRangeLessThan(T, min, max);
+}
+
 // [0, 1)
 fn randomReal01(rand: std.rand.Random) f64 {
     return rand.float(f64);
@@ -465,6 +527,106 @@ const Aabb = struct {
     }
 };
 
+fn surroundingBox(box0: Aabb, box1: Aabb) Aabb {
+    return .{
+        .min = .{
+            .x = @min(box0.min.x, box1.min.x),
+            .y = @min(box0.min.y, box1.min.y),
+            .z = @min(box0.min.z, box1.min.z),
+        },
+        .max = .{
+            .x = @max(box0.max.x, box1.max.x),
+            .y = @max(box0.max.y, box1.max.y),
+            .z = @max(box0.max.z, box1.max.z),
+        },
+    };
+}
+
+const BvhNode = struct {
+    left: *Hittable, // TODO
+    right: *Hittable, // TODO
+    box: Aabb,
+
+    fn init(
+        objects: ArrayList(*Hittable),
+        start: usize,
+        end: usize,
+        time0: f64,
+        time1: f64,
+    ) BvhNode {
+        var left: *Hittable = undefined;
+        var right: *Hittable = undefined;
+
+        var objects_ = objects;
+        const axis = randomInt(u8, 0, 3);
+
+        const objectSpan = end - start;
+        if (objectSpan == 1) {
+            left = objects.items[start];
+            right = objects.items[start];
+        } else if (objectSpan == 2) {
+            if (BvhNode.boxCompare(axis, objects[start], objects[start + 1])) {
+                left = objects[start];
+                right = objects[start + 1];
+            } else {
+                left = objects[start + 1];
+                right = objects[start];
+            }
+        } else {
+            std.sort.sort(*Hittable, objects_, axis, BvhNode.boxCompare);
+            const mid = start + objectSpan / 2;
+            left.* = .{ .bvhNode = BvhNode.init(objects, start, mid, time0, time1) };
+            right.* = .{ .bvhNode = BvhNode.init(objects, mid, end, time0, time1) };
+        }
+
+        var boxLeft: Aabb = undefined;
+        var boxRight: Aabb = undefined;
+
+        if (!left.boudingBox(time0, time1, boxLeft) || !right.boudingBox(time0, time1, boxRight)) {
+            // ERROR
+        }
+
+        return .{
+            .left = left,
+            .right = right,
+            .box = surroundingBox(boxLeft, boxRight),
+        };
+    }
+
+    fn boxCompare(axis: u8, a: *const Hittable, b: *const Hittable) bool {
+        if (axis == 0) {
+            return a.x < b.x;
+        } else if (axis == 1) {
+            return a.y < b.y;
+        } else {
+            return a.z < b.z;
+        }
+    }
+
+    fn hit(node: BvhNode, r: Ray, tMin: f64, tMax: f64, record: *HitRecord) bool {
+        if (!node.box.hit(r, tMin, tMax)) {
+            return false;
+        }
+
+        const hitLeft = node.left.hit(r, tMin, tMax, record);
+        const hitRight = node.right.hit(r, tMin, if (hitLeft) record.t else tMax, record);
+
+        return hitLeft or hitRight;
+    }
+
+    fn boudingBox(node: BvhNode, time0: f64, time1: f64, outputBox: *Aabb) bool {
+        _ = time0;
+        _ = time1;
+        outputBox.* = node.box;
+        return true;
+    }
+
+    fn deinit(node: *const BvhNode, allocator: anytype) void {
+        _ = node;
+        _ = allocator;
+    }
+};
+
 const Camera = struct {
     origin: Point3,
     horizontal: Vec3,