” 辅导AMS 562、 写作C++ STL、 辅导C/C++程序AMS 562 Final ProjectSpherical TriangularMeshesDue Dec. 20, 2018 5.00 pm1 IntroductionMesh is an important concept in computational science; it is used in manydifferent applications, for instance, most PDE based engineering problems. Amesh is a tessellation of a domain with simple geometry objectsreferred aselements or cells.In general, mesh can be grouped into the following two families:1. structured grids, and2. unstructured meshes.The first one is topologically equivalent to unit square (in 2D) with uniformlydistributed (in some weighted sense) Grid lines along x and y directions. Therefore,each of the grid points can be accessed with a pair of indices, i.e. x-/y- index,see below.Structured grids are hard to extended to general domains that are needed intypical engineering problems. This is particularly true for structural mechanics,whereas the structural components can be very complicated.1AMS 562 Final ProjectSpherical Triangular Meshes 2 Data StructureWith this consideration, people have come up with the unstructured meshes,which can easily represent complex geometries; see the picture below for a surfacemesh on a dragon shape object.For unstructured meshes, one of the popular choices of element types for surfacedomain tessellation is triangles, because they are simple and robust (tessellatinga surface with triangles is much easier than with other cells, e.g. quadrilateralcells).However, with unstructured grids, its impossible to access the grid points withx-, y-, (z-) index. Therefore, special data structures are needed (later).For this project, we will only deal with unstructured triangularmeshes on spherical surfaces.2 Data Structure2.1 Core Concept for Storing Points and TrianglesFor unstructured meshes, one cannot store, like in structured grids, xyz coordinatesseparately. Typically, a n by 3 storage is utilized, where each entry ofthe array stands for a physical point in the Cartesian coordinate system. Forinstance, you can store five Arbitrary points in the following matrix format.x0 y0 z0x1 y1 z1x2 y2 z2x3 y3 z3x4 y4 z4In order to represent the mesh, we use a connectivity table that forms theconnection relation between triangles and coordinates IDs. A connectivity table2AMS 562 Final ProjectSpherical Triangular Meshes 2 Data Structure(for triangles) is an m by 3 integer storage, where m is the number of triangles,and the three integer IDs are the node IDs in the coordinates that form thetriangle.2.2 An ExampleLets consider a unit square plane, We then can split the plane into two trianglesalong one of the diagonal (say, [0 0] and [1 1]). Therefore, we have 4 points and2 triangles and the mesh can be represented by (assume xy plane)points =0.0 0.01.0 0.01.0 1.00.0 1.0triangles =0 1 22 3 0In this example, we have 4 points with the coordinates listed in points, then inthe connectivity table, i.e. triangles, the first triangle contains nodes 0, 1 and2, while 2, 3 and 1 for the second one.Hint draw this with pencil and paper.2.3 Store The Mesh with C++ STLFor both coordinates and connectivity table, we will use the std::vector asthe container, and for each single point and triangle, we will use std::array.Therefore, the overall data structures are:// spherical coordinatesclass SphCo {public:…private:std::vectorstd::arraydouble, 3 _pts;};// connectivityclass Triangles {public:…private:std::vectorstd::arrayint, 3 _conn;};3AMS 562 Final ProjectSpherical Triangular Meshes 3 Your TasksWith this implementation, we know that when you loop through the coordinatesand connectivity table, the entries are of types std::arraydouble, 3 andstd::arrayint, 3, resp.2.4 Remark Regarding Triangle Node OrderingFor the spherical mesh, you can assume that the node ordering of trianglesfollowing the right-hand rule results vectors that always point to outward normaldirections with respect to the Spherical triangular faces.3 Your TasksFor this project, you do NOT need to implement any of the data structureslisted above. They are already implemented and ready to use. What you needto do is to implement several algorithms in order to perform the following tasks.3.1 Determine Node to Triangle AdjacencyEssentially, a connectivity table defines the adjacency information betweentriangles and nodes, i.e. a row of the table is the adjacent nodes of that triangle.Starting from this, we can build its dual graph, i.e. node to cell adjacency, sothat, given a node, we can find all triangles contain it.Unlike the connectivity table, for unstructured meshes, the node to cell adjacencyinformation, in general, cannot be stored in a matrix-like storage, we, then, canuse// vector of vector// where the inner vector is the list of element IDs that// are shared by a specific nodestd::vectorstd::vectorint n2e_adj;In order to build the adjacency information, you need to implement the followingalgorithm.Algorithm I: Determine the node to cell adjInputs: Connectivity table conn and number of points npOutput: Node to triangle adjacency mapping, adjInitialize adj with size npfor each triangle Tiin conn, dofor each node vj in Ti, do4AMS 562 Final ProjectSpherical Triangular Meshes 3 Your Taskspush back triangle ID i to list adjjend forend for3.2 Compute the Averaged Outward Normal VectorsGiven a triangle, we can compute its normal vector by using the cross product,i.e. for a triangle ?ABC, the normal vector n~ is computed byn~ = AB~ AC~where denotes cross product.Since we already know that the triangle is oriented in the way that the right-handrule gives the outward normal, directly using the formula above will give youthe correct answer.We want first compute and store all outward normals of triangles, then use theadjacent mapping to average them on nodes.Algorithm II.1 : Compute the outward normals of spherical trianglesInputs: Connectivity table conn and coordinates coOutput: Outward normals of triangles, f_nrmsInitialize f_nrms with size ne = conn.size()for each triangle Tiin conn, doGet coordinates A, B, C = co(Ti,0), co(Ti,1), co(Ti,2)Assign f_nrmsi with the outward normal vectorend forNormalize f_nrms so that each of the vector has Euclidean length 1In order to easily normalized the vectors, you should consider use SphCo to storef_nrms.Algorithm II.2 : Compute the averaged normal on nodesInputs: Node to cell mapping adj, np, and f_nrmsOutput: Outward normals of nodes, n_nrmsInitialize n_nrms with size npfor each node vj , doGet the local adjacency information adjjAssign n_nrmsj to be the average of f_nrms(adjj )end forNormalize n_nrms so that each of the vector has Euclidean length 15AMS 562 Final ProjectSpherical Triangular Meshes 4 Requirements3.3 Determine the Computation ErrorsFor points located on the spherical surface, their outward normal directions areuniquely defined. In this case, we want to see how much error we have introducedfrom our computation. The metric we use is~a ~b = k~akk~bk cos()where is the angle between ~a and ~b. We, then, have = cos?1~a ~bk~akk~bk!Since we know that both ~a and ~b are normalized, we can simplify the computationby = cos?1~a ~bAlgorithm III: Compute the angle errorsInputs: Analytic normals (coordinates) exact and numerical normalsnumOutput: Error angles arccos_thetaInitialize arccos_theta with size exact.size()for each node vj , doAssign arccos_thetaj with the error angle given exactj and numjnormal vectorsend for4 RequirementsYou need to implement the algorithms list above in manip.cpp file and makesure you pass all tests. There are three test cases, which are list below.6AMS 562 Final ProjectSpherical Triangular Meshes 5 HintsNote that there are 4 for loops, you must implement at least two of them withstd::for_each with lambda or traditional functors.You will gain extra credits by using std::for_each for all iteration loops.5 HintsThere are some sample usages of std::for_each and lambda in co.hpp andconn.hpp. Also, type make debug to use Valgrind during development. Pleaselook at the comments in manip.hpp carefully.If you get error values of nan, then it means you probably have some bug inadj array (you have at least a node with no adjacent triangles). If you get errorvalues of ~ 180 degree, then it means you mess up with the node ordering sothat the right-hand rule gives you inner normal directions.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
