在数据结构中将B-Rep转换为树

1 B-rep流

明确指出要建立一个生产程序,将由某种标准多边形格式(例如,波前或java3D obj文件)在外部定义的B-rep导入到我们的几何管道的输入流中。多边形和法线提供的边界表示必须一致地定向。对于主要在计算机图形学中实现的一般归档的几何模型,可能需要过滤输入文件以应对非平面多边形和其他几何误差。然后,通过以下描述的算法步骤,将相干定向的三角形的输出流转换为我们的双渐进式BSP(二进制搜索分区)树。

2 B-rep到BSP算法概述

我们方法的基本过程是通过收缩每个三角形的预先计算出的惯性来计算三角形子集的惯性,并对三角形子集的惯性进行本征分解,以最优地和递归地约束其形状。

在d维情况下,对于Euler矩阵的每个d个特征向量,实施2个极值正切超平面可获得形状限制。对应的2d超空间的交集创建了当前单元格中包含的边界子集的最佳拟合(超)平行六面体。在3Dimension中,有6 = 2×3这样的平面。

初始化

  • 首先计算每个输入三角形的仿射扩展的欧拉张量(线性时间)。

  • 整个输入三角形集与BSP根相连。

  • 整个E3空间(凸面)都连接到根。

  • 根标签设置为FUZZY。

递归案例

  • 当前的FUZZY像元最多被垂直于当前三角形子集的Euler张量的矩阵表示的特征向量垂直的6个正交超平面划分。

  • 通过在当前三角形子集的顶点v上评估的线性函数w = a•v的最小值和最大值计算这些平面,其中a表示当前特征向量。

  • 在每个特征向量的情况下,最多由两个最大-最小平行超平面产生三个凸单元,它们是{OUT,FUZZY,IN}或{OUT,FUZZY,OUT}。

  • 每个FUZZY像元进一步被与最大特征向量相关的主超平面划分。

  • 较小的三角形子集通过其顶点的包含测试与每个分割的单元相连。

  • 穿过分割平面的三角形被分割,并且(子)三角形被连接到节点子树。

基本情况

当当前像元仅由少量边界三角形组成时,基于递归惯性的除法将停止。执行最终的单元划分,以实现边界三角形的平面。