tiny.geometry.Bvh

1pub const Bvh = struct {2    nodes: []const Node,3    triangles: []const Triangle,4    /// The mesh index of the triangle in each tree slot.5    order: []const u32,6    /// The depth of the deepest node, with the root at zero.7    depth: u32,8    /// The largest coordinate magnitude of the root box.9    magnitude: f32,1011    /// The tree over no triangles, which answers every query with nothing.12    pub const empty: Bvh = .{ .nodes = &empty_nodes, .triangles = &.{}, .order = &.{}, .depth = 0, .magnitude = 0 };1314    const Task = struct {15        node: u32,16        begin: u32,17        end: u32,18        depth: u32,19    };2021    /// Builds the tree over `mesh` into `storage`, which must fit the mesh's22    /// triangle count. The same mesh builds the same tree every time.23    pub fn build(mesh: Mesh, storage: Storage) Bvh {24        assert(mesh.isWellFormed());25        const count = mesh.triangleCount();26        assert(storage.fits(count));27        const order = storage.order[0..count];28        const centroids = storage.centroids[0..count];29        for (order, centroids, 0..) |*slot, *centroid, index| {30            slot.* = @intCast(index);31            centroid.* = mesh.triangle(index).centroid();32        }33        const builder = Builder{ .mesh = mesh, .centroids = centroids };3435        var node_count: u32 = 1;36        var depth: u32 = 0;37        var tasks: [depth_limit]Task = undefined;38        var task_count: usize = 1;39        tasks[0] = .{ .node = 0, .begin = 0, .end = @intCast(count), .depth = 0 };40        while (task_count > 0) {41            task_count -= 1;42            const task = tasks[task_count];43            const range = order[task.begin..task.end];44            var box = Aabb.empty;45            var centroid_box = Aabb.empty;46            for (range) |index| {47                box = box.join(mesh.triangle(index).bounds());48                centroid_box = centroid_box.joinPoint(centroids[index]);49            }50            depth = @max(depth, task.depth);51            assert(task.depth < depth_limit);52            if (range.len <= leaf_capacity) {53                storage.nodes[task.node] = .{ .min = box.min, .first = task.begin, .max = box.max, .count = @intCast(range.len) };54                continue;55            }56            assert(task.depth + levelsNeeded(range.len) < depth_limit);57            const allow_surface_area = task.depth + levelsNeeded(range.len) + 1 < depth_limit;58            const middle = task.begin + @as(u32, @intCast(builder.split(range, centroid_box, allow_surface_area)));59            const left = node_count;60            node_count += 2;61            assert(node_count <= Storage.nodeCapacity(count));62            storage.nodes[task.node] = .{ .min = box.min, .first = left, .max = box.max, .count = 0 };63            assert(task_count + 2 <= depth_limit);64            tasks[task_count] = .{ .node = left + 1, .begin = middle, .end = task.end, .depth = task.depth + 1 };65            tasks[task_count + 1] = .{ .node = left, .begin = task.begin, .end = middle, .depth = task.depth + 1 };66            task_count += 2;67        }68        for (storage.triangles[0..count], order) |*triangle, index| triangle.* = mesh.triangle(index);69        const root = storage.nodes[0].box();70        return .{71            .nodes = storage.nodes[0..node_count],72            .triangles = storage.triangles[0..count],73            .order = order,74            .depth = depth,75            .magnitude = if (count == 0) 0 else root.magnitude(),76        };77    }7879    pub fn triangleCount(bvh: Bvh) usize {80        return bvh.triangles.len;81    }8283    /// The nearest triangle the ray meets with `t` in `[t_min, t_max]`, as84    /// `Mesh.raycast` answers it.85    pub fn raycast(bvh: Bvh, ray: Ray, t_min: f32, t_max: f32, stats: ?*Stats) Error!?RayHit {86        assert(t_min <= t_max);87        var walk = try Walk.begin(bvh, stats);88        if (walk.done) return null;89        const slack = tolerance.boxSlack(@max(bvh.magnitude, ray.origin.abs().maxComponent()));90        var best: ?RayHit = null;91        var best_t = t_max;92        const root = intersect.raySlab(ray, bvh.nodes[0].box().inflate(slack), best_t) orelse return null;93        try walk.stack.push(.{ .node = 0, .entry = root[0] });94        while (walk.next(best_t)) |node| {95            if (node.isLeaf()) {96                for (node.first..node.first + node.count) |slot| {97                    walk.tested();98                    const hit = intersect.rayTriangle(ray, bvh.triangles[slot]) orelse continue;99                    if (hit.t < t_min or hit.t > best_t) continue;100                    const index = bvh.order[slot];101                    if (best) |held| {102                        if (hit.t == held.t and index > held.triangle) continue;103                    }104                    best = .{ .t = hit.t, .u = hit.u, .v = hit.v, .triangle = index };105                    best_t = hit.t;106                }107                continue;108            }109            const near = intersect.raySlab(ray, bvh.nodes[node.first].box().inflate(slack), best_t);110            const far = intersect.raySlab(ray, bvh.nodes[node.first + 1].box().inflate(slack), best_t);111            try walk.pushOrdered(node.first, near, far);112        }113        return best;114    }115116    /// Whether the ray meets any triangle with `t` in `[t_min, t_max]`.117    pub fn raycastAny(bvh: Bvh, ray: Ray, t_min: f32, t_max: f32, stats: ?*Stats) Error!bool {118        assert(t_min <= t_max);119        var walk = try Walk.begin(bvh, stats);120        if (walk.done) return false;121        const slack = tolerance.boxSlack(@max(bvh.magnitude, ray.origin.abs().maxComponent()));122        const root = intersect.raySlab(ray, bvh.nodes[0].box().inflate(slack), t_max) orelse return false;123        try walk.stack.push(.{ .node = 0, .entry = root[0] });124        while (walk.next(t_max)) |node| {125            if (node.isLeaf()) {126                for (node.first..node.first + node.count) |slot| {127                    walk.tested();128                    const hit = intersect.rayTriangle(ray, bvh.triangles[slot]) orelse continue;129                    if (hit.t >= t_min and hit.t <= t_max) return true;130                }131                continue;132            }133            const near = intersect.raySlab(ray, bvh.nodes[node.first].box().inflate(slack), t_max);134            const far = intersect.raySlab(ray, bvh.nodes[node.first + 1].box().inflate(slack), t_max);135            try walk.pushOrdered(node.first, near, far);136        }137        return false;138    }139140    /// The triangles the sphere touches, as `Mesh.overlapSphere` answers it.141    pub fn overlapSphere(bvh: Bvh, sphere: Sphere, out: []u32, stats: ?*Stats) Error!Overlap {142        assert(sphere.radius >= 0);143        const reach = sphere.bounds();144        const slack = tolerance.boxSlack(@max(bvh.magnitude, reach.magnitude()));145        var collector = Collector{ .out = out };146        var walk = try Walk.begin(bvh, stats);147        if (walk.done) return collector.finish();148        try walk.stack.push(.{ .node = 0, .entry = 0 });149        while (walk.next(0)) |node| {150            if (!intersect.sphereAabb(sphere, node.box().inflate(slack))) continue;151            if (node.isLeaf()) {152                for (node.first..node.first + node.count) |slot| {153                    walk.tested();154                    if (intersect.sphereTriangle(sphere, bvh.triangles[slot])) collector.add(bvh.order[slot]);155                }156                continue;157            }158            try walk.stack.push(.{ .node = node.first + 1, .entry = 0 });159            try walk.stack.push(.{ .node = node.first, .entry = 0 });160        }161        return collector.finish();162    }163164    /// The triangles the capsule touches, as `Mesh.overlapCapsule` answers165    /// it.166    pub fn overlapCapsule(bvh: Bvh, capsule: Capsule, out: []u32, stats: ?*Stats) Error!Overlap {167        assert(capsule.radius >= 0);168        const reach = capsule.bounds();169        const slack = tolerance.boxSlack(@max(bvh.magnitude, reach.magnitude()));170        var collector = Collector{ .out = out };171        var walk = try Walk.begin(bvh, stats);172        if (walk.done) return collector.finish();173        try walk.stack.push(.{ .node = 0, .entry = 0 });174        while (walk.next(0)) |node| {175            if (!reach.overlaps(node.box().inflate(slack))) continue;176            if (node.isLeaf()) {177                for (node.first..node.first + node.count) |slot| {178                    walk.tested();179                    if (intersect.capsuleTriangle(capsule, bvh.triangles[slot])) collector.add(bvh.order[slot]);180                }181                continue;182            }183            try walk.stack.push(.{ .node = node.first + 1, .entry = 0 });184            try walk.stack.push(.{ .node = node.first, .entry = 0 });185        }186        return collector.finish();187    }188189    /// The first triangle the sphere touches as it moves by `displacement`,190    /// as `Mesh.sweepSphere` answers it.191    pub fn sweepSphere(bvh: Bvh, sphere: Sphere, displacement: Vec3, stats: ?*Stats) Error!?SweepHit {192        assert(sphere.radius >= 0);193        const moved = Sphere{ .center = sphere.center.add(displacement), .radius = sphere.radius };194        const reach = sphere.bounds().join(moved.bounds());195        const margin = Swept{196            .low = Vec3.splat(-sphere.radius),197            .high = Vec3.splat(sphere.radius),198            .slack = tolerance.boxSlack(@max(bvh.magnitude, reach.magnitude())),199        };200        const path = Ray{ .origin = sphere.center, .direction = displacement };201        return bvh.sweepWith(path, margin, stats, sphere, sweepSphereTriangle);202    }203204    /// The first triangle the capsule touches as it moves by `displacement`,205    /// as `Mesh.sweepCapsule` answers it.206    pub fn sweepCapsule(bvh: Bvh, capsule: Capsule, displacement: Vec3, stats: ?*Stats) Error!?SweepHit {207        assert(capsule.radius >= 0);208        const moved = Capsule{ .a = capsule.a.add(displacement), .b = capsule.b.add(displacement), .radius = capsule.radius };209        const reach = capsule.bounds().join(moved.bounds());210        const axis = capsule.b.sub(capsule.a);211        const margin = Swept{212            .low = axis.min(.{}).sub(Vec3.splat(capsule.radius)),213            .high = axis.max(.{}).add(Vec3.splat(capsule.radius)),214            .slack = tolerance.boxSlack(@max(bvh.magnitude, reach.magnitude())),215        };216        const path = Ray{ .origin = capsule.a, .direction = displacement };217        return bvh.sweepWith(path, margin, stats, capsule, sweepCapsuleTriangle);218    }219220    fn sweepSphereTriangle(sphere: Sphere, displacement: Vec3, triangle: Triangle) ?sweep.Hit {221        return sweep.sphereTriangle(sphere, displacement, triangle);222    }223224    fn sweepCapsuleTriangle(capsule: Capsule, displacement: Vec3, triangle: Triangle) ?sweep.Hit {225        return sweep.capsuleTriangle(capsule, displacement, triangle);226    }227228    /// Walks the boxes a moving reference point can reach while the shape it229    /// carries could touch them. A shape whose points lie at offsets in230    /// `[low, high]` from the reference point touches a box only while that231    /// point is inside the box grown by `-high` below and `-low` above.232    fn sweepWith(233        bvh: Bvh,234        path: Ray,235        margin: Swept,236        stats: ?*Stats,237        shape: anytype,238        comptime test_triangle: fn (@TypeOf(shape), Vec3, Triangle) ?sweep.Hit,239    ) Error!?SweepHit {240        var walk = try Walk.begin(bvh, stats);241        if (walk.done) return null;242        var best: ?SweepHit = null;243        var best_t: f32 = 1;244        const root = intersect.raySlab(path, margin.grow(bvh.nodes[0]), best_t) orelse return null;245        try walk.stack.push(.{ .node = 0, .entry = root[0] });246        while (walk.next(best_t)) |node| {247            if (node.isLeaf()) {248                for (node.first..node.first + node.count) |slot| {249                    walk.tested();250                    const hit = test_triangle(shape, path.direction, bvh.triangles[slot]) orelse continue;251                    if (hit.t > best_t) continue;252                    const index = bvh.order[slot];253                    if (best) |held| {254                        if (hit.t == held.t and index > held.triangle) continue;255                    }256                    best = .{ .t = hit.t, .point = hit.point, .normal = hit.normal, .triangle = index };257                    best_t = hit.t;258                }259                continue;260            }261            const near = intersect.raySlab(path, margin.grow(bvh.nodes[node.first]), best_t);262            const far = intersect.raySlab(path, margin.grow(bvh.nodes[node.first + 1]), best_t);263            try walk.pushOrdered(node.first, near, far);264        }265        return best;266    }267};

1pub const Bvh = bvh.Bvh;