How to implement an half-edge data structure in Haskell?

For a description of the data structure see

• http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml
• http://www.cgal.org/Manual/latest/doc_html/cgal_manual/HalfedgeDS/Chapter_main.html

An half-edge data 开发者_JAVA技巧structure involves cycles.

• is it possible to implement it in a functional language like Haskell ?
• are mutable references (STRef) to way to go ?

Thanks

In order to efficiently construct half-edge data structures you need an acceleration structure for the HE_vert (let's call it HE_vert_acc... but you can actually just do this in HE_vert directly) that saves all HE_edges that point to this HE_vert. Otherwise you get very bad complexity when trying to define the "HE_edge* pair" (which is the oppositely oriented adjacent half-edge), e.g. via brute-force comparison.

So, making a half-edge data structure for a single face can easily be done with the tying-the-knot method, because there are (probably) no pairs anyway. But if you add the complexity of the acceleration structure to decide on those pairs efficiently, then it becomes a bit more difficult, since you need to update the same HE_vert_acc across different faces, and then update the HE_edges to contain a valid pair. Those are actually multiple steps. How you would glue them all together via tying-the-knot is way more complex than constructing a circular doubly linked list and not really obvious.

Because of that... I wouldn't really bother much about the question "how do I construct this data structure in idiomatic haskell". I think it's reasonable to use more imperative approaches here while trying to keep the API functional. I'd probably go for arrays and state-monads.

Not saying it isn't possible with tying-the-knot, but I haven't seen such an implementation yet. It is not an easy problem in my opinion.

EDIT: so I couldn't let go and implemented this, assuming the input is an .obj mesh file.

My approach is based on the method described here https://wiki.haskell.org/Tying_the_Knot#Migrated_from_the_old_wiki, but the one from Andrew Bromage where he explains tying the knots for a DFA without knowing the knots at compile-time.

Unfortunately, the half-edge data structure is even more complex, since it actually consists of 3 data structures.

So I started with what I actually want:

data HeVert a = HeVert {
    vcoord  :: a        -- the coordinates of the vertex
  , emedge  :: HeEdge a -- one of the half-edges emanating from the vertex
}

data HeFace a = HeFace {
  bordedge :: HeEdge a -- one of the half-edges bordering the face
}

data HeEdge a = HeEdge {
    startvert :: HeVert a          -- start-vertex of the half-edge
  , oppedge   :: Maybe (HeEdge a)  -- oppositely oriented adjacent half-edge
  , edgeface  :: HeFace a          -- face the half-edge borders
  , nextedge  :: HeEdge a          -- next half-edge around the face
}

The problem is that we run into multiple issues here when constructing it efficiently, so for all these data structures we will use an "Indirect" one which basically just saves plain information given by the .obj mesh file.

So I came up with this:

data IndirectHeEdge = IndirectHeEdge {
    edgeindex  :: Int  -- edge index
  , svindex    :: Int  -- index of start-vertice
  , nvindex    :: Int  -- index of next-vertice
  , indexf     :: Int  -- index of face
  , offsetedge :: Int  -- offset to get the next edge
}

data IndirectHeVert = IndirectHeVert {
    emedgeindex  :: Int    -- emanating edge index (starts at 1)
  , edgelist     :: [Int]  -- index of edge that points to this vertice
}

data IndirectHeFace =
  IndirectHeFace (Int, [Int]) -- (faceIndex, [verticeindex])

A few things are probably not intuitive and can be done better, e.g. the "offsetedge" thing. See how I didn't save the actual vertices anywhere. This is just a lot of index stuff which sort of emulates the C pointers. We will need "edgelist" to efficiently find the oppositely oriented ajdgacent half-edges later.

I don't go into detail how I fill these indirect data structures, because that is really specific to the .obj file format. I'll just give an example on how things convert.

Suppose we have the following mesh file:

v 50.0 50.0
v 250.0 50.0
v 50.0 250.0
v 250.0 250.0
v 50.0 500.0
v 250.0 500.0
f 1 2 4 3
f 3 4 6 5

The indirect faces will now look like this:

[IndirectHeFace (0,[1,2,4,3]),IndirectHeFace (1,[3,4,6,5])]

The indirect edges:

[IndirectHeEdge {edgeindex = 0, svindex = 1, nvindex = 2, indexf = 0, offsetedge = 1},
IndirectHeEdge {1, 2, 4, 0, 1},
IndirectHeEdge {2, 4, 3, 0, 1},
IndirectHeEdge {3, 3, 1, 0, -3},
IndirectHeEdge {0, 3, 4, 1, 1},
IndirectHeEdge {1, 4, 6, 1, 1},
IndirectHeEdge {2, 6, 5, 1, 1},
IndirectHeEdge {3, 5, 3, 1, -3}]

And the indirect vertices:

[(1,IndirectHeVert {emedgeindex = 0, edgelist = [3]}),
(2,IndirectHeVert {1, [0]}),
(3,IndirectHeVert {4, [7,2]}),
(4,IndirectHeVert {5, [4,1]}),
(5,IndirectHeVert {7, [6]}),
(6,IndirectHeVert {6, [5]})]

Now the really interesting part is how we can turn these indirect data structures into the "direct" one we defined at the very beginning. This is a bit tricky, but is basically just index lookups and works because of laziness.

Here's the pseudo code (the actual implementation uses not just lists and has additional overhead in order to make the function safe):

indirectToDirect :: [a]   -- parsed vertices, e.g. 2d points (Double, Double)
                 -> [IndirectHeEdge]
                 -> [IndirectHeFace]
                 -> [IndirectHeVert]
                 -> HeEdge a
indirectToDirect points edges faces vertices
  = thisEdge (head edges)
  where
    thisEdge edge
      = HeEdge (thisVert (vertices !! svindex edge) $ svindex edge)
               (thisOppEdge (svindex edge) $ indexf edge)
               (thisFace $ faces !! indexf edge)
               (thisEdge $ edges !! (edgeindex edge + offsetedge edge))
    thisFace face = HeFace $ thisEdge (edges !! (head . snd $ face))
    thisVert vertice coordindex
      = HeVert (points !! (coordindex - 1))
               (thisEdge $ points !! (emedgeindex vertice - 1))
    thisOppEdge startverticeindex faceindex
      = thisEdge
        <$>
        (headMay
          . filter ((/=) faceindex . indexf)
          . fmap (edges !!)
          . edgelist         -- getter
          $ vertices !! startverticeindex)

Mind that we cannot really make this return a "Maybe (HeEdge a)" because it would try to evaluate the whole thing (which is infinite) in order to know which constructor to use. I had to add a NoVert/NoEdge/NoFace constructor for each of them to avoid the "Maybe".

Another downside is that this heavily depends on the input and isn't really a generic library thing. I'm also not entirely sure if it will re-evaluate (which is still very cheap) already visited edges.

Using Data.IntMap.Lazy seems to increase performance (at least for the list of IndirectHeVert). Data.Vector didn't really do much for me here.

There's no need for using the state monad anywhere, unless you want to use Arrays or Vectors.

Obviously the problem is that a half-edge references the next and the opposite half-edge (the other references are no problem). You can "break the cycle" e.g. by referencing not directly to other half-edges, but to reference just an ID (e.g. simple Ints). In order to look up a half-edge by ID, you can store them in a Data.Map. Of course this approach requires some book-keeping in order to avoid a big hairy mess, but it is the easiest way I can think of.

Stupid me, I'm not thinking lazy enough. The solution above works for strict functional languages, but is unnecessary for Haskell.

If the task in question allows you to build the half-edge structure once and then query it many times, then lazy tying-the-know approach is the way to go, as was pointed out in the comments and the other answer.

However, if you want to update your structure, then purely-functional interface might prove cumbersome to work with. Also, you need to consider O(..) requirements for update functions. It might turn out that you need mutable internal representation (probably with pure API on top) after all.

I've run into a helpful application of polymorphism for this sort of thing. You'll commonly desire both a static non-infinite version for serialization, as well as a knot-tyed version for internal representation.

If you make one version that's polymorphic, then you can update that particular value using record syntax :

data Foo edge_type_t = Depot {
   edge_type :: edge_type_t,
   idxI, idxE, idxF, idxL :: !Int
} deriving (Show, Read)

loadFoo edgetypes d = d { edge_type = edgetypes ! edge_type d }
unloadFoo d = d { edge_type = edgetype_id $ edge_type d }

There is however one major caveat : You cannot make a Foo (Foo (Foo( ...))) type this way because Haskell must understand the type's recursively. :(