Project 3: Simplification
due: 04/19/2022 objectives
getting started
As with the previous projects, copy the project template stored in |
part 1: implement a mesh simplification algorithm (17 points)
Please implement the mesh simplification algorithm described in the notes for Lecture 13. Recall that there are two important pieces to this algorithm: (1) calculating the vertex, edge and face data and (2) implementing the collapse (contraction) operator. We practiced with the first ingredient in class (see Lecture 13, slides) so please revisit the exercises we did. Many of the functions we wrote in class can be directly used in your project.
implementing the collapse operator
The second ingredient consists of implementing the collapse (a.k.a. contraction) operator, which collapses an edge (a HalfEdge
), thereby removing one vertex of the edge, and relocating the other to the optimal location (stored in vbar
of the edge).
Implementing this requires attentive bookkeeping when updating the half-edge entities affected by the collapse.
Here is a summary of what to implement:
- Given an edge you want to collapse (with the highest priority), retrieve any relevant half-edge entity pointers around this edge (vertices, edges, faces).
- Perform check #1 described in the notes. In other words, extract the one-rings of the two endpoint vertices
p
andq
, and reject the collapse if the number of common vertices in the one-ring is not equal to 2. - Pick one of
p
orq
as the receiving vertex (which remains in the mesh after the collapse), and the other as the deleted vertex. - Re-assign the coordinates of the receiving vertex to those stored in
vbar
of the edge. - Update all the pointers of the half-edge entities affected by the collapse. This part has a lot of potential for bugs, so you should draw a sketch to visualize how the entities are updated. You will submit this sketch in your final report.
- Recompute
vbar
,Qbar
andcost
of any edge affected by the collapse (remember to assign the collapsed edgeQbar
to theQ
of the receiving vertex). - Update the priority queue by removing edges in the one-ring of the receiving vertex (including twins) and re-inserting them. We need to do this because the
cost
of these edges changes during a collapse.
When a collapse is performed, some half-edge entities are removed.
In particular, one HalfVertex
is removed, six HalfEdge
's are removed and two HalfFace
's are removed.
Each of these can be removed from the HalfEdgeMesh
container using the remove
function.
For example, to remove the entity associated with a HalfVertex*
called p
, you can use halfmesh.remove(p)
.
For further information, please see the three remove
functions in the documentation.
ordering the edges to collapse
Finally, you should maintain a priority queue of edges to collapse, such that we remove edges with the lowest cost first (lowest impact of collapsing the edge on the underlying geometry).
You can use a std::multiset<HalfEdge*,CompareCost>
, as described in the notes.
Some definitions are provided in the project template (in simplifier.h
) to help with this, notably the CompareCost
structure, as well as the definition of the CollapsePriorityQueue
via a std::multiset
.
Therefore, you can create a CollapsePriorityQueue
to keep track of which edges to collapse (in order).
Useful functions will be insert
(add a new edge with a cost into the queue), erase
(remove an edge) and begin
(an iterator to the edge at with the highest priority).
When a collapse is rejected (e.g. for topological reasons), you should still remove it from the priority queue.
For more information, see the C++
documentation for a std::multiset
: https://www.cplusplus.com/reference/set/multiset/.
Note that this is just a recommendation - you are free to use a different method to keep track of the order in which you want to collapse edges.
But you should still prioritize collapsing edges with a lower cost first.
As we practiced with in class, be careful when updating your priority queue and the HalfEdgeMesh
container - you should first remove edges that you no longer need from the priority queue, and then the HalfEdgeMesh
.
visualizing the simplified mesh
After your mesh has been simplified to some target number of faces (triangles) nf_target
, you can call halfmesh.extract(mesh)
where mesh
is the connectivity-based mesh structure that will be filled with the simplified mesh.
You can then pass this mesh to a Viewer
to visualize your simplified mesh.
testing your implementation
I highly recommend starting by testing your implementation with a Sphere
mesh as defined in the initial project template.
You should then test your algorithm with a mesh of your choosing as described in Part 3 below.
We are assuming that our meshes are closed (no boundary), so you should use the HalfEdgeMesh::nb_boundary()
function to ensure that there are 0 edges on the boundary for your initial mesh.
development tip
Don't try to get everything working at the same time.
I would suggest starting with a mesh (maybe a Sphere
with $N = 10$), pick some arbitrary HalfEdge
to collapse and write a function to collapse it.
You can visualize the result and verify that the edge was collapsed.
There might still be some bugs with updating the half-edge entities, but it's a good start.
Then try collapsing a handful of edges.
If that works, proceed to collapsing many more (e.g. hundreds).
If everything still seems to work, proceed to setting up a priority queue of edges.
There might still be some bugs to sort out, since this priority queue needs to be updated whenever a collapse is performed.
part 2: implement an additional check on the validity of a contraction (1 point)
In the notes, a second check is proposed to determine the validity of a collapse. In particular, we can check if the normals of the affected faces in the one-rings of the edge endpoint vertices flip directions as compared to the original normals (before the collapse). It will be hard to see a difference in the final meshes, so just print out the total number of edge contractions which are rejected by this check (print it out to the terminal at the end of the simplification).
part 3: report (2 points)
In the README.md
file, please include the following:
- Include a sketch that your group created to visualize all the half-edge entities affected by the collapse operator. It's okay if this is hand-drawn - you can take a picture of your work (a whiteboard, or your notebook). If you take a picture from your phone, try to make sure the image size isn't too large (phones sometimes create images that are several MB). Since you are committing this image to your repository, it would be best to keep the image small (while keeping a reasonable resolution). There are several online tools for reducing image size, e.g. https://www.imagereduce.com/.
- Include pictures of your simplified sphere mesh for a target number of triangles of $1000$, $100$ and $10$. The initial sphere mesh should be generated with $N = 100$ (which contains 19800 triangles).
- Include pictures of simplified meshes where the initial mesh is a mesh of your choosing. Make sure this initial mesh is closed (no boundary, like a sphere). Some sample meshes are posted here, if you'd like to use those. Perform the simplification to three target numbers of triangles of your choosing, e.g. $1000$, $500$ and $100$.
make project3
your code should simplify the mesh (of your choosing) and provide the ability to render the initial and simplified meshes.
submission
After completing the code and your README
, please push to your GitLab
repository.
Then copy a link to your project commit to this Canvas assignment.
All group members should submit this link in Canvas.