box2d_rust/dynamic_tree/
validate.rs

1// Tree validation from dynamic_tree.c. The C versions are compiled in only
2// with B2_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: 2023 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, max_int};
10
11impl DynamicTree {
12    /// Compute the height of a sub-tree. (static b2ComputeHeight)
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 b2ValidateStructure)
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 b2ValidateMetrics)
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        if node.is_leaf() {
73            debug_assert!(node.height == 0);
74            return;
75        }
76
77        let child1 = node.child1;
78        let child2 = node.child2;
79
80        debug_assert!(0 <= child1 && child1 < self.node_capacity());
81        debug_assert!(0 <= child2 && child2 < self.node_capacity());
82
83        let height1 = self.nodes[child1 as usize].height;
84        let height2 = self.nodes[child2 as usize].height;
85        let height = 1 + if height1 > height2 { height1 } else { height2 };
86        debug_assert!(node.height == height);
87
88        debug_assert!(aabb_contains(node.aabb, self.nodes[child1 as usize].aabb));
89        debug_assert!(aabb_contains(node.aabb, self.nodes[child2 as usize].aabb));
90
91        let category_bits =
92            self.nodes[child1 as usize].category_bits | self.nodes[child2 as usize].category_bits;
93        debug_assert!(node.category_bits == category_bits);
94
95        self.validate_metrics(child1);
96        self.validate_metrics(child2);
97    }
98
99    /// Validate this tree. For testing. (b2DynamicTree_Validate)
100    pub fn validate(&self) {
101        // B2_VALIDATE: compiled out in release like the C reference
102        if !cfg!(debug_assertions) {
103            return;
104        }
105
106        if self.root == NULL_INDEX {
107            return;
108        }
109
110        self.validate_structure(self.root);
111        self.validate_metrics(self.root);
112
113        let mut free_count = 0;
114        let mut free_index = self.free_list;
115        while free_index != NULL_INDEX {
116            debug_assert!(0 <= free_index && free_index < self.node_capacity());
117            free_index = self.nodes[free_index as usize].next;
118            free_count += 1;
119        }
120
121        let height = self.height();
122        let computed_height = self.compute_height(self.root);
123        debug_assert!(height == computed_height);
124        let _ = (height, computed_height);
125
126        debug_assert!(self.node_count + free_count == self.node_capacity());
127        let _ = free_count;
128    }
129
130    /// Validate this tree has no enlarged AABBs. For testing.
131    /// (b2DynamicTree_ValidateNoEnlarged)
132    pub fn validate_no_enlarged(&self) {
133        // B2_VALIDATE: compiled out in release like the C reference
134        if !cfg!(debug_assertions) {
135            return;
136        }
137
138        for node in &self.nodes {
139            if node.flags & ALLOCATED_NODE != 0 {
140                debug_assert!(node.flags & ENLARGED_NODE == 0);
141            }
142        }
143    }
144}
box2d_rust/dynamic_tree/validate.rs

box2d_rust/dynamic_tree/
validate.rs
