资源:半边结构

半边结构

翻译整理自Half-edge structure,这篇介绍比较完整

二维拓扑流形就是说,流形上的每个点都有一个领域,这个领域能够与欧几里得平面(就是普通意义上的平面)的某个区域一一连续对应, 简单地说,如果网格的每个边最多被两个面片共用,那么这个网格就是流形网格,否则称为非流形网格。

半边结构就是计算机用于描述二维拓扑流形的一种数据结构。

其数据结构简单,优点如下:

  • 有了点,边,面的显示表示,可以很容易存储关于点、边、面的用户自定义
  • 很容易通过循环器得到某一个顶点的1-ring领域,而不需要类似于基于面的结构中的分支判断语句
  • 查询速度较其他的数据结构而言快很多

半边结构主要有点是便于快速查询以下内容:

  • 哪些面使用了这个顶点
  • 哪些边使用了这个顶点
  • 哪些面使用了这条边
  • 哪些边构成了这个面
  • 哪些面和这个面相邻

半边结构可以描述许多多边形网格和所有图形(包括带循环的多个图形)。它甚至可以描述多边形网格和线框网格的许多混合体。线框网格在构建多边形网格时作为中间阶段自然出现:首先创建多段线,然后将其转换为实心多边形。

半边结构无法表示以下结构:

  • 不可定向流形(例如莫比乌斯带)
  • 非流形表面(例如两个立方体公用角点)

在计算机图形学上,表达表面网格的数据结构有三种,分别是

  • 面列表
  • 邻接矩阵
  • 半边结构

面列表的典型代表是.obj格式文件和Unity。其优点是,简单而且能够表达非流形网格,但网格查询和处理能力差。

当然还有一些不是利用索引,而是直接储存整个顶点的信息,典型代表是OpenGL可编程管线和.stl格式文件

数据结构示意:

struct VertexData;
struct EdgeData;
struct PolygonData;
 
struct HalfData
{
    HalfData* next;
    HalfData* previous;
    HalfData* pair;
 
    VertexData* origin;
    PolygonData* left;
    EdgeData* edge;
};
 
struct VertexData
{
    HalfData* half;
};
 
struct EdgeData
{
    HalfData* half;
};
 
struct PolygonData
{
    HalfData* half;
};
if (vertex.half != 0)
{
    HalfData* begin = vertex.half;
    HalfData* half = begin;
    do
    {
        // Do something.
        half = half->pair->next;
    }
    while(half != begin);
}
if (polygon.half != 0)
{
    HalfData* begin = polygon.half;
    HalfData* half = begin;
    do
    {
        // Do something.
        half = half->next;
    }
    while(half != begin);
}
bool HalfMesh::makeAdjacent(Half in, Half out)
{
    if (in.next() == out)
    {
        // Adjacency is already correct.
 
        return true;
    }
 
    Half b(in.next());
    Half d(out.previous());
 
    // Find a free incident half edge
    // after 'out' and before 'in'.
    Half g(findFreeIncident(out.origin(), 
        out.pair(), in));
    if (g.empty())
    {
        // There is no such half-edge.
        return false;
    }
    Half h(g.next());
 
    in.half_->next_ = out.half_;
    out.half_->previous_ = in.half_;
 
    g.half_->next_ = b.half_;
    b.half_->previous_ = g.half_;
 
    d.half_->next_ = h.half_;
    h.half_->previous_ = d.half_;
 
    return true;
}
  • 初始化点
  • 设置点半边为空
  • 初始化边
  • 初始化两个半边
  • 两个半边结构相互连接
  • 关联半边 ⇐⇒边
  • 关联边到面
  • 关联对边到面
Edge HalfMesh::addEdge(Vertex fromVertex, 
                       Vertex toVertex)
{
   // Decide what to do with loop edges.
   bool loopEdges = true;
   if (!loopEdges)
   {
      if (fromVertex == toVertex)
      {
         return Edge();
      }
   }
 
   // Decide what to do with parallel edges.
   bool parallelEdges = true;
   if (!parallelEdges)
   {
      Half existingHalf(findSomeHalf(fromVertex,
         toVertex));
 
      if (!existingHalf.empty())
      {
         return existingHalf.edge();
      }
   }
 
   // Allocate data
 
   Edge edge(allocateEdge());
   Half fromToHalf(allocateHalf());
   Half toFromHalf(allocateHalf());
 
   // Initialize data
 
   {
      EdgeData* edgeData = edge.edge_;
      edgeData->half_ = fromToHalf.half_;
   }
 
   {
      HalfData* halfData = fromToHalf.half_;
 
      halfData->next_ = toFromHalf.half_;
      halfData->previous_ = toFromHalf.half_;
      halfData->pair_ = toFromHalf.half_;
      halfData->origin_ = fromVertex.vertex_;
      halfData->edge_ = edge.edge_;
      halfData->left_ = 0;
   }
 
   {
      HalfData* halfData = toFromHalf.half_;
 
      halfData->next_ = fromToHalf.half_;
      halfData->previous_ = fromToHalf.half_;
      halfData->pair_ = fromToHalf.half_;
      halfData->origin_ = toVertex.vertex_;
      halfData->edge_ = edge.edge_;
      halfData->left_ = 0;
   }
 
   // Link the from-side of the edge.
 
   if (fromVertex.isolated())
   {
      VertexData* vertexData = fromVertex.vertex_;
      vertexData->half_ = fromToHalf.half_;
   }
   else
   {
      Half fromIn(findFreeIncident(fromVertex));
      Half fromOut(fromIn.next());
 
      fromIn.half_->next_ = fromToHalf.half_;
      fromToHalf.half_->previous_ = fromIn.half_;
 
      toFromHalf.half_->next_ = fromOut.half_;
      fromOut.half_->previous_ = toFromHalf.half_;
   }
 
   // Link the to-side of the edge.
 
   if (toVertex.isolated())
   {
      VertexData* vertexData = toVertex.vertex_;
      vertexData->half_ = toFromHalf.half_;
   }
   else
   {
      Half toIn(findFreeIncident(toVertex));
      Half toOut(toIn.next());
 
      toIn.half_->next_ = toFromHalf.half_;
      toFromHalf.half_->previous_ = toIn.half_;
 
      fromToHalf.half_->next_ = toOut.half_;
      toOut.half_->previous_ = fromToHalf.half_;
   }
 
   return edge;
}
  • 检查数据是否有效,以及给定的半边循环是否可以按照所需条件转换为面。
  • 重新排序链接,使给定的半边循环成为连续的,即一个半边的下一个字段指向循环中的下一个半边(类似于前一个字段)。
  • 创建面。
  • 将面连接到任意边界半边。
  • 将每个边界半边连接到面
Polygon HalfMesh::addPolygon(const std::vector<Half>& halfLoop)
{
   if (halfLoop.empty())
   {
      return Polygon();
   }
 
   integer halfCount = halfLoop.size();
 
   // Check that the half-edges are free
   // and form a chain.
 
   for (integer i = 0;i < halfCount;++i)
   {
      integer nextIndex = i + 1;
      if (nextIndex == halfCount)
      {
         nextIndex = 0;
      }
 
      Half current(halfLoop[i]);
      Half next(halfLoop[nextIndex]);
 
      if (current.destination() != next.origin())
      {
         // The half-edges do not form a chain.
         return Polygon();
      }
      if (!current.isFree())
      {
         // The half-edge would introduce a
         // non-manifold condition.
         return Polygon();
      }
   }
 
   // Try to reorder the links to get
   // a proper orientation.
 
   for (integer i = 0;i < halfCount;++i)
   {
      integer nextIndex = i + 1;
      if (nextIndex == halfCount)
      {
         nextIndex = 0;
      }
 
      if (!makeAdjacent(halfLoop[i], halfLoop[nextIndex]))
      {
         // The polygon would introduce a non-manifold
         // condition.
         return Polygon();
      }
   }
 
   // Create the polygon
 
   Polygon newPolygon(allocatePolygon());
 
   // Link the polygon to a half-edge
 
   PolygonData* polygonData = newPolygon.polygon_;
   polygonData->half_ = halfLoop[0].half_;
 
   // Link half-edges to the polygon.
 
   for (integer i = 0;i < halfCount;++i)
   {
      Half current(halfLoop[i]);
 
      HalfData* halfData = current.half_;
      halfData->left_ = newPolygon.polygon_;
   }
 
   return newPolygon;
}
  • 将每个边界半边的面设置为空。
  • 析构面
void HalfMesh::removePolygon(Polygon polygon)
{
   Half begin(polygon.half());
   Half current(begin);
 
   do
   {
      HalfData* halfData = current.half_;
      halfData->left_ = 0;
      current = current.next();
   } 
   while(current != begin);
 
   deAllocatePolygon(polygon);
}
  • 移除连接到边的所有面。
  • 将边的半边与网格取消连接。
  • 析构边及其半边。
bool HalfMesh::removeEdge(Edge edge)
{
   Half fromToHalf(edge.half());
   Half toFromHalf(fromToHalf.reverse());
 
   // Remove the neighbouring polygons.
 
   if (!fromToHalf.left().empty())
   {
      removePolygon(fromToHalf.left());
   }
 
   if (!toFromHalf.left().empty())
   {
      removePolygon(toFromHalf.left());
   }
 
   // Link the from-side of the edge
   // off the model.
 
   Vertex fromVertex(fromToHalf.origin());
 
   Half fromIn(fromToHalf.previous());
   Half fromOut(fromToHalf.rotateNext());
 
   if (fromVertex.half() == fromToHalf)
   {
      if (fromOut == fromToHalf)
      {
         fromVertex.vertex_->half_ = 0;
      }
      else
      {
         fromVertex.vertex_->half_ = fromOut.half_;
      }
   }
 
   fromIn.half_->next_ = fromOut.half_;
   fromOut.half_->previous_ = fromIn.half_;
 
   // Link the to-side of the edge
   // off the model.
 
   Vertex toVertex(toFromHalf.origin());
 
   Half toIn(toFromHalf.previous());
   Half toOut(toFromHalf.rotateNext());
 
   if (toVertex.half() == toFromHalf)
   {
      if (toOut == toFromHalf)
      {
         toVertex.vertex_->half_ = 0;
      }
      else
      {
         toVertex.vertex_->half_ = toOut.half_;
      }
   }
 
   toIn.half_->next_ = toOut.half_;
   toOut.half_->previous_ = toIn.half_;
 
   // 3) Deallocate data
 
   deAllocateHalf(fromToHalf);
   deAllocateHalf(toFromHalf);
   deAllocateEdge(edge);
}
  • 移除点到边的连接。
  • 析构顶点。
void HalfMesh::removeVertex(Vertex vertex)
{
   if (!vertex.isolated())
   {
      // Remove every edge that is connected
      // to this vertex
 
      Half current;
      Half next(vertex.half());
 
      do
      {
         current = next;
         next = next.rotateNext();
         // Avoid removing the same edge
         // twice in case of an edge loop.
         if (next.edge() == current.edge())
         {
            next = next.rotateNext();
         }
         removeEdge(current.edge());
      }
      while(current != next);
   }
 
   deAllocateVertex(vertex);
}
  • 资源/半边结构.txt
  • 最后更改: 2021/06/23 22:09
  • (外部编辑)