浏览量:167

5.3. 对线性对象的裁剪

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

5.3. 对线性对象的裁剪

5.3.1. 裁剪算法综述

问题描述:求矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)对线段\({{P}_{0}}{{P}_{1}}\)的裁剪。

2015-3-23 13-37-26

图5.5 线段的端点坐标沿着矩形的两条轴的投影

Cyrus-Beck算法解决了凸多边形或者凸多面体对象对线性对象的裁剪,矩形也是一个凸多边形,同样适用。在图形学中,有一个经典的问题,就是矩形窗口对线段的裁剪,即二维平面上轴对齐的矩形对线段的裁剪问题。对于非轴对齐的矩形的裁剪,可以把线段坐标按矩形的两条互相垂直的轴作投影,把矩形转化为轴对齐的情况。如图5.5所示,把线段的两个端点\({{P}_{0}}\)和\({{P}_{1}}\)投影到\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\)上,得到新的坐标P0‘和P1‘,投影等式为\( {{P}_{0}}’=\left( ({{P}_{0}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{0}}-C)\cdot {{{\vec{e}}}_{1}} \right),{{P}_{1}}’=\left( ({{P}_{1}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{1}}-C)\cdot {{{\vec{e}}}_{1}} \right)\),问题就转化为求轴对齐的矩形对线段P0‘P1‘的裁剪问题。求出裁剪后的线段Q0‘Q1‘后,再变换成原矩形的坐标,设\({{Q}_{0}}’=({{x}_{0}},{{y}_{0}}),{{Q}_{1}}’=({{x}_{1}},{{y}_{1}})\),则变换等式是\({{Q}_{0}}={{x}_{0}}{{\vec{e}}_{0}}+{{y}_{0}}{{\vec{e}}_{1}}+C,{{Q}_{1}}={{x}_{1}}{{\vec{e}}_{0}}+{{y}_{1}}{{\vec{e}}_{1}}+C\)。下面将重点讨论轴对齐的矩形对线段的裁剪算法。

大致有五种算法,可以解决轴对齐的矩形对线段的裁剪算法。最早由Danny Cohen&Ivan Sutherland提出的一种算法,称为Cohen-Sutherlad裁剪算法(简称CS算法),该算法把平面分成9个区域,根据点的位置确定与矩形的相交边。后来,Cyrus&Beck[1](1978)提出了Cyrus-Beck裁剪算法(简称CB算法),线段用参数方程来表示,计算与矩形的每条边所在的直线的交点,但是该算法的效率相对较低。Liang&Barsky[2](1984)尝试对CS算法进行改进,提出了该算法的一种变种,称为Liang-Barsky裁剪算法(简称为LB算法),Liang和Barsky[3](1992)进一步对LB算法进行了改进。Sobkow&Pospisil&Yang[4](1987)描述了另外一种线段的裁剪算法,称为快速裁剪算法(简称为SPY算法)。Nicholl,Lee&Nicholl[5]对前面四种线段裁剪算法进行了较为深入地分析和比较,并且描述了一种更加高效的算法,称为Nicholl-Lee-Nicholl算法(简称为NLN算法)。对比五种算法的性能,它们并不是在数量级上的差别,只是算法中运算个数的差别,比如NLN算法拥有最少的除法次数。CS、LB和SPY在不同机器、不同的数据集上,会显示出不同的算法性能。在算法实现上,NLN和SPY算法较为复杂,CS和LB相对简单。如果不会特别苛求算法的性能,建议选择CS或者LB算法,接下来将详细地描述这两种算法。

5.3.2. Cohen-Sutherland裁剪算法

设矩形的左侧边为\(x={{x}_{\min }}\),右侧边为\(x={{x}_{\max }}\),下侧边为\(y={{y}_{\min }}\),上侧边为\(y={{y}_{\max }}\)。矩形的四条边所在的直线,把平面分成9个区域,可以用4位的编码来指定点所在的区域,我们可以作如下所规定:

  • 0000       点在矩形区域内;
  • 0001       点在左侧边的左侧;
  • 0010       点在右侧边的右侧;
  • 0100       点在下侧边的下方;
  • 1000       点在上侧边的上方;

2015-3-23 13-37-36

图5.6 区域的编码表示

对于左上侧的区域的编码,就可以用0001 | 1000 = 1001得到,同理可以得到左下区域,右上区域和右下区域的编码,如图5.6所示。给定一个坐标,判断它所在区域的编码的伪码实现,如下所示:

int computeCode( Real x, Real y)
1.    令INSIDE = 0000, LEFT = 0001 , RIGHT = 0010 , BOTTOM = 0100 , TOP = 1000;
2.    code = INSIDE;
3.    if x < xmin, then
4.           code |= LEFT;
5.    else if x > xmax, then
6.           code |= RIGHT;
7.    end if;
8.    if y < ymin, then
9.           code |= BOTTOM;
10.   else y > ymax, then
11.          code |= TOP;
12.   end if;
13.   return code;

设当前线段的两个端点\({{Q}_{0}}\)和\({{Q}_{1}}\)的编码分别是\({{c}_{0}}\)和\({{c}_{1}}\),若\({{c}_{0}}=0000\)且\({{c}_{1}}=0000\),说明线段在矩形区域内;若\(({{c}_{0}}\And {{c}_{1}})\ne 0\),说明线段一定不与矩形区域相交;否则,说明线段与矩形相交,求出线段与矩形边界的交点,线段上一部分可能在矩形内,另一部分一定在矩形外,将在矩形外的部分丢弃。对于保留下的线段,重复这个过程,直至线段的两个端点都在矩形内为止,算法最多循环四次。

2015-3-23 13-37-44

图5.7 沿着矩形边界裁剪线段

 如何计算直线对线段的截断呢?如图5.7所示,显示了线段与矩形的右边界的相交情况,由相似三角形,可得

\[\frac{{y – {y_0}}}{{{y_1} – {y_0}}} = \frac{{{x_{\max }} – {x_0}}}{{{x_1} – {x_0}}} \tag{5.3}\]

则有

\[\left\{ \begin{array}{l}x = {x_{\max }}\\y = {y_0} + \frac{{{x_{\max }} – {x_0}}}{{{x_1} – {x_0}}}({y_1} – {y_0})\end{array} \right. \tag{5.4}\]

同理,可以计算出另外三条边界的相交情况,使用等式(5.4)计算交点时,可以保证两个端点不在同一个区域,因此分母一定不为零。

Cohen-Sutherlad线段裁剪算法的伪码如下所示:

求矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\]对线段\({{P}_{0}}{{P}_{1}}\)的裁剪
1.    令INSIDE = 0000, LEFT = 0001, RIGHT = 0010, BOTTOM = 0100, TOP = 1000;
2.    \({{x}_{0}}=({{P}_{0}}-C)\cdot {{\vec{e}}_{0}},{{y}_{0}}=({{P}_{0}}-C)\cdot {{\vec{e}}_{1}}\);
3.    \({{x}_{1}}=({{P}_{1}}-C)\cdot {{\vec{e}}_{0}},{{y}_{1}}=({{P}_{1}}-C)\cdot {{\vec{e}}_{1}}\);
4.    \({{x}_{\min }}=-{{u}_{0}},{{y}_{\min }}=-{{u}_{1}},{{x}_{\max }}={{u}_{0}},{{y}_{\max }}={{u}_{1}}\);
5.    code0 = computeCode(x0 , y0);
6.    code1 = computeCode(x1 , y1);
7.    accept = true;
8.    while( true )
9.           if !(code0 | code1), then
10.                 break;
11.          else if (code0 & code1), then
12.                 accept = false;
13.                 break;
14.          end if;
15.          code = \(code0\ne 0\)? code0 : code1;
16.          if (code & TOP), then
17.                 \(x={{x}_{0}}+({{x}_{1}}-{{x}_{0}})\cdot ({{y}_{\max }}-{{y}_{0}})/({{y}_{1}}-{{y}_{0}})\);
18.                 \(y={{y}_{\max }}\);
19.          else if (code & BOTTOM), then
20.                 \(x={{x}_{0}}+({{x}_{1}}-{{x}_{0}})\cdot ({{y}_{\min }}-{{y}_{0}})/({{y}_{1}}-{{y}_{0}})\);
21.                 \(y={{y}_{\min }}\);
22.          else if (code & LEFT), then
23.                 \(x={{x}_{\min }}\);
24.                 \(y={{y}_{0}}+({{y}_{1}}-{{y}_{0}})\cdot ({{x}_{\min }}-{{x}_{0}})/({{x}_{1}}-{{x}_{0}})\);
25.          else if (code & RIGHT), then
26.                 \(x={{x}_{\max }}\);
27.                 \(y={{y}_{0}}+({{y}_{1}}-{{y}_{0}})\cdot ({{x}_{\max }}-{{x}_{0}})/({{x}_{1}}-{{x}_{0}})\);
28.          end if;
29.          if code0 == code, then
30.                 \({{x}_{0}}=x,{{y}_{0}}=y\);
31.                 code0 = computeCode(x0,y0);
32.          else
33.                 \({{x}_{1}}=x,{{y}_{1}}=y\);
34.                 code1 = computeCode(x1,y1);
35.          end if;
36.   end while;
37.   if accept == true, then
38.          \({{Q}_{0}}={{x}_{0}}{{\vec{e}}_{0}}+{{y}_{0}}{{\vec{e}}_{1}}+C\);
39.          \({{Q}_{1}}={{x}_{1}}{{\vec{e}}_{0}}+{{y}_{1}}{{\vec{e}}_{1}}+C\);
40.          return true;                   //裁剪线段是\({{Q}_{0}}{{Q}_{1}}\);
41.   else
42.          return false;                  //舍弃线段
43.   end if;

5.3.3. Liang-Barsky裁剪算法

设矩形的左侧边为\(x={{x}_{\min }}\),右侧边为\(x={{x}_{\max }}\),下侧边为\(y={{y}_{\min }}\),上侧边为\(y={{y}_{\max }}\)。如果一个点(x,y)在矩形区域内,则它满足下面的不等式:

\[\left\{ \begin{array}{l}{x_{\min }} \le x \le {x_{\max }}\\{y_{\min }} \le y \le {y_{\max }}\end{array} \right. \tag{5.5}\]

设线段的两个端点分别是\({{P}_{0}}({{x}_{0}},{{y}_{0}})\)和\({{P}_{1}}({{x}_{1}},{{y}_{1}})\),线段可以用参数方程的形式来表示

\[\left\{ \begin{array}{l}x = {x_0} + \Delta x \cdot t\\y = {y_0} + \Delta y \cdot t\end{array} \right. \tag{5.6}\]

其中,\(\Delta x={{x}_{1}}-{{x}_{0}},\Delta y={{y}_{1}}-{{y}_{0}}\)。

把等式(5.6)代入等式(5.5)中,可得

\[\left\{ \begin{array}{l} – \Delta x \cdot t \le {x_0} – {x_{\min }}\\\Delta x \cdot t \le {x_{\max }} – {x_0}\\ – \Delta y \cdot t \le {y_0} – {y_{\min }}\\\Delta y \cdot t \le {y_{\max }} – {y_0}\end{array} \right. \tag{5.7}\]

等式(5.7)可以用一个统一的不等式形式来表示

\[{p_i}t \le {q_i},i = 1,2,3,4 \tag{5.9}\]

其中,

\[\begin{array}{*{20}{l}}{{p_1} = – \Delta x,}&{{q_1} = {x_0} – {x_{\min }}}\\{{p_2} = \Delta x,}&{{q_2} = {x_{\max }} – {x_0}}\\{{p_3} = – \Delta y,}&{{q_3} = {y_0} – {y_{\min }}}\\{{p_4} = \Delta y,}&{{q_4} = {y_{\max }} – {y_0}}\end{array}\]

现在考虑从几何意义上理解\({{q}_{i}}\)和\({{p}_{i}}\)。矩形的边界所在的直线把平面分成两半,称矩形所在的一侧半平面为可视半面,另一侧半平面为不可视半面。线段与边界线的交点处的参数值\(t={{q}_{i}}/{{p}_{i}}\),把它代入等式(5.6)就是交点。对于不等式中的\({{q}_{i}}\),若\({{q}_{i}}\ge 0\),说明点P0在可视可半面;若\({{q}_{i}}\prec 0\),说明点P1在不可视半面。对于不等式中的\({{p}_{i}}\),若\({{p}_{i}}\prec 0\),则不等式是\(t\ge {{q}_{i}}/{{p}_{i}}\),说明线段\({{P}_{0}}{{P}_{1}}\)可能由不可视半面进入可视半面,此时\({{q}_{i}}\ge 0\),则有\({{t}_{0}}\prec 0\),那么不再需要计算交点;若\({{p}_{i}}\succ 0\),不等式是\(t\le {{q}_{i}}/{{p}_{i}}\),说明线段\({{P}_{0}}{{P}_{1}}\)可能由可视半面进入不可视半面,此时\({{q}_{i}}\ge {{p}_{i}}\),则有\({{t}_{1}}\succ 1\),那么不再需要计算交点;若\({{p}_{i}}=0\),不等式是\(0\le {{q}_{i}}\),线段与边界线平行,如果\({{q}_{i}}\prec 0\),舍弃线段,因它它在边界之外,否则,完整的保留线段。\({{q}_{i}}\)和.\({{p}_{i}}\).的几何解释的流程图,如图5.8所示。

2015-3-23 13-55-54

图5.8 \({{q}_{i}}\)和\({{p}_{i}}\)的几何解释的流程图

对于给定其个裁剪边界的\(q\]和\(p\)值,当\(p\prec 0,q\prec 0\)时,\(r=q/p\),若\(r\succ {{t}_{1}}\),舍弃线段,否则更新\({{t}_{0}}=r\);当\(p\succ 0,q\prec p\]时,\(r=q/p\),若\(r\prec {{t}_{0}}\),舍弃线段,否则,更新\({{t}_{1}}=r\);若\(p=0\)时,若\(q\prec 0\),舍弃线段,否则,保留线段,\({{t}_{0}}\)和\({{t}_{1}}\)值不变。边界裁剪线段的实现伪码,如下所示:

bool clip(Real p,Real q,Real& t0,Real& t1)         //Real是单精度或双精度
1.    if p<0 && q<0, then
2.           r = q / p;
3.           if r > t1, then
4.                  return false;
5.           else if r > t0 , then
6.                  t0 = r;
7.           end if;
8.    else if p>0 && q<p, then
9.           r = q / p;
10.          if r < t0, then
11.                 return false;
12.          else if r < t1, then
13.                 t1 = r;
14.          end if;
15.   else if q < 0, then
16.          return false;
17.   end if;
18.   return true;

初始化t0=0和t1=1,计算出矩形的四条裁剪边的p值和q值,重复调用clip()方法四次,来判断是舍弃线段还是改变参数t。

举个例子来解释Liang-Barsky线段裁剪算法,设线段\({{P}_{0}}{{P}_{1}}\)的两个端点分别是\({{P}_{0}}(-1,-2)\)和\({{P}_{1}}(2,4)\),矩形的边界分别是\({{x}_{\min }}=0\),\({{x}_{\max }}=1\],\({{y}_{\min }}=0\)和\({{y}_{\max }}=1\),则有\(\Delta x=3\)和\(\Delta y=6\)。等式式(5.8),得到

\[\begin{array}{*{20}{l}}{{p_1} = – \Delta x = – 3,}&{{q_1} = {x_0} – {x_{\min }} = – 1,}&{{q_1}/{p_1} = 1/3;}\\{{p_2} = \Delta x = 3,}&{{q_2} = {x_{\max }} – {x_0} = 2,}&{{q_2}/{p_2} = 2/3;}\\{{p_3} = – \Delta y = – 6,}&{{q_3} = {y_0} – {y_{\min }} = – 2,}&{{q_3}/{p_3} = 1/3;}\\{{p_4} = \Delta y = 6,}&{{q_4} = {y_{\max }} – {y_0} = 3,}&{{q_3}/{p_3} = 1/2;}\end{array}\]

根据这些数值,可以计算出t0和t1的值,即

\[\left\{ \begin{array}{l}{t_0} = \max (\{ {q_i}/{p_i}|{p_i} \prec 0,i = 1,2,3,4\} \cup \{ 0\} ) = \max (1/3,1/3,0) = 1/3\\{t_1} = \min (\{ {q_i}/{p_i}|{p_i} \prec 0,i = 1,2,3,4\} \cup \{ 1\} ) = \max (2/3,1/2,1) = 1/2\end{array} \right.\]

在实现中特别注意,当\({{p}_{i}}\prec 0,{{q}_{i}}\ge 0\)或者\({{p}_{i}}\succ 0,{{q}_{i}}\ge {{p}_{i}}\)时,可以忽略\({{q}_{i}}/{{p}_{i}}\)的计算。

Liang-Barsky线段裁剪算法的伪码如下所示:

求矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)对线段\({{P}_{0}}{{P}_{1}}\)的裁剪
1.    \({{x}_{0}}=({{P}_{0}}-C)\cdot {{\vec{e}}_{0}},{{y}_{0}}=({{P}_{0}}-C)\cdot {{\vec{e}}_{1}}\);
2.    \({{x}_{1}}=({{P}_{1}}-C)\cdot {{\vec{e}}_{0}},{{y}_{1}}=({{P}_{1}}-C)\cdot {{\vec{e}}_{1}}\);
3.    \({{x}_{\min }}=-{{u}_{0}},{{y}_{\min }}=-{{u}_{1}},{{x}_{\max }}={{u}_{0}},{{y}_{\max }}={{u}_{1}}\);
4.    t0 = 0, t1 = 1;
5.    \(\Delta x\)= x1 – x0;
6.    if clip(-\(\Delta x\), x0-xmin, t0, t1) == true && clip( \(\Delta x\), xmax-x0, t0, t1) == true, then
7.           \(\Delta y\)= y1 – y0;
8.           if clip(-\(\Delta y\), y0-ymin, t0, t1) == true && clip( \(\Delta y\), ymax-y0, t0, t1) == true, then
9.                  if t0 ≥ 0, then
10.                        \(x={{x}_{0}}+{{t}_{0}}\cdot \Delta x,y={{y}_{0}}+{{t}_{0}}\cdot \Delta y\);
11.                 end if;
12.                 \({{Q}_{0}}=x{{\vec{e}}_{0}}+y{{\vec{e}}_{1}}+C\);
13.                 if t1 ≤ 1, then
14.                        \(x={{x}_{0}}+{{t}_{1}}\cdot \Delta x,y={{y}_{0}}+{{t}_{1}}\cdot \Delta y\);
15.                 end if;
16.                 \({{Q}_{1}}=x{{\vec{e}}_{0}}+y{{\vec{e}}_{1}}+C\);
17.                 return true;            //裁剪线段是\({{Q}_{0}}{{Q}_{1}}\)
18.          end if;
19.   end if;
20.   return false;                         //舍弃线段

spacer

Leave a reply