c++ - 统一共线边的网格简化算法

Question

通过从下面的网格中删除红色标记的顶点(将一个顶点分成两个共线的边缘)，并对受影响的面(在同一平面中)重新进行三角剖分，可以生成一个更简单的网格，表示完全相同的网格固体。

虽然用于短边折叠的算法非常普遍，但是我还找不到能够实现这种特定简化的任何东西。如果在CGAL或其他开源库中提供了实现，则可以加分。

Answer 1

首先，要测试两个相邻边是否共线，您需要确定是否可以允许舍入误差。 (假设您熟悉CGAL中的exact computation paradigm。)
第二个，如果您要进行无损抽取，则共线边缘可能不是一个好的指标。
共线边缘不能保证相应的面共面。
并且共面的面可能没有共线的边缘。

第三，每个边缘折叠操作都会产生成本。最常用的成本可能是二次误差，如Surface Simplification Using Quadric Error Metrics文件中所述。如果边缘折叠操作的成本为0，则表示该网格的形状未发生变化，而该误差度量标准则为零。
通过折叠所有成本为0的边，您可以获得想要的东西。
第四，在使边缘塌陷之后，您可能需要确定将新顶点放置在何处。至于无损抽取，您可以仅使用折叠边缘的端点之一。 (在this Stanford slides中称为半边折叠)。


CGAL不根据边缘崩溃成本提供停止谓词的实现(定义算法何时终止)。但是，实现一个很容易(这里我认为没有必要是精确的):

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

使用上述代码来无损简化四面体网格的结果:
(左:简化前，右:简化后)


还应注意，CGAL中实现的误差度量不是最常用的二次误差度量，而是 Lindstrom-Turk Cost，它具有更好的逼近度，如本文中所述: Fast and memory efficient polygonal simplification。
上面的代码不使用半边折叠，而是使用常规边折叠。这意味着新顶点将放置在最小化Lindstorm-Turk成本的位置。对于您的情况，此放置策略不是必需的。如果要减少额外的计算量，则可以自己实现半边折叠，这也不复杂。我想我只会使用现成的实现:)
只是让您知道， vcglib还提供了网格抽取功能，包括此多合一 tridecimator。