首页 > 编程学习 > source impl - 网格自相交区域检测

source impl - 网格自相交区域检测

发布时间:2022/9/1 19:18:24

source impl - 网格自相交区域检测

不同方法简介

方法一

  1. 利用[[cgal_sc_box_intersection_d]]粗筛相交对,这个过程中,忽略相邻的三角形对(包括,共边,和共点的三角形对);
  2. 对这些潜在的相交三角形对,进行准确的相交测试,获取得到自相交对SelfInterPair1;
  3. 获取共点但不共边的所有三角形对;FacePairSharedVertexNotSharedEdge
  4. 遍历FacePairSharedVertexNotSharedEdge,进行自相交计算(计算过程中需要特殊实现,需要共点外有其他相交),获取得到自相交对SelfInterPair2;
  5. SelfInterPair1和SelfInterPair2的并集,就是所有的自相交对;

方法二

[[paper-2004-self-intersection-removal-in-triangular-mesh-offsetting]]中介绍的方法:

为了避免invalid region中的三角形相交检测,我们使用了bucket的结构。每个bucket三角形数量要少于C(bucket的容量)。

如果bucket中的三角形数量大于C,那么沿着AABB的最长边,将其分成两个bucket。被切割面相交的三角形会存储到两个bucket中。然后再每个bucket中执行所有三角形对的相交测试。三角形对的相交测试基于Moller T. A fast triangle-triangle intersection test[J]. Journal of Graphics Tools, 1997, 2(2): 25-30.,[[paper-impl-a-fast-triangle-triangle-intersection-test]]。每个相交对存储了指向相交三角形的指针,以及每个三角形存储了相交对列表,并计算得到了相交线段。

不同方法实现

方法一的实现代码见:CGLaboratory/box_inter_based_get_self_intersection_pairs.h at main · grassofsky/CGLaboratory (github.com)

方法二的实现代码见:CGLaboratory/aabsptree_based_get_self_intersection_pairs.h at main · grassofsky/CGLaboratory (github.com)

结果示意

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号