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;
	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);
}

• 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()
{
	...
	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() 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)
            return true; // Bad triangle
        }
        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;
	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,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.