#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdlib>
#include <assert.h>
#include "tbb/tick_count.h"
#include "tbb/blocked_range.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/mutex.h"
#include "tbb/spin_mutex.h"
#include "polyover.h"
#include "polymain.h"
#include "pover_video.h"

Include dependency graph for polyover.cpp:

Classes
class	ApplyOverlay
	Simple version of parallel overlay (make parallel on polygons in map1)
class	ApplySplitOverlay
	parallel by columnar strip
Functions
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

Function Documentation

void NaiveParallelOverlay	(	Polygon_map_t *&	result_map,
		Polygon_map_t &	polymap1,
		Polygon_map_t &	polymap2
	)

Parameters:

[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
	)

Parameters:

[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
	)

Parameters:

[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
	)

Parameters:

[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;
    }

}

Classes

Functions

Function Documentation