February 9,2009 by bfield (link)
Mesh data structures

When I did subdivision for 559, the data structure I used for storing the mesh was a doubly connected edge list (DCEL). It's basically a half-edge structure (I believe the doubly-connected part comes from the fact that you connect the two halves of the edges). Searching for that data structure might be useful.

One thing that might prove useful if you try implementing any of these yourself is to write some testing code to make sure certain invariants are always true for your mesh (the twin of a edge's twin is itself, every edge has a valid twin, traversing the next pointers always keeps you on the same face, etc). This would've been helpful for me to hunt down inconsistency bugs in your code (especially if you are planning on updating it in place).

February 8,2009 by alex (link)
Link

My Project Page

Going to try to implement a general mesh data structure, probably the half-edge. This is probably a good place to start thinking about the design.

February 6,2009 by aderhold (link)
Initial thoughts

My Readings

I started my reading by just reviewing the surface-related reading from 559, and then moved on to a high-level reading of the SIGGRAPH subdivision course and a paper on mesh data structures.

For project ideas, I think the idea of adding Catmull-Clark subdivision to an open source library sounds both interesting and feasible. I'll look into that more this weekend.

February 6,2009 by bfield (link)
My first thoughts

My P1 reading I'm probably going to be doing something involving 3D surface point labeling. The basic problem is figuring out the best (or possibly most efficient) way of labeling some set of points on a surface subject to some set of constraints.

February 5,2009 by cory (link)
Initial Posting

Here's my P1 page!

Should get these initial posts out of the way so we can Discuss things sooner

February 3,2009 by alex (link)
Subdivision Library

As Mike mentioned: http://www.cs.nyu.edu/biermann/subdivision/

It does rely on some outside resources that I've been having a bit of trouble with, but I thought I'd share the link if anyone wanted to try their luck with it.

February 3,2009 by gleicher (link)
Suggested Readings

Dealing with surfaces is clearly a broad topic...

• Michael Garland's course http://mgarland.org/class/geometry/schedule.html has a good list of topics, with readings for all of them
• For subdivision, the SIGGRAPH course is a good place to start. http://mrl.nyu.edu/publications/subdiv-course2000/ You might also want to look at the two "classic" siggraph papers (both from SIGGRAPH '98) by Stam (Exact Evaluation...) and DeRose et al. (sorry don't have the exact title).
• If you want to learn about mesh data structures, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.4116
• Learning about simplification and smoothing is valuable for anything you will do. RTR3 Chapter 12 is a good start.
  • Quadric Error Metrics are one of the key ideas: paper http://mgarland.org/research/quadrics.html (suggests the vis paper instead of the siggraph paper)
  • Quadric simplification in any dimension http://doi.acm.org/10.1145/1061347.1061350
  • Lubke's survey http://www.cs.virginia.edu/~luebke/publications/pdf/cg+a.2001.pdf
  • Quad simplification http://portal.acm.org/citation.cfm?id=1409101 - this is interesting because it gets at the issues in quad meshes.

I had (mistakenly) suggested that subdivision libraries would be easy to find. TriMesh2 has subdivision, but only for triangles. OpenMesh (openmesh.org) has really nice general mesh data structures, but i'm not sure it has subdivision mixed in. Alex found another, older library as well. You might want to look around for code infrastructure. Adding subdivision support (say catmull-clark) to a general mesh data structure library could be itneresting.

Alternatively, the CGAL library includes a ton of stuff. You might spend the entire semester just learning your way through it. There are SIGGRAPH course notes reader:SIGCourses/CGAL.pdf

Starting with OpenMesh, and adding some of the central mesh operations (subdivision, smoothing/decimation, cutting/drilling) might be a good place to start a project.