In this example, we will flip edges in an unnatural looking triangulation to better match its **valleys and ridges**. Further we’ll use Fade’s **Weighted Laplacian smoothing** technique to improve the quality of a noisy triangle mesh. And finally we address an annoying problem, namely bad shaped triangles at the boundary of a triangulation. We remove these triangles according to predefined- or user-specified rules.

## Mesh Smoothing

**Sub-Example 0** demonstrates how weighted Laplacian smoothing is applied to a noisy mesh.

- Generate input points using
`getInputPoints()`

from the previous example and add some noise. - Triangulate
- Visualize the noisy terrain triangulation
- Apply smoothing with 2 iterations, then visualize again

// 0: Smoothing void smoothing() { // * 1 * Get input points and add some noise std::vector<Point2> vInputPoints; getInputPoints("MOUNTAIN",vInputPoints); for(size_t i=0;i<vInputPoints.size();++i) { Point2& p(vInputPoints[i]); p.setHeight(p.z()-.1+(.2*rand())/RAND_MAX);// Noise } // * 2 * Triangulate CloudPrepare cloudPrep; cloudPrep.add(vInputPoints); Fade_2D dt; dt.insert(&cloudPrep,true); // * 3 * Show the noisy terrain write(4,"terrain_noisy",dt); // * 4 * Smoothing and show Zone2* pGlobalZone(dt.createZone(NULL,ZL_GLOBAL)); pGlobalZone->smoothing(2); write(4,"terrain_smooth",dt); }

The smoothing method keeps the convex hull and constraint-segments (‘breaklines’) constant. Nevertheless it guarantees that the triangles keep their orientation i.e., no 180 degree flips happen.

## Edge flips to adapt the triangle mesh to Valleys and Ridges

The topology in a 2.5D Delaunay triangulation depends only on the `(x,y)`

-coordinates of the points and thus valleys, river courses and mountain ridges of a pure Delaunay triangulation may look unnatural. Fade contains 3 optimization algorithms that keep the measurement points constant but flip the triangle edges in such a way that the appearance is optimized.

// 1: ValleyRidge void valleyRidge() { ... Fade_2D dt; dt.insert(&cloudPrep,true); // * 4 * Flip edges to optimize valleys/ridges/rivers Zone2* pGlobalZone(dt.createZone(NULL,ZL_GLOBAL)); GASSEX(pGlobalZone!=NULL); pGlobalZone->slopeValleyRidgeOptimization(OPTMODE_BETTER); write(5,"flow",dt); }

The above code snippet triangulates points as in the previous code snippet. Then it defines `pGlobalZone`

consisting of all triangles and calls `slopeValleyRidgeOptimization()`

. Thereby three different optimization modes exist:

- OPTMODE_NORMAL is the fastest mode.
- OPTMODE_BETTER provides significantly better results while still taking only a moderate amount of time.
- OPTMODE_BEST achieves the best results, but also has a significantly higher time requirement.

“Flipping edges degrades the interior angles of the triangles to a certain degree. This is the unavoidable price of the optimization in favor of the valleys and ridges. For this reason, it may make sense not to push Valley-Ridge optimization to the limit and stick with OPTMODE_BETTER.”

## Removing unwanted Border Triangles

A Delaunay triangulation is always convex in the xy plane. Therefore, triangulated point clouds can easily have triangles at the border, which actually do not belong to the triangulation. Such triangles often have large edges or they are almost 90 degrees upwards. The rules, according to which border triangles should still be accepted or not depend on the user’s application. Thus the border-removal-algorithm takes a user-specified predicate, after whose decision the border triangles are removed or not. A suggestion how to write such a predicate can be seen in the following listing:

// 2: Custom Predicate derived from UserPredicateT class PeelDecider:public UserPredicateT { public: bool operator()(const Triangle2* pT) { // Angle between face normal and (0,0,1) Vector2 nv(pT->getNormalVector()); Vector2 up(0,0,1); double angle(-1); double cosPhi(nv*up); if(cosPhi>1.0) angle=0; // Robustness in case of numeric inaccuracy else if(cosPhi<-1.0) angle=180.0; // Robustness in case of numeric inaccuracy else angle=acos(cosPhi)*57.2958; if(angle>85.0) { // >85 degrees between face normal and v(0,0,1) return true; // Bad triangle } for(int i=0;i<3;++i) { if(pT->getInteriorAngle25D(i)>150) return true; } return false; } };

The above functor returns true if a border triangle `pT`

is to be deleted. For the decision it uses the angle between `pT`

‘s normal vector and the vector `(0,0,1)`

as well as the largest interior angle of `pT`

. You can use this functor or adapt its rules to your needs. For example, the maximum edge length would also be a good criterion in case that the point sampling is uniform. Now we still need the piece of code that uses and tests this functor. This happens in the following listing:

- A triangulation is made and simplified as in the previous example. But this time we deliberately do not protect the points of the convex hull from simplification and therefore the triangulation contains bad border triangles. Just what we need for this test.
- Create a global zone
`pGlobalZone`

consisting of all triangles (also the bad ones) - Call
`peelOffIf()`

with the global zone and the above functor as arguments. The result zone`pResult`

excludes the bad border triangles and looks reasonable.

// 2: Remove border triangles void removeBorderTriangles() { // * 1 * Get input points and simplify them without maintaining // the convex hull because this is very likely to create // bad border triangles - a setting that we want for this // demo: std::vector<Point2> vInputPoints; getInputPoints("MOUNTAIN",vInputPoints); CloudPrepare cloudPrep; cloudPrep.add(vInputPoints); cloudPrep.adaptiveSimplify(1.0,SMS_MEDIAN,CHS_NOHULL); cout<<"CloudPrepare adaptiveSimplify, numPoints reduced="<<cloudPrep.getNumPoints()<<endl; Fade_2D dt; dt.insert(&cloudPrep,true); dt.showGeomview("a6_badBorder.list",Visualizer3::CWHEAT); dt.writeObj("a6_badBorder.obj"); // * 2 * Create a global zone and a user precidate Zone2* pGlobalZone(dt.createZone(NULL,ZL_GLOBAL)); cout<<"Original, number of triangles: "<<pGlobalZone->getNumberOfTriangles()<<endl; // * 3 * Peel unwanted border triangles off cout<<"Getting rid of unwanted border triangles"<<endl; PeelDecider decider; Zone2* pResult=peelOffIf(pGlobalZone,&decider,false); if(pResult==NULL) { cout<<"NO RESULT ZONE"<<endl; return; } pResult->showGeomview("a6_goodBorder.list",Visualizer3::CORANGE); pResult->writeObj("a6_goodBorder.obj"); cout<<"Cleaned, number of triangles: "<<pResult->getNumberOfTriangles()<<endl; }