Tuesday, February 23, 2010

Capping a face with a library cap piece

For the past 3 days I've been working on a solution to replace (cap) a face of varying orientations and size with a standardized library of cap pieces using MaxScript. I'm pretty sure I've got all the kinks worked out and it appears to be working as expected.

The steps to do this are as follows (Don't worry, I'll break down each step further down in the post). Note: I don't include a few steps here as they are pretty common sense that you need to them, for example, I don't include deleting the bounding boxes, attaching the objects or deleting the original faces.

  1. Determine the faces that need to be capped

  2. Determine a library cap piece

  3. Determine the face orientation

  4. Determine the center position of the face

  5. Build the random cap object

  6. Create a normal reference poly

  7. Create a bounding box cap piece

  8. Store the custom FFD data for the bounding box object and the cap object

  9. Determine the corner verts on the cap object and adjust the bounding box

  10. Apply the FFD deformation

  11. Flip inverted normals

I know it looks like a lot of steps, but they are all broken down into pretty simple functions. So lets get to the breakdown.

  1. Determine the faces that need to be capped

    This step is pretty simple, at Volition we use Material ID's to differentiate between material types. By knowing the Material ID of the faces I want to cap, I use an EditablePoly method called selectByMaterial. The commands looks like this : .EditablePoly.selectByMaterial .

    Once that command is run, I am able to use a polyOp method to get the selected faces: polyOp.getFaceSelection

  2. Determine a library cap piece

    This step is to project dependant to really be explained, it is all up to how the project wants to build and setup a cap library. I will explain the proposed idea for our library in another post.

    One important thing to note in this section though is the parameters my library pieces need to have to work correctly using my methods. For me there are two important things:

    1. Flagged corner verts using bitFlags

      This step requires the artist designing the cap pieces to select the 4 corner verts on a cap piece and "flag" then using vertex bit flags. The code to do that is below:

      fn set_vertex_bit_flags obj vertex_list bit_flag bit_value = (
      -- Unreserved bits
      if (bit_flag > 24 and bit_flag < 33) then (
      -- Build the bit flag
      bit_to_set = bit.set 0 bit_flag bit_value

      -- Set the vertex flag
      obj.setVertexFlags vertex_list bit_to_set
      ) else (
      messageBox "Invalid bit flag" title:"Invalid bit flag"

      fn get_vertex_bit_flags obj bit_flag bit_value = (
      -- Return value
      verts_with_flag = #{}

      -- Unreserved bits
      if (bit_flag > 24 and bit_flag < 33) then (
      -- Build the bit flag
      bit_to_get = bit.set 0 bit_flag bit_value

      -- Get the verts matching the flags
      verts_with_flag = polyOp.getVertsByFlag obj bit_to_get
      ) else (
      messageBox "Invalid bit flag" title:"Invalid bit flag"

      -- Return the value

    3. Triangulated mesh

      Due to how max handles winding orders of faces and poly creating, the mesh needs to be triangulated for the method I use to flip the normals to work. You'll see more on that later. This can be automated though using polyOp.ConnectVertices. Code is as follows:

      polyOp.setVertSelection <selection> #{1..(polyOp.getNumVerts <selection>)}


  3. Determine the face orientation

    This one took a little bit to get right, but here are the steps

    1. Get the face normal of the face we are aligning too

      Pretty simple step, polyOp.getFaceNormal

    2. Get the edges from the face

      Again, pretty simple, polyOp.getEdgesUsingFace . This bitArray will be used in a further step

    3. Get the verts from the face

      polyOp.getVertsUsingFace . This bitArray will be used in a further step

    4. Look for the first vert that has 3 edges and store those edges

      This step is to make sure we get a corner vert, not floating vert on an edge. This may be unneccesary on your geometry, but for ours this is a neccessary step

    5. Determine the unused edges

      Subtracting the vert edges from the face edges will result in a bitArray of unused edges

    6. Determine the used edges

      Subtracting the vert edges from the unused edges will result in a bitArray of used edges

    7. Loop through all the used edges and build a list of verts used on each edge

      This will result in an array of coinciding verts that we will use to determine the face's orientation. Basically we are looking for a vert list that looks like the following image:

    8. Build our vectors

      Using the positions of our 3 verts, determine our vectors and determine the right vector on length.

      is determined by subtracting the second vert from the first vert. is determined by subtracting the last vert from the first vert.

      Once that is done, get the absolute length of both vectors, and using that length determine which is going to be used as the right vector.

      When that is determined, normalize both vectors and build your matrix using your two vectors and the face normal:

      matrix3 left_vector right_vector face_normal [0,0,0]


  4. Determine the center position of the face

    This is a pretty simple step as well, collect all of the vert positions using polyOp.getVert, add them all together and divide by the number of verts to get the average position (center of the face)

  5. Build the random cap object

    Simply clone the chosen cap object, this could be where you triangulate the cap as well.

  6. Create a normal reference poly

    To properly determine if the normals of the cap object were inverted in the transform, we need to create a reference poly on our cap object to get a baseline normal to compare against. By using the bounding box parameters of the cap object we can create a flat poly and flag the verts for later use. Code as follows:

    -- Get the vert positions
    vert_a_pos = [obj.min.x, obj.max.y, obj.min.z]
    vert_b_pos = [obj.max.x, obj.min.y, obj.min.z]
    vert_c_pos = [obj.max.x, obj.max.y, obj.min.z]

    -- Create the verts
    vert_a_ind = polyOp.createVert obj vert_a_pos
    vert_b_ind = polyOp.createVert obj vert_b_pos
    vert_c_ind = polyOp.createVert obj vert_c_pos

    -- Build the vert array
    vert_array = #(vert_a_ind, vert_b_ind, vert_c_ind)

    -- Make the polygon
    polyop.createPolygon obj vert_array


  7. Create a bounding box cap piece

    This is the box that will be used in the FFD (Free Form Deformation) calculation. This is created using the cap pieces bounding box positions. Be sure to reset the XForms and convert to a PolyObject

  8. Store the custom FFD data for the bounding box object and the cap object

    One of my collegues here, Will Smith, created a custom FFD function to use for this. We tried exploring using Max's FFD modifiers, but control was very limited and the coordinate system the FFD's use made this overly complex. We decided the best solution would be to write our own, which turns out wasn't very difficult. Since this isn't my code, I won't post it here, but essentialy we determine how much weight a vert on the FFD object (in this case our bounding box) has on the verts on the deforming object (in this case our cap object) based on the distance between the two positions. One thing to note though is that we needed to slightly scale up the bounding box to avoid division by zero and infinite numbers. I also added some checks in the function to prevent any floaters as well.

    If anyone is wondering about the math, we used the math found in this discussion on cgsociety.org for our baseline.

  9. Determine the corner verts on the cap object and adjust the bounding box

    This is where we properly adjust the bounding box to the corner verts of the face.

    To do this I loop through the verts that make up the outer edges of the face (verts with at least 3 edges) and find the closest vert based on distance. Since I know that the box I create has 8 verts, I am able to move the first 4 verts of the bounding box to the 4 corner positions of the face. The second step to this is to determine the amount I am moving the vert and then applying that amount to the bounding boxes corresponding vert, to get that index simply add 4 to the current bounding box vert you are working with.

  10. Apply the FFD deformation

    Again, using Will Smith's Custom FFD script, we apply the FFD deformation to the cap object according to the adjusted bounding box

  11. Flip inverted normals

    I'm going to avoid going on a "Why I Hate Max" rant here, but I still want to explain something about this step. As anyone who has messed with maxscript knows, having the modifier panel open slows down your maxscript quite a bit, it is always best for performance reason to have the create panel open unless you specifically need something in the modifier panel. Saying that, polyOp has a built in method for flipping face normals, polyOp.flipNormal, unfortunately it doesn't work unless the modifier panel is enabled, which slowed down the execution of my script by quite a large amount. After speaking to Jeff Hanna, he explained that the face normal is derived from the winding order of vertices, which led me to an experiment. The experiment was, would it be faster to rebuild the geometry and transfer the UVs with the correct winding order instead of opening the modifier panel and calling polyOp.flipNormal. What blew me away was the answer was a resounding yes.

    I won't go into the geometry creation or transfering of UV's, but I will explain how the reference poly comes into play here for determining if the normals are reversed.

    To determine if the cap object's normals were reversed in the transform, I get the normal of the face we are applying to the cap object to and the normal of the reference face. I then get the dot product of the reference face's normal and the cap object's face normal.

    If that value is less than 1, than I know that the normal has been reversed and I go ahead and recreate the geometry.

So there you have it, the basics for aligning a cap object to an arbitrary face.

Tuesday, February 16, 2010

HTML in clipboard

It turns out copying/pasting hyperlinks to the windows clipboard isn't as easy as just copying the unformatted HTML. Turns out you need some crazy format inside of the clipboard for an application that handles HTML copy/paste to actually recognize it. Originally I looked for a solution using the Microsoft Office clipboard since that is where the html from the clipboard was going to be pasted to anyways, but it turns out there is no longer an object model for the office clipboard in versions past 2000. I ended up finding the solution to copy/pasting HTML in windows HTML Clipboard format.

This is what the clipboard actually looks like when you have HTML as your format in the clipboard:

<TITLE> The HTML Clipboard</TITLE>
<BASE HREF="http://sample/specs">
<!--StartFragment -->
<LI> The Fragment </LI>
<!--EndFragment -->

Some more information on the HTML clipboard format can be found Here
Standard clipboard formats can be found Here

To implement the HTML clipboard in python, I found a class Phillip Piper had written that does exactly what I need, that code can be found Here.

Also in my search I ran across this python script called PathCatcher - From the Doc String : PathCatcher is a Windows utility that allows one to right-click on
a folder or a file in Explorer and save its path to the clipboard. PathCatcher can be located Here

Thursday, February 11, 2010

Import errors - I always forget about this

Sometimes, boost can be a pain in the ass. I moved directories of the .pyd file as I was renaming everything and expanding the .pyd into different exposed modules. I thought I had messed something up, because when I tried importing the module in python, I got
ImportError: DLL load failed: The specified module could not be found.
I kept changing things on the C++ side trying to figure it out, and then I remembered, the boost.python dll needs to be in the same directory.

Moving it into the directory fixed the import issue. I'm full of fail this morning.


I have a pretty bad habit of changing things in one configuration and then not replicating the results in the others, so this morning while trying to compile in release I ran into a bunch of issues. Most were pretty easily solved, but then I ran into a linker error that I had solved yesterday, it took me a couple of minutes of comparing settings from configuration to configuration to figure it out but then I remembered. In my precompiled header I was getting these linker errors earlier yesterday:

1>precompiled.obj : error LNK2001: unresolved external symbol "private: static bool volatile boost::python::docstring_options::show_py_signatures_" (?show_py_signatures_@docstring_options@python@boost@@0_NC)
1>precompiled.obj : error LNK2001: unresolved external symbol "private: static bool volatile boost::python::docstring_options::show_user_defined_" (?show_user_defined_@docstring_options@python@boost@@0_NC)
1>precompiled.obj : error LNK2001: unresolved external symbol "private: static bool volatile boost::python::docstring_options::show_cpp_signatures_" (?show_cpp_signatures_@docstring_options@python@boost@@0_NC)

Web searches haven't been much help to explain why this is, and maybe I just don't know enough about boost to understand it, but the solution to this error is to change your preprocesser defines.

Previously I was using
in my preprocessor defines, it works fine for everything else I've done, but something in my new project doesn't like it. The solution to this is to tell boost to static link instead by using
instead of

When I have some more time I'm going to look into this a little bit more, I'd personally just like an explanation as to why I need to do this.

Wednesday, February 10, 2010

Speed Results of C++ vLib XML Parsing

This is what I’ve got so far:

The test: Getting all the diffuse, specular, and normal maps used in a chunk file that has 669859 lines.

Note – I’m not checking for duplicate entries when appending to the array, the number of textures is basically a count of how many times “Diffuse_Map”, “Normal_Map” and “Specular_Map” show up in the file.

Another thing to note – Initializing vlib adds .5 second overhead to the first run of the function. When parsing a small file, using this module may be overkill. You’ll see the most performance gain in larger files or when parsing multiple files in a single instance of an application.

Using SAX:
Number of textures 351
Total time - 20.9679999352

Using RE Parsing:
Number of textures 351
Total time - 9.78900003433

Using the wrapped parser:
Number of textures 351
Total time - 1.47599983215

In summary:

Boost Python and Custom Classes

Yesterday I started messing around with exposing our XML parsing code written in C++ to python using Boost.Python. I've gone down this road before, but never exposed a complex class structure to python. About 15 minutes into starting this task I realized that I would need to do that, I had no idea it was going to cause so many issues.

Simply exposing a class and the needed functions wasn't exactly straight forward. For about a day and a half I kept running into compiler issues with boost. Mainly involving compile errors along the lines of "specify_a_return_value_policy_to_wrap_functions_returning" in boost.

Scouring the interwebs for hours really didn't seem to yield many results, but I finally stumbled across the solution. It all has to do with defining the functions inside of the module. For example this is what my module looked like before I found my solution:

class_<parse_xml, boost::noncopyable>("parse_xml", boost::python::no_init)
.def("find_element", &parse_xml::find_element)
.def("find_next_element", &parse_xml::find_next_element)
.def("get_element_data", &parse_xml::get_element_data)


def("get_filepath_from_vac", get_vdir_path_cf);
def("parse_chunkx", parse_chunkx);

Now this obviously wasn't working like I stated above, it turns out the key is to add another parameter to the .def function, boost::python::return_internal_reference<>().
What this does is tells boost that this function is returning a non-standard type. In my case it is returning a custom class. So, the moral of the story is, if you are using boost.python to expose a class or a function that returns a custom datatype, make sure you include boost::python::return_internal_reference<>() in the def arguments.

This is what my code looked like afterwards:

class_<parse_xml, boost::noncopyable>("parse_xml", boost::python::no_init)
.def("find_element", &parse_xml::find_element, boost::python::return_internal_reference<>())
.def("find_next_element", &parse_xml::find_next_element,boost::python::return_internal_reference<>())
.def("get_element_data", &parse_xml::get_element_data,boost::python::return_internal_reference<>())


def("get_filepath_from_vac", get_vdir_path_cf);
def("parse_chunkx", parse_chunkx, boost::python::return_internal_reference<>());

Another thing that I've run into on this is trying to access parameters on an exposed struct wasn't working as expected. It comes down to the fact that if you have a char * that you want to access in python, you simply can't without having a wrapper for it. When trying to access a char *, you lose the sizing information, which makes it basically useless to python.

So, to access a char * member, you need to write a wrapper function that returns a const char *. For example:

const char *parse_xml::get_value_from_element(xml_element *root) {
return root->text;

Now I can easily access the member variable I was going after.