Algorithm for mesh simplification unifying co-linear edges

Question

By removing the red-marked vertices (which split an edge into two co-linear edges) from the mesh below, and re-triangulating the affected faces (which are in the same plane), one can produce a simpler mesh representing exactly the same solid.

While algorithms for short-edge collapsing are very common, I have not been able to find anything which realizes this specific simplification. Bonus point if an implementation is available in CGAL or in other opensource libraries.

Answer 1

First, to test if two adjacent edges are co-linear, you need to decide if you can tolerate rounding errors. (Assuming you're familiar with the exact computation paradigm in CGAL.)

Second, co-linear edges might not be a good metric if you want loss-less decimation.
Co-linear edges does not guarantee the corresponding faces are co-planar.
And co-planar faces might not have co-linear edges.

Third, each edge-collapse operation incurs a cost. The most used cost might be quadric error as stated in the paper Surface Simplification Using Quadric Error Metrics. If the cost of an edge-collapse operation is 0, that means the shape of the mesh has not changed, w.r.t this error metric.
By collapsing all edges that have 0 cost, you can get what you want.

Fourth, after collapsing an edge, you might need to determine where to put the new vertex. As for your loss-less decimation, you can just use one of the endpoints of the collapsed edge. (Termed half-edge collapse as in this Stanford slides).

---

CGAL does not provide the implementation of a stop predicate (defines when the algorithm terminates) according to edge-collapse cost. However it's easy to implement one (here I assume exactness is not necessary):

#include <iostream>
#include <fstream>

#include <CGAL/Simple_cartesian.h>
// #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Surface_mesh_simplification/edge_collapse.h>
// #include <CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Count_ratio_stop_predicate.h>


// typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Surface_mesh; 

namespace SMS = CGAL::Surface_mesh_simplification;


// Stops when the cost of an edge-collapse operation exceeds a user-specified value.
template<class TM_>    
class Cost_stop_predicate
{
public:
  typedef TM_ TM ;

public :
  Cost_stop_predicate( double aThres ) : mThres(aThres) {}
  
  template <typename F, typename Profile> 
  bool operator()( F const&          aCurrentCost
                 , Profile const& // aEdgeProfile
                 , std::size_t    // aInitialCount
                 , std::size_t    // aCurrentCount
                 ) const 
  {
    return static_cast<double>(aCurrentCost) > mThres ;
  }
  
private:
  double mThres ;
};    


int main( int argc, char** argv ) 
{
  Surface_mesh surface_mesh; 
  
  std::ifstream is(argv[1]);
  is >> surface_mesh;
  if (!CGAL::is_triangle_mesh(surface_mesh)){
    std::cerr << "Input geometry is not triangulated." << std::endl;
    return EXIT_FAILURE;
  }

  // In this example, the simplification stops when 
  // the cost of an edge collapse execeeds 0.0000001
  std::cout << surface_mesh.number_of_faces() << " faces.\n";
  Cost_stop_predicate<Surface_mesh> stop(1e-10);
 
  int r = SMS::edge_collapse(surface_mesh, stop);

  std::cout << "\nFinished...\n" << r << " edges removed.\n" 
      << surface_mesh.number_of_faces() << " final faces.\n";
 
  std::ofstream os( argc > 2 ? argv[2] : "out.off" );
  os.precision(17);
  os << surface_mesh;
  
  return EXIT_SUCCESS;      
}

The result of using the above code to loss-lessly simplify a mesh of a tetrahedron:
(left: before simplification, right: after simplification)

---

Also note that the error metric implemented in CGAL is not the most usual quadric error metric, but Lindstrom-Turk Cost which has better approximating power as stated in the paper: Fast and memory efficient polygonal simplification.

And the code above does not use half-edge collapse but general edge collapse. That means the new vertex will be placed in a position minimizing the Lindstorm-Turk Cost. For your case, this placement strategy is not necessary. If you want to reduce the extra computation, you can implement half-edge collapse yourself, which is also not complicated. I guess I'll just use the off the shelf implementation :)

And just to let you know, vcglib also provides mesh decimation capabilities, including this all-in-one tridecimator.