CSE 190 Assignment 2

Mesh Viewer

I made a simple parser and viewer for the OFF files. You can spin objects around with the WASD+QE keys, and zoom in with R and F. My program computes vertex normals on load, and on combination of vertices does a cheap average to approximate the new normal.

Although it uses a shader workflow for lighting, it uses vertex colors, where the color is the function of the vertex index, in order to identify the merging of vertices.

Data Structures

For this assignment I took advantage of Boost’s Bimap data structure — not only a bidirectional map, but a bidirectional multimap, which means that I can represent many-to-many relationships (a vertex can belong to many faces, a face can contain many vertices). With this key access is O(log n) as these structures are ordered and are implemented with red-black trees internally. The ordering is good though, as through a custom comparator I can also use the bimap as a sorted tree for O(log n) access to the minimum element (for things like quadric error). With this data structure I created a mapping between vertex indices and face indices (with actual vertex data being stored in a separate array to avoid duplication). This all results in my decimation being relatively quick — for the simpler models like the teapot, you can decimate them in real-time.

Decimation and Quadric Error

I started out with basic randomized pair selection and midpoint clustering. It seemed to work most of the time, but as the example picture above shows (the tried clustering of 11 and 23) it sometimes had the tendency to join to the center of the screen — it seems like some vector object (I used GLM interally for math) wasn’t being passed around correctly and ended up constructing the default Vec3 (0, 0, 0), as through a lot of debugging I couldn’t find the source.

The same goes for quadric analysis in general. Although I’m pretty sure I had the math and systems set up correctly, I had issues with edges and discarded vertices remaining after being collapsed. The propensity of joining at the center regardless of what I told of it also continued.

Videos and Progressive Meshes

Here are some videos of meshes being decimated randomly with midpoint joins, followed by them being “recreated”. Again, with issues of edges not collapsing properly (I had separate mappings between vectors and faces vs vectors and edges so I’m sure there was probably a syncing issue somewhere) so although vertex data is preserved (giving objects a familiar shape on reconstruction), edges aren’t really.

I had this data sent to a file and then read back for reconstruction. Here’s an example line from the file:

148 3.16254 2.25684 0.036914 -0.327855 1.51885 -0.187426 147 3.19062 2.25703 0 -0.35967 1.57317 0.0886586 2 151 152 3 150 201 202

It encodes the vertex indices of both participating vertices, their coords and normals, as well as the face indices that were destroyed (and therefore needing to be fixed on reconstruction).

Download

Here’s a link to a ZIP file containing an executable and the resources it needs to run: https://www.dropbox.com/s/pas8jyyaei1rbw1/MeshDecA10836922.zip?dl=0. It should be configured to run standalone (tell me if it isn’t, I’m sure I can make a standalone version).

The application is programmed to take “torus.off” currently, so if you wish to change the model, rename the model you want to use to “torus.off”.

The controls are WASD+EQ to rotate the camera, R and F to zoom in and out, and C to start the decimation/restoration process.