How to cut a line segment against truncation?

Question

For two vectors A and B , which form a line segment L = AB. In addition, taking into account the type of fustum F , which is determined by its left, right, lower, upper, near and far planes.

How to copy L to F ?

That is, check the intersection and where does the intersection occur on L? (Keep in mind that a line segment can have more than one intersection with a truncation if it intersects two sides in a corner.)

If possible, provide sample code (preferably C ++ or Python).

Answer 1

I do not want to write code for this now, but if I understand "truncation" correctly, this should work.

• Cross Line with all given planes
• If you have two intersections, you are done.
• If you have only one intersection, calculate the front plane and intersect.
• If you still have only one intersection, calculate the back plane and intersect.

But I may have completely misunderstood. In this case, please specify :)

Answer 2

Adding to what Corporal Tatti said above, you need to know how to cross a line segment with a plane . In the description on this page, u represents the parameter in the parametric definition of your line. First calculate u using one of the two methods described. If the u value falls in the range from 0.0 to 1.0, then the plane pinches the line somewhere on your segment. Including u back in your linear equation gives you the point at which this intersection occurs.

Another approach is to find the directional distance of each point to the plane. If the distance of one point is positive and the other negative, then they lie on opposite sides of the plane. Then you know which point is outside of your truncation (based on how your normal points on the plane). Using this approach, the intersection point can be found faster by performing linear interpolation based on the ratio of the directed distances. For instance. if the distance of one point is +12 and the other is -12, you know that the plane cuts the segment in half, and your parameter u is 0.5.

Hope this helps.

Answer 3

First, get the planes out of your view matrix .

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

Here is an example of a pure Python function, no external fingerprints.

 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]