[CGAL] 3D快速相交和距离计算（AABB_tree）- 三角形碰撞检测

柔情只为你懂 2022-11-24 14:24 193阅读 0赞

### 文章目录 ###

*  AABB Tree简介
 *  接口
 *   *  构造
     *   *  由Triangle构造
         *  由Polyhedron构造
     *  相交测试
     *  构造出结果（Constructions）
     *  距离计算
 *  简单例子
 *   *  三角形碰撞检测

> 官方文档：[3D Fast Intersection and Distance Computation (AABB Tree)][3D Fast Intersection and Distance Computation _AABB Tree]  
> [原文链接][Link 1]，不定时更新，此文档为第一版，之后不再同步。

# AABB Tree简介 #

「AABB Tree」AABB树组件提供了静态数据结构和算法，以支持对有限的3D对象集执行**相交和距离查询**。可以查询存储在数据结构中的一组几何对象，以进行相交检测、相交计算和距离计算。

1.  如果在traits类中实现了相应的相交谓词和构造函数，则相交查询可以支持任何类型
2.  距离查询仅限于点查询

「官方提供的例子」

1.  相交查询：针对三角形集的线对象（射线、线、线段）查询、针对线段集的平面对象（平面、三角形）
2.  距离查询：查找从点查询到一组三角形的最近点

「注意」此组件不适合在n个对象集中查找所有对象的交对。适用于dD lso定向盒的相交序列组件，它可以找到所有ISO定向盒的相交对  
  
  
「工作原理」

1.  AABB树将几何数据的迭代器（例如，`std::list<Triangle>`的迭代器）作为输入，然后将其转换为基元(primitives)
2.  根据这些原语(primitives)，构建轴对齐边界框（AABB）的层次结构，并将其用于加快相交和距离查询。每个图元(primitive)可以访问一个输入几何对象（称之为基准）和该对象的一个参考标识。
3.  每个相交查询可以返回相交图元的相交对象（例如，用于射线查询的3D点或线段）以及id（face的句柄）
4.  同样，每个距离查询都可以返回点查询中最接近的点以及最接近的图元id

# 接口 #

## 构造 ##

AABB Tree组件的主要入口点是`AABB_tree`，该类从**几何数据集**中构建一个**静态的AABB树**，该类实例化后，即可进行**相交和距离查询等操作**。

### 由Triangle构造 ###

#include <CGAL/Simple_cartesian.h>
    #include <CGAL/AABB_tree.h>
    #include <CGAL/AABB_traits.h>
    #include <CGAL/AABB_triangle_primitive.h>
    
    typedef CGAL::Simple_cartesian<double> K;
    
    typedef K::FT FT;
    typedef K::Ray_3 Ray;
    typedef K::Line_3 Line;
    typedef K::Point_3 Point;
    typedef K::Triangle_3 Triangle;
    
    typedef std::list<Triangle>::iterator Iterator;
    typedef CGAL::AABB_triangle_primitive<K, Iterator> Primitive;
    typedef CGAL::AABB_traits<K, Primitive> AABB_triangle_traits;
    typedef CGAL::AABB_tree<AABB_triangle_traits> Tree;
    
    Point a(1.0, 0.0, 0.0);
    Point b(0.0, 1.0, 0.0);
    Point c(0.0, 0.0, 1.0);
    Point d(0.0, 0.0, 0.0);
    
    std::list<Triangle> triangles;
    triangles.push_back(Triangle(a,b,c));
    triangles.push_back(Triangle(a,b,d));
    triangles.push_back(Triangle(a,d,c));
    
    Tree tree(triangles.begin(),triangles.end());

### 由Polyhedron构造 ###

#include <CGAL/Simple_cartesian.h>
    #include <CGAL/AABB_tree.h>
    #include <CGAL/AABB_traits.h>
    #include <CGAL/Polyhedron_3.h>
    #include <CGAL/AABB_face_graph_triangle_primitive.h>
    
    typedef CGAL::Simple_cartesian<double> K;
    typedef K::Point_3 Point;
    typedef K::Plane_3 Plane;
    typedef K::Vector_3 Vector;
    typedef K::Segment_3 Segment;
    typedef K::Ray_3 Ray;
    typedef CGAL::Polyhedron_3<K> Polyhedron;
    typedef CGAL::AABB_face_graph_triangle_primitive<Polyhedron> Primitive;
    typedef CGAL::AABB_traits<K, Primitive> Traits;
    typedef CGAL::AABB_tree<Traits> Tree;
    typedef boost::optional< Tree::Intersection_and_primitive_id<Segment>::Type > Segment_intersection;
    typedef boost::optional< Tree::Intersection_and_primitive_id<Plane>::Type > Plane_intersection;
    typedef Tree::Primitive_id Primitive_id;
    
    Point p(1.0, 0.0, 0.0);
    Point q(0.0, 1.0, 0.0);
    Point r(0.0, 0.0, 1.0);
    Point s(0.0, 0.0, 0.0);
    
    Polyhedron polyhedron;
    polyhedron.make_tetrahedron(p, q, r, s);
    
    // constructs AABB tree
    Tree tree(faces(polyhedron).first, faces(polyhedron).second, polyhedron);

## 相交测试 ##

1.  `AABB_tree::do_intersect()`：测试输入图形是否与AABB树相交。此函数之所以快速，是因为它仅涉及谓词，并在遇到第一个相交点后就停止
2.  `AABB_tree::number_of_intersected_primitives()`：计算所有相交图元，返回个数
3.  `AABB_tree::all_intersected_primitives()`：枚举出所有相交图元的id（所以无需构造相应的相交对象）
4.  `AABB_tree::any_intersected_primitive()`：返回第一个相交的图元id（如果存在相交情况）
5.  `AABB_tree::first_intersected_primitive()`：返回与射线最近的相交对象ID（如果存在）

// 与线段是否相交
    Segment segment_query(a,b);
    if(tree.do_intersect(segment_query))
            std::cout << "intersection(s)" << std::endl;
    else
        std::cout << "no intersection" << std::endl;
    
    // 与射线相交的个数
    Ray ray_query(a,b);
    std::cout << tree.number_of_intersected_primitives(ray_query) 
        << " intersections(s) with ray query" << std::endl;
    
    // 与线段相交的所有图元的ID
    std::list<Primitive_id> primitives;
    tree.all_intersected_primitives(segment_query, std::back_inserter(primitives));

## 构造出结果（Constructions） ##

1.  `AABB_tree::all_intersections()`：与输入图元做相交检测，并构造出所有对象
2.  `AABB_tree::any_intersection()`：检测并构造出第一个相交图元
3.  `AABB_tree::first_intersection()`：检测并构造出与射线最近的相交对象

// 获得所有结果
    std::list<Segment_intersection> intersections;
    tree.all_intersections(segment_query, std::back_inserter(intersections));
    
    // 检测并构造出第一个相交图元
    Vector vec(0.0,0.0,1.0);
    Plane plane_query(a,vec);
    Plane_intersection plane_intersection = tree.any_intersection(plane_query);
    if(plane_intersection) { 
        if(boost::get<Segment>(&(plane_intersection->first)))
            std::cout << "intersection object is a segment" << std::endl;
    }

## 距离计算 ##

1.  `AABB_tree::closet_point()`：获得距离给定点最近的点
2.  `AABB_tree::closest_point_and_primitive()`：获得距离给定点最近的图元ID

说明：`AABB_tree`使用辅助搜索结构来加快距离查询，但默认情况下并不会生成此数据结构，因为它仅用于距离计算。用户可在第一次计算距离之前，通过调用`AABB_tree::accelerate_distance_queries()`来请求二级结构的构造。

// 计算最近点
    Point point_query(2.0, 2.0, 2.0);
    Point closest_point = tree.closest_point(point_query);
    std::cerr << "closest point is: " << closest_point << std::endl;
    
    // 最近的距离
    FT sqd = tree.squared_distance(point_query);
    std::cout << "squared distance: " << sqd << std::endl;
    
    // 计算最近点和最近点所在的图元ID
    typedef Tree::Point_and_primitive_id Point_and_primitive_id;
    Point_and_primitive_id pp = tree.closest_point_and_primitive(query);
    Point closest_point = pp.first; // 最近点
    Polyhedron::Face_handle f = pp.second;	// 最近点所在的图元ID
    std::cout << "closest point: " << closest_point << std::endl;
    std::cout << "closest triangle: ( "
        << f->halfedge()->vertex()->point() << " , " 
        << f->halfedge()->next()->vertex()->point() << " , "
        << f->halfedge()->next()->next()->vertex()->point()
        << " )" << std::endl;

# 简单例子 #

## 三角形碰撞检测 ##

// Author(s) : GeoDoer
    
    #include <iostream>
    #include <list>
    
    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/AABB_tree.h>
    #include <CGAL/AABB_traits.h>
    #include <CGAL/AABB_triangle_primitive.h>
    
    typedef CGAL::Simple_cartesian<double> Kernel;
    typedef Kernel::Point_3 Point3;
    typedef Kernel::Triangle_3 Triangle_3;
    typedef std::list<Triangle_3>::iterator Iterator;
    typedef CGAL::AABB_triangle_primitive<Kernel, Iterator> Primitive;
    typedef CGAL::AABB_traits<Kernel, Primitive> AABB_triangle_traits;
    typedef CGAL::AABB_tree<AABB_triangle_traits> Tree;
    typedef Tree::Primitive_id Primitive_id;
    
    int main()
    { 
    	三角网
    	Point3 a(1.0, 0.0, 0.0);
    	Point3 b(0.0, 1.0, 0.0);
    	Point3 c(0.0, 0.0, 1.0);
    	Point3 d(0.0, 0.0, 0.0);
    
    	std::list<Triangle_3> triangles;
    	triangles.push_back(Triangle_3(a, b, c));
    	triangles.push_back(Triangle_3(a, b, d));
    	triangles.push_back(Triangle_3(a, d, c));
    
    	三角网的AABB_tree
    	Tree tree(triangles.begin(), triangles.end());
    
    	用一个三角形与该三角网做相撞测试
    	Triangle_3 tri_query(c, d, b);
    
    	碰撞检测
    	if(!tree.do_intersect(tri_query))
    	{ 
    		std::cout << "不相交" << std::endl;
    	}
    
    	相交个数
    	std::cout << "相交个数" << tree.number_of_intersected_primitives(tri_query) << std::endl;
    
    	获得与tri_query相交的所有图元
    	std::list<Primitive_id> primitives;
    	tree.all_intersected_primitives(tri_query, std::back_inserter(primitives));
    
    	for(std::list<Primitive_id>::iterator it = primitives.begin(); it != primitives.end(); ++it)
    	{ 
    		const Primitive_id& primitive_id = *it;
    		int index = std::distance(primitives.begin(), it); //第几个
    		std::cout << "第" << index << "个三角形：";
    		std::cout << primitive_id->vertex(0) << ";" << primitive_id->vertex(1) << ";" << primitive_id->vertex(2) << std::endl;
    	}
    
    	第一个相交的图元
    	auto first_intersection_id = tree.any_intersected_primitive(tri_query);
        
    	return EXIT_SUCCESS;
    }

三角网太复杂时，遇到这种问题：初判是精度问题，还不知道如何解决

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20200806162437785.png]

[3D Fast Intersection and Distance Computation _AABB Tree]: https://doc.cgal.org/latest/AABB_tree/index.html
[Link 1]: https://www.yuque.com/docs/share/d5d96582-fa02-431b-bbad-e92c5ae2595d?#%E3%80%8A3D%E5%BF%AB%E9%80%9F%E7%9B%B8%E4%BA%A4%E5%92%8C%E8%B7%9D%E7%A6%BB%E8%AE%A1%E7%AE%97%EF%BC%88AABB%E6%A0%91%EF%BC%89%E3%80%8B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]: /images/20221124/a14b126119d84b138641c7bc80025a11.png
[20200806162437785.png]: /images/20221124/f57b2d859dd647f897252ac51aa53b44.png