(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210621732.7 (22)申请日 2022.06.01 (71)申请人 浙江大学 地址 310058 浙江省杭州市西湖区余杭塘 路866号 申请人 浙江钱塘机 器人及智能装备研究有 限公司 (72)发明人 王进　厉圣杰　王鹏　陆国栋　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 万尾甜　韩介梅 (51)Int.Cl. G06T 17/20(2006.01) G06F 30/20(2020.01) (54)发明名称 一种基于改进包络测试的高效误差可控网 格简化方法 (57)摘要 本发明属于计算机图形学领域， 公开了一种 基于改进包络测试的高效误差可控网格简化方 法。 该方法是： 对于原始模型的网格， 首先对所有 面片生成误差包络多面体， 形成集合B， 并对集合 B构建稀疏网格加速 结构， 然后使用Q slim选出一 条待折叠边e， 将与e相邻的面片集合设为D， 基于 稀疏网格快速查找包络体集合B中与集合D 的面 片相交的包络体， 将其集合定义为B ’， 最后计算 出B’中裁剪平面与集合D中三角面片的交线， 从 而实现降维的覆 盖测试， 若B ’中的包络体完全包 含面片D， 则对边e进行折叠， 至此完成一次折叠。 循环直至没有边可以进行折叠为止。 本发明采用 误差包络体有效控制了简化模型的误差， 并且基 于稀疏网格查找和降维覆盖测试实现了更高的 简化效率。 权利要求书2页 说明书6页 附图4页 CN 115019012 A 2022.09.06 CN 115019012 A 1.一种基于改进包络测试的高效误差可控网格简化方法， 其特 征在于， 包括如下步骤： 步骤1： 对于原始模型的网格， 对所有面片生成误差包络多面体， 形成集合B， 并对集合B 构建稀疏网格加速结构； 步骤2： 使用Qsl im选出一条待折叠边e， 将与e相邻的面片集 合设为D， 步骤3： 基于稀疏网格快速查找包络体集合B中与集合D的面片相交 的包络体， 将其集合 定义为B’； 步骤4： 计算出B ’中裁剪平面与 集合D中三角面片的交线， 从而实现降维的覆盖测试， 若 B’中的包络体完全 包含面片D， 则可以对边e进行折叠； 步骤5： 循环执 行步骤2‑4， 直至没有边可以进行折叠为止 。 2.如权利要求1所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 步骤1中采用误差包络多面体进 行简化误差控制， 生成所述误差包络多面体需要先定 义误差值 δ， 然后对面片从二维的网格开始向外膨胀 δ 的距离 。 3.如权利要求1所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 步骤2 中采用Qslim选择每次折叠的待折叠边， 方法是找出模型面片中二次误差QE最 小的边作为待折叠边， 模型面片中边的二次误差QE是其两端顶点二次误差QE之和， 模型面 片中顶点的二次误差QE是从该点到其领域所有三角面片的距离平方和。 4.如权利要求1所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 步骤3中基于稀疏网格采用直接索引的方式进 行包络体筛选， 具体是基于三 维空间网 格即立方体网格对所有包络体的信息进行保存， 每个网格保存了占用此网格空间的所有包 络体的索引值： 利用基于链表结构的稀疏网格对包络体信息进行保存， 只有在三维空间网 格被占用时才 会为其构造节点， 根据式(1)定义 三维空间 网格尺寸s： s＝avg({li|li＝max(bi.x,bi.y,bi.z),i＝1,2,......,n})      (1) 其中bi为模型第i个网格的AABB包围盒， n表示模型网格总数， x、 y、 z表示包围盒沿x、 y、 z 方向的长度， li表示包围盒最长的棱长； 在完成稀疏网格的构建后， 为每个网格筛选与之相 关的包络体。 5.如权利要求4所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 在完成稀疏网格的构建后， 为每个网格筛选与之相关的包络体： 找出若待折叠边e被 折叠后会影响到的所有三角网格， 定义此集合为D； 遍历D中的元素f， 根据f的AABB包围盒的 坐标范围算出其所覆盖的三维空间网格； 对f记录其覆盖的三维空间网格所索引的包络体 ID并去重， 定义包络体集 合为B'， 若f没有被B'完全覆盖， 则不进行折叠 。 6.如权利要求1所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 采用降维覆盖测试降低原始覆盖测试方法所需的时间复杂度， 在做三角形 的包含测 试时， 检验三角形是否完全被一个凸多面体集合包含只需要检验以下三类点是否被凸多面 体集合包含即可： C1:三角形的顶点(ver tex)； C2:三角形 各边与凸多面体产生的交点； C3:三角形与凸多面体集 合中任意两个面之间产生的交点。 7.如权利要求6所述的一种基于改进包络测试的高效误差可控网格简化方法， 其特征 在于， 三维包络测试的本质在于判断三类交点是否在包络体内,权　利　要　求　书 1/2 页 2 CN 115019012 A 2由于只需要判定网格面是否被完全覆盖， 将三维包络问题转化为网格面所在平面的二 维问题， 并通过计算交线把三维的包络测试降至二维， 只在用到某一包络体时才对其进行 求交计算， 并保存交线方程的参数： ax2+by2+c＜0      (2) 其中x2和y2表示坐标值， 在求 交线时可以将C1类点的判断过程进一步简 化， 假设一个网 格面片的三个顶点的坐标分别为p1,p2,p3， 定义面片上任意 一点为p， 因此： p＝u(p2‑p1)+v(p3‑p1)+p1          (3) 其中u和v为0到1之间的标量， 可构成uv坐标系， 计算三角面片与凸多面体上任一平面 的交线： 其中A、 B、 C、 D均为定义凸多面体上某一平面的常数， A、 B、 C组成了 凸多面体上某一平面 的法向量， D可视作定义平面所处位置的附加约束， 在uv坐标系中， 包含测试中的C1类点分 别转化为(0,0),(0,1),(1,0)， 这三个点与直线的方向判别只需要检验c'， b'+c'与a'+c'的 符号即可， 其中 a'、 b'、 c'为式(4)中直线方程的系数。权　利　要　求　书 2/2 页 3 CN 115019012 A 3