Internal data structure

Plankton 0.4.2. If I take any simple mesh object generated in grasshopper and convert it with the PMesh module, then try running the following python code, I get:



for v in range(pm.Vertices.Count):

    print (v, pm.Halfedges[pm.Vertices[v].OutgoingHalfedge].StartVertex)



(0, 0)

(1, 1)

(2, 2)

(3, 3)

(4, 4)



... etc

My understanding of the halfedge structure is that a vertex points to a halfedge, which points its other vertex (image linked). It seems these halfedges are pointing back to the vertices referencing them. What am I missing?

Replies to This Discussion

Permalink Reply by Will Pearson on November 26, 2018 at 7:09am

Hi Cory, you're correct – in Plankton, for any given halfedge the StartVertex property gives the index of the vertex from which the halfedge originates. I don't recall the reasoning behind this decision, unfortunately. To traverse from one vertex to another, you can use pm.Halfedges(int).GetPairHalfedge(int) to get the halfedge pair and, subsequently, it's StartVertex. Of course you have no control over which outgoing halfedge is referenced by each vertex... In case it's useful, I made a web page a few years ago to describe the Plankton data structure: https://www.pearswj.co.uk/halfedge/

Permalink Reply by Cory on November 26, 2018 at 7:58am

> Of course you have no control over which outgoing halfedge is referenced by each vertex...

This is actually what I was investigating. I have a mesh I had been doing some custom operations on, and had come to realize that Vertices.IsBoundary() was returning False for some of my boundary vertices. I read that it's important that each boundary vert's outgoing halfedge is on the boundary, if there is one, and it seems plankton makes this assumption as well. Though I fear I've created a broken mesh structure, for now I seem to be getting away with a workaround replacement for IsBoundary:

any(pm.Halfedges.IsBoundary(h) for h in pm.Vertices.GetHalfedgesCirculator(v))

But I'm concerned I may have more serious underlying issues I should address before moving forward.

Permalink Reply by Will Pearson on November 26, 2018 at 8:17am

Ah, yes... That's supposed to be an optimisation. Each operation (e.g. collapse/split edge) should ensure that it leaves the data structure in the correct state, with any boundary vertices pointing to a halfedge with no adjacent face. This keeps the IsBoundary() query fast.

If you use the pm.Vertices.Add() and pm.Faces.AddFace() helper methods when constructing your mesh then this should all be handled for you. If you add/delete/modify the halfedges yourself then you'll need to be careful!

Permalink Reply by Cory on November 26, 2018 at 8:39am

Can I simply modify which halfedge a vertex points to after my operation and not worry about that breaking anything else?

Permalink Reply by Will Pearson on November 27, 2018 at 11:28am

That should work just fine

RSS