“MeshShop” Project Description
Your project will be to implement some sort of major feature for the mesh processing application the class will be writing. Each persons effort will be roughly equal to implementing the contents of ‘one paper’. If working in teams, you’ll need to implement several (possibly related) features. Examples of possible projects are given below. Feel free to come up with your own ideas.
You might like to browse recent SIGGRAPH conference proceedings to get ideas. You can borrow physical books from me. I also have DVDs for some conferences which you could watch to get ideas for projects. If you prefer to browse the web, check this site for pointers to online papers for some graphics conferences.
Project Proposal
You’ll first need to come up with a project proposal. You should tell me
1) Who is on your team
(Examples in italics) - Joe
Smith and Jane Doe
2) What you plan to accomplish by the end of the project
We plan to implement mesh
hole filling. We are going to implement the volumetric method of paper XX.
Since this requires scan converting a polygonal mesh into a volumetric grid,
and then the actual hole filling, and then turning the results back into a polygonal
mesh, we feel that its more than enough work for two people. In particular
we’ll be using Marching Cubes (cite paper YY) to turn the volume back into a
polygon mesh.
3) Which papers/books/websites you’re using for inspiration
paper XX, paper YY, and website ZZ on rasterizing polygons into volumes
4) What you plan to do by each of the first and second checkpoints
For the first check point
we just want to figure out how to manipulate the mesh in terms of the course
framework. We’re going to get the basic framework in place and do some simple
test like traversing the mesh and removing half of the polygons. Also we’ll get
all our options and interface in place. For the second check we want to
transform our mesh intro a volumetric representation and then back to a mesh
representation. Since the volume grid might be at a different resolution, the
resulting mesh won’t be exactly the same, but it will be similar. It still
won’t have holes filled. We’ll get the actual volumetric hole
filling implemented by the final project demo.
5) What you are planning to implement yourselves, and what libraries you hope to get from somewhere else
We are hoping to get code
from the web to turn polygons into some volumetric representation. We plan to
implement to hole filling method ourselves in this
volumetric space. We plan to get code off the web to turn the volume
representation back into polygons. Although we haven’t settled on exactly which
libraries yet, we were thinking of these two (cite web pages).
6) How you plan to implement this in terms of the project framework
This work is primarily a
mesh filter. Thus we plan to basically implement a filter()
method which modifies a mesh, but no display() method and no keyboard or mouse
interaction. However we do need some options such as “how many iterations”, and
“use space carving yes/no”, etc.., so will specify those in the startup() function
Figuring out what you want to do and formulating a plan will take you some time. All my suggestions below are relatively vague and you may need to do some browsing and reading to decide. I encourage you to work extra hard on planning since this will probably make your life easier later. You can come to my office and chat with me, or grab me after class if you’d like to discuss.
Grading
Grading will be roughly as follows:
F – doesn’t work
D – works sometimes
C – works but with less functionality than we agreed on
B – works exactly like the paper you’re implementing
A – works and innovates beyond the paper (possibly in a very very small way)
Very Short Introduction to the project framework
You’ll be implementing your project inside a framework that we provide to you. The main reason for the framework is so that we can hopefully get everyone’s project to compile together. There will be some very simple code in place which allows you to load a mesh from a file, render it on the screen, and change its orientation. For the purposes of this document we’ll describe in a high level, so that you can see where the following projects might fit into the framework.
The framework will have a basic Mesh datatype which contains the data for the loaded mesh(es). Each project will be a “feature plugin”, and each one of these will implement some subset of the following functions:
Startup() – Initialize any data structures you need, request the interface elements you need, such as sliders and checkboxes
Display() – Draw something on the screen using openGL
Filter() – Called whenever your plugin is selected from a menu, or when one of your sliders or checkboxes is changed. Probably you want to look at the current polygon list and then manipulate it in some way.
Mouse() – Mouse interaction on the screen directed at your plugin
Keyboard() – Keypress in the main window directed at your plugin
Idle() – Background processing you might want to do
You probably won’t use all of these. For example, if you want to make a painterly rendering option, and you don’t want any options, you might only implement a display() function which draws each mesh on the screen. If you want to make a sophisticated manipulator which allows the user to drag the mouse and change the mesh viewing direction, you might implement mouse() and nothing else. Someone who wants to remove noise in the mesh might only implement filter(). However most people will probably implement a few of the callbacks.
All of the core functionality that we provide you will also be implemented as “feature plugins” so you can see examples of what to do. We’ll be providing roughly the following: “Load Mesh From File”, “Very Simple Drawing On Screen”, “Simple Mesh Manipulator”, and “Very Simple Mesh Filter”.
Example Project Ideas
Rendering
You might want to implement a special rendering style. There are lots of rendering methods, which produce images with substantially different characteristics. Here are some examples.
Normal OpenGL (similar to scanalyze)
You could implement a basic OpenGL renderer. This would normally be the default renderer since its going to run fast enough for interaction. Since OpenGL does most of the work for you, you’ll need to add lots of options, such as filled polygons, wireframe, lighting, no lighting, antialiasing, shiny, not shiny, all one color, each mesh a different color. You can install and use ‘scanalyze’ as a reference to get ideas.
http://graphics.stanford.edu/software/scanalyze/
Painterly
These methods try to mimic the style of a painting.
Painterly
Rendering with Curved Brush Strokes of Multiple Sizes
Painterly Rendering for
Animation
Curtis, Anderson, Seims, Fleischer, Salesin Siggraph 1997
Many more can be found here:
Visualization or diagrammatic
Sometimes the goal is to make the rendering more understandable to the viewer, rather than more photo realistic. This is common in technical illustrations that come in manuals for example.
A
Non-Photorealistic Lighting Model For
Automatic Technical Illustration
Amy Gooch - Bruce Gooch - Peter Shirley - Elaine Cohen SIGGRAPH 1998
Pen & Ink
Pen and ink style illustration is another possibility.
Raytraced
Ray tracing is a rendering method which allows multi-bounce shadows, reflections, and refractions to be handled. Its usually been considered as slow, but recently there have been real time implementations. There are whole textbooks on this topic, but I would only expect a simple implementation from you. I’ve listed two of the earliest papers below.
Overview of raytracing on the web
A. Appel
"Some Techniques for Shading Machine Renderings of Solids," American Federation of Information Processing Societies Proceedings of the Spring Joint Computer Conference, 1968, 37-45.
Silhouettes or key edges
Sometimes choosing silhouette boundaries, or certain important curvature boundaries produces the desired effect.
Mesh Processing
Many of you will implement some sort of mesh processing filter. We would like to be able to take the meshes we have and change them in some way. Maybe smooth the mesh, or join two meshes together, or simplify the mesh to have fewer polygons. A link to a class entirely on this topic at UBC with lots of related papers is here:
http://www.cs.ubc.ca/~sheffa/dgp/papers.html
Fairing (noise reduction)
The process of scanning a mesh is often noisy. We’d like to discard the noise but keep the important features on the mesh. That is, we still want the sharp edges that are supposed to be there, just none of the sharp little spikes that are really noise.
Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow
(Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan Barr), Proceedings of SIGGRAPH 99.
http://www.multires.caltech.edu/pubs/ImplicitFairing.pdf
A Simple Algorithm for Surface Denoising
Jianbo Peng, Vasily Strela,
Denis Zorin
Proceedings of IEEE Visualization 2001.
http://mrl.nyu.edu/projects/multires/denoise/
G. Taubin.
A signal processing approach to fair surface design. In Proceedings of SIGGRAPH 1995. [PDF]
Simplification (fewer polygons)
Sometimes the mesh we start with has a billion polygons, and we’d like to be able to deal with it on a poor old machines from 1995 or send it across a low bandwidth network connection. We need a way to reduce the number of polygons in the mesh, while keeping it looking the same.
M. Garland and P. Heckbert. Surface Simplification Using Quadric Error Metrics. In Proceedings of SIGGRAPH 97. [PDF]
M. Garland and E. Shaffer. A Multiphase Approach to Efficient Surface Simplification. In Proceedings of IEEE Visualization 2002, October 2002. [PDF]
Progressive
meshes.
H. Hoppe.
ACM SIGGRAPH 1996, 99-108.
Aligning two meshes
After scanning an object from different angles we get two partial meshes. They won’t necessarily be sharing a coordinate frame. We’d like to find the transformation (translation + rotation) that brings them into alignment. Some algorithms require an initial guess and iterate to an exact solution, and some work completely automatically.
Efficient Variants of the ICP Algorithm
Szymon Rusinkiewicz
Marc Levoy, 3DIM2001
Surface Registration by Matching
Oriented Points
A. Johnson
and M. Hebert
International Conference on Recent Advances in 3-D Digital Imaging and
Modeling, May, 1997, pp. 121-128.
Fully automatic registration of
multiple 3D data sets
D. Huber and M. Hebert
Image and Vision Computing, Vol. 21, No. 7, July, 2003, pp. 637-650.
Merging two meshes (VRIP or zipper)
Usually we scan objects from only one side at a time. Eventually we want to merge all these partial meshes into a single mesh. They usually aren’t quite the same at the boundaries and we need to find a way to put them together without making weird little seems at the edges.
Zippered Polygon Meshes from Range Images
Greg Turk and Marc Levoy, Proc. SIGGRAPH '94 (Orlando, Florida, July 24-29, 1994). In Computer Graphics Proceedings, Annual Conference Series, 1994, ACM SIGGRAPH, pp. 311-318.
A
Volumetric Method for Building Complex Models from Range Images
Brian Curless and Marc Levoy,
Proc. SIGGRAPH '96.
http://ww2.cs.fsu.edu/~hui/research/scanalyze_tutorial/tutorial.html
Filling holes
Scanned meshes often have holes because the scanner couldn’t see anything, or the surface was too shiny, or there was too much dirt. We’d like to automatically find and fill all these holes.
Filling holes in complex surfaces using volumetric diffusion
James Davis, Stephen R. Marschner, Matt Garr, and Marc Levoy
First International Symposium on 3D Data Processing, Visualization, and Transmission
Reconstruction and Representation of 3D Objects with Radial Basis Functions
J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, T. R. Evans
SIGGRAPH 2001, Computer Graphics Proceedings
http://www.farfieldtechnology.com/download/
Reconstruction from a point cloud
Some scanners only give us a cloud of points. We’d like to take this cloud of points and make a mesh out of it. But how do we decide what is connected to what? There are lots of methods. Pick one and try it out.
The Ball-Pivoting Algorithm for Surface Reconstruction
IEEE Transactions on Visualization and Computer Graphics 1999
Fausto Bernardini Joshua Mittleman Holly Rushmeier Cl´ audio Silva Gabriel Taubin
Surface reconstruction from unorganized points.
H. Hoppe, T. DeRose,
T. Duchamp,
J. McDonald, W. Stuetzle.
ACM SIGGRAPH 1992, 71-78.
http://research.microsoft.com/~hoppe/
Interaction
Some of these interactions are pretty easy, so you may need to do a couple together.
Copy/Paste
What would an application be without copy and paste? You’ll need to work out some way to select regions, and have an undo function, etc..
Selecting regions on a mesh
If we want to select a region on a mesh, how should it work? Points within some distance in Euclidean space? Or maybe along the surface of the mesh (surface geodesics)? Or maybe drawing a boundary on the mesh and selecting the inside? Perhaps just drawing a box on the screen and selecting the inside of the box? I don’t know what the user will find easiest to use – maybe you could try several? Or make up your own?
Animation controls
Sometimes we have a whole set of meshes which represent the same object deforming over time. We’d like to have some animation controls that let use play, fast-fwd, pause, etc. Also, it would be nice to save animated movies (images) of the meshes from the current viewpoint, so you’ll need to make play the frames back one at a time and save the current image. Maybe select sub-sections of the movie, letting me trim off a few bad frames at the beginning and end? If you’re interested in animating meshes, I can give you some data, and you can figure out how to make it easy for people to work with it.
Motion capture data
If you’d like to work with motion capture data (the ping pong ball looking things), then I can give you some of that and you can figure out how to make sure we can load it, and look at it, and play an animation from it, etc.. [You can probably pretend that each marker (ping pong ball) is a mesh vertex, and there are no triangles in the mesh, and then just stick it in the same data structure we are using for meshes. However you’ll need to make sure the display() routine works reasonably when there are just vertices, and no polygons.]
Trackball controller
We’re providing a very simple controller that lets you turn the current mesh. However it would be great to have a real trackball style controller that lets you turn the mesh easily. I don’t know what’s best. I did a quick web search and turned up these two papers which actually studied the question by test a bunch of people. Maybe you should implement to best one. =)
A study in interactive 3-D rotation using 2-D control devices http://portal.acm.org/citation.cfm?id=378497
(another paper about evaluating trackballs)
http://research.microsoft.com/users/kenh/papers/UISTrotation-final.pdf
Surface deformations
There are lots of ways to deform a surface, usually by defining some mathematical function and then changing a few parameters of that function. They come under a variety of names, but the basic question is, if you let me pull on the mesh with a mouse at point X, how does the surface deform? We don’t want to move each polygon one at a time, we’d like some high level operator.
Free-form deformation of solid geometric models
http://portal.acm.org/citation.cfm?id=15903
Laplacian Surface Editing
Olga Sorkine Daniel Cohen-Or Yaron Lipman Marc Alexa Christian Rössl Hans-Peter Seidel
http://www.cs.tau.ac.il/~sorkine/ProjectPages/Editing/lse.html
Visualizing
Line plot along a surface
It turns out that being able to visualize the depth of a line drawn across a mesh is very useful. It lets us “see” the quality of the mesh, or the alignment between several meshes in a way that a normal rendering does not. Implement a way for the user to do this. (By the way, the picture above shows that the depth on this test object doesn’t have flat steps, instead it has little peaks on each step. The real object does have flat steps, thus I had a bug in my code. But note that you can’t really tell that from the mesh rendering.)
GUI (overall architecture)
Adding menus, buttons, sliders, etc…
We will be providing a basic framework for people to implement “plugin features”. And we’ll be implementing a very simple “GUI plugin” that uses GLUT and makes some basic menus. However the interface will be very very simple. Someone could develop a better “GUI plugin” that makes the program easier to use. If everything has gone as plan, the rest of the class’ “feature plugins” will work with either our simple GUI, or your new and improved GUI. You’ll be the class hero if you do a good job, since probably everyone will hate whatever simple thing we wrote.
Research topics
The example ideas in this section are related to ongoing research projects I’d like to start. I’m proposing the first small steps as class projects. These differ from all the others in that they are research before all the unknowns are worked out. It would be great if you wanted to continue with an independent study to take the next steps, but its obviously not required.