Task-2: Simplify the mesh using quadratic error metrics Purpose:
The goal of this task is to load a mesh and to simplify the mesh down to a specified number of triangles. You will learn about modern mesh simplification algorithms with a half-edge data structure.
Description:
In this task, we will perform mesh simplification algorithm based on quadric error metric (QEM), you may read the following paper for reference: https://www.cs.cmu.edu/ ̃./garland/Papers/quadrics.pdf
Copyright By PowCoder代写 加微信 powcoder
To perform surface simplification, you should use the half-edge data structure implemented in task1 to achieve a pair-contraction operator for the mesh. This pair- contraction operation should preserve the topology of the surface.
To reduce the difficulty of the implementation, we’ll simplify the algorithm in the original paper introduced as follows:
1. (1) When choosing valid pairs (v1,v2) and perform contraction, we only consider cases where (v1, v2) form an edge. Without loss of generality, we’ll use the term “pair contraction” and “edge collapse” interchangeably.
2. (2) We will not use the point-to-plane distance as discussed in the paper that computes the distance to adjacent planes to act as error metric, because degenerate cases may make the problem more difficult to solve. Instead, we will use distance to adjacent vertices with the derivation below. You should collapse edges in the order dictated by the error function below and place new vertices at the minimizer of this error function:
• Let E(v) = Pni=1(v − vi)2 be the error function associated with each vertex v of the mesh, where {vi, i = 1. . . n} are the neighbours of v. If we expand this quadratic, we find that
E(v) = nvT v − 2vT Pni=1 vi + Pni=1 viT vi, whose minimizer is given by v = Pni=1 vi/n.
• We can further rewrite E(v) as vector dot product form, which is: E(v) = n Pn v Pn i=1 i i=1
viT viT vT v −2v 1. Therefore, all we need to store to represent
this quadratic is the coefficient q = n Pn v Pn v T v , which is a 5-d vector. i=1 i i=1 i i
• The benefit of this representation is that when creating the combined quadratic for the union of two vertices, we simply need to sum the two vectors, each containing 5 numbers, together for the two different vertices.
You should perform edge-collapse operations using the error function above until you achieve the desired number of polygons or there are no more edges that can be collapsed safely. The processing time must be below one minutes. Your report should display the original and simplified surface and also report the number of vertices, faces and edges respectively.
You must disallow edge collapses if they create illegal topology. While you should work independently, it is a good idea to compare your results with other students, to verify code correctness. You should assure in your input OBJ all the polygons are triangles and the input surface is closed.
Steps to take:
Perform mesh simplification in task2.cpp. We already provide the code framework for this function and all you need to do is to complete the missing functions as specified in the code. However, you’re also welcomed to implement the whole pipeline in your own way as long as it successfully achieves the simplification functionality and generate the same results. Complete the following functionalities:
1. (1) Vertex::compute qem coeff() to compute the coefficient vector q that represent the quadratic coefficient of this vertex.
2. (2) Edge::compute contraction() to compute the following results for this edge (v1, v2), which will be used later to perform edge collapse:
• The optimal contraction target v∗; 5
• The quadratic error metrics E(v∗) which is the combined quadratic for the union of v1,v2. Note that the computed results will become the cost of contracting this edge.
(3) Edge::edge contraction() to perform edge-collapse, which we will write as (v1, v2) → v∗. It contains the following steps:
• Moves the vertex v1 to the new position v*, remember to update all corresponding attributes
• Connects all incident edges of v1 and v2 to v*, and remove the vertex v2
• Any faces, half edges, and edges associated with this collapsed edge will be
(4) Your lab report should contain the following contents:
• Use the two OBJ meshes provided in ”model” folder to demonstrate the results.
• Display the original mesh as well as the simplified mesh with MeshLab or
• Take the screenshot of the mesh geometric information as well as the
verification results from the terminal output to demonstrate the correctness of your implementation.
More example mesh surfaces can be found here: happy, teddy
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com