use na::{Vec3, Vec2, zero};
use std::ops::{Add, Mul};
use densevec::DenseVec;
use crate::mesh;
#[cfg(feature="rayon")]
use rayon::prelude::*;
#[cfg(not(feature="rayon"))]
mod rayon {
#[derive(Copy, Clone)]
pub struct Scope;
pub struct Spawn;
pub fn scope<F: FnMut(Scope)>(mut f: F){
f(Scope)
}
impl Scope {
pub fn spawn<F: FnMut(Spawn)>(self, mut f: F) {
f(Spawn)
}
}
}
#[inline]
pub fn lerp<T: Add<T, Output = T> + Mul<f32, Output = T>>(p0: T, p1: T, pct: f32) -> T{
p0 * (1.0 - pct) + p1 * pct
}
#[derive(Clone)]
struct Face<V>{
v: V,
uv: Option<Vec2>,
face: u32,
edges: Vec<u32>
}
#[derive(Clone, Debug)]
struct Edge<'a, V>{
v: V,
deform_vert: Option<mesh::MDeformVert>,
v1: u32,
v2: u32,
crease: u8,
faces: &'a EdgeFaces,
}
#[derive(Clone, Debug)]
struct EdgeFaces{
f1: u32,
f2: u32,
len: u8,
}
impl EdgeFaces{
fn new() -> EdgeFaces {
EdgeFaces{
f1: 0,
f2: 0,
len: 0,
}
}
fn push(&mut self, f: u32) {
match self.len {
0 => self.f1 = f,
1 => self.f2 = f,
_ => unreachable!(),
}
self.len += 1;
}
fn len(&self) -> u8 {
self.len
}
fn iter(&self) -> EdgeFacesIter {
EdgeFacesIter {
faces: self,
i: 0,
}
}
}
struct EdgeFacesIter<'a>{
faces: &'a EdgeFaces,
i: u8,
}
impl<'a> Iterator for EdgeFacesIter<'a>{
type Item = u32;
fn next(&mut self) -> Option<u32> {
if self.i < self.faces.len() {
let f = if self.i == 0 {
self.faces.f1
}else{
self.faces.f2
};
self.i += 1;
Some(f)
}else{
None
}
}
}
#[inline]
fn mid_point<V: Add<V, Output=V> + Mul<f32, Output=V>>(v1: V, v2: V) -> V{
(v1 + v2) * 0.5
}
#[inline]
fn mid_point4<V: Add<V, Output=V> + Mul<f32, Output=V>>(v1: V, v2: V, v3: V, v4: V) -> V{
(v1 + v2 + v3 + v4) * 0.25
}
mod edgesmap {
use densevec::DenseVec;
pub struct OccupiedEntry<'a> {
entry: &'a mut (u32, usize),
}
pub struct VacantEntry<'a> {
pos: usize,
dst: u32,
list: &'a mut smallvec::SmallVec<[(u32, usize);8]>,
}
pub enum Entry<'a> {
Occupied(OccupiedEntry<'a>),
Vacant(VacantEntry<'a>),
}
impl<'a> Entry<'a> {
pub fn or_insert_with<F>(self, default: F) -> &'a mut usize
where F: FnOnce() -> usize
{
match self {
Entry::Occupied(occupied) => &mut occupied.entry.1,
Entry::Vacant(vacant) => {
vacant.list.insert(vacant.pos, (vacant.dst, default()));
unsafe{ &mut vacant.list.get_unchecked_mut(vacant.pos).1 }
}
}
}
}
pub struct EdgesMap {
edges: DenseVec<smallvec::SmallVec<[(u32, usize);8]>>,
}
impl EdgesMap {
pub fn with_capacity(capacity: usize) -> EdgesMap {
EdgesMap { edges: DenseVec::with_capacity(capacity) }
}
pub fn entry(&mut self, v1: u32, v2: u32) -> Entry {
let d = v1 as i32 - v2 as i32;
let min = (v2 as i32 + (d & d>>31)) as u32;
let max = (v1 as i32 - (d & d>>31)) as u32;
let list = self.edges.entry(min as usize)
.or_insert_with(|| smallvec::SmallVec::new());
match list.binary_search_by(|entry| entry.0.cmp(&max)) {
Ok(pos) => Entry::Occupied(OccupiedEntry{entry: &mut list[pos]}),
Err(pos) => Entry::Vacant(VacantEntry{pos, list, dst: max}),
}
}
}
}
pub fn subdivide(mesh: &mut mesh::Mesh, subdivide_uvs: bool){
let has_uvs = subdivide_uvs && !mesh.mloopuv.is_empty();
let zero3: Vec3 = zero();
let zero2: Vec2 = zero();
trace!(
"Subdividing {} vertices, {} faces, {} edges",
mesh.mvert.len(),
mesh.mpoly.len(),
mesh.medge.len()
);
let new_face_points: Vec<Face<Vec3>> =
time!("create face points", {
#[cfg(feaqture = "rayon")]
let polys = mesh.mpoly.par_iter();
#[cfg(not(feaqture = "rayon"))]
let polys = mesh.mpoly.iter();
if has_uvs {
polys.enumerate().map(|(idx,poly)| {
let loopstart = poly.loopstart as usize;
let totloop = poly.totloop as usize;
let face = &mesh.mloop[loopstart..loopstart+totloop];
let faceuv = &mesh.mloopuv[loopstart..loopstart+totloop];
let (sum, sum_uv) = face.iter().zip(faceuv.iter()).map(|(mloop, mloopuv)|{
(mesh.mvert[mloop.v as usize].position, mloopuv.uv)
}).fold((zero3, zero2), |(sum, sum_uv), (v, uv)| (sum + v, sum_uv + uv));
let avg = sum / totloop as f32;
let avg_uv = sum_uv / totloop as f32;
let edges = face.iter().map(|mloop| mloop.e).collect();
Face{
v: avg,
uv: Some(avg_uv),
face: idx as u32,
edges: edges
}
}).collect()
}else{
polys.enumerate().map(|(idx,poly)|{
let loopstart = poly.loopstart as usize;
let totloop = poly.totloop as usize;
let face = &mesh.mloop[loopstart..loopstart+totloop];
let sum = face.iter().map(|mloop|{
mesh.mvert[mloop.v as usize].position
}).fold(zero3, |sum, v| sum + v);
let avg = sum / totloop as f32;
let edges = face.iter().map(|mloop| mloop.e).collect();
Face{
v: avg,
uv: None,
face: idx as u32,
edges: edges
}
}).collect()
}
});
let mut vertex_edge_index: DenseVec<Vec<u32>>
= DenseVec::with_capacity(mesh.medge.len() * 2);
let mut edge_face_index: DenseVec<EdgeFaces>
= DenseVec::with_capacity(new_face_points.len() * 4);
let mut loop_poly_index = vec![];
let mut new_polys = vec![];
time!("fill vertex->edge, edge->face, loop->poly indices and recreate polys", {
rayon::scope(|s| {
s.spawn(|_| for (edge_idx, edge) in mesh.medge.iter().enumerate(){
vertex_edge_index
.entry(edge.v1 as usize)
.or_insert(vec![])
.push(edge_idx as u32);
vertex_edge_index
.entry(edge.v2 as usize)
.or_insert(vec![])
.push(edge_idx as u32);
});
s.spawn(|_| for face in new_face_points.iter() {
for edge in face.edges.iter() {
edge_face_index
.entry(*edge as usize)
.or_insert(EdgeFaces::new())
.push(face.face);
}
});
s.spawn(|_| loop_poly_index = mesh.mpoly.iter().enumerate()
.flat_map(|(face_idx, poly)| {
std::iter::repeat(face_idx).take(poly.totloop as usize)
}).collect::<Vec<_>>()
);
s.spawn(|_| new_polys = mesh.mpoly.iter()
.flat_map(|poly| {
let start = poly.loopstart * 4;
(start .. start + poly.totloop * 4).step_by(4).map(move |loopstart|
mesh::MPoly {
loopstart,
totloop: 4,
mat_nr: poly.mat_nr,
flag: poly.flag,
pad: 0,
}
)
})
.collect()
);
})
});
let no_faces = EdgeFaces::new();
#[cfg(feaqture = "rayon")]
let edges = mesh.medge.par_iter();
#[cfg(not(feaqture = "rayon"))]
let edges = mesh.medge.iter();
let new_edge_points: Vec<Edge<Vec3>> =
time!("create edge points", {
edges.enumerate().map(|(edge_idx,edge)| {
let faces = edge_face_index.get(edge_idx).unwrap_or(&no_faces);
let edge_v1 = mesh.mvert[edge.v1 as usize].position;
let edge_v2 = mesh.mvert[edge.v2 as usize].position;
let v = if faces.len == 2 {
if edge.crease == 0 {
let face1_v = new_face_points[faces.f1 as usize].v;
let face2_v = new_face_points[faces.f2 as usize].v;
mid_point4(edge_v1, edge_v2, face1_v, face2_v)
}else if edge.crease == 255 {
mid_point(edge_v1, edge_v2)
}else{
let face1_v = new_face_points[faces.f1 as usize].v;
let face2_v = new_face_points[faces.f2 as usize].v;
let smooth = mid_point4(edge_v1, edge_v2, face1_v, face2_v);
let hard = mid_point(edge_v1, edge_v2);
lerp(smooth, hard, edge.crease as f32 / 255.)
}
}else{
mid_point(edge_v1, edge_v2)
};
Edge{
v: v,
deform_vert: None,
v1: edge.v1,
v2: edge.v2,
crease: edge.crease,
faces: faces,
}
}).collect()
});
let num_verts = mesh.mvert.len() as u32;
let num_edges = mesh.medge.len();
let num_faces = new_face_points.len() as u32;
time!("modify old vertices", {
#[cfg(feaqture = "rayon")]
let verts = mesh.mvert.par_iter();
#[cfg(not(feaqture = "rayon"))]
let verts = mesh.mvert.iter();
let old_vertices = verts.enumerate().map(|(vert_idx,p)| {
let mut any_single_face = false;
let mut num_faces = 0;
let vertex_edges = &vertex_edge_index[vert_idx];
let edges: Vec<&Edge<Vec3>> = vertex_edges.iter()
.map(|edge_idx| {
let edge = &new_edge_points[(*edge_idx) as usize];
any_single_face |= edge.faces.len() == 1;
num_faces += edge.faces.len() as usize;
edge
})
.collect();
let num_sharp_edges = vertex_edges.iter()
.filter(|&&edge_idx| mesh.medge[edge_idx as usize].crease > 0)
.count();
let sharpness = vertex_edges.iter()
.map(|edge_idx| mesh.medge[(*edge_idx) as usize].crease as f32 / 255.)
.fold(0., |sum, crease| sum + crease) / num_sharp_edges as f32;
let num_edges = edges.len();
let is_hole = num_faces != num_edges;
let (num_edges, sum) = if is_hole && any_single_face {
edges.iter().filter(|edge| edge.faces.len() == 1 ).map(|edge| {
let v1 = &mesh.mvert[edge.v1 as usize];
let v2 = &mesh.mvert[edge.v2 as usize];
mid_point(v1.position, v2.position)
}).fold((0, zero3), |(num, sum), v|{
(num + 1, sum + v)
})
}else{
let sum = edges.iter().map(|edge| {
let v1 = &mesh.mvert[edge.v1 as usize];
let v2 = &mesh.mvert[edge.v2 as usize];
mid_point(v1.position, v2.position)
}).fold(zero3, |sum, v|{
sum + v
});
(edges.len(), sum)
};
let r = sum/num_edges as f32;
let mut new_p = *p;
if !is_hole{
let sum = edges.iter()
.flat_map(|edge| edge.faces.iter())
.map(|face_idx| new_face_points[face_idx as usize].v)
.fold(zero3, |sum, v|{
sum + v
});
let f = sum/num_faces as f32;
if num_sharp_edges<2 {
new_p.position = (f + 2.0 * r + (num_faces as f32 - 3.0) * p.position) / num_faces as f32;
}else if num_sharp_edges==2 {
let hard_edges: Vec<&mesh::MEdge> = vertex_edges.iter()
.filter(|&&edge_idx| mesh.medge[edge_idx as usize].crease > 0)
.map(|&idx| &mesh.medge[idx as usize])
.collect();
let v2 = if hard_edges[0].v1 == vert_idx as u32{
hard_edges[0].v2 as usize
}else{
hard_edges[0].v1 as usize
};
let v3 = if hard_edges[1].v1 == vert_idx as u32{
hard_edges[1].v2 as usize
}else{
hard_edges[1].v1 as usize
};
let hard_v = p.position * 3./4. + mesh.mvert[v2].position * 1./8. + mesh.mvert[v3].position * 1./8.;
let soft_v = (f + 2.0 * r + (num_faces as f32 - 3.0) * p.position) / num_faces as f32;
new_p.position = lerp(soft_v, hard_v, sharpness);
}else{
let hard_v = p.position;
let soft_v = (f + 2.0 * r + (num_faces as f32 - 3.0) * p.position) / num_faces as f32;
new_p.position = lerp(soft_v, hard_v, sharpness);
}
}else{
new_p.position = mid_point(r, p.position);
}
new_p
}).collect();
mesh.mvert = old_vertices;
});
let loop_edges_index = time!("loop edges", {
#[cfg(feaqture = "rayon")]
let loops = mesh.mloop.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loops = mesh.mloop.iter();
loops
.enumerate()
.map(|(idx, mloop)| {
let v = mloop.v;
let face_idx = loop_poly_index[idx];
let mut edges = new_face_points[face_idx as usize].edges.iter()
.filter(|&&edge_idx| {
let edge = &new_edge_points[edge_idx as usize];
edge.v1 == v || edge.v2 == v
})
.copied();
let edge0 = edges.next().unwrap();
let edge1 = edges.next().unwrap();
let (edge0_idx, edge1_idx) = if edge0 == mloop.e{
(edge0, edge1)
}else{
(edge1, edge0)
};
(edge0_idx, edge1_idx)
})
.collect::<Vec<_>>()
});
let mut new_edges = Vec::with_capacity(num_edges * 4);
let mut new_edge_index = Vec::with_capacity(mesh.mloop.len());
time!("recreate edges and add face and edge vertices", {
let mvert = &mut mesh.mvert;
let mloop = &mesh.mloop;
let medge = &mesh.medge;
rayon::scope(|s| {
s.spawn(|_| {
let mut set = edgesmap::EdgesMap::with_capacity(num_edges * 4);
let mut loop_edges = loop_edges_index.iter();
for (mloop, face_idx) in mloop.iter().zip(loop_poly_index.iter().copied()) {
let v = mloop.v;
let (edge0_idx, edge1_idx) = loop_edges.next().unwrap();
let edge0 = &medge[*edge0_idx as usize];
let edge1 = &medge[*edge1_idx as usize];
let v1 = v;
let v2 = num_verts + num_faces + edge0_idx;
let v3 = num_verts + face_idx as u32;
let v4 = num_verts + num_faces + edge1_idx;
let e1 = *set.entry(v1, v2).or_insert_with(|| {
let e = new_edges.len();
new_edges.push(mesh::MEdge {
v1: v1,
v2: v2,
crease: edge0.crease,
bweight: edge0.bweight,
flag: edge0.flag,
});
e
});
let e2 = *set.entry(v2, v3).or_insert_with(|| {
let e = new_edges.len();
new_edges.push(mesh::MEdge {
v1: v2,
v2: v3,
crease: edge0.crease,
bweight: edge0.bweight,
flag: edge0.flag,
});
e
});
let e3 = *set.entry(v3, v4).or_insert_with(|| {
let e = new_edges.len();
new_edges.push(mesh::MEdge {
v1: v3,
v2: v4,
crease: edge1.crease,
bweight: edge1.bweight,
flag: edge1.flag,
});
e
});
let e4 = *set.entry(v4, v1).or_insert_with(|| {
let e = new_edges.len();
new_edges.push(mesh::MEdge {
v1: v4,
v2: v1,
crease: edge1.crease,
bweight: edge1.bweight,
flag: edge1.flag,
});
e
});
new_edge_index.push((e1 as u32, e2 as u32, e3 as u32, e4 as u32));
}
});
s.spawn(|_| {
mvert.extend(new_face_points.iter().map(|face|{
mesh::MVert{
position: face.v,
normal: zero3,
flag: 0,
bweight: 0,
pad: [0; 6]
}
}));
mvert.extend(new_edge_points.iter().map(|edge|{
mesh::MVert{
position: edge.v,
normal: zero3,
flag: 0,
bweight: 0,
pad: [0; 6]
}
}));
});
});
});
mesh.medge = new_edges;
let new_loops: Vec<mesh::MLoop> = time!("recreate loops", {
#[cfg(feaqture = "rayon")]
let loops = mesh.mloop.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loops = mesh.mloop.iter();
#[cfg(feaqture = "rayon")]
let loop_polys = loop_poly_index.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loop_polys = loop_poly_index.iter();
#[cfg(feaqture = "rayon")]
let loop_edges = loop_edges_index.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loop_edges = loop_edges_index.iter();
#[cfg(feaqture = "rayon")]
let new_edges = new_edge_index.par_iter();
#[cfg(not(feaqture = "rayon"))]
let new_edges = new_edge_index.iter();
let mloop = loops
.zip(loop_polys.copied())
.zip(loop_edges)
.zip(new_edges)
.map(|(((mloop, face_idx), (edge0_idx, edge1_idx)), (e1, e2, e3, e4))|{
let v1 = mloop.v;
let v2 = num_verts + num_faces + edge0_idx;
let v3 = num_verts + face_idx as u32;
let v4 = num_verts + num_faces + edge1_idx;
(
mesh::MLoop{
v: v1,
e: *e1,
},
mesh::MLoop{
v: v2,
e: *e2,
},
mesh::MLoop{
v: v3,
e: *e3,
},
mesh::MLoop{
v: v4,
e: *e4,
}
)
}).collect::<Vec<_>>();
let len = mloop.len();
let cap = mloop.capacity();
let mloop_ = unsafe{ Vec::from_raw_parts(mloop.as_ptr() as *mut mesh::MLoop, len * 4, cap * 4) };
std::mem::forget(mloop);
mloop_
});
let new_loops_uv: Vec<mesh::MLoopUV> = time!("recreate loops uvs", {
if has_uvs {
#[cfg(feaqture = "rayon")]
let loops = mesh.mloop.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loops = mesh.mloop.iter();
#[cfg(feaqture = "rayon")]
let loops_uv = mesh.mloopuv.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loops_uv = mesh.mloopuv.iter();
#[cfg(feaqture = "rayon")]
let loop_polys = loop_poly_index.par_iter();
#[cfg(not(feaqture = "rayon"))]
let loop_polys = loop_poly_index.iter();
let mloopuvs = loops
.zip(loops_uv)
.zip(loop_polys.copied())
.enumerate()
.map(|(i, ((mloop, mloopuv), face_idx))| {
let v = mloop.v;
let face_point_uv: Vec2 = new_face_points[face_idx].uv.unwrap();
let poly = &mesh.mpoly[face_idx];
let loops = &mesh.mloop[poly.loopstart as usize .. poly.loopstart as usize + poly.totloop as usize];
let loopuvs = &mesh.mloopuv[poly.loopstart as usize .. poly.loopstart as usize + poly.totloop as usize];
let (edge0_idx, edge1_idx) = loop_edges_index[i];
let edge0 = &new_edge_points[edge0_idx as usize];
let edge1 = &new_edge_points[edge1_idx as usize];
let edges = [edge0, edge1];
let mut edges_uvs = edges.iter().map(|edge| {
let edge_uv1 = loops.iter().position(|mloop| mloop.v == edge.v1).unwrap();
let edge_uv2 = loops.iter().position(|mloop| mloop.v == edge.v2).unwrap();
let edge_uv1 = loopuvs[edge_uv1].uv;
let edge_uv2 = loopuvs[edge_uv2].uv;
if edge.faces.len() == 2{
let face1_uv = new_face_points[edge.faces.f1 as usize].uv.unwrap();
let face2_uv = new_face_points[edge.faces.f2 as usize].uv.unwrap();
mid_point4(edge_uv1, edge_uv2, face1_uv, face2_uv)
}else{
mid_point(edge_uv1, edge_uv2)
}
});
let edge0_uv = edges_uvs.next().unwrap();
let edge1_uv = edges_uvs.next().unwrap();
let mut num_faces_this_vert = 0;
let mut any_single_face = false;
let vert_edges: Vec<&Edge<Vec3>> = vertex_edge_index[v as usize].iter()
.map(|edge_idx| {
let edge = &new_edge_points[(*edge_idx) as usize];
any_single_face |= edge.faces.len() == 1;
num_faces_this_vert += edge.faces.len() as usize;
edge
})
.collect();
let num_edges_this_vert = vert_edges.len();
let is_hole = num_faces_this_vert != num_edges_this_vert;
let (num_edges, sum_uv) = if is_hole && any_single_face {
vert_edges.iter().filter(|edge| edge.faces.len() == 1).map(|edge| {
let poly = edge.faces.f1;
let poly = mesh.mpoly[poly as usize];
let loopstart = poly.loopstart as usize;
let loops = &mesh.mloop[loopstart..loopstart+poly.totloop as usize];
let loopuvs = &mesh.mloopuv[loopstart..loopstart+poly.totloop as usize];
let edge_uv1 = loops.iter().position(|mloop| mloop.v == edge.v1).unwrap();
let edge_uv2 = loops.iter().position(|mloop| mloop.v == edge.v2).unwrap();
let edge_uv1 = loopuvs[edge_uv1].uv;
let edge_uv2 = loopuvs[edge_uv2].uv;
mid_point(edge_uv1, edge_uv2)
}).fold((0, zero2), |(num, sum_uv), uv|{
(num + 1, sum_uv + uv)
})
}else{
let sum_uv = vert_edges.iter().map(|edge| {
let poly = edge.faces.f1;
let poly = mesh.mpoly[poly as usize];
let loopstart = poly.loopstart as usize;
let loops = &mesh.mloop[loopstart..loopstart+poly.totloop as usize];
let loopuvs = &mesh.mloopuv[loopstart..loopstart+poly.totloop as usize];
let edge_uv1 = loops.iter().position(|mloop| mloop.v == edge.v1).unwrap();
let edge_uv2 = loops.iter().position(|mloop| mloop.v == edge.v2).unwrap();
let edge_uv1 = loopuvs[edge_uv1].uv;
let edge_uv2 = loopuvs[edge_uv2].uv;
mid_point(edge_uv1, edge_uv2)
}).fold(zero2, |sum_uv, uv|{
sum_uv + uv
});
(num_edges_this_vert, sum_uv)
};
let r = sum_uv/num_edges as f32;
let uv = if !is_hole {
let sum_uv = vert_edges.iter().flat_map(|edge| edge.faces.iter())
.map(|face_idx| new_face_points[face_idx as usize].uv.unwrap())
.fold(zero2, |sum_uv, uv| sum_uv + uv);
let f = sum_uv/num_faces_this_vert as f32;
(f + 2.0 * r + (num_faces_this_vert as f32 - 3.0) * mloopuv.uv) / num_faces_this_vert as f32
}else{
mid_point(r, mloopuv.uv)
};
(
mesh::MLoopUV{
uv: uv,
flag: mloopuv.flag,
},
mesh::MLoopUV{
uv: edge0_uv,
flag: mloopuv.flag,
},
mesh::MLoopUV{
uv: face_point_uv,
flag: mloopuv.flag,
},
mesh::MLoopUV{
uv: edge1_uv,
flag: mloopuv.flag,
}
)
}).collect::<Vec<_>>();
let len = mloopuvs.len();
let cap = mloopuvs.capacity();
let mloopuvs_ = unsafe{ Vec::from_raw_parts(mloopuvs.as_ptr() as *mut mesh::MLoopUV, len * 4, cap * 4) };
std::mem::forget(mloopuvs);
mloopuvs_
}else{
vec![]
}
});
mesh.mloop = new_loops;
mesh.mloopuv = new_loops_uv;
mesh.mpoly = new_polys;
mesh.dvert.clear();
}