Article directory
- Preface
- 1. Introduction to bounding box algorithm
- 2. PCA-based bounding box implementation principle
- 3. Code implementation
- 4. Test results
Foreword
In PCL (Point Cloud Library), a bounding box is a geometric shape used to describe the boundaries of objects in point cloud data. It is usually a cube or cylinder that can be used to surround objects in point cloud data, and can easily calculate information such as the position, size, and shape of objects in point cloud data.
PCL provides many different types of bounding boxes, including cubes, spheres, cylinders, polygons, etc. These bounding boxes can adjust their size and shape by setting their parameters to adapt to different point cloud data and application scenarios.
When using bounding boxes for tasks such as point cloud data segmentation, target detection, and pose estimation, it is usually necessary to first use some algorithm to extract the boundary information of the object from the point cloud data, and then match this boundary information with the bounding box, thereby Determine information such as the location, size, and shape of each object. PCL provides a variety of algorithms for point cloud data segmentation, target detection, attitude estimation and other tasks, and these algorithms usually use bounding boxes to assist in processing point cloud data.
1. Introduction to bounding box algorithm
Bounding box is an algorithm for solving the optimal bounding space of a discrete point set. The basic idea is to approximately replace complex geometric objects with slightly larger geometric objects (called bounding boxes) with simple characteristics.
Common bounding box algorithms include AABB bounding box, bounding sphere, directional bounding box OBB and fixed direction convex hull FDH. Collision detection problems are widely used in fields such as virtual reality, computer-aided design and manufacturing, games, and robots, and have even become a key technology. The bounding box algorithm is one of the important methods for preliminary detection of collision interference.
The most common bounding box algorithms are AABB bounding box (Axis-aligned bounding box), bounding sphere (Sphere), directional bounding box OBB (Oriented bounding box) and fixed direction convex hull FDH (Fixed directions hulls or k- DOP).
AABB is the earliest bounding box used. It is defined as the smallest hexahedron that contains the object and has sides parallel to the coordinate axis (parallel coordinate axes not only means that the box is parallel to the world coordinate axis, but also means that each face of the box is perpendicular to a coordinate axis. The same object AABB may also be different in different directions. If an object moves and transforms in the scene, its AABB also needs to move accordingly. When the object rotates, there are two options. Use the transformed object to recalculate the AABB, or do the sum of the AABB. The same transformation of objects). Therefore, to describe an AABB, only six scalars are needed. AABB has a relatively simple structure and small storage space, but its compactness is poor. Especially for irregular geometric shapes, the redundant space is large. When the object is rotated, it cannot be rotated accordingly. The processing objects are rigid and convex, which is not suitable for complex virtual environment situations involving soft body deformation.
The points in AABB need to satisfy the xyz coordinate points that are greater than the minimum coordinate and less than the maximum coordinate point. Therefore, you need to know the minimum point and maximum point of the two vertices; the center point is the midpoint of the two vertices and represents the center of mass of the bounding box.
An object’s bounding sphere is defined as the smallest sphere that contains the object. To determine the surrounding sphere, you first need to calculate the mean of the x, y, and z coordinates of the vertices of all elements in the set of basic geometric elements that make up the object to determine the center of the surrounding sphere, and then determine the center of the sphere and the three maximum coordinates. The distance between points determines the radius r. The collision detection of the surrounding sphere is mainly to compare the radius between the two spheres and the distance from the center of the sphere. (Since the sphere has only one degree of freedom, detecting the sphere is not sensitive to the direction of the object.)
OBB is a more commonly used bounding box type. It is the smallest cuboid that contains the object and has any direction relative to the coordinate axis (OBB determines the size and direction of the box based on the geometric shape of the object itself, and the box does not need to be perpendicular to the coordinate axis). The biggest feature of OBB is the arbitrariness of its direction, which allows it to surround the object as closely as possible according to the shape characteristics of the surrounded object, but it also makes its intersection test complicated. The OBB bounding box approximates the object more closely than the AABB bounding box and the bounding sphere, and can significantly reduce the number of bounding bodies, thereby avoiding intersection detection between a large number of bounding bodies. But intersection detection between OBBs is more time-consuming than intersection detection between AABBs or surrounding spheres.
FDH (k-DOP) is a special convex hull that inherits the simplicity of AABB, but in order to have good spatial compactness, it must use enough fixed directions. It is defined as the convex hull containing the object and having the normal vectors of all its faces taken from a fixed set of directions (k vectors). FDH surrounds the original object more closely than other bounding volumes, and the hierarchical tree created has fewer nodes, which reduces more redundant calculations during intersection detection, but the intersection operations are more complicated.
Advantages and disadvantages:
AABB is also a relatively simple type of bounding box. But for elongated objects placed diagonally, the tightness is poor. Due to the simplicity and good tightness of the AABB intersection test, it has been widely used and can also be used for collision detection of soft objects.
The bounding ball is a relatively simple bounding box, and when the object rotates, the bounding ball does not need to be updated. When the geometric object undergoes frequent rotational motion, using the bounding ball may get good results; when the object deforms , its bounding sphere needs to be recalculated. But its tightness is relatively poor, so it is rarely used.
The simplicity of OBB is worse than the above two bounding boxes, but its compactness is better and can greatly reduce the number of bounding boxes participating in the intersection test, so the overall performance is better than AABB and bounding balls. When the geometric object rotates, just perform the same rotation on the OBB. Therefore, for collision detection between rigid bodies, OBB is a better choice, but so far, there is no effective method that can better solve the problem of updating the OBB tree after the object is deformed, and recalculate each node. The cost of OBB is too high, so OBB is not suitable for complex environments containing software objects.
FDH has the best compactness compared to the above three bounding boxes, and its intersection test algorithm is much simpler than OBB. Can be used for collision detection of soft objects.
2. PCA-based bounding box implementation principle
The calculation process of the minimum bounding box is roughly as follows:
1. Use the PCA principal component analysis method to obtain the three main directions of the point cloud, obtain the centroid, calculate the covariance, obtain the covariance matrix, and obtain the eigenvalues and specialty vectors of the covariance matrix. The eigenvector is the main direction.
2. Use the main direction and center of mass obtained in step 1 to convert the input point cloud to the origin, and return the main direction to the direction of the coordinate system to establish a bounding box of the point cloud transformed to the origin.
3. Set the main direction and bounding box for the input point cloud, and implement it through the inverse transformation of the input point cloud to the origin point cloud.
The process of calculating the minimum bounding box vertices is roughly as follows:
1. After converting the input point cloud to a far point, obtain the maximum and minimum x, y, and z-axis coordinates of the converted point cloud. At this time, (max.x, max.y, max.z), (max.x, min.y,max.z),(max.x,max.y,min.z),(min.x,max.y,max.z),(min.x,max.y,min.z) ,(min.x,min.y,max.z),(min.x,min.y,max.z),(min.x,min.y,min.z)
It is the bounding box of the transformed point cloud, and it is also the changed coordinates of the vertex coordinates of the bounding box of the original input point cloud.
2. Inversely transform the six bounding box coordinates obtained above back to the coordinate system of the input point cloud, that is, obtain the bounding box vertex coordinates of the original input point cloud.
3. Code implementation
Calculate AABB bounding box
void AABB(pcl::PointCloud<pcl::PointXYZ>::Ptr cloud)
{
<!-- -->
\t
pcl::MomentOfInertiaEstimation <pcl::PointXYZ> feature_extractor;
feature_extractor.setInputCloud(cloud);
feature_extractor.compute();
std::vector <float> moment_of_inertia;
std::vector <float> eccentricity;
pcl::PointXYZ min_point_AABB;//AABB bounding box
pcl::PointXYZ max_point_AABB;
Eigen::Vector3f major_vector, middle_vector, minor_vector;
Eigen::Vector3f mass_center;
feature_extractor.getMomentOfInertia(moment_of_inertia);
feature_extractor.getEccentricity(eccentricity);
feature_extractor.getAABB(min_point_AABB, max_point_AABB);
feature_extractor.getEigenVectors(major_vector, middle_vector, minor_vector);
feature_extractor.getMassCenter(mass_center);
//Draw AABB bounding box
pcl::visualization