In this thread I open a discussion on re-constructing meshes with problems so that they become more simple, user friendly and good for further design work. In two words - meshed to become “just normal”…
At first let me tell you what I mean by the term a “problematic mesh”… This is a mesh which puts the designer in a very uncomfortable position while trying to modify it (further change mesh size, shape and/or structure) thus bringing the designers a lot of trouble while, if untouched, the mesh may look pretty goog and serve nicely as it needs to! Usially, such meshes do contain one or more of the following:
Twisted faces;
Zero-faces (faces with area = 0);
Overlapped faces.
I have worked on the above issue but there may be some more not-so-that-nice specifics of meshes that make them PROBLEMATIC… Please share your ideas on that…
I issued a solution for the first item in the list - dealing (eliminating) twisted faces - in another threasd here in this forum. Link given there are not OK now but I will re-work them to be available again pretty soon…
The perfect situation as a result of this thread will be an integrated script that eliminates problems in meshes selectively or entirely as soon as they exist.
your approach to determine if a face is twisted uses the determinant and it obviously works… My naive approach would be to take the dot product of two ‘triangle normals’, those being the cross product of any pair of edges that define a triangular half of a quad. If this dot product is not (almost) ± 1 the face is twisted. Now, that might actually be the same effectively as your approach but I’m not quite certain.
The script is useful but it has some limitations. I’ve tested it on a custom mesh (constructed in a bad way, on purpose) and it produced wrong results. When the mesh contains a face that is scaled down to zero, it even crashes. Here’s the .blend I used to test.
Another thing I noticed is that it gets exponentially slower on larger meshes. Even on relatively small meshes (3k verts) it’s already pretty slow (18 seconds, though I have to admit that my computer is weak).
Hopefully I don’t sound too harsh, but you said you were very critical yourself, so I guess you can handle it. I’m just trying to be constructive
So I tried if I could come up with a script myself. Here’s my try. It fixes the test-blend you provided correctly as well as the .blend I used for testing. It’s also a lot faster (and it scales up linearly). For 3k verts it only took 0.14 seconds
I’m using a different way to determine if faces are twisted. I’m using LineIntersect() to get the intersection of edges on an infinite plane. Then I calculate if the intersection point is on the edge segment, so I know if the edges intersect inside the mesh face. If that is the case I untwist the face and remove any redundant edges.
ps: I got your pm, but I got no time to reply now. I’ll get back to you before the end of the week.
@ varkenvarken: Twisted face is really that one which is real hard twisted, i.e. both triangles lye in 1 plane. In other words, their normals form an angle = 180 degrees. This is in the ideal (theoretical) situation. This, I think will result always in dot-product = -1… In real situation, a resonably small threshold should be used to eliminate Blender’s inaccuracy in working with floats as coordinates. Such a threshold will allow the script to deal only with REALLY twisted faces (by mistake of a script’s work or due to other reason) and NOT to touch almost twisted face that the designer wants to stay twisted.
@ Crouch: Well, I admit that I havent made any attempts for optimising its performance since June (when I produced it) cause there wasnt any discussion on that in this forum and also I really used it in relatively small meshes (verts < 300). I guess the exponential increase of time comes from the GREAT number of matrix operations needed…
Your so described crash relates to dealing with zero-faces… right? Obviously, matrix and vector operations fail when vector(s) len = 0. That is what I’ve meant putting this issue in the list of problems to deal with --> it always makes a great mess in scripts work! :eek:
Nice that you have ideas exposed here already… I will take a look a bit later today… Just to mention - as far as I remember - I started dealing with the issue exactly this way: use LineIntersection and then look if it is within the face… But there was a reason I abandoned this solution! I think it relates to possible twisted faces having a concave form in which case the intersection of the two diagonals lye outside the face itself. I need to check this though. May be a combined approach will be the solution…
It turns that my script also needs re-working to deal with concave twisted faces case… :eek:
Some crashes in work of my script appear when re-calculating the threshold to work with. I have already fixed this procedure. The idea is to NOT to use a fixed minimal threshold for each mesh. It is needed (in some cases) to re-calculate it in accordance with verts’ density of the mesh. The procedure I use is more or less based on experimental data/results. It evaluates to some extend density of verts but if verts are more dense in one part of the mesh while in the other part they are at a huge relative distance, a BIG value of the threshold wont allow any processing in the dense part while a small value wont allow the script(s) to judge what is the real situation at the less dense part. The reason for the latter is AGAIN Blender’s imperfection while working with floats as coordinates ov mesh verts --> the nastiest issue in BLENDER!!! Any other isdeas to re-calculate the threshols dynamically are welcomed.
The re-working proc is:
def Recalc_min_threshold(ob,me,min_threshold):
ob_box = ob.getBoundBox(0) # object's local bound box
n = len(ob_box)
if (n > 0):
minX = ob_box[0][0]
maxX = ob_box[0][0]
minY = ob_box[0][1]
maxY = ob_box[0][1]
minZ = ob_box[0][2]
maxZ = ob_box[0][2]
for i in xrange(1,n):
if (minX > ob_box[i][0]):
minX = ob_box[i][0]
if (maxX < ob_box[i][0]):
maxX = ob_box[i][0]
if (minY > ob_box[i][1]):
minY = ob_box[i][1]
if (maxY < ob_box[i][1]):
maxY = ob_box[i][1]
if (minZ > ob_box[i][2]):
minZ = ob_box[i][2]
if (maxZ < ob_box[i][2]):
maxZ = ob_box[i][2]
cube_units = (maxX-minX)*(maxY-minY)*(maxZ-minZ)
ratio = cube_units / (len(me.verts) + 1) # to avoid 0 as delimiter ;)
if (-1E-12 < ratio < 1E-12):
new_min_threshold = 1E-7
else:
new_min_threshold = min_threshold * ratio
if new_min_threshold > min_threshold:
new_min_threshold = min_threshold
if new_min_threshold < 1E-7:
new_min_threshold = 1E-7
return new_min_threshold
There is also problem of accumulating great processing times when number of verts of mesh processed goes up. I thought I have solved it by a matrix operation but it refers only to determing which face is non-planar.
Conclusion: a solution to working with both convex and concave twisted faces is needed…
Apparently, the logic I used in my script is not completely correct. It also leads to transferring BIG lists of data when meshes of thousands verts are processed. Searching within such BIG lists seems to have a very bad effect on time of processing. I think this is the reason the script I proposed shows exponentially high values for timing when number of verts in the processed mesh increases. Also, I have some conversions to 2 lists plus some processing at rows 65-70 which is ineffective but at the time when I produced the script I wasnt able to organize it differently. I that respect, the algorithm proposed by crouch is a better one. It shows though some wierd stability… When number of verts in the mesh is small (100-200) it processes the mesh in X milliseconds. When the mesh has 10 times more verts, processing time increases only by 25%! This is a rather good achievement, I think!!!
I’ve made some more time testing… As my original idea was to mainly use the kind of a script over an unknown mesh usually imported from MakeHuman or 3DS, I expect such a mesh to have relatively small number of flat faces. Twisted faces issue can appear ONLY at flat faces, soooo I first check for non-planar faces and then check for twisted faces among the rest. I have two procedures for that in my script called NonPlanarFaces and List_difference. The latter produces a difference between two lists - I havent seen such an API function so I produced that proc… Both ptocs do cost time but it is NOT a great deal - they ALWAYS complete their tasks within 3-4% (both) of the total processing time while, if most of faces are non-planar => a very restricted set of faces will remain for testing if they are twisted or not. Therefore, I think this helps a lot the script’s performance… and I tried to use this tactics within the Crouch script. The result is quite unexpected from my prospective --> processing time remains at the same level as without measures to restrict the set of faces for testing against twisting!!! Sooo I’d be interested to read comments, especaially Crouch’s comments, on the above… Pls Crouch & others!
Sooo I’d be interested to read comments, especaially Crouch’s comments, on the above… Pls Crouch & others!