Assignement One HalfEdge Data Structure
Instructor: David Gu TA: Xinyue Huang Due Date: 11:59pm May 26th, 2019
Computer Science Department, Stony Brook University
1 Assignment Objectives
This assignment is designed to make students get familiar with the half-edge data structure, which is the fundamental data structure for geometric programming. In details:
– Reads geometric surface from a mesh file and build the halfedge data struc- ture in the memory
– Trace the boundary, compute the number of boundaries
– Compute the face normal on each face
– Compute the vertex normal on each vertex
– Compute the Euler number of the surface
– Compute the Gaussian curvature for each vertex
– Compute the total Gaussian curvature, verify Gauss-Bonnet formula
2 Expected Results
The solution binary and data meshes can be downloaded from blackboard. The command for running the solution is as follows:
Assignement solution.exe -Gauss Curvature mesh.m
where mesh.m can be one of eight.m, kitten.m, maxplanck.m, segment.m.
name
Vertices
Faces
Edges
Euler
Genus
Boundary
Total K
2kids
4998
10004
15006
-4
3
0
−8π
Alex
80598
160058
240655
1
0
1
2π
genus2
2057
4118
6177
-2
2
0
−4π
kitten
10000
20000
30000
0
1
0
0π
Max-Planck
23609
47082
70690
1
0
1
2π
Segment
2427
4819
7249
-3
1
3
−6π
2 Assignment Three
eight kitten max planck
3 Algorithms
3.1 Trace Boundaries
The algorithm finds all the boundary loops. The class CBoundary⟨M⟩ and CLoop⟨M⟩ implement the algorithm.
CBoundary⟨M⟩ constructor Go through all the edges on the mesh using M::MeshEdgeIterator.
For each edge e, verify whether it is a boundary edge by m_pMesh->isBoundary(e).
For each boundary edge e, take the halfedge attached to it using m_pMesh->edgeHafedge( e,0 ).
Store all the boundary halfedges in a
std::list
While the list is non-empty, take out the first boundary halfedge h in the list, trace along this boundary halfedge h to generate a loop object
CLoop
Delete all the boundary halfedges in the loop from the list.
CLoop⟨M⟩ constructor Given a boundary halfedge h0, trace the whole boundary loop. Get the target vertex of the current halfedge by
M::CVertex * v = m_pMesh->halfEdgeTarget( M::CHalfEdge * )
Get the most clockwise out halfedge of the vertex,
M::CHalfEdge * h = m_pMesh->vertexMostClwOutHalfEdge( M::CVertex * ).
Repeat this process until the current halfedge is the head halfedge h0.
Lecture Notes in Computer Science: Authors’ Instructions 3
3.2 Calculate face normal
Suppose v0,v1,v2 are three vertices of a face f, sorted counter-clock-wisely, the normal to the face can be computed as follows:
d=(v1 →point()−v0 →point)×(v2 →point()−v0 →point) Then the area of the face sf = 1/2d.norm(), the normal of f
nf= d d.norm()
The algorithm is implemented in
void CGaussCurvature
Go through all the faces of the mesh using the face iterator
M::MeshFaceIterator( M * ),
for each face f, go through all its vertices, using the iterator M::FaceVertexIterator
access the vertex point pV → point(), store the vertex point in an std::vector
The face normal is computed using cross product
d = (pts[1] − pts[0]) × (pts[2] − pts[0])
The face area f → area() is half of the norm of d. The face normal f → normal() is the unit vector along d.
3.3 Calculate vertex normal
Suppose vi is the vertex, vi,vj,vk form a face, denoted as fjk, with normal njk ii
and area sjk, then the normal ni at vertex vi is computed as i
then
njk×sjk jki i
di= sjk jk i
ni= di
di .norm()
The algorithm is implemented in
void CGaussCurvature
Go through all the vertices using vertex iterator
M::MeshVertexIterator.
For each vertex, go through all faces attaching to it, using vertex face iterator
M::VertexFaceIterator
4 Assignment Three
3.4 Euler Number
The Euler number of a mesh M equals to the number of vertices plus the number of faces, minus the number of edges:
χ(M)=V +F−E.
The number of handles is called genus, denoted as g. From topological theory: χ(M ) = 2 − 2g − b
where b is the number of boundaries.
The algorithm in implemented in the function
void CGaussCurvature
The vertex, edge and face number are given by
m_pMesh->numVertices(), m_pMesh->numEdges(), m_pMesh->numFaces(),
respectively. The number of boundary loops is given by
M::CBoundary.loops().size().
3.5 Vertex Gaussian Curvature
The algorithm in implemented in the function
void CGaussCurvature
calculate edge length Given an edge [vj,vk] the edge lengths are defined as ljk = (vj → point() − vk → point()).norm(),
Go through all edges using
M::MeshEdgeIterator
for each edge, access its two vertices by
m_pMesh->edgeVertex1(e), m_pMesh->edgeVertex2(e).
store the edge length in e → length().
calculate corner angle Given a triangle [vi,vj,vk], the edge lengths of [vj,vk],
[vk,vi] and [vi,vj] are li,lj,lk respectively. The corner angle at vertex vi is
θ i = a r c c o s l j2 + l k2 − l i2 2lj lk
Go through all faces using
M::MeshFaceIterator.
For an face, access all halfedges using
M::FaceHalfEdgeIterator.
The corner angle is stored in
M::CHalfEdge.angle().
Lecture Notes in Computer Science: Authors’ Instructions 5
calculate vertex curvature Then if vi is on the boundary, its curvature is defined as jk
Ki=π− θi, jk
where θjk is the corner angle at vi in face vi,vj,vk. i
If vi is an interior vertex, its curvature is
Ki =2π−θjk.
Go through all vertices of the mesh using
M::MeshVertexIterator
Go through all the entering halfedges attaching to a vertex using
M::VertexInHalfedgeIterator
verify Gauss-Bonnet Formula The total Gaussian curvature is related to the Euler number Ki = 2πχ(M ).
4 Coding Environment
The solution code is compiled on windows platform using Visual Studio. You can compile, debug the assignment in the same environment. The student computer lab has windows machines with Visual Studio IDE.
The procedure for testing the solution binary is as follows:
1. Download GaussCurvature.zip and unzip the package
2. There is a subfolder demo, enter demo
3. Select any subfolder under demo, double click on the batch file GaussCur-
vature test.bat.
4. In the command window, you will see
..\..\bin\GaussCurvature.exe -Gauss_Curvature alex.m Vertices: 80598 Faces: 160058 Edges: 240655
Euler Characteristic Number 1
Number of boundaries 1
Genus 0
Total Curvature is 2 PI
Then an OpenGL window will popup, show the mesh model.
i jk
6 Assignment Three
5 Submission Requirements
You need to submit the followings: source code with project file or makefile; The data meshes are unnecessary to be submitted; Detailed Readme file,
– Name, ID, email address
– Explain how to use your solution code
– Source codes
– Project files
– Explain your algorithm for each requirement.
Your source code will be examined in details, compiled, and executed in the grading process. If you have further questions, please contact the instruc- tor David Gu, gu@cs.stonybrook.edu, or the TA Xinyue Huang. If you need extension, please email to the instructor as well.