检测立方体和圆锥体是否相交？

Question

考虑3D中的两个几何对象：

• 与轴对齐并由其中心位置和范围（边长）定义的立方体
• 不与轴对齐的圆锥体，由其顶点的位置、底面的中心位置和顶点的半角来定义

这里是一个小代码，用于定义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;
};

我想写一个函数来检测立方体和圆锥体的交集是否为空：

^{pr2}$

以下是问题的说明（图示是二维的，但我的问题是三维的）：

<>如何高效地执行（我正在寻找一个算法，所以答案可以是C、C++或Python）？在

注意：这里的交集定义为：它存在于立方体和圆锥体中的非空三维体积（如果立方体在圆锥体内，或者如果圆锥体在立方体内，它们相交）。在

Answer 1

信息：我不知道这个想法是否已经是一个专利知识产权（在你的地区），或不是，或如何找到，或其他什么意思。我这样做是为了好玩。：）

但是，这是牛肉：

• 第1步：近似：为了提高效率，将两个对象都视为球体（使用外层球体）。计算它们的distance（在它们的两个中心点之间），以确定它们是否足够接近以相交。如果它们不可能相交（因为它们的距离大于两个球体的半径之和），则快速返回false。

• 第2步：精确计算：这是一种简单的方法：将圆锥体解释为一批称为voxels（或legos）的三维像素：选择您认为可以接受的任何分辨率（粒度）（可能为0.01）。创建一个向量，从（0,0,0）指向圆锥体体积内的任何体素点（从已命名为“顶点”的点开始）。如果给定立方体中存在该体素的坐标，则返回true。根据所选的粒度，对每个可以为圆锥体对象计算的体素重复此操作。

• 步骤3：如果没有匹配项，则返回false。

优化：通过考虑立方体的内部球体，确定是否有任何给定的三维点在立方体内部的函数可能是可优化的。也就是说，任何给定的三维点都在立方体内，如果它离立方体内部球体的中心足够近，就在这个球体内。乐趣开始了，当你开始用额外的球体填充空的立方体角落以获得更多的优化（这是完全可选的）。在

我相信第二步还有进一步的优化。然而，这种方法的好处是可以自由地调整粒度，在计算时间和计算精度之间进行微调。在

还可以创建一个解算器，该解算器在多次迭代中自动降低粒度。这意味着精度会随着时间的推移而提高（以获得更好的分辨率）。在

Answer 2

为了规范

这个答案会比你的问题略为笼统（例如，我考虑的是一个长方体而不是一个立方体）。适应你的情况应该很简单。在

一些定义

/*
    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开始：

^{pr2}$

直角圆锥交点

现在，我们可以检查平面的矩形部分是否与圆锥体相交（这将用于检查立方体的一个面是否与圆锥体相交）。还在圆锥空间里。这项计划以一种有助于我们的方式通过：两个矢量和一个点。为了简化计算，向量没有被规范化。在

/*
    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;
}

箱锥交点

现在，最后一部分：整个立方体：

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]);
}

为了数学

仍然在圆锥体空间中，圆锥体方程为：

// 0 is the base, the vertex is at z = H
x² + y² = (H - z)² * tan²(alpha)
0 <= z <= H

现在，三维中直线的参数方程为：

x = u + at
y = v + bt
z = w + ct

方向向量是（a，b，c），点（u，v，w）在直线上。在

现在，让我们把这些方程组合起来：

(u + at)² + (v + bt)² = (H - w - ct)² * tan²(alpha)

然后，对该方程进行展开和重分解后，得到如下结果：

At² + Bt + C = 0

其中A、B和C显示在第一个交集函数中。只需解决这个问题并检查z和t上的边界条件

Answer 3

1. 想象2条无限线

   • 圆锥轴
   • 穿过垂直于圆锥轴的点P（起始点为立方体中心）的直线。在

   圆锥轴是已知的，所以很容易，第二条直线定义为

   P+t*(perpendicular vector to cone axis)
   

   这个向量可以通过锥轴向量和垂直于图像的向量（假设Z轴）的乘积来获得。t是标量值参数。。。

2. 计算这两条线/轴的交集

   如果你不知道这些方程，就推导它们或者搜索它们。设交点为Q

3. 如果交点Q不在圆锥内

   （在顶点和底之间）则点P不是与圆锥体相交。从交集方程中，您将获得参数t1和t2

   • 设t1为P轴线
   • 圆锥轴线为t2

   如果轴线方向向量也是圆锥体的长度，则交点在圆锥体内如果t2 = <0,1>

4. 如果P不在三角形内（由这两个轴生成的切锥到平面）

   这也很容易知道Q在圆锥（t2）内的位置，所以你知道圆锥在P-轴上，从Q到{}的距离，其中R是圆锥体的底半径。所以你可以计算|P-Q|并检查它是否是<=R*t2，或者直接使用t1（如果P轴方向向量是单位）。在

   如果距离较大，则R*t2点P不与圆锥体相交。

5. 如果#3和#4为正，则P与圆锥体相交

   

   • 希望你不介意这里是你的形象，为清晰起见添加了一些东西

[注意事项]

现在最困难的是，当立方体的顶点不与圆锥体相交，而立方体本身却与圆锥体相交时，存在边的情况。当||P-Q|-R*t2| = <0,half cube size>在这种情况下，你应该检查更多的点，而不是沿着最近的立方体面立方体顶点。在

另一种方法是：

1. 为圆锥体创建变换矩阵

   其中：

   • 它的顶点作为原点
   • 其轴为+Z轴
   • 并且XY平面与其基底平行

   所以任何一个点都在圆锥内，如果

   • Z = <0,h>
   • X*X + Y*Y <= (R*Z/h)^2或{}

2. 将空间转换为

   检查是否有顶点在圆锥体内，你也可以用#1（代数）的条件检查所有立方体的边线，或者像前面的方法那样沿着立方体面使用更多的点。

聊天讨论：http://chat.stackoverflow.com/rooms/48756/discussion-between-spektre-and-joojaa