this repo has no description
altagos.dev
1const std = @import("std");
2
3const AABB = @import("AABB.zig");
4const hittable = @import("hittable.zig");
5const Hittable = hittable.Hittable;
6const HitRecord = hittable.HitRecord;
7const IntervalF32 = @import("interval.zig").IntervalF32;
8const Ray = @import("Ray.zig");
9const util = @import("util.zig");
10
11const log = std.log.scoped(.BVH);
12
13const BVH = @This();
14
15const Ast = struct {
16 left: ?*Node = null,
17 right: ?*Node = null,
18 bbox: AABB = AABB{},
19
20 pub fn hit(self: *Ast, r: *Ray, ray_t: IntervalF32) ?HitRecord {
21 // if (!self.bbox.hit(r, ray_t)) return null;
22
23 var rec: ?HitRecord = null;
24 var interval = ray_t;
25 if (self.left) |left| {
26 if (left.hit(r, interval)) |res| {
27 interval = IntervalF32.init(ray_t.min, res.t);
28 rec = res;
29 }
30 }
31
32 if (self.right) |right| {
33 if (right.hit(r, interval)) |res| {
34 return res;
35 }
36 }
37
38 return rec;
39 }
40};
41
42const Leaf = struct {
43 objects: []Hittable,
44 bbox: AABB,
45
46 pub fn hit(self: *Leaf, r: *Ray, ray_t: IntervalF32) ?HitRecord {
47 var rec: ?HitRecord = null;
48 var interval = ray_t;
49 for (self.objects) |obj| {
50 if (obj.hit(r, interval)) |res| {
51 interval = IntervalF32.init(ray_t.min, res.t);
52 rec = res;
53 }
54 }
55 return rec;
56 }
57};
58
59threadlocal var reached_depth: usize = 0;
60threadlocal var max_objects: usize = 0;
61
62const Node = union(enum) {
63 ast: Ast,
64 leaf: Leaf,
65
66 pub fn init(
67 self: *Node,
68 allocator: std.mem.Allocator,
69 objects: []Hittable,
70 max_depth: usize,
71 depth: usize,
72 ) !void {
73 if (reached_depth < depth) reached_depth = depth;
74
75 var ast_bbox = AABB{};
76 for (0..objects.len) |idx| {
77 ast_bbox = AABB.initAB(&ast_bbox, &objects[idx].boundingBox());
78 }
79
80 if (depth >= max_depth or objects.len <= 2) {
81 if (max_objects < objects.len) max_objects = objects.len;
82 self.* = .{ .leaf = .{ .objects = objects, .bbox = ast_bbox } };
83 return;
84 }
85
86 const axis = ast_bbox.longestAxis();
87 std.mem.sort(Hittable, objects, axis, boxCompare);
88
89 var left = try allocator.create(Node);
90 var right = try allocator.create(Node);
91
92 const mid = objects.len / 2;
93 try left.init(allocator, objects[0..mid], max_depth, depth + 1);
94 try right.init(allocator, objects[mid..], max_depth, depth + 1);
95
96 self.* = .{ .ast = .{
97 .left = left,
98 .right = right,
99 .bbox = ast_bbox,
100 } };
101 }
102
103 pub fn deinit(self: *Node, allocator: std.mem.Allocator) void {
104 switch (self.*) {
105 .ast => |*a| {
106 if (a.left) |left| {
107 left.deinit(allocator);
108 allocator.destroy(left);
109 }
110 if (a.right) |right| {
111 right.deinit(allocator);
112 allocator.destroy(right);
113 }
114 },
115 .leaf => |*l| {
116 allocator.destroy(&l.objects);
117 },
118 }
119 }
120
121 pub fn bbox(self: *Node) AABB {
122 return self.bbox;
123 }
124
125 pub inline fn hit(self: *Node, r: *Ray, ray_t: IntervalF32) ?HitRecord {
126 switch (self.*) {
127 inline else => |*n| if (n.bbox.hit(r, ray_t)) {
128 return n.hit(r, ray_t);
129 },
130 }
131
132 return null;
133 }
134};
135
136allocator: std.mem.Allocator,
137root: *Node,
138
139pub fn init(allocator: std.mem.Allocator, objects: hittable.HittableList, max_depth: usize) !BVH {
140 defer @constCast(&objects).deinit();
141 log.debug("Creating BVH Tree with {} objects", .{objects.list.items.len});
142
143 const root = try allocator.create(Node);
144 try root.init(allocator, objects.list.items, max_depth, 0);
145
146 log.debug("Reached depth of: {}, max objects: {}", .{ reached_depth, max_objects });
147
148 return .{
149 .allocator = allocator,
150 .root = root,
151 };
152}
153
154pub fn deinit(self: *BVH) void {
155 self.root.deinit(self.allocator);
156}
157
158pub inline fn hit(self: *const BVH, r: *Ray, ray_t: IntervalF32) ?HitRecord {
159 return self.root.hit(r, ray_t);
160}
161
162fn boxCompare(axis_index: i32, a: Hittable, b: Hittable) bool {
163 return @constCast(&a).boundingBox().axisInterval(axis_index).min < @constCast(&b).boundingBox().axisInterval(axis_index).min;
164}