box3d_rust/dynamic_tree/
validate.rs

1// Tree validation from dynamic_tree.c. The C versions are compiled in only
2// with B3_ENABLE_VALIDATION; here they always run when called (they are only
3// invoked explicitly and from rebuild) and assert in debug builds.
4// SPDX-FileCopyrightText: 2025 Erin Catto
5// SPDX-License-Identifier: MIT
6
7use super::{DynamicTree, ALLOCATED_NODE, ENLARGED_NODE};
8use crate::core::NULL_INDEX;
9use crate::math_functions::{aabb_contains, is_valid_aabb, max_int};
10
11impl DynamicTree {
12    /// Compute the height of a sub-tree. (static b3ComputeHeightRecurse)
13    fn compute_height(&self, node_id: i32) -> i32 {
14        debug_assert!(0 <= node_id && node_id < self.node_capacity());
15        let node = &self.nodes[node_id as usize];
16
17        if node.is_leaf() {
18            return 0;
19        }
20
21        let height1 = self.compute_height(node.child1);
22        let height2 = self.compute_height(node.child2);
23        1 + max_int(height1, height2)
24    }
25
26    /// (static b3ValidateStructure)
27    fn validate_structure(&self, index: i32) {
28        if index == NULL_INDEX {
29            return;
30        }
31
32        if index == self.root {
33            debug_assert!(self.nodes[index as usize].parent == NULL_INDEX);
34        }
35
36        let node = &self.nodes[index as usize];
37
38        debug_assert!(node.flags == 0 || (node.flags & ALLOCATED_NODE) != 0);
39
40        if node.is_leaf() {
41            debug_assert!(node.height == 0);
42            return;
43        }
44
45        let child1 = node.child1;
46        let child2 = node.child2;
47
48        debug_assert!(0 <= child1 && child1 < self.node_capacity());
49        debug_assert!(0 <= child2 && child2 < self.node_capacity());
50
51        debug_assert!(self.nodes[child1 as usize].parent == index);
52        debug_assert!(self.nodes[child2 as usize].parent == index);
53
54        if (self.nodes[child1 as usize].flags | self.nodes[child2 as usize].flags) & ENLARGED_NODE
55            != 0
56        {
57            debug_assert!(node.flags & ENLARGED_NODE != 0);
58        }
59
60        self.validate_structure(child1);
61        self.validate_structure(child2);
62    }
63
64    /// (static b3ValidateMetrics)
65    fn validate_metrics(&self, index: i32) {
66        if index == NULL_INDEX {
67            return;
68        }
69
70        let node = &self.nodes[index as usize];
71
72        debug_assert!(is_valid_aabb(node.aabb));
73
74        if node.is_leaf() {
75            debug_assert!(node.height == 0);
76            return;
77        }
78
79        let child1 = node.child1;
80        let child2 = node.child2;
81
82        debug_assert!(0 <= child1 && child1 < self.node_capacity());
83        debug_assert!(0 <= child2 && child2 < self.node_capacity());
84
85        let height1 = self.nodes[child1 as usize].height as i32;
86        let height2 = self.nodes[child2 as usize].height as i32;
87        let height = 1 + max_int(height1, height2);
88        debug_assert!(node.height as i32 == height);
89
90        debug_assert!(aabb_contains(node.aabb, self.nodes[child1 as usize].aabb));
91        debug_assert!(aabb_contains(node.aabb, self.nodes[child2 as usize].aabb));
92
93        let category_bits =
94            self.nodes[child1 as usize].category_bits | self.nodes[child2 as usize].category_bits;
95        debug_assert!(node.category_bits == category_bits);
96
97        self.validate_metrics(child1);
98        self.validate_metrics(child2);
99    }
100
101    /// Validate this tree. For testing. (b3DynamicTree_Validate)
102    pub fn validate(&self) {
103        if self.root == NULL_INDEX {
104            return;
105        }
106
107        self.validate_structure(self.root);
108        self.validate_metrics(self.root);
109
110        let mut free_count = 0;
111        let mut free_index = self.free_list;
112        while free_index != NULL_INDEX {
113            debug_assert!(0 <= free_index && free_index < self.node_capacity());
114            free_index = self.nodes[free_index as usize].next;
115            free_count += 1;
116        }
117
118        let height = self.height();
119        let computed_height = self.compute_height(self.root);
120        debug_assert!(height == computed_height);
121        let _ = (height, computed_height);
122
123        debug_assert!(self.node_count + free_count == self.node_capacity());
124        let _ = free_count;
125    }
126
127    /// Validate this tree has no enlarged AABBs. For testing.
128    /// (b3DynamicTree_ValidateNoEnlarged)
129    pub fn validate_no_enlarged(&self) {
130        for node in &self.nodes {
131            if node.flags & ALLOCATED_NODE != 0 {
132                debug_assert!(node.flags & ENLARGED_NODE == 0);
133            }
134        }
135    }
136}
box3d_rust/dynamic_tree/validate.rs

box3d_rust/dynamic_tree/
validate.rs
