计算机图形学——Liang-Barsky资料.ppt

Liang-Barsky 裁剪算法 Contents 算法思想 例题演示 Contents 1 Contents 2 算法思想 一条两端点为P1(x0,y0)、P2(x1,y1)的线段用参数方程表示为： x=x0+u(x1-x0)=x0+u?x y=y0+u(y1-y0)=y0+u?y；其中，0≤u ≤1 线段的参数方程与点裁剪条件结合，得到不等式 xmin≤x0+u?x≤xmax ymin≤y0+u?y≤ymax 算法思想 用upK≤qK(k=1,2,3,4)表示上式，则参数p、q定义为： p1=-?x, q1=x0-xmin p2=?x, q2=xmax-x0 p3=-?y, q3=y0-ymin p4=?y, q4=ymax-y0 算法思想 根据pk的值判断线段的方向： pk=0 线段平行于裁剪边界 qk0 线段完全位于边界外 qk≥0 线段位于平行边界内 pk0 线段从裁剪边界延长线的外到内 pk0 反之 算法思想 pk≠0时，计算线段与边界k延长线的交点u值： 对每条直线，计算u1和u2。 算法思想 u1----线段从外到内遇到的矩形边界决定（p0） 计算rk=qk/pk u1=max{0,r} u2----线段从内到外遇到的矩形边界决定（p0） 计算rk=qk/pk u2=min{r，1} 算法思想 若u1u2，线段完全在裁剪窗口外； 否则，由参数u1和u2计算出裁剪后的线段端点 例题演示 F1(1,-2) F2(6,3) (8,4) (0,0) y x Step1： 写出参数方程，计算?x和?y。 x=x0+u?x y=y0+u?y ?x=5 ?y=5 例题演示 Step2：计算pk、qk和rk的值，并确定u1、u2的值。 p1=-?x=-5, q1=x0-xmin=1， r1=q1/p1=-1/5 p2=?x=5, q2=xmax-x0=7， r2=q2/p2=7/5 p3=-?y=-5, q3=y0-ymin=-2， r3=q3/p3=2/5 p4=?y=5, q4=ymax-y0=6， r4=q4/p4=6/5 例题演示 将上面的计算列入表格： 故： u1=max{0,-1/5,2/5}=2/5 u2=min{1,7/5,6/5}=1 Edge pk qk rk Left -5 1 -1/5 Right 5 7 7/5 Bottom -5 -2 2/5 Top 5 6 6/5