1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 // Polygon overlay 18 // 19 #include <cstdlib> 20 #include <cstring> 21 #include <cassert> 22 23 #include <iostream> 24 #include <algorithm> 25 26 #include "oneapi/tbb/tick_count.h" 27 #include "oneapi/tbb/blocked_range.h" 28 #include "oneapi/tbb/parallel_for.h" 29 #include "oneapi/tbb/spin_mutex.h" 30 #include "oneapi/tbb/global_control.h" 31 32 #include "common/utility/get_default_num_threads.hpp" 33 34 #include "polyover.hpp" 35 #include "polymain.hpp" 36 #include "pover_video.hpp" 37 38 /*! 39 * @brief intersects a polygon with a map, adding any results to output map 40 * 41 * @param[out] resultMap output map (must be allocated) 42 * @param[in] polygon to be intersected 43 * @param[in] map intersected against 44 * @param[in] lock to use when adding output polygons to result map 45 * 46 */ 47 void OverlayOnePolygonWithMap(Polygon_map_t *resultMap, 48 RPolygon *myPoly, 49 Polygon_map_t *map2, 50 oneapi::tbb::spin_mutex *rMutex) { 51 int r1, g1, b1, r2, g2, b2; 52 int myr = 0; 53 int myg = 0; 54 int myb = 0; 55 int p1Area = myPoly->area(); 56 for (unsigned int j = 1; (j < map2->size()) && (p1Area > 0); j++) { 57 RPolygon *p2 = &((*map2)[j]); 58 RPolygon *pnew; 59 int newxMin, newxMax, newyMin, newyMax; 60 myPoly->getColor(&r1, &g1, &b1); 61 if (PolygonsOverlap(myPoly, p2, newxMin, newyMin, newxMax, newyMax)) { 62 p2->getColor(&r2, &g2, &b2); 63 myr = r1 + r2; 64 myg = g1 + g2; 65 myb = b1 + b2; 66 p1Area -= (newxMax - newxMin + 1) * (newyMax - newyMin + 1); 67 if (rMutex) { 68 oneapi::tbb::spin_mutex::scoped_lock lock(*rMutex); 69 resultMap->push_back(RPolygon(newxMin, newyMin, newxMax, newyMax, myr, myg, myb)); 70 } 71 else { 72 resultMap->push_back(RPolygon(newxMin, newyMin, newxMax, newyMax, myr, myg, myb)); 73 } 74 } 75 } 76 } 77 78 /*! 79 * @brief Serial version of polygon overlay 80 * @param[out] output map 81 * @param[in] first map (map that individual polygons are taken from) 82 * @param[in] second map (map passed to OverlayOnePolygonWithMap) 83 */ 84 void SerialOverlayMaps(Polygon_map_t **resultMap, Polygon_map_t *map1, Polygon_map_t *map2) { 85 std::cout << "SerialOverlayMaps called" 86 << "\n"; 87 *resultMap = new Polygon_map_t; 88 89 RPolygon *p0 = &((*map1)[0]); 90 int mapxSize, mapySize, ignore1, ignore2; 91 p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); 92 (*resultMap)->reserve(mapxSize * mapySize); // can't be any bigger than this 93 // push the map size as the first polygon, 94 (*resultMap)->push_back(RPolygon(0, 0, mapxSize, mapySize)); 95 for (unsigned int i = 1; i < map1->size(); i++) { 96 RPolygon *p1 = &((*map1)[i]); 97 OverlayOnePolygonWithMap(*resultMap, p1, map2, nullptr); 98 } 99 } 100 101 /*! 102 * @class ApplyOverlay 103 * @brief Simple version of parallel overlay (make parallel on polygons in map1) 104 */ 105 class ApplyOverlay { 106 Polygon_map_t *m_map1, *m_map2, *m_resultMap; 107 oneapi::tbb::spin_mutex *m_rMutex; 108 109 public: 110 /*! 111 * @brief functor to apply 112 * @param[in] r range of polygons to intersect from map1 113 */ 114 void operator()(const oneapi::tbb::blocked_range<int> &r) const { 115 PRINT_DEBUG("From " << r.begin() << " to " << r.end()); 116 for (int i = r.begin(); i != r.end(); i++) { 117 RPolygon *myPoly = &((*m_map1)[i]); 118 OverlayOnePolygonWithMap(m_resultMap, myPoly, m_map2, m_rMutex); 119 } 120 } 121 ApplyOverlay(Polygon_map_t *resultMap, 122 Polygon_map_t *map1, 123 Polygon_map_t *map2, 124 oneapi::tbb::spin_mutex *rmutex) 125 : m_resultMap(resultMap), 126 m_map1(map1), 127 m_map2(map2), 128 m_rMutex(rmutex) {} 129 }; 130 131 /*! 132 * @brief apply the parallel algorithm 133 * @param[out] result_map generated map 134 * @param[in] polymap1 first map to be applied (algorithm is parallel on this map) 135 * @param[in] polymap2 second map. 136 */ 137 void NaiveParallelOverlay(Polygon_map_t *&result_map, 138 Polygon_map_t &polymap1, 139 Polygon_map_t &polymap2) { 140 // ----------------------------------- 141 bool automatic_threadcount = false; 142 143 if (gThreadsLow == THREADS_UNSET || gThreadsLow == utility::get_default_num_threads()) { 144 gThreadsLow = gThreadsHigh = utility::get_default_num_threads(); 145 automatic_threadcount = true; 146 } 147 result_map = new Polygon_map_t; 148 149 RPolygon *p0 = &(polymap1[0]); 150 int mapxSize, mapySize, ignore1, ignore2; 151 p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); 152 result_map->reserve(mapxSize * mapySize); // can't be any bigger than this 153 // push the map size as the first polygon, 154 oneapi::tbb::spin_mutex *resultMutex = new oneapi::tbb::spin_mutex(); 155 int grain_size = gGrainSize; 156 157 for (int nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) { 158 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, 159 nthreads); 160 if (gIsGraphicalVersion) { 161 RPolygon *xp = 162 new RPolygon(0, 0, gMapXSize - 1, gMapYSize - 1, 0, 0, 0); // Clear the output space 163 delete xp; 164 } 165 // put size polygon in result map 166 result_map->push_back(RPolygon(0, 0, mapxSize, mapySize)); 167 168 oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now(); 169 oneapi::tbb::parallel_for( 170 oneapi::tbb::blocked_range<int>(1, (int)(polymap1.size()), grain_size), 171 ApplyOverlay(result_map, &polymap1, &polymap2, resultMutex)); 172 oneapi::tbb::tick_count t1 = oneapi::tbb::tick_count::now(); 173 174 double naiveParallelTime = (t1 - t0).seconds() * 1000; 175 std::cout << "Naive parallel with spin lock and "; 176 if (automatic_threadcount) 177 std::cout << "automatic"; 178 else 179 std::cout << nthreads; 180 std::cout << ((nthreads == 1) ? " thread" : " threads"); 181 std::cout << " took " << naiveParallelTime << " msec : speedup over serial " 182 << (gSerialTime / naiveParallelTime) << "\n"; 183 if (gCsvFile.is_open()) { 184 gCsvFile << "," << naiveParallelTime; 185 } 186 #if _DEBUG 187 CheckPolygonMap(result_map); 188 ComparePolygonMaps(result_map, gResultMap); 189 #endif 190 result_map->clear(); 191 } 192 delete resultMutex; 193 if (gCsvFile.is_open()) { 194 gCsvFile << "\n"; 195 } 196 // ----------------------------------- 197 } 198 199 template <typename T> 200 void split_at(Flagged_map_t &in_map, 201 Flagged_map_t &left_out, 202 Flagged_map_t &right_out, 203 const T median) { 204 left_out.reserve(in_map.size()); 205 right_out.reserve(in_map.size()); 206 for (Flagged_map_t::iterator i = in_map.begin(); i != in_map.end(); ++i) { 207 RPolygon *p = i->p(); 208 if (p->xmax() < median) { 209 // in left map 210 left_out.push_back(*i); 211 } 212 else if (p->xmin() >= median) { 213 right_out.push_back(*i); 214 // in right map 215 } 216 else { 217 // in both maps. 218 left_out.push_back(*i); 219 right_out.push_back(RPolygon_flagged(p, true)); 220 } 221 } 222 } 223 224 // range that splits the maps as well as the range. the flagged_map_t are 225 // vectors of pointers, and each range owns its maps (has to free them on destruction.) 226 template <typename T> 227 class blocked_range_with_maps { 228 typedef oneapi::tbb::blocked_range<T> my_range_type; 229 230 private: 231 my_range_type my_range; 232 Flagged_map_t my_map1; 233 Flagged_map_t my_map2; 234 235 public: 236 blocked_range_with_maps(T begin, 237 T end, 238 typename my_range_type::size_type my_grainsize, 239 Polygon_map_t *p1, 240 Polygon_map_t *p2) 241 : my_range(begin, end, my_grainsize) { 242 my_map1.reserve(p1->size()); 243 my_map2.reserve(p2->size()); 244 for (int i = 1; i < p1->size(); ++i) { 245 my_map1.push_back(RPolygon_flagged(&((*p1)[i]), false)); 246 } 247 for (int i = 1; i < p2->size(); ++i) { 248 my_map2.push_back(RPolygon_flagged(&(p2->at(i)), false)); 249 } 250 } 251 252 // copy-constructor required for deep copy of flagged maps. One copy is done at the start of the 253 // parallel for. 254 blocked_range_with_maps(const blocked_range_with_maps &other) 255 : my_range(other.my_range), 256 my_map1(other.my_map1), 257 my_map2(other.my_map2) {} 258 bool empty() const { 259 return my_range.empty(); 260 } 261 bool is_divisible() const { 262 return my_range.is_divisible(); 263 } 264 265 #if _DEBUG 266 void check_my_map() { 267 assert(my_range.begin() <= my_range.end()); 268 for (Flagged_map_t::iterator i = my_map1.begin(); i != my_map1.end(); ++i) { 269 RPolygon *rp = i->p(); 270 assert(rp->xmax() >= my_range.begin()); 271 assert(rp->xmin() < my_range.end()); 272 } 273 for (Flagged_map_t::iterator i = my_map2.begin(); i != my_map2.end(); ++i) { 274 RPolygon *rp = i->p(); 275 assert(rp->xmax() >= my_range.begin()); 276 assert(rp->xmin() < my_range.end()); 277 } 278 } 279 280 void dump_map(Flagged_map_t &mapx) { 281 std::cout << " ** MAP **\n"; 282 for (Flagged_map_t::iterator i = mapx.begin(); i != mapx.end(); ++i) { 283 std::cout << *(i->p()); 284 if (i->isDuplicate()) { 285 std::cout << " -- is_duplicate"; 286 } 287 std::cout << "\n"; 288 } 289 std::cout << "\n"; 290 } 291 #endif 292 293 blocked_range_with_maps(blocked_range_with_maps &lhs_r, oneapi::tbb::split) 294 : my_range(my_range_type(lhs_r.my_range, oneapi::tbb::split())) { 295 // lhs_r.my_range makes my_range from [median, high) and rhs_r.my_range from [low, median) 296 Flagged_map_t original_map1 = lhs_r.my_map1; 297 Flagged_map_t original_map2 = lhs_r.my_map2; 298 lhs_r.my_map1.clear(); 299 lhs_r.my_map2.clear(); 300 split_at(original_map1, lhs_r.my_map1, my_map1, my_range.begin()); 301 split_at(original_map2, lhs_r.my_map2, my_map2, my_range.begin()); 302 #if _DEBUG 303 this->check_my_map(); 304 lhs_r.check_my_map(); 305 #endif 306 } 307 308 const my_range_type &range() const { 309 return my_range; 310 } 311 Flagged_map_t &map1() { 312 return my_map1; 313 } 314 Flagged_map_t &map2() { 315 return my_map2; 316 } 317 }; 318 319 /*! 320 * @class ApplySplitOverlay 321 * @brief parallel by columnar strip 322 */ 323 class ApplySplitOverlay { 324 Polygon_map_t *m_map1, *m_map2, *m_resultMap; 325 oneapi::tbb::spin_mutex *m_rMutex; 326 327 public: 328 /*! 329 * @brief functor for columnar parallel version 330 * @param[in] r range of map to be operated on 331 */ 332 void operator()(/*const*/ blocked_range_with_maps<int> &r) const { 333 #ifdef _DEBUG 334 // if we are debugging, serialize the method. That way we can 335 // see what is happening in each strip without the interleaving 336 // confusing things. 337 oneapi::tbb::spin_mutex::scoped_lock lock(*m_rMutex); 338 std::cout << std::unitbuf << "From " << r.range().begin() << " to " << r.range().end() - 1 339 << "\n"; 340 #endif 341 // get yMapSize 342 int r1, g1, b1, r2, g2, b2; 343 int myr = -1; 344 int myg = -1; 345 int myb = -1; 346 int i1, i2, i3, yMapSize; 347 (*m_map1)[0].get(&i1, &i2, &i3, &yMapSize); 348 349 Flagged_map_t &fmap1 = r.map1(); 350 Flagged_map_t &fmap2 = r.map2(); 351 352 // When intersecting polygons from fmap1 and fmap2, if BOTH are flagged 353 // as duplicate, don't add the result to the output map. We can still 354 // intersect them, because we are keeping track of how much of the polygon 355 // is left over from intersecting, and quitting when the polygon is 356 // used up. 357 358 for (unsigned int i = 0; i < fmap1.size(); i++) { 359 RPolygon *p1 = fmap1[i].p(); 360 bool is_dup = fmap1[i].isDuplicate(); 361 int parea = p1->area(); 362 p1->getColor(&r1, &g1, &b1); 363 for (unsigned int j = 0; (j < fmap2.size()) && (parea > 0); j++) { 364 int xl, yl, xh, yh; 365 RPolygon *p2 = fmap2[j].p(); 366 if (PolygonsOverlap(p1, p2, xl, yl, xh, yh)) { 367 if (!(is_dup && fmap2[j].isDuplicate())) { 368 p2->getColor(&r2, &g2, &b2); 369 myr = r1 + r2; 370 myg = g1 + g2; 371 myb = b1 + b2; 372 #ifdef _DEBUG 373 #else 374 oneapi::tbb::spin_mutex::scoped_lock lock(*m_rMutex); 375 #endif 376 (*m_resultMap).push_back(RPolygon(xl, yl, xh, yh, myr, myg, myb)); 377 } 378 parea -= (xh - xl + 1) * (yh - yl + 1); 379 } 380 } 381 } 382 } 383 384 ApplySplitOverlay(Polygon_map_t *resultMap, 385 Polygon_map_t *map1, 386 Polygon_map_t *map2, 387 oneapi::tbb::spin_mutex *rmutex) 388 : m_resultMap(resultMap), 389 m_map1(map1), 390 m_map2(map2), 391 m_rMutex(rmutex) {} 392 }; 393 394 /*! 395 * @brief intersects two maps strip-wise 396 * 397 * @param[out] resultMap output map (must be allocated) 398 * @param[in] polymap1 map to be intersected 399 * @param[in] polymap2 map to be intersected 400 */ 401 void SplitParallelOverlay(Polygon_map_t **result_map, 402 Polygon_map_t *polymap1, 403 Polygon_map_t *polymap2) { 404 int nthreads; 405 bool automatic_threadcount = false; 406 double domainSplitParallelTime; 407 oneapi::tbb::tick_count t0, t1; 408 oneapi::tbb::spin_mutex *resultMutex; 409 if (gThreadsLow == THREADS_UNSET || gThreadsLow == utility::get_default_num_threads()) { 410 gThreadsLow = gThreadsHigh = utility::get_default_num_threads(); 411 automatic_threadcount = true; 412 } 413 *result_map = new Polygon_map_t; 414 415 RPolygon *p0 = &((*polymap1)[0]); 416 int mapxSize, mapySize, ignore1, ignore2; 417 p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); 418 (*result_map)->reserve(mapxSize * mapySize); // can't be any bigger than this 419 resultMutex = new oneapi::tbb::spin_mutex(); 420 421 int grain_size; 422 #ifdef _DEBUG 423 grain_size = gMapXSize / 4; 424 #else 425 grain_size = gGrainSize; 426 #endif 427 for (nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) { 428 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, 429 nthreads); 430 if (gIsGraphicalVersion) { 431 RPolygon *xp = 432 new RPolygon(0, 0, gMapXSize - 1, gMapYSize - 1, 0, 0, 0); // Clear the output space 433 delete xp; 434 } 435 // push the map size as the first polygon, 436 (*result_map)->push_back(RPolygon(0, 0, mapxSize, mapySize)); 437 t0 = oneapi::tbb::tick_count::now(); 438 oneapi::tbb::parallel_for( 439 blocked_range_with_maps<int>(0, (int)(mapxSize + 1), grain_size, polymap1, polymap2), 440 ApplySplitOverlay((*result_map), polymap1, polymap2, resultMutex)); 441 t1 = oneapi::tbb::tick_count::now(); 442 domainSplitParallelTime = (t1 - t0).seconds() * 1000; 443 std::cout << "Splitting parallel with spin lock and "; 444 if (automatic_threadcount) 445 std::cout << "automatic"; 446 else 447 std::cout << nthreads; 448 std::cout << ((nthreads == 1) ? " thread" : " threads"); 449 std::cout << " took " << domainSplitParallelTime << " msec : speedup over serial " 450 << (gSerialTime / domainSplitParallelTime) << "\n"; 451 if (gCsvFile.is_open()) { 452 gCsvFile << "," << domainSplitParallelTime; 453 } 454 #if _DEBUG 455 CheckPolygonMap(*result_map); 456 ComparePolygonMaps(*result_map, gResultMap); 457 #endif 458 (*result_map)->clear(); 459 } 460 delete resultMutex; 461 if (gCsvFile.is_open()) { 462 gCsvFile << "\n"; 463 } 464 } 465 466 class ApplySplitOverlayCV { 467 Polygon_map_t *m_map1, *m_map2; 468 concurrent_Polygon_map_t *m_resultMap; 469 470 public: 471 /*! 472 * @brief functor for columnar parallel version 473 * @param[in] r range of map to be operated on 474 */ 475 void operator()(blocked_range_with_maps<int> &r) const { 476 // get yMapSize 477 int r1, g1, b1, r2, g2, b2; 478 int myr = -1; 479 int myg = -1; 480 int myb = -1; 481 int i1, i2, i3, yMapSize; 482 (*m_map1)[0].get(&i1, &i2, &i3, &yMapSize); 483 484 Flagged_map_t &fmap1 = r.map1(); 485 Flagged_map_t &fmap2 = r.map2(); 486 487 // When intersecting polygons from fmap1 and fmap2, if BOTH are flagged 488 // as duplicate, don't add the result to the output map. We can still 489 // intersect them, because we are keeping track of how much of the polygon 490 // is left over from intersecting, and quitting when the polygon is 491 // used up. 492 493 for (unsigned int i = 0; i < fmap1.size(); i++) { 494 RPolygon *p1 = fmap1[i].p(); 495 bool is_dup = fmap1[i].isDuplicate(); 496 int parea = p1->area(); 497 p1->getColor(&r1, &g1, &b1); 498 for (unsigned int j = 0; (j < fmap2.size()) && (parea > 0); j++) { 499 int xl, yl, xh, yh; 500 RPolygon *p2 = fmap2[j].p(); 501 if (PolygonsOverlap(p1, p2, xl, yl, xh, yh)) { 502 if (!(is_dup && fmap2[j].isDuplicate())) { 503 p2->getColor(&r2, &g2, &b2); 504 myr = r1 + r2; 505 myg = g1 + g2; 506 myb = b1 + b2; 507 (*m_resultMap).push_back(RPolygon(xl, yl, xh, yh, myr, myg, myb)); 508 } 509 parea -= (xh - xl + 1) * (yh - yl + 1); 510 } 511 } 512 } 513 } 514 515 ApplySplitOverlayCV(concurrent_Polygon_map_t *resultMap, 516 Polygon_map_t *map1, 517 Polygon_map_t *map2) 518 : m_resultMap(resultMap), 519 m_map1(map1), 520 m_map2(map2) {} 521 }; 522 523 /*! 524 * @brief intersects two maps strip-wise, accumulating into a concurrent_vector 525 * 526 * @param[out] resultMap output map (must be allocated) 527 * @param[in] polymap1 map to be intersected 528 * @param[in] polymap2 map to be intersected 529 */ 530 void SplitParallelOverlayCV(concurrent_Polygon_map_t **result_map, 531 Polygon_map_t *polymap1, 532 Polygon_map_t *polymap2) { 533 int nthreads; 534 bool automatic_threadcount = false; 535 double domainSplitParallelTime; 536 oneapi::tbb::tick_count t0, t1; 537 if (gThreadsLow == THREADS_UNSET || gThreadsLow == utility::get_default_num_threads()) { 538 gThreadsLow = gThreadsHigh = utility::get_default_num_threads(); 539 automatic_threadcount = true; 540 } 541 *result_map = new concurrent_Polygon_map_t; 542 543 RPolygon *p0 = &((*polymap1)[0]); 544 int mapxSize, mapySize, ignore1, ignore2; 545 p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); 546 // (*result_map)->reserve(mapxSize*mapySize); // can't be any bigger than this 547 548 int grain_size; 549 #ifdef _DEBUG 550 grain_size = gMapXSize / 4; 551 #else 552 grain_size = gGrainSize; 553 #endif 554 for (nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) { 555 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, 556 nthreads); 557 if (gIsGraphicalVersion) { 558 RPolygon *xp = 559 new RPolygon(0, 0, gMapXSize - 1, gMapYSize - 1, 0, 0, 0); // Clear the output space 560 delete xp; 561 } 562 // push the map size as the first polygon, 563 (*result_map)->push_back(RPolygon(0, 0, mapxSize, mapySize)); 564 t0 = oneapi::tbb::tick_count::now(); 565 oneapi::tbb::parallel_for( 566 blocked_range_with_maps<int>(0, (int)(mapxSize + 1), grain_size, polymap1, polymap2), 567 ApplySplitOverlayCV((*result_map), polymap1, polymap2)); 568 t1 = oneapi::tbb::tick_count::now(); 569 domainSplitParallelTime = (t1 - t0).seconds() * 1000; 570 std::cout << "Splitting parallel with concurrent_vector and "; 571 if (automatic_threadcount) 572 std::cout << "automatic"; 573 else 574 std::cout << nthreads; 575 std::cout << ((nthreads == 1) ? " thread" : " threads"); 576 std::cout << " took " << domainSplitParallelTime << " msec : speedup over serial " 577 << (gSerialTime / domainSplitParallelTime) << "\n"; 578 if (gCsvFile.is_open()) { 579 gCsvFile << "," << domainSplitParallelTime; 580 } 581 #if _DEBUG 582 { 583 Polygon_map_t s_result_map; 584 for (concurrent_Polygon_map_t::const_iterator i = (*result_map)->begin(); 585 i != (*result_map)->end(); 586 ++i) { 587 s_result_map.push_back(*i); 588 } 589 CheckPolygonMap(&s_result_map); 590 ComparePolygonMaps(&s_result_map, gResultMap); 591 } 592 #endif 593 (*result_map)->clear(); 594 } 595 596 if (gCsvFile.is_open()) { 597 gCsvFile << "\n"; 598 } 599 } 600 601 // ------------------------------------------------------ 602 603 class ApplySplitOverlayETS { 604 Polygon_map_t *m_map1, *m_map2; 605 ETS_Polygon_map_t *m_resultMap; 606 607 public: 608 /*! 609 * @brief functor for columnar parallel version 610 * @param[in] r range of map to be operated on 611 */ 612 void operator()(blocked_range_with_maps<int> &r) const { 613 // get yMapSize 614 int r1, g1, b1, r2, g2, b2; 615 int myr = -1; 616 int myg = -1; 617 int myb = -1; 618 int i1, i2, i3, yMapSize; 619 (*m_map1)[0].get(&i1, &i2, &i3, &yMapSize); 620 621 Flagged_map_t &fmap1 = r.map1(); 622 Flagged_map_t &fmap2 = r.map2(); 623 624 // When intersecting polygons from fmap1 and fmap2, if BOTH are flagged 625 // as duplicate, don't add the result to the output map. We can still 626 // intersect them, because we are keeping track of how much of the polygon 627 // is left over from intersecting, and quitting when the polygon is 628 // used up. 629 630 for (unsigned int i = 0; i < fmap1.size(); i++) { 631 RPolygon *p1 = fmap1[i].p(); 632 bool is_dup = fmap1[i].isDuplicate(); 633 int parea = p1->area(); 634 p1->getColor(&r1, &g1, &b1); 635 for (unsigned int j = 0; (j < fmap2.size()) && (parea > 0); j++) { 636 int xl, yl, xh, yh; 637 RPolygon *p2 = fmap2[j].p(); 638 if (PolygonsOverlap(p1, p2, xl, yl, xh, yh)) { 639 if (!(is_dup && fmap2[j].isDuplicate())) { 640 p2->getColor(&r2, &g2, &b2); 641 myr = r1 + r2; 642 myg = g1 + g2; 643 myb = b1 + b2; 644 (*m_resultMap).local().push_back(RPolygon(xl, yl, xh, yh, myr, myg, myb)); 645 } 646 parea -= (xh - xl + 1) * (yh - yl + 1); 647 } 648 } 649 } 650 } 651 652 ApplySplitOverlayETS(ETS_Polygon_map_t *resultMap, Polygon_map_t *map1, Polygon_map_t *map2) 653 : m_resultMap(resultMap), 654 m_map1(map1), 655 m_map2(map2) {} 656 }; 657 658 /*! 659 * @brief intersects two maps strip-wise, accumulating into an ets variable 660 * 661 * @param[out] resultMap output map (must be allocated) 662 * @param[in] polymap1 map to be intersected 663 * @param[in] polymap2 map to be intersected 664 */ 665 void SplitParallelOverlayETS(ETS_Polygon_map_t **result_map, 666 Polygon_map_t *polymap1, 667 Polygon_map_t *polymap2) { 668 int nthreads; 669 bool automatic_threadcount = false; 670 double domainSplitParallelTime; 671 oneapi::tbb::tick_count t0, t1; 672 if (gThreadsLow == THREADS_UNSET || gThreadsLow == utility::get_default_num_threads()) { 673 gThreadsLow = gThreadsHigh = utility::get_default_num_threads(); 674 automatic_threadcount = true; 675 } 676 *result_map = new ETS_Polygon_map_t; 677 678 RPolygon *p0 = &((*polymap1)[0]); 679 int mapxSize, mapySize, ignore1, ignore2; 680 p0->get(&ignore1, &ignore2, &mapxSize, &mapySize); 681 // (*result_map)->reserve(mapxSize*mapySize); // can't be any bigger than this 682 683 int grain_size; 684 #ifdef _DEBUG 685 grain_size = gMapXSize / 4; 686 #else 687 grain_size = gGrainSize; 688 #endif 689 for (nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) { 690 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, 691 nthreads); 692 if (gIsGraphicalVersion) { 693 RPolygon *xp = 694 new RPolygon(0, 0, gMapXSize - 1, gMapYSize - 1, 0, 0, 0); // Clear the output space 695 delete xp; 696 } 697 // push the map size as the first polygon, 698 // This polygon needs to be first, so we can push it at the start of a combine. 699 // (*result_map)->local.push_back(RPolygon(0,0,mapxSize, mapySize)); 700 t0 = oneapi::tbb::tick_count::now(); 701 oneapi::tbb::parallel_for( 702 blocked_range_with_maps<int>(0, (int)(mapxSize + 1), grain_size, polymap1, polymap2), 703 ApplySplitOverlayETS((*result_map), polymap1, polymap2)); 704 t1 = oneapi::tbb::tick_count::now(); 705 domainSplitParallelTime = (t1 - t0).seconds() * 1000; 706 std::cout << "Splitting parallel with ETS and "; 707 if (automatic_threadcount) 708 std::cout << "automatic"; 709 else 710 std::cout << nthreads; 711 std::cout << ((nthreads == 1) ? " thread" : " threads"); 712 std::cout << " took " << domainSplitParallelTime << " msec : speedup over serial " 713 << (gSerialTime / domainSplitParallelTime) << "\n"; 714 if (gCsvFile.is_open()) { 715 gCsvFile << "," << domainSplitParallelTime; 716 } 717 #if _DEBUG 718 { 719 Polygon_map_t s_result_map; 720 oneapi::tbb::flattened2d<ETS_Polygon_map_t> psv = flatten2d(**result_map); 721 s_result_map.push_back(RPolygon(0, 0, mapxSize, mapySize)); 722 for (oneapi::tbb::flattened2d<ETS_Polygon_map_t>::const_iterator ci = psv.begin(); 723 ci != psv.end(); 724 ++ci) { 725 s_result_map.push_back(*ci); 726 } 727 CheckPolygonMap(&s_result_map); 728 ComparePolygonMaps(&s_result_map, gResultMap); 729 } 730 #endif 731 (*result_map)->clear(); 732 } 733 734 if (gCsvFile.is_open()) { 735 gCsvFile << "\n"; 736 } 737 } 738