CodeItNow

For a little under a year now, I’ve been using Modo to learn how to create 3D models. I’m doing this partly for fun, and partly to help me think about game engine features from the perspective of an artist. Along with the traditional poly-modeling tools, Modo (like many other 3D tools) also has support for subdivision surfaces. A subdivision surface basically allows you to create a low-poly control mesh for your model, and to add detail, you let the application divide each face in your mesh according to a set of rules.

Here’s an example:

Notice how few polygons there are in the leftmost model. At each increasing level of subdivision to the right, each face gets split into four new faces to add detail. This allows the square hole with sharp edges to become a nice round hole with smooth edges. If you made a mistake (as I frequently do), then it is relatively easy to fix the mistake in the low poly control mesh because there are so few vertices to deal with.

Sounds good, right? Mostly it is, but there is a fairly steep learning curve to subdivision surfaces. One of the main problems is really understanding how your original control mesh relates to the subdivided version. None of the points in the control mesh are guaranteed to remain in the exact same position once the subdivision has occurred, and working out where these points are going to move can sometimes seem like voodoo. In various forums, arguments rage on about edgeloop modeling, E-Poles, N-Poles, keeping only regular vertices, avoiding triangles, n-gons etc. I really wanted to better understand what was going on during subdivision, so I started to dig a little deeper into the details. In the rest of this article, I’m going to share what I’ve learned so far.

A Little Background First

How exactly does a 3D application decide how to subdivide a control mesh? Well, there are a few different subdivision schemes out there, but the most widely used is Catmull-Clark subdivision. Since the original paper by Ed Catmull and Jim Clark, there have been a number of improvements to the original scheme, in particular dealing with crease and boundary edges. This means that although an application might say that it uses Catmull-Clark subdivision, you’ll probably see slightly different results, particularly in regard to edge weights and boundaries.

Rules of Subdivision

The original rules for how to subdivide a control mesh are actually fairly simple. The paper describes the mathematics behind the rules for meshes with quads only, and then goes on to generalize this without proof for meshes with arbitrary polygons. I’m going to go through a very simple example here to show what happens when a mesh gets subdivided. I’m going to be concentrating solely on non-boundary sections of the mesh for simplicity. Also, the example uses a 2D mesh, but again this is only for simplicity, and the principles expand to 3D without change.

There are four basic steps to subdividing a mesh of control-points:

1. Add a new point to each face, called the face-point.
2. Add a new point to each edge, called the edge-point.
3. Move the control-point to another position, called the vertex-point.
4. Connect the new points.

Easy, right? The only question left to answer is, what are the rules for adding and moving these points? Well, like I wrote earlier, this really depends on who implemented it, but I’m going to show the original Catmull-Clark rules using screenshots from Modo. This doesn’t mean that these are the rules that Modo applies, but it should be fairly close.

Here’s the example mesh I’m going to be using:

No prizes for guessing which face we’re going to be looking at. I’ve made it a little bit skewed because that makes things more interesting. If you’re wondering about the double edges around the boundary, I’m going to be writing about those at a later date, so be patient! For now I need them to make the boundary hold shape, but they can be safely ignored for the purposes of this article.

Step One

Firstly, we need to insert a face point, but where? Well this is easy, it just needs to go at the average position of all the control points for the face:

I’ve drawn red dots approximately where each new face-point will go. The big dot is obviously the face-point for the highlighted face. The location for each dot is simply the sum of all the positions of the control-points in that face, divided by the number of control-points.

Step Two

Now we need to add edge-points. Because we’re not dealing with weighted, crease or boundary edges, this is also fairly simple. For each edge, we take the average of the two control points on either side of the edge, and the face-points of the touching faces.

Here’s an example for one edge-point, in blue, where the control points affecting its position are pink, and face-points are red. Note that the edge points don’t necessarily lie on the original edge!

For the highlighted face only, I’ve drawn all the roughly where each new edge-point will go in blue:

Step Three

This step is a little bit more complicated, but very interesting. We’re going to see how we place the vertex-points from the original control points, and why they get placed there. This time, we use a weighted average to determine where the vertex-point will be placed. A weighted average is just a normal average, except you allow some values to have greater influence on the final result than others.

Before I begin with the details of this step, I need to define a term that you may have heard used in regards to subdivision surfaces - valence. The valence of a point is simply the number of edges that connect to that point. In the example mesh, you can see that all of the control points have a valence of 4.
Alright, I’m going to dive into some math here, but I’m also going to explain what the math actually means in real terms, so don’t be put off!

The new vertex-point is placed at:

(Q/n) + (2R/n) + (S(n-3)/n)

where n is the valence, Q is the average of the surrounding face points, R is the average of all surround edge midpoints, and S is the control point.

When you break this down, it’s actually fairly simple. Looking at our example, our control-points have a valence of 4, which means n = 4. Applying this to the formula, we now get:

(Q/4) + (R/2) + (S/4)

Much simpler! What does this mean though? Well, it says that a quarter of the weighting for the vertex-point comes from the average of surrounding face-points, half of it comes from the surrounding edge midpoints, and the last quarter comes from the original control-point.

If we look at the top left control point in the highlighted face, Q is the average of the surrounding face-points, the red dots:

R is the average of the surrounding edge midpoints, the yellow dots. Note that the yellow dots represent the middle of the edge (just the average of the two end points) which is a little bit different from the edge-points we inserted above because they don’t factor in the nearby face-points.

S is just the original control-point, the pink dot:

Below is my rough approximation of where all these averages come out, using the same color scheme as before. So the yellow dot is the average of all the yellow dots above, and the red dot is the average of all the red dots above.

Now all we do is take the weighted average of these points. So remember that the red dot accounts for a quarter, the yellow dot accounts for half, and the pink dot accounts for the final quarter. So the final resting place for the vertex-point should be somewhere near the yellow dot, slightly toward the pink dot, roughly where the pink dot is below:

So now I hope you can see why the control point is going to get pulled down and to the right. All the surrounding points just get averaged together and weighted to pull the vertex around. This means that if a control-point is next to a huge face, and three small faces, the huge face is going to pull that vertex towards it much more that the small faces do.

One other thing you can see from this is that if the mesh is split into regular faces, then the control point won’t move at all because the average of all the points will be the same as the original control point. The pull from each face-point and edge midpoint gets canceled out by a matching point on the other side:

Step Four

The final step is just to connect all the points. Confusingly, Modo has two ways to subdivide a mesh which actually return slightly different results. I don’t know why this is, or how the subdivision schemes differ, but they are close enough for all intents and purposes to call the same. For clarity, I’m using a screenshot from Modo where I have subdivided using the SDS subdivide command. For the highlighted face only, I’ve drawn the new face-point in red, the new edge-points in blue, and the moved vertex-points in pink:

Below is an overlay of the original control mesh for reference. As expected, you can see that the top left control-point gets pulled to the right. The same process is applied to all faces, resulting in four times as many quads as we had previously.

One More Thing

If you look at the formula for moving the control-point to its new location, you can see that not only are the immediate neighbor points used, so are the all the rest of the points in the adjoining faces. How much any single one of these surrounding points affects the control-point isn’t very clear from the original formula. This information is actually really easy to find out just by substituting in the surrounding points into the original formula.

I’m making the assumption from hereon out that all of the surrounding faces are quads to make things easier on myself. Also, I’m not going to write down each step of the expansion here since it got pretty big, but at the end, I got the following weights:

Control-point weight = (4n-7) / 4n
Edge-neighbor weight = 3 / 2n^2
Face-neighbor weight = 1 / 4n^2

I’m using the term edge-neighbor to denote a neighboring point sharing the same edge as the control point, and face-neighbor as a neighbor that only shares the same face as the control-point. In the picture below, the edge-neighbors are cyan, and the face neighbors are yellow. Note that for quads, you have exactly n edge-neighbors, and n face-neighbors.

Applying this formula to various different valences, you get the following weights for a single point of the given type:

Valence	Control	Edge Neighbor	Face Neighbor
3	5/12	3/18	1/36
4	9/16	3/32	1/64
5	13/20	3/50	1/100
Infinity	1	0	0

What does this mean? If we look at a the valence-4 row, you can see that if you move a face-neighbor, that’s going to affect the position of the vertex-point by 1/64th of however much you move it. So if you move it 64 cm on the x-axis, then the resulting vertex-point will move 1 cm in the same direction. I tested this scenario out in Modo, and it seems to match up very closely.

Clearly, the edge-neighbors are weighted more heavily than the face-neighbors, and the control-point itself always the most influence on the final vertex-point location. Remember though, each point represents a different thing (control-point, edge-neighbor, face-neighbor, nothing) depending on which particular face is getting subdivided!

It is interesting to note what happens as the valence gets larger and larger. The control-point influence tends towards 1, while all the neighboring points tend to zero. The reverse is also true, where at valence-4, the control-point weight is about 0.56, at valence-3 it is only 0.41 which means it is getting pulled around by its neighbors a lot more.

Wrap Up

I’ve learned a lot while investigating Catmull-Clark subdivision. There’s a lot more to learn, and a lot more to share, but I don’t have the time right now. This post was much longer than I thought it would be, so I’m going to look at some other aspects of subdivision modeling in later posts. One of the next things I’m going to look at will be how the rules change for boundary points, since these are often the bane of my modeling life…

I’m not really sure this will make me a better modeler, but at least I have a much better understanding of what will happen to my mesh when it gets subdivided. Hopefully I will be able to apply this knowledge to make my modeling process more predictable.

Remember that this only applies to non-boundary/crease points, and that different applications may use different weights for the points.

If you’re interested in checking out Modo, they have a 30 day trial available on the Luxology website. It’s really rather good, and I’ve seen some absolultely stunning images on the forums which were modeled and rendered using Modo.

No comments

While I was reading through some C# 2.0 code that a friend of mine wrote, I noticed that he was finding some objects in a List using a foreach loop. As soon as I saw that, I thought to myself that I would probably have done that using FindAll with an anonymous delegate.

That got me thinking about all the different ways you can find things in a List in C#. I’ve recently upgraded to using Visual Studio 2008, so with the advent of C# 3.5 there are even more ways to do something like this. Which method is best is not very clear, so I thought it was time for some performance tests.

The Test

I decided that a nice and simple performance test would be to find all the numbers less than 10,000 in an array of 1,000,000 random integers. To even things out, I perform the same test 100 times for each method, and take the average time. I generated the set of random numbers once, and then used that same set in all tests.

Techniques

So far, I’ve thought of eight different ways to implement the performance test. There are probably more ways, but these seem to be a fairly sensible set:

1. Use a for loop and index into the list.
2. Use a foreach loop.
3. ForEach function in List.
4. FindAll function in List with an anonymous delegate.
5. FindAll function in List with a lambda function.
6. Count function in List with an anonymous delegate.
7. Count function in List with a lambda function.
8. Linq.

Results

I ran the tests on my laptop in the standard release config. I verified that all implementations returned the same number of items.

Technique	Time(ms)
For Loop	8
ForEach Loop	6
ForEach Function	10
FindAll Function Delegate	11
FindAll Function Lambda	11
Count Function Delegate	34
Count Function Lambda	34
Linq	19

Well it turns out that my friend had indeed picked the best way to find things in an unsorted list. I was surprised that the for loop was so much slower than foreach, but then I took a look at the IL. The foreach implementation had one virtual function call to GetEnumerator at the top of the loop, and then used non-virtual function calls to get_Current on the enumerator inside the loop. By contrast, the for loop had virtual function calls to get_Item inside the loop.

Clearly, using delegates and lambda functions makes no difference. Looking at the IL in Reflector, they generated identical delegates. That’s enough for me to avoid delegates wherever possible, since the lambda functions were much easier to read.

I had heard about the relatively poor performance of Linq, but I was surprised that it was really three times slower than the best solution. There was more code to write than using FindAll with the lambda function, so it was no more brief either.

While I was looking though the list functions, I came across Count, so I thought I would include it here. I don’t know why you would ever use this function given how terribly it performed. Initially when I saw it, I thought that maybe it was used internally for Linq, but I don’t suppose it can be. I’d be interested to know what its purpose is.

I hope this was informative!

p.s. Charles just pointed me to this page explaining some of the reasons behind the current performance of Linq.

1 comment

Well, there’s not much to report really. I’ve been spreading myself very thin recently, investigating a few different things, so I thought might be nice to post a status update.

Variance Shadow Maps

Yes, I’m jumping on the variance shadow maps boat. They look nice, they’re easy to implement, and have relatively small overhead over traditional shadow maps. I read the article in GPU Gems 3, which is also available here, and it was pretty easy to implement from there. It probably took me about 2 hours to go from no shadows at all to variance shadow maps. After a bit of tomfoolery to get rid of the light-leaking I ended up with the image below. I haven’t implemented any bias yet, so there are some errors there, but the VSMs appear to be working very nicely.

Better Tone Mapping

My current tone mapping algorithm doesn’t look that good, so I’ve been investigating any alternatives. I was initially put off Reinhard tone mapping when I first looked at the DirectX HDRLighting sample a long time ago because it treated each channel completely independently. This is a really nasty idea since it can change the hue of the image during tone mapping as each channel gets compressed by a different amount. I recently re-read a gamedev article and then implemented Reinhard’s tone mapping using based on the pixel luminance, which gave much nicer results, and didn’t change the hue. One note on that article though: It says that to convert to RGB from the final luminance you need to multiply by the luminance, which doesn’t seem right. What I did was to divide by the old luminance and then multiply by the tone mapped luminance. It’s hard to tell right now if it looks better or worse, it’s just different.

The image above is using this new tone mapping, but I’m not doing the dynamic image key calculation at the moment. That basically gives me three variables (image key, midzone luminance, and white luminance) which aren’t very intuitive to tweak. I’ve generally been leaving the midzone gray at 0.18 as suggested, and then tweaking the image key and white luminance to get something that looks OK.

Windows Presentation Foundation

I’ve spent a lot of time at work recently improving one of our C# tools, which is Windows Forms based. There are many things I dislike about Windows Forms, like the lack of built-in support for something useful like the command-pattern, the horrible input handling, menu shortcuts, you name it! For my own education, last weekend I started reading about the latest and greatest from Microsoft: The Windows Presentation Foundation. From my brief foray into WPF, it seems that a lot of the the things in Windows Forms that I’ve spent time trying to fix or circumvent appear to have been adressed.

For example, in Windows Forms, if you don’t handle a key-press event in a control, then no-one else gets to handle it either, unless they have specifically attached an event handler to that controls key-press event. In WPF they have the notion of tunneling and bubbling commands. This basically means that if you don’t handle that event then your parent gets a chance to handle it (it bubbles up), and vice-versa for tunneling events.

There seems to be a much greater emphasis of splitting the View from the Model (in the Model-View-Controller sense that is), with only very loose references (or none at all) required to bind everything together. I’m very interested in finding a good method for splitting the View code from the Controller and Model code, so I’ve been reading a few articles, some of which you can read here: Model-View-Controller, Model-View-ViewModel, Presentation Model. I really liked Martin Fowler’s description of Presentation Model in particular. The Model-View-ViewModel paper was also a good read, but I really dislike the resuse of the words Model and View in the terminology (it’s doubly confusing since I already have C++ classes called Model and View representing a 3D model and a view point respectively). In Windows Forms you seem to be almost forced to keep your View and Controller code tightly bound, but there appears to be much more freedom in WPF.

I also bought a book about WPF by some bloke from Microsoft called Adam Nathan, which so far has been some good reading (despite the liberal sprinkling of exclamation marks on every page). I’d love to see a book that combines WPF and something like Model-View-ViewModel to create a real-world, complicated application rather than the fairly simple examples that appear in books and online articles. If anyone knows of a book like this, then please let me know!

Oh, but it’s not all roses in WPF though. One of the first videos I watched was this one. If you’ve seen it, then you probably have the same same thought running around your head that that I did when I first watched it: WTF? You’re basically allowed to reuse some storage from a dependency property that isn’t used to affect your control. For example, assuming you’re not parented to a DockPanel, you can use something like DockPanel.Width to store an arbitrary number. It’s like the Tag in Windows Forms, but much much worse. Microsoft seem to be touting it like a really cool feature, when it feels more like a dirty hack to me. Using unused properties to store arbitrary data is a really quick way to make your code unmaintainable as far as I’m concerned. I don’t want to have to search the code for where someone put the data into the property in order to work out what it is actually storing… Urgh!

Articles

Yeah, I’m about 80% through writing one about storing function call arguments in MockItNow at the moment. It’ll be up as soon as I finish the last 80%.

That’s all!

3 comments

I finally took the plunge to set up my own website! I’ve been wanting to do this for a while to be able to share some of the things that have interested me as I spend my spare time writing a small game engine. I hope that someone somewhere finds these things interesting!

One other reason that I set up the site is to have central place to store information about a couple of small pieces of software I wrote: DoItNow and MockItNow.

DoItNow is a little addin for Visual Studio 2005 that I use both at work and at home to speed certain parts of the development process up. It’s like Visual Assist, but not as good, and freer.

MockItNow is a C++ mocking framework. If you write unit tests in C#, then you have probably tried out using something like RhinoMocks, or maybe TypeMock. There isn’t much choice in C++, so I wanted to see if I could write something.

MockItNow was a great venture into the unknown for me. I wasn’t at all sure that I would be able to pull it off at the start. In fact, I had two failed attempts (based on ludicrous ideas) before I landed on what I use now. Along the way I learned a lot about areas I’d never looked at in great detail before, like stack frames, x86 assembly, calling conventions, type traits… The list goes on and on. I also learned some nasty little tricks that you can do in order to get at certain pieces of information I needed along the way too. I wouldn’t recommend using some of these techniques, but I had to do what I had to do.

I’ll be providing some more of the gritty details about how MockItNow works over the coming weeks, but If you can’t wait, then feel free to download it and take a look.

The site’s still a bit of a work in progress at the moment, but I set myself the goal of getting something up this weekend, so here I am. Unfortunately the great weather stole a lot of my time, but be sure that I’ll be improving things as I learn more!

1 comment