Categories
Fade2.5D Examples

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;
	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);
}
Terrain with noise
Terrain with noise
Terrain after weighted Laplacian smoothing
Terrain after weighted Laplacian smoothing

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()
{
	...
	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 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.”

Terrain original
Terrain original
Triangle mesh fitted to valleys and ridges
Triangle mesh fitted to valleys and ridges
Terrain not optimized for valleys and ridges
Terrain not optimized for valleys and ridges
Terrain, edges flipped to better fit valleys and ridges
Terrain, edges flipped to better fit valleys and ridges

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)
			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:

  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;
	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;
}
Triangle mesh with unwanted border triangles
Triangle mesh with bad shaped border triangles
Triangle mesh, bad shaped border triangles removed
Triangle mesh, unwanted border triangles have been removed

Leave a Reply

Your email address will not be published. Required fields are marked *