1.1 --- a/src/contrib/pyviz.cc Thu Dec 04 18:49:58 2008 +0000
1.2 +++ b/src/contrib/pyviz.cc Thu Jan 29 16:46:39 2009 +0000
1.3 @@ -706,13 +706,504 @@
1.4 }
1.5
1.6
1.7 +
1.8 +
1.9 +
1.10 +
1.11 +namespace
1.12 +{
1.13 + // Adapted from http://en.wikipedia.org/w/index.php?title=Line_clipping&oldid=248609574
1.14 + class FastClipping
1.15 + {
1.16 + public:
1.17 + struct Vector2
1.18 + {
1.19 + double x;
1.20 + double y;
1.21 + };
1.22 +
1.23 + Vector2 m_clipMin, m_clipMax;
1.24 +
1.25 + struct Line
1.26 + {
1.27 + Vector2 start, end;
1.28 + double dx, dy;
1.29 + };
1.30 +
1.31 + private:
1.32 +
1.33 + void ClipStartTop (Line &line)
1.34 + {
1.35 + line.start.x += line.dx * (m_clipMin.y - line.start.y) / line.dy;
1.36 + line.start.y = m_clipMin.y;
1.37 + }
1.38 +
1.39 + void ClipStartBottom (Line &line)
1.40 + {
1.41 + line.start.x += line.dx * (m_clipMax.y - line.start.y) / line.dy;
1.42 + line.start.y = m_clipMax.y;
1.43 + }
1.44 +
1.45 + void ClipStartRight (Line &line)
1.46 + {
1.47 + line.start.y += line.dy * (m_clipMax.x - line.start.x) / line.dx;
1.48 + line.start.x = m_clipMax.x;
1.49 + }
1.50 +
1.51 + void ClipStartLeft (Line &line)
1.52 + {
1.53 + line.start.y += line.dy * (m_clipMin.x - line.start.x) / line.dx;
1.54 + line.start.x = m_clipMin.x;
1.55 + }
1.56 +
1.57 + void ClipEndTop (Line &line)
1.58 + {
1.59 + line.end.x += line.dx * (m_clipMin.y - line.end.y) / line.dy;
1.60 + line.end.y = m_clipMin.y;
1.61 + }
1.62 +
1.63 + void ClipEndBottom (Line &line) {
1.64 + line.end.x += line.dx * (m_clipMax.y - line.end.y) / line.dy;
1.65 + line.end.y = m_clipMax.y;
1.66 + }
1.67 +
1.68 + void ClipEndRight (Line &line)
1.69 + {
1.70 + line.end.y += line.dy * (m_clipMax.x - line.end.x) / line.dx;
1.71 + line.end.x = m_clipMax.x;
1.72 + }
1.73 +
1.74 + void ClipEndLeft (Line &line)
1.75 + {
1.76 + line.end.y += line.dy * (m_clipMin.x - line.end.x) / line.dx;
1.77 + line.end.x = m_clipMin.x;
1.78 + }
1.79 +
1.80 + public:
1.81 + FastClipping (Vector2 clipMin, Vector2 clipMax)
1.82 + : m_clipMin (clipMin), m_clipMax (clipMax)
1.83 + {
1.84 + }
1.85 +
1.86 +
1.87 + bool ClipLine (Line &line)
1.88 + {
1.89 + uint8_t lineCode = 0;
1.90 +
1.91 + if (line.end.y < m_clipMin.y)
1.92 + lineCode |= 8;
1.93 + else if (line.end.y > m_clipMax.y)
1.94 + lineCode |= 4;
1.95 +
1.96 + if (line.end.x > m_clipMax.x)
1.97 + lineCode |= 2;
1.98 + else if (line.end.x < m_clipMin.x)
1.99 + lineCode |= 1;
1.100 +
1.101 + if (line.start.y < m_clipMin.y)
1.102 + lineCode |= 128;
1.103 + else if (line.start.y > m_clipMax.y)
1.104 + lineCode |= 64;
1.105 +
1.106 + if (line.start.x > m_clipMax.x)
1.107 + lineCode |= 32;
1.108 + else if (line.start.x < m_clipMin.x)
1.109 + lineCode |= 16;
1.110 +
1.111 + // 9 - 8 - A
1.112 + // | | |
1.113 + // 1 - 0 - 2
1.114 + // | | |
1.115 + // 5 - 4 - 6
1.116 + switch (lineCode)
1.117 + {
1.118 + // center
1.119 + case 0x00:
1.120 + return true;
1.121 +
1.122 + case 0x01:
1.123 + ClipEndLeft (line);
1.124 + return true;
1.125 +
1.126 + case 0x02:
1.127 + ClipEndRight (line);
1.128 + return true;
1.129 +
1.130 + case 0x04:
1.131 + ClipEndBottom (line);
1.132 + return true;
1.133 +
1.134 + case 0x05:
1.135 + ClipEndLeft (line);
1.136 + if (line.end.y > m_clipMax.y)
1.137 + ClipEndBottom (line);
1.138 + return true;
1.139 +
1.140 + case 0x06:
1.141 + ClipEndRight (line);
1.142 + if (line.end.y > m_clipMax.y)
1.143 + ClipEndBottom (line);
1.144 + return true;
1.145 +
1.146 + case 0x08:
1.147 + ClipEndTop (line);
1.148 + return true;
1.149 +
1.150 + case 0x09:
1.151 + ClipEndLeft (line);
1.152 + if (line.end.y < m_clipMin.y)
1.153 + ClipEndTop (line);
1.154 + return true;
1.155 +
1.156 + case 0x0A:
1.157 + ClipEndRight (line);
1.158 + if (line.end.y < m_clipMin.y)
1.159 + ClipEndTop (line);
1.160 + return true;
1.161 +
1.162 + // left
1.163 + case 0x10:
1.164 + ClipStartLeft (line);
1.165 + return true;
1.166 +
1.167 + case 0x12:
1.168 + ClipStartLeft (line);
1.169 + ClipEndRight (line);
1.170 + return true;
1.171 +
1.172 + case 0x14:
1.173 + ClipStartLeft (line);
1.174 + if (line.start.y > m_clipMax.y)
1.175 + return false;
1.176 + ClipEndBottom (line);
1.177 + return true;
1.178 +
1.179 + case 0x16:
1.180 + ClipStartLeft (line);
1.181 + if (line.start.y > m_clipMax.y)
1.182 + return false;
1.183 + ClipEndBottom (line);
1.184 + if (line.end.x > m_clipMax.x)
1.185 + ClipEndRight (line);
1.186 + return true;
1.187 +
1.188 + case 0x18:
1.189 + ClipStartLeft (line);
1.190 + if (line.start.y < m_clipMin.y)
1.191 + return false;
1.192 + ClipEndTop (line);
1.193 + return true;
1.194 +
1.195 + case 0x1A:
1.196 + ClipStartLeft (line);
1.197 + if (line.start.y < m_clipMin.y)
1.198 + return false;
1.199 + ClipEndTop (line);
1.200 + if (line.end.x > m_clipMax.x)
1.201 + ClipEndRight (line);
1.202 + return true;
1.203 +
1.204 + // right
1.205 + case 0x20:
1.206 + ClipStartRight (line);
1.207 + return true;
1.208 +
1.209 + case 0x21:
1.210 + ClipStartRight (line);
1.211 + ClipEndLeft (line);
1.212 + return true;
1.213 +
1.214 + case 0x24:
1.215 + ClipStartRight (line);
1.216 + if (line.start.y > m_clipMax.y)
1.217 + return false;
1.218 + ClipEndBottom (line);
1.219 + return true;
1.220 +
1.221 + case 0x25:
1.222 + ClipStartRight (line);
1.223 + if (line.start.y > m_clipMax.y)
1.224 + return false;
1.225 + ClipEndBottom (line);
1.226 + if (line.end.x < m_clipMin.x)
1.227 + ClipEndLeft (line);
1.228 + return true;
1.229 +
1.230 + case 0x28:
1.231 + ClipStartRight (line);
1.232 + if (line.start.y < m_clipMin.y)
1.233 + return false;
1.234 + ClipEndTop (line);
1.235 + return true;
1.236 +
1.237 + case 0x29:
1.238 + ClipStartRight (line);
1.239 + if (line.start.y < m_clipMin.y)
1.240 + return false;
1.241 + ClipEndTop (line);
1.242 + if (line.end.x < m_clipMin.x)
1.243 + ClipEndLeft (line);
1.244 + return true;
1.245 +
1.246 + // bottom
1.247 + case 0x40:
1.248 + ClipStartBottom (line);
1.249 + return true;
1.250 +
1.251 + case 0x41:
1.252 + ClipStartBottom (line);
1.253 + if (line.start.x < m_clipMin.x)
1.254 + return false;
1.255 + ClipEndLeft (line);
1.256 + if (line.end.y > m_clipMax.y)
1.257 + ClipEndBottom (line);
1.258 + return true;
1.259 +
1.260 + case 0x42:
1.261 + ClipStartBottom (line);
1.262 + if (line.start.x > m_clipMax.x)
1.263 + return false;
1.264 + ClipEndRight (line);
1.265 + return true;
1.266 +
1.267 + case 0x48:
1.268 + ClipStartBottom (line);
1.269 + ClipEndTop (line);
1.270 + return true;
1.271 +
1.272 + case 0x49:
1.273 + ClipStartBottom (line);
1.274 + if (line.start.x < m_clipMin.x)
1.275 + return false;
1.276 + ClipEndLeft (line);
1.277 + if (line.end.y < m_clipMin.y)
1.278 + ClipEndTop (line);
1.279 + return true;
1.280 +
1.281 + case 0x4A:
1.282 + ClipStartBottom (line);
1.283 + if (line.start.x > m_clipMax.x)
1.284 + return false;
1.285 + ClipEndRight (line);
1.286 + if (line.end.y < m_clipMin.y)
1.287 + ClipEndTop (line);
1.288 + return true;
1.289 +
1.290 + // bottom-left
1.291 + case 0x50:
1.292 + ClipStartLeft (line);
1.293 + if (line.start.y > m_clipMax.y)
1.294 + ClipStartBottom (line);
1.295 + return true;
1.296 +
1.297 + case 0x52:
1.298 + ClipEndRight (line);
1.299 + if (line.end.y > m_clipMax.y)
1.300 + return false;
1.301 + ClipStartBottom (line);
1.302 + if (line.start.x < m_clipMin.x)
1.303 + ClipStartLeft (line);
1.304 + return true;
1.305 +
1.306 + case 0x58:
1.307 + ClipEndTop (line);
1.308 + if (line.end.x < m_clipMin.x)
1.309 + return false;
1.310 + ClipStartBottom (line);
1.311 + if (line.start.x < m_clipMin.x)
1.312 + ClipStartLeft (line);
1.313 + return true;
1.314 +
1.315 + case 0x5A:
1.316 + ClipStartLeft (line);
1.317 + if (line.start.y < m_clipMin.y)
1.318 + return false;
1.319 + ClipEndRight (line);
1.320 + if (line.end.y > m_clipMax.y)
1.321 + return false;
1.322 + if (line.start.y > m_clipMax.y)
1.323 + ClipStartBottom (line);
1.324 + if (line.end.y < m_clipMin.y)
1.325 + ClipEndTop (line);
1.326 + return true;
1.327 +
1.328 + // bottom-right
1.329 + case 0x60:
1.330 + ClipStartRight (line);
1.331 + if (line.start.y > m_clipMax.y)
1.332 + ClipStartBottom (line);
1.333 + return true;
1.334 +
1.335 + case 0x61:
1.336 + ClipEndLeft (line);
1.337 + if (line.end.y > m_clipMax.y)
1.338 + return false;
1.339 + ClipStartBottom (line);
1.340 + if (line.start.x > m_clipMax.x)
1.341 + ClipStartRight (line);
1.342 + return true;
1.343 +
1.344 + case 0x68:
1.345 + ClipEndTop (line);
1.346 + if (line.end.x > m_clipMax.x)
1.347 + return false;
1.348 + ClipStartRight (line);
1.349 + if (line.start.y > m_clipMax.y)
1.350 + ClipStartBottom (line);
1.351 + return true;
1.352 +
1.353 + case 0x69:
1.354 + ClipEndLeft (line);
1.355 + if (line.end.y > m_clipMax.y)
1.356 + return false;
1.357 + ClipStartRight (line);
1.358 + if (line.start.y < m_clipMin.y)
1.359 + return false;
1.360 + if (line.end.y < m_clipMin.y)
1.361 + ClipEndTop (line);
1.362 + if (line.start.y > m_clipMax.y)
1.363 + ClipStartBottom (line);
1.364 + return true;
1.365 +
1.366 + // top
1.367 + case 0x80:
1.368 + ClipStartTop (line);
1.369 + return true;
1.370 +
1.371 + case 0x81:
1.372 + ClipStartTop (line);
1.373 + if (line.start.x < m_clipMin.x)
1.374 + return false;
1.375 + ClipEndLeft (line);
1.376 + return true;
1.377 +
1.378 + case 0x82:
1.379 + ClipStartTop (line);
1.380 + if (line.start.x > m_clipMax.x)
1.381 + return false;
1.382 + ClipEndRight (line);
1.383 + return true;
1.384 +
1.385 + case 0x84:
1.386 + ClipStartTop (line);
1.387 + ClipEndBottom (line);
1.388 + return true;
1.389 +
1.390 + case 0x85:
1.391 + ClipStartTop (line);
1.392 + if (line.start.x < m_clipMin.x)
1.393 + return false;
1.394 + ClipEndLeft (line);
1.395 + if (line.end.y > m_clipMax.y)
1.396 + ClipEndBottom (line);
1.397 + return true;
1.398 +
1.399 + case 0x86:
1.400 + ClipStartTop (line);
1.401 + if (line.start.x > m_clipMax.x)
1.402 + return false;
1.403 + ClipEndRight (line);
1.404 + if (line.end.y > m_clipMax.y)
1.405 + ClipEndBottom (line);
1.406 + return true;
1.407 +
1.408 + // top-left
1.409 + case 0x90:
1.410 + ClipStartLeft (line);
1.411 + if (line.start.y < m_clipMin.y)
1.412 + ClipStartTop (line);
1.413 + return true;
1.414 +
1.415 + case 0x92:
1.416 + ClipEndRight (line);
1.417 + if (line.end.y < m_clipMin.y)
1.418 + return false;
1.419 + ClipStartTop (line);
1.420 + if (line.start.x < m_clipMin.x)
1.421 + ClipStartLeft (line);
1.422 + return true;
1.423 +
1.424 + case 0x94:
1.425 + ClipEndBottom (line);
1.426 + if (line.end.x < m_clipMin.x)
1.427 + return false;
1.428 + ClipStartLeft (line);
1.429 + if (line.start.y < m_clipMin.y)
1.430 + ClipStartTop (line);
1.431 + return true;
1.432 +
1.433 + case 0x96:
1.434 + ClipStartLeft (line);
1.435 + if (line.start.y > m_clipMax.y)
1.436 + return false;
1.437 + ClipEndRight (line);
1.438 + if (line.end.y < m_clipMin.y)
1.439 + return false;
1.440 + if (line.start.y < m_clipMin.y)
1.441 + ClipStartTop (line);
1.442 + if (line.end.y > m_clipMax.y)
1.443 + ClipEndBottom (line);
1.444 + return true;
1.445 +
1.446 + // top-right
1.447 + case 0xA0:
1.448 + ClipStartRight (line);
1.449 + if (line.start.y < m_clipMin.y)
1.450 + ClipStartTop (line);
1.451 + return true;
1.452 +
1.453 + case 0xA1:
1.454 + ClipEndLeft (line);
1.455 + if (line.end.y < m_clipMin.y)
1.456 + return false;
1.457 + ClipStartTop (line);
1.458 + if (line.start.x > m_clipMax.x)
1.459 + ClipStartRight (line);
1.460 + return true;
1.461 +
1.462 + case 0xA4:
1.463 + ClipEndBottom (line);
1.464 + if (line.end.x > m_clipMax.x)
1.465 + return false;
1.466 + ClipStartRight (line);
1.467 + if (line.start.y < m_clipMin.y)
1.468 + ClipStartTop (line);
1.469 + return true;
1.470 +
1.471 + case 0xA5:
1.472 + ClipEndLeft (line);
1.473 + if (line.end.y < m_clipMin.y)
1.474 + return false;
1.475 + ClipStartRight (line);
1.476 + if (line.start.y > m_clipMax.y)
1.477 + return false;
1.478 + if (line.end.y > m_clipMax.y)
1.479 + ClipEndBottom (line);
1.480 + if (line.start.y < m_clipMin.y)
1.481 + ClipStartTop (line);
1.482 + return true;
1.483 + }
1.484 +
1.485 + return false;
1.486 + }
1.487 + };
1.488 +}
1.489 +
1.490 void
1.491 PyViz::LineClipping (double boundsX1, double boundsY1, double boundsX2, double boundsY2,
1.492 double &lineX1, double &lineY1, double &lineX2, double &lineY2)
1.493 {
1.494 + FastClipping::Vector2 clipMin = {boundsX1, boundsY1}, clipMax = {boundsX2, boundsY2};
1.495 + FastClipping::Line line = { { lineX1, lineY1 }, { lineX2, lineY2 }, (lineX2-lineX1), (lineY2-lineY1) };
1.496 +
1.497 + FastClipping clipper (clipMin, clipMax);
1.498 + clipper.ClipLine (line);
1.499 + lineX1 = line.start.x;
1.500 + lineX2 = line.end.x;
1.501 + lineY1 = line.start.y;
1.502 + lineY2 = line.end.y;
1.503 +}
1.504 +
1.505
1.506 }
1.507
1.508 -
1.509 -}
1.510 -