检测立方体和圆锥体是否相交? [英] Detect if a cube and a cone intersect each other?
问题描述
考虑两个 3D 几何对象:
Consider two geometrical objects in 3D:
- 一个与轴对齐并由其中心位置和范围(边长)定义的立方体
- 一个不与轴对齐并由其顶点位置、底中心位置和顶点处的半角定义的圆锥体
下面是一段用 C++ 定义这些对象的小代码:
Here is a small code to define these objects in C++:
// Preprocessor
#include <iostream>
#include <cmath>
#include <array>
// 3D cube from the position of its center and the side extent
class cube
{
public:
cube(const std::array<double, 3>& pos, const double ext)
: _position(pos), _extent(ext)
{;}
double center(const unsigned int idim)
{return _position[idim];}
double min(const unsigned int idim)
{return _position[idim]-_extent/2;}
double max(const unsigned int idim)
{return _position[idim]+_extent/2;}
double extent()
{return _extent;}
double volume()
{return std::pow(_extent, 3);}
protected:
std::array<double, 3> _position;
double _extent;
};
// 3d cone from the position of its vertex, the base center, and the angle
class cone
{
public:
cone(const std::array<double, 3>& vert,
const std::array<double, 3>& bas,
const double ang)
: _vertex(vert), _base(bas), _angle(ang)
{;}
double vertex(const unsigned int idim)
{return _vertex[idim];}
double base(const unsigned int idim)
{return _base[idim];}
double angle()
{return _angle;}
double height()
{return std::sqrt(std::pow(_vertex[0]-_base[0], 2)+std::pow(
_vertex[1]-_base[1], 2)+std::pow(_vertex[2]-_base[2], 2));}
double radius()
{return std::tan(_angle)*height();}
double circle()
{return 4*std::atan(1)*std::pow(radius(), 2);}
double volume()
{return circle()*height()/3;}
protected:
std::array<double, 3> _vertex;
std::array<double, 3> _base;
double _angle;
};
我想写一个函数来检测一个立方体和一个圆锥体的交集是否为空:
I would like to write a function to detect whether the intersection of a cube and a cone is empty or not:
// Detect whether the intersection between a 3d cube and a 3d cone is not null
bool intersection(const cube& x, const cone& y)
{
// Function that returns false if the intersection of x and y is empty
// and true otherwise
}
这是问题的说明(说明是 2D 的，但我的问题是 3D 的):
Here is an illustration of the problem (the illustration is in 2D, but my problem is in 3D):
如何有效地做到这一点(我正在寻找一种算法，所以答案可以是 C、C++ 或 Python)?
How to do that efficiently (I am searching for an algorithm, so the answer can be in C, C++ or Python) ?
注意:这里的交集定义为:在立方体和圆锥体中存在一个非空的3D体积(如果立方体在圆锥体内，或者如果圆锥体在立方体内部，它们相交).
Note: Here intersection is defined as: it exists a non-null 3D volume that is in the cube and in the cone (if the cube is inside the cone, or if the cone is inside the cube, they intersect).
推荐答案
对于代码
这个答案将比您的问题更笼统(例如，我考虑的是一个盒子而不是一个立方体).适应您的情况应该非常简单.
For the code
This answer will be slightly more general than your problem (I consider a box instead of a cube for example). Adapting to your case should be really straightforward.
/*
Here is the cone in cone space:
+ ^
/| |
/*| | H
/ | |
/ |
+---------+ v
* = alpha (angle from edge to axis)
*/
struct Cone // In cone space (important)
{
double H;
double alpha;
};
/*
A 3d plane
v
^----------+
| |
| |
+----------> u
P
*/
struct Plane
{
double u;
double v;
Vector3D P;
};
// Now, a box.
// It is assumed that the values are coherent (that's only for this answer).
// On each plane, the coordinates are between 0 and 1 to be inside the face.
struct Box
{
Plane faces[6];
};
线-锥交点
现在，让我们计算一个线段和我们的锥体之间的交集.请注意，我将在锥空间中进行计算.另请注意，我将 Z 轴设为垂直轴.将其更改为 Y 留给读者作为练习.假定该线位于锥体空间中.线段方向未归一化；相反，该段具有方向向量的长度，并从点 P 开始:
/*
The segment is points M where PM = P + t * dir, and 0 <= t <= 1
For the cone, we have 0 <= Z <= cone.H
*/
bool intersect(Cone cone, Vector3D dir, Vector3D P)
{
// Beware, indigest formulaes !
double sqTA = tan(cone.alpha) * tan(cone.alpha);
double A = dir.X * dir.X + dir.Y * dir.Y - dir.Z * dir.Z * sqTA;
double B = 2 * P.X * dir.X +2 * P.Y * dir.Y - 2 * (cone.H - P.Z) * dir.Z * sqTA;
double C = P.X * P.X + P.Y * P.Y - (cone.H - P.Z) * (cone.H - P.Z) * sqTA;
// Now, we solve the polynom At² + Bt + C = 0
double delta = B * B - 4 * A * C;
if(delta < 0)
return false; // No intersection between the cone and the line
else if(A != 0)
{
// Check the two solutions (there might be only one, but that does not change a lot of things)
double t1 = (-B + sqrt(delta)) / (2 * A);
double z1 = P.Z + t1 * dir.Z;
bool t1_intersect = (t1 >= 0 && t1 <= 1 && z1 >= 0 && z1 <= cone.H);
double t2 = (-B - sqrt(delta)) / (2 * A);
double z2 = P.Z + t2 * dir.Z;
bool t2_intersect = (t2 >= 0 && t2 <= 1 && z2 >= 0 && z2 <= cone.H);
return t1_intersect || t2_intersect;
}
else if(B != 0)
{
double t = -C / B;
double z = P.Z + t * dir.Z;
return t >= 0 && t <= 1 && z >= 0 && z <= cone.H;
}
else return C == 0;
}
矩形 - 圆锥交点
现在，我们可以检查平面的矩形部分是否与锥体相交(这将用于检查立方体的面是否与锥体相交).还在锥体空间.该计划以一种对我们有帮助的方式通过:2 个向量和一个点.向量未归一化，以简化计算.
Rect - cone intersection
Now, we can check whether a rectangular part of a plan intersect the cone (this will be used to check whether a face of the cube intersects the cone). Still in cone space. The plan is passed in a way that will help us: 2 vectors and a point. The vectors are not normalized, to simplify the computations.
/*
A point M in the plan 'rect' is defined by:
M = rect.P + a * rect.u + b * rect.v, where (a, b) are in [0;1]²
*/
bool intersect(Cone cone, Plane rect)
{
bool intersection = intersect(cone, rect.u, rect.P)
|| intersect(cone, rect.u, rect.P + rect.v)
|| intersect(cone, rect.v, rect.P)
|| intersect(cone, rect.v, rect.P + rect.u);
if(!intersection)
{
// It is possible that either the part of the plan lie
// entirely in the cone, or the inverse. We need to check.
Vector3D center = P + (u + v) / 2;
// Is the face inside the cone (<=> center is inside the cone) ?
if(center.Z >= 0 && center.Z <= cone.H)
{
double r = (H - center.Z) * tan(cone.alpha);
if(center.X * center.X + center.Y * center.Y <= r)
intersection = true;
}
// Is the cone inside the face (this one is more tricky) ?
// It can be resolved by finding whether the axis of the cone crosses the face.
// First, find the plane coefficient (descartes equation)
Vector3D n = rect.u.crossProduct(rect.v);
double d = -(rect.P.X * n.X + rect.P.Y * n.Y + rect.P.Z * n.Z);
// Now, being in the face (ie, coordinates in (u, v) are between 0 and 1)
// can be verified through scalar product
if(n.Z != 0)
{
Vector3D M(0, 0, -d/n.Z);
Vector3D MP = M - rect.P;
if(MP.scalar(rect.u) >= 0
|| MP.scalar(rect.u) <= 1
|| MP.scalar(rect.v) >= 0
|| MP.scalar(rect.v) <= 1)
intersection = true;
}
}
return intersection;
}
盒子 - 圆锥交点
现在，最后一部分:整个立方体:
Box - cone intersection
Now, the final part : the whole cube:
bool intersect(Cone cone, Box box)
{
return intersect(cone, box.faces[0])
|| intersect(cone, box.faces[1])
|| intersect(cone, box.faces[2])
|| intersect(cone, box.faces[3])
|| intersect(cone, box.faces[4])
|| intersect(cone, box.faces[5]);
}
对于数学
仍然在锥空间中，锥方程为:
For the maths
Still in cone space, the cone equations are:
// 0 is the base, the vertex is at z = H
x² + y² = (H - z)² * tan²(alpha)
0 <= z <= H
现在，3D 中直线的参数方程为:
Now, the parametric equation of a line in 3D is:
x = u + at
y = v + bt
z = w + ct
方向向量为(a, b, c)，点(u, v, w)位于直线上.
The direction vector is (a, b, c), and the point (u, v, w) lie on the line.
现在，让我们把方程式放在一起:
Now, let's put the equations together:
(u + at)² + (v + bt)² = (H - w - ct)² * tan²(alpha)
然后在开发和重新分解这个等式之后，我们得到以下内容:
Then after developping and re-factorizing this equation, we get the following:
At² + Bt + C = 0
其中 A、B 和 C 显示在第一个交集函数中.只需解决这个问题并检查 z 和 t 的边界条件.
where A, B and C are shown in the first intersection function. Simply resolve this and check the boundary conditions on z and t.
这篇关于检测立方体和圆锥体是否相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
