13 files changed, 1046 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/1.svg b/1.svg
new file mode 100644
index 0000000..5ca96b9
--- /dev/null
+++ b/1.svg
@@ -0,0 +1,81 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 9.0.0 (0)
+ -->
+<!-- Title: DCEL Pages: 1 -->
+<svg width="53pt" height="192pt"
+ viewBox="0.00 0.00 52.90 192.03" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 188.03)">
+<title>DCEL</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-188.03 48.9,-188.03 48.9,4 -4,4"/>
+<!-- 0 -->
+<g id="node1" class="node">
+<title>0</title>
+<ellipse fill="none" stroke="black" cx="22.15" cy="-166.03" rx="18" ry="18"/>
+<text text-anchor="middle" x="22.15" y="-160.98" font-family="Times,serif" font-size="14.00">0</text>
+</g>
+<!-- edge_0 -->
+<g id="node3" class="node">
+<title>edge_0</title>
+<ellipse fill="black" stroke="black" cx="1.15" cy="-95.17" rx="0.36" ry="0.36"/>
+</g>
+<!-- 0&#45;&gt;edge_0 -->
+<g id="edge1" class="edge">
+<title>0&#45;&gt;edge_0</title>
+<path fill="none" stroke="black" d="M17.18,-148.56C11.36,-129.29 2.37,-99.54 1.27,-95.9"/>
+<text text-anchor="middle" x="14.53" y="-116.73" font-family="Times,serif" font-size="14.00">0</text>
+</g>
+<!-- 1 -->
+<g id="node2" class="node">
+<title>1</title>
+<ellipse fill="none" stroke="black" cx="21.15" cy="-21.15" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="21.15" y="-16.1" font-family="Times,serif" font-size="14.00">far</text>
+</g>
+<!-- edge_1 -->
+<g id="node4" class="node">
+<title>edge_1</title>
+<ellipse fill="black" stroke="black" cx="43.15" cy="-95.17" rx="0.36" ry="0.36"/>
+</g>
+<!-- 1&#45;&gt;edge_1 -->
+<g id="edge3" class="edge">
+<title>1&#45;&gt;edge_1</title>
+<path fill="none" stroke="black" d="M27.13,-41.89C33.18,-61.87 41.81,-90.38 43.01,-94.35"/>
+<text text-anchor="middle" x="41.53" y="-63.51" font-family="Times,serif" font-size="14.00">1</text>
+</g>
+<!-- edge_0&#45;&gt;1 -->
+<g id="edge2" class="edge">
+<title>edge_0&#45;&gt;1</title>
+<path fill="none" stroke="black" d="M1.28,-94.35C2.19,-91.06 7.72,-70.95 12.72,-52.78"/>
+<polygon fill="black" stroke="black" points="16.04,-53.92 15.32,-43.35 9.29,-52.06 16.04,-53.92"/>
+</g>
+<!-- edge_0&#45;&gt;edge_1 -->
+<g id="edge5" class="edge">
+<title>edge_0&#45;&gt;edge_1</title>
+<path fill="none" stroke="red" d="M13.27,-95.17C18.92,-95.17 25.62,-95.17 31.24,-95.17"/>
+<polygon fill="red" stroke="red" points="13.4,-91.67 3.4,-95.17 13.4,-98.67 13.4,-91.67"/>
+<polygon fill="red" stroke="red" points="31.24,-98.67 41.24,-95.17 31.24,-91.67 31.24,-98.67"/>
+<text text-anchor="middle" x="22.15" y="-101.37" font-family="Times,serif" font-size="14.00">twin</text>
+</g>
+<!-- edge_0&#45;&gt;edge_1 -->
+<g id="edge6" class="edge">
+<title>edge_0&#45;&gt;edge_1</title>
+<path fill="none" stroke="green" d="M1.22,-94.54C1.57,-91.72 3.41,-80.15 10.53,-75.67 19.28,-70.17 25.03,-70.17 33.78,-75.67 36.67,-77.49 38.69,-80.48 40.1,-83.58"/>
+<polygon fill="green" stroke="green" points="36.68,-84.35 42.69,-93.08 43.44,-82.51 36.68,-84.35"/>
+<text text-anchor="middle" x="22.15" y="-78.87" font-family="Times,serif" font-size="14.00">next</text>
+</g>
+<!-- edge_1&#45;&gt;0 -->
+<g id="edge4" class="edge">
+<title>edge_1&#45;&gt;0</title>
+<path fill="none" stroke="black" d="M43.04,-95.9C42.14,-98.9 35.87,-119.64 30.44,-137.63"/>
+<polygon fill="black" stroke="black" points="27.11,-136.53 27.57,-147.11 33.81,-138.55 27.11,-136.53"/>
+</g>
+<!-- edge_1&#45;&gt;edge_0 -->
+<g id="edge7" class="edge">
+<title>edge_1&#45;&gt;edge_0</title>
+<path fill="none" stroke="green" d="M43.1,-95.8C42.8,-98.61 41.19,-110.17 34.15,-114.67 25.17,-120.42 19.14,-120.42 10.15,-114.67 7.3,-112.84 5.33,-109.85 3.99,-106.75"/>
+<polygon fill="green" stroke="green" points="7.43,-106.1 1.58,-97.26 0.65,-107.82 7.43,-106.1"/>
+<text text-anchor="middle" x="22.15" y="-123.87" font-family="Times,serif" font-size="14.00">next</text>
+</g>
+</g>
+</svg>
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..3ca3525
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,137 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "autocfg"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
+
+[[package]]
+name = "byteorder"
+version = "1.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "dcel"
+version = "0.1.0"
+dependencies = [
+ "either",
+ "ghost-cell",
+ "rand",
+ "stl_io",
+ "typed-arena",
+]
+
+[[package]]
+name = "either"
+version = "1.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07"
+
+[[package]]
+name = "float-cmp"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "98de4bbd547a563b716d8dfa9aad1cb19bfab00f4fa09a6a4ed21dbcf44ce9c4"
+dependencies = [
+ "num-traits",
+]
+
+[[package]]
+name = "getrandom"
+version = "0.2.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "190092ea657667030ac6a35e305e62fc4dd69fd98ac98631e5d3a2b1575a12b5"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
+name = "ghost-cell"
+version = "0.2.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a5fdd3f2182d5fad2c97a25af8992c30e844a775f8fc7339dae5328377d164e6"
+
+[[package]]
+name = "libc"
+version = "0.2.152"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "13e3bf6590cbc649f4d1a3eefc9d5d6eb746f5200ffb04e5e142700b8faa56e7"
+
+[[package]]
+name = "num-traits"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "39e3200413f237f41ab11ad6d161bc7239c84dcb631773ccd7de3dfe4b5c267c"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
+
+[[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
+name = "stl_io"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d520eb03e632e666ac32f3c0cf018ac6dcd535ab0be1420937e2d896f44f7cf7"
+dependencies = [
+ "byteorder",
+ "float-cmp",
+]
+
+[[package]]
+name = "typed-arena"
+version = "2.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6af6ae20167a9ece4bcb41af5b80f8a1f1df981f6391189ce00fd257af04126a"
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..cdeda6f
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,13 @@
+[package]
+name = "dcel"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+either = "1.9.0"
+ghost-cell = "0.2.3"
+rand = "0.8.5"
+stl_io = "0.7.0"
+typed-arena = "2.0.2"
diff --git a/Utah teapot (solid) - 852078.zip b/Utah teapot (solid) - 852078.zip
new file mode 100644
index 0000000..ebf89fb
--- /dev/null
+++ b/Utah teapot (solid) - 852078.zip
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..960c334
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,545 @@
+#![allow(unused)]
+// the cell! macro will expand to complex types but makes things easier to read for humans
+// unlike type definitions, a macro can capture the 'brand and 'arena lifetimes from the scope
+#![allow(clippy::type_complexity)]
+
+use either::Either::{self, *};
+use ghost_cell::{GhostBorrow, GhostCell, GhostToken};
+use typed_arena::Arena;
+
+type Id = Option<usize>;
+
+// trait for a kind of topological element (i.e. Vertex, HalfEdge, Face)
+trait Kind {
+    type Init;
+
+    fn new(id: usize, init: Self::Init) -> Self;
+
+    fn is_alive(&self) -> bool {
+        self.get_id().is_some()
+    }
+
+    fn get_id(&self) -> Id;
+    fn clear(&mut self);
+}
+
+macro_rules! cell_t {
+	($T:ty) => {
+		&'arena GhostCell<'brand, $T>
+	}
+}
+
+macro_rules! cell {
+	($T:ident) => {
+		&'arena GhostCell<'brand, $T<'brand, 'arena, V>>
+	};
+}
+
+macro_rules! impl_kind {
+	($T:ident, $init_name:ident: $init_ty:ty $(, $($init_field:ident : $init_expr:tt),* )? $(; $($fields:ident),*)?) => {
+		impl<'brand, 'arena, V> Kind for $T<'brand, 'arena, V> {
+			type Init = $init_ty;
+
+			fn get_id(&self) -> Id {
+				self.id
+			}
+
+			fn new(id: usize, $init_name: $init_ty) -> Self {
+				Self {
+					id: Some(id),
+					$($($init_field: $init_expr,)*)?
+					$($($fields: Default::default(),)*)?
+				}
+			}
+
+			fn clear(&mut self) {
+				self.id = Default::default();
+				#[cfg(debug_assertions)]
+				{ $($(self.$fields = Default::default();)*)? }
+			}
+		}
+
+		impl<'brand, 'arena, V: Default> PartialEq for $T<'brand, 'arena, V> {
+			fn eq(&self, other: &Self) -> bool {
+				self.get_id() == other.get_id()
+			}
+		}
+		impl<'brand, 'arena, V: Default> Eq for $T<'brand, 'arena, V> {}
+	};
+}
+
+use std::fmt;
+
+trait DcelDebug<'brand> {
+    fn fmt(
+        &self,
+        long: bool,
+        token: &GhostToken<'brand>,
+        f: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error>;
+}
+
+macro_rules! impl_debug {
+    ($T:ty) => {
+        impl<'brand> DcelDebug<'brand> for $T {
+            fn fmt(
+                &self,
+                long: bool,
+                token: &GhostToken<'brand>,
+                f: &mut fmt::Formatter<'_>,
+            ) -> Result<(), fmt::Error> {
+                fmt::Debug::fmt(self, f)?;
+                writeln!(f, "")
+            }
+        }
+    };
+}
+
+impl<'brand, T: DcelDebug<'brand>> DcelDebug<'brand> for Option<T> {
+    fn fmt(
+        &self,
+        long: bool,
+        token: &GhostToken<'brand>,
+        f: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        match self {
+            None => write!(f, "None"),
+            Some(x) => DcelDebug::fmt(x, long, token, f),
+        }
+    }
+}
+
+macro_rules! impl_kind_debug {
+	($T:ident $(, $($fields:ident),*)?) => {
+		impl<'brand, 'arena, V> DcelDebug<'brand> for &'arena GhostCell<'brand, $T<'brand, 'arena, V>> where V: DcelDebug<'brand> {
+			fn fmt(
+				&self,
+				long: bool,
+				token: &GhostToken<'brand>,
+				f: &mut fmt::Formatter<'_>,
+			) -> Result<(), fmt::Error> {
+				writeln!(f, "{} {:?}", stringify!($T), self.borrow(token).id)?;
+
+				if long {
+					$($(
+						write!(f, "\t{} = ", stringify!($fields))?;
+						DcelDebug::fmt(&self.borrow(token).$fields, false, token, f)?;
+					)*)?
+				}
+
+				Ok(())
+			}
+		}
+	};
+}
+
+// responsible for allocation of a certain Kind
+struct Container<'brand, 'arena, T: Kind> {
+    next_id: usize,
+    arena: &'arena Arena<T>,
+    elements: Vec<cell_t!(T)>,
+    freelist: Vec<cell_t!(T)>,
+}
+
+impl<'brand, 'arena, T: Kind> Container<'brand, 'arena, T> {
+    fn new(arena: &'arena Arena<T>) -> Self {
+        Self {
+            next_id: 0,
+            arena,
+            elements: Vec::new(),
+            freelist: Vec::new(),
+        }
+    }
+
+    fn alloc(
+        &mut self,
+        token: &mut GhostToken<'brand>,
+        init: T::Init, /*f: impl FnOnce(Id) -> T*/
+    ) -> cell_t!(T) {
+        let id = self.next_id;
+        self.next_id += 1;
+
+        let t = Kind::new(id, init);
+
+        if let Some(cell) = self.freelist.pop() {
+            *cell.borrow_mut(token) = t;
+            cell
+        } else {
+            let cell = GhostCell::from_mut(self.arena.alloc(t));
+            self.elements.push(cell);
+            cell
+        }
+    }
+
+    fn free(&mut self, token: &mut GhostToken<'brand>, cell: cell_t!(T)) {
+        debug_assert!(!cell.borrow(token).is_alive(), "double free");
+        cell.borrow_mut(token).clear();
+        self.freelist.push(cell);
+    }
+}
+
+#[derive(Default)]
+struct DcelAllocator<'brand, 'arena, V> {
+    edge: Arena<HalfEdge<'brand, 'arena, V>>,
+    vertex: Arena<Vertex<'brand, 'arena, V>>,
+    face: Arena<Face<'brand, 'arena, V>>,
+}
+
+struct Dcel<'brand, 'arena, V: Default> {
+    token: GhostToken<'brand>,
+    half_edges: Container<'brand, 'arena, HalfEdge<'brand, 'arena, V>>,
+    vertices: Container<'brand, 'arena, Vertex<'brand, 'arena, V>>,
+    faces: Container<'brand, 'arena, Face<'brand, 'arena, V>>,
+}
+
+struct Vertex<'brand, 'arena, V> {
+    id: Id,
+    data: V,
+    outgoing: Option<cell!(HalfEdge)>,
+}
+//type VertexRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Vertex<'brand, 'arena, V>>;
+impl_kind!(Vertex, init: V, data: init; outgoing);
+impl_kind_debug!(Vertex, data, outgoing);
+
+struct HalfEdge<'brand, 'arena, V> {
+    id: Id,
+    next: Option<cell!(HalfEdge)>,
+    origin: Option<cell!(Vertex)>,
+    twin: Option<cell!(HalfEdge)>,
+    face: Option<cell!(Face)>,
+    prev: Option<cell!(HalfEdge)>,
+}
+//type HalfEdgeRef<'brand, 'arena, V> = &'arena GhostCell<'brand, HalfEdge<'brand, 'arena, V>>;
+impl_kind!(HalfEdge, init: (); origin, twin, face, next, prev);
+impl_kind_debug!(HalfEdge, origin, twin, face, next, prev);
+
+/*
+struct FaceL<'brand, 'arena, V> {
+    id: Id,
+    outer: Vec<cell!(Loop)>,
+    inner: Vec<cell!(Loop)>,
+    solid: Option<cell!(Solid)>,
+}
+
+struct Solid<'brand, 'arena, V> {
+    id: Id,
+    faces: Vec<cell!(Faces)>,
+    half_edges: Vec<cell!(HalfEdge)>,
+}*/
+
+struct Face<'brand, 'arena, V> {
+    id: Id,
+    outer: Vec<cell!(HalfEdge)>,
+    inner: Vec<cell!(HalfEdge)>,
+}
+//type FaceRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Face<'brand, 'arena, V>>;
+impl_kind!(Face, init: (); outer, inner);
+impl_kind_debug!(Face);
+
+impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> {
+    fn new(token: GhostToken<'brand>, alloc: &'arena DcelAllocator<'brand, 'arena, V>) -> Self {
+        Self {
+            token,
+            half_edges: Container::new(&alloc.edge),
+            vertices: Container::new(&alloc.vertex),
+            faces: Container::new(&alloc.face),
+        }
+    }
+
+    pub fn mvsf(&mut self, data: V) -> (cell!(Vertex), cell!(Face)) {
+        let f = self.faces.alloc(&mut self.token, ());
+        let v = self.vertices.alloc(&mut self.token, data);
+
+        (v, f)
+    }
+
+    pub fn mevvls(&mut self, data: [V; 2]) -> (cell!(HalfEdge), [cell!(Vertex); 2], cell!(Face)) {
+        let [d1, d2] = data;
+
+        let l = self.faces.alloc(&mut self.token, ());
+        let v1 = self.vertices.alloc(&mut self.token, d1);
+        let v2 = self.vertices.alloc(&mut self.token, d2);
+        let a = self.half_edges.alloc(&mut self.token, ());
+        let b = self.half_edges.alloc(&mut self.token, ());
+
+        self.twin(a, b);
+        self.follow(a, b);
+        self.follow(b, a);
+        self.origin(v1, a);
+        self.origin(v2, b);
+
+        (a, [v1, v2], l)
+    }
+
+    #[inline(always)]
+    fn twin(&mut self, a: cell!(HalfEdge), b: cell!(HalfEdge)) {
+        a.borrow_mut(&mut self.token).twin = Some(b);
+        b.borrow_mut(&mut self.token).twin = Some(a);
+    }
+
+    #[inline(always)]
+    fn origin(&mut self, v: cell!(Vertex), h: cell!(HalfEdge)) {
+        v.borrow_mut(&mut self.token).outgoing = Some(h);
+        h.borrow_mut(&mut self.token).origin = Some(v);
+    }
+
+    #[inline(always)]
+    fn follow(&mut self, prev: cell!(HalfEdge), next: cell!(HalfEdge)) {
+        next.borrow_mut(&mut self.token).prev = Some(prev);
+        prev.borrow_mut(&mut self.token).next = Some(next);
+    }
+
+    pub fn mve(
+        &mut self,
+        edge: cell!(HalfEdge),
+        data: V,
+    ) -> Option<(cell!(HalfEdge), cell!(Vertex))> {
+        // before:
+        //
+        //            fa
+        //                       / a3
+        //          a1 ->
+        // v1         v         v2
+        //          <- b1
+        //                       \ b3
+        //            fb
+        //
+        // after:
+        //
+        //            fa
+        //                       / a3
+        //     a1 ->     a2 ->
+        // v1         v         v2
+        //     <- b1     <- b2
+        //                       \ b3
+        //            fb
+
+        let v = self.vertices.alloc(&mut self.token, data);
+        let a2 = self.half_edges.alloc(&mut self.token, ());
+        let b2 = self.half_edges.alloc(&mut self.token, ());
+
+        let a1 = edge;
+        let v1 = a1.borrow(&self.token).origin?;
+        //let fa = a1.borrow(&self.token).face?;
+
+        let b1 = a1.borrow(&self.token).twin?;
+        let v2 = b1.borrow(&self.token).origin?;
+        //let fb = b1.borrow(&self.token).face?;
+
+        let mut a3 = a1.borrow(&self.token).next?;
+        if a3.borrow(&self.token) == b1.borrow(&self.token) {
+            a3 = b2;
+        }
+
+        let mut b3 = b1.borrow(&self.token).prev?;
+        if b3.borrow(&self.token) == a1.borrow(&self.token) {
+            b3 = a2;
+        }
+
+        self.twin(a2, b2);
+
+        self.origin(v, a2);
+        self.origin(v, b1);
+        self.origin(v2, b2);
+
+        self.follow(a1, a2);
+        self.follow(a2, a3);
+
+        self.follow(b3, b2);
+        self.follow(b2, b1);
+
+        Some((a1, v))
+    }
+
+    pub fn mel(&mut self, v1: cell!(Vertex), v2: cell!(Vertex)) -> Option<()> {
+        Some(())
+    }
+
+    fn mev(
+        &mut self,
+        from: cell!(Vertex),
+        data: V,
+    ) -> (cell!(Vertex), cell!(HalfEdge), cell!(HalfEdge)) {
+        let v = self.vertices.alloc(&mut self.token, data);
+        let a = self.half_edges.alloc(&mut self.token, ());
+        let b = self.half_edges.alloc(&mut self.token, ());
+
+        self.twin(a, b);
+
+        self.origin(v, a);
+        self.origin(from, b);
+
+        self.follow(a, b);
+        self.follow(b, a);
+
+        (v, a, b)
+    }
+}
+
+struct DcelDotOptions {
+    pub twin: bool,
+    pub next: bool,
+    pub prev: bool,
+}
+
+impl DcelDotOptions {
+    fn none() -> Self {
+        Self {
+            twin: false,
+            next: false,
+            prev: false,
+        }
+    }
+
+    fn all() -> Self {
+        Self {
+            twin: true,
+            next: true,
+            prev: true,
+        }
+    }
+}
+
+fn dcel_write_dot(
+    dcel: &Dcel<(&'static str, [i64; 2])>,
+    f: &mut fmt::Formatter<'_>,
+    opt: DcelDotOptions,
+) -> fmt::Result {
+    use rand::Rng;
+    use std::collections::HashSet;
+
+    writeln!(f, "digraph DCEL {{")?;
+    writeln!(f, "node [shape = circle]")?;
+    //writeln!(f, "nodesep = 1")?;
+
+    let mut rank = Vec::new();
+
+    for v in dcel.vertices.elements.iter() {
+        let v = v.borrow(&dcel.token);
+        if let Some(id) = v.id {
+            // writeln!(f, "\t{id} [pos=\"{},{}!\"]", v.data.0, v.data.1)?;
+            writeln!(
+                f,
+                "{id} [label=\"{}\", pos=\"{},{}!\"]",
+                v.data.0, v.data.1[0], v.data.1[1]
+            );
+            rank.push(id);
+        }
+    }
+
+    /*
+    write!(f, "{{ rank=same; ")?;
+    for r in rank {
+        write!(f, "{r}; ")?;
+    }
+    writeln!(f, "}}");*/
+
+    for h in dcel.half_edges.elements.iter() {
+        let h = h.borrow(&dcel.token);
+        if let Some(id) = h.id {
+            let twin = h.twin.unwrap().borrow(&dcel.token);
+            let twin_id = twin.id.unwrap();
+
+            let a_v = h.origin.unwrap().borrow(&dcel.token);
+            let b_v = twin.origin.unwrap().borrow(&dcel.token);
+
+            let mut vec = [
+                -(b_v.data.1[1] - a_v.data.1[1]) as f64,
+                (b_v.data.1[0] - a_v.data.1[0]) as f64,
+            ];
+
+            let len = (vec[0] * vec[0] + vec[1] * vec[1]).sqrt();
+            vec[0] *= 0.2 / len;
+            vec[1] *= 0.2 / len;
+
+            let mid = [
+                (a_v.data.1[0] + b_v.data.1[0]) as f64 / 2.0 + vec[0],
+                (a_v.data.1[1] + b_v.data.1[1]) as f64 / 2.0 + vec[1],
+            ];
+
+            let a = a_v.id.unwrap();
+            let b = b_v.id.unwrap();
+
+            writeln!(
+                f,
+                "edge_{id} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]",
+                mid[0], mid[1]
+            )?;
+            writeln!(f, "{a} -> edge_{id} [arrowhead=none]")?;
+            writeln!(f, "edge_{id} -> {b} [label=\"{id}\"]")?;
+
+            if opt.twin {
+                writeln!(f, "edge_{id} -> edge_{twin_id} [color=\"red\"]")?;
+            }
+
+            if opt.next {
+                writeln!(
+                    f,
+                    "edge_{id} -> edge_{} [color=\"green\"]",
+                    h.next.unwrap().borrow(&dcel.token).id.unwrap()
+                )?;
+            }
+
+            if opt.prev {
+                writeln!(
+                    f,
+                    "edge_{id} -> edge_{} [color=\"blue\"]",
+                    h.prev.unwrap().borrow(&dcel.token).id.unwrap()
+                )?;
+            }
+        }
+    }
+
+    writeln!(f, "}}")
+}
+
+impl_debug!(i32);
+
+struct DisplayFn<T>(T);
+impl<T: Fn(&mut fmt::Formatter<'_>) -> fmt::Result> fmt::Display for DisplayFn<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0(f)
+    }
+}
+
+fn main() {
+    GhostToken::new(|token| {
+        let alloc = DcelAllocator::default();
+        let mut dcel = Dcel::new(token, &alloc);
+
+        let h0 = dcel.mevvls([("S", [0, 0]), ("E", [9, 0])]).0;
+        let h2 = dcel.mve(h0, ("P1", [6, 0])).unwrap().0;
+        dcel.mve(h2, ("P2", [3, 0])).unwrap();
+
+        dcel.mev(h0.borrow(&dcel.token).origin.unwrap(), ("B", [0, 3]));
+
+        print!(
+            "{}",
+            DisplayFn(|f: &mut fmt::Formatter<'_>| dcel_write_dot(
+                &dcel,
+                f,
+                DcelDotOptions {
+                    prev: false,
+                    next: true,
+                    twin: false,
+                }
+            ))
+        );
+
+        /*
+        print!(
+            "{}",
+            DisplayFn(|f: &mut fmt::Formatter<'_>| {
+                for v in dcel.vertices.elements.iter() {
+                    DcelDebug::fmt(v, true, &dcel.token, f)?;
+                }
+
+                for h in dcel.half_edges.elements.iter() {
+                    DcelDebug::fmt(h, true, &dcel.token, f)?;
+                }
+
+                Ok(())
+            })
+        );*/
+    });
+}
diff --git a/utahteapot/LICENSE.txt b/utahteapot/LICENSE.txt
new file mode 100644
index 0000000..7421e49
--- /dev/null
+++ b/utahteapot/LICENSE.txt
@@ -0,0 +1 @@
+This thing was created by Thingiverse user zzubnik, and is licensed under Creative Commons - Public Domain Dedication
\ No newline at end of file
diff --git a/utahteapot/README.txt b/utahteapot/README.txt
new file mode 100644
index 0000000..19d4877
--- /dev/null
+++ b/utahteapot/README.txt
@@ -0,0 +1 @@
+Utah teapot (solid) by zzubnik on Thingiverse: https://www.thingiverse.com/thing:852078
\ No newline at end of file
diff --git a/utahteapot/files/utahteapot.stl b/utahteapot/files/utahteapot.stl
new file mode 100644
index 0000000..d225918
--- /dev/null
+++ b/utahteapot/files/utahteapot.stl
diff --git a/utahteapot/images/teapot_stl.jpg b/utahteapot/images/teapot_stl.jpg
new file mode 100644
index 0000000..1d091f1
--- /dev/null
+++ b/utahteapot/images/teapot_stl.jpg
diff --git a/utahteapot/images/utahteapot.png b/utahteapot/images/utahteapot.png
new file mode 100644
index 0000000..ae8f786
--- /dev/null
+++ b/utahteapot/images/utahteapot.png
diff --git a/x.dot b/x.dot
new file mode 100644
index 0000000..77dea66
--- /dev/null
+++ b/x.dot
@@ -0,0 +1,40 @@
+digraph DCEL {
+node [shape = circle]
+0 [label="S", pos="0,0!"]
+1 [label="E", pos="9,0!"]
+2 [label="P1", pos="6,0!"]
+3 [label="P2", pos="3,0!"]
+4 [label="B", pos="0,3!"]
+edge_0 [pos="1.5,0.2!", shape=point, width=0.01, height=0.01]
+0 -> edge_0 [arrowhead=none]
+edge_0 -> 3 [label="0"]
+edge_0 -> edge_4 [color="green"]
+edge_1 [pos="1.5,-0.2!", shape=point, width=0.01, height=0.01]
+3 -> edge_1 [arrowhead=none]
+edge_1 -> 0 [label="1"]
+edge_1 -> edge_0 [color="green"]
+edge_2 [pos="7.5,0.2!", shape=point, width=0.01, height=0.01]
+2 -> edge_2 [arrowhead=none]
+edge_2 -> 1 [label="2"]
+edge_2 -> edge_3 [color="green"]
+edge_3 [pos="7.5,-0.2!", shape=point, width=0.01, height=0.01]
+1 -> edge_3 [arrowhead=none]
+edge_3 -> 2 [label="3"]
+edge_3 -> edge_5 [color="green"]
+edge_4 [pos="4.5,0.2!", shape=point, width=0.01, height=0.01]
+3 -> edge_4 [arrowhead=none]
+edge_4 -> 2 [label="4"]
+edge_4 -> edge_2 [color="green"]
+edge_5 [pos="4.5,-0.2!", shape=point, width=0.01, height=0.01]
+2 -> edge_5 [arrowhead=none]
+edge_5 -> 3 [label="5"]
+edge_5 -> edge_1 [color="green"]
+edge_6 [pos="0.2,1.5!", shape=point, width=0.01, height=0.01]
+4 -> edge_6 [arrowhead=none]
+edge_6 -> 0 [label="6"]
+edge_6 -> edge_7 [color="green"]
+edge_7 [pos="-0.2,1.5!", shape=point, width=0.01, height=0.01]
+0 -> edge_7 [arrowhead=none]
+edge_7 -> 4 [label="7"]
+edge_7 -> edge_6 [color="green"]
+}
diff --git a/x.svg b/x.svg
new file mode 100644
index 0000000..16f61db
--- /dev/null
+++ b/x.svg
@@ -0,0 +1,227 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 9.0.0 (0)
+ -->
+<!-- Title: DCEL Pages: 1 -->
+<svg width="692pt" height="263pt"
+ viewBox="0.00 0.00 692.00 263.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 259)">
+<title>DCEL</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-259 688,-259 688,4 -4,4"/>
+<!-- 0 -->
+<g id="node1" class="node">
+<title>0</title>
+<ellipse fill="none" stroke="black" cx="18" cy="-21" rx="18" ry="18"/>
+<text text-anchor="middle" x="18" y="-15.95" font-family="Times,serif" font-size="14.00">S</text>
+</g>
+<!-- edge_0 -->
+<g id="node6" class="node">
+<title>edge_0</title>
+<ellipse fill="black" stroke="black" cx="126" cy="-35.4" rx="0.36" ry="0.36"/>
+</g>
+<!-- 0&#45;&gt;edge_0 -->
+<g id="edge1" class="edge">
+<title>0&#45;&gt;edge_0</title>
+<path fill="none" stroke="black" d="M36.32,-23.44C65.21,-27.29 118.75,-34.43 125.33,-35.31"/>
+</g>
+<!-- edge_7 -->
+<g id="node13" class="node">
+<title>edge_7</title>
+<ellipse fill="black" stroke="black" cx="3.6" cy="-129" rx="0.36" ry="0.36"/>
+</g>
+<!-- 0&#45;&gt;edge_7 -->
+<g id="edge22" class="edge">
+<title>0&#45;&gt;edge_7</title>
+<path fill="none" stroke="black" d="M15.56,-39.32C11.71,-68.21 4.57,-121.75 3.69,-128.33"/>
+</g>
+<!-- 1 -->
+<g id="node2" class="node">
+<title>1</title>
+<ellipse fill="none" stroke="black" cx="666" cy="-21" rx="18" ry="18"/>
+<text text-anchor="middle" x="666" y="-15.95" font-family="Times,serif" font-size="14.00">E</text>
+</g>
+<!-- edge_3 -->
+<g id="node10" class="node">
+<title>edge_3</title>
+<ellipse fill="black" stroke="black" cx="558" cy="-6.6" rx="0.36" ry="0.36"/>
+</g>
+<!-- 1&#45;&gt;edge_3 -->
+<g id="edge10" class="edge">
+<title>1&#45;&gt;edge_3</title>
+<path fill="none" stroke="black" d="M647.68,-18.56C618.79,-14.71 565.25,-7.57 558.67,-6.69"/>
+</g>
+<!-- 2 -->
+<g id="node3" class="node">
+<title>2</title>
+<ellipse fill="none" stroke="black" cx="450" cy="-21" rx="20.64" ry="20.64"/>
+<text text-anchor="middle" x="450" y="-15.95" font-family="Times,serif" font-size="14.00">P1</text>
+</g>
+<!-- edge_2 -->
+<g id="node9" class="node">
+<title>edge_2</title>
+<ellipse fill="black" stroke="black" cx="558" cy="-35.4" rx="0.36" ry="0.36"/>
+</g>
+<!-- 2&#45;&gt;edge_2 -->
+<g id="edge7" class="edge">
+<title>2&#45;&gt;edge_2</title>
+<path fill="none" stroke="black" d="M470.82,-23.78C500.25,-27.7 551.12,-34.48 557.37,-35.32"/>
+</g>
+<!-- edge_5 -->
+<g id="node11" class="node">
+<title>edge_5</title>
+<ellipse fill="black" stroke="black" cx="342" cy="-6.6" rx="0.36" ry="0.36"/>
+</g>
+<!-- 2&#45;&gt;edge_5 -->
+<g id="edge16" class="edge">
+<title>2&#45;&gt;edge_5</title>
+<path fill="none" stroke="black" d="M429.18,-18.22C399.75,-14.3 348.88,-7.52 342.63,-6.68"/>
+</g>
+<!-- 3 -->
+<g id="node4" class="node">
+<title>3</title>
+<ellipse fill="none" stroke="black" cx="234" cy="-21" rx="20.64" ry="20.64"/>
+<text text-anchor="middle" x="234" y="-15.95" font-family="Times,serif" font-size="14.00">P2</text>
+</g>
+<!-- edge_4 -->
+<g id="node7" class="node">
+<title>edge_4</title>
+<ellipse fill="black" stroke="black" cx="342" cy="-35.4" rx="0.36" ry="0.36"/>
+</g>
+<!-- 3&#45;&gt;edge_4 -->
+<g id="edge13" class="edge">
+<title>3&#45;&gt;edge_4</title>
+<path fill="none" stroke="black" d="M254.82,-23.78C284.25,-27.7 335.12,-34.48 341.37,-35.32"/>
+</g>
+<!-- edge_1 -->
+<g id="node8" class="node">
+<title>edge_1</title>
+<ellipse fill="black" stroke="black" cx="126" cy="-6.6" rx="0.36" ry="0.36"/>
+</g>
+<!-- 3&#45;&gt;edge_1 -->
+<g id="edge4" class="edge">
+<title>3&#45;&gt;edge_1</title>
+<path fill="none" stroke="black" d="M213.18,-18.22C183.75,-14.3 132.88,-7.52 126.63,-6.68"/>
+</g>
+<!-- 4 -->
+<g id="node5" class="node">
+<title>4</title>
+<ellipse fill="none" stroke="black" cx="18" cy="-237" rx="18" ry="18"/>
+<text text-anchor="middle" x="18" y="-231.95" font-family="Times,serif" font-size="14.00">B</text>
+</g>
+<!-- edge_6 -->
+<g id="node12" class="node">
+<title>edge_6</title>
+<ellipse fill="black" stroke="black" cx="32.4" cy="-129" rx="0.36" ry="0.36"/>
+</g>
+<!-- 4&#45;&gt;edge_6 -->
+<g id="edge19" class="edge">
+<title>4&#45;&gt;edge_6</title>
+<path fill="none" stroke="black" d="M20.44,-218.68C24.29,-189.79 31.43,-136.25 32.31,-129.67"/>
+</g>
+<!-- edge_0&#45;&gt;3 -->
+<g id="edge2" class="edge">
+<title>edge_0&#45;&gt;3</title>
+<path fill="none" stroke="black" d="M126.69,-35.31C132.43,-34.54 172.81,-29.16 202.35,-25.22"/>
+<polygon fill="black" stroke="black" points="202.49,-28.73 211.94,-23.94 201.56,-21.79 202.49,-28.73"/>
+<text text-anchor="middle" x="161.15" y="-33.46" font-family="Times,serif" font-size="14.00">0</text>
+</g>
+<!-- edge_0&#45;&gt;edge_4 -->
+<g id="edge3" class="edge">
+<title>edge_0&#45;&gt;edge_4</title>
+<path fill="none" stroke="green" d="M126.62,-35.4C137.43,-35.4 286.63,-35.4 330.16,-35.4"/>
+<polygon fill="green" stroke="green" points="329.9,-38.9 339.9,-35.4 329.9,-31.9 329.9,-38.9"/>
+</g>
+<!-- edge_4&#45;&gt;2 -->
+<g id="edge14" class="edge">
+<title>edge_4&#45;&gt;2</title>
+<path fill="none" stroke="black" d="M342.69,-35.31C348.43,-34.54 388.81,-29.16 418.35,-25.22"/>
+<polygon fill="black" stroke="black" points="418.49,-28.73 427.94,-23.94 417.56,-21.79 418.49,-28.73"/>
+<text text-anchor="middle" x="377.15" y="-33.46" font-family="Times,serif" font-size="14.00">4</text>
+</g>
+<!-- edge_4&#45;&gt;edge_2 -->
+<g id="edge15" class="edge">
+<title>edge_4&#45;&gt;edge_2</title>
+<path fill="none" stroke="green" d="M342.62,-35.4C353.43,-35.4 502.63,-35.4 546.16,-35.4"/>
+<polygon fill="green" stroke="green" points="545.9,-38.9 555.9,-35.4 545.9,-31.9 545.9,-38.9"/>
+</g>
+<!-- edge_1&#45;&gt;0 -->
+<g id="edge5" class="edge">
+<title>edge_1&#45;&gt;0</title>
+<path fill="none" stroke="black" d="M125.31,-6.69C119.41,-7.48 76.93,-13.14 47.22,-17.1"/>
+<polygon fill="black" stroke="black" points="47.13,-13.58 37.68,-18.38 48.06,-20.52 47.13,-13.58"/>
+<text text-anchor="middle" x="82.89" y="-15.1" font-family="Times,serif" font-size="14.00">1</text>
+</g>
+<!-- edge_1&#45;&gt;edge_0 -->
+<g id="edge6" class="edge">
+<title>edge_1&#45;&gt;edge_0</title>
+<path fill="none" stroke="green" d="M126,-7.31C126,-9.57 126,-16.83 126,-23.4"/>
+<polygon fill="green" stroke="green" points="122.5,-23.3 126,-33.3 129.5,-23.3 122.5,-23.3"/>
+</g>
+<!-- edge_2&#45;&gt;1 -->
+<g id="edge8" class="edge">
+<title>edge_2&#45;&gt;1</title>
+<path fill="none" stroke="black" d="M558.69,-35.31C564.59,-34.52 607.07,-28.86 636.78,-24.9"/>
+<polygon fill="black" stroke="black" points="636.87,-28.42 646.32,-23.62 635.94,-21.48 636.87,-28.42"/>
+<text text-anchor="middle" x="594.36" y="-33.3" font-family="Times,serif" font-size="14.00">2</text>
+</g>
+<!-- edge_2&#45;&gt;edge_3 -->
+<g id="edge9" class="edge">
+<title>edge_2&#45;&gt;edge_3</title>
+<path fill="none" stroke="green" d="M558,-34.69C558,-32.43 558,-25.17 558,-18.6"/>
+<polygon fill="green" stroke="green" points="561.5,-18.7 558,-8.7 554.5,-18.7 561.5,-18.7"/>
+</g>
+<!-- edge_3&#45;&gt;2 -->
+<g id="edge11" class="edge">
+<title>edge_3&#45;&gt;2</title>
+<path fill="none" stroke="black" d="M557.31,-6.69C551.57,-7.46 511.19,-12.84 481.65,-16.78"/>
+<polygon fill="black" stroke="black" points="481.51,-13.27 472.06,-18.06 482.44,-20.21 481.51,-13.27"/>
+<text text-anchor="middle" x="516.1" y="-14.94" font-family="Times,serif" font-size="14.00">3</text>
+</g>
+<!-- edge_3&#45;&gt;edge_5 -->
+<g id="edge12" class="edge">
+<title>edge_3&#45;&gt;edge_5</title>
+<path fill="none" stroke="green" d="M557.38,-6.6C546.57,-6.6 397.37,-6.6 353.84,-6.6"/>
+<polygon fill="green" stroke="green" points="354.1,-3.1 344.1,-6.6 354.1,-10.1 354.1,-3.1"/>
+</g>
+<!-- edge_5&#45;&gt;3 -->
+<g id="edge17" class="edge">
+<title>edge_5&#45;&gt;3</title>
+<path fill="none" stroke="black" d="M341.31,-6.69C335.57,-7.46 295.19,-12.84 265.65,-16.78"/>
+<polygon fill="black" stroke="black" points="265.51,-13.27 256.06,-18.06 266.44,-20.21 265.51,-13.27"/>
+<text text-anchor="middle" x="300.1" y="-14.94" font-family="Times,serif" font-size="14.00">5</text>
+</g>
+<!-- edge_5&#45;&gt;edge_1 -->
+<g id="edge18" class="edge">
+<title>edge_5&#45;&gt;edge_1</title>
+<path fill="none" stroke="green" d="M341.38,-6.6C330.57,-6.6 181.37,-6.6 137.84,-6.6"/>
+<polygon fill="green" stroke="green" points="138.1,-3.1 128.1,-6.6 138.1,-10.1 138.1,-3.1"/>
+</g>
+<!-- edge_6&#45;&gt;0 -->
+<g id="edge20" class="edge">
+<title>edge_6&#45;&gt;0</title>
+<path fill="none" stroke="black" d="M32.31,-128.31C31.52,-122.41 25.86,-79.93 21.9,-50.22"/>
+<polygon fill="black" stroke="black" points="25.42,-50.13 20.62,-40.68 18.48,-51.06 25.42,-50.13"/>
+<text text-anchor="middle" x="23.73" y="-92.47" font-family="Times,serif" font-size="14.00">6</text>
+</g>
+<!-- edge_6&#45;&gt;edge_7 -->
+<g id="edge21" class="edge">
+<title>edge_6&#45;&gt;edge_7</title>
+<path fill="none" stroke="green" d="M32.32,-128.18C31.32,-123.36 21.49,-121.48 13.61,-122.54"/>
+<polygon fill="green" stroke="green" points="11.94,-119.46 4.99,-127.46 15.41,-125.54 11.94,-119.46"/>
+</g>
+<!-- edge_7&#45;&gt;4 -->
+<g id="edge23" class="edge">
+<title>edge_7&#45;&gt;4</title>
+<path fill="none" stroke="black" d="M3.69,-129.69C4.48,-135.59 10.14,-178.07 14.1,-207.78"/>
+<polygon fill="black" stroke="black" points="10.58,-207.87 15.38,-217.32 17.52,-206.94 10.58,-207.87"/>
+<text text-anchor="middle" x="5.52" y="-171.93" font-family="Times,serif" font-size="14.00">7</text>
+</g>
+<!-- edge_7&#45;&gt;edge_6 -->
+<g id="edge24" class="edge">
+<title>edge_7&#45;&gt;edge_6</title>
+<path fill="none" stroke="green" d="M3.68,-129.82C4.68,-134.64 14.51,-136.52 22.39,-135.46"/>
+<polygon fill="green" stroke="green" points="24.06,-138.54 31.01,-130.54 20.59,-132.46 24.06,-138.54"/>
+</g>
+</g>
+</svg>