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

Question

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

虽然短边折叠算法很常见，但我还没有找到任何实现这种特定简化的算法。如果 CGAL 或其他开源库中的实现可用，则加分。

Answer 1

首先，要测试相邻的两条边是否共线，需要决定是否可以容忍舍入误差。（假设您熟悉 CGAL 中的 exact computation paradigm。）

其次，如果您想要无损抽取，共线边缘可能不是一个好的指标。
共线边不能保证对应的面是共面的。
并且共面可能没有共线边。

第三种，每次边塌陷操作都会产生成本。正如论文 Surface Simplification Using Quadric Error Metrics 中所述，最常用的成本可能是 二次误差 。如果边缘折叠操作的成本为 0，这意味着网格的形状没有改变，w.r.t 这个误差指标。
通过折叠所有成本为 0 的边，您可以得到您想要的。

第四，折叠边后，您可能需要确定放置新顶点的位置。至于你的无损抽取，你可以只使用折叠边缘的端点之一。（在 this Stanford slides 中称为 half-edge collapse）。

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 which has better approximating power as stated in the paper: Fast and memory efficient polygonal simplification.

而且上面的代码没有使用半边折叠，而是一般边折叠。这意味着新顶点将放置在最小化 Lindstorm-Turk 成本 的位置。对于您的情况，这种放置策略不是必需的。如果想减少额外的计算量，可以自己实现半边折叠，也不复杂。我想我只会使用现成的实现:)

只想告诉你，vcglib also provides mesh decimation capabilities, including this all-in-one tridecimator。

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

Algorithm for mesh simplification unifying co-linear edges

c++

algorithm

computational-geometry

mesh

cgal