首页 > 代码库 > [计算机图形学 with OpenGL] Chapter8 习题8.12 NLN二维线段裁剪算法实现
[计算机图形学 with OpenGL] Chapter8 习题8.12 NLN二维线段裁剪算法实现
Nicholl-Lee-Nicholl二维线段裁剪算法相对于Cohen-Sutherland和Liang-Barsky算法来说，在求交点之前进行了线段端点相对于几个区域的判断，可以确切的知道要求交点的边的信息。
此方法只在二维空间裁剪时使用，C-S和L-B裁剪方法则可应用到三维空间。
算法步骤：
1 先使用C-S裁剪算法的区域码判断方法，去除一部分在裁剪区域外面的线段、显示在完全在裁剪区域内的线段。其他不能判断的情况，采用NLN算法进行裁剪。
2 p1和p2若有一点在区域内，必要时交换端点以确保p1在区域内。
分别计算p1到裁剪区域四个顶点斜率m1-m4（从左下端点顺时针的4个顶点），判断线段斜率m与m1-m4的关系，决定计算哪条边与线段的交点。交点值赋给p2.
3 p1和p2有一个点在区域0001（左侧），必要时交换端点以确保p1在0001内。
因为p2在区域内的情况被步骤2覆盖，因此p1为线段与左边界的交点。
分别计算m1-m4，判断线段斜率m与m1-m4的关系，决定计算哪条边与线段的交点。此交点赋值给p2.
4 p1和p2有一个点在区域1001（左上角），必要时交换端点以确保p1在1001内。
同样p2在区域内的情况被步骤2覆盖。
分别计算m1-m4，判断线段斜率m与m1-m4的关系（注意此处需要判断m2与m4的大小，决定计算哪条边与线段的交点）。分别计算p1和p2。
5 对于其他6种情况，分别判断p1和p2的位置，在不同的区域，将线段和裁剪区域旋转相应的角度，重复步骤2-4进行裁剪。裁剪完成后再将线段旋转回原来的位置。
1 #include <GLUT/GLUT.h> 2 #include <iostream> 3 #include <math.h> 4 #include "lineNLN.h" 5 #include "linebres.h" 6 7 GLfloat m1, m2, m3, m4; 8 9 const GLint winLeftBitCode = 0x1; // 直接为1也没问题 10 const GLint winRightBitCode = 0x2; 11 const GLint winBottomBitCode = 0x4; 12 const GLint winTopBitCode = 0x8; 13 14 typedef GLfloat Matrix3x3 [3][3]; 15 Matrix3x3 matRotate; 16 Matrix3x3 matComposite; 17 const GLdouble pi = 3.14159; 18 GLfloat delta; 19 wcPt2D center; 20 21 inline GLint inside (GLint code) 22 { 23 return GLint (!(code)); 24 } 25 inline GLint reject (GLint code1, GLint code2) 26 { 27 return GLint (code1 & code2); 28 } 29 inline GLint accept (GLint code1, GLint code2) 30 { 31 return GLint (!(code1 | code2)); 32 } 33 34 GLubyte encode (wcPt2D pt, wcPt2D winMin, wcPt2D winMax) 35 { 36 GLubyte code = 0x00; 37 38 if(pt.getx() < winMin.getx()) 39 code = code | winLeftBitCode; 40 if(pt.getx() > winMax.getx()) 41 code = code | winRightBitCode; 42 if(pt.gety() < winMin.gety()) 43 code = code | winBottomBitCode; 44 if(pt.gety() > winMax.gety()) 45 code = code | winTopBitCode; 46 47 return code; 48 } 49 50 void swapPts (wcPt2D * p1, wcPt2D * p2) // TODO 为什么要用指针？ 51 { 52 wcPt2D tmp; 53 tmp = * p1; * p1 = * p2; * p2 = tmp; 54 } 55 56 void swapCode (GLubyte * c1, GLubyte * c2) 57 { 58 GLubyte tmp; 59 tmp = * c1; * c1 = * c2; * c2 = tmp; 60 } 61 62 void renewWinVertexes (wcPt2D * winMin, wcPt2D * winMax) 63 { 64 wcPt2D tmp1, tmp2; 65 tmp1.setCoords(fmin(winMin->getx(), winMax->getx()), fmin(winMin->gety(), winMax->gety())); 66 tmp2.setCoords(fmax(winMin->getx(), winMax->getx()), fmax(winMin->gety(), winMax->gety())); 67 * winMin = tmp1; 68 * winMax = tmp2; 69 } 70 71 void matrix3x3SetIdentity (Matrix3x3 matIden3x3) 72 { 73 GLint row, col; 74 for(row = 0; row < 3; row++) 75 { 76 for(col = 0; col < 3; col++) 77 { 78 matIden3x3[row][col] = (row == col); 79 } 80 } 81 } 82 83 void matrix3x3Premultiply (Matrix3x3 m1, Matrix3x3 m2) 84 { 85 GLint row, col; 86 Matrix3x3 matTemp; 87 88 for(row = 0; row < 3; row++) 89 { 90 for(col = 0; col < 3; col++) 91 { 92 matTemp[row][col] = m1[row][0] * m2 [0][col] + m1[row][1] * m2 [1][col] + m1[row][2] * m2 [2][col]; 93 } 94 } 95 96 for(row = 0; row < 3; row++) 97 { 98 for(col = 0; col < 3; col++) 99 {100 m2[row][col] = matTemp[row][col];101 }102 }103 }104 105 void rotate2D (wcPt2D pivotPt, GLfloat theta)106 {107 matrix3x3SetIdentity(matRotate);108 109 matRotate[0][0] = cos(theta);110 matRotate[0][1] = -sin(theta);111 matRotate[0][2] = pivotPt.getx() * (1 - cos(theta)) + pivotPt.gety() * sin(theta);112 matRotate[1][0] = sin(theta);113 matRotate[1][1] = cos(theta);114 matRotate[1][2] = pivotPt.gety() * (1 - cos(theta)) + pivotPt.getx() * sin(theta);115 }116 117 void transformVerts2D (wcPt2D * verts)118 {119 GLfloat tempx, tempy;120 121 tempx = matRotate[0][0] * verts->getx() + matRotate[0][1] * verts->gety() + matRotate[0][2];122 tempy = matRotate[1][0] * verts->getx() + matRotate[1][1] * verts->gety() + matRotate[1][2];123 124 verts->setCoords(tempx, tempy);125 }126 127 void slopeWith4Vertexes (wcPt2D winMin, wcPt2D winMax, wcPt2D p1)128 {129 m1 = (p1.gety() - winMin.gety()) / (p1.getx() - winMin.getx());130 m2 = (p1.gety() - winMax.gety()) / (p1.getx() - winMin.getx());131 m3 = (p1.gety() - winMax.gety()) / (p1.getx() - winMax.getx());132 m4 = (p1.gety() - winMin.gety()) / (p1.getx() - winMax.getx());133 134 // std::cout << "slope : m1 : " << m1 << " m2 : " << m2 << " m3 : " << m3 << " m4 : " << m4 << std::endl;135 }136 137 void lineClipNLN (wcPt2D winMin, wcPt2D winMax, wcPt2D p1, wcPt2D p2)138 {139 GLubyte code1, code2;140 GLint plotLine = false, done = false;141 GLfloat m = 0.0;142 143 while (!done)144 {145 code1 = encode(p1, winMin, winMax);146 code2 = encode(p2, winMin, winMax);147 if(accept(code1, code2))148 {149 plotLine = true;150 done = true;151 }152 else153 {154 if(reject(code1, code2))155 {156 std::cout << "1 rejected line!" << std::endl;157 done = true;158 }159 else160 {161 // 有一个点在裁剪区域内162 if(inside(code1) || inside(code2))163 {164 plotLine = true;165 done = true;166 if(!inside(code1))167 {168 swapPts(&p1, &p2);169 swapCode(&code1, &code2);170 }171 wcPt2D topLeft, bottomRight;172 topLeft.setCoords(winMin.getx(), winMax.gety());173 bottomRight.setCoords(winMax.getx(), winMin.gety());174 if(p1.equals(winMin) || p1.equals(winMax) || p1.equals(topLeft) || p1.equals(bottomRight))175 {176 p2.setCoords(p1.getx(), p1.gety());177 }178 else179 {180 slopeWith4Vertexes(winMin, winMax, p1);181 182 if(p1.getx() != p2.getx())183 {184 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());185 186 if(m <= m1 && m >= m2 && (code2 & winLeftBitCode))187 {//L188 p2.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));189 }190 else if(m <= m3 && m >= m4 && (code2 & winRightBitCode))191 {//R192 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));193 }194 else if((m > m3 || m < m2) && (code2 & winTopBitCode))195 {//T196 p2.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());197 }198 else if((m > m1 || m < m4) && (code2 & winBottomBitCode))199 {//B200 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());201 }202 }203 else204 {205 if(p2.gety() > winMax.gety())206 {207 p2.setCoords(p2.getx(), winMax.gety());208 }209 else210 {211 p2.setCoords(p2.getx(), winMin.gety());212 }213 }214 }215 }216 else217 {218 if(code1 == 0x01 || code2 == 0x01)219 // 有一个点的区域码是0001，即在裁剪区域正左侧，L的情况在上一个if中包含，这里只会有LT，LR，LB和rejected的情况220 {221 if(code1 != 0x01)222 {223 swapPts(&p1, &p2);224 swapCode(&code1, &code2);225 }226 slopeWith4Vertexes(winMin, winMax, p1);227 if(p1.getx() != p2.getx())228 {229 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());230 }231 if(m < m1 || m > m2)232 {233 std::cout << "2 rejected line!" << std::endl;234 done = true;235 }236 else237 {238 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));239 if((m <= m2 && m >= m3) && (code2 & winTopBitCode))240 {//LT241 p2.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());242 }243 else if((m < m3 && m >= m4) && (code2 & winRightBitCode))244 {//LR245 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));246 }247 else if((m < m4 && m >= m1) && (code2 & winBottomBitCode))248 {//LB249 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());250 }251 plotLine = true;252 done = true;253 }254 }255 else if(code1 == (winLeftBitCode | winTopBitCode) || code2 == (winLeftBitCode | winTopBitCode))256 // 有一个点在裁剪区域外左上角的情况，这里的L、T情况已经在第一个if里包含257 {258 if(code1 != (winLeftBitCode | winTopBitCode))259 {260 swapPts(&p1, &p2);261 swapCode(&code1, &code2);262 }263 264 slopeWith4Vertexes(winMin, winMax, p1);265 if(p1.getx() != p2.getx())266 {267 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());268 }269 if(m > m3 || m < m1)270 {271 std::cout << "3 rejected line!" << std::endl;272 done = true;273 }274 else275 {276 plotLine = true;277 done = true;278 if(m <= m3 && m >= m4)279 {280 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));281 if(m2 > m4 && m <= m2)282 {//LR283 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));284 }285 else286 {//TR287 p1.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());288 }289 }290 else if(m < m4 && m >= m1)291 {292 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());293 if(m2 < m4 && m >= m2)294 {//TB295 p1.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());296 }297 else298 {//LB299 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));300 }301 }302 }303 }304 else305 {306 center.setCoords((winMin.getx() + winMax.getx())/2, (winMin.gety() + winMax.gety())/2);307 308 if(code1 == (winLeftBitCode | winBottomBitCode) || code2 == (winLeftBitCode | winBottomBitCode))309 {//LB310 delta = -pi/2;311 }312 else if(code1 == winBottomBitCode || code2 == winBottomBitCode)313 {//B314 delta = -pi/2;315 }316 else if(code1 == (winBottomBitCode | winRightBitCode) || code2 == (winBottomBitCode | winRightBitCode))317 {//BR318 delta = pi;319 }320 else if(code1 == winRightBitCode || code2 == winRightBitCode)321 {//R322 delta = pi;323 }324 else if(code1 == (winRightBitCode | winTopBitCode) || code2 == (winRightBitCode | winTopBitCode))325 {//TR326 delta = pi/2;327 }328 else if(code1 == winTopBitCode || code2 == winTopBitCode)329 {//T330 delta = pi/2;331 }332 rotate2D(center, delta);333 transformVerts2D(&p1);334 transformVerts2D(&p2);335 transformVerts2D(&winMin);336 transformVerts2D(&winMax);337 renewWinVertexes(&winMin, &winMax);338 }339 }340 }341 }342 }343 344 if(plotLine)345 {346 if(delta != 0)347 {348 rotate2D(center, -delta);349 transformVerts2D(&p1);350 transformVerts2D(&p2);351 }352 lineBres(round(p1.getx()), round(p1.gety()), round(p2.getx()), round(p2.gety()));353 }354 delta = 0;355 }
完整代码路径：https://github.com/p0e0o0p0l0e0/Computer_Graphics/tree/f9a7ad1987586445d780de2461d423af0dd9ba6a
[计算机图形学 with OpenGL] Chapter8 习题8.12 NLN二维线段裁剪算法实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。