1.一种基于二叉树的网格划分方法,其特征在于,包括二叉树网格的创建与二叉树网格的划分,所述二叉树网格的划分包含区域网格的划分,其中,所述二叉树网格的创建包含以下步骤:
(1)构造三角形库(Triangles),并将构成3D模型的所有三角形输入三角形库中;
(2)构造树节点;
(3)构造树节点库(TreeNodes),并将得到的树节点加入到树节点库中;
(4)遍历查找所有所述三角形以获得完整的树节点库,其中所述树节点库中的每一个树节点分别对应于所述三角形库中的一个节点三角形;
所述区域网格的划分包含以下步骤:
(5)输入区域点t1、t2和最大细分网格面积S;
(6)在所述三角形库中查找所有所述节点三角形,记为V,其投影包含于或相交于区域(t1,t2);
(7)确定是否遍历V中的三角形N1,并响应于确定结构执行以下步骤:(7.1)如果所述确定结构为非空且所述三角形N1的面积大于所述最大细分网格面积S,则对所述三角形N1划分直至其满足所述最大细分网格面积S的要求,然后结束划分;
(7.2)如果所述确定结构为非空且所述三角形N1的面积小于所述最大细分网格面积S,从V中移除N1并返回至步骤(7)继续循环;
(7.3)如果所述确定结果为空,则直接结束划分。
2.根据权利要求1所述的基于二叉树的网格划分方法,其特征在于,所述构造树节点包含:在三角形库中任选择一个三角形作为起始三角形①,以该三角形任一条边为父边,并确定左边和右边,得到第一个树节点。
3.根据权利要求2所述的基于二叉树的网格划分方法,其特征在于,所述遍历查找所有所述三角形包含:查找与所述起始三角形①的左边、右边共边的另外的三角形以确定是否存在新的树节点,若存在,则以该共边为父边,重复上述操作以从另外的三角形继续遍历查找。
4.根据权利要求3所述的基于二叉树的网格划分方法,其特征在于,通过以下步骤基于原树节点来查找新的树节点:(4.1)确定在树节点库中查找原树节点的左边/右边是否存在于除原树节点以外的其他树节点中;
(4.2)如果是,则在原树节点与查到的树节点之间建立连接关系并结束本次查找;
(4.3)如果不是,则确定在三角形库中查找原树节点的左边/右边是否存在于除原树节点以外的其他树节点中,(4.3.1)如果是,则用查到的三角形构造新的树节点并将新的树节点加入到树节点库中,(4.3.2)如果不是,则发出错误报告并结束本次查找。
5.根据权利要求1所述的基于二叉树的网格划分方法,其特征在于,对所述三角形N1划分包含:则计算三角形N1的最长边L,计所述最长边L相邻三角形为N2,并确定所述三角形N2投影与区域(t1,t2)是否包含或相交;
(7.1.1)如果结果为是,若三角形N2最长边是L则划分N1、N2公共边L,得到三角形n1、n2、n3、n4,若三角形N2最长边不是L则返回至步骤(7)继续循环;
(7.1.2)如果结果为否,则直接划分N1、N2公共边L,得到n1、n2、n3、n4。
6.根据权利要求5所述的基于二叉树的网格划分方法,其特征在于,所述方法进一步包含:(7.1.3)待所述三角形N1被划分为n1、n2、n3、n4后,从V中移除N1,将n1三个相邻节点加入到V中,并返回至步骤2.3.3继续循环。
7.根据权利要求6所述的基于二叉树的网格划分方法,其特征在于,通过以下步骤划分N1、N2公共边L,得到n1、n2、n3、n4:(1)输入父节点n1、子节点n2;
(2)计算n1、n2共边的终点P;
(3)将终点P存入顶点库(Vertices)中;
(4)用P点分割n1得到n3;
(5)用P点替换n1的所述顶点库和所述三角形库对应的信息;
(6)将n3存入所述三角形库和所述树节点库中;
(7)用P点分割n2得到n4;
(8)用P点替换n2的所述顶点库和所述三角形库对应的信息;
(9)将n4存入所述三角形库和所述树节点库中;
(10)构造n1、n2、n3、n4的连接关系。