Alex / Project1BlogQuicklink: Surfaces Page,Project1Proposal,Cory's Blog March 26,2009 by alex (link) All of last night's work was fiddling with my cutting algorithm trying to move vertices to the cutting plane and make it all pretty but it just turned into a mess... I did manage to tweak it just a hair so that it recognizes the newly formed border along the cut polygons. Tonight I wrote an OBJ parser (because I was sick of all my models) which was a bigger pain than anticipated because nobody can just follow conventions when creating them.  But when that was done(ish) I tested out my implementation for the boundary cases for Loop subdivision, with good results:   So you see the cutting is pretty ugly, but the subdivision works fine. I looked at all the equations for Butterfly edge cases, but there are like 7 different boundary cases to check for and different equations for each, sooo I decided not to bother. I'm actually much busier this week than anticipated, which is why I stopped decimation at the reading/understanding phase and didn't get around to implementing it. I understand Garland's method at a high level, but I am having trouble wrapping my head around computing the cost function. In RTR chapter 12 they present a simple form of the function, but I was still a bit confused by one of the terms involved. The paper linked a couple posts down on decimation I found a pretty easy read and actually pretty impressive visually. Its comparisons to QSlim (Garland's) look very similar. If I were to implement a decimation scheme, I'd probably try that one since it seems a little more straight-forward to me. Like we talked about, though, there's a lot of overhead just implementing a half-edge collapse operation. Not to mention a customized priority queue to sort the importance of each collapse. It's more code than I really have time to churn out right now, unfortunately. Not sure if I'll be able to put any more time into this. Perhaps Sunday morning? March 24,2009 by alex (link) Tonight I added boundary support to my data structure and implemented the boundary cases for Catmull-Clark subdivision:  I'm trying to adapt my cutting algorithm to actually figure out where its new border is so I can experiment with more non-manifold models. I also plan on implementing the boundary cases for the other subdivision methods as well. March 6,2009 by alex (link) Just wanna give big props to Gamasutra for common-sensically explaining and presenting the equations for both Butterfly and Catmull-Clark subdivision. Great link: http://www.gamasutra.com/features/20000411/sharp_01.htm March 5,2009 by alex (link) OK so it's coming towards the end of project-time. There are a couple things I'd still LIKE to do but I don't think I'll have time. For example, I'd like to put some time into that decimation algorithm linked below. I also think within that method lies some foundational ideas for perhaps converting triangle meshes into minimally-different quad meshes for getting Catmull-Clark surfaces, which was actually one of the earlier topics I was interested in. BUT, I have another Computational Photography assignment due next week that I haven't started yet and will require a lot of time and energy. Since the goal of this project was to build a [relatively] robust half-edge data structure and implement subdivision schemes, I'm going to call this a big success. Big. I had a really, really good time learning about the data structure and all the different mesh operations, and while I didn't get to implement all of them to their most satisfactory state, I really learned a lot about meshes from the papers I looked at. If I have time I might just look over what I've done already and clean things up, eg maybe putting the cap on my cutting algorithm or correcting the issues in my Taubin smoothing. But other than that I think I'll have to put the project to rest and be satisfied that my ultimate goal of getting beautiful subdivision surfaces on a home-made mesh data structure was 100% a success. March 4,2009 by alex (link) Link to remember: http://wscg.zcu.cz/wscg2004/Papers_2004_Full/F61.pdf I've kind of abandoned Kobbelt subdivision because I can't find any good (non-technical jargon) descriptions of the masks it uses and I can't quite figure out how to apply them properly. I'm going to try my hand at the above decimation technique as it seems pretty straight-forward, and a good decimation algorithm will give me more simple models to test subdivision on. This post is really just so I can easily find that paper when I get to work. March 3,2009 by alex (link) Fixed up my Butterfly Scheme to handle extraordinary vertexes, seems to work pretty well:  Three iterations later:  You can definitely tell the difference between C1- and C2-continuity when you compare the results using Loop's subdivision (C2) versus this Modified Butterfly Scheme (C1). March 2,2009 by alex (link) Catmull-Clark surfaces rock my socks off. The main challenege of subdivision was actually dividing the faces while maintaining all the correct half-edge connectivity references. But after I got a working general strategy on that it was just a matter of getting the right numbers punched into the right vertexes. I also had a go at the Modified Butterfly Scheme today but I couldn't quite get the extraordinary vertex cases to work out, so I moved on for the time being because I've been anxious to do Catmull-Clark since 559. Happy to say they work splendidly, at least on the 4 non-triangle mesh models I have right now... Results!         I'm going to try to fix up my Butterfly Scheme next and then work on an interpolating Quad Subdivision method (Kobbert). March 2,2009 by alex (link) I lied, I couldn't stop thinking about what could be wrong with the subdivision. Looked over a couple papers/references on it, they all had a little bit different notation for weighting even (original) vertexes. Turns out I wasn't factoring in the vertex's valence correctly. Now it's just a thing of beauty, really. An ugly, inefficient thing of beauty. I'm actually really happy with everything except my method of not creating duplicate vertices. Logic would tell me to hash them or keep track of them in some efficient manner, but right now I'm just linearly searching. But that's beside the real educational thrust of the experience. Results!   After 2 iterations it's already pretty darn smooth. Shaded wireframe after 3rd iteration:  March 1,2009 by alex (link) If I said I wasn't struggling I'd be lying. But, things are at least progressing. It's a surprisingly daunting task to decide how to subdivide a mesh. (Keeping some of the original, starting a complete new one, keeping track of old parts vs. new parts, etc). At the very least I've managed to subdivide triangle meshes into a topologically equivalent mesh with a consistent Half-Edge structure. At that point I said "Great, now just gotta move the points around." This was harder than expected. I chose to keep the mesh's original vertex list to avoid allocating tons of new memory (every time I try to delete something my program crashes, don't feel like hunting down why). Well that delivered the problem of traversing through a web of old/new vertexes. With the indexing it's easy enough to tell if a vertex is new or old, but navigating around to an old vertex's OLD neighborhood in order to weight its new position was a confusing task. The most frustrating part is that I'm really close. I feel like my new vertexes are being positioned appropriately, but something's going awry with the displacement of the original mesh points. It's almost midnight and and I'm tired so I'm not going to continue hunting this down tonight, but here are my current results. Torus:  After 3 iterations of Loop's subdivision: You can see the original control points don't quite conform to the limit surface like the rest of the points. Not sure what's causing this; I think I'm following the equations pretty accurately...  February 27,2009 by alex (link) Tonight I may have (did) gotten ahead of myself. I started my work on performing Loop subdivision. I unfortunately spent a good chunk of time initially splitting each face. That turned out to be a pretty poor choice. My current implementation (which is incomplete) is to first split each edge into 2 edges (preserving linkage) and then somehow (semi-iteratively) create each face's internal faces and link all of it together to preserve the half-edge structure. Since I spent a lot of my night implementing a method that absolutely will not work, I'm still working on this. BUT, I do have a much better game-plan in place, and any free time I have this weekend will be spent working on this [and hopefully other] triangle subdivision schemes. February 25,2009 by alex (link) The only real addition for tonight was changing that one thing about Taubin smoothing. I still don't know how to choose good values of lambda and mu to ensure that the model doesn't completely disappear from the shrinkage of a number of iterations. Lame. I spent most of my night rearranging the program's control structure (ie How you tell the window to load/save/edit the model in the view). Just giving each operation a key and making the FlTk window handle it was getting sloppy and really not elegant. Now there's a few base keyboard events for loading, saving, transforming, and editing the mesh. These bring up other prompts in the command window for further input. Much cleaner, and way fewer keys to remember. I was initially interested in Quad meshes because I wanted to implement Catmull-Clark subdivision, but almost every model I have is entirely composed of triangles. There are a couple exceptions; the shark model, in particular, is composed primarily of quads. I've also written a few very simple shapes from quads (a cup, a chess piece) that will make good test subjects for Catmull-Clark subdivision. Given that most of my models are triangle meshes, the next thing I'm going to look into is simplification methods via edge collapsing. A good simplification scheme would give me models that would be good for testing a triangle subdivision scheme, like Loop, Butterfly, or sqrt(3). Probably start on simplification tomorrow. February 25,2009 by alex (link) I just wanted to give a note about how I'm approaching face orientation consistency, kind of as a response to Cory's approach. As part of the Edge class, I have an equals(Edge*) method. This returns 1 if the compared edge has the same vertexes in opposite order as the edge, 0 if they don't share vertexes, and -1 if they share the same vertexes but are in the same order. When I'm loading vertexes and edges from a file, I maintain a list of adjacent faces for each vertex. When I'm done creating every edge present in the input file, I go about finding each twin's vertex using this adjacentcy list. I iterate over each edge in each face adjacent to the current vertex, seeing if the edges are equal. If they're indeed equal but face the same direction (equals() yields -1), I reverse the adjacent face so the edge cycle goes the other way. On most manifold models, this does well. There are a few models that haven't worked, but at this point in the project and for the level of robustness that I will settle for, I'm pretty happy with the result I've gotten from this procedure. I test for this after loading each model by iterating the edge list ensuring that for every edge E, E(vert0,vert1) = E->twin(vert1,vert0). For most truly manifold meshes (for every edge E there exists E->twin) this method has done very well. Thoughts, criticisms, additions, etc, are more than welcome.
February 24,2009 by alex (link) So... My implementation of Taubin smoothing "works" I think. The trouble I'm having is choosing good values of lambda (L) and Mu (M) to preserve the size of the mesh while also smoothing it nicely. I came close on the shark model but that was already very smooth to begin with. Tests on the torus and teapot models definitely smoothed them out, but the values for the torus resulted in significant shrinkage, and the teapot isn't manifold so the pieces separated from each other in addition to the shrinkage. Perhaps I lost the method of choosing good values in Taubin's jargon about 'transfer functions' and signal processing lingo, but on the bright side I'm fairly certain the algorithm itself is sound. My only question on the algorithm is this: While iterating through the vertex list, if a vertex in the neighborhood being looked at has already been moved due to smoothing, do we use that new value to contribute to the current vertex? Or during every iteration should we use all of the vertexes' original positions before smoothing? I'm currently using the former method, but I feel the difference between the two methods would be noticeable and I don't want to get it wrong. No time to implement it both ways tonight though. At this point I handle non-manifold meshes by simply breaking from the weighted-summing loop when I encounter a twin-less edge and compensating for any potential lost weight. As with cutting and - probably in the future - subdivision, making these operations truly robust to all arbitrary meshes (manifold/non-manifold) is more of a tedius programming exercise than a truly useful learning experience. I'm personally very content learning the concepts and getting a good handle on the math behind these [and more advanced] methods, but ensuring their performance on any arbitrary mesh will be more busy-work than true education, I feel. February 24,2009 by alex (link) Found another directory of supposedly manifold PLY files. Here's the ones I tested my load on with good results. A nice handful of good, correctly oriented (or orientABLE), completely manifold, interesting models:
Models found here. Currently working on Taubin's Smoothing Method. Hopefully shouldn't be too hard. February 23,2009 by alex (link) I'm not doing any actual coding tonight (all my current progress is on my work computer). But I'm thinking long and hard about numerical ways to determine if edges are oriented in a clockwise or counter-clockwise fashion. If I can determine that based only on the points on the face, at load-time I can guarantee that every face created is oriented the same way, and that every half-edge's twin will have the opposite direction. If not... well I'll need to think of something else. February 22,2009 by alex (link) Been busy all weekend with my Computational Photography assignment, due tomorrow at midnight. Work on this project will resume on Tuesday. February 20,2009 by gleicher (link) I was hoping that cutting would be an instructive exercize, and you've confirmed it! And yes, that smoothing paper is a good one. Its a little harder than the simple (Taubin's method) smoothing, but a lot better. I'd recommend starting with the easier one. We'll discuss it in class (but maybe not before you want to implement it). February 18,2009 by alex (link) Boy was I feeling good about my initial (simple) cutting algorithm. Cutting all the models along a given axis at a given value was working perfectly... until I checked how many vertices I was storing. Cutting my shark down the middle (Z = 0) started at 2560 vertices and 2562 faces, ended up at 4832 vertices! It's because I was storing every face's every vertex as a unique vertex, instead of the original model-loader approach of indexing the vertices first, then building edges/faces just referencing their indices. To be honest I thought cutting was a pretty silly exercise to go through in developing a mesh, but it turns out that it really requires thinking through a lot of book-keeping and structural problems, and is a great exercise for developing a robust mesh. Touché. More thought definitely has to go into managing the reconstruction after cutting. But on the bright side, the actual initial algorithm to just get rid of polygons seems to work fine:  Link to remember: Impressive smoothing algorithm for later, perhaps? February 17,2009 by gleicher (link) The idea of storing the faces with the vertices means that information is duplicated, causing a a problem when you start modifying things (since you have to keep them consistent). In general, this is a caching strategy. There are others, like keeping the 1-ring, or the shortest path distance to all other vertices, ... February 17,2009 by alex (link) So the management of the edges went splendidly. Storing a list of faces for each vertex was simple and sufficiently inexpensive, and now twin-finding is incredibly fast. The real time-consuming operations are actually reading and tokenizing the lines of the input file, especially when creating edges. I also implemented normal calculation based on the implementation linked below. Here are some results: Stanford Bunny - 69,451 faces, 208,353 half-edges, 20.1sec load time Teapot - 1,024 faces, 3,072 half-edges, 282ms load time Shark - 2,562 faces, 10,240 half-edges, 953ms load time Kitten - 274,196 faces, 822,588 edges, 74.8sec load time :-( Those are all using per-face normals, and that was just a laziness factor on my part as I was wrapping up my shift at work. The normals ARE calculated per vertex as well, to allow for smooth shading. February 17,2009 by alex (link) Good find by Cory, this guy managed his edges by storing for each vertex all the faces that include that vertex. This means that finding an edge's twin is a matter of searching only the faces touching its incident (or source) vertex, not the entire edge list. Brilliant. February 15,2009 by alex (link) PLY is really subpar on including normals. This guy has an open source PLY library with some code that calculates the face normals from the vertices. This will be very useful later. February 15,2009 by alex (link) One of the more complicated models I tried to load had over 280,000 half-edges (which actually isn't that many relative to a lot of other models), so I'll obviously need some method of searching them efficiently. The method that immediately comes to mind is bucket-hashing them, but I'll be searching through other people's work to see if I can find out how they manage their edges. February 12,2009 by alex (link) So, it's absolutely by no means robust/stable at this point, but to some small degree I can read in a .ply file, construct a data structure for it, and display its wireframe. The real problem I'm running into is finding which pairs of edges go together. ie Find each edge's opposing edge. Right now I'm just scanning the list of all edges for one that has opposite endpoints for each one. But a) That assumes every face of the mesh is declared in the same order (clockwise/counterclockwise), and b) That's ridiculously, ridiculously slow when dealing with any practical model. The chain is simple enough that that's not really an issue.  February 11,2009 by alex (link) Tonight I laid a painfully simple foundation for the classes I think I'll need. Basic frameworks for Vertices, Edges, Faces, HalfEdgeDS, and a PLY parser are in the works. Most work tonight went into the PLY parser so I can get some data to work with efficiently. I'll continue working a bit tonight on that. Also in my searching for design ideas I came across this mesh library that implements a half-edge data structure in C. I haven't built or really looked at it yet (literally JUST found it). One thing I noticed about that library is that it is limited to triangle meshes, but the author claims "Because all the data structures are based on double linked list, it is straight forward to generalize the library for arbitrary sided faces." Perhaps if this whole from-scratch thing doesn't work I can generalize his code, make it parse a more common format (he uses OFF/NOFF format?), and proceed to do more interesting things with surfaces? Food for thought, at least. February 8,2009 by alex (link) This morning I've basically been familiarizing myself with some mesh file types, namely .obj and .ply. OBJ files seem easier but PLY files seem more robust and customizable (especially in regards to edges) and will probably be a better suit for a generic mesh data structure.
February 3,2009 by alex (link) So far from the suggested Surfaces/Subdivision readings, I've looked at these:
February 1,2009 by alex (link) Currently: Creating decent Catmull-Clark surfaces from triangle meshes. Recommended reading from Mike: http://portal.acm.org/citation.cfm?id=1409101 An open-source subdivision library that deals with Quad meshes (Catmull-Clark subdivision) and Tri meshes (Loop subdivision): http://www.cs.nyu.edu/biermann/subdivision/ |
