# immutable half-edge data structure

8 messages
Open this post in threaded view
|

## immutable half-edge data structure

 I realize there are many advantages to immutable data structures and scala provides many different classes with immutable functionality like the List.  However, I can't seem to wrap my head around some more complex data structures that are interconnected at so many instances. One in particular is with polygonal models using the half-edge data structure. http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtmlI've implemented this several times before, but working with these structures with immutable classes seems incredibly complex especially if they're referenced by index instead of class reference. For a polygonal mesh, a vertex has an coordinate and a reference to one of the edges it touches a face and a reference to one of it's edges a edge has a reference to the next edge on the same face, the edge on the adjacent face, the first vertex of the edge, and a reference to the the face itself that it lies on If each one of these references is stored as an integer keyed to a hashmap, each would probably need a reference to the mesh holding the hashmaps of vertices, faces, and edges as well.  That seems to make sense, but it makes manipulating the geometry extremely tedious.  As a simple example, one might need to extrude a face on the top of a cube.  So, four new vertices would need to be created, but since no edges are made yet, they're just dummy vertices classes I'll have to recreate later when I have references to the edges and faces and vice versa. I assume this kind of thing is handled already in functional programming when doing anything graph related, but I'd appreciate some advice or references to good reading material on handling these kind of problems in a functional way.  This is more of a general functional programming question, but I'm trying to implement it specifically in scala. Josh
Open this post in threaded view
|

## Re: immutable half-edge data structure

 On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben
Open this post in threaded view
|

## Re: immutable half-edge data structure

 If Scala had write-once vals - I think that would solve the problem with constructing immutable data with cyclical references.Using write-once vals you could construct the data graph and once all references have stabilised to their final states you can then expose it to the world and take advantage of all the benefits that immutability gives you. Note that "lazy vals" don't fill this hole.Ishaaq2009/11/2 Ben Hutchison On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state  However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben
Open this post in threaded view
|

## Re: immutable half-edge data structure

 In reply to this post by Ben Hutchison-3 It is perfectly possible to create cycles with lazy structures.On Mon, Nov 2, 2009 at 3:01 AM, Ben Hutchison wrote: On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state  However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben -- Daniel C. SobralSomething I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.
Open this post in threaded view
|

## Re: immutable half-edge data structure

Open this post in threaded view
|

## Re: immutable half-edge data structure

 On Nov 2, 2009, at 7:40 PM, Ishaaq Chandy wrote:http://www.haskell.org/haskellwiki/Tying_the_KnotHowever, my haskell-foo isn't quite there yet - can someone please translate?I’m sure someone can write a tidier example, but off the cuff, something like the below. Note how the geta “thunk” is, crucially, in the same scope as the value ‘a’ that it returns.object Example {  case class A(val b: B)  case class B(_a: () => A) {    def a = _a()  }    val geta: () => A = () => a  val b = new B(geta)  val a = new A(b)   println(b)  println(a)  println(a.b)  println(b.a)}
Open this post in threaded view
|

## Re: immutable half-edge data structure

 On Tue, Nov 3, 2009 at 3:07 AM, Aaron Harnly <[hidden email]> wrote: > I’m sure someone can write a tidier example, but off the cuff, something > like the below. Note how the geta “thunk” is, crucially, in the same scope > as the value ‘a’ that it returns. The principle is the same, but here no explicit thunk is needed, scala> trait A { val b : B } ; trait B { val a : A } defined trait A defined trait B scala> val a = new A { thisA => val b = new B { val a = thisA } } a: \$anon forSome { type \$anon <: java.lang.Object with A{def b: java.lang.Object with B{def a: \$anon}} } = \$anon\$1@266b44 scala> a.b res0: java.lang.Object with B{def a: \$anon} = \$anon\$1\$\$anon\$2@6743e2 scala> a.b.a res1: \$anon = \$anon\$1@266b44 scala> a.b.a.b res2: java.lang.Object with B{def a: \$anon} = \$anon\$1\$\$anon\$2@6743e2 Cheers, Miles -- Miles Sabin tel: +44 (0)7813 944 528 skype:  milessabin http://www.chuusai.com/http://twitter.com/milessabin
Open this post in threaded view
|

## Re: immutable half-edge data structure

 In reply to this post by Ben Hutchison-3 I agree with Ben, immutability is not appropriate everywhere.2009/11/2 Ben Hutchison [snip] Is the essence of your problem Cyclic References? Yes, i think this is the essence, and if I'm not mistaken, the biggest problem whith them is that there is no data sharing at all in a immutable variant of a circular data structure.  E.g. Here is a list   scala> val a = List(1,2,3)   a: List[Int] = List(1, 2, 3) Update the first element   scala> val b = 0 :: a.tail    b: List[Int] = List(0, 2, 3)Most of the data is still represented with the same objects    scala> a.tail eq b.tail   res3: Boolean = true       But this wouldn't be the case for e.g. circular lists: every cons-cell of a and b would be different objects. This carries over to the half-edge data structure where you can reach every element (face, half edge, vertex) from each other by pointer chasing. (Ouups, pointer, my C-heritage leaked through). So, e.g. when coloring the top of a white box black you end up in two separate sets of interconnected objects and, worse, when you build up such a graph one at a time you end up with a quadratic algorithm, at least in time. (The GC can rescue you from quadratic space consumption, I hope) In other words, translating that haskell-magic into scala wouldn't help much.Well as I said, if I am not mistaken.Greetings,Burkhard.