CGAL：有效地找到体积中的所有三角形（边界框或球查询）
CGAL: efficiently finding all triangles in a volume (bounding box or ball query)
我想有效地找到包含在体积中或与体积相交的所有三角形（例如多面体网格的面）（例如 AABB 或球体查询）。如果可能且合理，我想使用 CGAL 的内置功能来执行此操作。
我目前的解决方案是简单的暴力破解：对于网格中的所有面，检查面到球中心的距离是否小于球半径。我之前在顶点上使用了 KD 树的模糊球体查询，但它对我的应用程序来说不够准确。我需要完整的球体-三角形交叉点。
CGAL AABB 树 (https://doc.cgal.org/latest/AABB_tree/index.html) seems like the best datastructure but I need the 3D linear Kernel which has no intersection test for triangles and any kind of volume (https://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html)。
CGAL KD树不起作用，因为它只能包含点。
我的想法是：
- 为 AABB 树可以使用的 Triangle_3 和 Sphere_3 添加自定义 do_intersect()。这可能吗？这可能还需要自定义 squared_distance()。
- 通过将三角形投影到例如，将体积查询转换为两个面积查询。 XY 和 YZ 平面。 AABB 树甚至可以处理二维搜索吗？圆形和 2D 三角形没有交集，但我可以使用 Iso_rectangle_2 和 Triangle_2 的交集作为第一个猜测。
- 以某种方式遍历 AABB 树的内部并在找到不再包含我的查询的节点之前停止。
- 修改 closest_point_and_primitive() 方法，提供一个可选的 max_distance 参数和 return 该距离内的所有图元。这需要我弄乱 CGAL 代码。
- 写我自己的数据结构。这需要一些时间才能正确完成。
我错过了什么吗？哪种解决方案最省力？
对于一组相交三角形，您可以使用：
std::vector<Primitive> primitives;
tree.all_intersected_primitives(sphere, std::back_inserter(primitives));
//or
tree.all_intersected_primitives(tree2, std::back_inserter(primitives));
其中 tree2 是边界体积的 AABB-tree 个三角形。
这将为您提供与体积边界相交的元素。然后你可以使用 Surface_mesh properties 为所有相交的面设置一个布尔值 true 。然后在边上创建一个新的 属性 并将其设置为 true 如果您将其中一个事件面的 属性 设置为 true。
然后调用 connected_components() 您将能够将网格拆分为包围体内部和外部的部分（忽略相交部分）。
最后，您需要为每个连接的组件选取一个点，并查看它是在包围体内部还是外部。对于球体，它是直接的，您可以使用 Side_of_triangle_mesh 作为网格情况（无需复制 AABB-tree 以节省内存和时间）。
如果你的边界体积是一个 bbox，你可以对球体做类似的事情。
使用 sloriot 的回答中的一些想法，我能够解决我的问题。
由于 do_intersect() 的文档没有显示 Sphere_3 和 Triangle_3 的重载，因此 AABB 树不支持 [= 的查询也就不足为奇了24=].
但是，AABB 树支持 BBox_3 的查询，do_intersect() 文档中没有提及。
使用 Bbox_3 returns 调用 all_intersected_primitives() Bbox_3 包含或相交的 AABB 树的所有原语。这是获得与球体的实际交点的第一个很好的猜测。
通过此优化，我可以将具有 100k 个面的网格上的查询时间从 20 毫秒（简单的蛮力）减少到 3 毫秒，其中一次查询 returns 大约 10 个面。
相关代码如下：
double r = CGAL::sqrt(patch_radius_squared);
CGAL::Bbox_3 query(
sphere_center.x() - r,
sphere_center.y() - r,
sphere_center.z() - r,
sphere_center.x() + r,
sphere_center.y() + r,
sphere_center.z() + r);
std::list<Tree::Primitive_id> primitives;
tree.all_intersected_primitives(query, std::back_inserter(primitives));
std::vector<Triangle_3> intersected_facets;
for (const Tree::Primitive_id& p : primitives)
{
// intersection with bb gives only a good first guess -> check actual intersection
if (CGAL::squared_distance(*p, sphere_center) <= patch_radius_squared)
{
intersected_facets.push_back(*p);
}
}
我想有效地找到包含在体积中或与体积相交的所有三角形（例如多面体网格的面）（例如 AABB 或球体查询）。如果可能且合理，我想使用 CGAL 的内置功能来执行此操作。
我目前的解决方案是简单的暴力破解：对于网格中的所有面，检查面到球中心的距离是否小于球半径。我之前在顶点上使用了 KD 树的模糊球体查询，但它对我的应用程序来说不够准确。我需要完整的球体-三角形交叉点。
CGAL AABB 树 (https://doc.cgal.org/latest/AABB_tree/index.html) seems like the best datastructure but I need the 3D linear Kernel which has no intersection test for triangles and any kind of volume (https://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html)。 CGAL KD树不起作用，因为它只能包含点。
我的想法是：
- 为 AABB 树可以使用的 Triangle_3 和 Sphere_3 添加自定义 do_intersect()。这可能吗？这可能还需要自定义 squared_distance()。
- 通过将三角形投影到例如，将体积查询转换为两个面积查询。 XY 和 YZ 平面。 AABB 树甚至可以处理二维搜索吗？圆形和 2D 三角形没有交集，但我可以使用 Iso_rectangle_2 和 Triangle_2 的交集作为第一个猜测。
- 以某种方式遍历 AABB 树的内部并在找到不再包含我的查询的节点之前停止。
- 修改 closest_point_and_primitive() 方法，提供一个可选的 max_distance 参数和 return 该距离内的所有图元。这需要我弄乱 CGAL 代码。
- 写我自己的数据结构。这需要一些时间才能正确完成。
我错过了什么吗？哪种解决方案最省力？
对于一组相交三角形，您可以使用：
std::vector<Primitive> primitives;
tree.all_intersected_primitives(sphere, std::back_inserter(primitives));
//or
tree.all_intersected_primitives(tree2, std::back_inserter(primitives));
其中 tree2 是边界体积的 AABB-tree 个三角形。
这将为您提供与体积边界相交的元素。然后你可以使用 Surface_mesh properties 为所有相交的面设置一个布尔值 true 。然后在边上创建一个新的 属性 并将其设置为 true 如果您将其中一个事件面的 属性 设置为 true。
然后调用 connected_components() 您将能够将网格拆分为包围体内部和外部的部分（忽略相交部分）。
最后，您需要为每个连接的组件选取一个点，并查看它是在包围体内部还是外部。对于球体，它是直接的，您可以使用 Side_of_triangle_mesh 作为网格情况（无需复制 AABB-tree 以节省内存和时间）。
如果你的边界体积是一个 bbox，你可以对球体做类似的事情。
使用 sloriot 的回答中的一些想法，我能够解决我的问题。
由于 do_intersect() 的文档没有显示 Sphere_3 和 Triangle_3 的重载，因此 AABB 树不支持 [= 的查询也就不足为奇了24=].
但是，AABB 树支持 BBox_3 的查询，do_intersect() 文档中没有提及。
使用 Bbox_3 returns 调用 all_intersected_primitives() Bbox_3 包含或相交的 AABB 树的所有原语。这是获得与球体的实际交点的第一个很好的猜测。
通过此优化，我可以将具有 100k 个面的网格上的查询时间从 20 毫秒（简单的蛮力）减少到 3 毫秒，其中一次查询 returns 大约 10 个面。
相关代码如下：
double r = CGAL::sqrt(patch_radius_squared);
CGAL::Bbox_3 query(
sphere_center.x() - r,
sphere_center.y() - r,
sphere_center.z() - r,
sphere_center.x() + r,
sphere_center.y() + r,
sphere_center.z() + r);
std::list<Tree::Primitive_id> primitives;
tree.all_intersected_primitives(query, std::back_inserter(primitives));
std::vector<Triangle_3> intersected_facets;
for (const Tree::Primitive_id& p : primitives)
{
// intersection with bb gives only a good first guess -> check actual intersection
if (CGAL::squared_distance(*p, sphere_center) <= patch_radius_squared)
{
intersected_facets.push_back(*p);
}
}