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.


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, 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.