Assignment 04
Morse Complex
Due: Nov. 12, 2017 11:59:59 PM
Graded: Nov. 19, 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’ll develop a TTK filter and plugin to approximate the Morse Complex of a scalar function. You may want to review Section IV.2 of Edelsbrunner and Harer before beginning this assignment. Recall that a stable manifold of a critical point \(u\) is the set of all points whose integral lines end at \(u\). For a given scalar field, the stable manifolds of all critical points decompose the domain into a cell complex called the Morse Complex.
Using our CriticalPoints
filter from the previous assignment, we will approximate the Morse Complex through a labeling of vertices based on which critical point their integral curve arrives at. To approximate integral curves, we will approximate the gradient. Recall that the gradient at a position \(x\) for a scalar field \(f\) is the unique direction in the tangent space of \(x\) where \(f\) increases the most. To compute the stable manifolds, for every vertex in our input dataset, we will follow the gradient uphill until we arrive at a critical point. Instead of computing the gradient as a vector, your MorseComplex
filter will compute, for each vertex \(v\) the neighboring vertex \(w\) whose functional value \(f(w)\) is maximally above \(f(v)\). Thus, we can approximate integral curves by walking vertex-to-vertex until we arrive at a critical vertex. TTK’s triangulation data structure makes such a query straightforward using GetVertexNeighbor()
.
Likewise, your filter should also be able to produce the decomposition based on unstable manifolds, which is found by walking in the direction of steepest descent at every vertex.
Datasets
For this assignment, feel free to experiment with the datasets previously provided: data01, data02, and data03. I have also provided two terrains to examine in data04
Part 1: Code Structure
You will need to modify your CriticalPoints
filter to output an additional field. For every point in the vtkPointSet
you produce, you should have defined two different values: (1) the critical type (an integer in \([0,dimension]\), you already were computing this) and (2) you will also need the original vertex id (also an integer). You may want to look at ttkScalarFieldCriticalPoints to see how to output multiple fields.
Using the createTTKmodule.sh
, create a new project called MorseComplex
. This will create the usual files in baseCode
, vtkWrappers
, paraview
, and standalone
. You will need to eventually edit all of these.
In this assignment, your vtkWrapper will be modified to accept two inputs. Consider looking at ttkTopologicalSimplification for an example of this. The first input should be a vtkDataSet
with a scalar field defined on it. Your second input should be a vtkPointSet
with two fields defined on it (ideally, this should be precisely the output of your CriticalPoints
filter). Because of the interoperability of filters, you should also be able to test with ttkScalarFieldCriticalPoints
.
In addition, your filter should also accept an input that specifies whether you will compute the stable manifold decomposition or the unstable manifold decomposition. You do not have to support computing both, but if you do then your MorseComplex
filter should produce two labelings.
You will also have to modify your paraview/MorseComplex.xml
carefully so that the user can select the appropriate scalar field as well as the fields for the critical type and their vertex ids. Again, the TopologicalSimplification
filter is a decent example of how to do this. You should have 3 string parameters defined for the names of these fields.
At the lower level, your baseCode class should be able to directly pass pointers around for the fields that you will populate. Based on how you choose to implement this, you will either produce one or two arrays that you will store in the point data for the vtkDataSet
that you will output.
Part 2: Required Code Functionality
Our implementation will only use the data values stored on the vertices of the input dataset. Note that ttkIntegralCurves
is more sophisticated than this, and ttkMorseSmaleComplex
employs a different approach. Our simplifying approximation is that every regular vertex will have precisely one uphill direction that it can walk to and that direction is precisely towards another vertex. Thus, the first step for computing the Morse complex is to find the unique vertex that is the uphill direction for every vertex in the input dataset. You can do this by iterating over the neighbors and finding the one with the highest scalar value that is larger than the vertex. Storing these internally as an array of ids will be helpful for the later step. Similarly, your code may also benefit from computing a downhill vertex for each regular vertex.
The above assumes that such a vertex can be uniquely found. As in the last assignment, I am not requiring that you implement this in any particular way, but you will discover that you need to break ties somehow when the function is not Morse. Note that vertices which are critical may now have a unique direction, but this is consistent with the fact that critical points have a gradient of zero.
After computing the “uphill” vertex for each regular vertex, you will walk the integral curve until you arrive at a critical vertex. To do so, you will iteratively step to the uphill vertex, and then the uphill vertices’ uphill vertex, and so on. When you arrive at a critical point, you can then assign a label to the vertex based on which stable manifold you have arrived at (I used the vertex id of the critical point, which is a unique label). Note that you can also apply the same label to all other vertices you traveled through along the integral curve.
You may or may not encounter saddles in this way. I do not require that the Morse complex you compute is a true complex. But, I do recommend that you keep around the information that you find with respect to saddles (at best, it will only be partial). You should, however, get a reasonably good decomposition of the stable manifolds of the maxima.
Part 3: Experimentation
First, examine the dataset sine.vtu
. This is a simplified version of a terrain that we will look at later, that is simply a 2D sinusoidal dataset. You should see that the 2D ascending and descending manifolds regions correspond to particular types of critical points. Which critical points for each? What do the boundaries between regions correspond to?
Next, consider the dataset BuiltInExample1.vti
used in the scalar data example of TTK. This example dataset is a vector field, but you can produce a scalar field for the magnitude of the vector field using the Calculator
filter. Do the ascending/descending manifolds correspond to any feature in this dataset? Run the TTK scalar data example and notice how vorticity is computed using the ComputeDerivatives
and then extracting the z component of the vorticity vector. Compare the ascending/decending manifolds for the vorticity field to the ascending/descending manifolds for the velocity magnitude. Do they extract the same information or are they different? You may also want to compare these to the ascending/descending manifolds that TTK’s MorseSmaleComplex
filter can produce in its segmentation, although note that TTK has flipped ascending and descending.
Now watch the Morse Persistence tutorial on TTK’s website. Using the topological simplification filter, you should be able to work with the noisyTerrain.vtu
dataset. Report the number of ascending/descending manifolds for this dataset after simplifying to a threshold of 0.67 and 3, in particular comparing this to sine.vtu
.
Finally, compute the critical points and ascending/descending manifolds for the foo.vti
dataset from data03. After, use ParaView’s Contour
filter to extract the isosurface associated with the value 1 for the input field Scalars
. This should extract a molecular surface. Color this filter by the descending manifolds associated with the maxima – what do you see?
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 and ParaView plugin.
- 40% Completing the report, being sure to document any implementation details as well as the experimental results.
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.