文件名称：分裂平面的选-differential privacy and applications 差分隐私综述
文件大小：453KB
文件格式：PDF
更新时间：2024-06-23 12:35:35
AABB包围盒 碰撞检测
AABB 包围盒划分成左右两个子节点。(2) 分裂平面的选 择是使 AABB 包围盒树平衡的关键 ,首先确定分裂轴 ,使 用最长轴方法 ,即选择的方向轴是 AABB 在此方向上最长 的 ;而后确定分裂点 ,选择根节点集合中所有基本几何元素 的中心点在分裂轴上的投影 ,以最小点和最大点为两个中 心点 ,按距离将所有投影点分为两组。将距离中心点等距 的点归入含投影点少的一组。建立平衡的 AABB 树提高 了遍历 AABB 树的效率。 2. 3. 2 叶结点的压缩存储 文献[2 ]对 AABB 树中的内部节点进行了存储压缩 , 减少了存储 AABB 树所需的字节数。本文在此基础上进 一步对 AABB 树的叶结点进行压缩存储 ,减少算法的执行 时间和存储空间。 AABB 树叶节点的常规存储结构包括 AABB 包围盒 信息和三角形索引两个域。应用 Möller [5 ,6 ] 提出的快速三 角形与三角形相交测试和快速三角形与包围盒相交测试算 法 ,两个测试对象的 AABB 树重叠测试过程中涉及到叶节 点的重叠测试都可以不用到包围盒信息而直接用三角形进 行测试 ,这样就可以从叶节点的存储结构中删去包围盒信 息。叶节点的存储结构中只有三角形的索引信息 ,此时就 不必再用一个独立的节点表示叶节点。将三角形索引存放 到父节点中 ,从包围盒树的存储空间中删除叶节点。叶节 点的三角形索引在父节点中存放时不需要为父节点分配额 外的存储空间 ,直接替换父节点的孩子索引域为孩子叶节 点的三角形索引信息。此时 ,叶节点的父节点结构如表 1 所示。表 1 中标志位的最后两位取值为 1 ,表示其左右孩 子节点均为叶节点。 表 1 叶节点的父节点结构 范围值 (12 个字节) 左子节点 三角形索引 (4 个字节) 右子节点 三角形索引 (4 个字节) 标志位 (1 个字节) 1 1 一棵含有 N 个叶节点的完全 AABB 树共有 2 3 N - 1 个节点 ,存储 AABB 树时不需要为叶节点分配存储空间 , 则相当于从包围盒树的节点中删掉了一半的节点。这样大 大节省了存储空间 ,减少了一半的内存需求。 3 实验结果 我们在 PC 机上进行了实验 ,输入数据是包含不同数 06