Symmetry Fix Algorithm for 3D Meshes

Symmetry Fix Algorithm for 3D Meshes

Not founding an existing solution on 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 that some of it’s vertices went out of symmetry.

The problem

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

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

This could be fixed manually with tedious process of copying a vertex coordinate, multiply the X by -1 and paste 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 is just a nightmare. But 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 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 the symmetry by the X axis.  Multiplying a vertex position by 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.

Lets use our instincts, and take a second look to our first image. How our brain knows which vertices should be paired?

The solution

Symmetry Fix Algorithm for 3D Meshes

Because we are instinctively also comparing their relationship with neighbor vertices. So from the image above we can pair E with E’, since all the connections of E corresponds 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 case, 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’ happens 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 mirrored brother (E’),  just find the best candidate to be E mirrored brother.  Then if we have two potential candidates to be E’, with the same set of connections but first one has  2 unpaired connections and the second one has 1 unpaired connection.  The second one wins the contest because it matches better the characteristics of E.

Letting our thoughts fly this can lead us generalize, and look for other characteristics of the vertices that could be mirrored and added to this “description”, like 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 run out of good findings.

NOTE: I have to admit I have failed writing a pseudo code, before linking to the source, but after rewritting it 2 times I never got satified with the complexity of the text. So, I’ll invite you better to take a 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 conveniece I have extrated it here as a gist. But I hope with the explanation above in this article you can have fun implementing yourself this algorithm in any other language. Ask me anything in the comments section.

 

Share

Popular Today

  • Free Lowpoly Donald Trump 3D CharacterFree Lowpoly Donald Trump 3D Character Lowpoly Donald Trump 3D Character is a minimalist artistic representation inspired by the most relevant features of the real person. Rigged in 3ds Max and ready to use for animations and games. Includes FBX format and Unity Demo. Brought for you, by me, for FREE download using Creative Commons Attribution…
  • Free Donald Trump High Quality 3D CaricatureFree Donald Trump High Quality 3D Caricature Many people are saying, this is the best 3D Trump caricature of the Internet. Believe me.  After 2 years on  TurboSquid it has more downloads than any other president ever, specially Obama. Winning bigly! Today on CyberMonday we're going to make Trump 3D Model free. Denys is tired of winning, he's a…

Leave a Reply