Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Changeset 8349 in orxonox.OLD for branches/terrain/src/lib


Ignore:
Timestamp:
Jun 13, 2006, 7:41:37 PM (18 years ago)
Author:
ponder
Message:
  • I changend the tesselation method. Now the tesselation level of the pages neighbors are taken into account. This is neccessary for the geomorphing.
  • Fixed a bug, that caused the visible pages to be put two times into the active pages list.
Location:
branches/terrain/src/lib/graphics/importer/terrain
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/terrain/src/lib/graphics/importer/terrain/terrain.cc

    r8328 r8349  
    3535       
    3636        //TODO: Determine layer visibility!
    37         printf( "creating terrain pages ( %d, %d )...", pagesX, pagesZ );
     37        printf( " * creating terrain pages ( %d, %d )...", pagesX, pagesZ );
    3838        pages = new pTerrainPage[pagesX*pagesZ];       
    3939        for ( int x = 0; x < pagesX; ++x )
     
    4141                        pages[z*pagesX+x] = createPage( x, z );
    4242        printf( "looks good\n" );
    43         printf( "creating quad_tree data structure..." );
     43        printf( " * inform pages about the adjacent pages..." );                       
     44        //Inform each page about its neighbors.
     45        for ( int x = 0; x < pagesX; ++x )
     46                for ( int z = 0; z < pagesZ; ++z )
     47                        pages[z*pagesX+x]->setNeighbors(
     48                                x > 0                   ? getPage( x-1, z+0 ) : NULL,
     49                                x < pagesX-1    ? getPage( x+1, z+0 ) : NULL,
     50                                z > 0                   ? getPage( x+0, z-1 ) : NULL,
     51                                z < pagesZ-1    ? getPage( x+0, z+1 ) : NULL );
     52       
     53        printf( "looks good\n" );
     54        printf( " * creating quad_tree data structure..." );
    4455        root = createQuadTree( 0, 0, pagesX, pagesZ );
    4556        activePages = NULL;
     
    132143        determineVisiblePages( root );
    133144               
    134         int count = 0;
    135145        page = activePages;     
    136146        while ( page ) {
     
    139149                        page = tmp->getNext();
    140150                        tmp->setVisibility( false );
    141                         tmp->deactivate();
    142                         deactivatedCount++;
    143151                        continue;
    144152                }       
    145                 count++;
    146153                page->updateTesselation();
    147154                //Draw the page. TODO: It would be nice if all the pages with an LOD of 4 could be merged
     
    150157                page = page->getNext();
    151158        }
    152         //printf( "%d pages activated, %d pages deactivated\n", activatedCount, deactivatedCount );
    153159        activatedCount = 0; deactivatedCount = 0;
    154         float percentage = (float)cullCount/(float)(pagesX*pagesZ)*100.0f;
     160        //float percentage = (float)cullCount/(float)(pagesX*pagesZ)*100.0f;
    155161        //printf( "culled %f%% terrain pages away\n",  percentage );
    156162}
  • branches/terrain/src/lib/graphics/importer/terrain/terrain_page.cc

    r8328 r8349  
    4242}
    4343
     44void TerrainPage::tesselateRow( int _z, int _xStride, int _zStride, bool _adaptLeft, bool _adaptRight )
     45{
     46        int xStart = 0, xEnd = owner->getPageSize();
     47       
     48        int halfStride = _zStride >> 1;
     49
     50
     51        if ( _z ) {
     52                addAgain( );
     53                addIndex( getIndex( 0, _z ) );
     54        }
     55        if ( _adaptLeft ) {
     56                assert( halfStride > 0 );               
     57                addIndex( getIndex( 0, _z ) );
     58                addIndex( getIndex( 0, _z+halfStride ) );
     59                addIndex( getIndex( _xStride, _z ) );
     60                addIndex( getIndex( 0, _z+_zStride ) );
     61                addIndex( getIndex( _xStride, _z+_zStride ) );
     62                addAgain();
     63                xStart = _xStride;
     64        }
     65       
     66        if ( _adaptRight )
     67                xEnd-=_xStride;
     68               
     69        for ( int x = xStart; x < xEnd; x+=_xStride ) {
     70                addIndex( getIndex( x, _z) );
     71                addIndex( getIndex( x, _z+_zStride ) );
     72        }
     73       
     74        int w = owner->getPageSize()-1;
     75       
     76        if ( _adaptRight ) {
     77                assert( halfStride > 0 );               
     78                addIndex( getIndex( w-_xStride, _z ) );
     79                addAgain();
     80                addIndex( getIndex( w, _z ) );
     81                addIndex( getIndex( w-_xStride, _z+_zStride ) );
     82                addIndex( getIndex( w, _z+halfStride ) );
     83                addIndex( getIndex( w, _z+_zStride ) );
     84        }
     85}
     86
     87//TODO: Perform benchmark to measure if the isVisible test should be included
     88//in this method.
     89
     90void TerrainPage::determineBorderAdaption( bool _adapt[] )
     91{
     92        _adapt[0] = _adapt[1] = _adapt[2] = _adapt[3] = false;
     93       
     94        if ( left  && left->isVisible )
     95                _adapt[TP_LEFT] = ( wantedLOD - left->getWantedLOD() ) > 0;
     96               
     97        if ( right && right->isVisible )
     98                _adapt[TP_RIGHT] = ( wantedLOD - right->getWantedLOD() ) > 0;
     99               
     100        if ( top && top->isVisible)
     101                _adapt[TP_TOP] = ( wantedLOD - top->getWantedLOD() ) > 0;                               
     102               
     103        if ( bottom && bottom->isVisible )
     104                _adapt[TP_BOTTOM] = ( wantedLOD - bottom->getWantedLOD() ) > 0;         
     105}
     106
    44107int TerrainPage::chooseLOD()
    45108{
     
    65128                wantedLOD = TerrainPage::MAX_LODS-1;
    66129        }       
    67         // Calculate the tween factor. This is differently if the LOD is 0.
     130        // Calculate the tween factor. The calculation is different if LOD is 0
     131        //
    68132        if ( wantedLOD > 0 ) {
    69133               
     
    82146        if ( list )
    83147                list->previous = this;
    84         owner->incActivated();
    85148        owner->setActiveList( this );
    86149}
     
    99162                owner->setActiveList( next );
    100163        next = NULL;
    101         owner->incDeactivated();
    102164        previous = NULL;
    103165       
     
    111173        if( _lod!=0 )
    112174        {
    113                 int pow = 1 << _lod, x0, y0, xi, yi;
     175                int stride = 1 << _lod, x0, y0, xi, yi;
    114176                // Altough these four nested loops look very scary, they're not
    115                 // that bad.
    116                 for( y0 = 0 ; y0 < size-pow; y0 += pow ) {
    117                         for( x0 = 0; x0 < size-pow; x0 += pow ) {
    118                                 for( yi = 1; yi < pow; yi++ ) {
    119                                         for( xi = 1; xi < pow; xi++ )
     177                // that bad and require only about O(n^2).
     178                for( y0 = 0 ; y0 < size-stride; y0 += stride ) {
     179                        for( x0 = 0; x0 < size-stride; x0 += stride ) {
     180                                for( yi = 1; yi < stride; yi++ ) {
     181                                        for( xi = 1; xi < stride; xi++ )
    120182                                        {
    121183                                                int     x = x0+xi,
    122184                                                y = y0+yi;
    123                                                 float   fx0 = ( float )xi/( float )pow, fx1 = 1.0f-fx0,
    124                                                                 fy0 = ( float )yi/( float )pow, fy1 = 1.0f-fy0;
     185                                                float   fx0 = ( float )xi/( float )stride, fx1 = 1.0f-fx0,
     186                                                                fy0 = ( float )yi/( float )stride, fy1 = 1.0f-fy0;
    125187                                               
    126188                                                float   height00 = getAltitude( x0, y0 ),
    127                                                                 height10 = getAltitude( x0+pow,y0 ),
    128                                                                 height01 = getAltitude( x0,y0+pow ),
    129                                                                 height11 = getAltitude( x0+pow, y0+pow );
     189                                                                height10 = getAltitude( x0+stride,y0 ),
     190                                                                height01 = getAltitude( x0,y0+stride ),
     191                                                                height11 = getAltitude( x0+stride, y0+stride );
    130192                                               
    131193                                                float   paintHeight =   fx1*fy1 * height00 +
     
    179241}
    180242
     243bool TerrainPage::needsRetesselation()
     244{
     245       
     246        bool    leftChanged     = ( left && left->isVisible ) && ( left->wantedLOD != left->currentLOD ),
     247                        rightChanged    = ( right && right->isVisible ) && ( right->wantedLOD != right->currentLOD ),
     248                        topChanged              = ( top && top->isVisible ) && ( top->wantedLOD != currentLOD ),
     249                        bottomChanged   = ( bottom && bottom->isVisible ) && ( bottom->wantedLOD != bottom->currentLOD ),
     250                        iChanged                =  wantedLOD != currentLOD;
     251                               
     252        return ( leftChanged || rightChanged || topChanged || bottomChanged || forceTesselation || iChanged );
     253}
     254
    181255void TerrainPage::updateTesselation( )
    182256{
     257
     258        if ( needsRetesselation() ) {
     259                tesselate( wantedLOD );
     260        }       
    183261        currentLOD = wantedLOD;
    184         if ( forceTesselation || currentLOD != currentLOD ) {
    185                 tesselate( currentLOD );
    186         }       
    187 
    188262        forceTesselation = false;
    189263}
    190264
    191 /**
    192  * Genererates a tesselation for the given _lod.
    193  */
     265void TerrainPage::tesselateLevelFourPatch( bool _adapt[] )
     266{
     267        const int       halfStride = 8, stride = 16;
     268       
     269        enum { ADAPT_L = 1, ADAPT_R = 2, ADAPT_B = 4, ADAPT_T = 8,
     270                ADAPT_LR = 3, ADAPT_LB = 5, ADAPT_LT = 9, ADAPT_RB = 6,
     271                ADAPT_RT = 10, ADAPT_BT = 12, ADAPT_LRB = 7, ADAPT_LBT = 13, ADAPT_LRT = 11,
     272                ADAPT_RBT = 14, ADAPT_LRBT = 15, ADAPT_NONE = 0 };
     273               
     274        int                     code =  ( _adapt[TP_LEFT]       ? ADAPT_L : 0 ) |
     275                                                ( _adapt[TP_RIGHT]      ? ADAPT_R : 0 ) |
     276                                                ( _adapt[TP_BOTTOM] ? ADAPT_B : 0 ) |
     277                                                ( _adapt[TP_TOP]        ? ADAPT_T : 0 );
     278        switch( code ) {
     279                case ADAPT_NONE:
     280                        addIndex( getIndex( 0, 0 ) );
     281                        addIndex( getIndex( 0, stride ) );
     282                        addIndex( getIndex( stride, 0 ) );
     283                        addIndex( getIndex( stride, stride ) );
     284                        break;
     285                       
     286                case ADAPT_L:
     287                        addIndex( getIndex( 0, 0 ) );
     288                        addIndex( getIndex( 0, halfStride ) );
     289                        addIndex( getIndex( stride, 0 ) );
     290                        addIndex( getIndex( 0, stride ) );
     291                        addIndex( getIndex( stride, stride ) );
     292                        addAgain(  );
     293                        break;
     294               
     295                case ADAPT_R:
     296                        addIndex( getIndex( stride, stride ) );
     297                        addIndex( getIndex( stride, halfStride ) );
     298                        addIndex( getIndex( 0, stride ) );
     299                        addIndex( getIndex( stride, 0 ) );
     300                        addIndex( getIndex( 0, 0 ) );
     301                        addAgain(  );
     302                        break;
     303
     304                case ADAPT_LR:
     305                        addIndex( getIndex( 0, 0 ) );
     306                        addIndex( getIndex( 0, halfStride ) );
     307                        addIndex( getIndex( stride, 0 ) );
     308                        addIndex( getIndex( 0, stride ) );
     309                        addIndex( getIndex( stride, halfStride ) );
     310                        addIndex( getIndex( stride, stride ) );
     311                        break;
     312
     313                case ADAPT_B:
     314                        addIndex( getIndex( 0, 0 ) );
     315                        addAgain(  );
     316                        addIndex( getIndex( halfStride, 0 ) );
     317                        addIndex( getIndex( 0, stride ) );
     318                        addIndex( getIndex( stride, 0 ) );
     319                        addIndex( getIndex( stride, stride ) );
     320                        break;
     321
     322                case ADAPT_LB:
     323                        addIndex( getIndex( 0, 0 ) );
     324                        addIndex( getIndex( 0, halfStride ) );
     325                        addIndex( getIndex( halfStride, 0 ) );
     326                        addIndex( getIndex( 0, stride ) );
     327                        addIndex( getIndex( stride, 0 ) );
     328                        addIndex( getIndex( stride, stride ) );
     329                        break;
     330
     331                case ADAPT_RB:
     332                        addIndex( getIndex( 0, 0 ) );
     333                        addIndex( getIndex( 0, stride ) );
     334                        addIndex( getIndex( halfStride, 0 ) );
     335                        addIndex( getIndex( stride, 0 ) );
     336                        addAgain(  );
     337                        addIndex( getIndex( 0, stride ) );
     338                        addIndex( getIndex( stride, halfStride ) );
     339                        addIndex( getIndex( stride, stride ) );
     340                        break;
     341
     342                case ADAPT_LRB:
     343                        addIndex( getIndex( stride, stride ) );
     344                        addIndex( getIndex( stride, halfStride ) );
     345                        addIndex( getIndex( 0, stride ) );
     346                        addIndex( getIndex( stride, 0 ) );
     347                        addIndex( getIndex( 0, halfStride ) );
     348                        addIndex( getIndex( halfStride, 0 ) );
     349                        addIndex( getIndex( 0, 0 ) );
     350                        addAgain(  );
     351                        break;
     352
     353                case ADAPT_T:
     354                        addIndex( getIndex( stride, stride ) );
     355                        addAgain(  );
     356                        addIndex( getIndex( halfStride, stride ) );
     357                        addIndex( getIndex( stride, 0 ) );
     358                        addIndex( getIndex( 0, stride ) );
     359                        addIndex( getIndex( 0, 0 ) );
     360                        break;
     361
     362                case ADAPT_LT:
     363                        addIndex( getIndex( stride, stride ) );
     364                        addIndex( getIndex( stride, 0 ) );
     365                        addIndex( getIndex( halfStride, stride ) );
     366                        addIndex( getIndex( 0, stride ) );
     367                        addAgain(  );
     368                        addIndex( getIndex( stride, 0 ) );
     369                        addIndex( getIndex( 0, halfStride ) );
     370                        addIndex( getIndex( 0, 0 ) );
     371                        break;
     372
     373                case ADAPT_RT:
     374                        addIndex( getIndex( stride, stride ) );
     375                        addIndex( getIndex( stride, halfStride ) );
     376                        addIndex( getIndex( halfStride, stride ) );
     377                        addIndex( getIndex( stride, 0 ) );
     378                        addIndex( getIndex( 0, stride ) );
     379                        addIndex( getIndex( 0, 0 ) );
     380                        break;
     381
     382                case ADAPT_LRT:
     383                        addIndex( getIndex( 0, 0 ) );
     384                        addIndex( getIndex( 0, halfStride ) );
     385                        addIndex( getIndex( stride, 0 ) );
     386                        addIndex( getIndex( 0, stride ) );
     387                        addIndex( getIndex( stride, halfStride ) );
     388                        addIndex( getIndex( halfStride, stride ) );
     389                        addIndex( getIndex( stride, stride ) );
     390                        addAgain(  );
     391                        break;
     392
     393                case ADAPT_BT:
     394                        addIndex( getIndex( 0, 0 ) );
     395                        addAgain(  );
     396                        addIndex( getIndex( halfStride, 0 ) );
     397                        addIndex( getIndex( 0, stride ) );
     398                        addIndex( getIndex( stride, 0 ) );
     399                        addIndex( getIndex( halfStride, stride ) );
     400                        addIndex( getIndex( stride, stride ) );
     401                        addAgain(  );
     402                        break;
     403
     404                case ADAPT_LBT:
     405                        addIndex( getIndex( 0, 0 ) );
     406                        addIndex( getIndex( 0, halfStride ) );
     407                        addIndex( getIndex( halfStride, 0 ) );
     408                        addIndex( getIndex( 0, stride ) );
     409                        addIndex( getIndex( stride, 0 ) );
     410                        addIndex( getIndex( halfStride, stride ) );
     411                        addIndex( getIndex( stride, stride ) );
     412                        addAgain(  );
     413                        break;
     414
     415                case ADAPT_RBT:
     416                        addIndex( getIndex( stride, stride ) );
     417                        addIndex( getIndex( stride, halfStride ) );
     418                        addIndex( getIndex( halfStride, stride ) );
     419                        addIndex( getIndex( stride, 0 ) );
     420                        addIndex( getIndex( 0, stride ) );
     421                        addIndex( getIndex( halfStride, 0 ) );
     422                        addIndex( getIndex( 0, 0 ) );
     423                        addAgain(  );
     424                        break;
     425
     426                case ADAPT_LRBT:
     427                        addIndex( getIndex( 0, 0 ) );
     428                        addIndex( getIndex( 0, halfStride ) );
     429                        addIndex( getIndex( halfStride, 0 ) );
     430                        addIndex( getIndex( 0, stride ) );
     431                        addIndex( getIndex( stride, 0 ) );
     432                        addIndex( getIndex( halfStride, stride ) );
     433                        addIndex( getIndex( stride, halfStride ) );
     434                        addIndex( getIndex( stride, stride ) );
     435                        break;
     436        }
     437}
     438
     439
    194440void TerrainPage::tesselate( int _lod )
    195441{
     442
    196443        int count = owner->getPageSize()*owner->getPageSize(); 
     444
    197445        memset( indexHash, 0xffff,
    198446                        sizeof(unsigned short)*count );
     447       
    199448        numVertices = 0; numIndices = 0;
    200449       
    201         assert( isVisible );
    202450        //Calculate the pace, based on the lod.
    203451        int stride = 1 << _lod;
    204         for ( int z = 0; z < owner->getPageSize()-stride; z+=stride ) {
    205                 if ( z > 0 ) {                 
    206                         //Connect the two rows together by inserting the last index of last row
    207                         //and the first index of the next row two times. This will produce two
    208                         //degenerate triangles.
    209                         addAgain( );
    210                         addIndex( getIndex( 0, z ) );
    211                 }
    212                 for ( int x = 0; x < owner->getPageSize(); x+=stride ) {
    213                         addIndex( getIndex( x, z ) );
    214                         addIndex( getIndex( x, z+stride ) );
    215                 }
    216         }
     452               
     453        bool adapt[4];
     454        determineBorderAdaption( adapt );
     455        assert( isVisible );
     456        if ( _lod == TerrainPage::MAX_LODS-1 ) {
     457                tesselateLevelFourPatch( adapt );
     458                return;
     459        }
     460       
     461        int zStart = 0, zEnd = owner->getPageSize()-stride;
     462       
     463        if ( adapt[TP_TOP] ) {
     464                tesselateRow( 0, stride / 2, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );
     465                zStart+= stride;
     466        }
     467       
     468        if ( adapt[TP_BOTTOM] )
     469                zEnd-= stride;
     470               
     471        for ( int z = zStart; z < zEnd; z+=stride )
     472                tesselateRow( z, stride, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );
     473       
     474
     475        if ( !adapt[TP_BOTTOM] )
     476                return;
     477               
     478        addAgain( );
     479        addIndex( getIndex( 0, owner->getPageSize()-1-stride ) );
     480       
     481        tesselateRow( owner->getPageSize()-1-stride, stride / 2, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );
     482
    217483}
    218484
  • branches/terrain/src/lib/graphics/importer/terrain/terrain_page.h

    r8328 r8349  
    3535class TerrainPage : public TerrainQuad {
    3636        public:
     37                enum { TP_LEFT = 0, TP_RIGHT = 1, TP_BOTTOM = 2, TP_TOP = 3 };
    3738                const static int MAX_LODS = 5;
    3839                /**
     
    112113                 * No geometry is updated in this method. You need to call
    113114                 * updateTesselation() in order to see a change in geometry. This method is
    114                  * just a recommandation.
     115                 * just a recommondation for the LOD. It might be invalid due to outer
     116                 * constraints.
    115117                 */
    116118                int chooseLOD();
     
    140142                 */
    141143                bool cull( );
    142                
     144
     145                bool needsRetesselation();
    143146                /**
    144147                 * Sets the neighbors of this terrain page. pass null if a neighbor if this
     
    160163                        position.z = _pos.z;
    161164                }
     165
     166                pTerrainPage getLeft() { return left; }
     167                pTerrainPage getRight() { return right; }
     168                pTerrainPage getBottom() { return bottom; }
     169                pTerrainPage getTop() { return top; }                                           
    162170               
    163171                /**
     
    175183                 */
    176184                inline pTerrainPage getPrevious() { return previous; }                 
    177                
     185                inline int getCurrentLOD() { return currentLOD; }
    178186                /**
    179187                 * @return Returns the wanted LOD. Make sure you call this method after a call to
     
    194202                protected:
    195203                       
    196                        
     204                        /**
     205                         * @brief Tesselates one row of the terrain page.
     206                         * @param _z                    The z-offset of the row
     207                         * @param _xStride              Determines the step-size horizontally
     208                         * @param _zStride              Determines the step-size vertically.
     209                         * @param _adaptRight   True if the right neighbor has a coarser
     210                         *                                              tesselation level.
     211                         * @param _adaptLeft    True if the left neighbor has a coarser
     212                         *                                              tesselation level.                     
     213                         */
     214                        void tesselateRow( int _z, int _xStride, int _zStride, bool _adaptLeft, bool _adaptRight );
     215
     216                        /**
     217                         * @brief Returns four boolean values in the oder
     218                         */
     219                        void determineBorderAdaption( bool _adapt[] );
     220                       
     221                        /**
     222                         * @brief Adds the given index to the index-array
     223                         */
    197224                        inline void addIndex( unsigned short _index );
    198        
     225                       
     226                        /**
     227                         * @brief We programmers are very lazy :) This method just adds the last added index
     228                         * again.
     229                         */
    199230                        inline void addAgain();
    200231                       
     232                       
    201233                        void getCoord( int _x, int _z, TexCoord& _coord) const;
     234                       
    202235                        /**
    203236                         * Fills _vertex with the vertex information at index.
     
    205238                        void getVertex( int _x, int _z, Triple& _vertex ) const;
    206239                       
    207                         /**
    208                         * Use this method to safely get a vertex at location ( _x, _z ). If it wasn't
    209                         * created before, this method does that for you.
    210                         */                     
     240                        /**
     241                         * Use this method to safely get a vertex at location ( _x, _z ). If it wasn't
     242                         * created before, this method does that for you.
     243                         */                     
    211244                        short getIndex( int _x, int _z );
    212                        
     245                        void tesselateLevelFourPatch( bool _adapt[] );
    213246                   /**
    214247                        * Generates the tesselation for the given level of detail.
Note: See TracChangeset for help on using the changeset viewer.