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        if self.root == NULL_INDEX {
102            return;
103        }
104
105        self.validate_structure(self.root);
106        self.validate_metrics(self.root);
107
108        let mut free_count = 0;
109        let mut free_index = self.free_list;
110        while free_index != NULL_INDEX {
111            debug_assert!(0 <= free_index && free_index < self.node_capacity());
112            free_index = self.nodes[free_index as usize].next;
113            free_count += 1;
114        }
115
116        let height = self.height();
117        let computed_height = self.compute_height(self.root);
118        debug_assert!(height == computed_height);
119        let _ = (height, computed_height);
120
121        debug_assert!(self.node_count + free_count == self.node_capacity());
122        let _ = free_count;
123    }
124
125    /// Validate this tree has no enlarged AABBs. For testing.
126    /// (b2DynamicTree_ValidateNoEnlarged)
127    pub fn validate_no_enlarged(&self) {
128        for node in &self.nodes {
129            if node.flags & ALLOCATED_NODE != 0 {
130                debug_assert!(node.flags & ENLARGED_NODE == 0);
131            }
132        }
133    }
134}
box2d_rust/dynamic_tree/validate.rs

box2d_rust/dynamic_tree/
validate.rs
