Administrative Details

The official due date for your project is Wed 2016-04-27. A proposal for your project must be submitted by 2016-04-20. In particular, the proposal should:

• Be submitted to us (by email) as a web site with a publicly-accessible URL,
• Specify your name (or possibly two names, if you work with a partner)
• Give a brief description of the proposed project and what you hope to achieve—motivating images are extremely valuable here (e.g., "in a perfect world, the output of our algorithm would look like this photograph...")
• Give a list of concrete steps you will take to implement the proposed algorithm.

As just one "toy" example, let's say your goal is to extend the MeshEdit code to implement the most basic version of Catmull-Clark subdivision (which is not enough for a real assignment!). You might write:

1. "We will first modify the viewer to load and display quadrilateral meshes."
2. "We will then implement simple linear subdivision by splitting each polygon at its center."
3. "Finally, we will write a routine that computes new vertex positions according to the actual Catmull-Clark routine."

For a real project, these bullet points should be slightly bigger and higher-level than the ones in the example above. But they should still be split enough into small enough chunks that you have a concrete sense of what to do next. If you're having trouble coming up with a concrete game plan, indicate which steps are giving you trouble and the staff will try to provide some guidance. Overall, a big part of this project will be developing your skill in starting with a high-level conceptual target, and turning it into concrete, actionable items that you can actually achieve. (This kind of ability is one key difference between a good developer and a stellar one!)

Finally, to allow you to implement "cooler stuff," you may work with a partner if you so desire. However, partners must be clearly indicated on your proposal statement and final project submission.

Option B: Cartoon Interpolation

This was the official assignment 4 for the previous semester. See more details here.

Option D: Font Rendering

In your first assignment, you wrote a rasterizer to draw 2D vector graphics. An extremely important example of 2D vector graphics is text! In other words, whenever fonts are getting rendered to the screen, some kind of 2D rasterization is needed. It's easy to dismiss text rendering as a dry, "solved" problem, but in reality typography is a beautiful and challenging subject, with a long and rich history. It also has a clear impact on the daily lives of billions of people. One possible project is to extend your rasterization engine to handle type:

1. Implement rasterization of cubic and quadratic Bézier curves. As we studied in one of the quizzes, these curves are needed to render either TrueType or PostScript fonts (respectively). There are two principal ways to render Bézier curves. One is to use an incremental algorithm, like the "Bresenham" algorithm we studied for lines. A more modern way is to convert explicit Bézier curves into an implicit representation, and evaluate ths implicit function at each sample in a convex region containing the curve; this approach is more amenable to parallel or GPU implementation. Implement both methods
2. Character layout. Given a font and a plain-text string of characters, where and how should each character display on screen? This question is deceptively simple, and has led to generations of ideas in professional typography about kerning, ligatures, and so forth. To begin with, you could implement Donald Knuth's dynamic programming line-breaking algorithm (full justification) and all the fancy special cases for font ligatures. Character width will need to be extracted from the font definition (see below).
3. Implement a loader for TrueType/PostScript fonts, or link against an existing one! Obviously loading fonts is a critical part of actually rendering them, but perhaps your time is better spent on the rasterization algorithms themselves. (No reason to reinvent the wheel.)
4. A completely different direction you could go is to move past traditional font definitions, and develop/design your own. For instance, what if you want animated fonts? Or fonts that encode the random variations found in handwriting? Can you come up with a nice representation for these "richer" fonts? Should you still use Bézier curves? Or, given that you already know that implicit representations lead to efficient algorithms for curve rasterization (as mentioned above), why not design a font format based on implicit representations from the ground up? How can you respect history while still moving forward? Can you add richness to font descriptions without abandoning important and hard-earned knowledge about things like kerning and ligatures? Just because there's an existing standard doesn't mean you have to adhere to it forever—your job as a thinking, breathing individual is to go out into the world and innovate.

Option F: Advanced Rendering and Simulation

Finally, you could extend the physically-based renderer you started to develop for your third assignment—as you experienced first-hand, the basic path tracing algorithm does not converge very quickly! It also doesn't capture some important (and beautiful!) physical phenomena. Here are several specific suggestions for directions you might pursue:

• Improve performance of BVH construction. For large and/or dynamic scenes, the cost of building a bounding volume hierarchy is specific. Consider, for instance, running a large, mesh-based physical simulation of water, which you then want to ray trace in order to get beautiful caustics. Lots of geometry changing in unpredictable ways—and millions of rays to properly resolve the appearance of the surface. You could improve the performance of your renderer by implementing one of the the top modern parallel BVH build algorithms such as

  • Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees
  • Fast Parallel Construction of High-Quality Bounding Volume Hierarchies
  • tThinking Parallel, Part III: Tree Construction on the GPU

  Note: If you choose this topic, you can work based on your assignment 3's code.

  Task Decomposition:

  1. Implemented the Morton code based BVH construction method (which runs on CPU) described in Thinking Parallel, Part III: Tree Construction on the GPU

  2. Implement the parallel binary radix tree(BRT) construction algorithm as proposed in Karras, Tero. Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees for general BRT construction

  3. implemented the parallel algorithm for BVH construction based on BRT construction algorithm, which augments it by adding a bottom-up parallel bounding box construction phase as described in the previous paper.

• SPH Fluid Simulation. Fluid simulation and rendering enhances the immersive experience of interactive applications like video games and movies. Among many approaches, Smoothed Particle Hydrodynamics(SPH) is arguably the easiest one to implement. In this task, you will need to simulate the fluids particles using SPH model, then reconstruct triangle meshes from the discrete particles using Marching Cubes algorithm. If you want, you can render the scene using some graphics APIs like OpenGL and DirectX. Then you will be surprised by how beautiful the result is. References include:

  • Smoothed Particle Hydrodynamics
    • Particle-based fluid simulation for interactive applications
    • Fluid Simulation for Video Games (part 1)
    • Fluid Simulation for Video Games (part 2)
  • Marching Cube Algorithm
    • Marching Cubes: A high resolution 3D surface construction algorithm
  • OpenGL Tutorial

  Note: If you choose this topic, we expect you to write everything from scratch. (chanllenging but a lot of fun).

  Tasks Decomposition:

  1. Implment SPH model to update particle positions/velocities. (At this stage, you can visualize the result by plotting the particles in matlab.)

  2. Implement Marching Cube algorithm to reconstruct triangle mehes

  3. Rendering the fluid using OpenGL/DirectX

Option G: Iterated Function Systems (IFS)

You may extend your p1 rasterization program to render fractal images based on Iterated Function Systems. The main idea is that you start with a point and then repeatedly rasterize the point and then apply a distribution of affine transformations to it. This is a wonderful opportunity to create beauty from mathematics. Here are some concrete steps and features you could implement:

1. Sierpinski triangle: As a warmup you should render a simple IFS such as the Sierpinski Triangle. You will need to modify the p1 code to drive the rendering via procedures instead of an SVG file..
2. Barnsley Fern You can then make simple renderings of Barnsley Ferns
3. Extend the SVG for representing IFS based files. You would then need to extend other relevant functions such as the file parser.
4. Irradiance Caching If you were to simply plot each of the points, then you would end up with an image looking like a set of dots and would be limited in detail to the rasterization size of a point. Most images you will see on the internet never get past naive plotting. To combat this we can instead create a buffer and instead of plotting points as an opaque color, we plot their relative energies interpolated around the 4 pixels they are plotted upon. You can then compute colors for each pixel based on the irradiance cache's energy divided by the largest energy value. In other words we are mapping all energy values from 'black' to 'white'. You may need to think through you aesthetic sensibilities when deciding upon a background color and the colors on each end of the spectrum.
5. Distance Function Now the question is how do we render the background in a way that is aestetically based on the IFS? One solution is to color every background pixel colors based on how far away they are from the set of points defined by the IFS. In other words the shortest distance form the background point to any point that was rasterized inside of the set. This problem is closely related to voronoi diagrams. Here is one efficient way to go about doing this:
   • Create a buffer with one value for every pixel describing how far the given location is from the IFS set. Lets call this the distance buffer.
   • Initialize those locations with non zero energy values in the irradiance cache to have values of 0 in the distance buffer.
   • Creatively propagate distance buffer values using an algorithm similar to flood fill and breadth first search. Every distance buffer location should propagate a pointer to the member of the set they are closest to into their neighboring locations that either have not been initialized yet or have distances larger than the value they would be updated to. You will need to think about which neighbors it will be most efficient to propagate values to, because you want to minimize the amount of times a given value is updated.
   • Color background pixels using the data in the distance buffer. This a great opportunity to experiment with color gradients and interpolation between colors. This is somewhat related to tone mapping.
   • Talk to Bryce and ask him questions about this option.
6. Fractal Flame Algorithm Implement the Fractal Flame Algorithm
7. Design your own IFS! If you are tired of the same old triangles and ferns, you could and should design and formalize your own IFS. Come up with an idea for a shape, derive some affine transformations for it, implement it, render it, stylize it, make something amazing. Be sure to include the mathematics you came up with in your creative process.

Option I: kPhone 869 (15-869 Assignment)

You could implement a simple image processing pipeline for the data produced by the image sensor of the much-anticipated kPhone 869s. (The 's' is for the student version of the phone. It is identical to the 869p, except the gradebook app has been removed, and a voice-assistant app, accessed by speaking 'Ok Yong', has been added.) The 869s has a camera, and your job is to process the data coming off the kPhone 869s's sensor to produce the highest quality image you can. In addition to implementing basic image processing of sensor outputs, you are also be responsible for controlling the focus of the camera!

This is an assignment from Kayvon's Visual Computing Systems class 15-869 from fall of 2014. Here is a link to the details.