From 4b7532ca0d6ff21d5531febb749b43112d0451e8 Mon Sep 17 00:00:00 2001 From: Charlotte Pabst Date: Sat, 23 Mar 2024 16:54:20 +0100 Subject: --- src/entity.rs | 4 +- src/img.rs | 165 +++++++++ src/lib.rs | 1044 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 986 -------------------------------------------------- src/obj_export.rs | 154 ++++++++ src/obj_import.rs | 187 ++++++++++ 6 files changed, 1552 insertions(+), 988 deletions(-) create mode 100644 src/img.rs create mode 100644 src/lib.rs delete mode 100644 src/main.rs create mode 100644 src/obj_export.rs create mode 100644 src/obj_import.rs (limited to 'src') diff --git a/src/entity.rs b/src/entity.rs index b3e3359..1c2eb7a 100644 --- a/src/entity.rs +++ b/src/entity.rs @@ -172,12 +172,12 @@ macro_rules! entity { return; }; - let last = item; + let last = item.id(token); while { let next_item = item.next(token); f(item, token); item = next_item; - !item.eq(last, token) + matches!(item.maybe_id(token), Some(x) if x != last) } {} } diff --git a/src/img.rs b/src/img.rs new file mode 100644 index 0000000..5d015ff --- /dev/null +++ b/src/img.rs @@ -0,0 +1,165 @@ +use crate::*; + +pub use cairo; +pub use enumset::{self, EnumSet}; + +use cairo::{Context, Surface}; +use enumset::EnumSetType; +use std::borrow::{Borrow, Cow}; + +#[derive(EnumSetType, Debug)] +pub enum ImgOption { + Twin, + Next, + Prev, + EdgeIds, +} + +pub fn write_img( + dcel: &Dcel, + ctx: &Context, + opt: EnumSet, + pos: impl Fn(&V) -> [f64; 2], + label: impl Fn(&V) -> Cow, + font_size: f64, +) -> Result<(), cairo::Error> { + // let (_, _, width, height) = ctx.clip_extents()?; + + ctx.set_font_size(font_size); + for shell in dcel.iter_bodies().flat_map(Lens::iter_shells) { + for hedges in shell + .iter_edges() + .map(|x| x.half_edges()) + .flat_map(|[a, b]| [[a, b], [b, a]]) + { + let mut points = hedges.map(|h| pos(h.origin().data())); + + let mut dir = [points[1][0] - points[0][0], points[1][1] - points[0][1]]; + let scale = ctx.line_width() / (dir[0] * dir[0] + dir[1] * dir[1]).sqrt(); + dir = [dir[0] * scale, dir[1] * scale]; + let prp = [-dir[1], dir[0]]; + points[0] = [points[0][0] + prp[0] * 2.0, points[0][1] + prp[1] * 2.0]; + points[1] = [points[1][0] + prp[0] * 2.0, points[1][1] + prp[1] * 2.0]; + + ctx.move_to(points[0][0], points[0][1]); + ctx.line_to(points[1][0], points[1][1]); + ctx.stroke()?; + + let arrow_pos = 1.2; + let arrow = [ + (points[0][0] * (2.0 - arrow_pos) + points[1][0] * arrow_pos) / 2.0, + (points[0][1] * (2.0 - arrow_pos) + points[1][1] * arrow_pos) / 2.0, + ]; + let arrow_scale = 3.0; + + ctx.move_to(arrow[0], arrow[1]); + ctx.rel_line_to( + (-dir[0] + prp[0]) * arrow_scale, + (-dir[1] + prp[1]) * arrow_scale, + ); + ctx.rel_line_to(-prp[0] * 2.0 * arrow_scale, -prp[1] * 2.0 * arrow_scale); + ctx.line_to(arrow[0], arrow[1]); + ctx.close_path(); + ctx.fill()?; + + if opt.contains(ImgOption::EdgeIds) { + //arrow[0] + + let num_pos = [arrow[0] + prp[0] * 4.0, arrow[1] + prp[1] * 4.0]; + let num_text = hedges[0].id().to_string(); + + ctx.set_font_size(font_size / 2.0); + let ext = ctx.text_extents(&num_text)?; + ctx.move_to( + num_pos[0] - ext.x_advance() / 2.0, + num_pos[1] - ext.y_bearing() - ext.height() / 2.0, + ); + ctx.show_text(&num_text)?; + ctx.set_font_size(font_size); + } + + /* + writeln!( + f, + "half_edge_{} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]", + ids[0], mid[0], mid[1] + )?; + writeln!( + f, + "vertex_{} -> half_edge_{} [arrowhead=none]", + vertices[0].id(), + ids[0] + )?; + writeln!( + f, + "half_edge_{} -> vertex_{} [label=\"{}\"]", + ids[0], + vertices[1].id(), + ids[0] + )?; + + if opt.twin { + writeln!( + f, + "half_edge_{} -> half_edge_{} [color=\"red\"]", + ids[0], ids[1] + )?; + } + + if opt.next { + writeln!( + f, + "half_edge_{} -> half_edge_{} [color=\"green\"]", + ids[0], + hedges[0].next().id(), + )?; + } + + if opt.prev { + writeln!( + f, + "half_edge_{} -> half_edge_{} [color=\"blue\"]", + ids[0], + hedges[0].prev().id(), + )?; + }*/ + } + + for vertex in shell.iter_vertices() { + let v = vertex.data(); + let [x, y] = pos(v); + let text = label(v); + let ext = ctx.text_extents(text.borrow())?; + + let mat = ctx.matrix(); + ctx.translate(x, y); + ctx.scale( + (ext.x_advance() + ctx.line_width()) / 2.0f64.sqrt(), + (ext.height() + ctx.line_width()) / 2.0f64.sqrt(), + ); + ctx.translate(-x, -y); + ctx.new_path(); + ctx.arc(x, y, 1.0, 0.0, 2.0 * std::f64::consts::PI); + ctx.set_matrix(mat); + + let path = ctx.copy_path()?; + + ctx.set_source_rgb(1.0, 1.0, 1.0); + ctx.fill()?; + + ctx.append_path(&path); + ctx.set_source_rgb(0.0, 0.0, 0.0); + ctx.stroke()?; + + ctx.move_to( + x - ext.x_advance() / 2.0, + y - ext.y_bearing() - ext.height() / 2.0, + ); + ctx.show_text(text.borrow())?; + } + } + + Ok(()) + + // writeln!(f, "}}") +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..6b0542e --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,1044 @@ +#![allow(private_bounds)] + +use core::ops::Deref; +pub use ghost_cell::{GhostBorrow, GhostCell, GhostToken}; +use paste::paste; +use std::{ + collections::HashMap, + convert::Infallible, + fmt::{self, Debug, Display, Formatter}, + hash::{Hash, Hasher}, +}; +use thiserror::Error; +pub use typed_arena::Arena; + +macro_rules! try_check { + ($this:ident, $dcel:ident) => { + match $this.check($dcel) { + Ok(x) => x, + Err(e) => return Err(OperatorErr::new($this, e)), + } + }; +} + +#[macro_use] +mod entity; +use entity::*; + +mod entity_iterator; +pub use entity_iterator::*; + +mod dot; +pub use dot::*; + +#[cfg(feature = "img")] +mod img; + +#[cfg(feature = "img")] +pub use img::*; + +mod obj_export; +pub use obj_export::*; + +#[cfg(feature = "obj_import")] +mod obj_import; + +#[cfg(feature = "obj_import")] +pub use obj_import::*; + +#[cfg(test)] +mod tests; + +mod mevvlfs; +pub use mevvlfs::*; + +mod mev; +pub use mev::*; + +mod mve; +pub use mve::*; + +mod melf; +pub use melf::*; + +mod mekh; +pub use mekh::*; + +mod msev; +pub use msev::*; + +mod mpkh; +pub use mpkh::*; + +pub trait ReflAsRef { + fn as_ref(&self) -> &T; +} + +impl ReflAsRef for T { + fn as_ref(&self) -> &T { + self + } +} + +pub trait ReflAsMut: ReflAsRef { + fn as_mut(&mut self) -> &mut T; +} + +impl ReflAsMut for T { + fn as_mut(&mut self) -> &mut T { + self + } +} + +struct DisplayFn fmt::Result>(F); +impl fmt::Result> Display for DisplayFn { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.0(f) + } +} +impl fmt::Result> Debug for DisplayFn { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.0(f) + } +} + +#[macro_export] +macro_rules! ptr_t { + ($T:ty) => { + Ptr<'brand, 'arena, $T> + } +} + +#[macro_export] +macro_rules! ptr { + ($T:ident) => { + Ptr<'brand, 'arena, $T<'brand, 'arena, V>> + }; +} + +#[macro_export] +macro_rules! own_t { + ($T:ty) => { + Own<'brand, 'arena, $T> + } +} + +#[macro_export] +macro_rules! own { + ($T:ident) => { + Own<'brand, 'arena, $T<'brand, 'arena, V>> + }; +} + +#[macro_export] +macro_rules! lens_t { + ($T:ty) => { + Lens<'tok, 'brand, 'arena, $T> + } +} + +#[macro_export] +macro_rules! lens { + ($T:ident) => { + Lens<'tok, 'brand, 'arena, $T<'brand, 'arena, V>> + }; +} + +#[macro_export] +macro_rules! mklens { + ($token: expr, $($name:ident),*) => { + $( let $name = $name.lens($token); )* + }; +} + +fn short_debug_(ty: &'static str, id: usize, f: &mut Formatter) -> fmt::Result { + f.debug_tuple(ty).field(&id).finish() +} + +fn short_debug<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>>( + x: lens_t!(T), + f: &mut Formatter, +) -> fmt::Result { + short_debug_(T::type_name(), x.id(), f) +} + +fn short_debug_fn<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>>(x: lens_t!(T)) -> impl Debug { + let id = x.id(); + DisplayFn(move |f| short_debug_(T::type_name(), id, f)) +} + +fn short_debug_list<'tok, 'brand, 'arena, T, I>(iter: I, f: &mut Formatter) -> fmt::Result +where + 'brand: 'tok + 'arena, + T: Entity<'brand, 'arena> + 'arena, + I: Iterator, +{ + f.debug_list().entries(iter.map(short_debug_fn)).finish() +} + +fn or_err(cond: bool, err: T) -> Result<(), T> { + if cond { + Ok(()) + } else { + Err(err) + } +} + +pub struct Ptr<'brand, 'arena, T>(pub &'arena GhostCell<'brand, T>); + +impl<'brand, 'arena, T> Clone for ptr_t!(T) { + fn clone(&self) -> Self { + Self(self.0) + } +} +impl<'brand, 'arena, T> Copy for ptr_t!(T) {} + +impl<'brand, 'arena, T> ptr_t!(T) { + pub fn borrow<'tok, 'out>(self, token: &'tok impl ReflAsRef>) -> &'out T + where + 'arena: 'out, + 'tok: 'out, + { + self.0.borrow(token.as_ref()) + } + + pub fn borrow_mut<'tok, 'out>( + self, + token: &'tok mut impl ReflAsMut>, + ) -> &'out mut T + where + 'arena: 'out, + 'tok: 'out, + { + self.0.borrow_mut(token.as_mut()) + } + + pub fn lens<'tok>(self, token: &'tok impl ReflAsRef>) -> lens_t!(T) { + Lens::new(self, token) + } +} + +#[allow(unused)] +impl<'brand, 'arena, T: Entity<'brand, 'arena>> ptr_t!(T) { + fn clear(self, token: &mut impl ReflAsMut>) { + self.borrow_mut(token).clear() + } + + pub fn id(self, token: &impl ReflAsRef>) -> usize { + self.borrow(token).id() + } + fn maybe_id(self, token: &impl ReflAsRef>) -> Option { + self.borrow(token).maybe_id() + } + fn alive(self, token: &impl ReflAsRef>) -> bool { + self.borrow(token).alive() + } + + pub fn eq(self, other: Self, token: &impl ReflAsRef>) -> bool { + self.borrow(token) == other.borrow(token) + } + + fn next(self, token: &impl ReflAsRef>) -> Self { + self.borrow(token).next() + } + fn maybe_next(self, token: &impl ReflAsRef>) -> Option { + self.borrow(token).maybe_next() + } + fn set_next(self, x: Self, token: &mut impl ReflAsMut>) { + self.borrow_mut(token).set_next(x) + } + fn set_next_opt(self, x: Option, token: &mut impl ReflAsMut>) { + self.borrow_mut(token).set_next_opt(x) + } + + fn prev(self, token: &impl ReflAsRef>) -> Self { + self.borrow(token).prev() + } + fn maybe_prev(self, token: &impl ReflAsRef>) -> Option { + self.borrow(token).maybe_prev() + } + fn set_prev(self, x: Self, token: &mut impl ReflAsMut>) { + self.borrow_mut(token).set_prev(x) + } + fn set_prev_opt(self, x: Option, token: &mut impl ReflAsMut>) { + self.borrow_mut(token).set_prev_opt(x) + } +} + +pub struct Own<'brand, 'arena, T>(ptr_t!(T)); + +impl<'brand, 'arena, T> Own<'brand, 'arena, T> { + // avoid this + pub fn unsafe_make_owned(this: ptr_t!(T)) -> Self { + Self(this) + } +} + +impl<'brand, 'arena, T> Deref for own_t!(T) { + type Target = ptr_t!(T); + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +pub struct Lens<'tok, 'brand, 'arena, T> { + pub item: ptr_t!(T), + pub token: &'tok GhostToken<'brand>, +} + +impl<'tok, 'brand, 'arena, T> Clone for lens_t!(T) { + fn clone(&self) -> Self { + Self::new(self.item, self.token) + } +} +impl<'tok, 'brand, 'arena, T> Copy for lens_t!(T) {} + +impl<'tok, 'brand, 'arena, T: PartialEq> PartialEq for lens_t!(T) { + fn eq(&self, other: &Self) -> bool { + self.item.borrow(self.token) == other.item.borrow(other.token) + } +} +impl<'tok, 'brand, 'arena, T: PartialEq> Eq for lens_t!(T) {} + +impl<'tok, 'brand, 'arena, T: Hash> Hash for lens_t!(T) { + fn hash(&self, state: &mut H) { + self.item.borrow(self.token).hash(state); + } +} + +impl<'tok, 'brand, 'arena, T> ReflAsRef> for lens_t!(T) { + fn as_ref(&self) -> &GhostToken<'brand> { + &self.token + } +} + +impl<'tok, 'brand, 'arena, T> From for ptr_t!(T) { + fn from(x: lens_t!(T)) -> Self { + x.item + } +} + +impl<'tok, 'brand, 'arena, T> lens_t!(T) { + pub fn new(item: ptr_t!(T), token: &'tok impl ReflAsRef>) -> Self { + Self { + item, + token: token.as_ref(), + } + } +} + +#[allow(unused)] +impl<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>> lens_t!(T) { + pub fn id(self) -> usize { + self.item.id(&self) + } + fn maybe_id(self) -> Option { + self.item.maybe_id(&self) + } + fn alive(self) -> bool { + self.item.alive(&self) + } + + pub fn eq(self, other: ptr_t!(T)) -> bool { + self.item.eq(other, &self) + } + + fn next(self) -> Self { + self.item.next(&self).lens(self.token) + } + fn maybe_next(self) -> Option { + self.item.maybe_next(&self).map(|x| x.lens(self.token)) + } + + fn prev(self) -> Self { + self.item.prev(self.token).lens(self.token) + } + fn maybe_prev(self) -> Option { + self.item.maybe_prev(&self).map(|x| x.lens(self.token)) + } +} + +entity!(vertex: Vertex (init: V), + data: Option = Some(init); + outgoing: HalfEdge +); + +pub struct OutgoingIterator<'tok, 'brand, 'arena, V>(Option<(lens!(HalfEdge), lens!(HalfEdge))>); + +impl<'tok, 'brand, 'arena, V> Clone for OutgoingIterator<'tok, 'brand, 'arena, V> { + fn clone(&self) -> Self { + Self(self.0) + } +} + +impl<'tok, 'brand, 'arena, V> Copy for OutgoingIterator<'tok, 'brand, 'arena, V> {} + +impl<'tok, 'brand, 'arena, V> OutgoingIterator<'tok, 'brand, 'arena, V> { + fn new(start: Option, token: &'tok impl ReflAsRef>) -> Self { + Self(start.map(|s| { + let l = Lens::new(s, token); + (l, l) + })) + } +} + +impl<'tok, 'brand, 'arena, V> Iterator for OutgoingIterator<'tok, 'brand, 'arena, V> { + type Item = lens!(HalfEdge); + + fn next(&mut self) -> Option { + let range = self.0.as_mut()?; + let ret = range.0; + + range.0 = range.0.twin().next(); + if range.0 == range.1 { + self.0 = None; + } + + Some(ret) + } +} + +impl<'brand, 'arena, V> own!(Vertex) { + fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) -> V { + let data = self.borrow_mut(dcel).data.take().unwrap(); + self.free(dcel); + data + } +} + +impl<'brand, 'arena, V> ptr!(Vertex) { + pub fn data<'tok, 'out>(self, token: &'tok impl ReflAsRef>) -> &'out V + where + 'arena: 'out, + 'tok: 'out, + { + self.borrow(token).data.as_ref().unwrap() + } + + pub fn mut_data<'tok, 'out>( + self, + token: &'tok mut impl ReflAsMut>, + ) -> &'out mut V + where + 'arena: 'out, + 'tok: 'out, + { + self.borrow_mut(token).data.as_mut().unwrap() + } + + pub fn iter_outgoing<'tok>( + self, + token: &'tok impl ReflAsRef>, + ) -> OutgoingIterator<'tok, 'brand, 'arena, V> { + // FIXME: maybe enforce at least one item by using .outgoing() + // there should be no "standalone" vertices (?) + OutgoingIterator::new(self.maybe_outgoing(token), token) + } + + pub fn find_outgoing( + self, + loop_: ptr!(Loop), + token: &impl ReflAsRef>, + ) -> Option { + self.lens(token).find_outgoing(loop_).map(|x| x.item) + } +} + +impl<'tok, 'brand, 'arena, V> lens!(Vertex) { + pub fn data(&self) -> &V { + self.item.data(self) + } + + pub fn iter_outgoing(self) -> OutgoingIterator<'tok, 'brand, 'arena, V> { + self.item.iter_outgoing(self.token) + } + + pub fn find_outgoing(self, loop_: ptr!(Loop)) -> Option { + self.iter_outgoing().find(|x| x.loop_().eq(loop_)) + } + + fn debug_data(self, f: &mut Formatter) -> fmt::Result + where + V: Debug, + { + self.data().fmt(f) + } +} + +// TODO: target +entity!(half_edge: HalfEdge; + pub origin: Vertex, + pub twin: HalfEdge, + pub loop_: Loop, + pub edge: Edge +); + +impl<'brand, 'arena, V> ptr!(HalfEdge) { + pub fn target(self, token: &impl ReflAsRef>) -> ptr!(Vertex) { + self.twin(token).origin(token) + } + + fn update_origin(self, v: ptr!(Vertex), token: &mut impl ReflAsMut>) { + self.set_origin(v, token); + v.set_outgoing(self, token); + } +} + +impl<'tok, 'brand, 'arena, V> lens!(HalfEdge) { + pub fn target(self) -> lens!(Vertex) { + self.item.target(&self).lens(self.token) + } +} + +entity!(loop_: Loop; + half_edges[half_edge: half_edge back]: HalfEdge, + pub face: Face +); + +impl<'brand, 'arena, V> ptr!(Loop) { + pub fn is_outer(self, token: &impl ReflAsRef>) -> bool { + self.lens(token).is_outer() + } + + fn update_connectivity(self, token: &mut impl ReflAsMut>) { + self.iter_mut_half_edges(token, |x, token| x.set_loop_(self, token)); + } +} + +impl<'tok, 'brand, 'arena, V> lens!(Loop) { + pub fn is_outer(self) -> bool { + self.face().outer_loop() == self + } +} + +entity!(edge: Edge, + half_edges: [Option; 2] = [None, None] +); + +impl<'brand, 'arena, V> Edge<'brand, 'arena, V> { + fn create( + shell: ptr!(Shell), + dcel: &mut Dcel<'brand, 'arena, V>, + ) -> (own!(Edge), [ptr!(HalfEdge); 2]) { + let edge = shell.add_new_edge(dcel); + + let he1_own = HalfEdge::new(dcel); + let he2_own = HalfEdge::new(dcel); + + let he1 = *he1_own; + let he2 = *he2_own; + + edge.borrow_mut(dcel).half_edges = [Some(he1_own), Some(he2_own)]; + // edge.set_half_edges([he1_own, he2_own], dcel); + + he1.set_twin(he2, dcel); + he2.set_twin(he1, dcel); + he1.set_edge(*edge, dcel); + he2.set_edge(*edge, dcel); + + (edge, [he1, he2]) + } +} + +impl<'brand, 'arena, V> own!(Edge) { + fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) { + for x in self + .borrow_mut(dcel) + .half_edges + .each_mut() + .map(Option::take) + .into_iter() + .flatten() + { + x.free(dcel); + } + self.free(dcel); + } +} + +impl<'brand, 'arena, V> ptr!(Edge) { + pub fn half_edges(self, token: &impl ReflAsRef>) -> [ptr!(HalfEdge); 2] { + self.borrow(token) + .half_edges + .each_ref() + .map(|x| *x.as_deref().unwrap()) + } + + pub fn vertices(self, token: &impl ReflAsRef>) -> [ptr!(Vertex); 2] { + self.half_edges(token).map(|x| x.origin(token)) + } + + /* + fn set_half_edges( + self, + x: [own!(HalfEdge); 2], + token: &mut impl ReflAsMut>, + ) { + self.borrow_mut(token).half_edges = Some(x); + }*/ +} + +impl<'tok, 'brand, 'arena, V> lens!(Edge) { + pub fn half_edges(self) -> [lens!(HalfEdge); 2] { + self.item.half_edges(self.token).map(|x| x.lens(self.token)) + } + + pub fn vertices(self) -> [lens!(Vertex); 2] { + self.item.vertices(self.token).map(|x| x.lens(self.token)) + } + + fn debug_half_edges(self, f: &mut Formatter) -> fmt::Result + where + V: Debug, + { + f.debug_list().entries(self.half_edges()).finish() + } +} + +entity!(face: Face; + pub outer_loop: Loop, + inner_loops[inner_loop: loop_ back]: Loop, + pub shell: Shell +); + +impl<'brand, 'arena, V> own!(Face) { + fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) { + Own::unsafe_make_owned(self.outer_loop(dcel)).free(dcel); + self.iter_mut_inner_loops(dcel, |x, dcel| { + Own::unsafe_make_owned(x).free(dcel); + }); + self.free(dcel); + } +} + +entity!(shell: Shell; + faces[face: face back]: Face, + edges[edge: edge]: Edge, + vertices[vertex: vertex (V)]: Vertex, + pub body: Body +); + +impl<'brand, 'arena, V> own!(Shell) { + fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) { + self.iter_mut_faces(dcel, |x, dcel| { + Own::unsafe_make_owned(x).destroy(dcel); + }); + self.iter_mut_edges(dcel, |x, dcel| { + Own::unsafe_make_owned(x).destroy(dcel); + }); + self.iter_mut_vertices(dcel, |x, dcel| { + Own::unsafe_make_owned(x).destroy(dcel); + }); + self.free(dcel); + } +} + +entity!(body: Body; + shells[shell: shell back]: Shell +); + +impl<'brand, 'arena, V> own!(Body) { + fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) { + self.iter_mut_shells(dcel, |x, dcel| { + Own::unsafe_make_owned(x).destroy(dcel); + }); + dcel.delete_body(self); + } +} + +struct Allocator<'brand, 'arena, T: Entity<'brand, 'arena>> { + next_id: usize, + arena: &'arena Arena, + freelist: Vec, +} + +impl<'brand, 'arena, T: Entity<'brand, 'arena>> Allocator<'brand, 'arena, T> { + fn new(arena: &'arena Arena) -> Self { + Self { + next_id: 0, + arena, + freelist: Vec::new(), + } + } + + fn next_id(&mut self) -> usize { + let id = self.next_id; + self.next_id += 1; + id + } + + fn alloc(&mut self, x: T, token: &mut impl ReflAsMut>) -> own_t!(T) { + if let Some(ptr) = self.freelist.pop() { + *ptr.borrow_mut(token) = x; + ptr + } else { + Own::unsafe_make_owned(Ptr(GhostCell::from_mut(self.arena.alloc(x)))) + } + } + + fn free(&mut self, token: &mut impl ReflAsMut>, ptr: own_t!(T)) { + debug_assert!(ptr.alive(token), "double free"); + ptr.clear(token); + self.freelist.push(ptr); + } +} + +pub struct OperatorErr { + pub op: T, + pub err: E, +} + +impl OperatorErr { + pub fn new(op: T, err: E) -> Self { + Self { op, err } + } +} + +impl std::error::Error for OperatorErr {} +impl Debug for OperatorErr { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.err.fmt(f) + } +} +impl Display for OperatorErr { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.err.fmt(f) + } +} + +pub trait Operator<'brand, 'arena, V>: Sized { + type Inverse: Operator<'brand, 'arena, V>; + type Error: std::error::Error; + type Check; + + fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result; + + fn apply( + self, + dcel: &mut Dcel<'brand, 'arena, V>, + ) -> Result>; +} + +pub struct DcelArena<'brand, 'arena, V> { + pub vertex: Arena>, + pub half_edge: Arena>, + pub loop_: Arena>, + pub edge: Arena>, + pub face: Arena>, + pub shell: Arena>, + pub body: Arena>, +} + +impl<'brand, 'arena, V> Default for DcelArena<'brand, 'arena, V> { + fn default() -> Self { + Self { + vertex: Default::default(), + half_edge: Default::default(), + loop_: Default::default(), + edge: Default::default(), + face: Default::default(), + shell: Default::default(), + body: Default::default(), + } + } +} + +pub struct Dcel<'brand, 'arena, V> { + pub token: GhostToken<'brand>, + vertex: Allocator<'brand, 'arena, Vertex<'brand, 'arena, V>>, + half_edge: Allocator<'brand, 'arena, HalfEdge<'brand, 'arena, V>>, + loop_: Allocator<'brand, 'arena, Loop<'brand, 'arena, V>>, + edge: Allocator<'brand, 'arena, Edge<'brand, 'arena, V>>, + face: Allocator<'brand, 'arena, Face<'brand, 'arena, V>>, + shell: Allocator<'brand, 'arena, Shell<'brand, 'arena, V>>, + body: Allocator<'brand, 'arena, Body<'brand, 'arena, V>>, + bodies: Option, +} + +impl<'brand, 'arena, V> ReflAsRef> for Dcel<'brand, 'arena, V> { + fn as_ref(&self) -> &GhostToken<'brand> { + &self.token + } +} + +impl<'brand, 'arena, V> ReflAsMut> for Dcel<'brand, 'arena, V> { + fn as_mut(&mut self) -> &mut GhostToken<'brand> { + &mut self.token + } +} + +impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> { + pub fn from_token(token: GhostToken<'brand>, ar: &'arena DcelArena<'brand, 'arena, V>) -> Self { + Self { + token, + bodies: None, + vertex: Allocator::new(&ar.vertex), + half_edge: Allocator::new(&ar.half_edge), + loop_: Allocator::new(&ar.loop_), + edge: Allocator::new(&ar.edge), + face: Allocator::new(&ar.face), + shell: Allocator::new(&ar.shell), + body: Allocator::new(&ar.body), + } + } + + pub fn new(fun: F) -> R + where + for<'new_brand, 'new_arena> F: FnOnce(Dcel<'new_brand, 'new_arena, V>) -> R, + { + GhostToken::new(|token| { + let arena = DcelArena::default(); + let dcel = Dcel::from_token(token, &arena); + + fun(dcel) + }) + } + + pub fn new_body(&mut self) -> own!(Body) { + let body = Body::new(self); + self.bodies = Some(Entity::list_add(*body, self.bodies, self)); + body + } + + pub fn delete_body(&mut self, body: own!(Body)) { + self.bodies = Entity::list_remove(*body, self); + body.free(self); + } + + pub fn iter_bodies<'tok>( + &'tok self, + ) -> EntityIterator<'tok, 'brand, 'arena, Body<'brand, 'arena, V>> { + EntityIterator::new(self.bodies, self) + } + + // fn new_edge(&mut self, shell: ptr!(Shell)) -> (own!(Edge), [ptr!(HalfEdge); 2]) {} + + fn follow(&mut self, prev: ptr!(HalfEdge), next: ptr!(HalfEdge)) { + next.set_prev(prev, self); + prev.set_next(next, self); + } + + pub fn mevvlfs( + &mut self, + body: ptr!(Body), + data: [V; 2], + ) -> Result, OperatorErr, Infallible>> + { + Mevvlfs::new(body, data).apply(self) + } + + pub fn kevvlfs( + &mut self, + edge: own!(Edge), + vertices: [own!(Vertex); 2], + loop_: own!(Loop), + face: own!(Face), + shell: own!(Shell), + ) -> Result, OperatorErr, KevvlfsError>> + { + Kevvlfs::new(edge, vertices, loop_, face, shell).apply(self) + } + + pub fn mev( + &mut self, + loop_: ptr!(Loop), + vertex: ptr!(Vertex), + data: V, + ) -> Result, OperatorErr, MevError>> { + Mev::new(loop_, vertex, data).apply(self) + } + + pub fn kev( + &mut self, + edge: own!(Edge), + vertex: own!(Vertex), + ) -> Result, OperatorErr, KevError>> { + Kev::new(edge, vertex).apply(self) + } + + pub fn melf( + &mut self, + vertices: [ptr!(Vertex); 2], + loop_: ptr!(Loop), + ) -> Result, OperatorErr, MelfError>> { + Melf::new(vertices, loop_).apply(self) + } + + pub fn kelf( + &mut self, + edge: own!(Edge), + loop_: own!(Loop), + face: own!(Face), + ) -> Result, OperatorErr, KelfError>> { + Kelf::new(edge, loop_, face).apply(self) + } + + pub fn mve( + &mut self, + edge: ptr!(Edge), + data: V, + ) -> Result, OperatorErr, Infallible>> { + Mve::new(edge, data).apply(self) + } + + pub fn kve( + &mut self, + edge: own!(Edge), + vertex: own!(Vertex), + ) -> Result, OperatorErr, KveError>> { + Kve::new(edge, vertex).apply(self) + } + + pub fn mekh( + &mut self, + shell: ptr!(Shell), + into_loop: ptr!(Loop), + into_vertex: ptr!(Vertex), + hole_loop: own!(Loop), + hole_vertex: ptr!(Vertex), + ) -> Result, OperatorErr, MekhError>> { + Mekh::new(shell, into_loop, into_vertex, hole_loop, hole_vertex).apply(self) + } + + pub fn kemh( + &mut self, + shell: ptr!(Shell), + edge: own!(Edge), + loop_: ptr!(Loop), + hole_vertex: ptr!(Vertex), + ) -> Result, OperatorErr, KemhError>> { + Kemh::new(shell, edge, loop_, hole_vertex).apply(self) + } + + pub fn msev( + &mut self, + shell: ptr!(Shell), + vertex: ptr!(Vertex), + loops: [ptr!(Loop); 2], + data: V, + ) -> Result, OperatorErr, MsevError>> { + Msev::new(shell, vertex, loops, data).apply(self) + } + + pub fn ksev( + &mut self, + shell: ptr!(Shell), + loops: [ptr!(Loop); 2], + old_vertex: ptr!(Vertex), + new_vertex: own!(Vertex), + edge: own!(Edge), + ) -> Result, OperatorErr, KsevError>> { + Ksev::new(shell, loops, old_vertex, new_vertex, edge).apply(self) + } + + pub fn mpkh( + &mut self, + loop_: ptr!(Loop), + ) -> Result, OperatorErr, MpkhError>> { + Mpkh::new(loop_).apply(self) + } + + pub fn kpmh( + &mut self, + new_shell: Option, + old_face: ptr!(Face), + new_face: own!(Face), + ) -> Result, OperatorErr, KpmhError>> { + Kpmh::new(new_shell, old_face, new_face).apply(self) + } +} + +use std::io::Write; + +fn _main() { + 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, + |v| v.1.map(|x| x as _), + |v, f| write!(f, "{}", v.0), + f, + DcelDotOptions { + prev: false, + next: true, + twin: true, + } + )) + ) + .unwrap(); + }; + + GhostToken::new(|token| { + let arena = DcelArena::default(); + let mut dcel = Dcel::from_token(token, &arena); + + let body = dcel.new_body(); + // Mevvlfs(a, [w, n], l, f, s) + + //let op = dcel.mevvlfs(*body, [("W", [-4, 0]), ("N", [0, 4])]); + let op = dcel + .mevvlfs(*body, [("W", [-4, 0]), ("N", [0, 4])]) + .unwrap(); + let op2 = dcel.mev(*op.loop_, *op.vertices[1], ("E", [4, 0])).unwrap(); + let op3 = dcel.mev(*op.loop_, *op2.vertex, ("S", [0, -4])).unwrap(); + + dcel.melf([*op3.vertex, *op.vertices[0]], *op.loop_) + .unwrap(); + dcel.melf([*op.vertices[0], *op2.vertex], *op.loop_) + .unwrap(); + + show("cool_stuff.dot", &dcel); + + /*println!("{:?}", op.edge.lens(&dcel)); + println!("{:?}", op.vertices[0].lens(&dcel)); + println!("{:?}", op.vertices[1].lens(&dcel)); + println!("{:?}", op.loop_.lens(&dcel)); + println!("{:?}", op.face.lens(&dcel)); + println!("{:?}", op.shell.lens(&dcel));*/ + + //dbg!(body.lens(&dcel)); + + // dcel.undo(op); + + /* + + 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(w, n); + show("4.dot", &dcel);*/ + + /* + eprintln!( + "{} {}", + a.borrow(&dcel.token).id.unwrap(), + b.borrow(&dcel.token).id.unwrap() + );*/ + + /* + print!( + "{}", + "{}", + layFn(|f: &mut fmt::Formatter<'_>| { + v in dcel.vertices.elements.iter() { + } + + + h in dcel.half_edges.elements.iter() { + } + + Ok(()) + }) + }) + );*/ + }); +} diff --git a/src/main.rs b/src/main.rs deleted file mode 100644 index c3a3f4f..0000000 --- a/src/main.rs +++ /dev/null @@ -1,986 +0,0 @@ -#![allow(private_bounds)] - -use core::ops::Deref; -pub use ghost_cell::{GhostBorrow, GhostCell, GhostToken}; -use paste::paste; -use std::{ - collections::HashMap, - convert::Infallible, - fmt::{self, Debug, Display, Formatter}, - hash::{Hash, Hasher}, -}; -use thiserror::Error; -pub use typed_arena::Arena; - -macro_rules! try_check { - ($this:ident, $dcel:ident) => { - match $this.check($dcel) { - Ok(x) => x, - Err(e) => return Err(OperatorErr::new($this, e)), - } - }; -} - -#[macro_use] -mod entity; -use entity::*; - -mod entity_iterator; -pub use entity_iterator::*; - -mod dot; -pub use dot::*; - -#[cfg(test)] -mod tests; - -mod mevvlfs; -pub use mevvlfs::*; - -mod mev; -pub use mev::*; - -mod mve; -pub use mve::*; - -mod melf; -pub use melf::*; - -mod mekh; -pub use mekh::*; - -mod msev; -pub use msev::*; - -mod mpkh; -pub use mpkh::*; - -pub trait ReflAsRef { - fn as_ref(&self) -> &T; -} - -impl ReflAsRef for T { - fn as_ref(&self) -> &T { - self - } -} - -pub trait ReflAsMut: ReflAsRef { - fn as_mut(&mut self) -> &mut T; -} - -impl ReflAsMut for T { - fn as_mut(&mut self) -> &mut T { - self - } -} - -struct DisplayFn fmt::Result>(F); -impl fmt::Result> Display for DisplayFn { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.0(f) - } -} -impl fmt::Result> Debug for DisplayFn { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.0(f) - } -} - -#[macro_export] -macro_rules! ptr_t { - ($T:ty) => { - Ptr<'brand, 'arena, $T> - } -} - -#[macro_export] -macro_rules! ptr { - ($T:ident) => { - Ptr<'brand, 'arena, $T<'brand, 'arena, V>> - }; -} - -#[macro_export] -macro_rules! own_t { - ($T:ty) => { - Own<'brand, 'arena, $T> - } -} - -#[macro_export] -macro_rules! own { - ($T:ident) => { - Own<'brand, 'arena, $T<'brand, 'arena, V>> - }; -} - -#[macro_export] -macro_rules! lens_t { - ($T:ty) => { - Lens<'tok, 'brand, 'arena, $T> - } -} - -#[macro_export] -macro_rules! lens { - ($T:ident) => { - Lens<'tok, 'brand, 'arena, $T<'brand, 'arena, V>> - }; -} - -#[macro_export] -macro_rules! mklens { - ($token: expr, $($name:ident),*) => { - $( let $name = $name.lens($token); )* - }; -} - -fn _short_debug(ty: &'static str, id: usize, f: &mut Formatter) -> fmt::Result { - f.debug_tuple(ty).field(&id).finish() -} - -fn short_debug<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>>( - x: lens_t!(T), - f: &mut Formatter, -) -> fmt::Result { - _short_debug(T::type_name(), x.id(), f) -} - -fn short_debug_fn<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>>(x: lens_t!(T)) -> impl Debug { - let id = x.id(); - DisplayFn(move |f| _short_debug(T::type_name(), id, f)) -} - -fn short_debug_list<'tok, 'brand, 'arena, T, I>(iter: I, f: &mut Formatter) -> fmt::Result -where - 'brand: 'tok + 'arena, - T: Entity<'brand, 'arena> + 'arena, - I: Iterator, -{ - f.debug_list().entries(iter.map(short_debug_fn)).finish() -} - -fn or_err(cond: bool, err: T) -> Result<(), T> { - if cond { - Ok(()) - } else { - Err(err) - } -} - -pub struct Ptr<'brand, 'arena, T>(pub &'arena GhostCell<'brand, T>); - -impl<'brand, 'arena, T> Clone for ptr_t!(T) { - fn clone(&self) -> Self { - Self(self.0) - } -} -impl<'brand, 'arena, T> Copy for ptr_t!(T) {} - -impl<'brand, 'arena, T> ptr_t!(T) { - pub fn borrow<'tok, 'out>(self, token: &'tok impl ReflAsRef>) -> &'out T - where - 'arena: 'out, - 'tok: 'out, - { - self.0.borrow(token.as_ref()) - } - - pub fn borrow_mut<'tok, 'out>( - self, - token: &'tok mut impl ReflAsMut>, - ) -> &'out mut T - where - 'arena: 'out, - 'tok: 'out, - { - self.0.borrow_mut(token.as_mut()) - } - - pub fn lens<'tok>(self, token: &'tok impl ReflAsRef>) -> lens_t!(T) { - Lens::new(self, token) - } -} - -#[allow(unused)] -impl<'brand, 'arena, T: Entity<'brand, 'arena>> ptr_t!(T) { - fn clear(self, token: &mut impl ReflAsMut>) { - self.borrow_mut(token).clear() - } - - pub fn id(self, token: &impl ReflAsRef>) -> usize { - self.borrow(token).id() - } - fn maybe_id(self, token: &impl ReflAsRef>) -> Option { - self.borrow(token).maybe_id() - } - fn alive(self, token: &impl ReflAsRef>) -> bool { - self.borrow(token).alive() - } - - pub fn eq(self, other: Self, token: &impl ReflAsRef>) -> bool { - self.borrow(token) == other.borrow(token) - } - - fn next(self, token: &impl ReflAsRef>) -> Self { - self.borrow(token).next() - } - fn maybe_next(self, token: &impl ReflAsRef>) -> Option { - self.borrow(token).maybe_next() - } - fn set_next(self, x: Self, token: &mut impl ReflAsMut>) { - self.borrow_mut(token).set_next(x) - } - fn set_next_opt(self, x: Option, token: &mut impl ReflAsMut>) { - self.borrow_mut(token).set_next_opt(x) - } - - fn prev(self, token: &impl ReflAsRef>) -> Self { - self.borrow(token).prev() - } - fn maybe_prev(self, token: &impl ReflAsRef>) -> Option { - self.borrow(token).maybe_prev() - } - fn set_prev(self, x: Self, token: &mut impl ReflAsMut>) { - self.borrow_mut(token).set_prev(x) - } - fn set_prev_opt(self, x: Option, token: &mut impl ReflAsMut>) { - self.borrow_mut(token).set_prev_opt(x) - } -} - -pub struct Own<'brand, 'arena, T>(ptr_t!(T)); - -impl<'brand, 'arena, T> Own<'brand, 'arena, T> { - // avoid this - pub fn unsafe_make_owned(this: ptr_t!(T)) -> Self { - Self(this) - } -} - -impl<'brand, 'arena, T> Deref for own_t!(T) { - type Target = ptr_t!(T); - - fn deref(&self) -> &Self::Target { - &self.0 - } -} - -pub struct Lens<'tok, 'brand, 'arena, T> { - pub item: ptr_t!(T), - pub token: &'tok GhostToken<'brand>, -} - -impl<'tok, 'brand, 'arena, T> Clone for lens_t!(T) { - fn clone(&self) -> Self { - Self::new(self.item, self.token) - } -} -impl<'tok, 'brand, 'arena, T> Copy for lens_t!(T) {} - -impl<'tok, 'brand, 'arena, T: PartialEq> PartialEq for lens_t!(T) { - fn eq(&self, other: &Self) -> bool { - self.item.borrow(self.token) == other.item.borrow(other.token) - } -} -impl<'tok, 'brand, 'arena, T: PartialEq> Eq for lens_t!(T) {} - -impl<'tok, 'brand, 'arena, T: Hash> Hash for lens_t!(T) { - fn hash(&self, state: &mut H) { - self.item.borrow(self.token).hash(state); - } -} - -impl<'tok, 'brand, 'arena, T> ReflAsRef> for lens_t!(T) { - fn as_ref(&self) -> &GhostToken<'brand> { - &self.token - } -} - -impl<'tok, 'brand, 'arena, T> From for ptr_t!(T) { - fn from(x: lens_t!(T)) -> Self { - x.item - } -} - -impl<'tok, 'brand, 'arena, T> lens_t!(T) { - pub fn new(item: ptr_t!(T), token: &'tok impl ReflAsRef>) -> Self { - Self { - item, - token: token.as_ref(), - } - } -} - -#[allow(unused)] -impl<'tok, 'brand, 'arena, T: Entity<'brand, 'arena>> lens_t!(T) { - pub fn id(self) -> usize { - self.item.id(&self) - } - fn maybe_id(self) -> Option { - self.item.maybe_id(&self) - } - fn alive(self) -> bool { - self.item.alive(&self) - } - - pub fn eq(self, other: ptr_t!(T)) -> bool { - self.item.eq(other, &self) - } - - fn next(self) -> Self { - self.item.next(&self).lens(self.token) - } - fn maybe_next(self) -> Option { - self.item.maybe_next(&self).map(|x| x.lens(self.token)) - } - - fn prev(self) -> Self { - self.item.prev(self.token).lens(self.token) - } - fn maybe_prev(self) -> Option { - self.item.maybe_prev(&self).map(|x| x.lens(self.token)) - } -} - -entity!(vertex: Vertex (init: V), - data: Option = Some(init); - outgoing: HalfEdge -); - -pub struct OutgoingIterator<'tok, 'brand, 'arena, V>(Option<(lens!(HalfEdge), lens!(HalfEdge))>); - -impl<'tok, 'brand, 'arena, V> Clone for OutgoingIterator<'tok, 'brand, 'arena, V> { - fn clone(&self) -> Self { - Self(self.0) - } -} - -impl<'tok, 'brand, 'arena, V> Copy for OutgoingIterator<'tok, 'brand, 'arena, V> {} - -impl<'tok, 'brand, 'arena, V> OutgoingIterator<'tok, 'brand, 'arena, V> { - fn new(start: Option, token: &'tok impl ReflAsRef>) -> Self { - Self(start.map(|s| { - let l = Lens::new(s, token); - (l, l) - })) - } -} - -impl<'tok, 'brand, 'arena, V> Iterator for OutgoingIterator<'tok, 'brand, 'arena, V> { - type Item = lens!(HalfEdge); - - fn next(&mut self) -> Option { - let range = self.0.as_mut()?; - let ret = range.0; - - range.0 = range.0.twin().next(); - if range.0 == range.1 { - self.0 = None; - } - - Some(ret) - } -} - -impl<'brand, 'arena, V> own!(Vertex) { - fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) -> V { - let data = self.borrow_mut(dcel).data.take().unwrap(); - self.free(dcel); - data - } -} - -impl<'brand, 'arena, V> ptr!(Vertex) { - pub fn data<'tok, 'out>(self, token: &'tok impl ReflAsRef>) -> &'out V - where - 'arena: 'out, - 'tok: 'out, - { - self.borrow(token).data.as_ref().unwrap() - } - - pub fn mut_data<'tok, 'out>( - self, - token: &'tok mut impl ReflAsMut>, - ) -> &'out mut V - where - 'arena: 'out, - 'tok: 'out, - { - self.borrow_mut(token).data.as_mut().unwrap() - } - - pub fn iter_outgoing<'tok>( - self, - token: &'tok impl ReflAsRef>, - ) -> OutgoingIterator<'tok, 'brand, 'arena, V> { - // FIXME: maybe enforce at least one item by using .outgoing() - // there should be no "standalone" vertices (?) - OutgoingIterator::new(self.maybe_outgoing(token), token) - } - - pub fn find_outgoing( - self, - loop_: ptr!(Loop), - token: &impl ReflAsRef>, - ) -> Option { - self.lens(token).find_outgoing(loop_).map(|x| x.item) - } -} - -impl<'tok, 'brand, 'arena, V> lens!(Vertex) { - pub fn data(&self) -> &V { - self.item.data(self) - } - - pub fn iter_outgoing(self) -> OutgoingIterator<'tok, 'brand, 'arena, V> { - self.item.iter_outgoing(self.token) - } - - pub fn find_outgoing(self, loop_: ptr!(Loop)) -> Option { - self.iter_outgoing().find(|x| x.loop_().eq(loop_)) - } - - fn debug_data(self, f: &mut Formatter) -> fmt::Result - where - V: Debug, - { - self.data().fmt(f) - } -} - -// TODO: target -entity!(half_edge: HalfEdge; - pub origin: Vertex, - pub twin: HalfEdge, - pub loop_: Loop, - pub edge: Edge -); - -impl<'brand, 'arena, V> ptr!(HalfEdge) { - pub fn target(self, token: &impl ReflAsRef>) -> ptr!(Vertex) { - self.twin(token).origin(token) - } - - fn update_origin(self, v: ptr!(Vertex), token: &mut impl ReflAsMut>) { - self.set_origin(v, token); - v.set_outgoing(self, token); - } -} - -impl<'tok, 'brand, 'arena, V> lens!(HalfEdge) { - pub fn target(self) -> lens!(Vertex) { - self.item.target(&self).lens(self.token) - } -} - -entity!(loop_: Loop; - half_edges[half_edge: half_edge back]: HalfEdge, - pub face: Face -); - -impl<'brand, 'arena, V> ptr!(Loop) { - pub fn is_outer(self, token: &impl ReflAsRef>) -> bool { - self.lens(token).is_outer() - } - - fn update_connectivity(self, token: &mut impl ReflAsMut>) { - self.iter_mut_half_edges(token, |x, token| x.set_loop_(self, token)); - } -} - -impl<'tok, 'brand, 'arena, V> lens!(Loop) { - pub fn is_outer(self) -> bool { - self.face().outer_loop() == self - } -} - -entity!(edge: Edge, - half_edges: Option<[own!(HalfEdge); 2]> = None -); - -impl<'brand, 'arena, V> Edge<'brand, 'arena, V> { - fn create( - shell: ptr!(Shell), - dcel: &mut Dcel<'brand, 'arena, V>, - ) -> (own!(Edge), [ptr!(HalfEdge); 2]) { - let edge = shell.add_new_edge(dcel); - - let he1_own = HalfEdge::new(dcel); - let he2_own = HalfEdge::new(dcel); - - let he1 = *he1_own; - let he2 = *he2_own; - - edge.borrow_mut(dcel).half_edges = Some([he1_own, he2_own]); - // edge.set_half_edges([he1_own, he2_own], dcel); - - he1.set_twin(he2, dcel); - he2.set_twin(he1, dcel); - he1.set_edge(*edge, dcel); - he2.set_edge(*edge, dcel); - - (edge, [he1, he2]) - } -} - -impl<'brand, 'arena, V> own!(Edge) { - fn destroy(self, dcel: &mut Dcel<'brand, 'arena, V>) { - let [a, b] = self.borrow_mut(dcel).half_edges.take().unwrap(); - self.free(dcel); - a.free(dcel); - b.free(dcel); - } -} - -impl<'brand, 'arena, V> ptr!(Edge) { - pub fn half_edges(self, token: &impl ReflAsRef>) -> [ptr!(HalfEdge); 2] { - let he = self.borrow(token).half_edges.as_ref().unwrap(); - [*he[0], *he[1]] - } - - pub fn vertices(self, token: &impl ReflAsRef>) -> [ptr!(Vertex); 2] { - self.half_edges(token).map(|x| x.origin(token)) - } - - /* - fn set_half_edges( - self, - x: [own!(HalfEdge); 2], - token: &mut impl ReflAsMut>, - ) { - self.borrow_mut(token).half_edges = Some(x); - }*/ -} - -impl<'tok, 'brand, 'arena, V> lens!(Edge) { - pub fn half_edges(self) -> [lens!(HalfEdge); 2] { - self.item.half_edges(self.token).map(|x| x.lens(self.token)) - } - - pub fn vertices(self) -> [lens!(Vertex); 2] { - self.item.vertices(self.token).map(|x| x.lens(self.token)) - } - - fn debug_half_edges(self, f: &mut Formatter) -> fmt::Result - where - V: Debug, - { - f.debug_list().entries(self.half_edges()).finish() - } -} - -entity!(face: Face; - pub outer_loop: Loop, - inner_loops[inner_loop: loop_ back]: Loop, - pub shell: Shell -); - -entity!(shell: Shell; - faces[face: face back]: Face, - edges[edge: edge]: Edge, - vertices[vertex: vertex (V)]: Vertex, - pub body: Body -); - -entity!(body: Body; - shells[shell: shell back]: Shell -); - -struct Allocator<'brand, 'arena, T: Entity<'brand, 'arena>> { - next_id: usize, - arena: &'arena Arena, - freelist: Vec, -} - -impl<'brand, 'arena, T: Entity<'brand, 'arena>> Allocator<'brand, 'arena, T> { - fn new(arena: &'arena Arena) -> Self { - Self { - next_id: 0, - arena, - freelist: Vec::new(), - } - } - - fn next_id(&mut self) -> usize { - let id = self.next_id; - self.next_id += 1; - id - } - - fn alloc(&mut self, x: T, token: &mut impl ReflAsMut>) -> own_t!(T) { - if let Some(ptr) = self.freelist.pop() { - *ptr.borrow_mut(token) = x; - ptr - } else { - Own::unsafe_make_owned(Ptr(GhostCell::from_mut(self.arena.alloc(x)))) - } - } - - fn free(&mut self, token: &mut impl ReflAsMut>, ptr: own_t!(T)) { - debug_assert!(ptr.alive(token), "double free"); - ptr.clear(token); - self.freelist.push(ptr); - } -} - -pub struct OperatorErr { - pub op: T, - pub err: E, -} - -impl OperatorErr { - pub fn new(op: T, err: E) -> Self { - Self { op, err } - } -} - -impl std::error::Error for OperatorErr {} -impl Debug for OperatorErr { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.err.fmt(f) - } -} -impl Display for OperatorErr { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.err.fmt(f) - } -} - -pub trait Operator<'brand, 'arena, V>: Sized { - type Inverse; //: Operator<'brand, 'arena, V>; - type Error: std::error::Error; - type Check; - - fn check(&self, dcel: &Dcel<'brand, 'arena, V>) -> Result; - - fn apply( - self, - dcel: &mut Dcel<'brand, 'arena, V>, - ) -> Result>; -} - -pub struct DcelArena<'brand, 'arena, V> { - pub vertex: Arena>, - pub half_edge: Arena>, - pub loop_: Arena>, - pub edge: Arena>, - pub face: Arena>, - pub shell: Arena>, - pub body: Arena>, -} - -impl<'brand, 'arena, V> Default for DcelArena<'brand, 'arena, V> { - fn default() -> Self { - Self { - vertex: Default::default(), - half_edge: Default::default(), - loop_: Default::default(), - edge: Default::default(), - face: Default::default(), - shell: Default::default(), - body: Default::default(), - } - } -} - -pub struct Dcel<'brand, 'arena, V> { - pub token: GhostToken<'brand>, - vertex: Allocator<'brand, 'arena, Vertex<'brand, 'arena, V>>, - half_edge: Allocator<'brand, 'arena, HalfEdge<'brand, 'arena, V>>, - loop_: Allocator<'brand, 'arena, Loop<'brand, 'arena, V>>, - edge: Allocator<'brand, 'arena, Edge<'brand, 'arena, V>>, - face: Allocator<'brand, 'arena, Face<'brand, 'arena, V>>, - shell: Allocator<'brand, 'arena, Shell<'brand, 'arena, V>>, - body: Allocator<'brand, 'arena, Body<'brand, 'arena, V>>, - bodies: Option, -} - -impl<'brand, 'arena, V> ReflAsRef> for Dcel<'brand, 'arena, V> { - fn as_ref(&self) -> &GhostToken<'brand> { - &self.token - } -} - -impl<'brand, 'arena, V> ReflAsMut> for Dcel<'brand, 'arena, V> { - fn as_mut(&mut self) -> &mut GhostToken<'brand> { - &mut self.token - } -} - -impl<'brand, 'arena, V> Dcel<'brand, 'arena, V> { - pub fn from_token(token: GhostToken<'brand>, ar: &'arena DcelArena<'brand, 'arena, V>) -> Self { - Self { - token, - bodies: None, - vertex: Allocator::new(&ar.vertex), - half_edge: Allocator::new(&ar.half_edge), - loop_: Allocator::new(&ar.loop_), - edge: Allocator::new(&ar.edge), - face: Allocator::new(&ar.face), - shell: Allocator::new(&ar.shell), - body: Allocator::new(&ar.body), - } - } - - pub fn new(fun: F) -> R - where - for<'new_brand, 'new_arena> F: FnOnce(Dcel<'new_brand, 'new_arena, W>) -> R, - { - GhostToken::new(|token| { - let arena = DcelArena::default(); - let dcel = Dcel::from_token(token, &arena); - - fun(dcel) - }) - } - - pub fn new_body(&mut self) -> own!(Body) { - let body = Body::new(self); - self.bodies = Some(Entity::list_add(*body, self.bodies, self)); - body - } - - pub fn delete_body(&mut self, body: own!(Body)) { - self.bodies = Entity::list_remove(*body, self); - body.free(self); - } - - pub fn iter_bodies<'tok>( - &'tok self, - ) -> EntityIterator<'tok, 'brand, 'arena, Body<'brand, 'arena, V>> { - EntityIterator::new(self.bodies, self) - } - - // fn new_edge(&mut self, shell: ptr!(Shell)) -> (own!(Edge), [ptr!(HalfEdge); 2]) {} - - fn follow(&mut self, prev: ptr!(HalfEdge), next: ptr!(HalfEdge)) { - next.set_prev(prev, self); - prev.set_next(next, self); - } - - pub fn mevvlfs( - &mut self, - body: ptr!(Body), - data: [V; 2], - ) -> Result, OperatorErr, Infallible>> - { - Mevvlfs::new(body, data).apply(self) - } - - pub fn kevvlfs( - &mut self, - edge: own!(Edge), - vertices: [own!(Vertex); 2], - loop_: own!(Loop), - face: own!(Face), - shell: own!(Shell), - ) -> Result, OperatorErr, KevvlfsError>> - { - Kevvlfs::new(edge, vertices, loop_, face, shell).apply(self) - } - - pub fn mev( - &mut self, - loop_: ptr!(Loop), - vertex: ptr!(Vertex), - data: V, - ) -> Result, OperatorErr, MevError>> { - Mev::new(loop_, vertex, data).apply(self) - } - - pub fn kev( - &mut self, - edge: own!(Edge), - vertex: own!(Vertex), - ) -> Result, OperatorErr, KevError>> { - Kev::new(edge, vertex).apply(self) - } - - pub fn melf( - &mut self, - vertices: [ptr!(Vertex); 2], - loop_: ptr!(Loop), - ) -> Result, OperatorErr, MelfError>> { - Melf::new(vertices, loop_).apply(self) - } - - pub fn kelf( - &mut self, - edge: own!(Edge), - loop_: own!(Loop), - face: own!(Face), - ) -> Result, OperatorErr, KelfError>> { - Kelf::new(edge, loop_, face).apply(self) - } - - pub fn mve( - &mut self, - edge: ptr!(Edge), - data: V, - ) -> Result, OperatorErr, Infallible>> { - Mve::new(edge, data).apply(self) - } - - pub fn kve( - &mut self, - edge: own!(Edge), - vertex: own!(Vertex), - ) -> Result, OperatorErr, KveError>> { - Kve::new(edge, vertex).apply(self) - } - - pub fn mekh( - &mut self, - shell: ptr!(Shell), - into_loop: ptr!(Loop), - into_vertex: ptr!(Vertex), - hole_loop: own!(Loop), - hole_vertex: ptr!(Vertex), - ) -> Result, OperatorErr, MekhError>> { - Mekh::new(shell, into_loop, into_vertex, hole_loop, hole_vertex).apply(self) - } - - pub fn kemh( - &mut self, - shell: ptr!(Shell), - edge: own!(Edge), - loop_: ptr!(Loop), - hole_vertex: ptr!(Vertex), - ) -> Result, OperatorErr, KemhError>> { - Kemh::new(shell, edge, loop_, hole_vertex).apply(self) - } - - pub fn msev( - &mut self, - shell: ptr!(Shell), - vertex: ptr!(Vertex), - loops: [ptr!(Loop); 2], - data: V, - ) -> Result, OperatorErr, MsevError>> { - Msev::new(shell, vertex, loops, data).apply(self) - } - - pub fn ksev( - &mut self, - shell: ptr!(Shell), - loops: [ptr!(Loop); 2], - old_vertex: ptr!(Vertex), - new_vertex: own!(Vertex), - edge: own!(Edge), - ) -> Result, OperatorErr, KsevError>> { - Ksev::new(shell, loops, old_vertex, new_vertex, edge).apply(self) - } - - pub fn mpkh( - &mut self, - loop_: ptr!(Loop), - ) -> Result, OperatorErr, MpkhError>> { - Mpkh::new(loop_).apply(self) - } - - pub fn kpmh( - &mut self, - new_shell: Option, - old_face: ptr!(Face), - new_face: own!(Face), - ) -> Result, OperatorErr, KpmhError>> { - Kpmh::new(new_shell, old_face, new_face).apply(self) - } -} - -use std::io::Write; - -fn main() { - 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, - |v| v.1.map(|x| x as _), - |v, f| write!(f, "{}", v.0), - f, - DcelDotOptions { - prev: false, - next: true, - twin: true, - } - )) - ) - .unwrap(); - }; - - GhostToken::new(|token| { - let arena = DcelArena::default(); - let mut dcel = Dcel::from_token(token, &arena); - - let body = dcel.new_body(); - // Mevvlfs(a, [w, n], l, f, s) - - //let op = dcel.mevvlfs(*body, [("W", [-4, 0]), ("N", [0, 4])]); - let op = dcel - .mevvlfs(*body, [("W", [-4, 0]), ("N", [0, 4])]) - .unwrap(); - let op2 = dcel.mev(*op.loop_, *op.vertices[1], ("E", [4, 0])).unwrap(); - let op3 = dcel.mev(*op.loop_, *op2.vertex, ("S", [0, -4])).unwrap(); - - dcel.melf([*op3.vertex, *op.vertices[0]], *op.loop_) - .unwrap(); - dcel.melf([*op.vertices[0], *op2.vertex], *op.loop_) - .unwrap(); - - show("cool_stuff.dot", &dcel); - - /*println!("{:?}", op.edge.lens(&dcel)); - println!("{:?}", op.vertices[0].lens(&dcel)); - println!("{:?}", op.vertices[1].lens(&dcel)); - println!("{:?}", op.loop_.lens(&dcel)); - println!("{:?}", op.face.lens(&dcel)); - println!("{:?}", op.shell.lens(&dcel));*/ - - //dbg!(body.lens(&dcel)); - - // dcel.undo(op); - - /* - - 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(w, n); - show("4.dot", &dcel);*/ - - /* - eprintln!( - "{} {}", - a.borrow(&dcel.token).id.unwrap(), - b.borrow(&dcel.token).id.unwrap() - );*/ - - /* - print!( - "{}", - "{}", - layFn(|f: &mut fmt::Formatter<'_>| { - v in dcel.vertices.elements.iter() { - } - - - h in dcel.half_edges.elements.iter() { - } - - Ok(()) - }) - }) - );*/ - }); -} diff --git a/src/obj_export.rs b/src/obj_export.rs new file mode 100644 index 0000000..7998112 --- /dev/null +++ b/src/obj_export.rs @@ -0,0 +1,154 @@ +use crate::*; + +struct VertAttr { + func: F, + items: Vec, + local: HashMap>, + // global: HashMap, + marker: std::marker::PhantomData<(V, L)>, +} + +impl VertAttr +where + F: FnMut(L, &V) -> Option, + T: Copy, // + Hash + Eq, +{ + fn new(func: F) -> Self { + Self { + func, + items: Vec::new(), + local: HashMap::new(), + // global: HashMap::new(), + marker: std::marker::PhantomData, + } + } + + fn add(&mut self, local: L, vert_id: usize, vert_data: &V) -> Option { + *self.local.entry(vert_id).or_insert_with(|| { + let item = (self.func)(local, vert_data); + + //*self.global.entry(item).or_insert_with(|| { + item.map(|item| { + self.items.push(item); + self.items.len() + }) + //}) + }) + } +} + +pub struct ObjExport<'tok, 'brand, 'arena, V, W, VPos, VTex, VNorm> { + writer: &'tok mut W, + dcel: &'tok Dcel<'brand, 'arena, V>, + vertex_pos: VPos, + pos_ids: HashMap, + textures: VertAttr)>), V>, + normals: VertAttr, +} + +impl<'tok, 'brand, 'arena, V, W, VPos, VTex, VNorm> + ObjExport<'tok, 'brand, 'arena, V, W, VPos, VTex, VNorm> +where + W: std::io::Write, + VPos: FnMut(&V) -> (f64, f64, f64, Option), + VTex: FnMut(lens!(Face), &V) -> Option<(f64, Option<(f64, Option)>)>, + VNorm: FnMut(lens!(Face), &V) -> Option<(f64, f64, f64)>, +{ + pub fn export( + writer: &'tok mut W, + dcel: &'tok Dcel<'brand, 'arena, V>, + vertex_pos: VPos, + vertex_texture: VTex, + vertex_normal: VNorm, + ) -> std::io::Result<()> { + Self { + writer, + dcel, + vertex_pos, + pos_ids: HashMap::new(), + textures: VertAttr::new(vertex_texture), + normals: VertAttr::new(vertex_normal), + } + .write() + } + + fn write(&mut self) -> std::io::Result<()> { + let mut next_id = 1; + for shell in self.dcel.iter_bodies().flat_map(Lens::iter_shells) { + for vertex in shell.iter_vertices() { + self.pos_ids.insert(vertex.id(), next_id); + next_id += 1; + + let (x, y, z, w) = (self.vertex_pos)(vertex.data()); + write!(self.writer, "v {x} {y} {z}")?; + if let Some(w) = w { + write!(self.writer, " {w}")?; + } + writeln!(self.writer)?; + } + + for face in shell.iter_faces() { + write!(self.writer, "f")?; + + for inner in face.iter_inner_loops() { + self.write_vertex(face, face.outer_loop().half_edges())?; + for h in inner.iter_half_edges() { + self.write_vertex(face, h)?; + } + } + + for h in face.outer_loop().iter_half_edges() { + self.write_vertex(face, h)?; + } + + self.textures.local.clear(); + self.normals.local.clear(); + + writeln!(self.writer)?; + } + } + + for (u, vw) in &self.textures.items { + write!(self.writer, "vt {u}")?; + if let Some((v, w)) = vw { + write!(self.writer, " {v}")?; + if let Some(w) = w { + write!(self.writer, " {w}")?; + } + } + writeln!(self.writer)?; + } + + for (x, y, z) in &self.normals.items { + writeln!(self.writer, "vn {x} {y} {z}")?; + } + + Ok(()) + } + + fn write_vertex( + &mut self, + face: lens!(Face), + half_edge: lens!(HalfEdge), + ) -> std::io::Result<()> { + let vert = half_edge.origin(); + write!(self.writer, " {}", self.pos_ids[&vert.id()])?; + + let t = self.textures.add(face, vert.id(), vert.data()); + let n = self.normals.add(face, vert.id(), vert.data()); + + if t.is_some() || n.is_some() { + write!(self.writer, "/")?; + } + + if let Some(t) = t { + write!(self.writer, "{t}")?; + } + + if let Some(n) = n { + write!(self.writer, "/{n}")?; + } + + Ok(()) + } +} diff --git a/src/obj_import.rs b/src/obj_import.rs new file mode 100644 index 0000000..577fa1e --- /dev/null +++ b/src/obj_import.rs @@ -0,0 +1,187 @@ +use crate::*; +pub use obj; +use obj::raw::object::RawObj; + +#[derive(Debug, Error)] +pub enum ObjImportError { + #[error("vertex position index out of bounds")] + InvalidPositionIndex, + #[error("half-edge between vertices {0} and {1} appears twice")] + SameHalfEdge(usize, usize), + #[error("half-edge between vertices {0} and {1} does not have a twin")] + UnclaimedHalfEdge(usize, usize), + #[error("empty face")] + EmptyFace, + #[error("vertex is not connected to any edges")] + StandaloneVertex, +} + +use ObjImportError::*; + +pub struct ObjImport<'tok, 'brand, 'arena, V> { + dcel: &'tok mut Dcel<'brand, 'arena, V>, + obj: &'tok RawObj, + shell: ptr!(Shell), + half_edges: HashMap<(usize, usize), Option>, + vertices: Vec, +} + +struct CyclicWindows { + first: Option, + last: Option, + iter: I, +} + +fn cyclic_windows(iter: I) -> CyclicWindows { + CyclicWindows { + first: None, + last: None, + iter, + } +} + +impl Iterator for CyclicWindows +where + T: Clone, + I: Iterator, +{ + type Item = (T, T); + + fn next(&mut self) -> Option { + let Some(item) = self.iter.next() else { + let first = self.first.take()?; + let last = self.last.take()?; + return Some((last, first)); + }; + + self.first.get_or_insert_with(|| item.clone()); + let Some(last) = self.last.replace(item.clone()) else { + return self.next(); + }; + + Some((last, item)) + } +} + +impl<'tok, 'brand, 'arena, V> ObjImport<'tok, 'brand, 'arena, V> { + pub fn import( + dcel: &'tok mut Dcel<'brand, 'arena, V>, + obj: &'tok RawObj, + fun: impl Fn((f32, f32, f32, f32)) -> V, + ) -> Result { + let body = dcel.new_body(); + let shell = *body.add_new_shell(dcel); + + let vertices = obj + .positions + .iter() + .map(|&x| *shell.add_new_vertex(fun(x), dcel)) + .collect(); + + let mut imp = ObjImport { + dcel, + obj, + shell, + half_edges: HashMap::new(), + vertices, + }; + + match imp.import_faces() { + Ok(_) => Ok(body), + Err(x) => { + body.destroy(dcel); + Err(x) + } + } + } + + fn iter_polygon( + p: &obj::raw::object::Polygon, + ) -> impl Iterator + DoubleEndedIterator + '_ { + use either::{Left, Right}; + use obj::raw::object::Polygon::*; + + match p { + P(v) => Left(Left(v.iter().cloned())), + PT(v) => Left(Right(v.iter().map(|&(x, _)| x))), + PN(v) => Right(Left(v.iter().map(|&(x, _)| x))), + PTN(v) => Right(Right(v.iter().map(|&(x, _, _)| x))), + } + } + + fn import_faces(&mut self) -> Result<(), ObjImportError> { + for p in self.obj.polygons.iter() { + if cyclic_windows(Self::iter_polygon(p)) + .any(|(a, b)| matches!(self.half_edges.get(&(a, b)), Some(None))) + { + self.import_face(Self::iter_polygon(p).rev())?; + } else { + self.import_face(Self::iter_polygon(p))?; + } + } + + if let Some((k, _)) = self.half_edges.iter().find(|(_, v)| v.is_some()) { + Err(UnclaimedHalfEdge(k.1 + 1, k.0 + 1)) + } else if self + .vertices + .iter() + .any(|x| x.maybe_outgoing(self.dcel).is_none()) + { + Err(StandaloneVertex) + } else { + Ok(()) + } + } + + fn add_half_edge( + &mut self, + loop_: ptr!(Loop), + prev: Option, + vertices: [usize; 2], + ) -> Result { + use std::collections::hash_map::Entry::*; + + let [a, b] = vertices; + let v = *self.vertices.get(a).ok_or(InvalidPositionIndex)?; + + let he = match self.half_edges.entry((a, b)) { + Occupied(mut e) => e.get_mut().take().ok_or(SameHalfEdge(a + 1, b + 1))?, + Vacant(e) => { + let (_, [he1, he2]) = Edge::create(self.shell, self.dcel); + e.insert(None); + self.half_edges.insert((b, a), Some(he2)); + he1 + } + }; + + he.update_origin(v, self.dcel); + he.set_loop_(loop_, self.dcel); + + if let Some(prev) = prev { + self.dcel.follow(prev, he); + } + + Ok(he) + } + + fn import_face(&mut self, mut it: impl Iterator) -> Result<(), ObjImportError> { + let face = *self.shell.add_new_face(self.dcel); + let loop_ = *Loop::new(self.dcel); + loop_.set_face(face, self.dcel); + face.set_outer_loop(loop_, self.dcel); + + let fv = it.next().ok_or(EmptyFace)?; + let (fe, le, lv) = it.try_fold((None, None, fv), |(fe, le, a), b| { + let he = self.add_half_edge(loop_, le, [a, b])?; + Ok((fe.or(Some(he)), Some(he), b)) + })?; + + let fe = fe.ok_or(EmptyFace)?; + let le = self.add_half_edge(loop_, le, [lv, fv])?; + self.dcel.follow(le, fe); + + loop_.set_half_edges(fe, self.dcel); + + Ok(()) + } +} -- cgit v1.2.3