immutable half-edge data structure

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

immutable half-edge data structure

Josh Stratton
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.shtml

I'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 <x,y,z> 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
Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Ben Hutchison-3
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
Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Ishaaq Chandy
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.

Ishaaq

2009/11/2 Ben Hutchison <[hidden email]>
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

Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Daniel Sobral
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 <[hidden email]> 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. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.
Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Ishaaq Chandy
Ok, your post prompted me to search on google and I found this:

http://www.haskell.org/haskellwiki/Tying_the_Knot

However, my haskell-foo isn't quite there yet - can someone please translate?

Ishaaq

2009/11/3 Daniel Sobral <[hidden email]>
It is perfectly possible to create cycles with lazy structures.


On Mon, Nov 2, 2009 at 3:01 AM, Ben Hutchison <[hidden email]> 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. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Aaron Harnly-2-2

On Nov 2, 2009, at 7:40 PM, Ishaaq Chandy wrote:
http://www.haskell.org/haskellwiki/Tying_the_Knot

However, 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)
}


Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Miles Sabin
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
Reply | Threaded
Open this post in threaded view
|

Re: immutable half-edge data structure

Burkhard Ludwig
In reply to this post by Ben Hutchison-3
I agree with Ben, immutability is not appropriate everywhere.

2009/11/2 Ben Hutchison <[hidden email]>
[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.