From 0628e1bc68fd077ef76100b494638a7327e8410e Mon Sep 17 00:00:00 2001
From: Isaac Clayton
Date: Sat, 22 Jan 2022 13:35:33 +0100
Subject: Started working on rendering quadtree
---
src/ctx.rs | 29 +++++++------
src/main.rs | 10 +++--
src/quad.rs | 135 +++++++++++++++++++++++++++++++++++++++++-------------------
src/step.rs | 4 +-
4 files changed, 118 insertions(+), 60 deletions(-)
diff --git a/src/ctx.rs b/src/ctx.rs
index 3eebbec..90d6c15 100644
--- a/src/ctx.rs
+++ b/src/ctx.rs
@@ -1,35 +1,40 @@
-use crate::quad::{Quad, Node};
+use std::marker::PhantomData;
+use crate::quad::{Quad, Node, Embed};
/// Represents a context with shared state.
-pub struct Ctx();
+#[derive(Default, Debug)]
+pub struct Ctx<A: Embed, B: Embed> {
+ _phantom_a: PhantomData<A>,
+ _phantom_b: PhantomData<B>,
+}
-impl Ctx {
+impl<A: Embed, B: Embed> Ctx<A, B> {
/// Creates a new uninitialized context.
pub fn new_empty() -> Self {
- Ctx()
+ Default::default()
}
/// Combines 4 child node representations into a single representation
/// Using a neural network.
- pub fn combine<B>(&mut self, compr: [B; 4]) -> B {
+ pub fn combine(&mut self, compr: [B; 4]) -> B {
todo!("Build new B from 4 child B");
}
/// Compresses a base-level cell into a vector.
- pub fn compress_base<A, B>(&mut self, base: A) -> B {
+ pub fn compress_base(&mut self, base: A) -> B {
todo!("Turn Base Cell into a vector B");
}
- pub fn color_base<A>(&mut self, base: &A) -> [u8; 4] {
+ pub fn color_base(&mut self, base: &A) -> [u8; 4] {
todo!();
}
/// Compresses a single node into a vector representation.
/// Returns `None` if node has already been compressed and trimmed from tree.
/// To recover a trimmed node, use `expand` on the compressed representation.
- pub fn compress<A: Default, B: Copy>(&mut self, quad: &Quad<A, B>) -> Option<B> {
+ pub fn compress(&mut self, quad: &Quad<A, B>) -> Option<B> {
match quad {
- Quad::Base(b) => Some(self.compress_base(b)),
+ Quad::Base(b) => Some(self.compress_base(*b)),
Quad::Node(n) => Some(
self.combine([
n[0].compr,
@@ -43,16 +48,16 @@ impl Ctx {
}
/// Compresses a base-level cell into a vector.
- fn expand_base<A: Default, B: Copy>(&mut self, compr: B) -> A {
+ fn expand_base(&mut self, compr: B) -> A {
todo!("Turn compressed B into the A that made it");
}
- fn expand_node<B>(&mut self, compr: B) -> [B; 4] {
+ fn expand_node(&mut self, compr: B) -> [B; 4] {
todo!("Turn compressed B into 4 child B that made it");
}
/// Expands the compressed representation of a node into a node with 4 children.
- pub fn expand<A: Default, B: Copy>(&mut self, mut compr: Node<A, B>) -> Node<A, B> {
+ pub fn expand(&mut self, mut compr: Node<A, B>) -> Node<A, B> {
match compr.data {
// Can't expand a base node.
Quad::Base(_) => {
diff --git a/src/main.rs b/src/main.rs
index aa5a312..3078f49 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -6,10 +6,12 @@ mod render;
fn main() {
println!("Warming up...");
- // let mut ctx = ctx::Ctx::new_empty();
- // let quad: quad::Node<u8, u8> = quad::Node::new_empty(&mut ctx);
+ let mut ctx = ctx::Ctx::new_empty();
+ let quad: quad::Node<u8, u8> = quad::Node::new_from_square(
+ &mut ctx, vec![0xFF;64],
+ );
- render::graphics();
+ // render::graphics();
- println!("Hello!");
+ println!("{:#?}", quad);
}
diff --git a/src/quad.rs b/src/quad.rs
index 640b1f9..2eb23b1 100644
--- a/src/quad.rs
+++ b/src/quad.rs
@@ -1,8 +1,13 @@
use crate::ctx::Ctx;
+pub trait Embed: Default + Copy + Sized + std::fmt::Debug {
+
+}
+
/// Represents the data present in a quad-tree node.
/// May be the base-level repr, or a node with 4 children.
-pub enum Quad<A: Default, B: Copy> {
+#[derive(Debug)]
+pub enum Quad<A: Embed, B: Embed> {
/// Base cell in grid.
/// May actually be a chunk of cells for performance.
Base(A),
@@ -12,66 +17,67 @@ pub enum Quad<A: Default, B: Copy> {
Cached,
}
+impl Embed for u8 {}
+
/// Represends a node in a quadtree.
/// Has a depth denoting the number of nodes below it.
/// The base node has a depth of 0
/// Nodes should only be siblings of nodes with the same depth.
/// Data stored inside a quadtree node, including children, are in `data`.
-pub struct Node<A: Default, B: Copy> {
+#[derive(Debug)]
+pub struct Node<A: Embed, B: Embed> {
pub depth: usize,
pub compr: B,
pub data: Quad<A, B>,
}
-impl<A: Default, B: Copy> Node<A, B> {
- /// Bytes must be of size (2**depth)**2 * 4
- pub fn write_rgba8(
- self,
- ctx: &mut Ctx,
- bytes: &mut [u8],
- depth: usize,
- x: usize,
- y: usize,
- ) -> Self {
- let mut expanded = ctx.expand(self);
- expanded.data = match expanded.data {
- // Base cell in grid.
- Quad::Base(base) => {
- let mut color = ctx.color_base(&base);
- let idx = ((1 << depth) * y + x) * 4;
- bytes[idx..(idx + 4)].swap_with_slice(&mut color);
- Quad::Base(base)
- },
- // Node with 4 children.
- Quad::Node(children) => {
- let size = 1 << expanded.depth;
- let half = size / 2;
- let c = [
- children[0].write_rgba8(ctx, bytes, depth, x, y ),
- children[1].write_rgba8(ctx, bytes, depth, x + half, y ),
- children[2].write_rgba8(ctx, bytes, depth, x, y + half),
- children[3].write_rgba8(ctx, bytes, depth, x + half, y + half),
- ];
- todo!()
+impl<A: Embed, B: Embed> Node<A, B> {
+ pub fn sample_color(self, ctx: &mut Ctx<A, B>, x: isize, y: isize) -> (Self, [u8; 4]) {
+ // self = ctx.expand(self);
+ // if let Quad::Base(b) = self.data {
+ // return (self, ctx.color_base(&b));
+ // }
+
+ let child_size = 1 << (self.depth - 1);
+ let nx = (x + child_size) % child_size;
+ let ny = (y + child_size) % child_size;
+
+ match (x >= 0, y >= 0) {
+ (true, true) => {
+ let x = x;
},
- // Children may be generated from Node.
- Cached => { unreachable!(); },
- };
- expanded
+ _ => { unreachable!(); }
+ }
+
+ // self
+ todo!()
+ }
+
+ /// Creates a new tree with a single empty base node
+ pub fn new_empty(ctx: &mut Ctx<A, B>) -> Self {
+ Self::new_base(ctx, Default::default())
}
/// Creates a new tree from a single base node
- pub fn new_base(base: A, ctx: &mut Ctx) -> Self {
+ pub fn new_base(ctx: &mut Ctx<A, B>, base: A) -> Self {
Node {
depth: 0,
- compr: ctx.compress_base(&base),
+ compr: ctx.compress_base(base),
data: Quad::Base(base),
}
}
- /// Creates a new tree with a single empty base node
- pub fn new_empty(ctx: &mut Ctx) -> Self {
- Self::new_base(Default::default(), ctx)
+ pub fn new_node(ctx: &mut Ctx<A, B>, children: [Node<A, B>;4]) -> Self {
+ // Make sure the depths check out
+ assert_eq!(children[0].depth, children[1].depth);
+ assert_eq!(children[1].depth, children[2].depth);
+ assert_eq!(children[2].depth, children[3].depth);
+ let depth = children[0].depth + 1;
+
+ // compress and build the node
+ let quad = Quad::Node(Box::new(children));
+ let compr = ctx.compress(&quad).unwrap();
+ Node { depth, compr, data: quad }
}
pub fn new_cached(compr: B, depth: usize) -> Self {
@@ -82,9 +88,54 @@ impl<A: Default, B: Copy> Node<A, B> {
}
}
+ fn build_square(
+ ctx: &mut Ctx<A, B>,
+ square: &[A],
+ abs_size: usize,
+ depth: usize,
+ x: isize,
+ y: isize,
+ ) -> Node<A, B> {
+ if depth == 0 {
+ let abs_x = (x + (abs_size / 2) as isize) as usize;
+ let abs_y = (y + (abs_size / 2) as isize) as usize;
+ let idx = abs_y * abs_size + abs_x;
+ Self::new_base(ctx, square[idx])
+ } else {
+ let size = 1 << depth;
+ let half = size / 2;
+ // in a z-like pattern
+ let children = [
+ Self::build_square(ctx, square, abs_size, depth - 1, x + half, y ),
+ Self::build_square(ctx, square, abs_size, depth - 1, x , y ),
+ Self::build_square(ctx, square, abs_size, depth - 1, x + half, y + half),
+ Self::build_square(ctx, square, abs_size, depth - 1, x , y + half),
+ ];
+ Self::new_node(ctx, children)
+ }
+ }
+
+ pub fn new_from_square(ctx: &mut Ctx<A, B>, square: Vec<A>) -> Self {
+ // get the side length, ensure this is a pow2 square
+ let area = square.len();
+ let size = ((area as f64).sqrt() + 0.5) as usize;
+ dbg!(size);
+ assert!(size.is_power_of_two());
+ assert!(size * size == area);
+
+ // Takes the log2 of the number
+ // Power of two, so `size - 1` is all ones
+ let depth: usize = (size - 1).trailing_ones() as usize;
+ let half = (size / 2) as isize;
+
+ // Start in lower-left corner (half, half),
+ // build up and out recursively
+ Self::build_square(ctx, &square, size, depth, -half, -half)
+ }
+
/// Creates a new node double the size by centering the current node
/// on a node double the size.
- pub fn pad_empty(self, ctx: &mut Ctx) -> Self {
+ pub fn pad_empty(self, ctx: &mut Ctx<A, B>) -> Self {
todo!()
}
}
diff --git a/src/step.rs b/src/step.rs
index 1256688..7010bd9 100644
--- a/src/step.rs
+++ b/src/step.rs
@@ -1,7 +1,7 @@
use crate::ctx::Ctx;
-use crate::quad::Node;
+use crate::quad::{Node, Embed};
-pub fn step<A: Default, B: Copy>(ctx: &mut Ctx, node: Node<A, B>) -> Node<A, B> {
+pub fn step<A: Embed, B: Embed>(ctx: &mut Ctx<A, B>, node: Node<A, B>) -> Node<A, B> {
// pad the graph if needed.
// if we're at the base, run the cellular automation rule:
--
cgit v1.2.3