# TP9 : Subdivision Surfaces on Triangle Meshes

## Code

As always, do

```
git pull
```

or, if you don’t have the local repo,

```
git clone https://github.com/bbrrck/geo-num-2016.git
```

Then

```
cd TP9/
mkdir build
cd build
cmake ..
make
./geonum_TP9 sphere
```

Later, you can specify number of subdivision steps via additional command line parameter.

```
./geonum_TP9 sphere 3
```

`SimpleViewer`

controls are listed below (should be the same on AZERTY keyboard).

```
face toggle : F
edge toggle : E
light on/off : L
smooth/flat : S
zoom : (mouse scroll) or [pageup]/[pagedown]
rotate : (mouse click & drag)
```

**Important:** For those still having problems with `SimpleViewer`

, a code with python binding to OpenGL is provided.
More info on how to configure everything is at the end of the text.

## Subdivision surfaces

Mesh subdivision is a powerful tool, extensively used in modern geometric modeling.
Unlike B-spline subdivision you implemented in TP8, subdivision surfaces are not limited to rectangular topology;
in fact they provide the means for representing surfaces of *arbitrary* topology.

Almost every current animated movie uses subdivision surfaces to some extent.
Even though their mathematical foundations date back to 1978,
Pixar’s short *Geri’s Game* (1997) is considered to be the first ‘real’ application.

Geri’s game, an Academy award-winning short movie by Pixar.

## Loop subdivision scheme

Today, you’ll be implementing the Loop subdivision scheme for triangle meshes. Like every surface subdivision scheme, it consists of two general steps:

- Split the topology; each triangle is replaced by four smaller triangles.
**Compute the new vertex positions from the old positions.**

The first step is already provided in the code; only the second part needs to be implemented.

To compute the new geometry, two sets of vertices are recognized, each with its own rules: new edge midpoints and old vertices. The masks for both groups are visualised below.

Edge and vertex masks for the Loop subdivision scheme.

The $n$ in the vertex mask denotes the number of neighbours. The original definition of $\beta$ was introduced by Charles Loop in his master’s thesis (1987):

\[\beta = \frac1{n} \left( \frac58 - \left( \frac38 + \frac14 \cos{\frac{2\pi}{n}} \right)^2 \right)\]Joe Warren proposed using the simplified weights (1995):

\[\beta = \begin{cases} \frac{3}{8n} & n > 3, \\ \frac{3}{16} & n = 3 . \end{cases}\]## Implementation

To represent a triangle mesh with arbitrary topology, we use two matrices.

- geometry
`V`

—`V.row(i)`

is the position of the vertex`i`

. - topology
`F`

—`F.row(j)`

are the indices of three vertices in triangle`j`

.

### Example: sphere

### Adjacency

The topological step is implemented in the function `triangleSplit( F0,V0, F1,V1, VertexAdjacency, MidpointAdjacency );`

.
After the execution of this function, the last two arguments contain indices necessary to compute the new geometry.

If v, e is the number of vertices and edges in the mesh `V0, F0`

, then

`VertexAdjacency`

is a matrix with v rows, row i contains adjacency information for old vertex i.

column 0: number of adjacent vertices = $n$

columns 1-n: indices of adjacent vertices (weight $\beta$)`MidpointAdjacency`

is a matrix with e rows, row j contains adjacency information for new midpoint vertex j.

columns 0 and 1: indices of adjacent edge vertices (weight $\frac38$)

columns 2 and 3: indices of opposite vertices (weight $\frac18$)

## ToDo

- Implement the computation of new geometry in the Loop subdivision scheme using the original weights $\beta$.
- Use the simplified weights (Warren) and compare the results.
- Subdivide the sphere and cube five times. Which surface is closer to the real sphere? Why?

## Test surfaces

This is the list of all provided test surfaces, with vertex and face counts.

Don’t apply too many iterations on surfaces with more faces, as the number of faces grows exponentially. Take the horse mesh with 1000 faces for instance: we get 4000 faces after one iteration, 16000 after two, and 64000 after three.

In general, three iterations are sufficient. For the sphere and cube, up to five iterations should work. If you get a failed assertion somewhere, it probably means there are too many vertices in the mesh.

#V | #F | |
---|---|---|

cube | 8 | 12 |

sphere | 12 | 20 |

testsurf | 69 | 134 |

bumpycube | 201 | 398 |

cow | 278 | 552 |

armadillo | 434 | 864 |

horse | 502 | 1000 |

## Resources

- Pixar’s OpenSubdiv
- A Quick Introduction to Subdivision Surfaces by Ryan Holmes
- Subdivision by Matthew Fischer
- behind the scenes video showing the use of subdivision surfaces in Brave

## Appendix: PyOpenGL

Here are the instructions on how to configure PyOpenGL and use the python script `viewsurface.py`

based on the code by Matthijs Douze.
Modify the configuration as needed. Be sure to use absolute paths!

```
curl -O https://pypi.python.org/packages/source/P/PyOpenGL/PyOpenGL-3.1.0b3.tar.gz
tar xvzf PyOpenGL-3.1.0b3.tar.gz
cd PyOpenGL-3.1.0b3
mkdir -p /home/tibor/TP-geo-num/TP9/plots/lib/python2.7/site-packages/
export PYTHONPATH=/home/tibor/TP-geo-num/TP9/plots/lib/python2.7/site-packages/
python setup.py install --prefix=/home/tibor/TP-geo-num/TP9/plots
cd /home/tibor/TP-geo-num/TP9/plots
python viewsurface.py sphere
```

This assumes you already have an exported `sphere.off`

in your plots folder.
You can also test using the input data:

```
python viewsurface.py ../data/sphere
```

Don’t forget to use `cmake/CMakeLists2.txt`

and to comment the lines 2, 61-65 in `main.cpp`

.