View Full Version : Fixing faces with more than 5 sides

06 June 2012, 02:54 AM
I'm not sure if this has been done before or not but I'm trying to fix faces with more than 5 sides with the following algorithm in python (assuming that the neighbouring faces are all ok):
1. for a n-sided face, pick a vert with ID x (vert x) and a vert that is floor(n/2) neighbors away (vert y) and create an edge between them (polysplit)
1.a. If n is odd and n>5 then add another edge between the vert y and the vert 2 neighbors away that will create a face with 3 sides which is alright.
2. do a loop for b times where b=floor(n/2)-3 . for each loop iteration, do the following:
2.a. start at the verts that is 2 neighbours away (left and right) from vert x and create an edge that intersect the edge that was created in step 1; and keep on doing it for every vert that is 1 neighbour away (left and right) from the previous iteration (if any)
I've attached the image as an example of some n-sided faces with the sequence the edges are added.
My question is if there is something out there that already does something like this? Also, every time I do a polySplit, the ID of the verts and edges keep changing, if there a way to make sure that the variables keep track of the changing ID? Is there a better way to create the edges for this other than polySplits since I have to keep track of the edges that are connected to the verts

06 June 2012, 06:59 AM
How about just selecting the faces and do Mesh> Triangulate?

All you examples are fairly simple where the polygon is convex. In that case you can simply connect one vertex to all the others.
I'm not sure why adding edges changes your vertex ids; it doesn't sound natural.

06 June 2012, 07:16 AM
Thanks for the reply but triangulate might create verts in that face that have more than 5 edges connected to it whereas this algoritm doesn't do that (this is the assumption that the existing verts are only connected to only 1 edge outside the face).
Also, yes, I can do it manually but the problem is that I have hundreds (maybe even thousands) of faces like this of various n-sides, so maybe I thought it would be better to script it.
Also, if the face is more than 8 sides, it does add a vert (because of the intersecting edges) and therefore creates a new vert and for some reason the vert ID gets shuffled. Also when I add the edge, the existing ID get shuffled around (same for the face ID as well)

06 June 2012, 12:09 PM
triangulate will never create or add a vertex, and if you ever add any verts you are doing it wrong.

either use Mesh > Cleanup... and don't code anything, or, if you do want to code it for some reason, use selectionConstraints to select the faces with more than 4 sides, triangulate then quadrangulate (if you don't want triangles).

There shouldn't be a reason why the above won't work properly (apart from seriously corrupt geometry)

06 June 2012, 07:23 PM
I am with Nathan on this.

I never meant for you to do anything manually. If there is one good thing in maya, it's that almost everything that can be done manually, can be done programmatically. The first thing to do is turn echo on in the script editor (actually not needed in this case), then do manually mesh> triangulate, and see in the script editor the source code for it.

In 3D most edges permutations are valid (intersection free), but it is customary to project the polygon to 2D and then triangulate, and I suppose that maya already does it for you. When you triangulate something, as Nathan said you never need to add vertices, and there is always a valid triangulation (intersection free). Maya is not sophisticated ( :surprised ), but if you used external libs, you could pursue delaunay triangulation.

So again, what I suggest for you is to go over you polygons in a loop, and send each face to polyTriangulate (or why not the whole mesh in one shot?). If you still have a problem, such as vertices were added, vertices changed their ids, the triangulation is intersecting, then please attach your source code with the problematic mesh.

EDIT: @traltixxx (, you know what, before you start doing anything, manually: select your mesh, then mesh> triangulate, and tell me if you still need anything else.

06 June 2012, 01:19 AM
Thanks for the suggestions guys. The triangulate & quadrulate works only sometimes; I just tried to triangulate and quad an octagon (or any even sided polygon-face) and sometimes instead of creating all 4-sided faces, it sometimes creates 2 triangles. For example, on the 10-sided face the triangulate+quad instead of making 6 4-sided faces, it created 2 triangles and 3 4-sided faces; though it does work for polygons with odd-faces.
Also, I noticed with triangulate and/or quad, it doesn't create new verts.
Anyway, I'll try and see if there are any other way to do this without coding.
Thanks again

06 June 2012, 04:12 AM
I tried to reproduce your problem for octagon:

polyCone -r 1 -h 2 -sx 20 -sy 1 -sz 0 -ax 0 1 0 -rcp 0 -cuv 3 -ch 1;
setAttr "polyCone1.subdivisionsAxis" 8;
select -r pCone1.f[1:8] ;
select -r pCone1.f[0] ;
polyTriangulate -ch 1 pCone1.f[0];

But I can't see any problem - one vertex is connected to all the others.
Please show a specific example that you deem problematic.

06 June 2012, 09:22 PM
looking at the illustrations provided, it seems the OT is looking for an algorithm that can tesselate as well as triangulate N-Gons.
Simply triangulating and Quadrangulating won't create the internal structures described in the illustrations.

everytime you add new edges/verts, the IDs are re-ordered. If you want to progressively split a single N-Gon, you'll need to compare all the components IDs before to all the IDs after to establish the new faces.

06 June 2012, 01:23 AM
Yes, thank you for that explanation. And yes, I had a look around and it seems the 'sets' command, keeps track of the ID of the edges, faces and verts.

06 June 2012, 02:17 PM
No need to use sets, you can just store off the IDs before the split, then query the IDs after the split. New components always come last.

I did something similar to divide a face up N times along a single axis.

Psuedo-code (dont have the cmds ref available):

# store off all the current faces
origID ='shape.f
', flatten=1)
# split the face
# get the new list of faces
newID ='shape.f
', flatten=1)
# diff the two sets
newFaces = list(set(newID).difference(set(origID)))
# continue splitting...

you'll probably want to retrieve the new edge, and then get both faces on either side to properly bisect them and create the mid point.

CGTalk Moderation
06 June 2012, 02:17 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.