summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main.rs128
-rw-r--r--src/spatial/mod.rs9
-rw-r--r--src/spatial/mtree.rs59
-rw-r--r--src/spatial/octtree.rs66
4 files changed, 198 insertions, 64 deletions
diff --git a/src/main.rs b/src/main.rs
index 065fa0d..7f13114 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,14 +1,25 @@
+pub mod spatial;
+
use anyhow::Result;
use glam::DVec3;
use indicatif::ProgressIterator;
use log::{debug, info};
use osm_pbf_reader::{Blobs, data::primitives::Primitive};
use rayon::iter::{ParallelBridge, ParallelIterator};
-use std::{collections::HashMap, env::args, f64::consts::PI};
+use spatial::{SpatialTree, octtree::Octtree};
+use std::{collections::BTreeMap, env::args, f64::consts::PI, fs::File, io::BufWriter};
+use weareshared::{
+ helper::AABB,
+ packets::Resource,
+ resources::{Prefab, RespackEntry, SpatialIndex},
+ respack::save_full_respack,
+ store::ResourceStore,
+};
fn main() -> Result<()> {
env_logger::init_from_env("LOG");
let inpath = args().nth(1).unwrap();
+ let outpath = args().nth(2).unwrap();
let node_positions = Blobs::from_path(&inpath)?
.progress_count(1_500)
@@ -22,20 +33,20 @@ fn main() -> Result<()> {
let lat = n.nano_lat as f64 / 1_000_000_000. / 180. * PI;
let lon = n.nano_lon as f64 / 1_000_000_000. / 180. * PI;
let pos = DVec3::new(lat.sin() * lon.cos(), lon.sin(), lat.cos() * lon.cos());
- npos.push((n.id, pos));
+ npos.push((map_nodeid(n.id), pos));
};
}
npos
})
.fold(
- || HashMap::new(),
+ || BTreeMap::new(),
|mut a, b| {
a.extend(b);
a
},
)
.reduce(
- || HashMap::new(),
+ || BTreeMap::new(),
|mut a, b| {
if !a.is_empty() && !b.is_empty() {
debug!("merge positions {} + {}", a.len(), b.len());
@@ -45,78 +56,67 @@ fn main() -> Result<()> {
},
);
- let mut tree = MTree::default();
- info!("Building M-Tree over node positions...");
+ let mut tree = Octtree::new(DVec3::splat(1.5));
+ info!("Building tree over node positions...");
for (id, pos) in node_positions.into_iter().progress() {
tree.insert(pos, id);
}
info!("Done, depth={}", tree.depth());
- // Blobs::from_path(&inpath)?
- // .progress_count(1_500)
- // .par_bridge()
- // .map(|e| {
- // let mut e = e.unwrap();
- // let e = e.decode().unwrap();
- // for p in e.primitives() {
- // if let Primitive::Node(n) = p {
- // }
- // }
- // })
- // .for_each(|_| ());
+ let store = ResourceStore::new_memory();
+ let (_, root) = export_level(&tree, &store)?;
+ let entry = Some(store.set(&RespackEntry {
+ c_spatial_index: vec![root],
+ ..Default::default()
+ })?);
+ let output = BufWriter::new(File::create(outpath)?);
+ save_full_respack(output, &store, entry)?;
Ok(())
}
-type NodeID = i64;
+fn export_level(node: &Octtree, store: &ResourceStore) -> Result<(AABB, Resource<SpatialIndex>)> {
+ let child = node
+ .children
+ .iter()
+ .flat_map(|e| e.as_slice())
+ .flatten()
+ .flatten()
+ .map(|o| export_level(o, store))
+ .collect::<Result<Vec<_>>>()?;
+
+ let prefab = if node.elems.is_empty() {
+ None
+ } else {
+ Some(store.set(&Prefab {
+ ..Default::default()
+ })?)
+ };
-struct MTree {
- center: DVec3,
- radius: f64,
- nodes: Vec<(DVec3, NodeID)>,
- children: Vec<MTree>,
+ Ok((
+ AABB {
+ min: (node.center - node.size / 2.).as_vec3(),
+ max: (node.center + node.size / 2.).as_vec3(),
+ },
+ store.set(&SpatialIndex {
+ level: None,
+ prefab,
+ child,
+ })?,
+ ))
}
-impl Default for MTree {
- fn default() -> Self {
- Self {
- center: DVec3::ZERO,
- radius: 0.,
- nodes: Vec::new(),
- children: Vec::new(),
- }
- }
+
+type NodeID = u64;
+
+fn map_nodeid(id: i64) -> u64 {
+ // xorshift(xorshift(xorshift(id as u64)))
+ id as u64
}
-impl MTree {
- pub fn insert(&mut self, pos: DVec3, id: NodeID) {
- if self.children.is_empty() {
- self.nodes.push((pos, id));
- if self.nodes.len() > 16 {
- for (pos, id) in self.nodes.drain(..) {
- self.children.push(MTree {
- center: pos,
- radius: 0.,
- nodes: vec![(pos, id)],
- children: Vec::new(),
- });
- }
- }
- } else {
- let mut min_dist = f64::MAX;
- let mut min_index = 0;
- for (i, c) in self.children.iter().enumerate() {
- let d = c.center.distance_squared(pos);
- if d < min_dist {
- min_index = i;
- min_dist = d;
- }
- }
- self.radius = self.radius.max(min_dist.sqrt());
- self.children[min_index].insert(pos, id);
- }
- }
- pub fn depth(&self) -> usize {
- self.children.iter().map(|c| c.depth()).max().unwrap_or(0) + 1
- }
+fn xorshift(mut x: u64) -> u64 {
+ x ^= x << 13;
+ x ^= x >> 7;
+ x ^= x << 17;
+ x
}
enum Elem {
diff --git a/src/spatial/mod.rs b/src/spatial/mod.rs
new file mode 100644
index 0000000..c09824d
--- /dev/null
+++ b/src/spatial/mod.rs
@@ -0,0 +1,9 @@
+use crate::NodeID;
+use glam::DVec3;
+pub mod mtree;
+pub mod octtree;
+
+pub trait SpatialTree {
+ fn insert(&mut self, pos: DVec3, id: NodeID);
+ fn depth(&self) -> usize;
+}
diff --git a/src/spatial/mtree.rs b/src/spatial/mtree.rs
new file mode 100644
index 0000000..d8d2282
--- /dev/null
+++ b/src/spatial/mtree.rs
@@ -0,0 +1,59 @@
+use super::SpatialTree;
+use crate::NodeID;
+use glam::DVec3;
+
+pub struct MTree {
+ center: DVec3,
+ id: NodeID,
+ radius: f64,
+ children: Vec<MTree>,
+}
+impl Default for MTree {
+ fn default() -> Self {
+ Self {
+ id: 0,
+ center: DVec3::ZERO,
+ radius: 0.,
+ children: Vec::new(),
+ }
+ }
+}
+const MAX_CHILDREN: usize = 32;
+impl SpatialTree for MTree {
+ fn insert(&mut self, pos: DVec3, id: NodeID) {
+ if self.children.len() < MAX_CHILDREN {
+ self.children.push(MTree {
+ center: pos,
+ radius: 0.,
+ id,
+ children: Vec::new(),
+ });
+ if self.children.len() == MAX_CHILDREN {
+ for c in &mut self.children {
+ c.children.push(MTree {
+ center: c.center,
+ id: c.id,
+ radius: 0.,
+ children: Vec::new(),
+ });
+ c.id = 0;
+ }
+ }
+ } else {
+ let mut min_dist = f64::MAX;
+ let mut min_index = 0;
+ for (i, c) in self.children.iter().enumerate() {
+ let d = c.center.distance_squared(pos);
+ if d < min_dist {
+ min_index = i;
+ min_dist = d;
+ }
+ }
+ self.radius = self.radius.max(min_dist.sqrt());
+ self.children[min_index].insert(pos, id);
+ }
+ }
+ fn depth(&self) -> usize {
+ self.children.iter().map(|c| c.depth()).max().unwrap_or(0) + 1
+ }
+}
diff --git a/src/spatial/octtree.rs b/src/spatial/octtree.rs
new file mode 100644
index 0000000..f8919f5
--- /dev/null
+++ b/src/spatial/octtree.rs
@@ -0,0 +1,66 @@
+use super::SpatialTree;
+use crate::NodeID;
+use glam::{DVec3, dvec3};
+use std::mem::swap;
+
+pub struct Octtree {
+ pub center: DVec3,
+ pub size: DVec3,
+ pub elems: Vec<(DVec3, NodeID)>,
+ pub children: Option<Box<[[[Octtree; 2]; 2]; 2]>>,
+}
+impl Octtree {
+ pub fn new(size: DVec3) -> Self {
+ Self {
+ center: DVec3::ZERO,
+ size,
+ children: None,
+ elems: Vec::new(),
+ }
+ }
+}
+impl SpatialTree for Octtree {
+ fn insert(&mut self, pos: DVec3, id: NodeID) {
+ if let Some(c) = &mut self.children {
+ let [x, y, z] = (pos - self.center)
+ .to_array()
+ .map(|e| if e > 0. { 1 } else { 0 });
+ c[x][y][z].insert(pos, id);
+ } else {
+ self.elems.push((pos, id));
+ if self.elems.len() > 64 {
+ self.children = Some(Box::new([-1., 1.].map(|x| {
+ [-1., 1.].map(|y| {
+ [-1., 1.].map(|z| Octtree {
+ center: self.center + (self.size / 4.) * dvec3(x, y, z),
+ size: self.size / 2.,
+ elems: Vec::new(),
+ children: None,
+ })
+ })
+ })));
+ let mut elems = Vec::new();
+ swap(&mut elems, &mut self.elems);
+ for (pos, id) in elems {
+ self.insert(pos, id);
+ }
+ }
+ }
+ }
+
+ fn depth(&self) -> usize {
+ if let Some(c) = &self.children {
+ 1 + c[0][0][0]
+ .depth()
+ .max(c[0][0][1].depth())
+ .max(c[0][1][0].depth())
+ .max(c[0][1][1].depth())
+ .max(c[1][0][0].depth())
+ .max(c[1][0][1].depth())
+ .max(c[1][1][0].depth())
+ .max(c[1][1][1].depth())
+ } else {
+ 0
+ }
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.0) at 2025-10-07 21:54:38 +0000