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’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.

1. Generate input points using `getInputPoints()` from the previous example and add some noise.
2. Triangulate
3. Visualize the noisy terrain triangulation
4. 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;
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. That is, 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. Therefore Fade contains 3 optimization algorithms that keep the measurement points constant but flip the triangle edges to optimize the 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 which 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 vertical. 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 it removes the border triangles or not. The following listing suggests such a predicate:

```// 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)
}
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:

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 consequence the triangulation contains bad border triangles. 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.
```// 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,&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;
}
```