CODEWITHSUNDEEP
mathclipping
MHOOO
MHOOO

Reputation: 643

How do I clip a line segment against a frustum?

Given two vectors A and B which form the line segment L = A-B. Furthermore given a view frustum F which is defined by its left, right, bottom, top, near and far planes.

How do I clip L against F?

That is, test for an intersection and where on L that intersection occurs? (Keep in mind that a line segment can have more than one intersection with the frustum if it intersects two sides at a corner.)

If possible, provide a code example please (C++ or Python preferred).

Upvotes: 5

Views: 4845

Answers (3)

ideasman42
ideasman42

Reputation: 48058

First extract the planes from your view matrix.

Then use your points to define a vector and min/max as (0, 1), then iterate over the planes and intersect them with the segment, updating the min/max, bailing out early if the min > max.

Here's an example of a pure Python function, no external deps.

def clip_segment_v3_plane_n(p1, p2, planes):
    """
    - p1, p2: pair of 3d vectors defining a line segment.
    - planes: a sequence of (4 floats): `(x, y, z, d)`.

    Returns 2 vector triplets (the clipped segment)
    or (None, None) then segment is entirely outside.
    """
    dp = sub_v3v3(p2, p1)

    p1_fac = 0.0
    p2_fac = 1.0

    for p in planes:
        div = dot_v3v3(p, dp)
        if div != 0.0:
            t = -plane_point_side_v3(p, p1)
            if div > 0.0:  # clip p1 lower bounds
                if t >= div:
                    return None, None
                if t > 0.0:
                    fac = (t / div)
                    if fac > p1_fac:
                        p1_fac = fac
                        if p1_fac > p2_fac:
                            return None, None
            elif div < 0.0:  # clip p2 upper bounds
                if t > 0.0:
                    return None, None
                if t > div:
                    fac = (t / div)
                    if fac < p2_fac:
                        p2_fac = fac
                        if p1_fac > p2_fac:
                            return None, None

    p1_clip = add_v3v3(p1, mul_v3_fl(dp, p1_fac))
    p2_clip = add_v3v3(p1, mul_v3_fl(dp, p2_fac))

    return p1_clip, p2_clip


# inline math library
def add_v3v3(v0, v1):
    return (
        v0[0] + v1[0],
        v0[1] + v1[1],
        v0[2] + v1[2],
        )

def sub_v3v3(v0, v1):
    return (
        v0[0] - v1[0],
        v0[1] - v1[1],
        v0[2] - v1[2],
        )

def dot_v3v3(v0, v1):
    return (
        (v0[0] * v1[0]) +
        (v0[1] * v1[1]) +
        (v0[2] * v1[2])
        )

def mul_v3_fl(v0, f):
    return (
        v0[0] * f,
        v0[1] * f,
        v0[2] * f,
        )

def plane_point_side_v3(p, v):
    return dot_v3v3(p, v) + p[3]

Upvotes: 1

jasonmray
jasonmray

Reputation: 2378

Adding to what Corporal Touchy said above, you'll need to know how to intersect a line segment with a plane. In the description on that page, u represents the parameter in the parametric definition of your line. First, calculate u using one of the 2 methods described. If the value of u falls in the range of 0.0 to 1.0, then the plane clips the line somewhere on your segment. Plugging u back into your line equation gives you the point where that intersection occurs.

Another approach is to find the directed distance of each point to a plane. If the distance of one point is positive and the other is negative, then they lie on opposite sides of the plane. You then know which point is outside your frustum (based on which way your plane normal points). Using this approach, finding the intersection point can be done faster by doing a linear interpolation based on the ratio of the directed distances. E.g. if the distance of one point is +12 and the other is -12, you know the plane cuts the segment in half, and your u parameter is 0.5.

Hope this helps.

Upvotes: 0

Sarien
Sarien

Reputation: 6972

I don't want to get into writing code for this now but if I understand "frustum" correctly the following should work.

  1. Intersect the Line with all given planes
  2. If you have two intersections you're done.
  3. If you have only one intersection calculate the front plane and intersect.
  4. If you still have only one intersection calculate the back plane and intersect.

But I may have completely misunderstood. In that case please elaborate :)

Upvotes: 4

Related Questions