About: A sidequest is an optional, not graded, not evaluated in anyway exploration into a topic. Sometimes it is just cool to know what is out there in the world. Sidequests come with a little descritions, presentations, related resources, and a sample code or exercise you can try. Side quests are likely a good area for further independent studies, research project, thesis, etc.

Vertex Cache Optimization

(Note a background in Computer Graphics will be beneficial for this sidequest)

Overview

We have learned that adding layers of abstraction can help us in performance. A cache in hardware is a way to store frequently executed instructions in a piece of memory that is faster than transferring instructions from a hard drive.

Cache's however are found not just on our CPU, but on our GPU as well (remember, caches are everywhere--even your web browser!).

Problem Statement

Nearly all the computer graphics you see on your screen(whether in a game or in a movie) are made up of triangles (3 edges and 3 vertices). In order to draw these triangles, the vertices (which consist of an x,y, and z coordinate) are passed from your CPU onto your GPU. As you can imagine, there are many thousands or millions of of these vertices. Depending on what final shape you want to draw, your GPU indexes particular vertices from a separte indicies list (which also may be very long).

So in total we have two data structures: one list of vertices and one list of indicies. Ideally vertices that are used often together should be placed nearby. This means that the order of vertices and indicies matters--which makes this an optimization problem. Tom Forsyth's article [1] describes the problem more in detail.

Proposed Exercise

Build an alogorithm that loads in a set of vertices and indicies. It should first have the ability to select 3 indices to draw a triangle (consider this an object). You should then extend it further to select larger geometry that would represent an object. You may look at [2] as an example of how actual 3D data is loaded in the .obj file format.

Proposed Evaluation

Step 1 is implementing Forsyth's original algorithm. Forsyth's article proposes a score for each vertex and the likelihood that it will be drawn next. If we know this information, we can improve the ordering of our vertices. The proposed evaluation for this experiment would be to develop an algorithm that does better (or even worse) than this score and understand why.

Key Resources

(The first resource you should read)

Additional Resources