use nalgebra_glm::{IVec3, Vec3};
use super::brick_map::{BRICK_SIZE, BrickAllocator, BrickPointerGrid, EMPTY_BRICK, GRID_SIZE};
use super::bvh::SdfEditBvh;
use super::primitives::Aabb;
use super::resources::TerrainConfig;
pub const DEFAULT_LEVEL_COUNT: usize = 10;
pub const BASE_VOXEL_SIZE: f32 = 0.125;
const MAX_TERRAIN_BRICK_LEVELS: usize = 4;
pub struct SdfClipmap {
pub levels: Vec<BrickPointerGrid>,
pub center: Vec3,
pub allocator: BrickAllocator,
}
impl SdfClipmap {
pub fn new(level_count: usize, base_voxel_size: f32, max_bricks: u32) -> Self {
let mut levels = Vec::with_capacity(level_count);
for level_index in 0..level_count {
let voxel_size = base_voxel_size * (1 << level_index) as f32;
levels.push(BrickPointerGrid::new(voxel_size));
}
Self {
levels,
center: Vec3::zeros(),
allocator: BrickAllocator::new(max_bricks),
}
}
pub fn update_center(&mut self, new_center: Vec3) {
self.update_center_with_bvh(new_center, None, None, &TerrainConfig::default());
}
pub fn update_center_with_bvh(
&mut self,
new_center: Vec3,
bvh: Option<&SdfEditBvh>,
edits_aabb: Option<&Aabb>,
terrain: &TerrainConfig,
) {
let grid_size = GRID_SIZE as i32;
for (level_index, level) in self.levels.iter_mut().enumerate() {
let voxel_size = BASE_VOXEL_SIZE * (1 << level_index) as f32;
let brick_world_size = voxel_size * BRICK_SIZE as f32;
let new_origin_brick = IVec3::new(
((new_center.x / brick_world_size).floor() as i32) - (grid_size / 2),
((new_center.y / brick_world_size).floor() as i32) - (grid_size / 2),
((new_center.z / brick_world_size).floor() as i32) - (grid_size / 2),
);
let old_origin = level.origin_brick;
let delta = new_origin_brick - old_origin;
let is_first_population =
level.allocated_coords.is_empty() && level.dirty_bricks.is_empty();
if delta.x != 0 || delta.y != 0 || delta.z != 0 || is_first_population {
let freed_bricks = collect_scrolled_out_bricks(level, old_origin, new_origin_brick);
let had_freed_bricks = !freed_bricks.is_empty();
for brick_coord in freed_bricks {
let pointer = level.get_pointer(brick_coord);
if pointer != EMPTY_BRICK {
self.allocator.deallocate(pointer as u32);
level.set_pointer(brick_coord, EMPTY_BRICK);
}
}
if had_freed_bricks {
level.pointer_dirty = true;
}
let relevant_aabb = compute_relevant_aabb(edits_aabb, terrain, voxel_size);
let mut scratch = Vec::new();
let has_bvh = bvh.filter(|b| !b.is_empty()).is_some();
if is_first_population && has_bvh {
let (iter_min, iter_max) = clamp_iteration_range_to_aabb(
new_origin_brick,
IVec3::new(
new_origin_brick.x + grid_size,
new_origin_brick.y + grid_size,
new_origin_brick.z + grid_size,
),
&relevant_aabb,
brick_world_size,
);
for brick_z in iter_min.z..iter_max.z {
for brick_y in iter_min.y..iter_max.y {
for brick_x in iter_min.x..iter_max.x {
let brick_coord = IVec3::new(brick_x, brick_y, brick_z);
let brick_origin = Vec3::new(
brick_coord.x as f32 * brick_world_size,
brick_coord.y as f32 * brick_world_size,
brick_coord.z as f32 * brick_world_size,
);
let brick_half_size = brick_world_size * 0.5;
let brick_center = brick_origin
+ Vec3::new(brick_half_size, brick_half_size, brick_half_size);
let brick_bounds = Aabb::from_center_half_extents(
brick_center,
Vec3::new(brick_half_size, brick_half_size, brick_half_size),
);
if let Some(bvh) = bvh.filter(|b| !b.is_empty()) {
scratch.clear();
bvh.query_bounds(
&brick_bounds.expand(voxel_size * 4.0),
&mut scratch,
);
if !scratch.is_empty() {
level.mark_dirty(brick_coord);
}
}
}
}
}
} else if has_bvh {
let scroll_ranges =
collect_scrolled_in_brick_ranges(old_origin, new_origin_brick);
for (axis, &(primary_start, primary_end)) in scroll_ranges.iter().enumerate() {
if primary_start >= primary_end {
continue;
}
let (other1_start, other1_end, other2_start, other2_end) = match axis {
0 => (
new_origin_brick.y,
new_origin_brick.y + grid_size,
new_origin_brick.z,
new_origin_brick.z + grid_size,
),
1 => (
new_origin_brick.x,
new_origin_brick.x + grid_size,
new_origin_brick.z,
new_origin_brick.z + grid_size,
),
_ => (
new_origin_brick.x,
new_origin_brick.x + grid_size,
new_origin_brick.y,
new_origin_brick.y + grid_size,
),
};
let (
clamped_primary_start,
clamped_primary_end,
clamped_other1_start,
clamped_other1_end,
clamped_other2_start,
clamped_other2_end,
) = clamp_slab_ranges_to_aabb(
axis,
primary_start,
primary_end,
other1_start,
other1_end,
other2_start,
other2_end,
&relevant_aabb,
brick_world_size,
);
for primary in clamped_primary_start..clamped_primary_end {
for other1 in clamped_other1_start..clamped_other1_end {
for other2 in clamped_other2_start..clamped_other2_end {
let brick_coord = match axis {
0 => IVec3::new(primary, other1, other2),
1 => IVec3::new(other1, primary, other2),
_ => IVec3::new(other1, other2, primary),
};
let brick_origin = Vec3::new(
brick_coord.x as f32 * brick_world_size,
brick_coord.y as f32 * brick_world_size,
brick_coord.z as f32 * brick_world_size,
);
let brick_half_size = brick_world_size * 0.5;
let brick_center = brick_origin
+ Vec3::new(
brick_half_size,
brick_half_size,
brick_half_size,
);
let brick_bounds = Aabb::from_center_half_extents(
brick_center,
Vec3::new(
brick_half_size,
brick_half_size,
brick_half_size,
),
);
if let Some(bvh) = bvh.filter(|b| !b.is_empty()) {
scratch.clear();
bvh.query_bounds(
&brick_bounds.expand(voxel_size * 4.0),
&mut scratch,
);
if !scratch.is_empty() {
level.mark_dirty(brick_coord);
}
}
}
}
}
}
}
if terrain.enabled && level_index < MAX_TERRAIN_BRICK_LEVELS {
let full_range = BrickRange {
x_start: new_origin_brick.x,
x_end: new_origin_brick.x + grid_size,
z_start: new_origin_brick.z,
z_end: new_origin_brick.z + grid_size,
y_start: new_origin_brick.y,
y_end: new_origin_brick.y + grid_size,
};
if is_first_population {
mark_terrain_surface_bricks(level, terrain, brick_world_size, &full_range);
} else {
let terrain_ranges =
collect_scrolled_in_brick_ranges(old_origin, new_origin_brick);
let (x_start, x_end) = terrain_ranges[0];
if x_start < x_end {
mark_terrain_surface_bricks(
level,
terrain,
brick_world_size,
&BrickRange {
x_start,
x_end,
..full_range
},
);
}
let (y_start, y_end) = terrain_ranges[1];
if y_start < y_end {
let terrain_min_height =
terrain.base_height - terrain.max_surface_extent();
let terrain_max_height =
terrain.base_height + terrain.max_surface_extent();
let slab_min_y = y_start as f32 * brick_world_size;
let slab_max_y = y_end as f32 * brick_world_size;
if terrain_max_height >= slab_min_y && terrain_min_height <= slab_max_y
{
mark_terrain_surface_bricks(
level,
terrain,
brick_world_size,
&BrickRange {
y_start,
y_end,
..full_range
},
);
}
}
let (z_start, z_end) = terrain_ranges[2];
if z_start < z_end {
mark_terrain_surface_bricks(
level,
terrain,
brick_world_size,
&BrickRange {
z_start,
z_end,
..full_range
},
);
}
}
}
level.origin_brick = new_origin_brick;
}
}
self.center = new_center;
}
pub fn mark_dirty_in_bounds(&mut self, bounds: &Aabb) {
let grid_size = super::brick_map::GRID_SIZE as i32;
for level in &mut self.levels {
let expanded = bounds.expand(level.voxel_size * 4.0);
let brick_min = level.world_to_brick_coord(expanded.min);
let brick_max = level.world_to_brick_coord(expanded.max);
let clamped_min = IVec3::new(
brick_min.x.max(level.origin_brick.x),
brick_min.y.max(level.origin_brick.y),
brick_min.z.max(level.origin_brick.z),
);
let clamped_max = IVec3::new(
brick_max.x.min(level.origin_brick.x + grid_size - 1),
brick_max.y.min(level.origin_brick.y + grid_size - 1),
brick_max.z.min(level.origin_brick.z + grid_size - 1),
);
for z in clamped_min.z..=clamped_max.z {
for y in clamped_min.y..=clamped_max.y {
for x in clamped_min.x..=clamped_max.x {
let coord = IVec3::new(x, y, z);
level.mark_dirty(coord);
}
}
}
}
}
pub fn level_world_extent(&self, level_index: usize) -> f32 {
if level_index < self.levels.len() {
self.levels[level_index].world_extent()
} else {
0.0
}
}
pub fn select_level_for_distance(&self, distance_from_center: f32) -> usize {
for (level_index, level) in self.levels.iter().enumerate() {
let half_extent = level.world_extent() * 0.5;
if distance_from_center < half_extent * 0.85 {
return level_index;
}
}
self.levels.len().saturating_sub(1)
}
pub fn level_count(&self) -> usize {
self.levels.len()
}
pub fn voxel_sizes(&self) -> Vec<f32> {
self.levels.iter().map(|level| level.voxel_size).collect()
}
pub fn mark_all_dirty(&mut self) {
let grid_size = GRID_SIZE as i32;
for level in &mut self.levels {
for z in 0..grid_size {
for y in 0..grid_size {
for x in 0..grid_size {
let coord = IVec3::new(
level.origin_brick.x + x,
level.origin_brick.y + y,
level.origin_brick.z + z,
);
level.mark_dirty(coord);
}
}
}
}
}
pub fn force_reinitialize(&mut self) {
for level in &mut self.levels {
let coords: Vec<_> = level.allocated_coords.iter().copied().collect();
let had_bricks = !coords.is_empty();
for (x, y, z) in coords {
let coord = IVec3::new(x, y, z);
let pointer = level.get_pointer(coord);
if pointer != EMPTY_BRICK {
self.allocator.deallocate(pointer as u32);
level.set_pointer(coord, EMPTY_BRICK);
}
}
level.dirty_bricks.clear();
if had_bricks {
level.pointer_dirty = true;
}
}
}
pub fn mark_all_levels_pointer_dirty(&mut self) {
for level in &mut self.levels {
level.pointer_dirty = true;
}
}
}
fn compute_relevant_aabb(
edits_aabb: Option<&Aabb>,
terrain: &TerrainConfig,
voxel_size: f32,
) -> Option<Aabb> {
let margin = voxel_size * 4.0;
match (edits_aabb, terrain.enabled) {
(Some(aabb), _) => Some(aabb.expand(margin)),
(None, true) => None,
(None, false) => Some(Aabb {
min: Vec3::zeros(),
max: Vec3::new(-1.0, -1.0, -1.0),
}),
}
}
fn clamp_iteration_range_to_aabb(
grid_min: IVec3,
grid_max: IVec3,
relevant_aabb: &Option<Aabb>,
brick_world_size: f32,
) -> (IVec3, IVec3) {
match relevant_aabb {
Some(aabb) => {
if aabb.min.x > aabb.max.x {
return (grid_min, grid_min);
}
let aabb_brick_min = IVec3::new(
(aabb.min.x / brick_world_size).floor() as i32,
(aabb.min.y / brick_world_size).floor() as i32,
(aabb.min.z / brick_world_size).floor() as i32,
);
let aabb_brick_max = IVec3::new(
(aabb.max.x / brick_world_size).ceil() as i32 + 1,
(aabb.max.y / brick_world_size).ceil() as i32 + 1,
(aabb.max.z / brick_world_size).ceil() as i32 + 1,
);
let clamped_min = IVec3::new(
grid_min.x.max(aabb_brick_min.x),
grid_min.y.max(aabb_brick_min.y),
grid_min.z.max(aabb_brick_min.z),
);
let clamped_max = IVec3::new(
grid_max.x.min(aabb_brick_max.x),
grid_max.y.min(aabb_brick_max.y),
grid_max.z.min(aabb_brick_max.z),
);
(clamped_min, clamped_max)
}
None => (grid_min, grid_max),
}
}
#[allow(clippy::too_many_arguments)]
fn clamp_slab_ranges_to_aabb(
axis: usize,
primary_start: i32,
primary_end: i32,
other1_start: i32,
other1_end: i32,
other2_start: i32,
other2_end: i32,
relevant_aabb: &Option<Aabb>,
brick_world_size: f32,
) -> (i32, i32, i32, i32, i32, i32) {
match relevant_aabb {
Some(aabb) => {
if aabb.min.x > aabb.max.x {
return (
primary_start,
primary_start,
other1_start,
other1_start,
other2_start,
other2_start,
);
}
let aabb_brick_min = IVec3::new(
(aabb.min.x / brick_world_size).floor() as i32,
(aabb.min.y / brick_world_size).floor() as i32,
(aabb.min.z / brick_world_size).floor() as i32,
);
let aabb_brick_max = IVec3::new(
(aabb.max.x / brick_world_size).ceil() as i32 + 1,
(aabb.max.y / brick_world_size).ceil() as i32 + 1,
(aabb.max.z / brick_world_size).ceil() as i32 + 1,
);
let (primary_axis, other1_axis, other2_axis) = match axis {
0 => (0, 1, 2),
1 => (1, 0, 2),
_ => (2, 0, 1),
};
(
primary_start.max(aabb_brick_min[primary_axis]),
primary_end.min(aabb_brick_max[primary_axis]),
other1_start.max(aabb_brick_min[other1_axis]),
other1_end.min(aabb_brick_max[other1_axis]),
other2_start.max(aabb_brick_min[other2_axis]),
other2_end.min(aabb_brick_max[other2_axis]),
)
}
None => (
primary_start,
primary_end,
other1_start,
other1_end,
other2_start,
other2_end,
),
}
}
fn collect_scrolled_out_bricks(
level: &BrickPointerGrid,
_old_origin: IVec3,
new_origin: IVec3,
) -> Vec<IVec3> {
let grid_size = GRID_SIZE as i32;
level
.allocated_coords
.iter()
.filter_map(|&(x, y, z)| {
let relative_x = x - new_origin.x;
let relative_y = y - new_origin.y;
let relative_z = z - new_origin.z;
if relative_x < 0
|| relative_x >= grid_size
|| relative_y < 0
|| relative_y >= grid_size
|| relative_z < 0
|| relative_z >= grid_size
{
Some(IVec3::new(x, y, z))
} else {
None
}
})
.collect()
}
fn collect_scrolled_in_brick_ranges(old_origin: IVec3, new_origin: IVec3) -> [(i32, i32); 3] {
let grid_size = GRID_SIZE as i32;
let mut ranges = [(0i32, 0i32); 3];
for axis in 0..3 {
let delta = new_origin[axis] - old_origin[axis];
if delta == 0 {
ranges[axis] = (0, 0);
continue;
}
let (range_start, range_end) = if delta > 0 {
(
new_origin[axis] + grid_size - delta.min(grid_size),
new_origin[axis] + grid_size,
)
} else {
(new_origin[axis], new_origin[axis] - delta.max(-grid_size))
};
ranges[axis] = (range_start, range_end);
}
ranges
}
struct BrickRange {
x_start: i32,
x_end: i32,
z_start: i32,
z_end: i32,
y_start: i32,
y_end: i32,
}
fn mark_terrain_surface_bricks(
level: &mut BrickPointerGrid,
terrain: &TerrainConfig,
brick_world_size: f32,
range: &BrickRange,
) {
for brick_z in range.z_start..range.z_end {
for brick_x in range.x_start..range.x_end {
let x0 = brick_x as f32 * brick_world_size;
let x1 = (brick_x + 1) as f32 * brick_world_size;
let z0 = brick_z as f32 * brick_world_size;
let z1 = (brick_z + 1) as f32 * brick_world_size;
let h00 = terrain.height_at(x0, z0);
let h10 = terrain.height_at(x1, z0);
let h01 = terrain.height_at(x0, z1);
let h11 = terrain.height_at(x1, z1);
let min_height = h00.min(h10).min(h01).min(h11);
let max_height = h00.max(h10).max(h01).max(h11);
let min_brick_y = (min_height / brick_world_size).floor() as i32 - 1;
let max_brick_y = (max_height / brick_world_size).floor() as i32 + 1;
for brick_y in min_brick_y..=max_brick_y {
if brick_y >= range.y_start && brick_y < range.y_end {
let brick_coord = IVec3::new(brick_x, brick_y, brick_z);
if level.get_pointer(brick_coord) == EMPTY_BRICK {
level.mark_dirty(brick_coord);
}
}
}
}
}
}
pub struct LevelBlendInfo {
pub level: usize,
pub blend_factor: f32,
}
impl SdfClipmap {
pub fn get_blend_info(&self, world_pos: Vec3) -> LevelBlendInfo {
let diff = world_pos - self.center;
let distance_from_center = diff.x.abs().max(diff.y.abs()).max(diff.z.abs());
let level = self.select_level_for_distance(distance_from_center);
let level_extent = self.level_world_extent(level);
let half_extent = level_extent * 0.5;
let transition_width = level_extent * 0.1;
let edge_distance = half_extent - distance_from_center;
let blend_factor = (edge_distance / transition_width).clamp(0.0, 1.0);
LevelBlendInfo {
level,
blend_factor,
}
}
}