About the CheckMate Contest and problem solutions

 

Denys Almaral 

- Script file name: pX Tools-SceneInspector.mcr

 

Compatibility

 

The Script was programmed with 3ds Max 2009 and full tested with 3ds Max 9.0 sp2.

Was avoided the use of functions that works strictly with a particular high version of max. From my understanding the most high version function used is: <Unwrap_UVW>.selectOverlappedFaces() compatible with 3ds Max 8.0 and higher.

This can be implemented to try a more compatible and fast solution in future versions of this script.

**Version 1.0: The use of DotNet classes were also avoided, so the script should be easy adaptable to earlier than 9.0.

**Version 1.01: Use DotNet to fix incompatiblity with Win7 64 bits, this script can't run in lower version of max 9.0

 

Object preparation for inspection and restore

 

 The script first disable some modifiers that should be ignored defined in the script as array:

local IgnoreModifiers = #(TurboSmooth, MeshSmooth, SpacewarpModifier)  

Then it adds Edit_poly modifier in a proper position in the modifiers stack,  in a way that the modifiers below established by the artist can be respected.

  At the end of the inspection button Restore modifiers, can be used to restore the original state of the modifiers stack, and remove any modification created by the tool. The scrips know how to do it because it marks the modifiers with prefixes like TEMPMOD_ and TEMPDISABLED_

  

 Object Information

 

Gathering object information was separated in to stages and two List Views: Object Info and Mesh Analysis, isolating the most intensive calculation algorithms for Mesh Analysis while Objects Info gets the basic properties quickly.

 

 All the 14 points of Target Features were covered, with the following assumptions and definitions:

 

- Overlapping faces respond to faces sharing the same plane in space and colliding its 2D projected polygons in this plane.

 

- The topology info (number of polygons, quads, etc) is NOT collected from BASE OBJECT, since this will give wrong results because doesn’t respect the modifiers stack defined originally by the artist, for example if he uses a Symmetry modifier!, So the scripts only ignore subdivitions modifiers (TurboSmooth/MeshSmooth) and SpaceWarps, then gets the info bellow these ones using a Edit_poly modifier.

 

- The number of Quads isn’t relevant to show while the number of triangles, ngons and polygon totals are displayed.

 

-  Faces with flipped normals are those in a chunk of connected  polygons that in lower number are flipped to the opposite side of the major number of polygons. (cool J isn’t it?) Imagine a object of of 4 polygons, 2 polygons normal points up and the other 2 polygons points down? Which of them are the the flipped ones? :-o

 

- Hidden objects respond to objects that for any reason are not shown in the view port.

 

-  Not grouped objects are covered by Objects with no parents, because any object inside a group has a parent dummy, so isn’t necessary to differentiate groups from hierarchies.  

 

-  The Render image is taken from the first camera in the scene, if this camera doesn’t exist then renders from Perspective view.

 

- Viewport captures do Zoom Extents of Geometry objects only, so non-geometry could be clipped away form the main subject of the image.

 

Showing reports and Saving to file

 

The script shows in  standard Windows List Views all the info in a way that can be easy read, highlighting problems with different colors (See Scene Inspector README file). The artist or inspector could easy do without exporting reports to HTML files, while the visual interface help them to see all the required  info, interacting with the scene and reports.

 

The scripts currently support three formats: HTML, XML and CSV.

Exporting to these format are implemented in a way that they are conveniently dependent from List Views table structure and content, so if a new test value is needed to be added to reports, the only part that need small modification is the section in the script that put the values in the List Views data structures. After that when saving to any format the exporters gets the info present in those tables and save it to file, whatever new columns or data they contain. Also the HTML replicates the font color and format from the List Views J.

 

 Consequently the three file formats have the following similar structure:

- Header info (max file name,  Max version, local time…)

- Summary Table

- Objects Info Table

- Mesh Analysis Table

- Missing references list

- Rendered images (HTML only)

 

 

Problem solution and algorithm optimizations

 

Overlapping Vertices and Overlapping Faces.

The exponential iterations problem:

 There is a typical problem when you have to comparison test between every item in a list. The number of iterations grow exponential with the items count.

#iterations =  (count-1)^2 / 2

When the number of vertex count or faces count is big the iterations reach millions and the execution go extremely slow!

What  I did, from experience with old game programming as hobby was do some pre-calculations, partitioning the space to group near elements first, then rung tests after group by group.

 

 

When finding overlapping faces I first create a 3D dimensional array to store  list of vertices defined by an abstract cage of boxes, similar to the image above. This boxes should overlap with a minimum tolerance distance so vertices near a border of a single cell are assigned to both cells involved.

 

See the image above:

a)      two contiguous cells could miss vertices that are so near to its border that the distance between them are lower than the Tolerance admitted, then the algorithm would fail.

b)      Overlaping contigous cells solve this problem because those very-near vertices will be listed in the two cells.

 

After quickly storing vertexes in cells then the total amount of iterations fall drastically, testing shows: 10 times faster with 2,000 vertices and  50 times faster 10,000 vertices.

 

In the script source you can find the old-easy-slow implementation without partitioning called FindOverlappingVertsOld.

 

Finding overlapping faces the partitioning is much more abstract, avoiding the complexity of separate groups of polygons by position in space (that could be tried too), the value I decided to take this time was the Normal. Separating into 8 octants first, then taking X, Y componets of Normal and grouping faces with similar normal.  Mush more difficult to explain here graphically.

 

The test for FindOverlappingFacesOld (without partitioning ) for only 226 faces was : 7,0seconds, while FindOverlappingFaces (with parititioning) as low as 0.062 seconds!!

 

After the partitioning algorithms some optimization of code, like eliminating unnecessary variables and storing some values to avoid function calls reduced the time execution approximately to a half.

 

NOTE: The current TS CheckMate tool performs better or similar than this one when the scene present several small objects with low poly count. But my script beat it when the scene have lot of faces with just a few objects. (In order to do this comparison fair you must disable Finding flipped faces test that is not present in TS CheckMate tool.

 

 

Finding Flipped Faces

 Seems easy stuff at first sight but this one was one of the more complex problems to solve and give a good solution. Detect that exist at least one flipped face is very easy but determinate, but select which of them are the flipped ones, that’s a challenge.

 

This image above is a single object with 3 chunk of connected faces (or elements in Max)

 

You can not easly determinate when a face “normal” is flipped looking into de “normal” value, you have to check near faces and its vertex order.  Also a face could be flipped and be in the middle of a group of flipped faces! So you only can know if two near faces are flipped but not which of them is the bad guy.

 

Solution

- My function FindFlippedFaces, frist create a Graph of connection between faces and each  Link flag if the connection is flipped or not.

- If not flipped link is encountered then the function happily exit. If flipped links exists there it  come a second scan to determinate wich could be flagged as flipped.

- Scaning with a Flood fill algorithm: (Similar to those algorithms used by paint programs) The scan start in a random face and mark this first face with TRUE value.

-  The scan continue spreading and each time a near face with a Non-Flipped link is found it can be also marked with the same value of current face.

-  Then if a link to a face is a Flipped link that face  is marked as the opposite value of current face TRUE->FALSE, FALSE-> TRUE.

- Once a Chunk is completed run the same algorithm in the next chunk if exists.

- Now at the End of each chunk, if the amount of values with TRUE is greater than FALSE, this chunk must be completely inverted.

- Finally all faces marked with TRUE! are the Flipped faces!! J

 

Note: Don’t worry now. Seeing this algorithm graphically animated is very easy to understand.

 

Code reused from current TS CheckMate Tool

- Function detectDefaultNames()

 

Known problems and limitations

- In some undetermined cases, with huge amount of objects and polys, the Max function SelectOverlappedFaces() could rise memory problems. (The use of garbage collection gc() function at this moment has eradicated all in my current tests)

- If you stop the process holding  ESC, the script is interrupted and the Maxscript Editor would be opened.

- FindOverlappingFaces: Some cases of concave polygons, polygons with overlapping vertices and very rare case of coincident premeditated normals could report a misunderstand Overlapping faces.

-  Selecting objects via List View that has been deleted after the inspection process could raise errors.

Future development of this Scene Inspector script:

 

- Impement a new function to substitute the current <Unwrap_UVW>.selectOverlappedFaces()  to go lower than Max 8.0 version. Try to optimize with some fun algorithm. Implement also a select UV faces.

 

- Fix current detectDefaultNames() function that is missing some names.

 

- Detect texture stretching

 

- Detect duplicated object names (this can be a problem allowed by Max)

 

- A new button for Sub-Object Selector mini-tool: Select Next Problematic Object

 

- Save/remember options/preferences and other values in Windows registry

 

 

 

Denys Almaral