代码之家 › 专栏 › 技术社区 › devuxer

C中线段与轴对齐框的交点#

3d c#

devuxer · 技术社区 · 14 年前

我正在寻找一个算法,确定直线段和轴对齐框之间的近交点和远交点。

public static Point3D[] IntersectionOfLineSegmentWithAxisAlignedBox(
    Point3D rayBegin, Point3D rayEnd, Point3D boxCenter, Size3D boxSize)

如果线段与长方体不相交,则该方法应返回空值 Point3D 数组。

从我的研究到目前为止,我遇到了一些具有高度优化的算法的研究论文,但是它们似乎都是用C++编写的,并且需要多个长类文件转换为C类。就我的目的而言,一些合理有效的,容易理解的人谁得到点积和交叉积,简单/简短的将是首选。

2 回复 | 直到 14 年前

devuxer 14 年前

以下是我最终使用的:

public static List<Point3D> IntersectionOfLineSegmentWithAxisAlignedBox(
    Point3D segmentBegin, Point3D segmentEnd, Point3D boxCenter, Size3D boxSize)
{
    var beginToEnd = segmentEnd - segmentBegin;
    var minToMax = new Vector3D(boxSize.X, boxSize.Y, boxSize.Z);
    var min = boxCenter - minToMax / 2;
    var max = boxCenter + minToMax / 2;
    var beginToMin = min - segmentBegin;
    var beginToMax = max - segmentBegin;
    var tNear = double.MinValue;
    var tFar = double.MaxValue;
    var intersections = new List<Point3D>();
    foreach (Axis axis in Enum.GetValues(typeof(Axis)))
    {
        if (beginToEnd.GetCoordinate(axis) == 0) // parallel
        {
            if (beginToMin.GetCoordinate(axis) > 0 || beginToMax.GetCoordinate(axis) < 0)
                return intersections; // segment is not between planes
        }
        else
        {
            var t1 = beginToMin.GetCoordinate(axis) / beginToEnd.GetCoordinate(axis);
            var t2 = beginToMax.GetCoordinate(axis) / beginToEnd.GetCoordinate(axis);
            var tMin = Math.Min(t1, t2);
            var tMax = Math.Max(t1, t2);
            if (tMin > tNear) tNear = tMin;
            if (tMax < tFar) tFar = tMax;
            if (tNear > tFar || tFar < 0) return intersections;

        }
    }
    if (tNear >= 0 && tNear <= 1) intersections.Add(segmentBegin + beginToEnd * tNear);
    if (tFar >= 0 && tFar <= 1) intersections.Add(segmentBegin + beginToEnd * tFar);
    return intersections;
}

public enum Axis
{
    X,
    Y,
    Z
}

public static double GetCoordinate(this Point3D point, Axis axis)
{
    switch (axis)
    {
        case Axis.X:
            return point.X;
        case Axis.Y:
            return point.Y;
        case Axis.Z:
            return point.Z;
        default:
            throw new ArgumentException();
    }
}

public static double GetCoordinate(this Vector3D vector, Axis axis)
{
    switch (axis)
    {
        case Axis.X:
            return vector.X;
        case Axis.Y:
            return vector.Y;
        case Axis.Z:
            return vector.Z;
        default:
            throw new ArgumentException();
    }
}

Archie 14 年前

对于轴对齐的长方体,它非常简单:必须找到光线与6个平面(由长方体面定义)的交点,然后根据长方体顶点坐标限制检查找到的点。

Greg Kramida 5 年前

这是另一个高效而优雅的解决方案。

它是用C++编写的,但它可以简单地翻译为Python(每个线程到其他线程的每个线程)或C(每个原始PO)。这里假设可以访问3D向量类/结构 Vector3f ,定义了基本代数运算/运算符。在C++中,类似于 Eigen::Vector3f NumPy array 可以使用;在C#中 Vector3

使用简单的基于端点的构造函数定义段类:

class Segment {
public:
    Segment(const Vector3f& startPoint, const Vector3f& endPoint) :
            origin(startPoint), direction(endPoint - startPoint),
            inverseDirection(Vector3f(1.0) / direction),
            sign{(inverseDirection.x < 0),(inverseDirection.y < 0),(inverseDirection.z < 0)}
            {}

    float length(){
        return sqrtf(direction.x * direction.x + direction.y * direction.y +
                     direction.z * direction.z);
    }
    Vector3f origin, endpoint, direction;
    Vector3f inverseDirection;
    int sign[3];
};

执行检查的实际例程:

bool SegmentIntersectsGridAlignedBox3D(Segment segment, Vector3f boxMin, Vector3f boxMax){
    float tmin, tmax, tymin, tymax, tzmin, tzmax;
    Vector3f bounds[] = {boxMin, boxMax};

    tmin = (bounds[segment.sign[0]].x - segment.origin.x) * segment.inverseDirection.x;
    tmax = (bounds[1 - segment.sign[0]].x - segment.origin.x) * segment.inverseDirection.x;
    tymin = (bounds[segment.sign[1]].y - segment.origin.y) * segment.inverseDirection.y;
    tymax = (bounds[1 - segment.sign[1]].y - segment.origin.y) * segment.inverseDirection.y;

    if ((tmin > tymax) || (tymin > tmax)){
        return false;
    }
    if (tymin > tmin) {
        tmin = tymin;
    }
    if (tymax < tmax){
        tmax = tymax;
    }

    tzmin = (bounds[segment.sign[2]].z - segment.origin.z) * segment.inverseDirection.z;
    tzmax = (bounds[1 - segment.sign[2]].z - segment.origin.z) * segment.inverseDirection.z;

    if ((tmin > tzmax) || (tzmin > tmax)){
        return false;
    }
    if (tzmin > tmin){
        tmin = tzmin;
    }
    if (tzmax < tmax){
        tmax = tzmax;
    }
    // this last check is different from the 'ray' case in below references: 
    // we need to check that the segment is on the span of the line
    // that intersects the box
    return !(tmax < 0.0f || tmin > 1.0f); 
}

这个答案主要归功于scratchpixel.com和 this tutorial ,基于:

link

您可以在本教程中找到非常详细的代码解释。

我所做的只是稍微修改代码,以解决沿光线的线段问题,而不是光线相交的问题。