24小时客服

#### 关于我们

51Due提供Essay，Paper，Report，Assignment等学科作业的代写与辅导，同时涵盖Personal Statement，转学申请等留学文书代写。

51Due将让你达成学业目标
51Due将让你达成学业目标
51Due将让你达成学业目标
51Due将让你达成学业目标

# Assignment代写：Priority Queues for Mesh Simplification

2018-04-13 来源: 51due教员组 类别: 更多范文

In this assignment we will work with a 2D mesh or graph of vertices, edges, and triangles. At the vertices we store colors loaded from an image in .ppm format. The goal in this assignment is to reduce the total size of the mesh, but still provide a reasonable approximation of the original image. The images below show meshes with approximately 80,000 triangles, 10,000 triangles, and 1,000 triangles (from left to right), displayed with and without the edges between the triangles drawn with white lines. Be sure to read the entire handout before beginning the assignment.

To perform this simplification, we will use a standard mesh processing operation, the edge collapse, which is illustrated below. First, we identify an edge in the mesh that should be removed (drawn in blue). Next, we locate the two triangles on either side of that edge (drawn in light blue), and remove these triangles from the mesh. Finally, we locate all triangles using exactly one of the two endpoints of the edge and change that endpoint coordinate to the midpoint of the collapsed edge. Note: We reuse one of the endpoints of the collapsed edge, while the other is deleted. After the edge collapse is finished, the mesh has 1 fewer vertex, 2 fewer triangles, and 3 fewer edges (the blue edge and 2 green edges are removed). Note that if the edge to be collapsed is on the boundary of the image/mesh, the collapse will result in a mesh with 1 fewer vertex, 1 fewer triangle, and 2 fewer edges.

We provide a significant amount of code for this assignment. Be sure to review all of the provided code before starting your implementation. Search for the word “ASSIGNMENT” within these files to see the sections you need to fill in. The provided code should compile and run on your machine with no edits. The program has reasonable default values for all parameters, but you can override the defaults by providing any or all of these command line arguments (in any order):

-image

-dimensions

-target

-shortest

-random

-color

-preserve_area

-debug

-linear

-priority_queue

The image file must be a .ppm

The size of the grid for the original mesh

The target number of triangles after simplification

Choose the shortest edge to collapse

Choose a random edge to collapse

Choose an edge collapse with least impact on the overall appearance Disallow edge collapses that affect the total area of the mesh

Save intermediate meshes & perform extra error checking

Perform linear sweep over all edges to find the best edge collapse Use a priority queue to find the best edge collapse

As the parameters above indicate, we have some choices when selecting the next edge to collapse. Always choosing the shortest edge (which is our default) is known to be a very good algorithm for producing high quality meshes. The resulting triangles in the final mesh are roughly all the same area and many are approximately equilateral in shape.

Your first task is to complete the implementation of the edge collapse. The provided code (which should be rewritten/replaced) simply deletes the two triangles and leaves a hole. This should work “ok” for at least a few collapses, but if you enable debugging and the extra error checking the program will eventually crash with an error. Make sure your completed implementation of the edge collapse works robustly, and can aggressively simplify a large mesh down to a small number of triangles. The Mesh::Check function (and later the PriorityQueue::check_heap function) are used to sanity check the state of your data as you implement and debug. Use a memory debugger and make sure you have no errors or memory leaks.

Once collapse is working, you can also experiment with the -preserve area command line option. Certain edges should not be collapsed because they change the shape of the boundary of the mesh (as shown below left and middle), and decrease the overall area. The image below right visualizes these illegal edges in red. Note that most of these edges are along the boundary of the mesh, but sometimes they appear in the interior. Sometimes an edge collapse will cause triangles in the neighborhood to twist or flip upside down and overlap other triangles. These situations can be detected by calculating the total area before & after the proposed collapse or checking the clockwise/counter-clockwise orientation of the vertices. We provide finished code to detect illegal edge collapses.

51due留学教育原创版权郑重声明：原创assignment代写范文源自编辑创作，未经官方许可，网站谢绝转载。对于侵权行为，未经同意的情况下，51Due有权追究法律责任。主要业务有assignment代写、essay代写、paper代写、cs代写服务。

51due为留学生提供最好的assignment代写服务，亲们可以进入主页了解和获取更多assignment代写范文 提供作业代写服务，详情可以咨询我们的客服QQ：800020041。