altagos.dev
this repo has no description
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
13pub const 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
88 if (axis == 0) {
89 std.mem.sort(Hittable, objects, .{}, boxXCompare);
90 } else if (axis == 1) {
91 std.mem.sort(Hittable, objects, .{}, boxYCompare);
92 } else {
93 std.mem.sort(Hittable, objects, .{}, boxZCompare);
94 }
95
96 var left = try allocator.create(Node);
97 var right = try allocator.create(Node);
98
99 const mid = objects.len / 2;
100 try left.init(allocator, objects[0..mid], max_depth, depth + 1);
101 try right.init(allocator, objects[mid..], max_depth, depth + 1);
102
103 self.* = .{ .ast = .{
104 .left = left,
105 .right = right,
106 .bbox = ast_bbox,
107 } };
108 }
109
110 pub fn deinit(self: *Node, allocator: std.mem.Allocator) void {
111 switch (self.*) {
112 .ast => |*a| {
113 if (a.left) |left| {
114 left.deinit(allocator);
115 allocator.destroy(left);
116 }
117 if (a.right) |right| {
118 right.deinit(allocator);
119 allocator.destroy(right);
120 }
121 },
122 .leaf => |*l| {
123 allocator.destroy(&l.objects);
124 },
125 }
126 }
127
128 pub fn bbox(self: *Node) AABB {
129 return self.bbox;
130 }
131
132 pub inline fn hit(self: *Node, r: *Ray, ray_t: IntervalF32) ?HitRecord {
133 switch (self.*) {
134 inline else => |*n| if (n.bbox.hit(r, ray_t)) {
135 return n.hit(r, ray_t);
136 } else {
137 return null;
138 },
139 }
140 }
141};
142
143allocator: std.mem.Allocator,
144root: *Node,
145
146pub fn init(allocator: std.mem.Allocator, objects: hittable.HittableList, max_depth: usize) !BVH {
147 defer @constCast(&objects).deinit();
148 log.info("Creating BVH Tree with {} objects", .{objects.list.items.len});
149
150 const root = try allocator.create(Node);
151 try root.init(allocator, objects.list.items, max_depth, 0);
152 // const bbox = root.recomputeBbox();
153
154 log.debug("Reached depth of: {}, max objects: {}", .{ reached_depth, max_objects });
155
156 return .{
157 .allocator = allocator,
158 .root = root,
159 };
160}
161
162pub fn deinit(self: *BVH) void {
163 self.root.deinit(self.allocator);
164}
165
166pub inline fn hit(self: *BVH, r: *Ray, ray_t: IntervalF32) ?HitRecord {
167 return self.root.hit(r, ray_t);
168}
169
170inline fn boxCompare(a: *Hittable, b: *Hittable, axis_index: i32) bool {
171 return a.boundingBox().axisInterval(axis_index).min < b.boundingBox().axisInterval(axis_index).min;
172}
173
174fn boxXCompare(_: @TypeOf(.{}), a: Hittable, b: Hittable) bool {
175 return boxCompare(@constCast(&a), @constCast(&b), 0);
176}
177
178fn boxYCompare(_: @TypeOf(.{}), a: Hittable, b: Hittable) bool {
179 return boxCompare(@constCast(&a), @constCast(&b), 1);
180}
181
182fn boxZCompare(_: @TypeOf(.{}), a: Hittable, b: Hittable) bool {
183 return boxCompare(@constCast(&a), @constCast(&b), 2);
184}