Categories

# Valleys and Ridges, Smoothing, Mesh-Improvements

In this example, we will flip edges in an unnatural looking triangulation to better match its valleys and ridges. Further we will use Fade’s Weighted Laplacian smoothing technique to improve the quality of a noisy triangle mesh. And finally we address an annoying problem, namely large edges at the boundary of a triangulation and we remove them according to user-defined rules.

You can find the C++ source code of this example in the download in “examples_25D/b_meshImprovement.cpp

## Mesh Smoothing

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

```// 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;
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);
}
```
• Step1 generates input points using `getInputPoints()` as described in the previous example. Then it adds some noise.
• Step2 triangulates the point cloud
• The third step visualizes the noisy terrain triangulation
• Finally, Step4 applies smoothing and then it visualizes again.

The smoothing method keeps the convex hull and constraint-segments constant. Further 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. Thus valleys, river courses and mountain ridges of a pure Delaunay triangulation may look unnatural. For this reason Fade provides an optimization algorithm that keeps the measurement points constant but flips the triangle edges to optimize the visual appearance.

```// 1: ValleyRidge
void valleyRidge()
{
...
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()` where three different optimization modes can be chosen:

• OPTMODE_NORMAL is the fastest mode but
• 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 convex in the xy plane. Therefore, triangulated point clouds of concave areas have additional triangles at the border. Such triangles often have long edges and extreme interior angles and they may be almost vertical. The rules, according to which border triangles should be kept or not depend on your application. Thus the `Zone2::peelOffIf()` method takes a user-specified predicate, after whose decision it removes border triangles or not. The following listing suggests such a predicate:

Note: Since Fade v1.87 the base class for the below predicate is no longer `UserPredicateT` but `PeelPredicateTS`. For backwards compatibility the old version is also kept valid.”

```// 2: Custom Predicate derived from PeelPredicateTS
class PeelDecider:public PeelPredicateTS // (new since Fade v1.87)
{
public:
bool operator()(const Triangle2* pT,std::set<Triangle2*>* pCurrentSet)
{
// 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)
}
for (int i = 0; i < 3; ++i)
{
// Is the opposite edge of i a border edge of the zone?
Triangle2* pNeigT(pT->getOppositeTriangle(i));
if( pNeigT==NULL ||
pCurrentSet->find(pNeigT)==pCurrentSet->end() )
{
// Yes, border
if (pT->getInteriorAngle25D(i) > 140)
{
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:

```// 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;
dt.insert(&cloudPrep,true);

// * 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,true,&decider);
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;
}
```
1. Make a triangulation and simplify it as in the previous example. But this time we deliberately do not protect the points of the convex hull from simplification. As a result the triangulation contains bad border triangles see the image below. This is just what we need for this test.
2. Create a global zone `pGlobalZone` consisting of all triangles (also the bad ones)
3. Call `peelOffIf()` with the global zone and the above functor as arguments. The result zone `pResult` excludes the bad border triangles and looks reasonable.