diff options
| -rw-r--r-- | src/main.zig | 188 |
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, |