Checksums in 3ds Max (part 2 of 2)

In Part 1 I showed how to calculate checksums inside 3ds Max. Here's how to do something useful with them.

Any TA that's crossed paths with 3ds Max can tell you it doesn't do the best job of managing scene materials. Due to scene object merges/imports and other typical operations, it's common for a given material to be copied several times in one Max scene. Meaning, it's not instanced across several objects, but actually copied several times in memory. This can lead to increased memory usage and potentially inefficiencies in your game engine (depending how your exporter deals with this).

What's worse, you usually can't rely on similar material names to find duplicates by hand. To do a thorough search with MaxScript, you would need to loop through every material in the scene and compare every property in it to every other material's property. This would be a slow process in C, and a complete horror-show with MaxScript.

Enough grim talk. Here's a walkthrough of a MaxScript that uses checksums to make short work of this. To summarize, the script loops through the materials in your scene, creating a checksum for each as it goes. It uses that checksum to do a quick compare on previous material checksums it found, to see if they're actually property-identical. If it finds a dupe, that object is given the original material instead, effectively deleting the duplicated material.

The script is divided into three functions and a short bit of main code.

getChecksum() is the first function, taken from my previous post. It calls the Python COM object we registered, which returns a checksum to the MaxScript. If you can't (or don't want to) set-up the COM object, you can use the MaxScript implementation I listed in that blog post instead... it's just less robust than the MD5 checksums used by the Python method.

Next is the getPropsString() and getMaterialChecksum() functions:

------------------------------------------------------------
-- (str)getPropsString (material)mat
--
-- Description:
-- Builds a string representing the property names/values
-- of the supplied Max material.
------------------------------------------------------------
fn getPropsString mat = (
   myStr = "" as stringStream
   if (mat == undefined) then (
      format "undefined" to:myStr
   ) else (
      -- Start our string w/the classname
      format (classOf mat as string) to:myStr
      if (classof mat == ArrayParameter) then (
         -- Array, so recursively add strings for each element
         for element in mat do (
            format (getPropsString element) to:myStr
         )
      ) else (
         -- Not an array, so see if it has properties
         propNames = undefined
         try (
            propNames = getPropNames mat
         ) catch ()
         if (classOf mat == BitMap) then (
            try (  -- Add bitmap's filename
               format mat.filename to:myStr
            ) catch ()
         ) else if (propNames == undefined) then (
            format (mat as string) to:myStr
         ) else (
            format (propNames as string) to:myStr
            -- Loop through properties, adding their names
            -- and values to our string to be checksummed
            for i in 1 to propNames.count do (
               format (i as string) to:myStr
               p = propNames[i]
               val = getProperty mat p
               format (i as string) to:myStr
               format (getPropsString val) to:myStr
            )
         )
      )
   )
   (myStr as string)
)

------------------------------------------------------------
-- (str)getMaterialChecksum (material)mat
--
-- Description:
-- Takes a Max material (or multi-sub material) and
-- calculates a checksum value from it, for use as a
-- hashtable key, or whatever you like.
------------------------------------------------------------
fn getMaterialChecksum mat = (
   str = ""
   if (classof mat == Multimaterial) then (
      for id in mat.materialIDList do (
         -- Add material IDs as factors
         str += id as string
      )
      for subMat in mat.materialList do (
         -- Get string representing each submaterial
         str += (getPropsString subMat)
      )
      ) else (
         -- Get string representing this material
         str += getPropsString mat
      )
   -- Add string length as a factor
   str += str.count as string

   -- Get checksum from our base string
   -- 99991 = largest prime number under 10k
   (getChecksum str)
)

The above functions work together to generate a string of data representing the supplied 3ds Max material (or Multi-Sub material). Once it has that string, it's passed to getChecksum().

The main code block loops through the entire 3ds Max scene, doing the above for every material found on geometry objects:

----------
-- MAIN
----------
-- Set up a few things first.

timeStart = timestamp()  -- Time we started process
removedCount = 0  -- Counters for printing info below
uniqueCount = 0

-- Array of two synced arrays, first with the material
-- checksums, second with materials themselves.
-- Basically a poor-man's hashtable.
csMatArr = #(#(), #())

format "Scanning scene materials...\n"

-- Loop through all geometry
for obj in geometry do (
   mat = obj.material

   alreadyDone = (findItem csMatArr[2] mat) != 0

   if (not alreadyDone) and (mat != undefined) then (
      -- First get this material's checksum
      csum = getMaterialChecksum mat

      idx = findItem csMatArr[1] csum

      if (idx != 0) then (
         -- Dupe material found, so remove it by
         -- assigning the first mat to this object
         format "Replacing material '%' with '%'\n" mat.name csMatArr[2][idx].name
         obj.material = csMatArr[2][idx]
         removedCount += 1
      ) else (
         -- New checksum, so add it to our table,
         -- along with the material itself.
         append csMatArr[1] csum
         append csMatArr[2] mat
         uniqueCount += 1
      )
   )
)

gc()  -- Remind Max to take out the trash

-- Done, print some results
format "-- DONE in % secs --\n" ((timestamp() - timeStart) / 1000.0)
format "Old material count = %\n" (uniqueCount + removedCount)
format "New material count = %\n" uniqueCount
format "Duplicates removed = %\n" removedCount

That's it. At the end a summary is printed to the MaxScript Listener.

In the Max scene I was working with today this script cut the root material count from 533 to 261. That's 51% fewer materials! It also reduced the file load time from 136 seconds to 102 seconds.

You can download the complete script above here: RemoveDupeMaterials.zip (4 KB)
It includes the Python script to register the COM server, and the alternate MaxScript checksum method.

Update 7/25/08: I modified getPropsString() to better handle bitmap values, and generally run faster. The ZIP file above is updated as well. Thanks to MoonDoggie/Colin on CGTalk for the feedback!

Checksums in 3ds Max (part 1 of 2)

In my Calling Python from MaxScript post I mentioned the usefulness of checksums in Tech Art work. I was hoping to elaborate on that a bit.

In short, a checksum is a number computed from a larger piece of data. The checksum is (ideally) guaranteed to be unique for that data. Let's say that data is this string: "Tech Art is A-#1 Supar", and the checksum you've computed is "30532". If any character in that string changes, the computed checksum for it will be different, like "18835" or "1335"... basically anything other than "30532".

Checksums are most useful in cases where you need to compare two sets of data to see if they differ, but don't care where or how they differ. If you have a short number that uniquely identifies a huge piece of data, you can compare it to other data sets much faster/easier than comparing every element of the original data. If you're hip to how slow n-squared searches can be (especially in languages like MEL or MaxScript), this is a classic method for avoiding them.

Here's a MaxScript function that takes a string of any length and returns a checksum for it.

------------------------------------------------------------
-- (str)getChecksum (string)val (int)size:256
--
-- Description:
-- Calculates simple checksum value from supplied string (or
-- any value convertable to a string).  Default size is 256,
-- but can be changed with the optional "size" parameter.
------------------------------------------------------------
fn getChecksum val size:256 = (
   if (classof val != String) then (
      try (
         val = val as String
      ) catch (
         return false
      )
   )
   alphaKey = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 !@#$%^&*()[]\\{};':\",./<>?"
   total = 0
   for i in 1 to val.count do (
      thisVal = findString alphaKey val[i]
      if (thisVal == undefined) then (
         thisVal = 0
      )
      -- Multiply the alphanumeric value by its position in
      -- the input string, add to running total
      total += (thisVal * i)
   )
      -- make sure divisor is smaller than dividend
   while (total < size) do (
      total = total * 2
   )

   -- Return final checksum value
   checksum = mod total size
   return (checksum as string)
)

We used the above function in several of the Saints Row tools, primarily to help remove identical materials in 3ds Max scenes. It's very unscientific, however, and can generate collisions in rare cases (two different input strings that generate the same output checksum) **.

If you don't mind a little more setup, I would recommend an alternate checksum method. Python natively offers more robust checksum tools, and can be set up to be called directly from MaxScript. The steps for doing this, and the actual MD5 checksum function, are covered in my earlier blog, Calling Python from MaxScript.

Start with the Python script from that blog that defines and registers the COM server. Then you're able to use a far-shorter MaxScript function to get checksums:

fn getChecksum val = (
   comObj = createOLEObject "PythonCom.Utilities" 
   checksum = comObj.checksumMD5 val
   return checksum
)

That's it. The checksums you get from this function will create fewer collisions than the pure-MaxScript one above, and can be made to use any alternative method available in Python.

Now you know more about checksums, and how to generate them in 3ds Max. Next time (in Part 2) I'll discuss how you can use them to save memory in both Max and your game engine.

Python String Templates

The Template class, found in the standard Python string module, is extremely useful. Start with a template string containing keys you want to replace. By default keys start with "$".

>>> import string
>>> thisTmp = string.Template("The $speed $color $thing1")
>>> thisTmp.substitute(speed='quick', color='brown', thing1='fox')
'The quick brown fox'

You can also pass the substitute method a dictionary with key/value pairs for your template:

>>> strDict = {'speed':'slow', 'color':'toupe', 'thing1':'mango'}
>>> thisTmp.substitute(strDict)
'The slow toupe mango'

This makes it easy to insert variable parts in an otherwise fixed string or file. I use it all the time for generating table-based HTML reports.

Create a file like "report.html" with string keys like "$rowValue1" or "$user" in the appropriate places, and have your script read in the contents as a string Template and do the substitutions. This also allows the report layout/appearance to be altered later without touching the script code.

Calling Python from MaxScript

Unlike Maya, 3ds Max does not have internal support for Python. But that shouldn't stop you from calling useful Python code in your MaxScripts! Here's the basics of how to do that using COM.

COM is a Windows system that supports, among other arcane things, interprocess communication. You can use a language like Python, Visual Basic, or C to define a COM "server". This is a class or function, defined by a unique identifier (GUID) and a name. Here's some gory details on COM if you're curious.

Here's a simple COM server using Python:
Requires the Python Win32 Extensions (which no TA should be without)

# A simple Python COM server.
class PythonComUtilities:
   # These tell win32 what/how to register with COM
   _public_methods_ = ['checksumMD5']
   _reg_progid_ = 'PythonCom.Utilities'
   # Class ID must be new/unique for every server you create
   _reg_clsid_ = '{48dd4b8f-f35e-11dc-a4fd-0013029ef248}'

   def checksumMD5(self, string):
      """Creates MD5 checksum from string"""
      import hashlib
      m = hashlib.md5()
      m.update(str(string))
      return m.hexdigest()

if (__name__ == '__main__'):
   print 'Registering COM server...'
   import win32com.server.register as comReg
   comReg.UseCommandLine(PythonComUtilities)

This defines a function, checksumMD5 that takes a string as input, and returns the MD5 checksum for that string.

To register the COM server on a PC, simply run the Python script. Windows records it in registry, noting which script/application it uses.

Now that's done, another application (3ds Max, in this case) can connect to that COM server's interface and call it like any other function. Here's an example of doing that from MaxScript:

-- Connect to the COM server by name
comObj = createOLEObject "PythonCom.Utilities"
-- Call the function it exposes, with a sample string
checksum = comObj.checksumMD5 "The quick brown fox."

It's that simple. The checkum value returned for our sample string is "2e87284d245c2aae1c74fa4c50a74c77".

You might be wondering what a checksum is, or what it's good for. Stay tuned and I'll show you some slick stuff you can do with them in 3ds Max. See Checksums in 3ds Max, Part 1 and Part 2.

Python COM server example adapted from code appearing in Python Programming in Win32 by Mark Hammond and Andy Robinson... a great book for getting more out of Windows with Python.

Logging (I'm no lumberjack, but I'm okay)

Exploring the Python standard library is fun.

Not long ago I found how great the logging module is. Use it to create a logging channel, attach different handlers to it (for logging events to a file, through email or HTTP, etc), then make one-line log events of different types.

import logging
import logging.handlers

# Sets up a basic textfile log, with formatting
logging.basicConfig(level=logging.DEBUG,
   format='%(asctime)s %(levelname)-8s %(message)s',
   datefmt='%m/%d/%y %H:%M:%S',
   filename=r'C:\temp\mylog.log',
   filemode='a')

# Log a few different events
logging.info('Just testing the water.')
logging.warning('Hmm, something is not right here')
logging.error("Oh no, now you're in for it")

The resulting text log:

02/14/08 22:19:03 INFO     Just testing the water.
02/14/08 22:19:03 WARNING  Hmm, something is not right here
02/14/08 22:19:03 ERROR    Oh no, now you're in for it

Add a few more lines and it sends you an email for any logs that are level "ERROR" or above:

email = logging.handlers.SMTPHandler('smtp.foo.com',
   'script@foo.com',('techart@bar.com'),'Error Report')
email.setLevel(logging.ERROR)

logging.getLogger('').addHandler(email)

There's several other handler types as well. Very useful!