mod chains;
mod mirror;
mod sets;
pub(crate) use sets::{SetKey, SetLook};
use super::SceneError;
use super::deformation::InstanceDeformation;
use super::geometry::GeometryRange;
use super::materials::Material;
use super::models::{Model, Models};
use super::ranges::Ranges;
use crate::content::identity::{Identity, MaterialId, ModelId};
use crate::lod::MeshLod;
use crate::shading::culling::{ChainLevel, CullListsHeader, DrawCandidate};
use crate::shading::vertex::DrawInstance;
use chains::Chains;
use glam::Vec3;
use mirror::Mirror;
use sets::Sets;
use std::collections::BTreeSet;
use std::ops::Range;
#[derive(Clone, Copy, Default)]
struct Slot {
mesh: u32,
need: u32,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct CandidateMesh {
pub material: MaterialId,
pub look: SetLook,
pub blended: bool,
pub need: u32,
pub bounds: [Vec3; 2],
pub word: u32,
pub chain: u32,
pub positions: (u32, u32),
}
pub(crate) type CandidateKey = (SetKey, SetLook, u32);
fn keyed(
meshes: &[CandidateMesh],
mirrored: bool,
deforms: bool,
) -> impl Iterator<Item = (usize, CandidateKey)> + '_ {
meshes
.iter()
.enumerate()
.filter(|(_, mesh)| !mesh.blended && mesh.need > 0)
.map(move |(index, mesh)| {
let key = SetKey {
material: mesh.material,
mirrored,
deforms,
positions: mesh.positions.0,
};
(index, (key, mesh.look, mesh.need))
})
}
fn account(
(sets, placed): (&mut Sets, &mut Ranges),
(held, slots): (&[(u32, u32)], Range<u32>),
keys: &[CandidateKey],
) -> Option<(Range<u32>, Vec<u32>)> {
for &(set, need) in held {
sets.remove(set, need);
}
placed.free(slots);
let range = placed.allocate(keys.len() as u32)?;
let joined = keys
.iter()
.map(|&(key, look, need)| sets.add(key, look, need))
.collect();
Some((range, joined))
}
pub(crate) struct Candidates {
records: Mirror<DrawCandidate>,
slots: Vec<Slot>,
placed: Ranges,
by_instance: Vec<Range<u32>>,
blended: BTreeSet<u32>,
pub(crate) sets: Sets,
chains: Chains,
most_slots: u32,
most_regions: u32,
#[cfg(feature = "diagnostics")]
models: std::sync::Arc<Vec<Option<ModelId>>>,
}
impl Candidates {
pub fn new(limits: &wgpu::Limits) -> Self {
let binding = limits
.max_storage_buffer_binding_size
.min(limits.max_buffer_size);
let most = |stride: usize, head: usize| {
u32::try_from(binding.saturating_sub(head as u64) / stride as u64).unwrap_or(u32::MAX)
};
let candidate = std::mem::size_of::<DrawCandidate>();
let entry = 2 * std::mem::size_of::<u32>();
Self {
records: Mirror::new("draw candidates"),
slots: Vec::new(),
placed: Ranges::new(0),
by_instance: Vec::new(),
blended: BTreeSet::new(),
sets: Sets::new(),
chains: Chains::new(),
most_slots: most(candidate, 0).min(most(entry, std::mem::size_of::<CullListsHeader>())),
most_regions: most(2 * std::mem::size_of::<DrawInstance>(), 0),
#[cfg(feature = "diagnostics")]
models: Default::default(),
}
}
fn held(&self, index: usize) -> (Vec<(u32, u32)>, Range<u32>) {
let range = self.by_instance.get(index).cloned().unwrap_or(0..0);
let held = range
.clone()
.map(|slot| {
let set = self.records.get(slot).draw_set;
(set, self.slots[slot as usize].need)
})
.collect();
(held, range)
}
fn fits(&self, sets: &Sets, placed: &Ranges) -> bool {
placed.end() <= self.most_slots && sets.fit(self.most_regions)
}
pub fn fit(&self, instances: impl IntoIterator<Item = (usize, Vec<CandidateKey>)>) -> bool {
let (mut sets, mut placed) = (self.sets.clone(), self.placed.clone());
for (index, keys) in instances {
let (held, slots) = self.held(index);
if account((&mut sets, &mut placed), (&held, slots), &keys).is_none()
|| !self.fits(&sets, &placed)
{
return false;
}
}
true
}
pub fn keys(meshes: &[CandidateMesh], mirrored: bool, deforms: bool) -> Vec<CandidateKey> {
keyed(meshes, mirrored, deforms)
.map(|(_, key)| key)
.collect()
}
pub fn place(
&mut self,
index: usize,
(model, meshes): (ModelId, &[CandidateMesh]),
mirrored: bool,
deformed: Option<&[[Vec3; 2]]>,
) -> Result<(), SceneError> {
#[cfg(not(feature = "diagnostics"))]
let _ = model;
let placing: Vec<(usize, CandidateKey)> =
keyed(meshes, mirrored, deformed.is_some()).collect();
let keys: Vec<CandidateKey> = placing.iter().map(|&(_, key)| key).collect();
let (held, slots) = self.held(index);
let restore = (self.sets.clone(), self.placed.clone());
let placed = account(
(&mut self.sets, &mut self.placed),
(&held, slots.clone()),
&keys,
)
.filter(|_| self.fits(&self.sets, &self.placed));
let Some((range, joined)) = placed else {
(self.sets, self.placed) = restore;
return Err(SceneError::DeviceLimit);
};
for slot in slots {
self.free_slot(slot);
}
for (slot, ((mesh, (_, _, need)), set)) in
range.clone().zip(placing.into_iter().zip(joined))
{
let shape = &meshes[mesh];
let bounds = deformed.map_or(shape.bounds, |deformed| deformed[mesh]);
let record = DrawCandidate {
bounds_min: bounds[0].to_array(),
object: index as u32,
bounds_max: bounds[1].to_array(),
mesh: shape.word,
draw_set: set,
chain: shape.chain,
positions: shape.positions.1,
padding: 0,
};
self.records.set(slot, record, DrawCandidate::FREE);
if self.slots.len() <= slot as usize {
self.slots.resize(slot as usize + 1, Slot::default());
}
self.slots[slot as usize] = Slot {
mesh: mesh as u32,
need,
};
#[cfg(feature = "diagnostics")]
{
let models = std::sync::Arc::make_mut(&mut self.models);
if models.len() <= slot as usize {
models.resize(slot as usize + 1, None);
}
models[slot as usize] = Some(model);
}
}
if self.by_instance.len() <= index {
self.by_instance.resize(index + 1, 0..0);
}
self.by_instance[index] = range;
if meshes.iter().any(|mesh| mesh.blended) {
self.blended.insert(index as u32);
} else {
self.blended.remove(&(index as u32));
}
Ok(())
}
fn free_slot(&mut self, slot: u32) {
self.records
.set(slot, DrawCandidate::FREE, DrawCandidate::FREE);
self.slots[slot as usize] = Slot::default();
#[cfg(feature = "diagnostics")]
{
std::sync::Arc::make_mut(&mut self.models)[slot as usize] = None;
}
}
pub fn remove(&mut self, index: usize) {
self.blended.remove(&(index as u32));
let (held, slots) = self.held(index);
account(
(&mut self.sets, &mut self.placed),
(&held, slots.clone()),
&[],
)
.expect("an empty placement takes no slot");
for slot in slots {
self.free_slot(slot);
}
if let Some(range) = self.by_instance.get_mut(index) {
*range = 0..0;
}
}
pub fn deformed(&mut self, index: usize, deformation: &InstanceDeformation) {
let range = self.by_instance.get(index).cloned().unwrap_or(0..0);
for slot in range {
let bounds = deformation.mesh_bounds[self.slots[slot as usize].mesh as usize];
let record = DrawCandidate {
bounds_min: bounds[0].to_array(),
bounds_max: bounds[1].to_array(),
..*self.records.get(slot)
};
self.records.set(slot, record, DrawCandidate::FREE);
}
}
pub fn set_lods(&mut self, model: ModelId, mesh: usize, models: &Models) {
let owner = models.get(model).expect("a model with alternatives lives");
let base = &owner.meshes[mesh];
let bounds = base.ranges.bounds();
let levels: Vec<ChainLevel> = base
.lods
.iter()
.map(|lod| {
let alternative = models
.get(lod.model)
.expect("a level of detail's model lives");
let [min, max] = alternative.meshes[lod.mesh]
.ranges
.bounds()
.or(bounds)
.unwrap_or([Vec3::ZERO; 2]);
ChainLevel {
bounds_min: min.to_array(),
error: lod.max_error,
bounds_max: max.to_array(),
mesh: alternative.ray.mesh_word(lod.mesh),
}
})
.collect();
self.chains.set(model, mesh, &levels);
}
pub fn remove_chains(&mut self, model: ModelId) {
self.chains.remove_model(model);
}
pub fn material_changed(&mut self, id: MaterialId, look: SetLook) {
self.sets.material_changed(id, look);
}
pub fn upload(&mut self, device: &wgpu::Device, queue: &wgpu::Queue) {
self.records.upload(device, queue);
self.sets.upload(device, queue);
self.chains.upload(device, queue);
}
pub fn blended(&self) -> impl Iterator<Item = usize> + '_ {
self.blended.iter().map(|&index| index as usize)
}
pub fn end(&self) -> u32 {
self.placed.end()
}
pub fn buffers(&self) -> [&wgpu::Buffer; 3] {
[
self.records.buffer(),
self.sets.buffer(),
self.chains.buffer(),
]
}
#[cfg(feature = "diagnostics")]
pub fn models(&self) -> std::sync::Arc<Vec<Option<ModelId>>> {
self.models.clone()
}
#[cfg(any(test, feature = "diagnostics"))]
pub fn bytes(&self) -> [u64; 3] {
[self.records.bytes(), self.sets.bytes(), self.chains.bytes()]
}
}
pub(crate) fn look(material: &Material) -> SetLook {
SetLook {
group: material.values.visibility_group,
casts: material.casts_directional_shadows(),
opaque: material.values.alpha == crate::AlphaMode::Opaque,
}
}
pub(crate) fn mesh_need(base: u32, lods: &[MeshLod], models: &Models) -> u32 {
if base == 0 {
return 0;
}
lods.iter().fold(base, |need, lod| {
let alternative = &models
.get(lod.model)
.expect("a level of detail's model lives")
.meshes[lod.mesh];
need.max(alternative.ranges.section_count())
})
}
impl super::Scene {
pub(crate) fn candidate_meshes(&self, id: ModelId, model: &Model) -> Vec<CandidateMesh> {
model
.meshes
.iter()
.enumerate()
.map(|(index, mesh)| {
let material = self.drawn_material(mesh.material);
CandidateMesh {
material: mesh.material,
look: look(material),
blended: material.values.blended(),
need: mesh_need(mesh.ranges.section_count(), &mesh.lods, &self.models),
bounds: mesh.ranges.bounds().unwrap_or([Vec3::ZERO; 2]),
word: model.ray.mesh_word(index),
chain: self.candidates.chains.of(id, index),
positions: match mesh.positions {
GeometryRange { count: 0, .. } => (
GeometryRange::EMPTY.slab,
crate::shading::vertex::NO_POSITIONS,
),
range => (range.slab, range.first),
},
}
})
.collect()
}
fn instances_of(&self, models: &[ModelId]) -> Vec<Vec<crate::InstanceId>> {
let at: rustc_hash::FxHashMap<ModelId, usize> = models
.iter()
.enumerate()
.map(|(at, &model)| (model, at))
.collect();
let mut groups = vec![Vec::new(); models.len()];
for (id, instance) in self.instances.slots.iter() {
if let Some(&at) = at.get(&instance.state.model) {
groups[at].push(id);
}
}
groups
}
pub(crate) fn candidates_fit(
&self,
plan: &[(ModelId, &[CandidateMesh], Option<bool>)],
) -> bool {
let models: Vec<ModelId> = plan.iter().map(|&(model, ..)| model).collect();
let groups = self.instances_of(&models);
let instances = plan
.iter()
.zip(&groups)
.flat_map(|(&(_, meshes, deforms), ids)| {
ids.iter().map(move |&id| {
let instance = self.instances.get(id).expect("a grouped instance lives");
let mirrored = instance.state.pose.determinant() < 0.;
let deforms = deforms.unwrap_or(instance.deformation.is_some());
(id.index(), Candidates::keys(meshes, mirrored, deforms))
})
});
self.candidates.fit(instances)
}
pub(crate) fn place_candidates_of(&mut self, models: &[ModelId]) {
let groups = self.instances_of(models);
for (&model, ids) in models.iter().zip(groups) {
let meshes = self.candidate_meshes(model, self.drawn_model(model));
for id in ids {
let instance = self.instances.get(id).expect("a grouped instance lives");
let mirrored = instance.state.pose.determinant() < 0.;
let deformed = instance
.deformation
.as_ref()
.map(|deformation| deformation.mesh_bounds.as_slice());
self.candidates
.place(id.index(), (model, &meshes), mirrored, deformed)
.expect("an edit's dry run found its candidates fit");
}
}
}
}
#[cfg(test)]
mod tests;