# Home    # nevrax.com   
Nevrax
Nevrax.org
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
Docs
 
Documentation  
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  

move_container.cpp

Go to the documentation of this file.
00001 
00007 /* Copyright, 2001 Nevrax Ltd.
00008  *
00009  * This file is part of NEVRAX NEL.
00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
00011  * it under the terms of the GNU General Public License as published by
00012  * the Free Software Foundation; either version 2, or (at your option)
00013  * any later version.
00014 
00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00018  * General Public License for more details.
00019 
00020  * You should have received a copy of the GNU General Public License
00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00023  * MA 02111-1307, USA.
00024  */
00025 
00026 #include "stdpacs.h"
00027 
00028 #include "pacs/move_primitive.h"
00029 #include "pacs/move_element.h"
00030 #include "pacs/primitive_block.h"
00031 
00032 #include "nel/misc/hierarchical_timer.h"
00033 
00034 #include "nel/misc/i_xml.h"
00035 #include <math.h>
00036 #include <float.h>
00037 
00038 using namespace NLMISC;
00039 
00040 #define NELPACS_ALLOC_DYNAMIC_INFO 100
00041 #define NELPACS_ALLOC_STATIC_INFO 100
00042 
00043 namespace NLPACS 
00044 {
00045 
00046 // ***************************************************************************
00047 
00048 CMoveContainer::~CMoveContainer ()
00049 {
00050         clear ();
00051 }
00052 
00053 // ***************************************************************************
00054 
00055 void CMoveContainer::clear ()
00056 {
00057         // Clear all primitives
00058         std::set<CMovePrimitive*>::iterator ite=_PrimitiveSet.begin();
00059         while (ite!=_PrimitiveSet.end ())
00060         {
00061                 freePrimitive (*ite);
00062                 ite++;
00063         }
00064 
00065         // Clear primitive set
00066         _PrimitiveSet.clear ();
00067 
00068         // Clear root changed
00069         _ChangedRoot.clear ();
00070 
00071         // Clear static world image set
00072         _StaticWorldImage.clear ();
00073 
00074         // Clear cell array
00075         _VectorCell.clear ();
00076 
00077         // Clear time ot
00078         _TimeOT.clear ();
00079 }
00080 
00081 // ***************************************************************************
00082 
00083 void CMoveContainer::init (double xmin, double ymin, double xmax, double ymax, uint widthCellCount, uint heightCellCount, 
00084                                                    double primitiveMaxSize, uint8 numWorldImage, uint maxIteration, uint otSize)
00085 {
00086         // Clear arrays
00087         clear ();
00088 
00089         // Create world images
00090         _ChangedRoot.resize (numWorldImage);
00091         for (uint i=0; i<numWorldImage; i++)
00092                 _ChangedRoot[i]=NULL;
00093 
00094         // Not in test mode
00095         _Retriever=NULL;
00096 
00097         // Element size
00098         _PrimitiveMaxSize=primitiveMaxSize;
00099 
00100         // BB
00101         _Xmin=xmin;
00102         _Ymin=ymin;
00103         _Xmax=xmax;
00104         _Ymax=ymax;
00105 
00106         // Cells count
00107         _CellCountWidth=widthCellCount;
00108         _CellCountHeight=heightCellCount;
00109 
00110         // Cells size
00111         _CellWidth=(_Xmax - _Xmin)/(double)_CellCountWidth;
00112         _CellHeight=(_Ymax - _Ymin)/(double)_CellCountHeight;
00113 
00114         // Cell array
00115         _VectorCell.resize (numWorldImage);
00116         for (uint j=0; j<numWorldImage; j++)
00117                 _VectorCell[j].resize (_CellCountWidth * _CellCountHeight);
00118 
00119         // resize OT
00120         _OtSize=otSize;
00121         _TimeOT.resize (otSize);
00122 
00123         // Clear the OT
00124         clearOT ();
00125 
00126         // Clear test time
00127         _TestTime=0xffffffff;
00128         _MaxTestIteration=maxIteration;
00129 
00130         // Resize trigger array
00131         _Triggers.resize (NELPACS_CONTAINER_TRIGGER_DEFAULT_SIZE);
00132 }
00133 
00134 // ***************************************************************************
00135 
00136 void CMoveContainer::init (CGlobalRetriever* retriever, uint widthCellCount, uint heightCellCount, double primitiveMaxSize, 
00137                 uint8 numWorldImage, uint maxIteration, uint otSize)
00138 {
00139         // Get min max of the global retriever BB
00140         CVector min=retriever->getBBox().getMin();
00141         CVector max=retriever->getBBox().getMax();
00142 
00143         // Setup min max
00144         double xmin=min.x;
00145         double ymin=min.y;
00146         double xmax=max.x;
00147         double ymax=max.y;
00148 
00149         // Init
00150         init (xmin, ymin, xmax, ymax, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
00151 
00152         // Init the retriever
00153         _Retriever=retriever;
00154 }
00155 
00156 // ***************************************************************************
00157 
00158 void  CMoveContainer::evalCollision (double deltaTime, uint8 worldImage)
00159 {
00160         NL_ALLOC_CONTEXT( Pacs )
00161 
00162 //      H_AUTO(PACS_MC_evalCollision);
00163 
00164         // New test time
00165         _TestTime++;
00166 
00167         // Delta time
00168         _DeltaTime=deltaTime;
00169 
00170         // Clear triggers
00171         _Triggers.clear ();
00172 
00173         // Update the bounding box and position of modified primitives
00174         updatePrimitives (0.f, worldImage);
00175 
00176 #ifdef NL_DEBUG
00177         // Check list integrity
00178         //checkSortedList ();
00179 #endif // NL_DEBUG
00180 
00181         // Get first collision
00182         _PreviousCollisionNode = &_TimeOT[0];
00183 
00184         // Eval all collisions
00185         evalAllCollisions (0.f, worldImage);
00186 
00187         // Clear modified list
00188         clearModifiedList (worldImage);
00189 
00190         // Modified list is empty at this point
00191         nlassert (_ChangedRoot[worldImage]==NULL);
00192 
00193         // Previous node is a 'hard' OT node
00194         nlassert (!_PreviousCollisionNode->isInfo());
00195 
00196         // Get next collision
00197         CCollisionOTInfo        *nextCollision=_PreviousCollisionNode->getNextInfo ();
00198 
00199         // Collision ?
00200         while (nextCollision)
00201         {
00202                 // Get new previous OT hard node
00203                 _PreviousCollisionNode=nextCollision->getPrevious ();
00204 
00205                 // Previous node is a 'hard' OT node
00206                 nlassert (!_PreviousCollisionNode->isInfo());
00207 
00208                 // Keep this collision
00209                 reaction (*nextCollision);
00210 
00211                 // Last time
00212                 double newTime=nextCollision->getCollisionTime ();
00213 
00214                 // Remove modified objects from the OT
00215                 removeModifiedFromOT (worldImage);
00216 
00217                 // Must have been removed
00218                 nlassert (nextCollision->getPrevious ()==NULL);
00219                 nlassert (nextCollision->CCollisionOT::getNext ()==NULL);
00220 
00221                 // Update the bounding box and position of modified primitives
00222                 updatePrimitives (newTime, worldImage);
00223 
00224                 // Eval all collisions of modified objects for the new delta t
00225                 evalAllCollisions (newTime, worldImage);
00226 
00227                 // Clear modified list
00228                 clearModifiedList (worldImage);
00229 
00230                 // Get next collision
00231                 nextCollision=_PreviousCollisionNode->getNextInfo ();
00232         }
00233 
00234 #ifdef NL_DEBUG
00235         // OT must be cleared
00236         checkOT ();
00237 #endif // NL_DEBUG
00238 
00239         // Free ordered table info
00240         freeAllOTInfo ();
00241 
00242         // Some init
00243         _PreviousCollisionNode=NULL;
00244 }
00245 
00246 // ***************************************************************************
00247 
00248 bool CMoveContainer::testMove (UMovePrimitive* primitive, const CVectorD& speed, double deltaTime, uint8 worldImage, CVectorD *contactNormal)
00249 {
00250         NL_ALLOC_CONTEXT( Pacs )
00251 
00252 //      H_AUTO(PACS_MC_testMove);
00253 
00254         if (contactNormal)
00255                 *contactNormal = CVectorD::Null;
00256 
00257         // Cast
00258         nlassert (dynamic_cast<CMovePrimitive*>(primitive));
00259         CMovePrimitive* prim=static_cast<CMovePrimitive*>(primitive);
00260 
00261         // New test time
00262         _TestTime++;
00263 
00264         // Delta time
00265         _DeltaTime=deltaTime;
00266 
00267         // Get the world image primitive
00268         uint8 primitiveWorldImage;
00269         CPrimitiveWorldImage *wI;
00270         if (prim->isNonCollisionable ())
00271         {
00272                 wI=prim->getWorldImage (0);
00273                 primitiveWorldImage=worldImage;
00274         }
00275         else
00276         {
00277                 wI=prim->getWorldImage (worldImage);
00278                 primitiveWorldImage=worldImage;
00279         }
00280 
00281         // Backup speed
00282         CVectorD oldSpeed=wI->getSpeed ();
00283 
00284         // Set speed
00285         wI->move (speed, *this, *prim, primitiveWorldImage);
00286 
00287         // Update the bounding box and position of the primitive
00288         wI->update (0, _DeltaTime, *prim);
00289 
00290         // Compute cells overlaped by the primitive
00291         if (!prim->isNonCollisionable ())
00292                 updateCells (prim, worldImage);
00293 
00294 #ifdef NL_DEBUG
00295         // Check list integrity
00296 //      checkSortedList ();
00297 #endif // NL_DEBUG
00298 
00299         // Result
00300         bool result=false;
00301         bool testMoveValid;
00302 
00303         // Eval first each static world images
00304         result=evalOneTerrainCollision (0, prim, primitiveWorldImage, true, testMoveValid, NULL, contactNormal);
00305 
00306         // Eval first each static world images
00307         if (!result)
00308         {
00309                 std::set<uint8>::iterator ite=_StaticWorldImage.begin();
00310                 while (ite!=_StaticWorldImage.end())
00311                 {
00312 
00313                         // Eval in this world image
00314                         result=evalOnePrimitiveCollision (0, prim, *ite, primitiveWorldImage, true, true, testMoveValid, NULL, contactNormal);
00315 
00316                         // If found, abort
00317                         if (result)
00318                                 break;
00319 
00320                         // Next world image
00321                         ite++;
00322                 }
00323         }
00324 
00325         // Eval collisions if not found and not tested
00326         if ((!result) && (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end()))
00327                 result=evalOnePrimitiveCollision (0, prim, worldImage, primitiveWorldImage, true, false, testMoveValid, NULL, contactNormal);
00328 
00329         // Backup speed only if the primitive is inserted in the world image
00330         if (prim->isInserted (primitiveWorldImage))
00331                 wI->move (oldSpeed, *this, *prim, primitiveWorldImage);
00332 
00333 #ifdef NL_DEBUG
00334         // OT must be cleared
00335         checkOT ();
00336 #endif // NL_DEBUG
00337 
00338         // Free ordered table info
00339         freeAllOTInfo ();
00340 
00341         // Some init
00342         _PreviousCollisionNode=NULL;
00343 
00344         // Return result
00345         return !result;
00346 }
00347 
00348 // ***************************************************************************
00349 
00350 void CMoveContainer::updatePrimitives (double beginTime, uint8 worldImage)
00351 {
00352 //      H_AUTO(PACS_MC_updatePrimitives);
00353 
00354         // For each changed primitives
00355         CMovePrimitive *changed=_ChangedRoot[worldImage];
00356         while (changed)
00357         {
00358                 // Get the primitive world image
00359                 CPrimitiveWorldImage *wI;
00360                 if (changed->isNonCollisionable())
00361                         wI=changed->getWorldImage (0);
00362                 else
00363                         wI=changed->getWorldImage (worldImage);
00364 
00365                 // Force the build of the bounding box
00366                 wI->update (beginTime, _DeltaTime, *changed);
00367 
00368                 // Is inserted in this world image ?
00369                 if (changed->isInserted (worldImage))
00370                 {
00371 
00372                         // Compute cells overlaped by the primitive
00373                         updateCells (changed, worldImage);
00374                 }
00375 
00376                 // Next primitive
00377                 changed=wI->getNextModified ();
00378         }
00379 }
00380 
00381 // ***************************************************************************
00382 
00383 void CMoveContainer::updateCells (CMovePrimitive *primitive, uint8 worldImage)
00384 {
00385 //      H_AUTO(PACS_MC_updateCells);
00386 
00387         // Get the primitive world image
00388         CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
00389 
00390         // Check BB width not too large
00391         if (wI->getBBXMax() - wI->getBBXMin() > _CellWidth)
00392         {
00393                 nlwarning ("Primitives have moved more than a cell.");
00394         }
00395 
00396         // Check BB height not too large
00397         if (wI->getBBYMax() - wI->getBBYMin() > _CellHeight)
00398         {
00399                 nlwarning ("Primitives have moved more than a cell.");
00400         }
00401 
00402         // Get coordinate in the cell array
00403         sint minx=(int)floor ((wI->getBBXMin() - _Xmin) / _CellWidth);
00404         sint miny=(int)floor ((wI->getBBYMin() - _Ymin) / _CellHeight);
00405         sint maxx=(int)floor ((wI->getBBXMax() - _Xmin) / _CellWidth);
00406         sint maxy=(int)floor ((wI->getBBYMax() - _Ymin) / _CellHeight);
00407 
00408         // Born
00409         if (minx<0)
00410                 minx=0;
00411         if (miny<0)
00412                 miny=0;
00413         if (maxx>=(int)_CellCountWidth)
00414                 maxx=(int)_CellCountWidth-1;
00415         if (maxy>=(int)_CellCountHeight)
00416                 maxy=(int)_CellCountHeight-1;
00417 
00418         maxx=std::min (minx+1, maxx);
00419         maxy=std::min (miny+1, maxy);
00420 
00421         // flags founded
00422         bool found[4]={false, false, false, false};
00423 
00424         // For each old cells
00425         uint i;
00426         for (i=0; i<4; i++)
00427         {
00428                 // Element
00429                 CMoveElement *elm = wI->getMoveElement (i);
00430 
00431                 // Old element in this cell ?
00432                 if ( elm )
00433                 {
00434                         // Check
00435                         nlassert (elm->X<_CellCountWidth);
00436                         nlassert (elm->Y<_CellCountHeight);
00437 
00438                         // Must remove it ?
00439                         if ( (elm->X < minx) || (elm->X > maxx) || (elm->Y < miny) || (elm->Y > maxy) )
00440                         {
00441                                 // Yes remove it
00442                                 wI->removeMoveElement (i, *this, worldImage);
00443                         }
00444                         else
00445                         {
00446                                 // Checks
00447                                 nlassert (((elm->X - minx)==0)||((elm->X - minx)==1));
00448                                 nlassert (((elm->Y - miny)==0)||((elm->Y - miny)==1));
00449 
00450                                 // Update position
00451 #ifndef TEST_CELL
00452                                 _VectorCell[worldImage][elm->X+elm->Y*_CellCountWidth].updateSortedLists (elm, worldImage);
00453 #endif
00454 
00455                                 // Check found cells
00456                                 found[ elm->X - minx + ((elm->Y - miny) << (maxx-minx)) ]=true;
00457                         }
00458                 }
00459         }
00460 
00461         // For each case selected
00462         int x, y;
00463         i=0;
00464         for (y=miny; y<=(int)maxy; y++)
00465         for (x=minx; x<=(int)maxx; x++)
00466         {
00467                 // Check the formula
00468                 nlassert ((int)i == (x - minx + ((y - miny) << (maxx-minx)) ));
00469 
00470                 // If the cell is not found
00471                 if (!found[i])
00472                 {
00473                         // Center of the cell
00474                         double cx=((double)x+0.5f)*_CellWidth+_Xmin;
00475                         double cy=((double)y+0.5f)*_CellHeight+_Ymin;
00476 
00477                         // Add it in the list
00478                         wI->addMoveElement (_VectorCell[worldImage][x+y*_CellCountWidth], (uint16)x, (uint16)y, cx, cy, primitive, *this, worldImage);
00479                 }
00480 
00481                 // Next cell
00482                 i++;
00483         }
00484 }
00485 
00486 // ***************************************************************************
00487 
00488 void CMoveContainer::getCells (CMovePrimitive *primitive, uint8 worldImage, uint8 primitiveWorldImage, CMoveElement **elementArray)
00489 {
00490 //      H_AUTO(PACS_MC_getCells);
00491 
00492         // Get the primitive world image
00493         CPrimitiveWorldImage *wI;
00494         if (primitive->isNonCollisionable())
00495                 wI=primitive->getWorldImage (0);        
00496         else
00497                 wI=primitive->getWorldImage (primitiveWorldImage);
00498 
00499         // Check BB width not too large
00500         if (wI->getBBXMax() - wI->getBBXMin() > _CellWidth)
00501         {
00502                 nlwarning ("Primitives have moved more than a cell.");
00503         }
00504 
00505         // Check BB height not too large
00506         if (wI->getBBYMax() - wI->getBBYMin() > _CellHeight)
00507         {
00508                 nlwarning ("Primitives have moved more than a cell.");
00509         }
00510 
00511         // Get coordinate in the cell array
00512         int minx=(int)floor ((wI->getBBXMin() - _Xmin) / _CellWidth);
00513         int miny=(int)floor ((wI->getBBYMin() - _Ymin) / _CellHeight);
00514         int maxx=(int)floor ((wI->getBBXMax() - _Xmin) / _CellWidth);
00515         int maxy=(int)floor ((wI->getBBYMax() - _Ymin) / _CellHeight);
00516 
00517         // Born
00518         if (minx<0)
00519                 minx=0;
00520         if (miny<0)
00521                 miny=0;
00522         if (maxx>=(int)_CellCountWidth)
00523                 maxx=(int)_CellCountWidth-1;
00524         if (maxy>=(int)_CellCountHeight)
00525                 maxy=(int)_CellCountHeight-1;
00526 
00527         maxx=std::min (minx+1, maxx);
00528         maxy=std::min (miny+1, maxy);
00529 
00530         // For each case selected
00531         int x, y;
00532         int i=0;
00533         for (y=miny; y<=(int)maxy; y++)
00534         for (x=minx; x<=(int)maxx; x++)
00535         {
00536                 // Check the formula
00537                 nlassert ((int)i == (x - minx + ((y - miny) << (maxx-minx)) ));
00538 
00539                 // Center of the cell
00540                 double cx=((double)x+0.5f)*_CellWidth+_Xmin;
00541 
00542                 // Primitive center
00543                 double pcx=(wI->getBBXMin()+wI->getBBXMax())/2.f;
00544 
00545                 elementArray[i]->Primitive=primitive;
00546                 elementArray[i]->X=x;
00547                 elementArray[i]->Y=y;
00548                 // Insert in left or right ?
00549                 if (pcx<cx)
00550                 {
00551                         // In the left
00552                         elementArray[i]->NextX=_VectorCell[worldImage][x+y*_CellCountWidth].getFirstX ();
00553                         elementArray[i]->PreviousX=NULL;
00554                 }
00555                 else
00556                 {
00557                         // In the right
00558                         elementArray[i]->PreviousX=_VectorCell[worldImage][x+y*_CellCountWidth].getLastX ();
00559                         elementArray[i]->NextX=NULL;
00560                 }
00561 
00562                 // Next cell
00563                 i++;
00564         }
00565 
00566         // Erase last array element
00567         for (; i<4; i++)
00568         {
00569                 elementArray[i]=NULL;
00570         }
00571 }
00572 
00573 // ***************************************************************************
00574 
00575 void CMoveContainer::clearModifiedList (uint8 worldImage)
00576 {
00577         // For each changed primitives
00578         CMovePrimitive *changed=_ChangedRoot[worldImage];
00579         while (changed)
00580         {
00581                 // Get the world image primitive
00582                 CPrimitiveWorldImage *wI;
00583                 if (changed->isNonCollisionable())
00584                         wI=changed->getWorldImage (0);
00585                 else
00586                         wI=changed->getWorldImage (worldImage);
00587                 
00588                 // Next primitive
00589                 changed=wI->getNextModified ();
00590 
00591                 // Remove it from the list
00592                 wI->setInModifiedListFlag (false);
00593         }
00594 
00595         // Empty list
00596         _ChangedRoot[worldImage]=NULL;
00597 }
00598 
00599 // ***************************************************************************
00600 
00601 void CMoveContainer::checkSortedList ()
00602 {
00603         // Check each primitives in the set
00604         std::set<CMovePrimitive*>::iterator ite=_PrimitiveSet.begin();
00605         while (ite!=_PrimitiveSet.end())
00606         {
00607                 // Check
00608                 (*ite)->checkSortedList ();
00609 
00610                 ite++;
00611         }
00612 }
00613 
00614 // ***************************************************************************
00615 
00616 bool CMoveContainer::evalOneTerrainCollision (double beginTime, CMovePrimitive *primitive, uint8 primitiveWorldImage, 
00617                                                                            bool testMove, bool &testMoveValid, CCollisionOTStaticInfo *staticColInfo, CVectorD *contactNormal)
00618 {
00619 //      H_AUTO(PACS_MC_evalOneCollision);
00620 
00621         // Find its collisions
00622         bool found=false;
00623 
00624         // Get the primitive world image
00625         CPrimitiveWorldImage *wI;
00626         if (primitive->isNonCollisionable())
00627                 wI=primitive->getWorldImage (0);
00628         else
00629                 wI=primitive->getWorldImage (primitiveWorldImage);
00630 
00631         // Begin time must be the same as beginTime
00632         nlassert (wI->getInitTime()==beginTime);
00633 
00634         // Test its static collision
00635         if (_Retriever)
00636         {
00637                 // Delta pos..
00638                 // Test retriever with the primitive
00639                 const TCollisionSurfaceDescVector *result=wI->evalCollision (*_Retriever, _SurfaceTemp, _TestTime, _MaxTestIteration, *primitive);
00640                 if (result)
00641                 {
00642                         // TEST MOVE MUST BE OK !!
00643                         testMoveValid=true;
00644 
00645                         // Size of the array
00646                         uint size=result->size();
00647 
00648                         // For each detected collisions
00649                         for (uint c=0; c<size; c++)
00650                         {
00651                                 // Ref on the collision
00652                                 CCollisionSurfaceDesc desc=(*result)[c];
00653                                 double contactTime = (_DeltaTime-beginTime)*desc.ContactTime+beginTime;
00654 
00655                                 /*
00656                                  *  If beginTime is 0.999999999 and desc.ContactTime<1.0, contactTime will be 1.0.
00657                                  *  In this case, we force contactTime to be beginTime to avoid collision at time == 1.0.
00658                                 **/
00659                                 if ((contactTime >= 1.0) && (beginTime < 1.0) && (desc.ContactTime < 1.0))
00660                                         contactTime = beginTime;
00661 
00662                                 // Set the container's time space contact time
00663                                 desc.ContactTime = contactTime;
00664 
00665                                 // ptr on the surface
00666                                 const CRetrievableSurface *surf= _Retriever->getSurfaceById (desc.ContactSurface);
00667 
00668                                 // TODO: check surface flags  against primitive flags HERE:
00669                                 // Is a wall ?
00670                                 bool isWall;
00671                                 if(!surf)
00672                                         isWall= true;
00673                                 else
00674                                         isWall= !(surf->isFloor() || surf->isCeiling());
00675 
00676                                 // stop on a wall.
00677                                 if(isWall)
00678                                 {
00679                                         // Test move ?
00680                                         if (testMove)
00681                                         {
00682                                                 // return contact normal only when testmove and vector provided
00683                                                 if (contactNormal)
00684                                                         *contactNormal = desc.ContactNormal;
00685                                                 return true;
00686                                         }
00687                                         else
00688                                         {
00689                                                 // OK, collision if we are a collisionable primitive
00690                                                 newCollision (primitive, desc, primitiveWorldImage, beginTime, staticColInfo);
00691 
00692                                                 // One collision found
00693                                                 found=true;
00694                                                 break;
00695                                         }
00696                                 }
00697                         }
00698                 }
00699                 else
00700                         // More than maxtest made, exit
00701                         return false;
00702         }
00703         return found;
00704 }
00705 
00706 // ***************************************************************************
00707 
00708 bool CMoveContainer::evalOnePrimitiveCollision (double beginTime, CMovePrimitive *primitive, uint8 worldImage, uint8 primitiveWorldImage, 
00709                                                                            bool testMove, bool secondIsStatic, bool &testMoveValid, CCollisionOTDynamicInfo *dynamicColInfo,
00710                                                                                 CVectorD *contactNormal)
00711 {
00712 //      H_AUTO(PACS_MC_evalOneCollision);
00713 
00714         // Find its collisions
00715         bool found=false;
00716 
00717         // Get the primitive world image
00718         CPrimitiveWorldImage *wI;
00719         if (primitive->isNonCollisionable())
00720                 wI=primitive->getWorldImage (0);
00721         else
00722                 wI=primitive->getWorldImage (primitiveWorldImage);
00723 
00724         // Begin time must be the same as beginTime
00725         nlassert (wI->getInitTime()==beginTime);
00726 
00727         // Element table
00728         CMoveElement    tableNotInserted[4];
00729         CMoveElement    *table[4];
00730 
00731         // Single test ?
00732         bool singleTest=testMove;
00733         
00734         // Is in world image
00735         if ((worldImage==primitiveWorldImage) && wI->isInWorldImageFlag())
00736         {
00737                 // Get move element table from the primitive
00738                 table[0]=wI->getMoveElement (0);
00739                 table[1]=wI->getMoveElement (1);
00740                 table[2]=wI->getMoveElement (2);
00741                 table[3]=wI->getMoveElement (3);
00742         }
00743         else
00744         {
00745                 // Set table pointers
00746                 table[0]=tableNotInserted+0;
00747                 table[1]=tableNotInserted+1;
00748                 table[2]=tableNotInserted+2;
00749                 table[3]=tableNotInserted+3;
00750 
00751                 // Get cells
00752                 getCells (primitive, worldImage, primitiveWorldImage, table);
00753 
00754                 // Force the test
00755                 singleTest=true;
00756         }
00757 
00758         // For each move element
00759         for (uint i=0; i<4; i++)
00760         {
00761                 // Get the element
00762                 CMoveElement    *elm=table[i];
00763 
00764                 // Element valid ?
00765                 if (elm)
00766                 {
00767                         // Check
00768                         nlassert (elm->Primitive==primitive);
00769                         // Primitive to the left
00770 
00771                         // Lookup in X sorted list on the left
00772                         CMoveElement    *other=elm->PreviousX;
00773                         nlassert (other!=elm);
00774 
00775                         while (other && (wI->getBBXMin() - other->Primitive->getWorldImage(worldImage)->getBBXMin() < _PrimitiveMaxSize) )
00776                         {
00777                                 // Other primitive
00778                                 CMovePrimitive  *otherPrimitive=other->Primitive;
00779                                 CPrimitiveWorldImage *otherWI=otherPrimitive->getWorldImage (worldImage);
00780                                 nlassert (otherPrimitive!=primitive);
00781 
00782                                 // Continue the check if the other primitive is not int the modified list or if its pointer is higher than primitive
00783                                 if ( singleTest || ( (!otherWI->isInModifiedListFlag ()) || (primitive<otherPrimitive) ) )
00784                                 {
00785                                         // Look if valid in X
00786                                         if (wI->getBBXMin() < otherWI->getBBXMax())
00787                                         {
00788                                                 // Look if valid in Y
00789                                                 if ( (wI->getBBYMin() < otherWI->getBBYMax()) && (otherWI->getBBYMin() < wI->getBBYMax()) )
00790                                                 {
00791                                                         if (evalPrimAgainstPrimCollision (beginTime, primitive, otherPrimitive, wI, otherWI, testMove,
00792                                                                 primitiveWorldImage, worldImage, secondIsStatic, dynamicColInfo, contactNormal))
00793                                                         {
00794                                                                 if (testMove)
00795                                                                         return true;
00796                                                                 found=true;
00797                                                         }
00798                                                 }
00799                                         }
00800                                 }
00801 
00802                                 // Next primitive to the left
00803                                 other = other->PreviousX;
00804                         }
00805 
00806                         // Lookup in X sorted list on the right
00807                         other=elm->NextX;
00808 
00809                         // Primitive to the right
00810                         while (other && (other->Primitive->getWorldImage(worldImage)->getBBXMin() < wI->getBBXMax()) )
00811                         {
00812                                 // Other primitive
00813                                 CMovePrimitive  *otherPrimitive=other->Primitive;
00814                                 CPrimitiveWorldImage *otherWI=otherPrimitive->getWorldImage (worldImage);
00815                                 nlassert (otherPrimitive!=primitive);
00816 
00817                                 // Continue the check if the other primitive is not in the modified list or if its pointer is higher than primitive
00818                                 if ( singleTest || ( (!otherWI->isInModifiedListFlag ()) || (primitive<otherPrimitive) ) )
00819                                 {
00820                                         // Look if valid in Y
00821                                         if ( (wI->getBBYMin() < otherWI->getBBYMax()) && (otherWI->getBBYMin() < wI->getBBYMax()) )
00822                                         {
00823                                                 if (evalPrimAgainstPrimCollision (beginTime, primitive, otherPrimitive, wI, otherWI, testMove,
00824                                                         primitiveWorldImage, worldImage, secondIsStatic, dynamicColInfo, contactNormal))
00825                                                 {
00826                                                         if (testMove)
00827                                                                 return true;
00828                                                         found=true;
00829                                                 }
00830                                         }
00831                                 }
00832 
00833                                 // Next primitive to the left
00834                                 other = other->NextX;
00835                         }
00836                 }
00837         }
00838 
00839         return found;
00840 }
00841 
00842 // ***************************************************************************
00843 
00844 bool CMoveContainer::evalPrimAgainstPrimCollision (double beginTime, CMovePrimitive *primitive, CMovePrimitive *otherPrimitive, 
00845                                                                                         CPrimitiveWorldImage *wI, CPrimitiveWorldImage *otherWI, bool testMove,
00846                                                                                         uint8 firstWorldImage, uint8 secondWorldImage, bool secondIsStatic, CCollisionOTDynamicInfo *dynamicColInfo,
00847                                                                                         CVectorD *contactNormal)
00848 {
00849 //      H_AUTO(PACS_MC_evalPrimAgainstPrimCollision);
00850 
00851         // Test the primitive
00852         double firstTime, lastTime;
00853 
00854         // Collision
00855         CCollisionDesc desc;
00856         if (wI->evalCollision (*otherWI, desc, beginTime, _DeltaTime, _TestTime, _MaxTestIteration, 
00857                                                                 firstTime, lastTime, *primitive, *otherPrimitive))
00858         {
00859                 // Enter or exit
00860                 bool enter = (beginTime<=firstTime) && (firstTime<_DeltaTime);
00861                 bool exit = (beginTime<=lastTime) && (lastTime<_DeltaTime);
00862                 bool overlap = (firstTime<=beginTime) && (lastTime>_DeltaTime);
00863                 bool collision = ( beginTime<=((firstTime+lastTime)/2) ) && (firstTime<=_DeltaTime);
00864 
00865                 // Return collision time
00866 
00867                 if (testMove && collision)
00868                         return true;
00869                 else
00870                 {
00871                         // TODO: make new collision when collision==false to raise triggers
00872 
00881                         if (primitive->isNonCollisionable () && (enter || exit || overlap))
00882                         {
00883                                 if (primitive->isTriggered (*otherPrimitive, enter, exit))
00884                                 {
00885                                         // Add a trigger
00886                                         newTrigger (primitive, otherPrimitive, desc, enter ? UTriggerInfo::In : exit ? UTriggerInfo::Out : UTriggerInfo::Inside);
00887                                 }
00888 
00889                                 // If the other primitive is not an obstacle, skip it because it will re-generate collisions.
00890                                 if (!otherPrimitive->isObstacle ())
00891                                         return false;
00892                         }
00893 
00894                         // OK, collision
00895                         if (collision)
00896                                 newCollision (primitive, otherPrimitive, desc, collision, enter, exit, firstWorldImage, secondWorldImage, secondIsStatic,
00897                                                                 dynamicColInfo);
00898 
00899                         // Collision
00900                         return collision;
00901                 }
00902         }
00903         return false;
00904 }
00905 
00906 // ***************************************************************************
00907 
00908 void CMoveContainer::evalAllCollisions (double beginTime, uint8 worldImage)
00909 {
00910 //      H_AUTO(PACS_MC_evalAllCollisions);
00911 
00912         // First primitive
00913         CMovePrimitive  *primitive=_ChangedRoot[worldImage];
00914 
00915         // For each modified primitive
00916         while (primitive)
00917         {
00918                 // Get the primitive world image
00919                 uint8 primitiveWorldImage;
00920                 CPrimitiveWorldImage *wI;
00921                 if (primitive->isNonCollisionable ())
00922                 {
00923                         wI=primitive->getWorldImage (0);
00924                         primitiveWorldImage=worldImage;
00925                 }
00926                 else
00927                 {
00928                         wI=primitive->getWorldImage (worldImage);
00929                         primitiveWorldImage=worldImage;
00930                 }
00931 
00932                 CVectorD d0=wI->getDeltaPosition();
00933 
00934                 // Find a collision
00935                 bool found=false;
00936                 bool testMoveValid=false;
00937 
00938                 // Eval collision on the terrain
00939                 found|=evalOneTerrainCollision (beginTime, primitive, primitiveWorldImage, false, testMoveValid, NULL, NULL);
00940 
00941                 // Eval collision in each static world image
00942                 std::set<uint8>::iterator ite=_StaticWorldImage.begin();
00943                 while (ite!=_StaticWorldImage.end())
00944                 {
00945                         // Eval in this world image
00946                         found|=evalOnePrimitiveCollision (beginTime, primitive, *ite, primitiveWorldImage, false, true, testMoveValid, NULL, NULL);
00947 
00948                         // Next world image
00949                         ite++;
00950                 }
00951 
00952                 CVectorD d1=wI->getDeltaPosition();
00953 
00954                 // Eval collision in the world image if not already tested
00955                 if (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end())
00956                         found|=evalOnePrimitiveCollision (beginTime, primitive, worldImage, primitiveWorldImage, false, false, testMoveValid, NULL, NULL);
00957 
00958                 CVectorD d2=wI->getDeltaPosition();
00959 
00960                 // No collision ?
00961                 if (!found)
00962                 {
00963                         nlassert ((d0==d1)&&(d0==d2));
00964 //                      nlassert (f1==f2);
00965                         if (_Retriever&&testMoveValid)
00966                         {                                                               
00967                                 // Do move
00968                                 wI->doMove (*_Retriever, _SurfaceTemp, _DeltaTime, _DeltaTime, primitive->getDontSnapToGround());                               
00969                         }
00970                         else
00971                         {
00972                                 // Do move
00973                                 wI->doMove (_DeltaTime);
00974                         }
00975                 }
00976 
00977                 // Next primitive
00978                 primitive=wI->getNextModified ();
00979         }
00980 }
00981 
00982 // ***************************************************************************
00983 
00984 void CMoveContainer::newCollision (CMovePrimitive* first, CMovePrimitive* second, const CCollisionDesc& desc, bool collision, bool enter, bool exit,
00985                                                                    uint firstWorldImage, uint secondWorldImage, bool secondIsStatic, CCollisionOTDynamicInfo *dynamicColInfo)
00986 {
00987 //      H_AUTO(PACS_MC_newCollision_short);
00988 
00989         nlassert ((dynamicColInfo && first->isNonCollisionable ()) || (!dynamicColInfo && first->isCollisionable ()));
00990 
00991         if (dynamicColInfo)
00992         {
00993                 dynamicColInfo->init (first, second, desc, collision, enter, exit, firstWorldImage, secondWorldImage, secondIsStatic);
00994         }
00995         else
00996         {
00997                 // Get an ordered time index. Always round to the future.
00998                 int index=(int)(ceil (desc.ContactTime*(double)_OtSize/_DeltaTime) );
00999 
01000                 // Clamp left.
01001                 if (index<0)
01002                         index=0;
01003 
01004                 // If in time
01005                 if (index<(int)_OtSize)
01006                 {
01007                         // Build info
01008                         CCollisionOTDynamicInfo *info = allocateOTDynamicInfo ();
01009                         info->init (first, second, desc, collision, enter, exit, firstWorldImage, secondWorldImage, secondIsStatic);
01010 
01011                         // Add in the primitive list
01012                         first->addCollisionOTInfo (info);
01013                         second->addCollisionOTInfo (info);
01014 
01015                         // Insert in the time ordered table
01016                         nlassert (index<(int)_TimeOT.size());
01017                         _TimeOT[index].link (info);
01018 
01019                         // Check it is after the last hard collision
01020                         nlassert (_PreviousCollisionNode<=&_TimeOT[index]);
01021                 }
01022         }
01023 }
01024 
01025 // ***************************************************************************
01026 
01027 void CMoveContainer::newCollision (CMovePrimitive* first, const CCollisionSurfaceDesc& desc, uint8 worldImage, double beginTime, CCollisionOTStaticInfo *staticColInfo)
01028 {
01029 //      H_AUTO(PACS_MC_newCollision_long);
01030 
01031         // Check
01032         nlassert (_Retriever);
01033         nlassert ((staticColInfo && first->isNonCollisionable ()) || (!staticColInfo && first->isCollisionable ()));
01034 
01035         // Get the world image
01036         CPrimitiveWorldImage *wI;
01037         if (first->isNonCollisionable())
01038                 wI=first->getWorldImage (0);
01039         else
01040                 wI=first->getWorldImage (worldImage);
01041 
01042         // Time
01043         double time=desc.ContactTime;
01044 /*
01045         if (time == _DeltaTime)
01046                 time -= _DeltaTime*FLT_EPSILON;
01047 */
01048 
01049         // Check time interval
01050         nlassertex (beginTime<=time, ("beginTime=%f, time=%f", beginTime, time));
01051         nlassertex (time<_DeltaTime, ("time=%f, _DeltaTime=%f", time, _DeltaTime));
01052 
01053         // Time of the collision.
01054         time-=NELPACS_DIST_BACK/wI->getSpeed().norm();
01055         time=std::max(time, beginTime);
01056         double ratio=(time-beginTime)/(_DeltaTime-beginTime);
01057         nlassert (ratio>=0);
01058         nlassert (ratio<=1);
01059 
01060         if (staticColInfo)
01061         {
01062                 // Make a new globalposition
01063                 UGlobalPosition endPosition=_Retriever->doMove (wI->getGlobalPosition(), wI->getDeltaPosition(), 
01064                         (float)ratio, _SurfaceTemp, false);
01065 
01066                 // Init the info descriptor
01067                 staticColInfo->init (first, desc, endPosition, ratio, worldImage);
01068         }
01069         else
01070         {
01071                 // Get an ordered time index. Always round to the future.
01072                 int index=(int)(ceil (time*(double)_OtSize/_DeltaTime) );
01073 
01074                 // Clamp left.
01075                 if (index<0)
01076                         index=0;
01077 
01078                 // If in time
01079                 if (index<(int)_OtSize)
01080                 {
01081                         // Build info
01082                         CCollisionOTStaticInfo *info = allocateOTStaticInfo ();
01083 
01084                         // Make a new globalposition
01085                         UGlobalPosition endPosition=_Retriever->doMove (wI->getGlobalPosition(), wI->getDeltaPosition(), 
01086                                 (float)ratio, _SurfaceTemp, false);
01087 
01088                         // Init the info descriptor
01089                         info->init (first, desc, endPosition, ratio, worldImage);
01090 
01091                         // Add in the primitive list
01092                         first->addCollisionOTInfo (info);
01093 
01094                         // Insert in the time ordered table
01095                         nlassert (index<(int)_TimeOT.size());
01096                         _TimeOT[index].link (info);
01097 
01098                         // Check it is after the last hard collision
01099                         nlassert (_PreviousCollisionNode<=&_TimeOT[index]);
01100                 }
01101         }
01102 }
01103 
01104 // ***************************************************************************
01105 
01106 void CMoveContainer::newTrigger (CMovePrimitive* first, CMovePrimitive* second, const CCollisionDesc& desc, uint triggerType)
01107 {
01108         // Element index
01109         uint index=_Triggers.size();
01110 
01111         // Add one element
01112         _Triggers.resize (index+1);
01113 
01114         // Fill info
01115         _Triggers[index].Object0=first->UserData;
01116         _Triggers[index].Object1=second->UserData;
01117         _Triggers[index].CollisionDesc=desc;
01118         _Triggers[index].CollisionType = triggerType;
01119 }
01120 
01121 // ***************************************************************************
01122 
01123 void CMoveContainer::checkOT ()
01124 {
01125         // Check
01126         nlassert (_OtSize==_TimeOT.size());
01127 
01128         // Check linked list
01129         for (uint i=0; i<_OtSize-1; i++)
01130         {
01131                 // Check link
01132                 nlassert ( _TimeOT[i].getNext() == (&(_TimeOT[i+1])) );
01133                 nlassert ( _TimeOT[i+1].getPrevious() == (&(_TimeOT[i])) );
01134         }
01135 
01136         // Check first and last
01137         nlassert ( _TimeOT[0].getPrevious() == NULL );
01138         nlassert ( _TimeOT[_OtSize-1].getNext() == NULL );
01139 }
01140 
01141 // ***************************************************************************
01142 
01143 void CMoveContainer::clearOT ()
01144 {
01145         // Check
01146         nlassert (_OtSize==_TimeOT.size());
01147 
01148         // clear the list
01149         uint i;
01150         for (i=0; i<_OtSize; i++)
01151                 _TimeOT[i].clear ();
01152 
01153         // Relink the list
01154         for (i=0; i<_OtSize-1; i++)
01155                 // Link the two cells
01156                 _TimeOT[i].link (&(_TimeOT[i+1]));
01157 }
01158 
01159 // ***************************************************************************
01160 
01161 void CMoveContainer::removeModifiedFromOT (uint8 worldImage)
01162 {
01163         // For each changed primitives
01164         CMovePrimitive *changed=_ChangedRoot[worldImage];
01165         while (changed)
01166         {
01167                 // Remove from ot list
01168                 changed->removeCollisionOTInfo ();
01169 
01170                 // Get the primitive world image
01171                 CPrimitiveWorldImage *wI;
01172                 if (changed->isNonCollisionable())
01173                         wI=changed->getWorldImage (0);
01174                 else
01175                         wI=changed->getWorldImage (worldImage);
01176                 
01177                 // Next primitive
01178                 changed=wI->getNextModified ();
01179         }
01180 }
01181 
01182 // ***************************************************************************
01183 
01184 CCollisionOTDynamicInfo *CMoveContainer::allocateOTDynamicInfo ()
01185 {
01186         return _AllocOTDynamicInfo.allocate ();
01187 }
01188 
01189 // ***************************************************************************
01190 
01191 CCollisionOTStaticInfo *CMoveContainer::allocateOTStaticInfo ()
01192 {
01193         return _AllocOTStaticInfo.allocate ();
01194 }
01195 
01196 // ***************************************************************************
01197 
01198 // Free all ordered table info
01199 void CMoveContainer::freeAllOTInfo ()
01200 {
01201         _AllocOTDynamicInfo.free ();
01202         _AllocOTStaticInfo.free ();
01203 }
01204 
01205 // ***************************************************************************
01206 
01207 CMovePrimitive *CMoveContainer::allocatePrimitive (uint8 firstWorldImage, uint8 numWorldImage)
01208 {
01209         // Simply allocate
01210         return new CMovePrimitive (this, firstWorldImage, numWorldImage);
01211 }
01212 
01213 // ***************************************************************************
01214 
01215 void CMoveContainer::freePrimitive (CMovePrimitive *primitive)
01216 {
01217         // Simply deallocate
01218         delete primitive;
01219 }
01220 
01221 // ***************************************************************************
01222 
01223 CPrimitiveWorldImage    **CMoveContainer::allocateWorldImagesPtrs (uint numPtrs)
01224 {
01225         return new CPrimitiveWorldImage*[numPtrs];
01226 }
01227 
01228 // ***************************************************************************
01229 
01230 void CMoveContainer::freeWorldImagesPtrs (CPrimitiveWorldImage **ptrs)
01231 {
01232                 delete [] ptrs;
01233 }
01234 
01235 // ***************************************************************************
01236 
01237 CPrimitiveWorldImage    *CMoveContainer::allocateWorldImage ()
01238 {
01239         return new CPrimitiveWorldImage;
01240 }
01241 
01242 // ***************************************************************************
01243 
01244 void CMoveContainer::freeWorldImage (CPrimitiveWorldImage *worldImage)
01245 {
01246         delete worldImage;
01247 }
01248 
01249 // ***************************************************************************
01250 
01251 CMoveElement *CMoveContainer::allocateMoveElement ()
01252 {
01253         // Simply allocate
01254         return new CMoveElement;
01255 }
01256 
01257 // ***************************************************************************
01258 
01259 void CMoveContainer::freeMoveElement (CMoveElement *element)
01260 {
01261         // Simply deallocate
01262         delete element;
01263 }
01264 
01265 // ***************************************************************************
01266 
01267 void    UMoveContainer::deleteMoveContainer (UMoveContainer     *container)
01268 {
01269         delete (CMoveContainer*)container;
01270 }
01271 
01272 // ***************************************************************************
01273 
01274 UMovePrimitive *CMoveContainer::addCollisionablePrimitive (uint8 firstWorldImage, uint8 numWorldImage, const UMovePrimitive *copyFrom)
01275 {
01276         NL_ALLOC_CONTEXT( Pacs )
01277 
01278         // Allocate primitive
01279         CMovePrimitive *primitive=allocatePrimitive (firstWorldImage, numWorldImage);
01280 
01281         // Add into the set
01282         _PrimitiveSet.insert (primitive);
01283 
01284         // if copy from primitive is not null, copy attributes
01285         if (copyFrom != NULL)
01286         {
01287                 primitive->setPrimitiveType(copyFrom->getPrimitiveType());
01288                 primitive->setReactionType(copyFrom->getReactionType());
01289                 primitive->setTriggerType(copyFrom->getTriggerType());
01290                 primitive->setCollisionMask(copyFrom->getCollisionMask());
01291                 primitive->setOcclusionMask(copyFrom->getOcclusionMask());
01292                 primitive->setObstacle(copyFrom->getObstacle());
01293                 primitive->setAbsorbtion(copyFrom->getAbsorbtion());
01294                 primitive->setHeight(copyFrom->getHeight());
01295                 if (primitive->getPrimitiveType() == UMovePrimitive::_2DOrientedBox)
01296                 {
01297                         float   width=0.0f, height=0.0f;
01298                         copyFrom->getSize(width, height);
01299                         primitive->setSize(width, height);
01300                 }
01301                 else
01302                 {
01303                         primitive->setRadius(copyFrom->getRadius());
01304                 }
01305         }
01306 
01307         // Return it
01308         return primitive;
01309 }
01310 
01311 // ***************************************************************************
01312 
01313 UMovePrimitive *CMoveContainer::addNonCollisionablePrimitive (const UMovePrimitive *copyFrom)
01314 {
01315         NL_ALLOC_CONTEXT( Pacs )
01316 
01317         // Allocate primitive
01318         CMovePrimitive *primitive=allocatePrimitive (0, 1);
01319         
01320         // Set as noncollisionable
01321         primitive->setNonCollisionable (true);
01322         
01323         // Add into the set
01324         _PrimitiveSet.insert (primitive);
01325 
01326         // if copy from primitive is not null, copy attributes
01327         if (copyFrom != NULL)
01328         {
01329                 primitive->setPrimitiveType(copyFrom->getPrimitiveType());
01330                 primitive->setReactionType(copyFrom->getReactionType());
01331                 primitive->setTriggerType(copyFrom->getTriggerType());
01332                 primitive->setCollisionMask(copyFrom->getCollisionMask());
01333                 primitive->setOcclusionMask(copyFrom->getOcclusionMask());
01334                 primitive->setObstacle(copyFrom->getObstacle());
01335                 primitive->setAbsorbtion(copyFrom->getAbsorbtion());
01336                 primitive->setHeight(copyFrom->getHeight());
01337                 if (primitive->getPrimitiveType() == UMovePrimitive::_2DOrientedBox)
01338                 {
01339                         float   width=0.0f, height=0.0f;
01340                         copyFrom->getSize(width, height);
01341                         primitive->setSize(width, height);
01342                 }
01343                 else
01344                 {
01345                         primitive->setRadius(copyFrom->getRadius());
01346                 }
01347         }
01348 
01349         // Return it
01350         return primitive;
01351 }
01352 
01353 // ***************************************************************************
01354 
01355 void CMoveContainer::removePrimitive (UMovePrimitive* primitive)
01356 {
01357         NL_ALLOC_CONTEXT( Pacs )
01358 
01359         // CMovePrimitive pointer
01360         CMovePrimitive *prim=(CMovePrimitive*)primitive;
01361 
01362         // Get the primitive world image
01363         for (uint8 i=0; i<prim->getNumWorldImage (); i++)
01364         {
01365                 // World image
01366                 uint8 worldImage=prim->getFirstWorldImage ()+i;
01367 
01368                 // Get primitive world image
01369                 CPrimitiveWorldImage *wI=prim->getWorldImage (worldImage);
01370 
01371                 // In modified list ?
01372                 if (wI->isInModifiedListFlag ())
01373                 {
01374                         // Non collisionable primitive ?
01375                         if (prim->isNonCollisionable())
01376                         {
01377                                 // Remove from all world image
01378                                 removeNCFromModifiedList (prim, worldImage);
01379                         }
01380                         else
01381                         {
01382                                 // Remove from modified list
01383                                 removeFromModifiedList (prim, worldImage);
01384                         }
01385                 }
01386         }
01387 
01388         // Remove from the set
01389         _PrimitiveSet.erase (prim);
01390 
01391         // Erase it
01392         freePrimitive (prim);
01393 }
01394 
01395 // ***************************************************************************
01396 
01397 void CMoveContainer::removeNCFromModifiedList (CMovePrimitive* primitive, uint8 worldImage)
01398 {
01399         // For each world image
01400         uint i;
01401         uint worldImageCount = _ChangedRoot.size();
01402         for (i=0; i<worldImageCount; i++)
01403         {
01404                 // For each changed primitives
01405                 CMovePrimitive *changed=_ChangedRoot[i];
01406                 CPrimitiveWorldImage *previous=NULL;
01407                 CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
01408 
01409                 while (changed)
01410                 {
01411                         // Get the primitive world image
01412                         CPrimitiveWorldImage *changedWI=changed->getWorldImage (worldImage);
01413 
01414                         // Remove from ot list
01415                         if (changed==primitive)
01416                         {
01417                                 // There is a previous primitive ?
01418                                 if (previous)
01419                                         previous->linkInModifiedList (wI->getNextModified ());
01420                                 else
01421                                         _ChangedRoot[i]=wI->getNextModified ();
01422 
01423                                 // Unlink
01424                                 wI->linkInModifiedList (NULL);
01425                                 wI->setInModifiedListFlag (false);
01426                                 break;
01427                         }
01428                         
01429                         // Next primitive
01430                         previous=changedWI;
01431                         changed=changedWI->getNextModified ();
01432                 }
01433 
01434                 // Breaked ?
01435                 if (changed==primitive)
01436                         break;
01437         }
01438 }
01439 
01440 // ***************************************************************************
01441  
01442 void CMoveContainer::removeFromModifiedList (CMovePrimitive* primitive, uint8 worldImage)
01443 {
01444         // For each changed primitives
01445         CMovePrimitive *changed=_ChangedRoot[worldImage];
01446         CPrimitiveWorldImage *previous=NULL;
01447         CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
01448 
01449         while (changed)
01450         {
01451                 // Get the primitive world image
01452                 CPrimitiveWorldImage *changedWI=changed->getWorldImage (worldImage);
01453 
01454                 // Remove from ot list
01455                 if (changed==primitive)
01456                 {
01457                         // There is a previous primitive ?
01458                         if (previous)
01459                                 previous->linkInModifiedList (wI->getNextModified ());
01460                         else
01461                                 _ChangedRoot[worldImage]=wI->getNextModified ();
01462 
01463                         // Unlink
01464                         wI->linkInModifiedList (NULL);
01465                         wI->setInModifiedListFlag (false);
01466                         break;
01467                 }
01468                 
01469                 // Next primitive
01470                 previous=changedWI;
01471                 changed=changedWI->getNextModified ();
01472         }
01473 }
01474 
01475 // ***************************************************************************
01476  
01477 void CMoveContainer::unlinkMoveElement  (CMoveElement *element, uint8 worldImage)
01478 {
01479         // Some checks
01480         nlassert (element->X<_CellCountWidth);
01481         nlassert (element->Y<_CellCountHeight);
01482 
01483         // Unlink it
01484         CMoveCell &cell=_VectorCell[worldImage][element->X+element->Y*_CellCountWidth];
01485         cell.unlinkX (element);
01486         //cell.unlinkY (element);
01487 }
01488 
01489 // ***************************************************************************
01490 
01491 void CMoveContainer::reaction (const CCollisionOTInfo& first)
01492 {
01493 //      H_AUTO(PACS_MC_reaction);
01494 
01495         // Static collision ?
01496         if (first.isCollisionAgainstStatic())
01497         {
01498                 // Check mode
01499                 nlassert (_Retriever);
01500 
01501                 // Cast
01502                 const CCollisionOTStaticInfo *staticInfo=safe_cast<const CCollisionOTStaticInfo*> (&first);
01503 
01504                 // Get the primitive world image
01505                 CMovePrimitive *movePrimitive=staticInfo->getPrimitive ();
01506                 CPrimitiveWorldImage *wI;
01507                 if (movePrimitive->isNonCollisionable ())
01508                         wI=movePrimitive->getWorldImage (0);
01509                 else
01510                         wI=movePrimitive->getWorldImage (staticInfo->getWorldImage());
01511 
01512                 // Dynamic collision
01513                 wI->reaction ( staticInfo->getCollisionDesc (), staticInfo->getGlobalPosition (),
01514                                                 *_Retriever, staticInfo->getDeltaTime(), _DeltaTime, *staticInfo->getPrimitive (), *this, staticInfo->getWorldImage());
01515         }
01516         else
01517         {
01518                 // Cast
01519                 const CCollisionOTDynamicInfo *dynInfo=safe_cast<const CCollisionOTDynamicInfo*> (&first);
01520 
01521                 // Get the primitives world image
01522                 CPrimitiveWorldImage *firstWI;
01523                 if (dynInfo->getFirstPrimitive ()->isNonCollisionable ())
01524                         firstWI=dynInfo->getFirstPrimitive ()->getWorldImage (0);
01525                 else
01526                         firstWI=dynInfo->getFirstPrimitive ()->getWorldImage (dynInfo->getFirstWorldImage());
01527 
01528                 CPrimitiveWorldImage *secondWI;
01529                 if (dynInfo->getSecondPrimitive ()->isNonCollisionable ())
01530                         secondWI=dynInfo->getSecondPrimitive ()->getWorldImage (0);
01531                 else
01532                         secondWI=dynInfo->getSecondPrimitive ()->getWorldImage (dynInfo->getSecondWorldImage());
01533 
01534                 // Dynamic collision
01535                 firstWI->reaction ( *secondWI, dynInfo->getCollisionDesc (), _Retriever, _SurfaceTemp, dynInfo->isCollision(), 
01536                                                         *dynInfo->getFirstPrimitive (), *dynInfo->getSecondPrimitive (), this, dynInfo->getFirstWorldImage(),
01537                                                         dynInfo->getSecondWorldImage(), dynInfo->isSecondStatic());
01538 
01547                 if (dynInfo->getFirstPrimitive ()->isCollisionable ())
01548                 {
01549                         if (dynInfo->getFirstPrimitive ()->isTriggered (*dynInfo->getSecondPrimitive (), dynInfo->isEnter(), dynInfo->isExit()))
01550                                 newTrigger (dynInfo->getFirstPrimitive (), dynInfo->getSecondPrimitive (), dynInfo->getCollisionDesc (),
01551                                                         dynInfo->isEnter() ? UTriggerInfo::In : dynInfo->isExit() ? UTriggerInfo::Out : UTriggerInfo::Inside);
01552                 }
01553         }
01554 }
01555 
01556 // ***************************************************************************
01557 
01558 void CMoveContainer::setAsStatic (uint8 worldImage)
01559 {
01560         NL_ALLOC_CONTEXT( Pacs )
01561 
01562         // Add this world image in the static set of world image
01563         _StaticWorldImage.insert (worldImage);
01564 }
01565 
01566 // ***************************************************************************
01567 
01568 void CMoveContainer::duplicateWorldImage (uint8 source, uint8 dest)
01569 {
01570         NL_ALLOC_CONTEXT( Pacs )
01571 
01572         // Cell count
01573         uint cellCount=_CellCountWidth*_CellCountHeight;
01574 
01575         // Clear dest modified list
01576         clearModifiedList (dest);
01577 
01578         // Clear destination cells
01579         uint i;
01580         for (i=0; i<cellCount; i++)
01581         {
01582                 // Get first X
01583                 CMoveElement *elm;
01584                 while ((elm=_VectorCell[dest][i].getFirstX ()))
01585                 {
01586                         // Get primitive world image
01587                         CPrimitiveWorldImage *wI=elm->Primitive->getWorldImage (dest);
01588 
01589                         // Remove the primitive
01590                         int i;
01591                         for (i=0; i<4; i++)
01592                         {
01593                                 if (wI->getMoveElement(i))
01594                                         wI->removeMoveElement (i, *this, dest);
01595                         }
01596                 }
01597         }
01598 
01599         // Duplicate destination cells
01600         for (i=0; i<cellCount; i++)
01601         {
01602                 // Get first X
01603                 CMoveElement *elm=_VectorCell[source][i].getFirstX ();
01604                 while (elm)
01605                 {
01606                         // Get primitive world image
01607                         CPrimitiveWorldImage *wISource=elm->Primitive->getWorldImage (source);
01608                         CPrimitiveWorldImage *wIDest=elm->Primitive->getWorldImage (dest);
01609 
01610                         // First time the primitive is visited ?
01611                         if (wIDest->getMoveElement (0)==NULL)
01612                         {
01613                                 wIDest->copy (*wISource);
01614                         }
01615                 
01616                         // Add at the end of the list
01617                         wIDest->addMoveElementendOfList (_VectorCell[dest][i], elm->X, elm->Y, elm->Primitive, *this);
01618 
01619                         // Added ?
01620                         nlassert (wIDest->getMoveElement (0)!=NULL);
01621 
01622                         // Next primitive
01623                         elm=elm->NextX;
01624                 }
01625         }
01626 }
01627 
01628 // ***************************************************************************
01629 
01630 UMoveContainer *UMoveContainer::createMoveContainer (double xmin, double ymin, double xmax, double ymax, 
01631                 uint widthCellCount, uint heightCellCount, double primitiveMaxSize, uint8 numWorldImage, 
01632                 uint maxIteration, uint otSize)
01633 {
01634         NL_ALLOC_CONTEXT( Pacs )
01635 
01636         // Create a CMoveContainer
01637         return new CMoveContainer (xmin, ymin, xmax, ymax, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
01638 }
01639 
01640 // ***************************************************************************
01641 
01642 UMoveContainer *UMoveContainer::createMoveContainer (UGlobalRetriever* retriever, uint widthCellCount, 
01643         uint heightCellCount, double primitiveMaxSize, uint8 numWorldImage, uint maxIteration, uint otSize)
01644 {
01645         NL_ALLOC_CONTEXT( Pacs )
01646 
01647         // Cast
01648         nlassert (dynamic_cast<CGlobalRetriever*>(retriever));
01649         CGlobalRetriever* r=static_cast<CGlobalRetriever*>(retriever);
01650 
01651         // Create a CMoveContainer
01652         return new CMoveContainer (r, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
01653 }
01654 
01655 // ***************************************************************************
01656 
01657 void UCollisionDesc::serial (NLMISC::IStream& stream)
01658 {
01659         stream.serial (ContactPosition);
01660         stream.serial (ContactNormal0);
01661         stream.serial (ContactNormal1);
01662         stream.serial (ContactTime);
01663 };
01664 
01665 // ***************************************************************************
01666 
01667 void UTriggerInfo::serial (NLMISC::IStream& stream)
01668 {
01669         stream.serial (Object0);
01670         stream.serial (Object1);
01671         stream.serial (CollisionDesc);
01672 }
01673 
01674 
01675 
01676 // ***************************************************************************
01677 void CMoveContainer::addCollisionnablePrimitiveBlock(UPrimitiveBlock *pb,uint8 firstWorldImage,uint8 numWorldImage,std::vector<UMovePrimitive*> *primitives,float orientation,const NLMISC::CVector &position, bool dontSnapToGround /* = false*/)
01678 {
01679         NL_ALLOC_CONTEXT( Pacs )
01680 
01681         CPrimitiveBlock *block = NLMISC::safe_cast<CPrimitiveBlock *>(pb);
01682         // Reserve the pointer array
01683         if (primitives)
01684                 primitives->reserve (block->Primitives.size());
01685 
01686         // For each primitive
01687         uint prim;
01688         for (prim=0; prim<block->Primitives.size(); prim++)
01689         {
01690                 // Create a collisionable primitive
01691                 UMovePrimitive *primitive = addCollisionablePrimitive (firstWorldImage, numWorldImage);
01692                 
01693                 // Ref on the block descriptor
01694                 CPrimitiveDesc &desc = block->Primitives[prim];
01695 
01696                 // Set its properties
01697                 primitive->setPrimitiveType (desc.Type);
01698                 primitive->setReactionType (desc.Reaction);
01699                 primitive->setTriggerType (desc.Trigger);
01700                 primitive->setCollisionMask (desc.CollisionMask);
01701                 primitive->setOcclusionMask (desc.OcclusionMask);
01702                 primitive->setObstacle (desc.Obstacle);
01703                 primitive->setAbsorbtion (desc.Attenuation);
01704                 primitive->setDontSnapToGround(dontSnapToGround);
01705                 if (desc.Type == UMovePrimitive::_2DOrientedBox)
01706                 {
01707                         primitive->setSize (desc.Length[0], desc.Length[1]);
01708                 }
01709                 else
01710                 {
01711                         nlassert (desc.Type == UMovePrimitive::_2DOrientedCylinder);
01712                         primitive->setRadius (desc.Length[0]);
01713                 }
01714                 primitive->setHeight (desc.Height);
01715 
01716                 // Insert the primitives
01717 
01718                 // For each world image
01719                 uint wI;
01720                 for (wI=firstWorldImage; wI<(uint)(firstWorldImage+numWorldImage); wI++)
01721                 {
01722                         // Insert the primitive
01723                         primitive->insertInWorldImage (wI);
01724 
01725                         // Final position
01726                         float cosa = (float) cos (orientation);
01727                         float sina = (float) sin (orientation);
01728                         CVector finalPos;
01729                         finalPos.x = cosa * desc.Position.x - sina * desc.Position.y + position.x;
01730                         finalPos.y = sina * desc.Position.y + cosa * desc.Position.y + position.y;
01731                         finalPos.z = desc.Position.z + position.z;
01732 
01733                         // Set the primtive orientation
01734                         if (desc.Type == UMovePrimitive::_2DOrientedBox)
01735                                 primitive->setOrientation ((float)fmod (desc.Orientation + orientation, 2*Pi), wI);
01736 
01737                         // Set the primitive global position
01738                         primitive->setGlobalPosition (finalPos, wI);
01739                 }
01740 
01741                 // Feedback asked ?
01742                 if (primitives)
01743                 {
01744                         // Add the pointer
01745                         primitives->push_back (primitive);
01746                 }
01747         }                       
01748 }
01749 
01750 
01751 // ***************************************************************************
01752 
01753 bool CMoveContainer::loadCollisionablePrimitiveBlock (const char *filename, uint8 firstWorldImage, uint8 numWorldImage, std::vector<UMovePrimitive*> *primitives, float orientation, const NLMISC::CVector &position, bool dontSnapToGround /*= false*/)
01754 {
01755         NL_ALLOC_CONTEXT( Pacs )
01756 
01757         // Check world image
01758         if ( (uint)(firstWorldImage+numWorldImage) > _ChangedRoot.size() )
01759         {
01760                 nlwarning ("Invalid world image number.");
01761                 return false;
01762         }
01763 
01764         // Try to load the file
01765         CIFile file;
01766         if (file.open (filename))
01767         {
01768                 // Create the XML stream
01769                 CIXml input;
01770 
01771                 // Init
01772                 if (input.init (file))
01773                 {
01774                         // The primitive block
01775                         CPrimitiveBlock block;
01776 
01777                         // Serial it
01778                         file.serial (block);
01779 
01780                         // add primitives
01781                         addCollisionnablePrimitiveBlock(&block, firstWorldImage, numWorldImage, primitives, orientation, position, dontSnapToGround);
01782                 
01783                         return true;
01784                 }
01785                 else
01786                 {
01787                         // Warning
01788                         nlwarning ("Can't init XML stream with file %s.", filename);
01789 
01790                         return false;
01791                 }
01792         }
01793         else
01794         {
01795                 // Warning
01796                 nlwarning ("Can't load primitive block %s.", filename);
01797 
01798                 return false;
01799         }
01800 }
01801 
01802 
01803 // ***************************************************************************
01804 void CMoveContainer::getPrimitives(std::vector<const UMovePrimitive *> &dest) const
01805 {       
01806         NL_ALLOC_CONTEXT( Pacs )
01807 
01808         dest.resize(_PrimitiveSet.size());
01809         std::copy(_PrimitiveSet.begin(), _PrimitiveSet.end(), dest.begin());
01810 }
01811 
01812 
01813 // ***************************************************************************
01814 void UMoveContainer::getPACSCoordsFromMatrix(NLMISC::CVector &pos,float &angle,const NLMISC::CMatrix &mat)
01815 {
01816         pos = mat.getPos();
01817         CVector orient = mat.mulVector(NLMISC::CVector::I);
01818         orient.z = 0.f;
01819         orient.normalize();
01820         angle = orient.y >= 0.f ? ::acosf(orient.x)  
01821                                                         : 2.f * (float) NLMISC::Pi - ::acosf(orient.x);
01822 
01823 }
01824 
01825 // ***************************************************************************
01826 bool CMoveContainer::evalNCPrimitiveCollision (double deltaTime, UMovePrimitive *primitive, uint8 worldImage)
01827 {
01828         NL_ALLOC_CONTEXT( Pacs )
01829 
01830         // New test time
01831         _TestTime++;
01832 
01833         // Clear triggers
01834         _Triggers.clear ();
01835 
01836         // Only non-collisionable primitives
01837         if (!primitive->isCollisionable())
01838         {
01839                 // Delta time
01840                 _DeltaTime=deltaTime;
01841 
01842                 // Begin of the time slice to compute
01843                 double beginTime = 0;
01844                 double collisionTime = deltaTime;
01845 
01846                 // Get the world image
01847                 CPrimitiveWorldImage *wI = ((CMovePrimitive*)primitive)->getWorldImage (0);
01848 
01849                 CCollisionOTInfo *firstCollision = NULL;
01850                 do
01851                 {
01852 
01853                         nlassert (beginTime < 1.0);
01854 
01855                         // Update the primitive
01856                         wI->update (beginTime, deltaTime, *(CMovePrimitive*)primitive);
01857 
01858                         CVectorD d0=wI->getDeltaPosition();
01859 
01860                         // Eval collision again the terrain
01861                         bool testMoveValid = false;
01862                         CCollisionOTStaticInfo staticColInfo;
01863                         CCollisionOTDynamicInfo dynamicColInfoWI0;
01864                         CCollisionOTDynamicInfo dynamicColInfoWI;
01865 
01866                         firstCollision = NULL;
01867 
01868                         // If collision found, note it is on the landscape
01869                         if (evalOneTerrainCollision (beginTime, (CMovePrimitive*)primitive, worldImage, false, testMoveValid, &staticColInfo, NULL))
01870                         {
01871                                 firstCollision = &staticColInfo;
01872                         }
01873 
01874                         // Eval collision again the static primitives
01875                         std::set<uint8>::iterator ite=_StaticWorldImage.begin();
01876                         while (ite!=_StaticWorldImage.end())
01877                         {
01878                                 // Eval in this world image
01879                                 if (evalOnePrimitiveCollision (beginTime, (CMovePrimitive*)primitive, *ite, worldImage, false, true, testMoveValid, &dynamicColInfoWI0, NULL))
01880                                 {
01881                                         // First collision..
01882                                         if (!firstCollision || (firstCollision->getCollisionTime () > dynamicColInfoWI0.getCollisionTime ()))
01883                                         {
01884                                                 firstCollision = &dynamicColInfoWI0;
01885                                         }
01886                                 }
01887 
01888                                 // Next world image
01889                                 ite++;
01890                         }
01891 
01892                         // Checks
01893                         CVectorD d1=wI->getDeltaPosition();
01894 
01895                         // Eval collision again the world image
01896                         if (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end())
01897                         {
01898                                 if (evalOnePrimitiveCollision (beginTime, (CMovePrimitive*)primitive, worldImage, worldImage, false, false, testMoveValid, &dynamicColInfoWI, NULL))
01899                                 {
01900                                         // First collision..
01901                                         if (!firstCollision || (firstCollision->getCollisionTime () > dynamicColInfoWI.getCollisionTime ()))
01902                                         {
01903                                                 firstCollision = &dynamicColInfoWI;
01904                                         }
01905                                 }
01906                         }
01907 
01908                         // Checks
01909                         CVectorD d2=wI->getDeltaPosition();
01910                         nlassert ((d0==d1)&&(d0==d2));
01911 
01912 //                      if (found)
01913 //                              nlstop;
01914                         
01915                         // Reaction
01916                         if (firstCollision)
01917                         {
01918                                 collisionTime = firstCollision->getCollisionTime ();
01919                                 reaction (*firstCollision);
01920                                 nlassert (collisionTime != 1);
01921                         }
01922                         else
01923                         {
01924                                 // Retriever mode ?
01925                                 if (_Retriever&&testMoveValid)
01926                                 {                                                               
01927                                         // Do move
01928                                         wI->doMove (*_Retriever, _SurfaceTemp, deltaTime, collisionTime, ((CMovePrimitive*)primitive)->getDontSnapToGround());
01929                                 }
01930                                 else
01931                                 {
01932                                         // Do move
01933                                         wI->doMove (_DeltaTime);
01934                                 }
01935                         }
01936                         
01937                         beginTime = collisionTime;
01938                 }
01939                 while (firstCollision);
01940         }
01941         else
01942                 return false;
01943 
01944         return true;
01945 }
01946 
01947 
01948 } // NLPACS