From: <rt...@us...> - 2009-06-06 07:25:26
|
Revision: 7796 http://playerstage.svn.sourceforge.net/playerstage/?rev=7796&view=rev Author: rtv Date: 2009-06-06 07:24:49 +0000 (Sat, 06 Jun 2009) Log Message: ----------- cleaning up raytrace code in a bug hunt. performance dropped a little, traded for type safety Modified Paths: -------------- code/stage/trunk/libstage/region.cc code/stage/trunk/libstage/region.hh code/stage/trunk/libstage/stage.hh code/stage/trunk/libstage/world.cc Modified: code/stage/trunk/libstage/region.cc =================================================================== --- code/stage/trunk/libstage/region.cc 2009-06-06 01:27:44 UTC (rev 7795) +++ code/stage/trunk/libstage/region.cc 2009-06-06 07:24:49 UTC (rev 7796) @@ -7,18 +7,12 @@ #include "region.hh" using namespace Stg; -const uint32_t Region::WIDTH = REGIONWIDTH; -const uint32_t Region::SIZE = REGIONSIZE; -const uint32_t SuperRegion::WIDTH = SUPERREGIONWIDTH; -const uint32_t SuperRegion::SIZE = SUPERREGIONSIZE; - - Region::Region() - : cells(NULL), count(0) + : cells(), count(0) { - //for( unsigned int i=0; i<Region::SIZE; i++ ) - //cells[i].region = this; + for( int i=0; i<REGIONSIZE; i++ ) + cells[i].region = this; } Region::~Region() @@ -27,7 +21,20 @@ delete[] cells; } +void Region::DecrementOccupancy() +{ + assert( superregion ); + superregion->DecrementOccupancy(); + --count; +} +void Region::IncrementOccupancy() +{ + assert( superregion ); + superregion->IncrementOccupancy(); + ++count; +} + SuperRegion::SuperRegion( World* world, stg_point_int_t origin ) : count(0), origin(origin), world(world) { @@ -36,7 +43,7 @@ // printf( "superregion at %d %d\n", origin.x, origin.y ); // initialize the parent pointer for all my child regions - for( unsigned int i=0; i<SuperRegion::SIZE; i++ ) + for( int i=0; i<SUPERREGIONSIZE; i++ ) regions[i].superregion = this; } @@ -60,10 +67,10 @@ // outline regions glColor3f( 0,1,0 ); - for( unsigned int x=0; x<SuperRegion::WIDTH; x++ ) - for( unsigned int y=0; y<SuperRegion::WIDTH; y++ ) + for( int x=0; x<SUPERREGIONWIDTH; x++ ) + for( int y=0; y<SUPERREGIONWIDTH; y++ ) { - Region* r = GetRegionLocal(x,y); + const Region* r = GetRegion(x,y); if( r->count ) // outline regions with contents @@ -120,10 +127,10 @@ glColor3f( 1.0,0,0 ); - for( unsigned int x=0; x<SuperRegion::WIDTH; x++ ) - for( unsigned int y=0; y<SuperRegion::WIDTH; y++ ) + for( int x=0; x<SUPERREGIONWIDTH; x++ ) + for( int y=0; y<SUPERREGIONWIDTH; y++ ) { - Region* r = GetRegionLocal( x, y); + const Region* r = GetRegion( x, y); if( r->count < 1 ) continue; @@ -131,9 +138,9 @@ snprintf( buf, 15, "%lu", r->count ); Gl::draw_string( x<<RBITS, y<<RBITS, 0, buf ); - for( unsigned int p=0; p<Region::WIDTH; p++ ) - for( unsigned int q=0; q<Region::WIDTH; q++ ) - if( r->cells[p+(q*Region::WIDTH)].blocks.size() ) + for( int p=0; p<REGIONWIDTH; p++ ) + for( int q=0; q<REGIONWIDTH; q++ ) + if( r->cells[p+(q*REGIONWIDTH)].blocks.size() ) { GLfloat xx = p+(x<<RBITS); GLfloat yy = q+(y<<RBITS); @@ -145,12 +152,12 @@ } else // draw a rectangular solid { - Cell* c = &r->cells[p+(q*Region::WIDTH)]; + Cell* c = (Cell*)&r->cells[p+(q*REGIONWIDTH)]; for( std::vector<Block*>::iterator it = c->blocks.begin(); it != c->blocks.end(); ++it ) { - Block* block = *it;//(Block*)it->data; + Block* block = *it; //printf( "zb %.2f %.2f\n", ent->zbounds.min, ent->zbounds.max ); Modified: code/stage/trunk/libstage/region.hh =================================================================== --- code/stage/trunk/libstage/region.hh 2009-06-06 01:27:44 UTC (rev 7795) +++ code/stage/trunk/libstage/region.hh 2009-06-06 07:24:49 UTC (rev 7796) @@ -14,17 +14,27 @@ { // a bit of experimenting suggests that these values are fast. YMMV. -#define RBITS 4 // regions contain (2^RBITS)^2 pixels -#define SBITS 5 // superregions contain (2^SBITS)^2 regions -#define SRBITS (RBITS+SBITS) + const int32_t RBITS( 4 ); // regions contain (2^RBITS)^2 pixels + const int32_t SBITS( 5 );// superregions contain (2^SBITS)^2 regions + const int32_t SRBITS( RBITS+SBITS ); + + const int32_t REGIONWIDTH( 1<<RBITS ); + const int32_t REGIONSIZE( REGIONWIDTH*REGIONWIDTH ); -#define REGIONWIDTH (1<<RBITS) -#define REGIONSIZE REGIONWIDTH*REGIONWIDTH + const int32_t SUPERREGIONWIDTH( 1<<SBITS ); + const int32_t SUPERREGIONSIZE( SUPERREGIONWIDTH*SUPERREGIONWIDTH ); + + /** (x & CELLMASK) converts a global cell index into a local cell + index in a region */ + const int32_t CELLMASK( ~((~0x00)<< RBITS )); + /** (x & REGIONMASK)converts a global cell index into a local cell + index in a region */ + const int32_t REGIONMASK( ~((~0x00)<< SRBITS )); + + inline int32_t GETCELL( const int32_t x ) { return( x & CELLMASK); } + inline int32_t GETREG( const int32_t x ) { return( ( x & REGIONMASK ) >> RBITS); } + inline int32_t GETSREG( const int32_t x ) { return( x >> SRBITS); } -#define SUPERREGIONWIDTH (1<<SBITS) -#define SUPERREGIONSIZE SUPERREGIONWIDTH*SUPERREGIONWIDTH - - class Cell { friend class Region; @@ -44,87 +54,38 @@ { } - inline void RemoveBlock( Block* b ); - inline void AddBlock( Block* b ); - inline void AddBlockNoRecord( Block* b ); + void RemoveBlock( Block* b ); + void AddBlock( Block* b ); + void AddBlockNoRecord( Block* b ); }; - class Region { public: - Cell* cells; - SuperRegion* superregion; - - static const uint32_t WIDTH; - static const uint32_t SIZE; - - static int32_t CELL( const int32_t x ) - { - const int32_t _cell_coord_mask = ~ ( ( ~ 0x00 ) << RBITS ); - return( x & _cell_coord_mask ); - } - + Cell cells[ REGIONSIZE ]; + SuperRegion* superregion; unsigned long count; // number of blocks rendered into these cells Region(); ~Region(); - Cell* GetCellCreate( int32_t x, int32_t y ) + Cell* GetCell( int32_t x, int32_t y ) const { - if( ! cells ) - { - cells = new Cell[REGIONSIZE]; - for( unsigned int i=0; i<Region::SIZE; i++ ) - cells[i].region = this; - } - return( &cells[CELL(x) + (CELL(y)*Region::WIDTH)] ); + return( (Cell*)&cells[ x + (y*REGIONWIDTH) ] ); } - - Cell* GetCellGlobalCreate( const stg_point_int_t& c ) - { - if( ! cells ) - { - cells = new Cell[REGIONSIZE]; - for( unsigned int i=0; i<Region::SIZE; i++ ) - cells[i].region = this; - } - return( &cells[CELL(c.x) + (CELL(c.y)*Region::WIDTH)] ); - } - - Cell* GetCellGlobalNoCreate( int32_t x, int32_t y ) const - { - return( &cells[CELL(x) + (CELL(y)*Region::WIDTH)] ); - } - - Cell* GetCellLocallNoCreate( int32_t x, int32_t y ) const - { - return( &cells[x + y*Region::WIDTH] ); - } - - - Cell* GetCellGlobalNoCreate( const stg_point_int_t& c ) const - { - return( &cells[CELL(c.x) + (CELL(c.y)*Region::WIDTH)] ); - } - - - - void DecrementOccupancy(); - void IncrementOccupancy(); + + void DecrementOccupancy(); + void IncrementOccupancy(); }; - - class SuperRegion + class SuperRegion { - friend class World; - friend class Model; + friend class World; + friend class Model; private: - static const uint32_t WIDTH; - static const uint32_t SIZE; - + Region regions[SUPERREGIONSIZE]; unsigned long count; // number of blocks rendered into these regions @@ -133,31 +94,14 @@ public: - static int32_t REGION( const int32_t x ) - { - const int32_t _region_coord_mask = ~ ( ( ~ 0x00 ) << SRBITS ); - return( ( x & _region_coord_mask ) >> RBITS ); - } - - SuperRegion( World* world, stg_point_int_t origin ); ~SuperRegion(); - - Region* GetRegionGlobal( int32_t x, int32_t y ) - { - return( ®ions[ REGION(x) + (REGION(y)*SuperRegion::WIDTH) ] ); - } - - Region* GetRegionLocal( int32_t x, int32_t y ) - { - return( ®ions[ x + (y*SuperRegion::WIDTH) ] ); - } - - Region* GetRegionGlobal( const stg_point_int_t& r ) - { - return( ®ions[ REGION(r.x) + (REGION(r.y)*SuperRegion::WIDTH) ] ); - } - + + const Region* GetRegion( int32_t x, int32_t y ) const + { + return( ®ions[ x + (y*SUPERREGIONWIDTH) ] ); + } + void Draw( bool drawall ); void Floor(); @@ -165,21 +109,8 @@ void IncrementOccupancy(){ ++count; }; }; -inline void Region::DecrementOccupancy() -{ - assert( superregion ); - superregion->DecrementOccupancy(); - --count; -}; -inline void Region::IncrementOccupancy() -{ - assert( superregion ); - superregion->IncrementOccupancy(); - ++count; -} - -inline void printvec( std::vector<Block*>& vec ) +inline void printvec( std::vector<Block*>& vec ) { printf( "Vec: "); for( size_t i=0; i<vec.size(); i++ ) Modified: code/stage/trunk/libstage/stage.hh =================================================================== --- code/stage/trunk/libstage/stage.hh 2009-06-06 01:27:44 UTC (rev 7795) +++ code/stage/trunk/libstage/stage.hh 2009-06-06 07:24:49 UTC (rev 7796) @@ -999,10 +999,10 @@ SuperRegion* GetSuperRegionCached( int32_t x, int32_t y ); void ExpireSuperRegion( SuperRegion* sr ); - inline Cell* GetCellNoCreate( const stg_point_int_t& glob ); - inline Cell* GetCellNoCreate( const int32_t x, const int32_t y ); + inline Cell* GetCell( const stg_point_int_t& glob ); + //inline Cell* GetCellNoCreate( const int32_t x, const int32_t y ); //inline Cell* GetCellCreate( const int32_t x, const int32_t y ); - inline Cell* GetCellCreate( const stg_point_int_t& glob ); + //inline Cell* GetCellCreate( const stg_point_int_t& glob ); /** add a Cell pointer to the vector for each cell on the line from pt1 to pt2 inclusive */ Modified: code/stage/trunk/libstage/world.cc =================================================================== --- code/stage/trunk/libstage/world.cc 2009-06-06 01:27:44 UTC (rev 7795) +++ code/stage/trunk/libstage/world.cc 2009-06-06 07:24:49 UTC (rev 7796) @@ -60,8 +60,8 @@ World::World( const char* token, - stg_msec_t interval_sim, - double ppm ) + stg_msec_t interval_sim, + double ppm ) : // private charge_list( NULL ), @@ -145,7 +145,7 @@ for( GList* it = World::world_list; it; it=it->next ) { if( ((World*)it->data)->Update() == false ) - quit = false; + quit = false; } return quit; } @@ -156,7 +156,7 @@ g_mutex_lock( world->thread_mutex ); -// world->update_jobs_pending--; + // world->update_jobs_pending--; // if( world->update_jobs_pending == 0 ) if( g_thread_pool_unprocessed( world->threadpool ) < 1 ) @@ -181,7 +181,7 @@ { // lookup the group in which this was defined Model* mod = (Model*)g_hash_table_lookup( entitytable, - (gpointer)wf->GetEntityParent( entity ) ); + (gpointer)wf->GetEntityParent( entity ) ); if( ! mod ) PRINT_ERR( "block has no model for a parent" ); @@ -209,11 +209,11 @@ //printf( "creating model of type %s\n", typestr ); for( int i=0; i<MODEL_TYPE_COUNT; i++ ) - if( strcmp( typestr, typetable[i].token ) == 0 ) - { - creator = typetable[i].creator; - break; - } + if( strcmp( typestr, typetable[i].token ) == 0 ) + { + creator = typetable[i].creator; + break; + } // if we found a creator function, call it if( creator ) @@ -224,7 +224,7 @@ else { PRINT_ERR1( "Unknown model type %s in world file.", - typestr ); + typestr ); exit( 1 ); } @@ -239,10 +239,10 @@ int parent_entity = wf->GetEntityParent( entity ); PRINT_DEBUG2( "wf entity %d parent entity %d\n", - entity, parent_entity ); + entity, parent_entity ); Model* parent = (Model*)g_hash_table_lookup( entitytable, - (gpointer)parent_entity ); + (gpointer)parent_entity ); char *typestr = (char*)wf->GetEntityType(entity); assert(typestr); @@ -285,11 +285,11 @@ this->interval_sim = (stg_usec_t)thousand * wf->ReadInt( entity, "interval_sim", - (int)(this->interval_sim/thousand) ); + (int)(this->interval_sim/thousand) ); if( wf->PropertyExists( entity, "quit_time" ) ) { this->quit_time = (stg_usec_t) ( million * - wf->ReadFloat( entity, "quit_time", 0 ) ); + wf->ReadFloat( entity, "quit_time", 0 ) ); } if( wf->PropertyExists( entity, "resolution" ) ) @@ -303,22 +303,22 @@ int count = wf->ReadInt( entity, "threadpool", worker_threads ); if( count && (count != (int)worker_threads) ) - { - worker_threads = count; + { + worker_threads = count; - if( threadpool == NULL ) - threadpool = g_thread_pool_new( (GFunc)update_thread_entry, - this, - worker_threads, - true, - NULL ); - else - g_thread_pool_set_max_threads( threadpool, - worker_threads, - NULL ); + if( threadpool == NULL ) + threadpool = g_thread_pool_new( (GFunc)update_thread_entry, + this, + worker_threads, + true, + NULL ); + else + g_thread_pool_set_max_threads( threadpool, + worker_threads, + NULL ); - printf( "[threadpool %u]", worker_threads ); - } + printf( "[threadpool %u]", worker_threads ); + } } // Iterate through entitys and create objects of the appropriate type @@ -328,15 +328,15 @@ // don't load window entries here if( strcmp( typestr, "window" ) == 0 ) - { - /* do nothing here */ - } + { + /* do nothing here */ + } else if( strcmp( typestr, "block" ) == 0 ) - LoadBlock( wf, entity, entitytable ); - // else if( strcmp( typestr, "puck" ) == 0 ) - // LoadPuck( wf, entity, entitytable ); - else - LoadModel( wf, entity, entitytable ); + LoadBlock( wf, entity, entitytable ); + // else if( strcmp( typestr, "puck" ) == 0 ) + // LoadPuck( wf, entity, entitytable ); + else + LoadModel( wf, entity, entitytable ); } @@ -352,7 +352,7 @@ if( debug ) printf( "[Load time %.3fsec]\n", - (load_end_time - load_start_time) / 1000000.0 ); + (load_end_time - load_start_time) / 1000000.0 ); else putchar( '\n' ); } @@ -431,10 +431,10 @@ char buf[256]; if( hours > 0 ) - { - snprintf( buf, 255, "%uh", hours ); - str += buf; - } + { + snprintf( buf, 255, "%uh", hours ); + str += buf; + } snprintf( buf, 255, " %um %02us %03umsec", minutes, seconds, msec); str += buf; @@ -443,7 +443,7 @@ } void World::AddUpdateCallback( stg_world_callback_t cb, - void* user ) + void* user ) { // add the callback & argument to the list std::pair<stg_world_callback_t,void*> p(cb, user); @@ -451,21 +451,21 @@ } int World::RemoveUpdateCallback( stg_world_callback_t cb, - void* user ) + void* user ) { std::pair<stg_world_callback_t,void*> p( cb, user ); std::list<std::pair<stg_world_callback_t,void*> >::iterator it; for( it = cb_list.begin(); - it != cb_list.end(); - it++ ) - { - if( (*it) == p ) - { - cb_list.erase( it ); - break; - } - } + it != cb_list.end(); + it++ ) + { + if( (*it) == p ) + { + cb_list.erase( it ); + break; + } + } // return the number of callbacks now in the list. Useful for // detecting when the list is empty. @@ -477,17 +477,17 @@ // for each callback in the list for( std::list<std::pair<stg_world_callback_t,void*> >::iterator it = cb_list.begin(); - it != cb_list.end(); - it++ ) - { - //printf( "cbs %p data %p cvs->next %p\n", cbs, cbs->data, cbs->next ); + it != cb_list.end(); + it++ ) + { + //printf( "cbs %p data %p cvs->next %p\n", cbs, cbs->data, cbs->next ); - if( ((*it).first )( this, (*it).second ) ) - { - //printf( "callback returned TRUE - schedule removal from list\n" ); - it = cb_list.erase( it ); - } - } + if( ((*it).first )( this, (*it).second ) ) + { + //printf( "callback returned TRUE - schedule removal from list\n" ); + it = cb_list.erase( it ); + } + } } bool World::Update() @@ -520,35 +520,35 @@ { // push the update for every model that needs it into the thread pool for( GList* it = reentrant_update_list; it; it=it->next ) - { - Model* mod = (Model*)it->data; - - if( mod->UpdateDue() ) { - // printf( "updating model %s in WORKER thread\n", mod->Token() ); - //g_mutex_lock( thread_mutex ); - //update_jobs_pending++; - //g_mutex_unlock( thread_mutex ); - g_thread_pool_push( threadpool, mod, NULL ); - } - } + Model* mod = (Model*)it->data; + + if( mod->UpdateDue() ) + { + // printf( "updating model %s in WORKER thread\n", mod->Token() ); + //g_mutex_lock( thread_mutex ); + //update_jobs_pending++; + //g_mutex_unlock( thread_mutex ); + g_thread_pool_push( threadpool, mod, NULL ); + } + } // wait for all the last update job to complete - it will // signal the worker_threads_done condition var g_mutex_lock( thread_mutex ); while( g_thread_pool_unprocessed( threadpool ) ) //update_jobs_pending ) - g_cond_wait( worker_threads_done, thread_mutex ); + g_cond_wait( worker_threads_done, thread_mutex ); g_mutex_unlock( thread_mutex ); - // now call all the callbacks - ignores dueness, but not a big deal + // now call all the callbacks - ignores dueness, but not a big deal LISTMETHOD( reentrant_update_list, Model*, CallUpdateCallbacks ); } if( show_clock && ((this->updates % show_clock_interval) == 0) ) - { - printf( "\r[Stage: %s]", ClockString().c_str() ); - fflush( stdout ); - } + { + printf( "\r[Stage: %s]", ClockString().c_str() ); + fflush( stdout ); + } CallUpdateCallbacks(); @@ -599,14 +599,14 @@ void World::Raytrace( const Pose &gpose, // global pose - const stg_meters_t range, - const stg_radians_t fov, - const stg_ray_test_func_t func, - const Model* model, - const void* arg, - stg_raytrace_result_t* samples, // preallocated storage for samples - const uint32_t sample_count, // number of samples - const bool ztest ) + const stg_meters_t range, + const stg_radians_t fov, + const stg_ray_test_func_t func, + const Model* model, + const void* arg, + stg_raytrace_result_t* samples, // preallocated storage for samples + const uint32_t sample_count, // number of samples + const bool ztest ) { // find the direction of the first ray Pose raypose = gpose; @@ -614,16 +614,11 @@ for( uint32_t s=0; s < sample_count; s++ ) { - raypose.a = (s * fov / (double)sample_count) - starta; + raypose.a = (s * fov / (double)sample_count) - starta; samples[s] = Raytrace( raypose, range, func, model, arg, ztest ); } } -// fast macros for converting from global cell coordinates to local coords -#define GETCELL(X) (((int32_t)X) & ~((~0x00)<<RBITS )) -#define GETREG(X) ((((int32_t)X) & ~((~0x00)<<SRBITS ))>>RBITS) -#define GETSREG(X) (((int32_t)X)>>SRBITS) - // Stage spends 50-99% of its time in this method. stg_raytrace_result_t World::Raytrace( const Pose &gpose, const stg_meters_t range, @@ -657,32 +652,32 @@ const double tana(sina/cosa); // = tan(angle) // and the x and y offsets of the ray - const int dx( ppm * r.range * cosa); - const int dy( ppm * r.range * sina); + const int32_t dx( ppm * r.range * cosa); + const int32_t dy( ppm * r.range * sina); // fast integer line 3d algorithm adapted from Cohen's code from // Graphics Gems IV - const int sx(sgn(dx)); // sgn() is a fast macro - const int sy(sgn(dy)); - const int ax(abs(dx)); - const int ay(abs(dy)); - const int bx(2*ax); - const int by(2*ay); - int exy(ay-ax); - int n(ax+ay); // the manhattan distance to the goal cell + const int32_t sx(sgn(dx)); // sgn() is a fast macro + const int32_t sy(sgn(dy)); + const int32_t ax(abs(dx)); + const int32_t ay(abs(dy)); + const int32_t bx(2*ax); + const int32_t by(2*ay); + int32_t exy(ay-ax); + int32_t n(ax+ay); // the manhattan distance to the goal cell - const int rsize( Region::WIDTH ); + //const int REGIONWIDTH( REGIONWIDTH ); // fix a little issue where rays are not drawn long enough when // drawing to the right or up if( (dx > 0) || ( dy > 0 ) ) - n++; + n++; // the distances between region crossings in X and Y - const double xjumpx( sx * rsize ); - const double xjumpy( sx * rsize * tana ); - const double yjumpx( sy * rsize / tana ); - const double yjumpy( sy * rsize ); + const double xjumpx( sx * REGIONWIDTH ); + const double xjumpy( sx * REGIONWIDTH * tana ); + const double yjumpx( sy * REGIONWIDTH / tana ); + const double yjumpy( sy * REGIONWIDTH ); // manhattan distance between region crossings in X and Y const double xjumpdist( fabs(xjumpx)+fabs(xjumpy) ); const double yjumpdist( fabs(yjumpx)+fabs(yjumpy) ); @@ -693,7 +688,6 @@ double distX(0), distY(0); bool calculatecrossings( true ); - // puts( "=======================" ); // Stage spends up to 95% of its time in this loop! It would be @@ -701,189 +695,189 @@ // inline calls have a noticeable (2-3%) effect on performance while( n > 0 ) // while we are still not at the ray end { - SuperRegion* sr = - GetSuperRegionCached(GETSREG(glob.x), - GETSREG(glob.y)); - - // coordinates of the region inside the superregion - int32_t rx = GETREG(glob.x); - int32_t ry = GETREG(glob.y); - Region* reg = &sr->regions[ rx + (ry*SuperRegion::WIDTH) ]; + SuperRegion* sr = + GetSuperRegionCached(GETSREG(glob.x), GETSREG(glob.y)); - if( reg->count ) // if the region contains any objects - { - // invalidate the region crossing points used to jump over - // empty regions - calculatecrossings = true; + // coordinates of the region inside the superregion + int32_t rx( GETREG(glob.x) ); + int32_t ry( GETREG(glob.y) ); + Region* reg( &sr->regions[ rx + (ry*SUPERREGIONWIDTH) ] ); + + if( reg->count ) // if the region contains any objects + { + // invalidate the region crossing points used to jump over + // empty regions + calculatecrossings = true; - // convert from global cell to local cell coords - int32_t cx = GETCELL(glob.x); - int32_t cy = GETCELL(glob.y); + // convert from global cell to local cell coords + int32_t cx( GETCELL(glob.x) ); + int32_t cy( GETCELL(glob.y) ); - Cell* c = ®->cells[ cx + cy * Region::WIDTH ]; - assert(c); // should be a cell there + Cell* c( ®->cells[ cx + cy * REGIONWIDTH ] ); + assert(c); // should be a cell there - // while within the bounds of this region and while some ray remains - // we'll tweak the cell pointer directly to move around quickly - while( (cx>=0) && (cx<(int)Region::WIDTH) && - (cy>=0) && (cy<(int)Region::WIDTH) && - n > 0 ) - { - //printf( "cx %d cy %d\n", cx, cy ); - assert(c >= reg->cells); - - for( std::vector<Block*>::iterator it = c->blocks.begin(); - it != c->blocks.end(); - ++it ) - { - Block* block = *it; + // while within the bounds of this region and while some ray remains + // we'll tweak the cell pointer directly to move around quickly + while( (cx>=0) && (cx<REGIONWIDTH) && + (cy>=0) && (cy<REGIONWIDTH) && + n > 0 ) + { + //printf( "cx %d cy %d\n", cx, cy ); + assert(c >= reg->cells); + assert(c < (reg->cells + REGIONSIZE) ); + + for( std::vector<Block*>::iterator it = c->blocks.begin(); + it != c->blocks.end(); + ++it ) + { + Block* block = *it; - // skip if not in the right z range - if( r.ztest && - ( r.origin.z < block->global_z.min || - r.origin.z > block->global_z.max ) ) - continue; + // skip if not in the right z range + if( r.ztest && + ( r.origin.z < block->global_z.min || + r.origin.z > block->global_z.max ) ) + continue; - // test the predicate we were passed - if( (*r.func)( block->mod, (Model*)r.mod, r.arg )) - { - // a hit! - sample.color = block->GetColor(); - sample.mod = block->mod; + // test the predicate we were passed + if( (*r.func)( block->mod, (Model*)r.mod, r.arg )) + { + // a hit! + sample.color = block->GetColor(); + sample.mod = block->mod; - if( ax > ay ) // faster than the equivalent hypot() call - sample.range = fabs((glob.x-start.x) / cosa) / ppm; - else - sample.range = fabs((glob.y-start.y) / sina) / ppm; + if( ax > ay ) // faster than the equivalent hypot() call + sample.range = fabs((glob.x-start.x) / cosa) / ppm; + else + sample.range = fabs((glob.y-start.y) / sina) / ppm; - return sample; - } - } + return sample; + } + } - assert (sx >= -2 && sx < 2); - assert (sy >= -2 && sy < 2); - // increment our cell in the correct direction - if( exy < 0 ) // we're iterating along X - { - glob.x += sx; // global coordinate - exy += by; - c += sx; // move the cell left or right - cx += sx; // cell coordinate for bounds checking - } - else // we're iterating along Y - { - glob.y += sy; // global coordinate - exy -= bx; - c += sy * static_cast<int> (Region::WIDTH); // move the cell up or down - cy += sy; // cell coordinate for bounds checking - } - n--; // decrement the manhattan distance remaining + assert (sx >= -2 && sx < 2); + assert (sy >= -2 && sy < 2); + // increment our cell in the correct direction + if( exy < 0 ) // we're iterating along X + { + glob.x += sx; // global coordinate + exy += by; + c += sx; // move the cell left or right + cx += sx; // cell coordinate for bounds checking + } + else // we're iterating along Y + { + glob.y += sy; // global coordinate + exy -= bx; + c += sy * REGIONWIDTH; // move the cell up or down + cy += sy; // cell coordinate for bounds checking + } + n--; // decrement the manhattan distance remaining - //rt_cells.push_back( stg_point_int_t( glob.x, glob.y )); - } + //rt_cells.push_back( stg_point_int_t( glob.x, glob.y )); + } - //printf( "leaving populated region\n" ); - } - else // jump over the empty region - { - // on the first run, and when we've been iterating over cells, - // we need to calculate the next crossing of region in each - // axis - if( calculatecrossings ) - { - calculatecrossings = false; + //printf( "leaving populated region\n" ); + } + else // jump over the empty region + { + // on the first run, and when we've been iterating over cells, + // we need to calculate the next crossing of region in each + // axis + if( calculatecrossings ) + { + calculatecrossings = false; - // find the coordinate in cells of the bottom left corner of - // the current region - int ix = glob.x; - int iy = glob.y; - double regionx = ix/rsize*rsize; - double regiony = iy/rsize*rsize; - if( (glob.x < 0) && (ix % rsize) ) regionx -= rsize; - if( (glob.y < 0) && (iy % rsize) ) regiony -= rsize; + // find the coordinate in cells of the bottom left corner of + // the current region + int32_t ix( glob.x ); + int32_t iy( glob.y ); + double regionx( ix/REGIONWIDTH*REGIONWIDTH ); + double regiony( iy/REGIONWIDTH*REGIONWIDTH ); + if( (glob.x < 0) && (ix % REGIONWIDTH) ) regionx -= REGIONWIDTH; + if( (glob.y < 0) && (iy % REGIONWIDTH) ) regiony -= REGIONWIDTH; - //double regionx = glob.x - fmod(glob.x,rsize); - //double regiony = glob.y - fmod(glob.y,rsize); + //double regionx = glob.x - fmod(glob.x,REGIONWIDTH); + //double regiony = glob.y - fmod(glob.y,REGIONWIDTH); - //printf( "region %.2f %.2f\n", regionx, regiony ); + //printf( "region %.2f %.2f\n", regionx, regiony ); + + // calculate the distance to the edge of the current region + double xdx( sx < 0 ? + regionx - glob.x - 1.0 : // going left + regionx + REGIONWIDTH - glob.x ); // going right + double xdy( xdx*tana ); + + double ydy( sy < 0 ? + regiony - glob.y - 1.0 : // going down + regiony + REGIONWIDTH - glob.y ); // going up + double ydx( ydy/tana ); + + // these stored hit points are updated as we go along + xcrossx = glob.x+xdx; + xcrossy = glob.y+xdy; - // calculate the distance to the edge of the current region - double xdx = sx < 0 ? - regionx - glob.x - 1.0 : // going left - regionx + rsize - glob.x; // going right - double xdy = xdx*tana; + ycrossx = glob.x+ydx; + ycrossy = glob.y+ydy; - double ydy = sy < 0 ? - regiony - glob.y - 1.0 : // going down - regiony + rsize - glob.y; // going up - double ydx = ydy/tana; - - // these stored hit points are updated as we go along - xcrossx = glob.x+xdx; - xcrossy = glob.y+xdy; - - ycrossx = glob.x+ydx; - ycrossy = glob.y+ydy; - - // find the distances to the region crossing points - // manhattan distance is faster than using hypot() - distX = fabs(xdx)+fabs(xdy); - distY = fabs(ydx)+fabs(ydy); - } + // find the distances to the region crossing points + // manhattan distance is faster than using hypot() + distX = fabs(xdx)+fabs(xdy); + distY = fabs(ydx)+fabs(ydy); + } -// printf( "globx %.2f globy %.2f\n", glob.x, glob.y ); -// printf( "xcross (%.2f,%.2f) ycross(%.2f,%.2f)\n", xcrossx, xcrossy, ycrossx, ycrossy ); -// printf( "distX %.2f distY %.2f\n", distX, distY ); -// printf( "xjumpdist %.2f yjumpdist %.2f\n", xjumpdist, yjumpdist ); -// puts( "" ); + // printf( "globx %.2f globy %.2f\n", glob.x, glob.y ); + // printf( "xcross (%.2f,%.2f) ycross(%.2f,%.2f)\n", xcrossx, xcrossy, ycrossx, ycrossy ); + // printf( "distX %.2f distY %.2f\n", distX, distY ); + // printf( "xjumpdist %.2f yjumpdist %.2f\n", xjumpdist, yjumpdist ); + // puts( "" ); - if( distX < distY ) // crossing a region boundary left or right - { - //puts( "distX" ); - // move to the X crossing - glob.x = xcrossx; - glob.y = xcrossy; + if( distX < distY ) // crossing a region boundary left or right + { + //puts( "distX" ); + // move to the X crossing + glob.x = xcrossx; + glob.y = xcrossy; - n -= distX; // decrement remaining manhattan distance + n -= distX; // decrement remaining manhattan distance - // calculate the next region crossing - xcrossx += xjumpx; - xcrossy += xjumpy; + // calculate the next region crossing + xcrossx += xjumpx; + xcrossy += xjumpy; - distY -= distX; - distX = xjumpdist; + distY -= distX; + distX = xjumpdist; - //rt_candidate_cells.push_back( stg_point_int_t( xcrossx, xcrossy )); - } - else // crossing a region boundary up or down - { - //puts( "distY" ); - // move to the X crossing - glob.x = ycrossx; - glob.y = ycrossy; + //rt_candidate_cells.push_back( stg_point_int_t( xcrossx, xcrossy )); + } + else // crossing a region boundary up or down + { + //puts( "distY" ); + // move to the X crossing + glob.x = ycrossx; + glob.y = ycrossy; - n -= distY; // decrement remaining manhattan distance + n -= distY; // decrement remaining manhattan distance - // calculate the next region crossing - ycrossx += yjumpx; - ycrossy += yjumpy; + // calculate the next region crossing + ycrossx += yjumpx; + ycrossy += yjumpy; - distX -= distY; - distY = yjumpdist; + distX -= distY; + distY = yjumpdist; - //rt_candidate_cells.push_back( stg_point_int_t( ycrossx, ycrossy )); - } + //rt_candidate_cells.push_back( stg_point_int_t( ycrossx, ycrossy )); + } -// if( (GETCELL(xcrossx) == GETCELL(ycrossx) ) && -// (GETCELL(xcrossy) == GETCELL(ycrossy) ) ) -// printf( "SAME %d=%d %d=%d\n", -// GETCELL(xcrossx), GETCELL(ycrossx), -// GETCELL(xcrossy), GETCELL(ycrossy) ); + // if( (GETCELL(xcrossx) == GETCELL(ycrossx) ) && + // (GETCELL(xcrossy) == GETCELL(ycrossy) ) ) + // printf( "SAME %d=%d %d=%d\n", + // GETCELL(xcrossx), GETCELL(ycrossx), + // GETCELL(xcrossy), GETCELL(ycrossy) ); - //printf( "jumped to glob (%.2f %.2f)\n", glob.x, glob.y ); - } - //rt_cells.push_back( stg_point_int_t( glob.x, glob.y )); - } + //printf( "jumped to glob (%.2f %.2f)\n", glob.x, glob.y ); + } + //rt_cells.push_back( stg_point_int_t( glob.x, glob.y )); + } // hit nothing sample.mod = NULL; return sample; @@ -936,8 +930,6 @@ return sr; } - - inline SuperRegion* World::GetSuperRegionCached( int32_t x, int32_t y ) { // around 99% of the time the SR is the same as last @@ -977,28 +969,17 @@ return sr; } -Cell* World::GetCellNoCreate( const stg_point_int_t& glob ) +Cell* World::GetCell( const stg_point_int_t& glob ) { - Region* r = GetSuperRegionCached( GETSREG(glob.x), GETSREG(glob.y) ) - ->GetRegionGlobal( glob ); - - if( r->count ) - return r->GetCellGlobalNoCreate( glob ) ; - return NULL; -} - - -Cell* World::GetCellCreate( const stg_point_int_t& glob ) -{ return( GetSuperRegionCached( GETSREG(glob.x), GETSREG(glob.y) ) - ->GetRegionGlobal( glob ) - ->GetCellGlobalCreate( glob )) ; + ->GetRegion( GETREG(glob.x), GETREG(glob.y) ) + ->GetCell( GETCELL(glob.x), GETCELL(glob.y) )) ; } void World::ForEachCellInLine( const stg_point_int_t& start, - const stg_point_int_t& end, - std::vector<Cell*>& cells ) + const stg_point_int_t& end, + std::vector<Cell*>& cells ) { int dx = end.x - start.x; @@ -1025,20 +1006,20 @@ while( n-- ) { - // find or create the cell at this location, then add it to the vector - cells.push_back( GetCellCreate( cell ) ); + // find the cell at this location, then add it to the vector + cells.push_back( GetCell( cell ) ); // cleverly skip to the next cell if( exy < 0 ) - { - cell.x += sx; - exy += by; - } + { + cell.x += sx; + exy += by; + } else - { - cell.y += sy; - exy -= bx; - } + { + cell.y += sy; + exy -= bx; + } } } @@ -1075,15 +1056,15 @@ // update_list = g_list_append( update_list, mod ); if( mod->thread_safe ) - { - if( ! g_list_find( reentrant_update_list, mod ) ) - reentrant_update_list = g_list_append( reentrant_update_list, mod ); - } + { + if( ! g_list_find( reentrant_update_list, mod ) ) + reentrant_update_list = g_list_append( reentrant_update_list, mod ); + } else - { - if( ! g_list_find( nonreentrant_update_list, mod ) ) - nonreentrant_update_list = g_list_append( nonreentrant_update_list, mod ); - } + { + if( ! g_list_find( nonreentrant_update_list, mod ) ) + nonreentrant_update_list = g_list_append( nonreentrant_update_list, mod ); + } } void World::StopUpdatingModel( Model* mod ) @@ -1091,15 +1072,15 @@ // update_list = g_list_remove( update_list, mod ); if( mod->thread_safe ) - reentrant_update_list = g_list_remove( reentrant_update_list, mod ); + reentrant_update_list = g_list_remove( reentrant_update_list, mod ); else - nonreentrant_update_list = g_list_remove( nonreentrant_update_list, mod ); + nonreentrant_update_list = g_list_remove( nonreentrant_update_list, mod ); } void World::StartUpdatingModelPose( Model* mod ) { if( ! g_list_find( velocity_list, mod ) ) - velocity_list = g_list_append( velocity_list, mod ); + velocity_list = g_list_append( velocity_list, mod ); } void World::StopUpdatingModelPose( Model* mod ) This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |