15-418: Final Project

Subtitle

Project Checkpoint

Revised Schedule

WEEK
 DATES
 WORK
 1
 April 4-11
Initially planned to work on a gradient descent algorithm in Natural Language Processing; decided to switch topic to parallel Catmull-Clark subdivision. Did some initial research and found relevant articles.
 2
 April 11-18
Created a serial version of the Catmull-Clark algorithm that fully works and renders. Familiarized ourselves with the parallel implementation provided in the paper, including a novel portion dealing with the removal of T-junctions and cracks. 
 3
 April 18-25
First half: 
Integrate CUDA into existing code (Arjun)
Add code to help deal with cracks and T-junctions (Sally)
Complete a parallel version of code that operates as described in paper by mid-week. (Sally, Arjun)

Second half:
Match performance to the paper's performance, and try to optimize further (Sally, Arjun)
 4
 April 25-May 2
First half: 
Try to modify code to an alternate representation, like map representations or commonly used mesh data structures like half-edge mesh. (Arjun)
Second half: 
Identify key reasons for better performance with some structures over others, and create graphs representing this. (Sally)
 5
 May 2-May 9
Document code well (Arjun)
Set up our demos (Sally)
Complete final proposal (Arjun)
Prepare Final Presentation (Sally)

Progress Summary

So far, we have made solid progress by fully implementing a serial version of the Catmull-Clark algorithm. The serial version, utilizing some base code from a 15-462 project, not only generates the subdivided image but also renders it so that we can see the results. In addition, we have done careful reading and written up notes on the parallel implementation proposed in the paper, including the new task of implementing view-dependency. At this point we feel fully equipped to begin working out a parallel implementation, which we will work on this weekend.


Goals and Deliverables

We are on track to complete our primary goals of developing a parallel model of Catmull-Clark, as we already have a code base to work with and much of the algorithm written out. Although we will need to make changes to transition into the parallel implementation, such as breaking functions up into kernel calls, we believe this will not be too difficult because the structure of the code is already broken down into several separate steps, in most of which we loop through some entire array (and which we can do in parallel). We will also need to modify some data structures, but we believe this won't be significantly challenging because of our familiarity with the algorithm. In terms of our "Hope to Achieve"s, we very much expect to handle cracks/T-junctions and optimize, but we are not sure yet if we will have time to branch out into other approximating techniques and data structures.


Here is our updated list of goals.

Plan To Achieve:

1) Fully functional parallel model of Catmull-Clarke, with view-dependency and techniques for dealing with cracks and T-junctions.

2) Match performance results of the paper and identify bottlenecks.


Hope To Achieve:

1) Improve performance of the algorithm to achieve real-time speeds on all models.

2) Experiment with different data structures and approximating techniques (besides Catmull-Clark).


Parallelism Competition Demo

We hope to show a demo of our real-time Catmull-Clark-subdivision system, with animated images to demonstrate the effectiveness of the parallelization. We also expect to plot some graphs of our speedup vs. the sequential version of the algorithm.


Some Potential Concerns:

1. We are not completely sure yet how to determine the range of the view in OpenGL in order to address view-dependency and increase performance, although we have some ideas of how to approach it.