1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
//! Logic for propagating transforms through the hierarchy of grids.
use crate::prelude::*;
use bevy_ecs::prelude::*;
use bevy_reflect::Reflect;
use bevy_transform::prelude::*;
/// Marks entities in the big space hierarchy that are themselves roots of a low-precision subtree.
/// While finding these entities is slow, we only have to do it during hierarchy or archetype
/// changes. Once the entity is marked (updating its archetype), querying it is now very fast.
///
/// - This entity's parent must be a high precision entity (with a [`CellCoord`]).
/// - This entity must not have a [`CellCoord`].
/// - This entity may or may not have children.
#[derive(Component, Default, Reflect)]
pub struct LowPrecisionRoot;
impl Grid {
/// Update the `GlobalTransform` of entities with a [`CellCoord`], using the [`Grid`] the entity
/// belongs to.
pub fn propagate_high_precision(
mut stats: Option<ResMut<crate::timing::PropagationStats>>,
grids: Query<&Grid>,
mut entities: ParamSet<(
Query<(
Ref<CellCoord>,
Ref<Transform>,
Ref<ChildOf>,
&mut GlobalTransform,
)>,
Query<(&Grid, &mut GlobalTransform), With<BigSpace>>,
)>,
) {
let start = bevy_platform::time::Instant::now();
// Performance note: I've also tried to iterate over each grid's children at once, to avoid
// the grid and parent lookup, but that made things worse because it prevented dumb
// parallelism. The only thing I can see to make this faster is archetype change detection.
// Change filters are not archetype filters, so they scale with the total number of entities
// that match the query, regardless of change.
entities
.p0()
.par_iter_mut()
.for_each(|(cell, transform, parent, mut global_transform)| {
if let Ok(grid) = grids.get(parent.parent()) {
// Optimization: we don't need to recompute the transforms if the entity hasn't
// moved and the floating origin's local origin in that grid hasn't changed.
//
// This also ensures we don't trigger change detection on GlobalTransforms when
// they haven't changed.
//
// This check can have a big impact on reducing computations for entities in the
// same grid as the floating origin, i.e. the main camera. It also means that as
// the floating origin moves between cells, that could suddenly cause a spike in
// the amount of computation needed that grid. In the future, we might be able
// to spread that work across grids, entities far away can maybe be delayed for
// a grid or two without being noticeable.
if !grid.local_floating_origin().is_local_origin_unchanged()
|| transform.is_changed()
|| cell.is_changed()
|| parent.is_changed()
{
*global_transform = grid.global_transform(&cell, &transform);
}
}
});
// Root grids
//
// These are handled separately because the root grid doesn't have a Transform or GridCell -
// it wouldn't make sense because it is the root, and these components are relative to their
// parent. Due to floating origins, it *is* possible for the root grid to have a
// GlobalTransform - this is what makes it possible to place a low precision (Transform
// only) entity in a root transform - it is relative to the origin of the root grid.
entities
.p1()
.iter_mut()
.for_each(|(grid, mut global_transform)| {
if grid.local_floating_origin().is_local_origin_unchanged() {
return; // By definition, this means the grid has not moved
}
// The global transform of the root grid is the same as the transform of an entity
// at the origin - it is determined entirely by the local origin position:
*global_transform =
grid.global_transform(&CellCoord::default(), &Transform::IDENTITY);
});
if let Some(stats) = stats.as_mut() {
stats.high_precision_propagation += start.elapsed();
}
}
/// Marks entities with [`LowPrecisionRoot`]. Handles adding and removing the component.
pub fn tag_low_precision_roots(
mut stats: Option<ResMut<crate::timing::PropagationStats>>,
mut commands: Commands,
valid_parent: Query<(), (With<CellCoord>, With<GlobalTransform>, With<Children>)>,
unmarked: Query<
(Entity, &ChildOf),
(
With<Transform>,
With<GlobalTransform>,
Without<CellCoord>,
Without<LowPrecisionRoot>,
Or<(Changed<ChildOf>, Added<Transform>)>,
),
>,
invalidated: Query<
Entity,
(
With<LowPrecisionRoot>,
Or<(
Without<Transform>,
Without<GlobalTransform>,
With<CellCoord>,
Without<ChildOf>,
)>,
),
>,
has_possibly_invalid_parent: Query<(Entity, &ChildOf), With<LowPrecisionRoot>>,
) {
let start = bevy_platform::time::Instant::now();
for (entity, parent) in unmarked.iter() {
if valid_parent.contains(parent.parent()) {
commands.entity(entity).insert(LowPrecisionRoot);
}
}
for entity in invalidated.iter() {
commands.entity(entity).remove::<LowPrecisionRoot>();
}
for (entity, parent) in has_possibly_invalid_parent.iter() {
if !valid_parent.contains(parent.parent()) {
commands.entity(entity).remove::<LowPrecisionRoot>();
}
}
if let Some(stats) = stats.as_mut() {
stats.low_precision_root_tagging += start.elapsed();
}
}
/// Update the [`GlobalTransform`] of entities with a [`Transform`], without a [`CellCoord`], and
/// that are children of an entity with a [`GlobalTransform`]. This will recursively propagate
/// entities that only have low-precision [`Transform`]s, just like bevy's built in systems.
pub fn propagate_low_precision(
mut stats: Option<ResMut<crate::timing::PropagationStats>>,
root_parents: Query<
Ref<GlobalTransform>,
(
// A root big space does not have a grid cell, and not all high precision entities
// have a grid
Or<(With<Grid>, With<CellCoord>)>,
),
>,
roots: Query<(Entity, &ChildOf), With<LowPrecisionRoot>>,
transform_query: Query<
(Ref<Transform>, &mut GlobalTransform, Option<&Children>),
(
With<ChildOf>,
Without<CellCoord>, // Used to prove access to GlobalTransform is disjoint
Without<Grid>,
),
>,
parent_query: Query<
(Entity, Ref<ChildOf>),
(
With<Transform>,
With<GlobalTransform>,
Without<CellCoord>,
Without<Grid>,
),
>,
) {
let start = bevy_platform::time::Instant::now();
let update_transforms = |low_precision_root, parent_transform: Ref<GlobalTransform>| {
// High precision global transforms are change-detected and are only updated if that
// entity has moved relative to the floating origin's grid cell.
let changed = parent_transform.is_changed();
#[expect(
unsafe_code,
reason = "`propagate_recursive()` is unsafe due to its use of `Query::get_unchecked()`."
)]
// SAFETY:
// - Unlike the bevy version of this, we do not iterate over all children of the root
// and manually verify each child has a parent component that points back to the same
// entity. Instead, we query the roots directly, so we know they are unique.
// - We may operate as if all descendants are consistent, since `propagate_recursive`
// will panic before continuing to propagate if it encounters an entity with
// inconsistent parentage.
// - Since each root entity is unique and the hierarchy is consistent and forest-like,
// other root entities' `propagate_recursive` calls will not conflict with this one.
// - Since this is the only place where `transform_query` gets used, there will be no
// conflicting fetches elsewhere.
unsafe {
Self::propagate_recursive(
&parent_transform,
&transform_query,
&parent_query,
low_precision_root,
changed,
);
}
};
roots.par_iter().for_each(|(low_precision_root, parent)| {
if let Ok(parent_transform) = root_parents.get(parent.parent()) {
update_transforms(low_precision_root, parent_transform);
}
});
if let Some(stats) = stats.as_mut() {
stats.low_precision_propagation += start.elapsed();
}
}
/// Recursively propagates the transforms for `entity` and all of its descendants.
///
/// # Panics
///
/// If `entity`'s descendants have a malformed hierarchy, this function will panic occur before
/// propagating the transforms of any malformed entities and their descendants.
///
/// # Safety
///
/// - While this function is running, `transform_query` must not have any fetches for `entity`,
/// nor any of its descendants.
/// - The caller must ensure that the hierarchy leading to `entity` is well-formed and must
/// remain as a tree or a forest. Each entity must have at most one parent.
#[expect(
unsafe_code,
reason = "This function uses `Query::get_unchecked()`, which can result in multiple mutable references if the preconditions are not met."
)]
unsafe fn propagate_recursive(
parent: &GlobalTransform,
transform_query: &Query<
(Ref<Transform>, &mut GlobalTransform, Option<&Children>),
(
With<ChildOf>,
Without<CellCoord>, // ***ADDED*** Only recurse low-precision entities
Without<Grid>, // ***ADDED*** Only recurse low-precision entities
),
>,
parent_query: &Query<
(Entity, Ref<ChildOf>),
(
With<Transform>,
With<GlobalTransform>,
Without<CellCoord>,
Without<Grid>,
),
>,
entity: Entity,
mut changed: bool,
) {
let (global_matrix, children) = {
let Ok((transform, mut global_transform, children)) =
// SAFETY: This call cannot create aliased mutable references.
// - The top level iteration parallelizes on the roots of the hierarchy.
// - The caller ensures that each child has one and only one unique parent
// throughout the entire hierarchy.
(unsafe { transform_query.get_unchecked(entity) }) else {
return;
};
changed |= transform.is_changed() || global_transform.is_added();
if changed {
*global_transform = parent.mul_transform(*transform);
}
(global_transform, children)
};
let Some(children) = children else { return };
for (child, child_of) in parent_query.iter_many(children) {
assert_eq!(
child_of.parent(), entity,
"Malformed hierarchy. This probably means that your hierarchy has been improperly maintained, or contains a cycle"
);
// SAFETY: The caller guarantees that `transform_query` will not be fetched for any
// descendants of `entity`, so it is safe to call `propagate_recursive` for each child.
//
// The above assertion ensures that each child has one and only one unique parent
// throughout the entire hierarchy.
unsafe {
Self::propagate_recursive(
global_matrix.as_ref(),
transform_query,
parent_query,
child,
changed || child_of.is_changed(),
);
}
}
}
}
#[cfg(test)]
mod tests {
use crate::plugin::BigSpaceMinimalPlugins;
use crate::prelude::*;
use bevy::prelude::*;
#[test]
fn low_precision_in_big_space() {
#[derive(Component)]
struct Test;
let mut app = App::new();
app.add_plugins(BigSpaceMinimalPlugins)
.add_systems(Startup, |mut commands: Commands| {
commands.spawn_big_space_default(|root| {
root.spawn_spatial(FloatingOrigin);
root.spawn_spatial((
Transform::from_xyz(3.0, 3.0, 3.0),
CellCoord::new(1, 1, 1), // Default cell size is 2000
))
.with_children(|spatial| {
spatial.spawn((
Transform::from_xyz(1.0, 2.0, 3.0),
Visibility::default(),
Test,
));
});
});
});
app.update();
let mut q = app
.world_mut()
.query_filtered::<&GlobalTransform, With<Test>>();
let actual_transform = *q.single(app.world()).unwrap();
assert_eq!(
actual_transform,
GlobalTransform::from_xyz(2004.0, 2005.0, 2006.0)
);
}
}