Custom NGon meshes and their normals

Hi Daniel,

I’ve been exploring Plankton for a couple of days now and I am very happy with it, although I hit a small wall when I tried to work with custom NGon meshes. I’m feeding Plankton the list of vertices (no duplicates) and the faces (an ordered list of indices indicating the respective vertex in the list.

Note that the order in which I’m feeding the indices to create faces is not always counter-clockwise. I then tried compiling and using Plankton 0.3.4.0 to get vertex normals, but it fails. (When trying to download version 0.3.4 from github I am still getting the .dll from version 0.3.0). I therefore tried creating my own method to find them, but as you can see in the picture they are not pointing toward the same side of the mesh. My guess is that some faces are oriented wrong because their vertices are not supplied in the same order as the vertices of neighboring faces. This in turn breaks the interdependencies of the halfedge data structure and makes it impossible to navigate the mesh. If this is the case, is Plankton able to rebuild the halfedge data structure and unify the face orientations, normals and halfedge directions (counter-clockwise) for the whole mesh?

Thank you!

Replies to This Discussion

Permalink Reply by Will Pearson on April 25, 2015 at 6:43pm

Hi Marko,

Plankton is designed to work with orientable, manifold meshes, meaning that the faces must all be ordered in the same direction so that there is a definite "front" and "back" to the mesh. If two adjacent faces are oriented differently, you would end up with the shared edge having two halfedges that are aligned, not opposites as they should be (below).

One suggestion, if all the faces lie roughly in the same plane (as it seems they do in the above image) you could preprocess your face-vertex lists to orient all the faces in the same direction, thus ensuring that the Plankton mesh can be built. To do this take the first three vertex positions in each face-vertex list (A, B and C) and calculate (B-A)x(C-B). This cross product will give you a vector that follows the right hand screw rule – i.e. a rough normal. Use this as a guide as to which face-vertex lists need reversing!

Looks like we forgot to update the version when we released v0.3.4 – whoops!

Please ask if you need any clarification on the above :)

Permalink Reply by Marko Tomicic on April 26, 2015 at 3:35am

Hi Will,

thanks for your input. I am looking more for a general solution to this problem which will work with any mesh that I supply as a list of closed polylines and I hoped that you solved this in plankton so that I don't have to do it :-) Nevermind, I'll figure it out.

Cheers,

Marko

P.S. I must say, I am really happy with how Plankton performs from the point when I feed it a good mesh. Thank you guys for making and maintaining this library!

P.P.S. Are you going to update the Plankton.dll at https://github.com/meshmash/Plankton/releases to 0.3.4 ?

Permalink Reply by Will Pearson on April 28, 2015 at 7:44am

Thanks for the kind words. Glad Plankton is proving useful. I'm not going to update the current release because it's actually the correct DLL, it just has the wrong AssemblyVersion.

Thinking out loud here but maybe it helps you... So you have an array of arrays of ordered vertex indices. How about recursively traversing the original face-vertex data structure using the edges (i.e. pairs of vertex indices) to find adjacent faces. Starting with any face, mark it as done and take each pair of vertex indices in turn and search for this consecutive pair across the rest of the ragged array to find the adjacent face, if one exists. For each pair, search initially for the pair in reverse order (i.e. given indices 5 and 8, search for 8 and 5). If you find a face on the first pass, mark it as done and move onto the next consecutive index-pair of the original face. If not, you should search for the index-pair in order and if you find the associated face (making sure it's not the one you're search from!) you need to to flip it (i.e. reverse the order of its vertex indices) and mark it as done. The trick, I think, is in writing this as a self-contained function so that it can be called recursively – each time you mark a face as done you should call the function on that face, searching for adjacent faces and flipping them where necessary.

This won't be super fast because you're layering O(n) searches on top of one another, but I think it'll get the job done. I'm assuming no degenerate faces and no disjoint meshes, although the latter can be dealt with easily (kind of, but that's another matter!).

Permalink Reply by Marko Tomicic on June 25, 2015 at 8:39am

Thank you for the advice. It helped me to orient the faces properly!

Permalink Reply by DAFIK SMAK on September 4, 2015 at 12:27am