 |
Shadowrun: Awakened 29 September 2011 - Build 871
|
|
Shadowrun: Awakened 29 September 2011 - Build 871
|
#include "rpolygon.h"#include "tbb/mutex.h"#include "tbb/spin_mutex.h"
Include dependency graph for polyover.h: This graph shows which files directly or indirectly include this file:Go to the source code of this file.
Functions | |
| void | CheckPolygonMap (Polygon_map_t *checkMap) |
| bool | ComparePolygonMaps (Polygon_map_t *map1, Polygon_map_t *map2) |
| void | NaiveParallelOverlay (Polygon_map_t *&result_map, Polygon_map_t &polymap1, Polygon_map_t &polymap2) |
| apply the parallel algorithm | |
| void | OverlayOnePolygonWithMap (Polygon_map_t *resultMap, RPolygon *myPoly, Polygon_map_t *map2, tbb::spin_mutex *rMutex) |
| intersects a polygon with a map, adding any results to output map | |
| void | SerialOverlayMaps (Polygon_map_t **resultMap, Polygon_map_t *map1, Polygon_map_t *map2) |
| Serial version of polygon overlay. | |
| void | SplitParallelOverlay (Polygon_map_t **result_map, Polygon_map_t *polymap1, Polygon_map_t *polymap2) |
| intersects two maps strip-wise | |
| void CheckPolygonMap | ( | Polygon_map_t * | checkMap | ) |
Definition at line 490 of file polymain.cpp.
References gMapXSize, gMapYSize, indx, xRangeCheck, and yRangeCheck.
Referenced by NaiveParallelOverlay(), and SplitParallelOverlay().
{
#define indx(i,j) (i*gMapYSize + j)
#define rangeCheck(str,n,limit) if(((n)<0)||((n)>=limit)) {cout << "checkMap error: " << str << " out of range (" << n << ")" << std::endl;anError=true;}
#define xRangeCheck(str,n) rangeCheck(str,n,gMapXSize)
#define yRangeCheck(str,n) rangeCheck(str,n,gMapYSize)
// The first polygon is the whole map.
bool anError = false;
int *cArray;
if(checkMap->size() <= 0) {
cout << "checkMap error: no polygons in map" << std::endl;
return;
}
// mapXhigh and mapYhigh are inclusive, that is, if the map is 5x5, those values would be 4.
int mapXhigh, mapYhigh, mapLowX, mapLowY;
int gMapXSize, gMapYSize;
checkMap->at(0)->get(&mapLowX, &mapLowY, &mapXhigh, &mapYhigh);
if((mapLowX !=0) || (mapLowY != 0)) {
cout << "checkMap error: map origin not (0,0) (X=" << mapLowX << ", Y=" << mapLowY << ")" << std::endl;
anError = true;
}
if((mapXhigh < 0) || (mapYhigh < 0)) {
cout << "checkMap error: no area in map (X=" << mapXhigh << ", Y=" << mapYhigh << ")" << std::endl;
anError = true;
}
if(anError) return;
// bounds for array.
gMapXSize = mapXhigh + 1;
gMapYSize = mapYhigh + 1;
cArray = (int *)malloc(sizeof(int)*(gMapXSize*gMapYSize));
for(int i=0; i<gMapXSize; i++) {
for(int j=0; j< gMapYSize; j++) {
cArray[indx(i,j)] = 0;
}
}
int xlow, xhigh, ylow, yhigh;
for(int p=1; p < int(checkMap->size()) && !anError; p++) {
checkMap->at(p)->get(&xlow, &ylow, &xhigh, &yhigh);
xRangeCheck("xlow", xlow);
yRangeCheck("ylow", ylow);
xRangeCheck("xhigh", xhigh);
yRangeCheck("yhigh", yhigh);
if(xlow>xhigh) {
cout << "checkMap error: xlow > xhigh (" << xlow << "," << xhigh << ")" << std::endl;
anError = true;
}
if(ylow>yhigh) {
cout << "checkMap error: ylow > yhigh (" << ylow << "," << yhigh << ")" << std::endl;
anError = true;
}
for(int ii = xlow; ii <= xhigh; ii++) {
for(int jj = ylow; jj <= yhigh; jj++) {
if(cArray[indx(ii,jj)] != 0) {
cout << "checkMap error: polygons " << cArray[indx(ii,jj)] << " and " << p << " intersect" << std::endl;
anError = true;
}
cArray[indx(ii,jj)] = p;
}
}
}
for(int ii=0; ii < gMapXSize; ii++) {
for(int jj=0; jj < gMapYSize; jj++) {
if(cArray[indx(ii,jj)] == 0) {
cout << "checkMap error: block(" << ii << ", " << jj << ") not in any polygon" << std::endl;
anError = true;
}
}
}
free(cArray);
}
| bool ComparePolygonMaps | ( | Polygon_map_t * | map1, |
| Polygon_map_t * | map2 | ||
| ) |
Definition at line 580 of file polymain.cpp.
References CompOnePolygon(), and PolygonsEqual().
Referenced by NaiveParallelOverlay(), and SplitParallelOverlay().
{
// create two new polygon maps, copy the pointers from the original to these.
// we have to skip the first polygon, which is the size of the whole map
Polygon_map_t *t1, *t2;
bool is_ok = true;
t1 = new Polygon_map_t;
t1->reserve(map1->size());
for(unsigned int i=1;i<map1->size(); i++) {
t1->push_back(map1->at(i));
}
t2 = new Polygon_map_t;
t2->reserve(map2->size());
for(unsigned int i=1;i<map2->size();i++) {
t2->push_back(map2->at(i));
}
// sort the two created maps by (xlow, ylow)
sort(t1->begin(), t1->end(), CompOnePolygon);
sort(t2->begin(), t2->end(), CompOnePolygon);
// compare each element of both maps.
if(t1->size() != t2->size()) {
cout << "Error: maps not the same size ( " << int(t1->size()) << " vs " << int(t2->size()) << ")." << std::endl;
}
int maxSize = (int)((t1->size() < t2->size()) ? t1->size() : t2->size());
for(int i=0; i < maxSize; i++) {
if(!PolygonsEqual(t1->at(i), t2->at(i))) {
cout << "Error: polygons unequal (" << *(t1->at(i)) << " vs " << (*t2->at(i)) << std::endl;
is_ok = false;
}
}
delete t1;
delete t2;
return is_ok;
}
| void NaiveParallelOverlay | ( | Polygon_map_t *& | result_map, |
| Polygon_map_t & | polymap1, | ||
| Polygon_map_t & | polymap2 | ||
| ) |
| [out] | result_map | generated map |
| [in] | polymap1 | first map to be applied (algorithm is parallel on this map) |
| [in] | polymap2 | second map. |
Definition at line 144 of file polyover.cpp.
References RPolygon::alloc_RPolygon(), tbb::task_scheduler_init::automatic, CheckPolygonMap(), ComparePolygonMaps(), RPolygon::free_RPolygon(), gCsvFile, RPolygon::get(), gGrainSize, gIsGraphicalVersion, gMapXSize, gMapYSize, gResultMap, gSerialTime, gThreadsHigh, gThreadsLow, tbb::tick_count::now(), tbb::parallel_for(), t0, and THREADS_UNSET.
{
// -----------------------------------
bool automatic_threadcount = false;
if(gThreadsLow == THREADS_UNSET || gThreadsLow == tbb::task_scheduler_init::automatic) {
gThreadsLow = gThreadsHigh = tbb::task_scheduler_init::automatic;
automatic_threadcount = true;
}
result_map = new Polygon_map_t;
RPolygon *p0 = polymap1[0];
int mapxSize, mapySize, ignore1, ignore2;
p0->get(&ignore1, &ignore2, &mapxSize, &mapySize);
result_map->reserve(mapxSize*mapySize); // can't be any bigger than this
// push the map size as the first polygon,
tbb::spin_mutex *resultMutex = new tbb::spin_mutex();
int grain_size = gGrainSize;
for(int nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) {
tbb::task_scheduler_init init(nthreads);
if(gIsGraphicalVersion) {
RPolygon *xp = RPolygon::alloc_RPolygon(0, 0, gMapXSize-1, gMapYSize-1, 0, 0, 0); // Clear the output space
RPolygon::free_RPolygon( xp );
}
// put size polygon in result map
p0 = RPolygon::alloc_RPolygon(0,0,mapxSize, mapySize);
result_map->push_back(p0);
tbb::tick_count t0 = tbb::tick_count::now();
tbb::parallel_for (tbb::blocked_range<int>(1,(int)(polymap1.size()),grain_size), ApplyOverlay(result_map, &polymap1, &polymap2, resultMutex));
tbb::tick_count t1 = tbb::tick_count::now();
double naiveParallelTime = (t1-t0).seconds() * 1000;
cout << "Naive parallel with spin lock and ";
if(automatic_threadcount) cout << "automatic";
else cout << nthreads;
cout << ((nthreads == 1) ? " thread" : " threads");
cout << " took " << naiveParallelTime << " msec : speedup over serial " << (gSerialTime / naiveParallelTime) << std::endl;
if(gCsvFile.is_open()) {
gCsvFile << "," << naiveParallelTime;
}
#if _DEBUG
CheckPolygonMap(result_map);
ComparePolygonMaps(result_map, gResultMap);
#endif
for(int i=0; i<int(result_map->size());i++) {
RPolygon::free_RPolygon(result_map->at(i));
}
result_map->clear();
}
delete resultMutex;
if(gCsvFile.is_open()) {
gCsvFile << std::endl;
}
// -----------------------------------
}
| void OverlayOnePolygonWithMap | ( | Polygon_map_t * | resultMap, |
| RPolygon * | myPoly, | ||
| Polygon_map_t * | map2, | ||
| tbb::spin_mutex * | rMutex | ||
| ) |
polyover.h : extern declarations for polyover.cpp
| [out] | resultMap | output map (must be allocated) |
| [in] | polygon | to be intersected |
| [in] | map | intersected against |
| [in] | lock | to use when adding output polygons to result map |
Definition at line 57 of file polyover.cpp.
References RPolygon::alloc_RPolygon(), RPolygon::area(), RPolygon::getColor(), PolygonsOverlap(), and RPolygon::print().
Referenced by SerialOverlayMaps().
{
int r1, g1, b1, r2, g2, b2;
int myr=0;
int myg=0;
int myb=0;
int p1Area = myPoly->area();
for(unsigned int j=1; (j < map2->size()) && (p1Area > 0); j++) {
RPolygon *p2 = (*map2)[j];
RPolygon *pnew;
int newxMin, newxMax, newyMin, newyMax;
myPoly->getColor(&r1, &g1, &b1);
if(PolygonsOverlap(myPoly, p2, newxMin, newyMin, newxMax, newyMax)) {
p2->getColor(&r2, &g2, &b2);
myr = r1 + r2;
myg = g1 + g2;
myb = b1 + b2;
pnew = RPolygon::alloc_RPolygon(newxMin, newyMin, newxMax, newyMax, myr, myg, myb);
p1Area -= pnew->area(); // when all the area of the polygon is accounted for, we can quit.
if(rMutex) {
tbb::spin_mutex::scoped_lock lock(*rMutex);
#if _DEBUG
pnew->print(int(resultMap->size()));
#endif
resultMap->push_back(pnew);
}
else {
#ifdef _DEBUG
pnew->print(int(resultMap->size()));
#endif
resultMap->push_back(pnew);
}
}
}
}
| void SerialOverlayMaps | ( | Polygon_map_t ** | resultMap, |
| Polygon_map_t * | map1, | ||
| Polygon_map_t * | map2 | ||
| ) |
| [out] | output | map |
| [in] | first | map (map that individual polygons are taken from) |
| [in] | second | map (map passed to OverlayOnePolygonWithMap) |
Definition at line 98 of file polyover.cpp.
References RPolygon::alloc_RPolygon(), RPolygon::get(), and OverlayOnePolygonWithMap().
{
cout << "SerialOverlayMaps called" << std::endl;
*resultMap = new Polygon_map_t;
RPolygon *p0 = (*map1)[0];
int mapxSize, mapySize, ignore1, ignore2;
p0->get(&ignore1, &ignore2, &mapxSize, &mapySize);
(*resultMap)->reserve(mapxSize*mapySize); // can't be any bigger than this
// push the map size as the first polygon,
p0 = RPolygon::alloc_RPolygon(0,0,mapxSize, mapySize);
(*resultMap)->push_back(p0);
for(unsigned int i=1; i < map1->size(); i++) {
RPolygon *p1 = (*map1)[i];
OverlayOnePolygonWithMap(*resultMap, p1, map2, NULL);
}
}
| void SplitParallelOverlay | ( | Polygon_map_t ** | result_map, |
| Polygon_map_t * | polymap1, | ||
| Polygon_map_t * | polymap2 | ||
| ) |
| [out] | resultMap | output map (must be allocated) |
| [in] | polymap1 | map to be intersected |
| [in] | polymap2 | map to be intersected |
Definition at line 347 of file polyover.cpp.
References RPolygon::alloc_RPolygon(), tbb::task_scheduler_init::automatic, CheckPolygonMap(), ComparePolygonMaps(), RPolygon::free_RPolygon(), gCsvFile, RPolygon::get(), gGrainSize, gIsGraphicalVersion, gMapXSize, gMapYSize, gResultMap, gSerialTime, gThreadsHigh, gThreadsLow, tbb::tick_count::now(), tbb::parallel_for(), t0, and THREADS_UNSET.
{
int nthreads;
bool automatic_threadcount = false;
double domainSplitParallelTime;
tbb::tick_count t0, t1;
tbb::spin_mutex *resultMutex;
if(gThreadsLow == THREADS_UNSET || gThreadsLow == tbb::task_scheduler_init::automatic ) {
gThreadsLow = gThreadsHigh = tbb::task_scheduler_init::automatic;
automatic_threadcount = true;
}
*result_map = new Polygon_map_t;
RPolygon *p0 = (*polymap1)[0];
int mapxSize, mapySize, ignore1, ignore2;
p0->get(&ignore1, &ignore2, &mapxSize, &mapySize);
(*result_map)->reserve(mapxSize*mapySize); // can't be any bigger than this
resultMutex = new tbb::spin_mutex();
int grain_size;
#ifdef _DEBUG
grain_size = gMapXSize / 4;
#else
grain_size = gGrainSize;
#endif
for(nthreads = gThreadsLow; nthreads <= gThreadsHigh; nthreads++) {
tbb::task_scheduler_init init(nthreads);
if(gIsGraphicalVersion) {
RPolygon *xp = RPolygon::alloc_RPolygon(0, 0, gMapXSize-1, gMapYSize-1, 0, 0, 0); // Clear the output space
RPolygon::free_RPolygon( xp );
}
// push the map size as the first polygon,
p0 = RPolygon::alloc_RPolygon(0,0,mapxSize, mapySize);
(*result_map)->push_back(p0);
t0 = tbb::tick_count::now();
tbb::parallel_for (tbb::blocked_range<int>(0,(int)(mapxSize+1),grain_size), ApplySplitOverlay((*result_map), polymap1, polymap2, resultMutex));
t1 = tbb::tick_count::now();
domainSplitParallelTime = (t1-t0).seconds()*1000;
cout << "Splitting parallel with spin lock and ";
if(automatic_threadcount) cout << "automatic";
else cout << nthreads;
cout << ((nthreads == 1) ? " thread" : " threads");
cout << " took " << domainSplitParallelTime << " msec : speedup over serial " << (gSerialTime / domainSplitParallelTime) << std::endl;
if(gCsvFile.is_open()) {
gCsvFile << "," << domainSplitParallelTime;
}
#if _DEBUG
CheckPolygonMap(*result_map);
ComparePolygonMaps(*result_map, gResultMap);
#endif
for(int i=0; i<int((*result_map)->size());i++) {
RPolygon::free_RPolygon((*result_map)->at(i));
}
(*result_map)->clear();
}
delete resultMutex;
if(gCsvFile.is_open()) {
gCsvFile << std::endl;
}
}
Copyright © 2007-2010 by The Shadowrun: Awakened Team. This work is licensed under the GNU Lesser General Public License 3.
 |