img
Question:
Published on: 29 March, 2024

Liang-Barsky Line Clipping Algorithm

Answer:

Liang and Barsky have established an algorithm that uses floating-point arithmetic but finds the appropriate endpoints with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.

Mid Point Subdivision Line Clipping Algorithm

Let P(x1, y1), Q(x2, y2) is the line which we want to study. The parametric equation of the line segment from gives x-values and y-values for every point in terms of a parameter that ranges from 0 to 1. The equations are

x=x1+(x2-x1 )*t=x1+dx*t and y=y1+(y2-y1 )*t=y1+dy*t

We can see that when t = 0, the point computed is P(x1, y1); and when t = 1, the point computed is Q(x2, y2).

Algorithm of Liang-Barsky Line Clipping:

1. Set tmin=0 and tmax=1

2. Calculate the values tL,tR,tT and tB(tvalues).
      If t<tmin or t<tmax? ignore it and go to the next edge
      Otherwise classify the tvalue as entering or exiting value (using inner product to classify)
      If t is entering value set tmin=t if t is exiting value set tmax=t.</t</t

3. If tmin< tmax? then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax?, y1 + dy*tmax? )

4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax? , y1 + dy*tmax?) are intersection between line and edge.

Random questions