Setup

Clone the repo:

$ git clone --recurse-submodules

If you forget to --recurse-submodules:

$ git submodule update --init --recursive

Make a build directory, then run cmake .. from inside.

Debugging in Ubuntu

To build debug, run in build:

$ cmake -DCMAKE_BUILD_TYPE=Debug ..

A launch.json is provided for debugging using VS Code and GDB.

Mesh patch generation

Algorithm

Meshes textured with Ptex are entirely made up of quads, with a square of texels per face. The goal is to prevent texture distortion by only having squares in texture coordinate space.

A couple observations:

• each vertex in a patch can only associate with 4 faces
  • this is a simplified way of saying all faces must be able to lay square
• quads within a patch can't overlap each other

Ptex2Uv naively unwraps the mesh by performing the following steps:

1. select some face A
2. starting from face A, expand the UV patch "north" until any of the following occur:
   • the next quad in the traversal direction neighbors a quad already in this patch when going in the traversal direction
   • there are no more quads in the expanding direction
   • some predetermined distance has been reached
3. from face A, repeat step 2 going "south"
4. from face A, go "east" or "west" depending on which way is permissible based on the above rules to select face B
5. if face B exists, repeat steps 2-4 with face B
6. otherwise, the patch is complete. Start over at step 2

This kind of peels the mesh apart like a banana. Yay!

Datastructures

For the core algorithm to work, we build a traversable quad-graph, with quads linking "north, south, east, and west." We store the graph as structs in an array, ordered by the face order:

Quad Struct:
* indices of neighbors
* marker index for what patch this belongs to

Building the quad-graph requires building a dictionary of edges to quads. The edge dictionary allows us to identify neighbors for each quad, and is built in a single pass over all the quad faces. Keys for the edge dictionary are generated by Cantor pairing function:

key = ((i0 + i1) * (i0 + i1 + 1) / 2) + i1

Note that each edge can only be associated with at most two quads. So we can optimize:

• edge should map only to the index of the first quad for which the edge was encountered
• once an edge has been inserted into the dictionary and then looked up, it can be removed from the dictionary to save space.

Side note: with the second optimization, by the end of the process we conveniently have a map full of edges that are parts of edge loops in the original mesh. Cantor pairing is also reversible! But this isn't important to our algorithm, since the goal is to introduce a bunch of additional edge loops anyway.

Future work

• use a custom hash map for the edge map instead of std::unordered_map for better performance

UV generation

Given mesh patches that will lie flat without overlapping themselves, we can pack these into UV space using the technique here: http://the-witness.net/news/2010/03/graphics-tech-texture-parameterization/

• sort patches by area
• "rasterize" into a bit-grid starting from the top left
• double size of the bit grid as needed

Datastructures

A bit grid that allows fast copying into the top left of another bit grid.