# 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
• buildVertexVector
• buildEdgeVector
• buildFaceVector
• star
• closure
• 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. Lqq88888 says:

Hello! I am wondering what the grading criterion is? Will complexity be graded? I received some warnings of time cost when running tests.

1. Alex says:

If your code does not time out(with respect to the test cases) then you should be fine. The warnings serve as an indicator for how close you are to timing out.

1. Lqq88888 says:

Thank you! By the way, is office hour time decided?

1. Daniel Li says:

Yes! Check the course description page for all of the office hours times!

2. hawaiii says:

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

3. manugopa says:

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. Alex says:

Each k-dim simplex has a .index parameter which should be assigned uniquely.

4. tpan496 says:

I am using SparseMatrix.identity(m,n), but it seems that this only applies to square matrices?

5. lykospirit says:

Does our implementation only need to consider complexes containing $k$-simplices where $k\le 2$?

1. Alex says:

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.

6. Zhang Zetian says:

Do we assume there is orientation on our simplices when writing build matrix function? (Which should result in -1 entries in the matrix)

7. Liu Qiangdong says:

Can we assume the meshes are triangle meshes?

8. xTheBHox says:

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. Daniel Li says:

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.

9. lykospirit says:

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. lykospirit says:

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

1. Daniel Li says:

You don’t need it for this assignment, but you may for future assignments. If you pass all of the test cases now, you are ok.

2. Daniel Li says:

It does; however, if you have added the halfedges to your matrix, and you pass the test cases, you are ok.

3. OtB_BlueBerry says:

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.

10. Zhang Zetian says:

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?

1. Alex says:

Just zip your solutions file, not the whole exercises folder.

11. fpou says:

What should boundary return if the given subset is not a pure simplicial complex?

12. Ninae says:

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. Daniel Li says:

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.

13. hawner says:

What’s the difference between the Sparse/Dense Matrix classes and the Complex Sparse/Dense Matrix classes?

1. Daniel Li says:

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.