Symmetry Fix Algorithm for 3D Meshes

Symmetry Fix Algorithm for 3D Meshes

Having been unable to find an existing solution for my case (3Ds Max + MaxScript) I have “invented” (On the internet everything is already invented if you search enough… I didn’t search enough) an algorithm to fix a 3D mesh issue where some of its vertices went out of symmetry.

The problem

Imagine that we have a 3D mesh that is supposed to be symmetrical: for example, a finished character that needs additional symmetrical adjustments. Or imagine it is time to create morph targets (blend shapes) and having a nice symmetrical head mesh would save you precious time. One condition is that you CAN’T break the mesh’s topology, because UV mapping is already done and/or morph targets depend on the original topology.

Then, for some unfortunate reason, some vertices are out of symmetry.

This could be fixed manually with the tedious process of copying a vertex coordinate, multiplying the X by -1 and pasting it to the other vertex that you identify visually as being the symmetrical pair. But this is very slow, and with more than 10 vertices, it is simply a nightmare. Today, we know how to code!

The starting point

Symmetry Fix Algorithm for 3D Meshes

The simplest case to pair vertices is just comparing the coordinates. That’s what the 3Ds Max tool “Symmetry Tools” does. In order to know if two vertices are symmetrical, you need to do this:

//pseudo-code: v is our array of vertices, i and j are indices

  reflected_Pos = v[i] * vector(-1,1,1)
  d = distance from reflected_Pos to v[j]
  if (d < Tolerance) then We Found our Brother!

We are assuming we want symmetry on the X-axis.  Multiplying a vertex position by a Vector (-1, 1,1) we get the position mirrored. Then, calculating the distance to the other vertex, we can detect if they are symmetrical pairs if distance = 0 or less than Tolerance. But if Tolerance is too high, this quickly breaks.

Let’s use our instincts, and take a second look at our first image. How does our brain know which vertices should be paired?

The solution

Symmetry Fix Algorithm for 3D Meshes

The answer is because we are instinctively comparing their relationship with neighbor vertices. So from the image above we can pair E with E’, since all the connections of E correspond to the same connections of E’ in the mirrored side.

E.connections = A, B, C, D
E'.connections = A', B', C', D'

Note that C and C’ are special cases, since the X is zero we can (and should) say that the vertex C is paired to itself.

Now your mind will start finding many cases where this will not work! And that’s true. This method is to find the best solution, not the perfect one. Sometimes the solution simply doesn’t exist.

The next most immediate issue will come when some of the neighbor vertices are also unpaired.

Symmetry Fix Algorithm for 3D Meshes

When we are testing for E and E’ it may happen that we don’t know if A and A’ are pairs or not. What to do? Just don’t care… or wait, that’s useful info too.

E.connections = B, C, D, (1 unpaired)
E'.connections = B', C', D', (1 unpaired)

Don’t try to find E‘s mirrored brother (E’),  just find the best candidate to be E‘s mirrored brother.  Then if we have two potential candidates to be E’, with the same set of connections (but the first one has 2 unpaired connections and the second one has 1 unpaired connection), the second one wins the contest because it best matches the characteristics of E.

Letting our thoughts fly, this can lead us to generalize and look for other characteristics of the vertices that could be mirrored and added to this “description” such as normals, skin weights… but let’s keep it simpler for now and for good.

The code

proSymmetryTool
proSymmetryTool in action for 3Ds Max

Let’s see our symmetry fixer working now. It does it with passes, and for every pass that pairs are found more useful connections will be used on the next pass until it runs out of good findings.

NOTE: I have to admit I have failed writing a pseudo code before linking it to the source, but after rewriting it 2 times I never was satisfied with the complexity of the text. So, I’ll invite you to take a better look at the working source.

The implementation I did was for 3Ds Max using MaxScript, a tool that I call proSymmetryTool that also adds more functionality for 3Ds Max users that I plan to talk more about later in this blog. Now anyone can see or download it for free here on Github. Our function of interest is “function FindPairs EPolyObj” and for convenience, I have extracted it here as a gist. But I hope with the explanation above in this article you can have fun implementing this algorithm yourself in any other language. Ask me anything in the comments section.

 

Share

Popular Today

  • Free Low Poly Donald Trump 3D CharacterFree Low Poly Donald Trump 3D Character Low Poly Donald Trump 3D Character is a minimalist artistic representation inspired by the most relevant features of the real person. It is rigged in 3Ds Max and ready to use for animations and games. It also includes FBX format and Unity Demo. Brought for you by me, for FREE…
  • 3ds Max PNG Alpha Transparency and Anti-Alias Problem (SOLVED)3ds Max PNG Alpha Transparency and Anti-Alias… With every new year and every 3Ds Max Version, I try again to understand why this is never fixed and how to find a better solution to this annoying issue. It is simple (or should be simple) if you have an image with transparency info (alpha channel) and you want…
  • Fix Non-Symmetrical Vertices of 3Ds Max Mesh to use with Symmetry Tool (SCRIPT: pXSymmetryTool)Fix Non-Symmetrical Vertices of 3Ds Max Mesh to use… Imagine you want to use the useful Symmetry Tool dialog in 3Ds Max to create Morph Targets, and when you select your model it detects many vertices as non-symmetrical. To fix that manually is painful and I couldn't find any quick solution out there. Then, I made this script. It…

Leave a Reply