3d-graphics

Example 3D graphics engine. The design philosophy is heavily based on modern 3D graphics APIs such as DirectX 11 and OpenGL 4. As such, it's overkill for a web app like Snap. Additionally, I have yet to optimize much of anything, so it runs like a room full of people with no legs.

Note: This project does tend to run better in the editor than in the overview page, but I still rarely see anything faster than 2 FPS.

==== Overview ====
Math library makes heavy use of my opaque vector type that is backed by an n-element array. The vertex format is user-defined. In this example, the vertex input format consists of a 3-element vector describing the vertex position, and a 3-element vector describing the surface normal.
The "vertex shader" transforms each vertex, after which the perspective divide and viewport scaling are performed. The "vertex shader" in this example simply transforms the position into screen-space via two rotations, a translation, and then a perspective projection. It also transforms the surface normals, minus the perspective transform and translation. Once this stage completes, the perspective divide scales each component of each vertex by the inverse of its last component, putting the vertices in normalized device coordinates -- each vertex position component should now theoretically be in the range [-1, 1] to be visible. The final step in the vertex stage is to scale the vertices to fit the viewport (the Snap stage).
In order to draw depth-correct geometry, the vertices, now grouped into triangles, are z-sorted from far to near (the algorithm currently in use is a simply sort-by-z-component algorithm, and is not physically correct; artifacts can often be seen when some geometry is at grazing angles to the camera). This ensures that triangles nearer the camera will be drawn over geometry that is farther away. After this step, rasterization can occur. However, because of the triangle rasterization algorithm used, triangles must have their (uniform) color determined before drawing. Thus, at this stage the "fragment shader" is run, which takes as input entire triangles and outputs single colors (this stage could more appropriately be called the triangle "shader"). In the example program, there is a directional light source (a light source theoretically infinitely far away such that all incoming light rays are parallel) and a simple ambient term. The color of each triangle is determined by a simple dot product between the light direction and the surface normal (Lambert reflectance model).
The final step is to actually draw the triangles. This is done using a triangle fast-fill algorithm heavily based on a project found on Scratch user TheLogFather's page (https://scratch.mit.edu/projects/24828481). This algorithm is capable of filling thousands of triangles per second (so the triangle filling is clearly not the engine's bottleneck), and is capable of filling arbitrary triangles.


==== Future Work ====
I'm still working on cleaning up the interface for the shaders -- they're beyond a doubt the most confusing part of the engine -- I get quickly confused with them. The major improvments to be made obviously include performance -- I suspect the triangle sort algorithm is slowing it down, as it involves comparing triangles' centroids in O(n^2) time. This could be improved by quicksort to O(n log n) time. Face culling based on facing direction could possibly improve performance if performed before the sorting step, but reducing triangle count in general will likely see little performance gain for reasons already stated.
Finally, for what it is, this is quite a flexible pipeline, and it allows you to configure every stage. Once again, this is overkill and performance likely could be improved by putting more constraints on it, and given the limitations of per-triangle shading, I'm sure I could find things to take out that nobody will ever complain about. As it is, though, this has been a mostly academic exercise and I've thoroughly enjoyed myself. I plan on making a game out of this at some point (probably something in space since there's so little to draw), and that's probably where I'll start to focus a lot more on performance.

I hope you enjoyed this as much as I did!