use std::io;
pub const SPAN_MAX_HEIGHT: u16 = 8191;
#[must_use]
pub fn store13(v: u16) -> u16 {
v & SPAN_MAX_HEIGHT
}
const MAX_COLUMNS: usize = 1 << 24;
pub const NO_HIDE_PART: u16 = u16::MAX;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Span {
pub smin: u16,
pub smax: u16,
pub area: u8,
pub sub_area: u16,
pub hide_part: u16,
}
impl Span {
#[must_use]
pub fn new(smin: u16, smax: u16, area: u8) -> Self {
Self {
smin,
smax,
area,
sub_area: 0,
hide_part: NO_HIDE_PART,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct SpanPiece {
pub x: i32,
pub z: i32,
pub smin: u16,
pub smax: u16,
pub area: u8,
pub flag_merge_threshold: i32,
pub hide_part: Option<u16>,
}
impl SpanPiece {
#[must_use]
pub fn new(x: i32, z: i32, smin: u16, smax: u16, area: u8, flag_merge_threshold: i32) -> Self {
Self {
x,
z,
smin,
smax,
area,
flag_merge_threshold,
hide_part: None,
}
}
#[must_use]
pub fn in_hide_part(mut self, part: u16) -> Self {
self.hide_part = Some(part);
self
}
}
#[derive(Clone, Debug)]
pub struct Heightfield {
pub width: i32,
pub height: i32,
pub bmin: [f32; 3],
pub bmax: [f32; 3],
pub cs: f32,
pub ch: f32,
columns: Vec<Vec<Span>>,
span_count: usize,
span_limit: usize,
refused: usize,
}
impl Heightfield {
pub fn new(
width: i32,
height: i32,
bmin: [f32; 3],
bmax: [f32; 3],
cs: f32,
ch: f32,
) -> io::Result<Self> {
let w =
usize::try_from(width).map_err(|_| error!("heightfield width {width} is negative"))?;
let h = usize::try_from(height)
.map_err(|_| error!("heightfield height {height} is negative"))?;
let n = w
.checked_mul(h)
.filter(|n| *n <= MAX_COLUMNS)
.ok_or_else(|| error!("heightfield {width}x{height} is too large"))?;
if !(cs.is_finite() && cs > 0.0 && ch.is_finite() && ch > 0.0) {
return Err(error!(
"heightfield cell size {cs} / height {ch} is invalid"
));
}
Ok(Self {
width,
height,
bmin,
bmax,
cs,
ch,
columns: vec![Vec::new(); n],
span_count: 0,
span_limit: usize::MAX,
refused: 0,
})
}
pub fn set_span_limit(&mut self, limit: usize) {
self.span_limit = limit;
}
#[must_use]
pub fn span_count(&self) -> usize {
self.span_count
}
pub fn check_span_budget(&self) -> io::Result<()> {
if self.refused == 0 {
return Ok(());
}
Err(error!(
"too many spans ({}, limit {})",
self.span_count.saturating_add(self.refused),
self.span_limit
))
}
fn index(&self, x: i32, z: i32) -> Option<usize> {
if x < 0 || z < 0 || x >= self.width || z >= self.height {
return None;
}
let w = usize::try_from(self.width).ok()?;
usize::try_from(x)
.ok()?
.checked_add(usize::try_from(z).ok()?.checked_mul(w)?)
}
#[must_use]
pub fn column(&self, x: i32, z: i32) -> &[Span] {
self.index(x, z)
.and_then(|i| self.columns.get(i))
.map_or(&[], Vec::as_slice)
}
#[must_use]
pub fn columns(&self) -> &[Vec<Span>] {
&self.columns
}
pub fn columns_mut(&mut self) -> &mut [Vec<Span>] {
&mut self.columns
}
pub(crate) fn column_mut(&mut self, x: i32, z: i32) -> Option<&mut Vec<Span>> {
let i = self.index(x, z)?;
self.columns.get_mut(i)
}
pub fn add_span(
&mut self,
x: i32,
z: i32,
smin: u16,
smax: u16,
area: u8,
flag_merge_threshold: i32,
) {
self.add_piece(&SpanPiece::new(
x,
z,
smin,
smax,
area,
flag_merge_threshold,
));
}
pub fn add_piece(&mut self, piece: &SpanPiece) {
let SpanPiece {
x,
z,
smin,
smax,
area,
flag_merge_threshold,
hide_part,
} = *piece;
if self.span_count >= self.span_limit {
if self.index(x, z).is_some() {
self.refused = self.refused.saturating_add(1);
}
return;
}
let Some(i) = self.index(x, z) else {
return;
};
let Some(column) = self.columns.get_mut(i) else {
return;
};
let before = column.len();
let mut new = Span::new(store13(smin), store13(smax), area);
new.hide_part = hide_part.unwrap_or(NO_HIDE_PART);
let mut older = NO_HIDE_PART;
let mut i = 0;
while let Some(&cur) = column.get(i) {
if cur.smin > new.smax {
break;
}
if cur.smax < new.smin {
i += 1;
continue;
}
new.smin = new.smin.min(cur.smin);
new.smax = new.smax.max(cur.smax);
if (i32::from(new.smax) - i32::from(cur.smax)).abs() <= flag_merge_threshold {
new.area = new.area.max(cur.area);
}
if older == NO_HIDE_PART {
older = cur.hide_part;
}
column.remove(i);
}
if older != NO_HIDE_PART && hide_part.is_some() {
new.hide_part = older;
}
column.insert(i, new);
let after = column.len();
self.span_count = self.span_count.saturating_sub(before).saturating_add(after);
}
}