Geometry Processing – Introduction

To get started: Clone (do not fork publicly) this repository

git clone --recursive http://github.com/alecjacobson/geometry-processing-introduction.git

Welcome to Geometry Processing! The purpose of this assignment will be to get you up and running with the two C++ libraries we will be using: Eigen for dense and sparse linear algebra routines and libigl for geometry processing routines. We will make use of the OpenGL-based viewer used by the libigl tutorial. This viewer also depends on glfw, a library for managing windows on Linux, Mac OS X and windows.

Prerequisite installation

On all platforms, we will assume you have installed cmake and a modern c++ compiler on Mac OS X¹, Linux², or Windows³.

We also assume that you have cloned this repository using the --recursive flag (if not then issue git submodule update --init --recursive).

Layout

All assignments will have a similar directory and file layout:

README.md
CMakeLists.txt
main.cpp
include/
  function1.h
  function2.h
  ...
src/
  function1.cpp
  function2.cpp
  ...
shared/
  libigl/
    include/
      igl/
        ...
  ...

The README.md file will describe the background, contents and tasks of the assignment.

The CMakeLists.txt file setups up the cmake build routine for this assignment.

The main.cpp file will include the headers in the include/ directory and link to the functions compiled in the src/ directory. This file contains the main function that is executed when the program is run from the command line.

The include/ directory contains one file for each function that you will implement as part of the assignment. Do not change these files.

The src/ directory contains empty implementations of the functions specified in the include/ directory. This is where you will implement the parts of the assignment.

The shared/ directory will contain shared resources: cmake files, dependences (e.g., libigl) and data. Feel free to poke around in here, but you shouldn't change any of these files.

Compilation

This and all following assignments will follow a typical cmake/make build routine. Starting in this directory, issue:

mkdir build
cd build
cmake ..
make 

Why don't you try this right now?

Execution

Once built, you can execute the assignment from inside the build/ using

./introduction

After compiling according to the instructions above, if you try executing right now, then you'll see a bunny:

You can click and drag to change the view.

Optionally, this program can input a path to a triangle mesh file (other than the bunny):

./introduction [path to input file]

Background

Every assignment, including this one, will start with a Background section. This will review the math and algorithms behind the task in the assignment. Students following the lectures should already be familiar with this material and may opt to skip this section.

Let's get familiar with the explicit mesh representation of a discrete surface immersed in $\mathbb{R}^3$. Throughout the course, we will store the set of mesh vertices $V$⁴ and the set of triangles (a.k.a. faces) $F$ as two matrices: V and F.

The matrix V is $|V|$ by 3 in size, where the ith row of this matrix contains the x-, y- and z-coordinates of the ith vertex of the mesh.

The matrix F is $|F|$ by 3 in size, where the jth row of this matrix contains the indices into the rows of V of the first, second and third corners of the jth triangle as a non-negative number (remember in C++ arrays and matrices start with index 0).

The information in V alone is purely positional and encodes the geometry of the surface.

The information in F alone is purely combinatoric and encodes the topology of the surface.

By convention, the indices in each row of F are ordered counter-clockwise around the triangle. Using the right-hand rule, we can define the normal of each triangle as the vector that points most away from the surface.

Each oriented triangle also defines three directed edges between its three vertices. Other triangles in the mesh may contain edges with the same incident vertices, possibly in the opposite direction. A manifold mesh will have at most two triangles incident on the same (undirected) edge, therefor we'll refer to each triangle's directed edge as a half-edge.

The number of vertices $|V|$ and number of faces $|F|$ and number of unique (undirected) edges $|E|$ are intimately related. Adding a new triangle to a mesh may mean increasing the number of vertices and edges, too. The algebraic relationship between the number of vertices, edges and faces reveals the topological genus of the surface via the Euler Characteristic

$$ χ = 2c - 2h - b, $$

where $c$ is the number of connected components, $h$ is number of holes (as in donut), and $b$ is the number of connected components of the boundary of the surface.

For meshes representing polyhedral surfaces, the Euler Characteristic can be computed very simply:

Chi = |V| - |E| + |F|.

Assuming no unreferenced vertices in V, each of the quantities in the right-hand side can be determined from F alone. This indicates that its a purely topological property. Changing the geometric positions (i.e., changing the vertex positions in V) will not affect the Euler Characteristic. Due to this, we say that the Euler Characteristic is a topological invariant.

Tasks

Every assignment, including this one, will contain a Tasks section. This will enumerate all of the tasks a student will need to complete for this assignment. These tasks will match the header/implementation pairs in the include//src/ directories.

Groundrules

Libigl has implemented many of the tasks you'll find in this course. As a result, for some assignments, including this one, you'll see a Groundrules section that lists which functions you can and should use from libigl and/or functions you may not use (and should avoid copying your answers from).

Blacklist libigl functions

For this assignment you may not use

• igl::all_edges
• igl::edge_flaps
• igl::edge_topology
• igl::edges
• igl::euler_characteristic
• igl::exterior_edges
• igl::is_boundary_edge
• igl::unique_edge_map
• or any other libigl function that returns a list of edges.

src/edges.cpp

From a list of triangles F, construct a $|E|$ by 2 matrix E, where the kth row of this matrix contains the indices into the rows of V of the start and end point of the kth edge in the mesh. E should contain every undirected edge exactly once.

src/euler_characteristic.cpp

From the list of triangles F, return the Euler Characteristic X of the triangle mesh. You may and should use your edges function from the previous task.

Submission

Submit your src/ files on MarkUs

Questions?

Direct your questions to the Issues page of this repository.

Answers?

Help your fellow students by answering questions or positions helpful tips on the Issues page of this repository.

¹ Mac Users

You will need to install Xcode if you haven't already.

² Linux Users

Many linux distributions do not include gcc and the basic development tools in their default installation. On Ubuntu, you need to install the following packages:

sudo apt-get install git
sudo apt-get install build-essential
sudo apt-get install cmake
sudo apt-get install libx11-dev
sudo apt-get install mesa-common-dev libgl1-mesa-dev libglu1-mesa-dev
sudo apt-get install libxrandr-dev
sudo apt-get install libxi-dev
sudo apt-get install libxmu-dev
sudo apt-get install libblas-dev

³ Windows Users

libigl only supports the Microsoft Visual Studio 2015 compiler in 64bit mode. It will not work with a 32bit build and it will not work with older versions of visual studio.

⁴ LaTeX

This markdown document, and those for all other assignments, contains $\LaTeX$ math. GitHub just shows the un-evaluated LaTeX code, but other markdown browsers will show the typeset math. You can also generate README.html using multimarkdown:

cat shared/markdown/header.md README.md | multimarkdown --process-html -o README.html