Alex / Project1WriteUpFinal Write-Up for Project 1 1. Description of the Completed Project For this project I implemented a Half-Edge mesh data structure in C++ using an Object Oriented approach. The ultimate goal of the project was to learn about mesh representation and manipulation, with a particular interest in subdivision schemes. The capabilities and features of what I've implemented are as follows:
To use the viewer you can use the following keys while focused on the window, and continue input in the command prompt:
"How'd you do that!?" Loading/Saving models: .PLY and .OFF files have a very simple structure. The classes PLY and OFF included in the source code provide the code for parsing a text file and storing its required information for access by the HalfEdgeDS class. Each are an extension of the Model base class, which defines that subclasses store the number of vertices and faces, as well as provide a way to iterate through the list of vertices and faces one at a time. Doing it this way allows the center HalfEdgeDS class to simply pass the filename to the appropriate model parser and iterate through its information to create the mesh.
Loading vertices is just a matter of extracting the numbers from each line and creating new Vertex objects. Edge and Face objects are created by iterating through the model's face list, which just provides indexing into the vertex list. Indexes are extracted and an Edge object is created for each successive pair. Then a new Face object is created which only needs to keep a reference to one of its edges. When this is finished, we have vectors of the mesh's Vertex, Edge, and Face pointers.
Now we need the connectivity information (which edges go together). When we loaded the Face list, we created a vector of Faces associated with each vertex. So for each Edge in the Edge vector, if no twin has yet been found, we search all the Faces which contain the Edge's incident Vertex. We look for a match via the Edge class's equals(Edge*) method, which returns -1 for an Edge with the same vertices in the same order, 0 if the vertices don't match, and 1 if the vertices match in reverse order. If we yield a -1, we reverse the cycle-direction of that Face's Edges to maintain a consistent orientation across the entire mesh.
When done, the program tests that each Edge has a twin and that that twin has opposite orientation. It reports any errors; if none occur, we're ensured a manifold surface mesh.
Calculating Normals: My method for calculating normals is adapted from this PLY library. Here's the summary:
Cutting the Mesh Along a Plane: I only have a fairly naive implementation of this. The basic idea is to create a new mesh based on the cutting condition. We iterate over the face list and build up vectors of "good" faces, edges, and vertices. If any vertex on a face is beyond the cutting plane, we just throw out that face. In the end this requires completely re-indexing the elements we're going to keep, and we simply assign the data structure's element lists to the "good" ones we built up.
Subdivision: Step 1: Split each face while maintaining appropriate connectivity, resulting in a topologically equivalent mesh.
Step 2: Apply the 'mask' of each subdivision method on the even and odd vertices. Indexing makes it easy to separate new and old vertices.
Results: Load Complex Models:
  Cutting Algorithm:  Subdivision:  I never really got good smoothing results from Taubin's Method... 2. Evaluation of the "Things" See above pictures for examples of the implementations. "How good are the results, how do I know it's right?" I'm very pleased with my results. My cutting algorithm is a bit naive in that it just throws away faces instead of actually making an edge along the cutting plane, and it doesn't put a cap on it to keep it manifold. But the point of cutting was to think through how to edit a mesh while maintaining its necessary connectivity. Once I wrapped my head around the major issues with that, actually finishing the cutting in a robust way seemed like a tedious task that wouldn't result in much learning. Smoothing was never something I was that interested in, to be honest. The method I looked at (Taubin's Method) was a very, very simple scheme. There's a shrinking step, and a growing step, based on two hard-to-choose variables Lambda and Mu. While I'm pretty sure there are some errors in my implementation, the idea behind the method is as simple as you can get. Given another (free) week I'm sure I could have looked over the code more closely and determined how to make it work right, but I moved on to bigger and better things. My subdivision methods are what I'm really pleased with. Loop's Subdivision and Catmull-Clark Surfaces turned out absolutely perfectly. (You can evaluate that visually by just looking at the results...) There are ways to numerically assess how close to the 'limit' surface my models come, but given the wealth of examples for comparison and the straight-forwardness of the equations, I think assessing these methods visually suffices to declare victory. My Butterfly Scheme I think works, but I have some doubts since my canonical subdivision of a pyramid didn't get quite as smooth as the examples I was looking at. It could be a small bug/error in my implementation, or it could just be that my tension value isn't right (model in the example uses w = 1/16). Either way, I think the torus looks pretty good. "How does the implementation perform?" Short Version: Pretty well for a first draft, but it could be much better. Run times: Loading a model: As stated in the results in the first section, the most complicated model I loaded (almost 275k faces) took about a minute to load. That's not too shabby. The real overhead of constructing the mesh from a model file is actually parsing the text and retrieving the information. I also may have not used the most efficient means of tokenizing each line of input (I used the string::find(char*) function a lot).
Cutting a model: Very quickly on every model. The hand model (76k faces) from the results section was cut in 281ms. The kitten (275k faces) was cut in 921ms. Based on those numbers (and I actually never kept track until now for the purpose of this write-up) it looks like it's O(n) on the number of faces, which isn't too bad.
Subdividing: This is where I could really stand to make some performance improvements. Subdividing the torus 3 times with any method takes just over six seconds. The computational cost is my horribly inefficient way of checking if a new vertex has already been created on a previous face. As it is, for every new vertex it searches linearly through the vector of all newly created vertices for a match. This gives O(n^2) complexity for inserting new vertices into the mesh. After a couple levels of subdivision that just falls apart. A very simple solution that I thought of (but didn't implement) is to just keep the vertices sorted (on some axis value) and use a binary insert/search for the list of new vertices. This reduces to O(n*log(n)) which makes life quite a bit nicer through more and more levels of subdivision. Still, if the model is very large it probably doesn't need to be subdivided, and so for the models I worked on 6 seconds wasn't the end of the world.
Memory: My program wasn't written with memory management in mind. I don't do much more than delete temporary arrays within certain methods and delete the pointer to the model when loading a new one. Quite obviously, the memory consumption lies in allocating tons of Vertex, Edge, and Face objects. I didn't bother writing destructors for any of the classes because of all the inter-dependencies between those objects as well as the mesh object. As such, when loading multiple models in succession, you just build up more and more memory being used. Not that big of a deal because most of the models I used are small and I didn't keep the program running to load lots of them, but from a "good programming" point of view, it's a bit lacking in the memory management department.
3. Description of the Process I'll refer you to my Project Blog as a testament to where my time went and how things progressed. I updated it after just about every session I worked on it. With an extra two weeks, as mentioned in my last blog entry, I would've looked into decimation techniques. I read about one pretty impressive one, but probably would have read more on the classic techniques and implemented one of those. I'd have been more interested in that than correcting my smoothing issues, because a good decimation algorithm would give me more simple models to subdivide (and that's what really interests me). If that all went smoothly I'd probably go back to smoothing and try to fix that up. OR, if I still wasn't that interested in it, I would've transferred my code into a different framework to make the interaction a bit easier. I chose the ShaderAssignment framework because it was just so bare-bones and easy to hijack. The TrainProject would have probably been a better choice so I could incorporate buttons and interactive widgets instead of relying on key events and command line input. Mine works well enough though... Oh, another idea I had was to handle non-manifold meshes a little more gracefully. As it stands now, certain operations just aren't possible on non-manifold meshes because I didn't handle many special cases. Just a thought. Reading List: Half-Edge Data Structure resources:
Smoothing:
Decimation: Subdivision:
Most of those were pretty deep reads, if not reading the entire paper than going over the methods and figures to understand the ideas. The most helpful links were the least technical. That Gamasutra article is 100% responsible for helping me get my Catmull-Clark and Butterfly surfaces implemented. The SIGGRAPH course notes were paramount, as well. The most helpful things from the half-edge references were the diagrams illustrating all the pointer references, to be honest. 4. Self Evaluation If you've read the previous sections you'll probably know that I'm pretty happy with how I did on this project. The good results are the product of me picking a topic and a goal that I really enjoyed learning about and implementing. Not too much went wrong, really. The smoothing algorithm didn't work out on my first try, but I'm confident that it could have been fixed up if I hadn't moved on to subdivision. Technically speaking, I learned a great deal about mesh manipulation methods. Quite obviously I've gotten familiar with a handful of subdivision methods, smoothing methods, and decimation methods. Through some of the smoothing/decimation methods I even touched on calculating approximate curvature on a mesh. As stated in my project proposal, I think it's always helpful to learn and implement new data structures. And the half-edge is definitely the most elaborate one I've dealt with. While I already knew the theoretical value of going from O(n^2) to O(n*log(n)) complexity, dealing with meshes containing mountains upon mountains of data really demonstrated the need for efficient methods. Aside from that, it's kind of hard to quantify or describe what I "learned" while implementing this, but practice is always a good thing for a programmer. About projects in general: Not too much, I knew that planning is good, picking good topics is good... I will say that keeping a blog is apparently an excellent motivator for me. Doing it all over again, I would've picked a different code framework to work in (as mentioned before, the TrainProject would have done better). Apart from that, the only thing I might have changed is to completely skip smoothing/decimation after cutting and jumped right into subdivision. Subdivision was my real interest, and after [the very good exercise of] cutting there was no real reason to do smoothing or decimation before it. Perhaps if I'd done that first, I wouldn't have tried to rush through Taubin's method and I'd have gotten it right and working robustly. Other than that I'm pretty much 100% happy with the way things progressed and how my implementation developed. The only real advice beyond "Make sure your connectivity always stays consistent" pertains to programming in general, really: Work Incramentally! In the past I was one of those students who wrote his entire programming assignment at once, ran it, and said "Oh crap..." because I had no idea where it went wrong. I've since changed my ways and I think most programmers realize that lesson pretty quickly, but doing things that way was a really good practice when dealing with as much data as a mesh contains. You [Mike] stressed that pretty well from the beginning, for example pertaining to subdivision: First make sure you can divide each face into a topologically equivalent mesh, then start moving things. And as always: Make sure you type your equations right and USE PARENTHESES! (My initial subdivision was going WAY awry because I forgot to put a numerator in parentheses... took me all night to hunt it down...) 5. Evaluation of How the Project was Run I thought the project was run completely satisfactorily. Expectations were laid out, milestones were set up, everyone knew what was going on and knew it was their responsibility to make it happen. Perhaps some people function better when they need to turn things in periodically, but I think, in this class especially, it was announced pretty early on that we were kind of being let loose to do our project. And for me that worked out very well. Instead of writing up a progress report each week, I was writing more implementation. Maybe that's just me, but I thought the whole process rocked. The best thing about the project for me was the blog. And I think there are two reasons for that:
The process of looking around the SIGGRAPH notes for topics was just OK for me. My problem with that is that a lot of us are still very early in our graphics careers, and most of the things [that I saw] discussed were pretty advanced techniques. Of course, that can be used to motivate learning the fundamentals of the underlying topic, but for me it was just a lot of "Wow that's waaaaay ahead of me." In the end, I didn't choose a topic based on that exercise. I'd wanted to do meshes and subdivision since 559, and this project gave me an excellent platform for doing that. The planning process was good, especially in light of the aforementioned comment about a lot of topics being too advanced. The planning we had to do made us lay out exactly what we were going to accomplish, and at the very least you could have shot us down because it was too much. I think the whole "forcing people to ______" is a tough question. Personally, I'd be against it because I think if people can't take some initiative and get things done - that's their problem. Especially when it was clarified early on that you were taking kind of a hands-off approach to our projects. You might consider doing things on a case-by-case basis based on their progress or initiative, but that would be pretty hard on you I'd imagine, and would also single people out. My only further comment about the blogs is that more feedback can never hurt. Even if it's just a "Looks good." or something more in-depth, I think letting people know that you're actively monitoring their progress is a good thing. It might just make people update it more and still manage to avoid weekly progress reports. I didn't find the cohort aspect to be that positive or negative either way. I'm pretty neutral on the topic. It was nice to see how Cory's project was coming along and see how our results compared, but we didn't do a whole lot of discussion. But the way I see it - getting people together to bounce ideas off each other has never been bad, right? As far as the course in general goes, I'm pretty happy with it so far. The format is good and the lectures are interesting, though I'm pretty antsy to start talking about more animation-related topics. I like pretty pictures as much as the next guy, but making things move is definitely where it's at, and I hope we can spend a lot of the second half of class talking about it. PHEW!  |