a

6 files changed, 354 insertions, 64 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 1967b9d..d5f35c7 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -74,12 +74,57 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "dcfed56ad506cb2c684a14971b8861fdc3baaaae314b9e5f9bb532cbe3ba7a4f"
 
 [[package]]
+name = "arrayref"
+version = "0.3.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "76a2e8124351fda1ef8aaaa3bbd7ebbcb486bbcd4225aca0aa0d84bb2db8fecb"
+
+[[package]]
+name = "arrayvec"
+version = "0.7.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7c02d123df017efcdfbd739ef81735b36c5ba83ec3c59c80a9d7ecc718f92e50"
+
+[[package]]
+name = "bincode"
+version = "2.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "36eaf5d7b090263e8150820482d5d93cd964a81e4019913c972f4edcc6edb740"
+dependencies = [
+ "bincode_derive",
+ "serde",
+ "unty",
+]
+
+[[package]]
+name = "bincode_derive"
+version = "2.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bf95709a440f45e986983918d0e8a1f30a9b1df04918fc828670606804ac3c09"
+dependencies = [
+ "virtue",
+]
+
+[[package]]
 name = "bitflags"
 version = "2.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5c8214115b7bf84099f1309324e63141d4c5d7cc26862f97a0a857dbefe165bd"
 
 [[package]]
+name = "blake3"
+version = "1.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b17679a8d69b6d7fd9cd9801a536cec9fa5e5970b69f9d4747f70b39b031f5e7"
+dependencies = [
+ "arrayref",
+ "arrayvec",
+ "cc",
+ "cfg-if",
+ "constant_time_eq",
+]
+
+[[package]]
 name = "bumpalo"
 version = "3.17.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -141,6 +186,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "constant_time_eq"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7c74b8349d32d297c9134b8c88677813a227df8f779daa29bfc29c183fe3dca6"
+
+[[package]]
 name = "crc32fast"
 version = "1.4.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -259,6 +310,9 @@ name = "glam"
 version = "0.30.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "bf3aa70d918d2b234126ff4f850f628f172542bf0603ded26b8ee36e5e22d5f9"
+dependencies = [
+ "serde",
+]
 
 [[package]]
 name = "hashbrown"
@@ -462,6 +516,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "ppv-lite86"
+version = "0.2.21"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9"
+dependencies = [
+ "zerocopy",
+]
+
+[[package]]
 name = "proc-macro2"
 version = "1.0.94"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -538,6 +601,36 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "74765f6d916ee2faa39bc8e68e4f3ed8949b48cccdac59983d287a7cb71ce9c5"
 
 [[package]]
+name = "rand"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3779b94aeb87e8bd4e834cee3650289ee9e0d5677f976ecdb6d219e5f4f6cd94"
+dependencies = [
+ "rand_chacha",
+ "rand_core",
+ "zerocopy",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d3022b5f1df60f26e1ffddd6c66e8aa15de382ae63b3a0c1bfc0e4d3e3f325cb"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.9.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "99d9a13982dcf210057a8a78572b2217b667c3beacbf3a0d8b454f6f82837d38"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
 name = "rayon"
 version = "1.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -558,6 +651,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "redb"
+version = "2.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ea0a72cd7140de9fc3e318823b883abf819c20d478ec89ce880466dc2ef263c6"
+dependencies = [
+ "libc",
+]
+
+[[package]]
 name = "regex"
 version = "1.11.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -695,6 +797,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1fc81956842c57dac11422a97c3b8195a1ff727f06e85c84ed2e8aa277c9a0fd"
 
 [[package]]
+name = "unty"
+version = "0.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6d49784317cd0d1ee7ec5c716dd598ec5b4483ea832a2dced265471cc0f690ae"
+
+[[package]]
 name = "utf8parse"
 version = "0.2.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -707,6 +815,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "accd4ea62f7bb7a82fe23066fb0957d48ef677f6eeb8215f372f52e48bb32426"
 
 [[package]]
+name = "virtue"
+version = "0.0.18"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "051eb1abcf10076295e815102942cc58f9d5e3b4560e46e53c21e8ff6f3af7b1"
+
+[[package]]
 name = "wasi"
 version = "0.14.2+wasi-0.2.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -783,6 +897,21 @@ dependencies = [
  "log",
  "osm-pbf-reader",
  "rayon",
+ "weareshared",
+]
+
+[[package]]
+name = "weareshared"
+version = "0.1.0"
+dependencies = [
+ "anyhow",
+ "bincode",
+ "blake3",
+ "glam",
+ "log",
+ "rand",
+ "redb",
+ "xdg",
 ]
 
 [[package]]
@@ -890,6 +1019,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "xdg"
+version = "2.5.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "213b7324336b53d2414b2db8537e56544d981803139155afa84f76eeebb7a546"
+
+[[package]]
 name = "xz2"
 version = "0.1.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -897,3 +1032,23 @@ checksum = "388c44dc09d76f1536602ead6d325eb532f5c122f17782bd57fb47baeeb767e2"
 dependencies = [
  "lzma-sys",
 ]
+
+[[package]]
+name = "zerocopy"
+version = "0.8.24"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2586fea28e186957ef732a5f8b3be2da217d65c5969d4b1e17f973ebbe876879"
+dependencies = [
+ "zerocopy-derive",
+]
+
+[[package]]
+name = "zerocopy-derive"
+version = "0.8.24"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a996a8f63c5c4448cd959ac1bab0aaa3306ccfd060472f85943ee0750f0169be"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
diff --git a/Cargo.toml b/Cargo.toml
index cd3eb07..c0becf2 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,3 +11,4 @@ log = "0.4.27"
 osm-pbf-reader = "0.1.1"
 rayon = "1.10.0"
 glam = "0.30.1"
+weareshared = { path = "../wearechat/shared" }
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
+        }
+    }
+}