CODEWITHSUNDEEP
java3dgeometryraytracing
user17364069
user17364069

Reputation:

How to check if a line lies between a prism

If I have 2 points in 3d space how can I determine if a rectangular prism lies between those 2 points? Also the only information I have about the the rectangular prism is its min and max x, y, and z value. I know I could iterate down the line between those 2 points checking to see if that point is within the rectangular prism but that seems very resource heavy. What I really need is a way to check if a line segment intersects the prism but I am not sure how to do that any ideas?

I found these two resources that seem similar to my question https://math.stackexchange.com/questions/2134505/how-to-check-if-an-infinite-line-intersects-a-rectangular-prism-in-3d-space

How to check if an infinite line intersects a rectangular prism in 3d space?

Looking at that bottom link it just simply says to find parameters t that intersects the rectangular prism which is obvious but the problem is I dont know how to do that any thoughts?

Upvotes: 1

Views: 110

Answers (2)

MBo
MBo

Reputation: 80072

Let line segment is defined by two points (X1, Y1) and (X2, Y2). Let box is defined by ranges xmin..xmax, ymin..ymax, zmin..zmax.

We can write parametric eqiation for line segment, where t is in range 0..1:

X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2 - Y1)
Z = Z1 + t * (Z2 - Z1)

Box has 6 facets. Let the first one is at xmin. We can substitute xmin in the first equation and find parameter t where line intersects this facet.

xmin = X1 + t1 * (X2 - X1)
t1 = (xmin - X1) / (X2 - X1)

Now check that t1 is in range 0..1. If yes, substitute this t1 value in the second and third equations

Y = Y1 + t1 * (Y2 - Y1)
Z = Z1 + t1 * (Z2 - Z1)

and check that resulting Y and Z lie in ranges ymin..ymax and zmin..zmax respectively.
If yes - line segment does intersect the box

If no, repeat for other faces xmax, ymin and so on.

P.S. Also you can consider special case when line segment is fully inside the box (just check if X1,Y1,Z1 is in box range)

P.P.S. When line is parallel to some coordinate plane, don't check intersections with corresponding faces (for example, if X2-X1==0, you cannot divide by zero, but you just don't need check xmin and xmax faces)

Quick-made Python-like pseudocode for reference:

def DoesSegmentIntersectBox(x1,y1,z1,x2,y2,z2,xmin,xmax,yin,ymax,zmin,zmax):
    if zmin<=z1<=zmax and ymin<=y1<=ymax and xmin<=x1<=xmax:
        return True  #end inside the box

    if (x2-x1):
        t = (xmin-x1) / (x2-x1)
        if 0<=t<=1:    #line intersects plane in segment range
            y = y1+t*(y2-y1)
            if ymin<=y<=ymax:    #segment intersects face in y range
                z = z1+t*(z2-z1)
                if zmin<=z<=zmax:   #segment intersects face in z range
                    return True     #segment does intersect face xmin
        t = (xmax-x1) / (x2-x1)
            #same 6 lines

    if (y2-y1):
        t = (ymin-y1) / (y2-y1)
        if 0<=t<=1:
            x = x1+t*(x2-x1)
            if xmin<=x<=xmax:
                z = z1+t*(z2-z1)
                if zmin<=z<=zmax:
                    return True
        t = (ymax-y1) / (y2-y1)
            #same 6 lines

    if (z2-z1):
        t = (zmin-z1) / (z2-z1)
        if 0<=t<=1:
            x = x1+t*(x2-x1)
            if xmin<=x<=xmax:
                y = y1+t*(y2-y1)
                if ymin<=y<=ymax:
                    return True
        t = (zmax-z1) / (z2-z1)
            #same 6 lines

    return False

Upvotes: 0

jojo_Aero_smith_the_dummy
jojo_Aero_smith_the_dummy

Reputation: 375

project your line points and prism edges onto 2D plane that is perpendicular to your line. enter image description here On the 2D plane, the two points of line will be just one point and prism edges is just a bunch of connected vertices forming a closed region. check if the one point is within the closed region, this will be easy to do for 2D.

If your point is within then the line intersects the prism in 3D, if not then no.

now there is a case where it is a line segment where the two ends don't touch the prism. In this case you just check point to prism surface distance, there is a equation for that.

Upvotes: 1

Related Questions