use std::cmp::Ordering;
use crate::cameras::RenderCamera;
use crate::core::{Group, Layers, Node, Object3D};
use crate::materials::MeshBasicNodeMaterial;
use crate::math::{CoordinateSystem, Frustum, Matrix4};
use crate::objects::Payload;
#[derive(Clone)]
pub(crate) struct RenderItem {
pub node: Node,
pub id: u32,
pub group_order: f64,
pub render_order: f64,
pub z: f64,
pub matrix_world: Matrix4,
pub group: Option<Group>,
}
impl RenderItem {
pub fn material<'a>(&self, object: &'a Object3D) -> Option<&'a MeshBasicNodeMaterial> {
match self.group {
Some(group) => object.payload.material_array().get(group.material_index),
None => object.material(),
}
}
}
fn painter_sort_stable(a: &RenderItem, b: &RenderItem) -> Ordering {
compare(a.group_order, b.group_order)
.then_with(|| compare(a.render_order, b.render_order))
.then_with(|| compare(a.z, b.z))
.then_with(|| a.id.cmp(&b.id))
}
fn reverse_painter_sort_stable(a: &RenderItem, b: &RenderItem) -> Ordering {
compare(a.group_order, b.group_order)
.then_with(|| compare(a.render_order, b.render_order))
.then_with(|| compare(b.z, a.z))
.then_with(|| a.id.cmp(&b.id))
}
fn compare(a: f64, b: f64) -> Ordering {
a.partial_cmp(&b).unwrap_or(Ordering::Equal)
}
#[derive(Default)]
pub(crate) struct RenderList {
pub opaque: Vec<RenderItem>,
pub transparent: Vec<RenderItem>,
pub lights: Vec<Node>,
}
impl RenderList {
pub fn new() -> Self {
Self::default()
}
fn push(&mut self, item: RenderItem, transparent: bool) {
if transparent {
self.transparent.push(item);
} else {
self.opaque.push(item);
}
}
fn push_light(&mut self, light: Node) {
self.lights.push(light);
}
pub fn sort(&mut self) {
if self.opaque.len() > 1 {
self.opaque.sort_by(painter_sort_stable);
}
if self.transparent.len() > 1 {
self.transparent.sort_by(reverse_painter_sort_stable);
}
}
pub fn items(&self) -> impl Iterator<Item = &RenderItem> {
self.opaque.iter().chain(self.transparent.iter())
}
pub fn len(&self) -> usize {
self.opaque.len() + self.transparent.len()
}
}
pub(crate) struct ProjectCamera {
pub layers: Layers,
pub proj_screen_matrix: Matrix4,
pub frustum: Frustum,
pub sub_frustums: Vec<Frustum>,
}
impl ProjectCamera {
pub fn from_parts(
layers: Layers,
projection_matrix: &Matrix4,
matrix_world_inverse: &Matrix4,
coordinate_system: CoordinateSystem,
) -> Self {
let mut proj_screen_matrix = Matrix4::identity();
proj_screen_matrix.multiply_matrices(projection_matrix, matrix_world_inverse);
let mut frustum = Frustum::default();
frustum.set_from_projection_matrix(&proj_screen_matrix, coordinate_system, false);
Self {
layers,
proj_screen_matrix,
frustum,
sub_frustums: Vec::new(),
}
}
pub fn new(camera: &dyn RenderCamera) -> Self {
let mut proj_screen_matrix = Matrix4::identity();
proj_screen_matrix
.multiply_matrices(&camera.projection_matrix(), &camera.matrix_world_inverse());
let mut frustum = Frustum::default();
frustum.set_from_projection_matrix(&proj_screen_matrix, camera.coordinate_system(), false);
let sub_frustums = camera
.sub_cameras()
.iter()
.map(|sub| {
let mut matrix = Matrix4::identity();
matrix.multiply_matrices(&sub.projection_matrix, &sub.matrix_world_inverse);
let mut frustum = Frustum::default();
frustum.set_from_projection_matrix(&matrix, sub.coordinate_system, false);
frustum
})
.collect();
Self {
layers: camera.layers(),
proj_screen_matrix,
frustum,
sub_frustums,
}
}
}
pub(crate) fn project_object(
object: &Node,
camera: &ProjectCamera,
group_order: f64,
render_list: &mut RenderList,
sort_objects: bool,
) {
if !object.borrow().visible {
return;
}
let mut group_order = group_order;
let visible = object.borrow().layers.test(&camera.layers);
if visible {
let (is_group, is_light, is_drawable) = {
let o = object.borrow();
(
o.is_group,
o.is_light,
o.is_mesh() || o.is_line() || o.is_points() || o.payload.is_sprite(),
)
};
if is_group {
group_order = object.borrow().render_order;
} else if is_light {
render_list.push_light(object.clone());
} else if is_drawable {
project_drawable(object, camera, group_order, render_list, sort_objects);
}
}
for child in object.children() {
project_object(&child, camera, group_order, render_list, sort_objects);
}
}
fn project_drawable(
object: &Node,
camera: &ProjectCamera,
group_order: f64,
render_list: &mut RenderList,
sort_objects: bool,
) {
{
let needs_sphere = {
let o = object.borrow();
o.frustum_culled
&& matches!(&o.payload, Payload::InstancedMesh(instanced)
if instanced.bounding_sphere.is_none())
};
if needs_sphere {
if let Payload::InstancedMesh(instanced) = &mut object.borrow_mut().payload {
instanced.compute_bounding_sphere();
}
}
}
let o = object.borrow();
let geometry = match o.geometry() {
Some(geometry) => geometry.clone(),
None => return,
};
if o.frustum_culled {
let inside = match o.payload.bounding_sphere_in(&o.matrix_world) {
Some(sphere) if !camera.sub_frustums.is_empty() => camera
.sub_frustums
.iter()
.any(|frustum| frustum.intersects_sphere(&sphere)),
Some(sphere) => camera.frustum.intersects_sphere(&sphere),
None => false,
};
if !inside {
return;
}
}
let z = if sort_objects && o.payload.is_sprite() {
let e = &o.matrix_world.elements;
apply_matrix4_vector4(&camera.proj_screen_matrix, [e[12], e[13], e[14], e[15]])[2]
} else if sort_objects {
let center = geometry.bounding_sphere_center();
let v = apply_matrix4_vector4(&o.matrix_world, [center.x, center.y, center.z, 1.0]);
apply_matrix4_vector4(&camera.proj_screen_matrix, v)[2]
} else {
0.0
};
let material_array = o.payload.material_array();
if !material_array.is_empty() {
let items: Vec<(RenderItem, bool)> = geometry
.groups
.iter()
.filter_map(|group| {
let material = material_array.get(group.material_index)?;
material.visible.then(|| {
(
RenderItem {
node: object.clone(),
id: o.id,
group_order,
render_order: o.render_order,
z,
matrix_world: o.matrix_world,
group: Some(*group),
},
material.transparent || material.transmission > 0.0,
)
})
})
.collect();
drop(o);
for (item, transparent) in items {
render_list.push(item, transparent);
}
return;
}
let (visible, transparent) = match o.material() {
Some(material) => (
material.visible,
material.transparent || material.transmission > 0.0,
),
None => (true, false),
};
if !visible {
return;
}
let item = RenderItem {
node: object.clone(),
id: o.id,
group_order,
render_order: o.render_order,
z,
matrix_world: o.matrix_world,
group: None,
};
drop(o);
render_list.push(item, transparent);
}
fn apply_matrix4_vector4(m: &Matrix4, v: [f64; 4]) -> [f64; 4] {
let e = &m.elements;
[
e[0] * v[0] + e[4] * v[1] + e[8] * v[2] + e[12] * v[3],
e[1] * v[0] + e[5] * v[1] + e[9] * v[2] + e[13] * v[3],
e[2] * v[0] + e[6] * v[1] + e[10] * v[2] + e[14] * v[3],
e[3] * v[0] + e[7] * v[1] + e[11] * v[2] + e[15] * v[3],
]
}
#[cfg(test)]
mod tests {
use std::rc::Rc;
use super::*;
use crate::cameras::PerspectiveCamera;
use crate::core::BufferGeometry;
use crate::geometries::box_geometry;
use crate::lights::PointLight;
use crate::materials::MeshBasicNodeMaterial;
use crate::math::{Color, Vector3};
use crate::objects::{Group, Mesh, Scene};
fn camera() -> PerspectiveCamera {
let mut camera = PerspectiveCamera::new(70.0, 2.0, 0.1, 100.0);
camera.node.borrow_mut().position.z = 10.0;
camera.update_matrix_world();
camera
}
fn unit_box() -> Rc<BufferGeometry> {
Rc::new(box_geometry(1.0, 1.0, 1.0, 1, 1, 1))
}
fn mesh_at(z: f64) -> Node {
let node = Mesh::new(unit_box(), MeshBasicNodeMaterial::new());
node.borrow_mut().position.z = z;
node
}
fn world_x(node: &Node) -> f64 {
let mut position = Vector3::ZERO;
position.set_from_matrix_position(&node.borrow().matrix_world);
position.x
}
fn project(scene: &Scene, camera: &PerspectiveCamera) -> RenderList {
scene.update_matrix_world();
let mut list = RenderList::new();
project_object(
&scene.node,
&ProjectCamera::new(camera),
0.0,
&mut list,
true,
);
list.sort();
list
}
#[test]
fn multi_material_mesh_pushes_one_item_per_group() {
let scene = Scene::new();
let opaque = MeshBasicNodeMaterial::new();
let mut transparent = MeshBasicNodeMaterial::new();
transparent.transparent = true;
let mut hidden = MeshBasicNodeMaterial::new();
hidden.visible = false;
let mesh = Mesh::with_materials(unit_box(), vec![opaque, transparent.clone(), hidden]);
scene.add(&mesh);
let list = project(&scene, &camera());
let groups = |items: &[RenderItem]| -> Vec<usize> {
items
.iter()
.map(|item| item.group.expect("a group item").material_index)
.collect()
};
assert_eq!(groups(&list.opaque), vec![0]);
assert_eq!(groups(&list.transparent), vec![1]);
let object = mesh.borrow();
let item = &list.transparent[0];
assert!(item.material(&object).unwrap().transparent);
assert_eq!(
(item.group.unwrap().start, item.group.unwrap().count),
(6, 6)
);
}
#[test]
fn collects_meshes_nested_under_groups() {
let scene = Scene::new();
let group = Group::new();
let inner = Group::new();
let a = mesh_at(0.0);
let b = mesh_at(1.0);
scene.add(&group);
group.add(&inner);
inner.add(&a);
scene.add(&b);
let list = project(&scene, &camera());
assert_eq!(list.len(), 2, "a mesh two groups deep is still collected");
assert!(list.transparent.is_empty());
}
#[test]
fn group_world_matrix_reaches_the_nested_mesh() {
let scene = Scene::new();
let group = Group::new();
group.borrow_mut().position.set(3.0, 0.0, 0.0);
let mesh = mesh_at(0.0);
mesh.borrow_mut().position.x = 1.0;
scene.add(&group);
group.add(&mesh);
let list = project(&scene, &camera());
assert_eq!(list.len(), 1);
let world = list.opaque[0].matrix_world;
let mut position = Vector3::ZERO;
position.set_from_matrix_position(&world);
assert_eq!(position.x, 4.0, "the group's translation is composed in");
}
#[test]
fn scene_update_matrix_world_honours_the_auto_update_flags() {
let scene = Scene::new();
let group = Group::new();
let mesh = mesh_at(0.0);
scene.add(&group);
group.add(&mesh);
group.borrow_mut().position.x = 1.0;
mesh.borrow_mut().position.x = 2.0;
scene.update_matrix_world();
assert_eq!(world_x(&mesh), 3.0, "composed through the group");
group.borrow_mut().matrix_auto_update = false;
group.borrow_mut().position.x = 10.0;
scene.update_matrix_world();
assert_eq!(world_x(&mesh), 3.0, "matrixAutoUpdate = false pins it");
group.borrow_mut().update_matrix();
scene.update_matrix_world();
assert_eq!(
world_x(&mesh),
12.0,
"matrixWorldNeedsUpdate forces the walk"
);
mesh.borrow_mut().matrix_world_auto_update = false;
mesh.borrow_mut().position.x = 5.0;
scene.update_matrix_world();
assert_eq!(
world_x(&mesh),
12.0,
"matrixWorldAutoUpdate = false freezes it"
);
}
#[test]
fn invisible_parent_hides_the_whole_subtree() {
let scene = Scene::new();
let group = Group::new();
group.borrow_mut().visible = false;
scene.add(&group);
group.add(&mesh_at(0.0));
assert_eq!(project(&scene, &camera()).len(), 0);
}
#[test]
fn a_layers_miss_skips_the_object_but_not_its_children() {
let scene = Scene::new();
let outer = mesh_at(0.0);
outer.borrow_mut().layers.set(1);
let inner = mesh_at(1.0);
outer.add(&inner);
scene.add(&outer);
let list = project(&scene, &camera());
assert_eq!(list.len(), 1, "only the child is drawn");
assert_eq!(list.opaque[0].id, inner.borrow().id);
}
#[test]
fn frustum_culling_drops_an_object_behind_the_camera() {
let scene = Scene::new();
let behind = mesh_at(40.0); scene.add(&behind);
assert_eq!(project(&scene, &camera()).len(), 0, "culled");
behind.borrow_mut().frustum_culled = false;
assert_eq!(
project(&scene, &camera()).len(),
1,
"frustumCulled = false keeps it"
);
}
#[test]
fn opaque_sorts_front_to_back_and_transparent_back_to_front() {
let scene = Scene::new();
let near = mesh_at(4.0);
let far = mesh_at(-4.0);
scene.add(&far);
scene.add(&near);
let list = project(&scene, &camera());
assert_eq!(
[list.opaque[0].id, list.opaque[1].id],
[near.borrow().id, far.borrow().id],
"painterSortStable: ascending z"
);
for node in [&near, &far] {
node.borrow_mut()
.mesh_mut()
.unwrap()
.material
.as_mut()
.unwrap()
.transparent = true;
}
let list = project(&scene, &camera());
assert!(list.opaque.is_empty());
assert_eq!(
[list.transparent[0].id, list.transparent[1].id],
[far.borrow().id, near.borrow().id],
"reversePainterSortStable: descending z"
);
}
#[test]
fn render_order_and_group_order_outrank_z() {
let scene = Scene::new();
let near = mesh_at(4.0);
near.borrow_mut().render_order = 1.0;
let far = mesh_at(-4.0);
scene.add(&near);
scene.add(&far);
let list = project(&scene, &camera());
assert_eq!(
[list.opaque[0].id, list.opaque[1].id],
[far.borrow().id, near.borrow().id],
"renderOrder beats z"
);
let group = Group::new();
group.borrow_mut().render_order = -1.0;
scene.add(&group);
group.add(&near);
let list = project(&scene, &camera());
assert_eq!(list.opaque[0].group_order, -1.0);
assert_eq!(
[list.opaque[0].id, list.opaque[1].id],
[near.borrow().id, far.borrow().id],
"groupOrder beats renderOrder"
);
}
#[test]
fn an_invisible_material_is_not_pushed() {
let scene = Scene::new();
let mesh = mesh_at(0.0);
mesh.borrow_mut()
.mesh_mut()
.unwrap()
.material
.as_mut()
.unwrap()
.visible = false;
scene.add(&mesh);
assert_eq!(project(&scene, &camera()).len(), 0);
}
#[test]
fn lights_are_collected_and_not_drawn_but_their_children_are() {
let scene = Scene::new();
let light = PointLight::new(Color::new(1.0, 1.0, 1.0), 1.0, 100.0);
let bulb = mesh_at(0.0);
scene.add(&light);
light.add(&bulb);
let list = project(&scene, &camera());
assert_eq!(list.lights.len(), 1, "the light is pushed as a light");
assert_eq!(list.lights[0].borrow().id, light.borrow().id);
assert_eq!(list.len(), 1, "and its bulb mesh is still drawn");
assert_eq!(list.opaque[0].id, bulb.borrow().id);
light.borrow_mut().position.x = 2.0;
let list = project(&scene, &camera());
assert_eq!(world_x(&list.lights[0]), 2.0);
assert_eq!(world_x(&bulb), 2.0, "the bulb rides the light's matrix");
}
#[test]
fn unsorted_keeps_traversal_order() {
let scene = Scene::new();
let far = mesh_at(-4.0);
let near = mesh_at(4.0);
scene.add(&far);
scene.add(&near);
scene.update_matrix_world();
let mut list = RenderList::new();
project_object(
&scene.node,
&ProjectCamera::new(&camera()),
0.0,
&mut list,
false,
);
list.sort();
assert_eq!(
[list.opaque[0].id, list.opaque[1].id],
[far.borrow().id, near.borrow().id],
"with sortObjects off, z stays 0 and the id tie-break holds add order"
);
}
}