Assignment 0 (Coding): Combinatorial Surfaces — due 2/8

For the coding portion of your first assignment, you will implement some operations on simplicial complexes which were discussed in class and in Chapter 2 of the course notes. Once implemented, you will be able to select simplices and apply these operations to them by clicking the appropriate buttons in the viewer (shown above).

Getting Started

  • Please download or clone the files in this repository. It contains a fast and flexible framework for 3D geometry processing implemented in Javascript. Over the course of the semester, you will implement all of your coding assignments here.
  • For this assignment, you will need to implement the following routines in projects/simplicial-complex-operators/simplicial-complex-operators.js:
    • assignElementIndices
    • buildVertexEdgeAdjacencymatrix
    • buildEdgeFaceAdjacencymatrix
    • buildVertexVector
    • buildEdgeVector
    • buildFaceVector
    • star
    • closure
    • link
    • isComplex
    • isPureComplex
    • boundary

Notes

  • This assignment comes with a viewer projects/simplicial-complex-operators/index.html which lets you apply your operators to simplices of meshes and visualize the results.
  • Pay close attention to the course notes! Some routines really must be implemented with sparse matrices, not directly with the halfedge mesh data structure.
  • Selecting simplices will not work until you fill in the assignElementIndices function.
  • The assignment also comes with a test script tests/simplicial-complex-operators/text.html which you can use to verify the correctness of your operators.
  • The code framework is implemented in Javascript, which means no compilation or installation is necessary on any platform. You can simply get started by opening the index.html file in projects/discrete-exterior-calculus/ in a web browser. We recommend using Chrome or Firefox. Safari has poor WebGL performance.
  • If you do not have prior experience with Javascript, do not worry! You should be able to get a handle on Javascript syntax by reading through some of the code in the framework (a good place to start might be core/geometry.js). The framework also contains extensive documentation (see docs/index.html).
  • All browsers come with tools for debugging (for instance the JavaScript Console in Chrome).

Submission Instructions

Important: Please rename your simplicial-complex-operators.js file to simplicial-complex-operators.txt, so that your email does not get filtered out by the email server.

The assignment is due on February 8, 2020 at 5:59:59pm Eastern (not at midnight!). Remember to turn in the whole assignment via a single email including both the written exercises (as a PDF file) and the code (in a ZIP file). Further hand-in instructions can be found on this page.

30 thoughts on “Assignment 0 (Coding): Combinatorial Surfaces — due 2/8”

  1. I believe the half-edges on the boundary of the given disk should contain face:-1 instead of face 0. Currently the code probably defaults the halfedge.face.index to 0, but it results in wrong closure of face 0 (a triangle near the top-left of the mesh).

  2. I am having difficulty understanding how the assignElementIndices is supposed to modify the mesh data structure. Where do the assigned indices go in the mesh data structure?

    1. Yes. For the majority of the class we’ll be working in 2 or 3 dimensions because of the nature of the algorithms we’re working with(and because the differential geometry of curves and surfaces is “nicer” in many ways than that of higher dimensions). But for general operations like isComplex, it’s good to make sure you understand how this would generalize.

  3. Firstly, is there any way to get the index of all non-zero entries in a row or column of a sparse matrix data structure?

    Secondly, should assignElementIndices assign indexes to halfedges as well? Should it be identical to Mesh.indexElements?

    1. I don’t know of one that is there by default. The method .nnz() returns the number of nonzero entries in a sparse matrix, but that’s not exactly what you want.
      You don’t need to assign indices to halfedges. You are just assigning indices to the faces, edges, and vertices of the mesh.

  4. Quoting the course notes:

    $\text{For the [methods from }\texttt{star}\text{ onwards], recall that you }\textit{must}\text{ use}\\\text{the adjacency matrices [from the previous methods]; you should }\\\textit{not}\text{ be implementing these methods directly using the halfedge}\\\text{data structure.}$

    Double-checking that this applies to this assignment? I have unfortunately already done the latter and am hoping no-one makes the same mistake as me.

    1. Also, for the methods $\texttt{buildVertexEdgeAdjacencyMatrix}$ and $\texttt{buildEdgeFaceAdjacencyMatrix}$, can we directly use the halfedge data structure?

    2. I did the same thing 🙁

      The Coding Exercises section in the course note was not explicitly mentioned. I thought the instruction about sparse matrices was only referring to buildVertexEdgeAdjacencymatrix, etc.

  5. When submitting, should we zip the whole ddg-exercises-js folder or do we just zip the single .js file that we made change to? If we zip the whole folder, then do we need to change all .js extensions to .txt?

  6. I’m a bit confused how to tell whether things are “adjacent” while creating the adjacency matrix from the mesh itself. What does the mesh look like before we add these properties?

    1. We do provide a mesh, but we deindex it in the test cases. This is the reason why you have to write assignElementIndices. It’s good practice to know how to do. Basically, you may call mesh.edges and similar calls to access to access the edges, vertices, and faces to index. However, just indexing the mesh features is not enough because combinatorially, the edges of each associated index may not be together. Thus, you should loop through the edges and check for the vertices adjacent to them to add to you matrix or triplet using either the e.halfedege.vertex or commands similar to v.adjacentEdges which you can find in the code you downloaded.

    1. The Complex matrix classes represent m by n complex matrices. They store nonzero, possibly complex entries. We will see later on in the course why complex numbers matter in geometry processing. But here’s a sneak peak: when we deal with conformal, or angle preserving maps, manipulating data with complex numbers is key because geometrically they offer a way to preserve the angle because the difference between $1$ and $i$ is just a $90\deg$ rotation. Essentially, we will be dealing with complex differential forms! Also, many interesting things involving linear algebra deal with our field being over the complex numbers.

Leave a Reply