[Goal]

  • Visual-Inertial Algorithm에서는 delaunay triangulation으로 3D mesh 및 reconstruction을 할 수 있다.

[Reference Site]

  • Paper
    1. Jim Ruppert, “A Delaunay Refinement Algorithm for Quality 2-imensional Mesh Generation,” Journal of Algorithms, pp.548–585, May 1995.
    2. Jonathan Richard Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator," Applied Computational Geometry Towards Geometric Engineering, pp.203–222, 1996.

[Preliminary]

  • 알아야 할 용어들
    1. Vertex, Segment, Edge, Polygon
    2. Delaunay Triangulation

[Delaunay Triangulation]

  • Computational Geometry에서 주로 사용되는 용어로서 Delaunay Triangulation은 Delone Triangulation이라고도 부름
  • Delaunay Triangulation은 discrete points $P$가 있을 때, 결과는 다음과 같이 표기됨; $\mathcal{DT}(P)$
  • Delaunay Triangulation은 다음과 같은 조건들이 만족하는 알고리즘
    1. 삼각형 안에 다른 (외접) point들이 없어야 함
    2. 삼각형을 이루는 3개의 각들이 모두 최소 각 $\alpha$ 보다 커야함 (maximize acute or skinny angle)
      • Refinement 알고리즘에서는 약 30도정도 이상을 설정한다고 작성되어 있음
  • Delaunay Triangulation이 제대로 작성되지 않은 경우가 다음과 같음
    1. 하나의 line에 동일한 point들이 여러개가 있다면 $\mathcal{DT}$ 생성 안됨
    2. Point 3개로 외접원을 만들었는데 그 외접원에 다른 point도 들어가 있는 경우

[Overall Methodology]

  • Part 1. Generate Delaunay Triangulation
    • 먼저 Delaunany triangulation을 생성하는데 acute한 각이 생성되도 무관하게 generation
      • 이 삼각형을 silver triangle이라고 부름 (하나 또는 두개의 각이 극도록 예각인 삼각형)

 

template<typename T>
const std::vector<typename Delaunay<T>::TriangleType>&
Delaunay<T>::triangulate(std::vector<VertexType> &vertices)
{
     // Store the vertices locally
     _vertices = vertices;

     // Determinate the super triangle
     T minX = vertices[0].x;
     T minY = vertices[0].y;
     T maxX = minX;
     T maxY = minY;

     for(std::size_t i = 0; i < vertices.size(); ++i)
     {
         if (vertices[i].x < minX) minX = vertices[i].x;
         if (vertices[i].y < minY) minY = vertices[i].y;
         if (vertices[i].x > maxX) maxX = vertices[i].x;
         if (vertices[i].y > maxY) maxY = vertices[i].y;
     }

     const T dx = maxX - minX;
     const T dy = maxY - minY;
     const T deltaMax = std::max(dx, dy);
     const T midx = (minX + maxX) / 2;
     const T midy = (minY + maxY) / 2;

     const VertexType p1(midx - 20 * deltaMax, midy - deltaMax);
     const VertexType p2(midx, midy + 20 * deltaMax);
     const VertexType p3(midx + 20 * deltaMax, midy - deltaMax);

     // Create a list of triangles, and add the supertriangle in it
     _triangles.push_back(TriangleType(p1, p2, p3));

     for(auto p = begin(vertices); p != end(vertices); p++)
     {
         std::vector<EdgeType> polygon;

         for(auto & t : _triangles)
         {
             if(t.circumCircleContains(*p))
             {
                 t.isBad = true;
                 polygon.push_back(Edge<T>{*t.a, *t.b});
                 polygon.push_back(Edge<T>{*t.b, *t.c});
                 polygon.push_back(Edge<T>{*t.c, *t.a});
             }
         }

         _triangles.erase(std::remove_if(begin(_triangles), end(_triangles), [](TriangleType &t){
         return t.isBad;
         }), end(_triangles));

         for(auto e1 = begin(polygon); e1 != end(polygon); ++e1)
         {
             for(auto e2 = e1 + 1; e2 != end(polygon); ++e2)
             {
                 if(almost_equal(*e1, *e2))
                 {
                     e1->isBad = true;
                     e2->isBad = true;
                 }
             }
         }

         polygon.erase(std::remove_if(begin(polygon), end(polygon), [](EdgeType &e){
         return e.isBad;
         }), end(polygon));

         for(const auto e : polygon)
         _triangles.push_back(TriangleType(*e.v, *e.w, *p));
     }

     _triangles.erase(std::remove_if(begin(_triangles), end(_triangles), [p1, p2, p3](TriangleType &t){
     return t.containsVertex(p1) || t.containsVertex(p2) || t.containsVertex(p3);
     }), end(_triangles));

     for(const auto t : _triangles)
     {
         _edges.push_back(Edge<T>{*t.a, *t.b});
         _edges.push_back(Edge<T>{*t.b, *t.c});
         _edges.push_back(Edge<T>{*t.c, *t.a});
     }

     return _triangles;
}

[Results]

  • [문제점] 보면 silver triangle이 생성되는 것이 보임

                → 그래서 acute 한 각을 setting하는 것이 필요!!; Delaunay Triangulation Refinement 알고리즘 진행!! 

저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바