[toc]

# DCEL 为了解决什么？

首先我们知道，三角化后的 Mesh 的存储是一个又一个由顶点和边构成的的三角形
三角形与三角形之间存在的一定的关系，如 相邻 、 洞(包含在一个多边形内部的多边形) 等关系
三角形可能某些边有邻接边，但是某些边没有邻接边

为了能够更好的管理 Mesh 化后的图形，业界提出了 DCEL 这样的计算几何存储数据结构， 这种结构对于切分Mesh等操作而言非常的方便

共边
计算几何的图形最多只会存在一条边被两个 face 公用的情况

合法:

非法:

# DCEL 的一些定义

The main building block of a DCEL is a list of half edges.Every actual edge is represented by two half edges going in opposite directions,and these are called twins

DCEL 构建的最基本单位是 半边(half edges) ，半边是指: 有方向的两个顶点之间的边 ，通常，如果两个面相邻，有共边，则 共边是由两个半边构成,且方向相反 ，而这两个半边被称为 Twin 。
如上图， g2 和 h2 就是一个 twin, 且所有有向边都是 半边
其中对于半边和 twin 相关的函数式表达如下:

Tag: 但是看后面的实现，实际上会对每个半边都建立一个 twin, 而不是邻接边才会建立 twin

洞

如上图所示，一个多边形中很可能还包含一些 洞 ，所以 DCEL 结构还需要考虑这些洞的存储方式

# DCEL 的构建

主要分为:
1. 边表
2. 顶点表
3. 面表

首先一个 edge 需要保存的信息如上图所示

它的 Twin 边
它的 next 边
它的 prev 边
它的起点 (origin)
它的 Id
incident_face (这条边对应的面，位于边的左侧)

顶点对应的需要存储的信息

id
坐标 (x/y)
inc (以他为起始的第一条边)

面表需要存储的信息

id
inc (面对应的第一个边)

# DCEL 结构的实现

# 1. 边表

边表的起点 origin
边的 twin
边的 next
边的 prev
边对应的表面 incident_face

template<class type = float,size_t dim = DIM3>
struct EdgeDCEL {
    VertexDCEL<type, dim>* origin = nullptr;
    EdgeDCEL<type, dim>* twin = nullptr;
    EdgeDCEL<type, dim>* next = nullptr;
    EdgeDCEL<type, dim>* prev = nullptr;
    FaceDCEL<type, dim>* incident_face = nullptr;
    int id;

    EdgeDCEL() { id = -1; }

    EdgeDCEL(VertexDCEL<type, dim>* _origin) : origin(_origin) {
        id = _id++;
    }

    VertexDCEL<type, dim>* destination() {
        return twin->origin;
    }

    void print() {
        std::cout << "This point pointer" << this << "\n";
        std::cout << "Origin : "; this->origin->print();
        std::cout << "Twin pointer" << this->twin << "\n";
        std::cout << "Next pointer" << this->next << "\n";
        std::cout << "Prev pointer" << this->prev << "\n";
    }
};

# 2. 顶点表

顶点的坐标
以顶点为始的第一条边

template<class type = float, size_t dim = DIM3>
struct VertexDCEL {
    //Coordinates of the vertex
    Vector<float, dim> point;
    //Incident edge to the vertex
    EdgeDCEL<type, dim>* incident_edge = nullptr;

    VertexDCEL(Vector<type,dim>& _point) : point(_point){}

    void print() {
        std::cout << "(" << point[X] << "," << point[Y] << ")\n";
    }
};

# 面表

该面的第一个边 outer
inner 是干啥的暂时不知道 (应该是存边内的洞)

template<class type = float,size_t dim = DIM3>
struct FaceDCEL {
    //Pointer to one of the counter clockwise edge
    EdgeDCEL<type, dim>* outer = nullptr;
    //Pointer to first halfedges which represnt 
    std::vector<EdgeDCEL<type, dim>*> inner;
    void print(){
        if (outer) {
            auto edge_ptr = outer;
            auto next_ptr = outer->next;

            edge_ptr->origin->print();
            while (next_ptr != edge_ptr) {
                next_ptr->origin->print();
                next_ptr = next_ptr->next;
            }
        }
    }
    std::vector<EdgeDCEL<type,dim>*> getEdgeList(){
        std::vector<EdgeDCEL<type, dim>*> edge_list;
        if (outer) {
            auto edge_ptr = outer;
            auto next_ptr = outer->next;
            edge_list.push_back(edge_list);
            edge_ptr->origin->print();
            while (next_ptr != edge_ptr) {
                edge_list.push_back(next_ptr);
                next_ptr = next_ptr->next;
            }
        }
    }
    std::vector<Vector<float,dim>> getPoints(){
        std::vector<Vector<float, dim>> point_list;
        if (outer) {
            auto edge_ptr = outer;
            auto next_ptr = outer->next;
            point_list.push_back(edge_ptr->origin->point);
            while (next_ptr != edge_ptr) {
                point_list.push_back(next_ptr->origin->point);
                next_ptr = next_ptr->next;
            }
        }
        return point_list;
    }
};

Polygon (由面表构成的几何图集), 这个是更上一层的封装

vertex_list 代表该多边形的顶点列表
edge_list 代表该多边形的边列表
face_list 代表该多边形的面列表
empty_edge 是啥 (? 还没有被剖分过的列表么？)

方法: PolygonDCEL : 通过传入的顶点来初步构造 PolygonDCEL
split : 就是在三角剖分后找到一条对角线后，如何 插入这条对角线，并且对多边形进行切分 该切分边必须是一个合法的 diagonal
join : 合并两个面

template<class type = float,size_t dim = DIM3>
class PolygonDCEL {
    typedef Vector<type, dim> VectorNf;
    std::vector<VertexDCEL<type, dim>*> vertex_list;
    std::vector<EdgeDCEL<type, dim>*> edge_list;
    std::vector<FaceDCEL<type, dim>*> face_list;
    EdgeDCEL<type, dim>* empty_edge = new EdgeDCEL<type, dim>();
    public:
    //Construct the DCEL using given points
    //Assume the given points list is for polygon and have counter clockwise order
    explicit PolygonDCEL(std::vector<VectorNf>&);

    //Insert an edge between virtices _v1 and _v2 given that lies
    bool split(VertexDCEL<type, dim>* _v1, VertexDCEL<type, dim>* _v2);

    // Join the two faces sepated by edge between _v1 and _v2
    bool join(VertexDCEL<type, dim>* _v1, VertexDCEL<type, dim>* _v2);

    //Return the all the vertices across all the faces
    std::vector<VertexDCEL<type, dim>*> getVertexList();

    std::vector<FaceDCEL<type, dim>*> getFaceList();

    std::vector<EdgeDCEL<type, dim>*> getEdgeList();

    VertexDCEL<type, dim>* getVertex(VectorNf&);

    void getEdgesWithSamefaceAndGivenOrigins(VertexDCEL<type, dim>* _v1, VertexDCEL<type, dim>* _v2,
                                             EdgeDCEL<type, dim>** edge_leaving_v1, EdgeDCEL<type, dim>** edge_leaving_v2);
};

# 相关方法

假设只传入顶点，且顶点只有两个相邻顶点之间才有一个边

该结构体一开始是一个最 pure 的多边形 (很简单的所有点都在一个多边形上), 基于这个多边形可以去做一些三角剖分之类的事情，在做完这些事情后才会变得复杂

# 1. 多边形 DCEL 构造

总览

template<class type,size_t dim>
inline PolygonDCEL<type, dim>::PolygonDCEL(std::vector<VectorNf>& _points) {
    int size = _points.size();
    //Polygon should have atleast tree vertices
    if (size < 3)
        return;

    for (size_t i = 0; i < _points.size(); ++i) {
        vertex_list.push_back(new Vertex2dDCEL<type, dim>(_points[i]));
    }

    for (size_t i = 0; i <= vertex_list.size() - 2; ++i) {
        auto hfedge = new EdgeDCEL<type, dim>(vertex_list[i]);
        auto edge_twin = new EdgeDCEL<type, dim>(vertex_list[i + 1]);

        vertex_list[i]->incident_edge = hfedge;

        hfedge->twin = edge_twin;
        edge_twin->twin = hfedge;

        edge_list.push_back(hfedge);
        edge_list.push_back(edge_twin);
    }

    auto hfedge = new EdgeDCEL<type, dim>(vertex_list.back());
    auto edge_twin = new EdgeDCEL<type, dim>(vertex_list.front());

    hfedge->twin = edge_twin;
    edge_twin->twin = hfedge;

    edge_list.push_back(hfedge);
    edge_list.push_back(edge_twin);

    vertex_list[vertex_list.size() - 1]->incident_edge = hfedge;

    //Set the prev and next for the element middle of the list (2:size-2)
    for (size_t i = 2; i <= edge_list.size() - 3; ++i) {
        //偶数,计数
        if (i % 2 == 0) {
            edge_list[i]->next = edge_list[i + 2];
            edge_list[i]->prev = edge_list[i - 2];
        }
        else {
            edge_list[i]->next = edge_list[i - 2];
            edge_list[i]->prev = edge_list[i + 2];
        }
    }

    edge_list[0]->next = edge_list[2];
    edge_list[0]->prev = edge_list[edge_list.size() - 2];
    edge_list[1]->next = edge_list[edge_list.size() - 1];
    edge_list[1]->prev = edge_list[3];

    edge_list[edge_list.size() - 2]->next = edge_list[0];
    edge_list[edge_list.size() - 2]->prev = edge_list[edge_list.size() - 4];
    edge_list[edge_list.size() - 1]->next = edge_list[edge_list.size() - 3];
    edge_list[edge_list.size() - 1]->prev = edge_list[1];

    //Configure the faces
    FaceDCEL<type, dim>* f1 = new FaceDCEL<type, dim>();
    FaceDCEL<type, dim>* f2 = new FaceDCEL<type, dim>();

    f1->outer = edge_list[0];
    f2->inner.push_back(edge_list[1]);

    face_list.push_back(f1);
    face_list.push_back(f2);

    f1->outer->incident_face = f1;
    EdgeDCEL<type, dim>* edge = f1->outer->next;
    while (edge != f1->outer) {
        edge->incident_face = f1;
        edge = edge->next;
    }

    f2->inner[0]->incident_face = f2;
    edge = f2->inner[0]->next;
    while (edge != f2->inner[0]) {
        edge->incident_face = f2;
        edge = edge->next;
    }
}

先将所有顶点推到顶点表中

1
2
3

for (size_t i = 0; i < _points.size(); ++i) {
    vertex_list.push_back(new Vertex2dDCEL<type, dim>(_points[i]));
}

根据一个边 / 一个 twin 边的规则，构造出所有的边表 (每相邻的两个点之间有一个边)
最后连接一下起始点和终

for (size_t i = 0; i <= vertex_list.size() - 2; ++i) {
    auto hfedge = new EdgeDCEL<type, dim>(vertex_list[i]);
    auto edge_twin = new EdgeDCEL<type, dim>(vertex_list[i + 1]);

    vertex_list[i]->incident_edge = hfedge;

    hfedge->twin = edge_twin;
    edge_twin->twin = hfedge;

    edge_list.push_back(hfedge);
    edge_list.push_back(edge_twin);
}

auto hfedge = new EdgeDCEL<type, dim>(vertex_list.back());
auto edge_twin = new EdgeDCEL<type, dim>(vertex_list.front());

hfedge->twin = edge_twin;
edge_twin->twin = hfedge;

edge_list.push_back(hfedge);
edge_list.push_back(edge_twin);

vertex_list[vertex_list.size() - 1]->incident_edge = hfedge;

构造内边与外边的顺序关系

//Set the prev and next for the element middle of the list (2:size-2)
for (size_t i = 2; i <= edge_list.size() - 3; ++i) {
    //偶数,计数
    if (i % 2 == 0) {
        edge_list[i]->next = edge_list[i + 2];
        edge_list[i]->prev = edge_list[i - 2];
    }
    else {
        edge_list[i]->next = edge_list[i - 2];
        edge_list[i]->prev = edge_list[i + 2];
    }
}

edge_list[0]->next = edge_list[2];
edge_list[0]->prev = edge_list[edge_list.size() - 2];
edge_list[1]->next = edge_list[edge_list.size() - 1];
edge_list[1]->prev = edge_list[3];

edge_list[edge_list.size() - 2]->next = edge_list[0];
edge_list[edge_list.size() - 2]->prev = edge_list[edge_list.size() - 4];
edge_list[edge_list.size() - 1]->next = edge_list[edge_list.size() - 3];
edge_list[edge_list.size() - 1]->prev = edge_list[1];

把第一个边当作面的起始边，构造面和边的顺序关系

//Configure the faces
FaceDCEL<type, dim>* f1 = new FaceDCEL<type, dim>();
FaceDCEL<type, dim>* f2 = new FaceDCEL<type, dim>();

f1->outer = edge_list[0];
f2->inner.push_back(edge_list[1]);

face_list.push_back(f1);
face_list.push_back(f2);

f1->outer->incident_face = f1;
EdgeDCEL<type, dim>* edge = f1->outer->next;
while (edge != f1->outer) {
    edge->incident_face = f1;
    edge = edge->next;
}

f2->inner[0]->incident_face = f2;
edge = f2->inner[0]->next;
while (edge != f2->inner[0]) {
    edge->incident_face = f2;
    edge = edge->next;
}

# DCEL 为了解决什么？

# DCEL 的一些定义

# DCEL 的构建

# DCEL 结构的实现

# 1. 边表

# 2. 顶点表

# 面表

# 相关方法

# 1. 多边形 DCEL 构造

【计算几何】 剖分算法

【UE_Source】 部分FileSystem

【计算几何】剖分算法

【UE_Source】部分FileSystem