# Assignment 02

## V-R Complexes

Due: Oct. 15, 2017 11:59:59 PM

Graded: Oct. 22, 2017

Percentage of Grade: 11%

Assignment Description: **Finalized**

- Datasets
- Part 1: Code Structure
- Part 2: Required Code Functionality
- Part 3: Experimentation
- Submission and Grading

In this assignment, we’re going to design a TTK filter and plugin to compute Vietoris-Rips (V-R) complexes. Given a scalar radius, , and a -dimensional point set, , we can define the V-R complex to be the set of all subsets of such that their diameter is less than or equal .

V-R complexes provide approximations to the Čech complex, and both provide a view of the topology of a union of balls of radius centered at the points in . As we’ll find, writing the code to extract the V-R complex is quite simple, and requires a minimal number of distance calculations. On the other hand, V-R complexes tend to include a variety of excess elements, and as grows, they can become quite large.

## Datasets

For this assignment, we will use a variety of point sets. Our filter will be defined such that it can extract a set of points from any other standard type of vtk object (e.g. `*.vtu`

, `*.vtp`

, etc.). You’re welcome to test your code using the set of shapes from Assignment 1, and in addition some new datasets.

## Part 1: Code Structure

Using the `createTTKmodule.sh`

, create a new project called `VietorisRipsComplex`

. This will create the usual files in `baseCode`

, `vtkWrappers`

, `paraview`

, and `standalone`

. You will need to eventually edit all of these.

I recommend that your vtkWrapper uses a single input port of type `vtkPointSet`

and a single output port of type `vtkUnstructuredGrid`

. The V-R complex does include overlapping elements, but `vtkUnstructuredGrid`

will let you insert these even though they are not a valid triangulation. You won’t need to use a scalar field, so as we did in Assignment 01, you can comment this portion out. You will want to add a single Double argument (called `Radius`

) that we will allow a user to control.

Your V-R complex code will only need to compute the valid edges, triangles, and tetrahedra in the complex (`vtkUnstructuredGrid`

cannot easily store higher dimensional elements). You should also add 3 Boolean arguments to specify options as to which sets of elements (1-, 2-, and/or 3-cells) you will output.

For the inputs, I recommend that you look at `ttkGeometrySmoother`

and `ttkSphereFromPoints`

(and their associated baseCode elements) for examples on how a `vtkPointSet`

is manipulated. In particular, you will move from `vtkPointSet`

, to `vtkPoints`

, to eventually access the raw data of each point. For the outputs, you should also look at `ttkIntegralLines`

(and its associated baseCode elements). `ttkIntegralLines`

also produces a `vtkUnstructuredGrid`

, that stores a sequence of poly lines.

At the lower level, I recommend that your baseCode class uses an input that is a `void *`

, but will eventually be cast into an array of `datatype *`

. This is most similar to how the raw data stored in a `vtkPointSet`

will be accessed. To keep things simple, it should output a `vector<vector<int> >`

, which will be a list of cells (each cell being a single `vector<int>`

of indices to the `vtkPointSet`

. Your `ttkVietorisRipsComplex`

will have a function to convert from the `vector<vector<int> >`

to the `vtkUnstructuredGrid`

it will create.

## Part 2: Required Code Functionality

Your `execute()`

function in your `baseCode`

class should take parameters for the radius as well as flags that indicate which cells of which dimension will be returned.

To compute the V-R complex, you should check the distance between every pair of points and include any edge within the distance tolerance based on the radius. Next, you can use these checks to decide whether each triangle and tetrahedra is included (if all edges are included). You should not have to compute distances for anything other than the pairs/edges. For computing distances between points, there is a helper function in `Geometry.h`

(specifically `Geometry::distance()`

). To use this, you’ll have to include the appropriate header as well as editing `baseCode/vietorisRipsComplex.cmake`

to include `ttk_add_baseCode_package(geometry)`

.

This function should also produce an output message that reports the number of vertices that were passed as input, and the number of 1-, 2-, and 3-cells that will be produced.

You will have to modify your `VietorisRipsComplex.xml`

file to allow for all four parameters to be used. Note that you need to use a `DoubleVectorProperty`

for the `Radius`

instead of an `IntVectorProperty`

, otherwise your slider won’t be able to produce decimal values.

You’ll also need to modify the two `main.cpp`

files in both `cmd`

and `gui`

to accept the new parameters.

## Part 3: Experimentation

Using the datasets provided, let’s try to analyze some of the components of shape for various datasets. We will also compare to the Alpha complex, which can be computed using the `Delaunay 3D`

module available in ParaView. This module also allows you to set a radius and to enable/disable various elements of various dimensions of the Alpha complex.

Starting first with `annulus_small.vtp`

in data02, experiment with the Vietoris-Rips complex. I’ve included an inputs set of triangles so that you can compare with the V-R complex. Try to find an radius value such that the 2-cells of the V-R complex “reconstructs” the annulus (start out by setting this small first!). What value did you find? How does the shape of this change if you increase the radius beyond that? Why?

Next, take the Delaunay3D plugin and compare the V-R complex to the Alpha complex for various interesting values for radius. Which complex has more cells? Visually, can you see any differences? If so, explain what the cause(s) it.

Next, experiment with `sphere.vtp`

dataset. This is only a point cloud, so you may not be able to see anything when you load it in ParaView (you might need to switch to ‘Spherical Gaussian’ as a view type or use glyphs). Try to find the best possible radius value that creates a spherical shell with no boundary (again, start with small values and gradually increase them). Once you’ve found a value, use the information panel to report the number of 2-cells at that value. Considering the Euler characteristic and genus for a sphere, can you explain these numbers?

Finally, consider the `torus.vtp`

from data01. Starting with small values and gradually increasing, can you report anything about the distances between points on the inside of the through hole compared with on the outside? What values allow you to possible reconstruct the torus?

You may also want to experiment with other datasets I’ve provided, in particular `shape2.vtp`

and `annulus.vtp`

. Note that as the size of the point cloud increases, the size of the V-R complex can increase rapidly. In your report, discuss any optimizations you might use to speed up this computation. If you know the radius a priori, can you avoid having to check the distances between all possible pairs of vertices?

## Submission and Grading

Submit this entire release folder as a subdirectory to your git repository on bitbucket.

Your grade for this assignment will be based on the following:

- 60% Correct implementation of the filter, ParaView plugin, and command line programs.
- 40% Completing the report.

This percentage will be scaled to the total value of this assignment for your final grade (11%). Extra credit may be assigned for going beyond the specifications of the assignment. One possible direction you might consider is modifying your filter to also compute the Čech complex.