Mesh Operators

[pearswj]

Use this pull request to discuss the new mesh operators, such as edge splits, face splits, edge collapses, etc...

[pearswj]

Just to re-add the comments I left here previously:

1. Move face split to PlanktonFaceList class.
2. Suggest rename of He_AroundFace(int, int) to GetNextHalfedge(int, int). Could also add GetNextHalfedge(int) which simply returns this[int].NextHalfedge. Same for previous halfedge too!

[pearswj]

@Dan-Piker A late night last night! Nice work, I'll test it when I get the chance. Might be useful to send a build over to Dave too.

A quick suggestion re: naming conventions. Following these guidelines, all local variables should be camelCase (instead of PascalCase, which is used for everything else). This helps to demonstrate the scope of the variable, otherwise you might get confused with public Fields and Properties which are available across all methods in the class. I've also adopted the use of "Halfedge" instead of "HalfEdge". We should be consistent but my only argument for using "Halfedge" is that I found it to be common across other libraries (such as OpenMesh). What do you think?

Just for future reference, I've also adopted the convention of prefixing any private fields with and underscore (i.e. _mesh).

[Dan-Piker]

@pearswj I just realized that as long as these dead items still exist in the mesh, we need to check for them when converting back to a RhinoMesh, because otherwise it gets stuck in the circulator. Thanks for the naming guidelines, I'd been wondering about that. I'll try and stick to these

[pearswj]

I just noticed that I've also used a bit of local_variable_name which I think is okay too. If you're using underscores like this, I think its best to keep it completely lowercase. The point is to make the code really easy to understand which I think is really important for an open source project.

And yes, the data structure needs to be able to handle dead items now. It's probably best that the circulators themselves do this. Quick question though, which is better: items with a dead flag or just null items?

[Dan-Piker]

I just added the check into RhinoSupport.cs, but on reflection it is probably better to put it in the circulators themselves as you say. On first tests it seems to be working.

[pearswj]

I'm still debating in my head whether it would be better to have a dead bool or simply set the item to null. There's a certain simplicity in the latter... As it stands there's nothing to stop you setting an item in any of the collections to null, so it needs handling either way. Either we disallow any item in the collections from being null, or we leave it as is and handle the null items in the circulators etc. What are your thoughts on this?

[Dan-Piker]

I can't immediately see any disadvantages to setting them to null instead of having the bool, and as you say - it does seem simpler

[pearswj]

I've invited Dave to weigh in on the subject too. I definitely think that the mesh element classes should remain as lightweight as possible as there could be a lot of them (in fact I'm considering changing them to structs, but don't worry about that now :-)).

On 23 August 2013 12:09, Daniel Piker notifications@github.com wrote:

I can't immediately see any disadvantages to setting them to null instead of having the bool, and as you say - it does seem simpler

— Reply to this email directly or view it on GitHubhttps://github.com/Dan-Piker/Plankton/pull/3#issuecomment-23157144 .

[pearswj]

What do you think about renaming TriangleSplitEdge(int) to SplitEdge(int, bool) where the bool determines whether or not to split the adjacent faces? Also I wonder whether it would be better to use two halfedges as the arguments for the face split, and let the user use the "around" helper if they so wish. Otherwise, it's a bit awkward in the case where you already know the two halfedges...you'd have to work out the number of steps between them.

You've probably already seen the link below, but just in case:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Polyhedron_ref/Class_Polyhedron_3.html

Just writing some unit tests for your new methods by the way! Edge split done. I'll do the face split soon. It's quite a good way to review your code actually.

[pearswj]

p.s. This work is awesome! The next release is going to be jam packed with new functionality. :+1: Also, I hope you don't mind if I attach your diagram here for safe keeping (and because it's very relevant and looks fantastic!)

Process: edge split, face split, face split, edge flip, edge flip.

[pearswj]

@davestasiuk See this comment above regarding the handling of dead items. I'm curious to know whether you would prefer having a dead flag in each item, or simply replacing it with null (in the list that contained it). I'm more inclined towards the simplicity of the latter, but either way the plan is to modify the data structure such that it can handle these dead items (i.e. pre-compaction).

[pearswj]

I've pushed my tests (plus a fixed bug in the face split) to my fork. Am I okay to go ahead and merge into this branch?

[Dan-Piker]

Yes, let's merge. Good catch on that face-split bug. This reminds me - if we do change from dead bools to nulls, must remember to move some lines in edge-collapse to the end of the method.

[pearswj]

Merged.

[Dan-Piker]

about renaming the TriangleSplitEdge - if we did do this to make it something that isn't restricted to triangles, it would need to be something like SplitEdge(int, int, int), giving the halfedge to split, and the two 'around' values, one for each adjacent face (or directly giving the indices of the halfedges to join to as you suggest), and if -1 is supplied then don't split the faces.

[pearswj]

I was thinking keep the behaviour in TriangleSplitEdge (i.e. going two steps around the face) but make it sound a bit more general. If the user wanted to do something more fancy they could do the edge split and the two face splits themselves. Unless you have a specific use case in mind already?

[Dan-Piker]

It's just that I can't currently think of any case where we would want the restriction to triangle input, but then output quads by not splitting the faces. For the use case I'm thinking of exactly the edge split shown in the 4th image here: http://spacesymmetrystructure.wordpress.com/2012/09/20/meshmash/

[pearswj]

This is what I had in mind if, for example, you called SplitEdge(int, true) on and edge that is adjacent to two quads...

...and if you called it on an edge adjacent to two triangles then you'd get the example in your blog post.

[davestasiuk]

@pearswj Regarding treating dead items as null...it's interesting, c# and vb.net deal with nulls differently, with c# definitely simpler and more direct. look here: http://www.techrepublic.com/article/working-with-null-values-in-the-net-framework/ My guess is that if someone using vb.net wanted to address the list items (someone like me) they could probably test if an object = nothing...but there is a wrinkle in vb that makes it possible to test for a couple of properties (both = nothing and dbnull) which is super annoying, My guess is that it would work just to test for nothing, but it's also worth noting that vb users tend to avoid nulls for this very reason. But I completely understand that making a dead object null is simpler for a variety of reasons on the development side of things.

[pearswj]

@davestasiuk Thanks for bringing that to my attention. I'll have to look into it further...

[pearswj]

@Dan-Piker What do you think about renaming RemoveEdge to JoinFaces or MergeFaces? This would still be specified by the edge which separates the two faces. Personally I think that it's better to remove faces or use operators than to add/remove edges directly. Also, a couple of notes on the implementation:

1. If you ensure that _mesh.Faces[keptFace].FirstHalfedge is valid (i.e. if it is index then make it _mesh.Halfedges[index].NextHalfedge, or something) then you can iterate over _mesh.Faces.GetHalfedgeCirculator(keptFace) and set each halfedge's adjacent face to keptFace. See PlanktonFaceList @ 6e24538 for an example.
2. I think it would be useful to create an internal "helper" method that deals with removing a halfedge pair from the mesh (by closing it out of the loop at either end) and then making sure that if a face referenced a halfedge in said pair that this reference was moved (to the halfedge's "next"?). Reusability is always good!

[Dan-Piker]

@pearswj I agree that MergeFaces is a better name. Also - there are can sometimes be edges which are ok to be collapsed but not removed: (and also boundary edges can never be removed - something which I think is more obvious when it is called MergeFaces) In this case we could either: -remove all the edges between the 2 faces -return a failure

[pearswj]

That's a tough one. On one hand I'm inclined to just write some clear documentation which explains what's happening and leave it to the user to make sure that the two faces are good candidates for merging. (They could always use an edge collapse before/after merging...) On the other hand, if you want to merge two faces, then you want to merge them and you don't want to be left with a weird halfedge pair that has the same face on each side...

Perhaps its another case of:

• MergeFaces(int) does the minimum necessary, and
• MergeFaces(int, bool) gives you the option to automatically tidy up cases like these (by first performing any necessary collapses and then calling MergeFaces(int))?

[pearswj]

Or we could just provide a public helper method to loop around a face and collapse the outgoing halfedge of any 2-valent vertices (or, better yet, that halfedge's pair)? No idea what to call such a method though...

[pearswj]

More updates in my fork along the lines of my earlier comments. I've tried to make everything line up with CGAL's implementation (although they store end vertices, which made it a bit confusing...). All covered by tests and commented verbosely.

I'm off to a hockey game in Oxford now, but we can talk briefly this evening if you're around. I'd be interested to hear from both of you how usable you think these operators would be in their current form.

Have a nice day :-).

[Dan-Piker]

@pearswj Good stuff - all very readable. CGAL's vertex join is not what I had in mind for EdgeCollapse though. We should be able to collapse edges adjacent to triangles, resulting in the triangular faces being removed, and also to collapse boundary edges, just not internal edges with 2 boundary vertices. The conditions for when a collapse is allowed are described here: http://w3.impa.br/~zang/pg2012/pg2012-slides.pdf#page=20 Enjoy the game!

[pearswj]

Am I understanding the behaviour correctly? I've drawn what I think would happen in a relevant scenario below:

Halfedge, h, collapsed causing face no. 3 to be removed and face no. 4 to be merged into face no. 5.

I'm in the middle of writing a test for the situation in the image above. My current implementation performs any necessary removals/merges prior to collapsing the edge.

[Dan-Piker]

Yes, exactly. and if there is a triangle on one side of the edge and a quad on the other, then the triangle gets removed, while the quad turns into a triangle:

[pearswj]

Yep. Face no. 4 would be automatically merged into face no. 5 before collapsing the edge. I'll finish writing this test and I'll update my fork...

[pearswj]

You probably won't get this until the morning now... but I just pushed the latest to my fork (compare). Talk soon.

[Dan-Piker]

@pearswj Brilliant!

[Dan-Piker]

Here's a variable level sqrt3 subdivision using the new stellate :)

[pearswj]

Have you been able to test the vertex split? Also, I just found a bug in the edge split. Pushing a fix (plus a bit of a tidy up) now...

[Dan-Piker]

@pearswj Good catch on the edge-split bug. No I hadn't tested the vertex split yet, I'll take a look

[pearswj]

Is there a use for a function which does the opposite of stellate? That is, one which takes a non-boundary vertex and merges all of its incident faces, leaving the vertex unused?

[Dan-Piker]

@pearswj Yes - that might come in handy for something. I keep thinking of all of this in the context of sphere/circle packing based remeshing. This could be like a sphere getting pushed out of the packing, to be followed by retriangulating the resulting face:

[pearswj]

Cool. I think that would round out the set of Euler operators quite nicely. By the way, how did you get on with playing around with the library? Aside from the awesome sqrt3 subdiv that is!

[pearswj]

I didn't see that circle packing image until just now. That's a neat way of looking at. Better add some more methods of triangulating faces to the wish list! Finished that erase center vertex method last night – pushing it to this branch now...

[Dan-Piker]

There seems to be some bug in CollapseEdge. I can't see yet what it is, but after collapsing any edge, converting back to RhinoMesh gives a mess.

[Dan-Piker]

Actually I realize now - the bug is not with CollapseEdge, but with how ToRhinoMesh deals with Dead vertices- by just skipping over them, the indexing of the face vertices gets messed up.

I see some possible solutions: 1 - Make the cleanup/reindexing method to clear all dead items from the mesh, and always call it at the start of ToRhinoMesh 2 - Still skip over dead vertices, but keep track of them and shuffle down any indices over that value when adding faces 3 - Add the dead vertices to the Rhino mesh, keeping track of their indices, then at the end, use Rhino's Mesh.Vertices.Remove

[pearswj]

Good catch, it's always tricky when the error's not where you think it is! Well, we definitely need a Compact() method on the mesh to clean out all the dead items and reindex the mesh. Calling that before ToRhinoMesh would be my preferred option.

[davestasiuk]

Hi Will-

I wonder if it might be possible to make the compact an option? I plan on hitching simulations to the PlanktonMesh, and having the redraw occur at every n timesteps, say...having the compact occur automatically at the time the mesh goes out would really slow this down quite a bit, I think...

On Tue, Aug 27, 2013 at 3:55 PM, Will Pearson notifications@github.comwrote:

Good catch, it's always tricky when the error's not where you think it is! Well, we definitely need a Compact() method on the mesh to clean out all the dead items and reindex the mesh. Calling that before ToRhinoMeshwould be my preferred option.

— Reply to this email directly or view it on GitHubhttps://github.com/Dan-Piker/Plankton/pull/3#issuecomment-23337878 .

[Dan-Piker]

I agree we need a method to compact, and I realize now the second method I described would be doing the same work. Much better to shift down vertex indices of halfedges than of faces, as there will be more of the latter. I share Dave's concern about speed though. How about - we keep a bodycount of how many dead vertices the mesh has (incrementing it whenever one is removed) then the compact only happens if this is >0

[Dan-Piker]

(and maybe still keeping the option to skip the compacting, and just output a RhinoMesh with some unused vertices)

[pearswj]

You raise a good point Dave. One option could be to do the conversion by adding every vertex ((0,0,0) for the dead ones maybe) and then only adding the faces that aren't dead (or null)? If it's only for visualisation, the unused vertices shouldn't matter...

On 27 August 2013 15:06, Daniel Piker notifications@github.com wrote:

I agree we need a method to compact, and I realize now the second method I described would be doing the same work. Much better to shift down vertex indices of halfedges than of faces, as there will be more of the latter. I share Dave's concern about speed though. How about - we keep a 'bodycount' of how many dead vertices the mesh has (incrementing it whenever one is removed) then the compact only happens if this is >0

— Reply to this email directly or view it on GitHubhttps://github.com/Dan-Piker/Plankton/pull/3#issuecomment-23338873 .

[Dan-Piker]

Rhino/GH don't even display unused vertices, unless you decompose the mesh, so I think it won't be a problem. It also has a MeshVertexList.CullUnused method

[pearswj]

Just pushed a quick implementation for compacting the vertex list. I thought it might give you some ideas for implementing the same for the halfedge and face lists. I figured we'd have internal helpers for each list and then call all three in a public Compact() method in the mesh class itself.

CullUnused() would also be a handy method to have in the vertex list. I think that an unused vertex should simply be one with its OutgoingHalfedge set to -1. Some of the methods, such as face removal (or maybe the edge removal helper), should be updated to leave a vertex in this state if its no longer part of the mesh topology. As for other methods, the jury on how to represent dead vertices is still out...

[pearswj]

Just found another interesting bug in the edge collapse...! Try stellating all the faces in a triangular mesh, then collapsing one of the original faces. A non-manifold edge is created! We should probably have a check for this situation and prevent the collapse from happening.

Now, the question is how to do that check in a concise way...

[Dan-Piker]

I think the conditions described here are what we need: http://w3.impa.br/~zang/pg2012/pg2012-slides.pdf#page=19

[pearswj]

Ah, this is the one you showed me before? Sorry!! I'll implement it after dinner.