From ed18e4642d463658ff03f4dae4cfe644adce601a Mon Sep 17 00:00:00 2001 From: Charlotte Pabst Date: Thu, 18 Jan 2024 03:22:49 +0100 Subject: --- .gitignore | 3 + 1.svg | 81 -------------- Cargo.lock | 7 ++ Cargo.toml | 1 + Utah teapot (solid) - 852078.zip | Bin 917444 -> 0 bytes conv.sh | 8 ++ src/main.rs | 191 ++++++++++++++++++++------------ utahteapot/LICENSE.txt | 1 - utahteapot/README.txt | 1 - utahteapot/files/utahteapot.stl | Bin 471984 -> 0 bytes utahteapot/images/teapot_stl.jpg | Bin 194795 -> 0 bytes utahteapot/images/utahteapot.png | Bin 249715 -> 0 bytes x.dot | 40 ------- x.svg | 227 --------------------------------------- 14 files changed, 143 insertions(+), 417 deletions(-) delete mode 100644 1.svg delete mode 100644 Utah teapot (solid) - 852078.zip create mode 100755 conv.sh delete mode 100644 utahteapot/LICENSE.txt delete mode 100644 utahteapot/README.txt delete mode 100644 utahteapot/files/utahteapot.stl delete mode 100644 utahteapot/images/teapot_stl.jpg delete mode 100644 utahteapot/images/utahteapot.png delete mode 100644 x.dot delete mode 100644 x.svg diff --git a/.gitignore b/.gitignore index ea8c4bf..20df3bf 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,4 @@ /target +*.png +*.dot +*.gif diff --git a/1.svg b/1.svg deleted file mode 100644 index 5ca96b9..0000000 --- a/1.svg +++ /dev/null @@ -1,81 +0,0 @@ - - - - - - -DCEL - - - -0 - -0 - - - -edge_0 - - - - -0->edge_0 - -0 - - - -1 - -far - - - -edge_1 - - - - -1->edge_1 - -1 - - - -edge_0->1 - - - - - -edge_0->edge_1 - - - -twin - - - -edge_0->edge_1 - - -next - - - -edge_1->0 - - - - - -edge_1->edge_0 - - -next - - - diff --git a/Cargo.lock b/Cargo.lock index 3ca3525..c55db32 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2,6 +2,12 @@ # It is not intended for manual editing. version = 3 +[[package]] +name = "anyhow" +version = "1.0.79" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "080e9890a082662b09c1ad45f567faeeb47f22b5fb23895fbe1e651e718e25ca" + [[package]] name = "autocfg" version = "1.1.0" @@ -24,6 +30,7 @@ checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" name = "dcel" version = "0.1.0" dependencies = [ + "anyhow", "either", "ghost-cell", "rand", diff --git a/Cargo.toml b/Cargo.toml index cdeda6f..9fa1245 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -6,6 +6,7 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] +anyhow = "1.0.79" either = "1.9.0" ghost-cell = "0.2.3" rand = "0.8.5" diff --git a/Utah teapot (solid) - 852078.zip b/Utah teapot (solid) - 852078.zip deleted file mode 100644 index ebf89fb..0000000 Binary files a/Utah teapot (solid) - 852078.zip and /dev/null differ diff --git a/conv.sh b/conv.sh new file mode 100755 index 0000000..84c1e23 --- /dev/null +++ b/conv.sh @@ -0,0 +1,8 @@ +#!/bin/bash +set -e +cargo run +for x in *.dot; do + dot -Kneato -T png $x -o $x.png + ../resize/target/release/resize $x.png 830 827 +done +gifski --fast -r 1 -o dcel.gif *.dot.png diff --git a/src/main.rs b/src/main.rs index 6e6408c..f5989e8 100644 --- a/src/main.rs +++ b/src/main.rs @@ -246,13 +246,6 @@ impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { } } - 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; @@ -296,23 +289,23 @@ impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, 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, ()); @@ -328,12 +321,12 @@ impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { let mut a3 = a1.borrow(&self.token).next?; if a3.borrow(&self.token) == b1.borrow(&self.token) { - a3 = a1; // b3 + a3 = b1; // a1 } let mut b3 = b1.borrow(&self.token).prev?; if b3.borrow(&self.token) == a1.borrow(&self.token) { - b3 = b1; // a2 + b3 = a2; // b1 } self.twin(a2, b2); @@ -348,16 +341,48 @@ impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { self.follow(b3, b2); self.follow(b2, b1); - Some((a1, v)) + Some((a2, v)) } + // pub fn mel(&mut self, b0: cell!(HalfEdge), a2: cell!(HalfEdge)) -> Option<()> { pub fn mel(&mut self, v1: cell!(Vertex), v2: cell!(Vertex)) -> Option<()> { - let a = self.half_edges.alloc(&mut self.token, ()); - let b = self.half_edges.alloc(&mut self.token, ()); + // before: + // > > + // a0 \ / a2 + // v1 v2 + // b0 / \ b2 + // < < + // + // after: + // > > + // a0 \ a1 -> / a2 + // v1 v2 + // b0 / <- b1 \ b2 + // < < + // - self.twin(a, b); + let a1 = self.half_edges.alloc(&mut self.token, ()); + let b1 = self.half_edges.alloc(&mut self.token, ()); + + let b0 = v1.borrow(&self.token).outgoing?; + let a2 = v2.borrow(&self.token).outgoing?; + + //let v1 = b0.borrow(&self.token).origin?; + //let v2 = a2.borrow(&self.token).origin?; + + let a0 = b0.borrow(&self.token).twin?; + let b2 = a2.borrow(&self.token).twin?; + + self.twin(a1, b1); + + self.origin(v1, a1); + self.origin(v2, b1); + + self.follow(a0, a1); + self.follow(a1, a2); - //self.origin(); + self.follow(b2, b1); + self.follow(b1, b0); Some(()) } @@ -381,6 +406,8 @@ impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { (v, a, b) } + + //fn mekh(&mut self, ) } struct DcelDotOptions { @@ -424,65 +451,77 @@ fn dcel_write_dot( 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=\"{},{}!\"]", + "vertex_{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 connect = |f: &mut fmt::Formatter<'_>, + id: &str, + label: &str, + attr: &str, + pts: [(&str, [f64; 2]); 2]| + -> Result<(), fmt::Error> { + let mut vec = [pts[1].1[1] - pts[0].1[1], pts[1].1[0] - pts[0].1[0]]; - 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.075; + vec[1] *= 0.075; - let len = (vec[0] * vec[0] + vec[1] * vec[1]).sqrt(); - vec[0] *= 0.2 / len; - vec[1] *= 0.2 / len; + let mid = [ + (pts[1].1[0] + pts[0].1[0]) / 2.0 + vec[0], + (pts[1].1[1] + pts[0].1[1]) / 2.0 + vec[1], + ]; - 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], - ]; + writeln!( + f, + "{id} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]", + mid[0], mid[1] + )?; + writeln!(f, "{} -> {id} [{attr}arrowhead=none]", pts[0].0)?; + writeln!(f, "{id} -> {} [{attr}label=\"{label}\"]", pts[1].0)?; - let a = a_v.id.unwrap(); - let b = b_v.id.unwrap(); + Ok(()) + }; - writeln!( + let a = h.origin.unwrap().borrow(&dcel.token); + let b = twin.origin.unwrap().borrow(&dcel.token); + + connect( f, - "edge_{id} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]", - mid[0], mid[1] + &format!("half_edge_{id}"), + &format!("{id}"), + "", + [ + ( + &format!("vertex_{}", a.id.unwrap()), + [a.data.1[0] as _, a.data.1[1] as _], + ), + ( + &format!("vertex_{}", b.id.unwrap()), + [b.data.1[0] as _, b.data.1[1] as _], + ), + ], )?; - 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\"]")?; + writeln!(f, "half_edge_{id} -> half_edge_{twin_id} [color=\"red\"]")?; } if opt.next { writeln!( f, - "edge_{id} -> edge_{} [color=\"green\"]", + "half_edge_{id} -> half_edge_{} [color=\"green\"]", h.next.unwrap().borrow(&dcel.token).id.unwrap() )?; } @@ -490,7 +529,7 @@ fn dcel_write_dot( if opt.prev { writeln!( f, - "edge_{id} -> edge_{} [color=\"blue\"]", + "half_edge_{id} -> half_edge_{} [color=\"blue\"]", h.prev.unwrap().borrow(&dcel.token).id.unwrap() )?; } @@ -509,28 +548,46 @@ impl) -> fmt::Result> fmt::Display for DisplayFn| dcel_write_dot( - &dcel, - f, - DcelDotOptions { - prev: false, - next: true, - twin: false, - } - )) + let show = |name, dcel: &Dcel<(&'static str, [i64; 2])>| { + write!( + &mut std::fs::File::create(name).unwrap(), + "{}", + DisplayFn(|f: &mut fmt::Formatter<'_>| dcel_write_dot( + dcel, + f, + DcelDotOptions { + prev: false, + next: true, + twin: false, + } + )) + ) + .unwrap(); + }; + + let (a, [w, n], _) = dcel.mevvls([("W", [-4, 0]), ("N", [0, 4])]); + show("1.dot", &dcel); + + let b = dcel.mve(a, ("E", [4, 0])).unwrap().0; + show("2.dot", &dcel); + + dcel.mve(a, ("S", [0, -4])).unwrap(); + show("3.dot", &dcel); + + dcel.mel(/*a, b.borrow(&dcel.token).twin.unwrap()*/ w, n); + show("4.dot", &dcel); + + eprintln!( + "{} {}", + a.borrow(&dcel.token).id.unwrap(), + b.borrow(&dcel.token).id.unwrap() ); /* diff --git a/utahteapot/LICENSE.txt b/utahteapot/LICENSE.txt deleted file mode 100644 index 7421e49..0000000 --- a/utahteapot/LICENSE.txt +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index 19d4877..0000000 --- a/utahteapot/README.txt +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index d225918..0000000 Binary files a/utahteapot/files/utahteapot.stl and /dev/null differ diff --git a/utahteapot/images/teapot_stl.jpg b/utahteapot/images/teapot_stl.jpg deleted file mode 100644 index 1d091f1..0000000 Binary files a/utahteapot/images/teapot_stl.jpg and /dev/null differ diff --git a/utahteapot/images/utahteapot.png b/utahteapot/images/utahteapot.png deleted file mode 100644 index ae8f786..0000000 Binary files a/utahteapot/images/utahteapot.png and /dev/null differ diff --git a/x.dot b/x.dot deleted file mode 100644 index 573b826..0000000 --- a/x.dot +++ /dev/null @@ -1,40 +0,0 @@ -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_1 [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_3 [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 deleted file mode 100644 index 260b597..0000000 --- a/x.svg +++ /dev/null @@ -1,227 +0,0 @@ - - - - - - -DCEL - - - -0 - -S - - - -edge_0 - - - - -0->edge_0 - - - - -edge_7 - - - - -0->edge_7 - - - - -1 - -E - - - -edge_3 - - - - -1->edge_3 - - - - -2 - -P1 - - - -edge_2 - - - - -2->edge_2 - - - - -edge_5 - - - - -2->edge_5 - - - - -3 - -P2 - - - -edge_4 - - - - -3->edge_4 - - - - -edge_1 - - - - -3->edge_1 - - - - -4 - -B - - - -edge_6 - - - - -4->edge_6 - - - - -edge_0->3 - - -0 - - - -edge_0->edge_4 - - - - - -edge_4->2 - - -4 - - - -edge_4->edge_3 - - - - - -edge_1->0 - - -1 - - - -edge_1->edge_0 - - - - - -edge_2->1 - - -2 - - - -edge_2->edge_1 - - - - - -edge_3->2 - - -3 - - - -edge_3->edge_5 - - - - - -edge_5->3 - - -5 - - - -edge_5->edge_1 - - - - - -edge_6->0 - - -6 - - - -edge_6->edge_7 - - - - - -edge_7->4 - - -7 - - - -edge_7->edge_6 - - - - - -- cgit v1.2.3