use super::*;
#[derive(Clone, Copy, Debug, Default)]
#[non_exhaustive]
pub struct FlatDagCluster {
pub first_index: u32,
pub index_count: u32,
pub group: u32,
pub refined: i32,
pub center: [f32; 3],
pub radius: f32,
}
#[derive(Clone, Copy, Debug, Default)]
#[non_exhaustive]
pub struct FlatDagGroup {
pub center: [f32; 3],
pub radius: f32,
pub error: f32,
pub depth: i32,
pub first_cluster: u32,
pub cluster_count: u32,
}
pub struct DagBuffers<'a> {
pub vertex_source: &'a mut [u32],
pub vertex_positions: &'a mut [[f32; 3]],
pub indices: &'a mut [u32],
pub clusters: &'a mut [FlatDagCluster],
pub groups: &'a mut [FlatDagGroup],
pub nodes: &'a mut [Node],
}
#[derive(Clone, Copy, Debug, Default)]
#[non_exhaustive]
pub struct DagCounts {
pub vertices: usize,
pub indices: usize,
pub clusters: usize,
pub groups: usize,
pub nodes: usize,
pub level_count: u32,
pub bvh_depth: u32,
}
fn hash(key: [u32; 4]) -> usize {
let mut h = 0u64;
for word in key {
h = (h ^ u64::from(word)).wrapping_mul(0x9e3779b97f4a7c15);
h ^= h >> 32;
}
h as usize
}
fn key(dst: &DagBuffers<'_>, i: usize) -> [u32; 4] {
let p = dst.vertex_positions[i];
[
dst.vertex_source[i],
p[0].to_bits(),
p[1].to_bits(),
p[2].to_bits(),
]
}
fn slot(
table: &[u32],
k: [u32; 4],
dst: &DagBuffers<'_>,
ctx: &mut Context<'_>,
) -> Result<usize, Error> {
let mut at = hash(k) & (table.len() - 1);
loop {
ctx.tick(1)?;
if table[at] == u32::MAX || key(dst, table[at] as usize) == k {
return Ok(at);
}
at = (at + 1) & (table.len() - 1);
}
}
fn depth(nodes: &[Node], i: usize, d: u32, ctx: &mut Context<'_>) -> Result<u32, Error> {
ctx.tick(1)?;
if d > 32 {
return Err(Error::LimitExceeded);
}
let n = nodes[i];
let mut result = d;
if n.group < 0 {
for c in 0..n.child_count {
result = result.max(depth(nodes, (n.child_offset + c) as usize, d + 1, ctx)?);
}
}
Ok(result)
}
pub fn build_dag_into(
config: Config,
mesh: Mesh<'_>,
node_width: usize,
destination: DagBuffers<'_>,
workspace: &mut Workspace,
) -> Result<DagCounts, Error> {
let mut ctx = Context::new(workspace)?;
if node_width < 2 {
return Err(Error::InvalidParameter);
}
let mut counts = DagCounts::default();
let mut table = Vec::<u32>::new();
let mut groups = Vec::<Group>::new();
let dst = destination;
build_in_context(
config,
mesh,
&mut |g, clusters, positions, ctx| {
if g.depth < 0 || g.depth >= 64 {
return Err(Error::LimitExceeded);
}
if counts.groups >= i32::MAX as usize {
return Err(Error::SizeOverflow);
}
if counts.groups >= dst.groups.len() {
return Err(Error::BufferTooSmall);
}
let end = counts
.clusters
.checked_add(clusters.len())
.ok_or(Error::SizeOverflow)?;
if end > u32::MAX as usize {
return Err(Error::SizeOverflow);
}
if end > dst.clusters.len() {
return Err(Error::BufferTooSmall);
}
let gid = counts.groups as u32;
dst.groups[counts.groups] = FlatDagGroup {
center: g.simplified.center,
radius: g.simplified.radius,
error: g.simplified.error,
depth: g.depth,
first_cluster: counts.clusters as u32,
cluster_count: clusters.len() as u32,
};
ctx.grow(&mut groups, 1)?;
groups.push(g);
counts.groups += 1;
counts.level_count = counts.level_count.max(g.depth as u32 + 1);
for cl in &clusters {
let end = counts
.indices
.checked_add(cl.indices.len())
.ok_or(Error::SizeOverflow)?;
if end > u32::MAX as usize {
return Err(Error::SizeOverflow);
}
if end > dst.indices.len() {
return Err(Error::BufferTooSmall);
}
dst.clusters[counts.clusters] = FlatDagCluster {
first_index: counts.indices as u32,
index_count: cl.indices.len() as u32,
group: gid,
refined: cl.refined,
center: cl.bounds.center,
radius: cl.bounds.radius,
};
for &src in &cl.indices {
let p = positions[src as usize];
let k = [src, p[0].to_bits(), p[1].to_bits(), p[2].to_bits()];
if counts.vertices >= table.len() / 2 {
let size = table
.len()
.max(8)
.checked_mul(2)
.ok_or(Error::SizeOverflow)?;
let mut new = ctx.filled(size, u32::MAX)?;
for i in 0..counts.vertices {
let at = slot(&new, key(&dst, i), &dst, ctx)?;
new[at] = i as u32;
}
ctx.free(core::mem::replace(&mut table, new))?;
}
let at = slot(&table, k, &dst, ctx)?;
let id = if table[at] != u32::MAX {
table[at]
} else {
if counts.vertices >= u32::MAX as usize {
return Err(Error::SizeOverflow);
}
if counts.vertices >= dst.vertex_source.len()
|| counts.vertices >= dst.vertex_positions.len()
{
return Err(Error::BufferTooSmall);
}
let id = counts.vertices as u32;
dst.vertex_source[counts.vertices] = src;
dst.vertex_positions[counts.vertices] = p;
counts.vertices += 1;
table[at] = id;
id
};
dst.indices[counts.indices] = id;
counts.indices += 1;
}
counts.clusters += 1;
ctx.release(&cl.indices)?;
}
ctx.free(clusters)?;
Ok(gid as i32)
},
&mut ctx,
)?;
ctx.free(table)?;
let nodes = hierarchy_in_context(&groups, node_width, counts.level_count as usize, &mut ctx)?;
if nodes.len() > dst.nodes.len() {
return Err(Error::BufferTooSmall);
}
for i in 0..counts.level_count as usize {
counts.bvh_depth = counts.bvh_depth.max(depth(&nodes, i, 1, &mut ctx)?);
}
counts.nodes = nodes.len();
ctx.tick(nodes.len())?;
dst.nodes[..nodes.len()].copy_from_slice(&nodes);
Ok(counts)
}