nel/src/pacs/move_container.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010-2019  Winch Gate Property Limited
   3 //
   4 // This source file has been modified by the following contributors:
   5 // Copyright (C) 2020  Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
   6 //
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as
   9 // published by the Free Software Foundation, either version 3 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19
  20 #include "stdpacs.h"
  21
  22 #include "nel/pacs/move_primitive.h"
  23 #include "nel/pacs/move_element.h"
  24 #include "nel/pacs/primitive_block.h"
  25
  26 #include "nel/misc/hierarchical_timer.h"
  27
  28 #include "nel/misc/i_xml.h"
  29
  30 using namespace NLMISC;
  31
  32 #define NELPACS_ALLOC_DYNAMIC_INFO 100
  33 #define NELPACS_ALLOC_STATIC_INFO 100
  34
  35 H_AUTO_DECL ( NLPACS_Eval_Collision )
  36 #define NLPACS_HAUTO_EVAL_COLLISION     H_AUTO_USE ( NLPACS_Eval_Collision )
  37
  38 /****************************************************************************
  39
  40 Doc:
  41
  42           // Non collisionnable primitive
  43         Their moves are evaluate one by one with evalNCPrimitiveCollision().
  44         If a collision is found, reaction() is called.
  45
  46         // Collisionnable primitives
  47         Each primitive must be moved first with the move() method.
  48         Their moves are evaluate all at once. All the collisions found are time sorted in a time orderin table (_TimeOT).
  49         While the table is not empty, the first collision occurred in time is solved and
  50         If a collision is found, reaction() is called.
  51
  52
  53 ****************************************************************************/
  54
  55 namespace NLPACS
  56 {
  57
  58 // ***************************************************************************
  59
  60 CMoveContainer::~CMoveContainer ()
  61 {
  62         clear ();
  63 }
  64
  65 // ***************************************************************************
  66
  67 void CMoveContainer::clear ()
  68 {
  69         // Clear all primitives
  70         std::set<CMovePrimitive*>::iterator ite=_PrimitiveSet.begin();
  71         while (ite!=_PrimitiveSet.end ())
  72         {
  73                 freePrimitive (*ite);
  74                 ite++;
  75         }
  76
  77         // Clear primitive set
  78         _PrimitiveSet.clear ();
  79
  80         // Clear root changed
  81         _ChangedRoot.clear ();
  82
  83         // Clear static world image set
  84         _StaticWorldImage.clear ();
  85
  86         // Clear cell array
  87         _VectorCell.clear ();
  88
  89         // Clear time ot
  90         _TimeOT.clear ();
  91 }
  92
  93 // ***************************************************************************
  94
  95 void CMoveContainer::init (double xmin, double ymin, double xmax, double ymax, uint widthCellCount, uint heightCellCount,
  96                                                    double primitiveMaxSize, uint8 numWorldImage, uint maxIteration, uint otSize)
  97 {
  98         // Clear arrays
  99         clear ();
 100
 101         // Create world images
 102         _ChangedRoot.resize (numWorldImage);
 103         for (uint i=0; i<numWorldImage; i++)
 104                 _ChangedRoot[i]=NULL;
 105
 106         // Not in test mode
 107         _Retriever=NULL;
 108
 109         // Element size
 110         _PrimitiveMaxSize=primitiveMaxSize;
 111
 112         // BB
 113         _Xmin=xmin;
 114         _Ymin=ymin;
 115         _Xmax=xmax;
 116         _Ymax=ymax;
 117
 118         // Cells count
 119         _CellCountWidth=widthCellCount;
 120         _CellCountHeight=heightCellCount;
 121
 122         // Cells size
 123         _CellWidth=(_Xmax - _Xmin)/(double)_CellCountWidth;
 124         _CellHeight=(_Ymax - _Ymin)/(double)_CellCountHeight;
 125
 126         // Cell array
 127         _VectorCell.resize (numWorldImage);
 128         for (uint j=0; j<numWorldImage; j++)
 129                 _VectorCell[j].resize (_CellCountWidth * _CellCountHeight);
 130
 131         // resize OT
 132         _OtSize=otSize;
 133         _TimeOT.resize (otSize);
 134
 135         // Clear the OT
 136         clearOT ();
 137
 138         // Clear test time
 139         _TestTime=0xffffffff;
 140         _MaxTestIteration=maxIteration;
 141
 142         // Resize trigger array
 143         _Triggers.resize (NELPACS_CONTAINER_TRIGGER_DEFAULT_SIZE);
 144 }
 145
 146 // ***************************************************************************
 147
 148 void CMoveContainer::init (CGlobalRetriever* retriever, uint widthCellCount, uint heightCellCount, double primitiveMaxSize,
 149                 uint8 numWorldImage, uint maxIteration, uint otSize)
 150 {
 151         // Get min max of the global retriever BB
 152         CVector min=retriever->getBBox().getMin();
 153         CVector max=retriever->getBBox().getMax();
 154
 155         // Setup min max
 156         double xmin=min.x;
 157         double ymin=min.y;
 158         double xmax=max.x;
 159         double ymax=max.y;
 160
 161         // Init
 162         init (xmin, ymin, xmax, ymax, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
 163
 164         // Init the retriever
 165         _Retriever=retriever;
 166 }
 167
 168 // ***************************************************************************
 169
 170 void  CMoveContainer::evalCollision (double deltaTime, uint8 worldImage)
 171 {
 172         NLPACS_HAUTO_EVAL_COLLISION
 173
 174 //      H_AUTO(PACS_MC_evalCollision);
 175
 176         // New test time
 177         _TestTime++;
 178
 179         // Delta time
 180         _DeltaTime=deltaTime;
 181
 182         // Clear triggers
 183         _Triggers.clear ();
 184
 185         // Update the bounding box and position of modified primitives
 186         updatePrimitives (0.f, worldImage);
 187
 188 #ifdef NL_DEBUG
 189         // Check list integrity
 190         //checkSortedList ();
 191 #endif // NL_DEBUG
 192
 193         // Get first collision
 194         _PreviousCollisionNode = &_TimeOT[0];
 195         if(_PreviousCollisionNode == NULL)
 196                 return;
 197
 198         // Eval all collisions
 199         evalAllCollisions (0.f, worldImage);
 200
 201         // Clear modified list
 202         clearModifiedList (worldImage);
 203
 204         // Modified list is empty at this point
 205         nlassert (_ChangedRoot[worldImage]==NULL);
 206
 207         // Previous node is a 'hard' OT node
 208         nlassert (!_PreviousCollisionNode->isInfo());
 209
 210         // Get next collision
 211         CCollisionOTInfo        *nextCollision;
 212         {
 213                 H_AUTO (NLPACS_Get_Next_Info);
 214                 nextCollision=_PreviousCollisionNode->getNextInfo ();
 215         }
 216
 217         // Collision ?
 218         while (nextCollision)
 219         {
 220                 // Get new previous OT hard node
 221                 _PreviousCollisionNode=nextCollision->getPrevious ();
 222
 223                 // Previous node is a 'hard' OT node
 224                 nlassert (!_PreviousCollisionNode->isInfo());
 225
 226                 // Keep this collision
 227                 reaction (*nextCollision);
 228
 229                 // Remove this collision from ot
 230                 if (!nextCollision->isCollisionAgainstStatic ())
 231                 {
 232                         // Remove the primitive from OT
 233                         nextCollision->unlink();
 234
 235                         CCollisionOTDynamicInfo *info = static_cast<CCollisionOTDynamicInfo*>(nextCollision);
 236                         if (info->getFirstPrimitive())
 237                                 info->getFirstPrimitive()->removeCollisionOTInfo(info);
 238                         if (info->getSecondPrimitive())
 239                                 info->getSecondPrimitive()->removeCollisionOTInfo(info);
 240                 }
 241
 242                 // Last time
 243                 double newTime=nextCollision->getCollisionTime ();
 244
 245                 // Remove modified objects from the OT
 246                 removeModifiedFromOT (worldImage);
 247
 248                 // Must have been removed
 249                 nlassert (nextCollision->getPrevious ()==NULL);
 250                 nlassert (nextCollision->CCollisionOT::getNext ()==NULL);
 251
 252                 // Update the bounding box and position of modified primitives
 253                 updatePrimitives (newTime, worldImage);
 254
 255                 // Eval all collisions of modified objects for the new delta t
 256                 evalAllCollisions (newTime, worldImage);
 257
 258                 // Clear modified list
 259                 clearModifiedList (worldImage);
 260
 261                 // Get next collision
 262                 nextCollision=_PreviousCollisionNode->getNextInfo ();
 263         }
 264
 265 #ifdef NL_DEBUG
 266         // OT must be cleared
 267         checkOT ();
 268 #endif // NL_DEBUG
 269
 270         // Free ordered table info
 271         freeAllOTInfo ();
 272
 273         // Some init
 274         _PreviousCollisionNode=NULL;
 275 }
 276
 277 // ***************************************************************************
 278
 279 bool CMoveContainer::testMove (UMovePrimitive* primitive, const CVectorD& speed, double deltaTime, uint8 worldImage, CVectorD *contactNormal)
 280 {
 281
 282 //      H_AUTO(PACS_MC_testMove);
 283
 284         if (contactNormal)
 285                 *contactNormal = CVectorD::Null;
 286
 287         // Cast
 288         nlassert (dynamic_cast<CMovePrimitive*>(primitive));
 289         CMovePrimitive* prim=static_cast<CMovePrimitive*>(primitive);
 290
 291         // New test time
 292         _TestTime++;
 293
 294         // Delta time
 295         _DeltaTime=deltaTime;
 296
 297         // Get the world image primitive
 298         uint8 primitiveWorldImage;
 299         CPrimitiveWorldImage *wI;
 300         if (prim->isNonCollisionable ())
 301         {
 302                 wI=prim->getWorldImage (0);
 303                 primitiveWorldImage=worldImage;
 304         }
 305         else
 306         {
 307                 wI=prim->getWorldImage (worldImage);
 308                 primitiveWorldImage=worldImage;
 309         }
 310
 311         // Backup speed
 312         CVectorD oldSpeed=wI->getSpeed ();
 313
 314         // Set speed
 315         wI->move (speed, *this, *prim, primitiveWorldImage);
 316
 317         // Update the bounding box and position of the primitive
 318         wI->update (0, _DeltaTime, *prim);
 319
 320         // Compute cells overlaped by the primitive
 321         if (!prim->isNonCollisionable ())
 322                 updateCells (prim, worldImage);
 323
 324 #ifdef NL_DEBUG
 325         // Check list integrity
 326 //      checkSortedList ();
 327 #endif // NL_DEBUG
 328
 329         // Result
 330         bool result=false;
 331         bool testMoveValid;
 332
 333         // Eval first each static world images
 334         result=evalOneTerrainCollision (0, prim, primitiveWorldImage, true, testMoveValid, NULL, contactNormal);
 335
 336         // Eval first each static world images
 337         if (!result)
 338         {
 339                 std::set<uint8>::iterator ite=_StaticWorldImage.begin();
 340                 while (ite!=_StaticWorldImage.end())
 341                 {
 342
 343                         // Eval in this world image
 344                         result=evalOnePrimitiveCollision (0, prim, *ite, primitiveWorldImage, true, true, testMoveValid, NULL, contactNormal);
 345
 346                         // If found, abort
 347                         if (result)
 348                                 break;
 349
 350                         // Next world image
 351                         ite++;
 352                 }
 353         }
 354
 355         // Eval collisions if not found and not tested
 356         if ((!result) && (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end()))
 357                 result=evalOnePrimitiveCollision (0, prim, worldImage, primitiveWorldImage, true, false, testMoveValid, NULL, contactNormal);
 358
 359         // Backup speed only if the primitive is inserted in the world image
 360         if (prim->isInserted (primitiveWorldImage))
 361                 wI->move (oldSpeed, *this, *prim, primitiveWorldImage);
 362
 363 #ifdef NL_DEBUG
 364         // OT must be cleared
 365         checkOT ();
 366 #endif // NL_DEBUG
 367
 368         // Free ordered table info
 369         freeAllOTInfo ();
 370
 371         // Some init
 372         _PreviousCollisionNode=NULL;
 373
 374         // Return result
 375         return !result;
 376 }
 377
 378 // ***************************************************************************
 379
 380 void CMoveContainer::updatePrimitives (double beginTime, uint8 worldImage)
 381 {
 382         H_AUTO (NLPACS_Update_Primitives);
 383
 384         // For each changed primitives
 385         CMovePrimitive *changed=_ChangedRoot[worldImage];
 386         while (changed)
 387         {
 388                 // Get the primitive world image
 389                 CPrimitiveWorldImage *wI;
 390                 if (changed->isNonCollisionable())
 391                         wI=changed->getWorldImage (0);
 392                 else
 393                         wI=changed->getWorldImage (worldImage);
 394
 395                 // Force the build of the bounding box
 396                 wI->update (beginTime, _DeltaTime, *changed);
 397
 398                 // Is inserted in this world image ?
 399                 if (changed->isInserted (worldImage))
 400                 {
 401
 402                         // Compute cells overlaped by the primitive
 403                         updateCells (changed, worldImage);
 404                 }
 405
 406                 // Next primitive
 407                 changed=wI->getNextModified ();
 408         }
 409 }
 410
 411 // ***************************************************************************
 412
 413 void CMoveContainer::updateCells (CMovePrimitive *primitive, uint8 worldImage)
 414 {
 415 //      H_AUTO(PACS_MC_updateCells);
 416
 417         // Get the primitive world image
 418         CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
 419
 420 #if !FINAL_VERSION
 421 /*      // Check BB width not too large
 422         if (wI->getBBXMax() - wI->getBBXMin() > _CellWidth)
 423         {
 424                 nlwarning ("Primitives have moved more than a cell, width: %f.", (float)(wI->getBBXMax() - wI->getBBXMin()));
 425         }
 426
 427         // Check BB height not too large
 428         if (wI->getBBYMax() - wI->getBBYMin() > _CellHeight)
 429         {
 430                 nlwarning ("Primitives have moved more than a cell, height: %f.", (float)(wI->getBBYMax() - wI->getBBYMin()));
 431         }
 432 */
 433 #endif
 434
 435         // Get coordinate in the cell array
 436         sint minx=(int)floor ((wI->getBBXMin() - _Xmin) / _CellWidth);
 437         sint miny=(int)floor ((wI->getBBYMin() - _Ymin) / _CellHeight);
 438         sint maxx=(int)floor ((wI->getBBXMax() - _Xmin) / _CellWidth);
 439         sint maxy=(int)floor ((wI->getBBYMax() - _Ymin) / _CellHeight);
 440
 441         // Born
 442         if (minx<0)
 443                 minx=0;
 444         if (miny<0)
 445                 miny=0;
 446         if (maxx>=(int)_CellCountWidth)
 447                 maxx=(int)_CellCountWidth-1;
 448         if (maxy>=(int)_CellCountHeight)
 449                 maxy=(int)_CellCountHeight-1;
 450
 451         maxx=std::min (minx+1, maxx);
 452         maxy=std::min (miny+1, maxy);
 453
 454         // flags founded
 455         bool found[4]={false, false, false, false};
 456
 457         // For each old cells
 458         uint i;
 459         for (i=0; i<4; i++)
 460         {
 461                 // Element
 462                 CMoveElement *elm = wI->getMoveElement (i);
 463
 464                 // Old element in this cell ?
 465                 if ( elm )
 466                 {
 467                         // Check
 468                         nlassert (elm->X<_CellCountWidth);
 469                         nlassert (elm->Y<_CellCountHeight);
 470
 471                         // Must remove it ?
 472                         if ( (elm->X < minx) || (elm->X > maxx) || (elm->Y < miny) || (elm->Y > maxy) )
 473                         {
 474                                 // Yes remove it
 475                                 wI->removeMoveElement (i, *this, worldImage);
 476                         }
 477                         else
 478                         {
 479                                 // Checks
 480                                 nlassert (((elm->X - minx)==0)||((elm->X - minx)==1));
 481                                 nlassert (((elm->Y - miny)==0)||((elm->Y - miny)==1));
 482
 483                                 // Update position
 484 #ifndef TEST_CELL
 485                                 _VectorCell[worldImage][elm->X+elm->Y*_CellCountWidth].updateSortedLists (elm, worldImage);
 486 #endif
 487
 488                                 // Check found cells
 489                                 found[ elm->X - minx + ((elm->Y - miny) << (maxx-minx)) ]=true;
 490                         }
 491                 }
 492         }
 493
 494         // For each case selected
 495         int x, y;
 496         i=0;
 497         for (y=miny; y<=(int)maxy; y++)
 498         for (x=minx; x<=(int)maxx; x++)
 499         {
 500                 // Check the formula
 501                 nlassert ((int)i == (x - minx + ((y - miny) << (maxx-minx)) ));
 502
 503                 // If the cell is not found
 504                 if (!found[i])
 505                 {
 506                         // Center of the cell
 507                         double cx=((double)x+0.5f)*_CellWidth+_Xmin;
 508                         double cy=((double)y+0.5f)*_CellHeight+_Ymin;
 509
 510                         // Add it in the list
 511                         wI->addMoveElement (_VectorCell[worldImage][x+y*_CellCountWidth], (uint16)x, (uint16)y, cx, cy, primitive, *this, worldImage);
 512                 }
 513
 514                 // Next cell
 515                 i++;
 516         }
 517 }
 518
 519 // ***************************************************************************
 520
 521 void CMoveContainer::getCells (CMovePrimitive *primitive, uint8 worldImage, uint8 primitiveWorldImage, CMoveElement **elementArray)
 522 {
 523 //      H_AUTO(PACS_MC_getCells);
 524
 525         // Get the primitive world image
 526         CPrimitiveWorldImage *wI;
 527         if (primitive->isNonCollisionable())
 528                 wI=primitive->getWorldImage (0);
 529         else
 530                 wI=primitive->getWorldImage (primitiveWorldImage);
 531
 532 #if !FINAL_VERSION
 533         // Check BB width not too large
 534         if (wI->getBBXMax() - wI->getBBXMin() > _CellWidth)
 535         {
 536                 //nlwarning ("Primitives have moved more than a cell.");
 537         }
 538
 539         // Check BB height not too large
 540         if (wI->getBBYMax() - wI->getBBYMin() > _CellHeight)
 541         {
 542                 //nlwarning ("Primitives have moved more than a cell.");
 543         }
 544 #endif
 545
 546         // Get coordinate in the cell array
 547         int minx=(int)floor ((wI->getBBXMin() - _Xmin) / _CellWidth);
 548         int miny=(int)floor ((wI->getBBYMin() - _Ymin) / _CellHeight);
 549         int maxx=(int)floor ((wI->getBBXMax() - _Xmin) / _CellWidth);
 550         int maxy=(int)floor ((wI->getBBYMax() - _Ymin) / _CellHeight);
 551
 552         // Born
 553         if (minx<0)
 554                 minx=0;
 555         if (miny<0)
 556                 miny=0;
 557         if (maxx>=(int)_CellCountWidth)
 558                 maxx=(int)_CellCountWidth-1;
 559         if (maxy>=(int)_CellCountHeight)
 560                 maxy=(int)_CellCountHeight-1;
 561
 562         maxx=std::min (minx+1, maxx);
 563         maxy=std::min (miny+1, maxy);
 564
 565         // For each case selected
 566         int x, y;
 567         int i=0;
 568         for (y=miny; y<=(int)maxy; y++)
 569         for (x=minx; x<=(int)maxx; x++)
 570         {
 571                 // Check the formula
 572                 nlassert ((int)i == (x - minx + ((y - miny) << (maxx-minx)) ));
 573
 574                 // Center of the cell
 575                 double cx=((double)x+0.5f)*_CellWidth+_Xmin;
 576
 577                 // Primitive center
 578                 double pcx=(wI->getBBXMin()+wI->getBBXMax())/2.f;
 579
 580                 elementArray[i]->Primitive=primitive;
 581                 elementArray[i]->X=uint16(x);
 582                 elementArray[i]->Y=uint16(y);
 583                 // Insert in left or right ?
 584                 if (pcx<cx)
 585                 {
 586                         // In the left
 587                         elementArray[i]->NextX=_VectorCell[worldImage][x+y*_CellCountWidth].getFirstX ();
 588                         elementArray[i]->PreviousX=NULL;
 589                 }
 590                 else
 591                 {
 592                         // In the right
 593                         elementArray[i]->PreviousX=_VectorCell[worldImage][x+y*_CellCountWidth].getLastX ();
 594                         elementArray[i]->NextX=NULL;
 595                 }
 596
 597                 // Next cell
 598                 i++;
 599         }
 600
 601         // Erase last array element
 602         for (; i<4; i++)
 603         {
 604                 elementArray[i]=NULL;
 605         }
 606 }
 607
 608 // ***************************************************************************
 609
 610 void CMoveContainer::clearModifiedList (uint8 worldImage)
 611 {
 612         H_AUTO (NLPACS_Clear_Modified_List);
 613
 614         // For each changed primitives
 615         CMovePrimitive *changed=_ChangedRoot[worldImage];
 616         while (changed)
 617         {
 618                 // Get the world image primitive
 619                 CPrimitiveWorldImage *wI;
 620                 if (changed->isNonCollisionable())
 621                         wI=changed->getWorldImage (0);
 622                 else
 623                         wI=changed->getWorldImage (worldImage);
 624
 625                 // Next primitive
 626                 changed=wI->getNextModified ();
 627
 628                 // Remove it from the list
 629                 wI->setInModifiedListFlag (false);
 630         }
 631
 632         // Empty list
 633         _ChangedRoot[worldImage]=NULL;
 634 }
 635
 636 // ***************************************************************************
 637
 638 void CMoveContainer::checkSortedList ()
 639 {
 640         // Check each primitives in the set
 641         std::set<CMovePrimitive*>::iterator ite=_PrimitiveSet.begin();
 642         while (ite!=_PrimitiveSet.end())
 643         {
 644                 // Check
 645                 (*ite)->checkSortedList ();
 646
 647                 ite++;
 648         }
 649 }
 650
 651 // ***************************************************************************
 652
 653 bool CMoveContainer::evalOneTerrainCollision (double beginTime, CMovePrimitive *primitive, uint8 primitiveWorldImage,
 654                                                                            bool testMove, bool &testMoveValid, CCollisionOTStaticInfo *staticColInfo, CVectorD *contactNormal)
 655 {
 656 //      H_AUTO(PACS_MC_evalOneCollision);
 657         H_AUTO(NLPACS_Eval_One_Terrain_Collision);
 658
 659         // Find its collisions
 660         bool found=false;
 661
 662         // Get the primitive world image
 663         CPrimitiveWorldImage *wI;
 664         if (primitive->isNonCollisionable())
 665                 wI=primitive->getWorldImage (0);
 666         else
 667                 wI=primitive->getWorldImage (primitiveWorldImage);
 668
 669         // Begin time must be the same as beginTime
 670         //nlassert (wI->getInitTime()==beginTime);
 671         if (wI->getInitTime() != beginTime)
 672         {
 673                 nlwarning("PACS: evalOneTerrainCollision() failure, wI->getInitTime() [%f] != beginTime [%f]", wI->getInitTime(), beginTime);
 674                 return false;
 675         }
 676
 677         // Test its static collision
 678         if (_Retriever)
 679         {
 680                 // Delta pos..
 681                 // Test retriever with the primitive
 682                 const TCollisionSurfaceDescVector *result=wI->evalCollision (*_Retriever, _SurfaceTemp, _TestTime, _MaxTestIteration, *primitive);
 683                 if (result)
 684                 {
 685                         // TEST MOVE MUST BE OK !!
 686                         testMoveValid=true;
 687
 688                         // Size of the array
 689                         uint size=(uint)result->size();
 690
 691                         // For each detected collisions
 692                         for (uint c=0; c<size; c++)
 693                         {
 694                                 // Ref on the collision
 695                                 CCollisionSurfaceDesc desc=(*result)[c];
 696                                 double contactTime = (_DeltaTime-beginTime)*desc.ContactTime+beginTime;
 697
 698                                 /*
 699                                  *  If beginTime is 0.999999999 and desc.ContactTime<1.0, contactTime will be 1.0.
 700                                  *  In this case, we force contactTime to be beginTime to avoid collision at time == 1.0.
 701                                 **/
 702                                 if ((contactTime >= 1.0) && (beginTime < 1.0) && (desc.ContactTime < 1.0))
 703                                         contactTime = beginTime;
 704
 705                                 // Set the container's time space contact time
 706                                 desc.ContactTime = contactTime;
 707
 708                                 // ptr on the surface
 709                                 const CRetrievableSurface *surf= _Retriever->getSurfaceById (desc.ContactSurface);
 710
 711                                 // TODO: check surface flags  against primitive flags HERE:
 712                                 // Is a wall ?
 713                                 bool isWall;
 714                                 if(!surf)
 715                                         isWall= true;
 716                                 else
 717                                         isWall= !(surf->isFloor() || surf->isCeiling());
 718
 719                                 // stop on a wall.
 720                                 if(isWall)
 721                                 {
 722                                         // Test move ?
 723                                         if (testMove)
 724                                         {
 725                                                 // return contact normal only when testmove and vector provided
 726                                                 if (contactNormal)
 727                                                         *contactNormal = desc.ContactNormal;
 728                                                 return true;
 729                                         }
 730                                         else
 731                                         {
 732                                                 // OK, collision if we are a collisionable primitive
 733                                                 newCollision (primitive, desc, primitiveWorldImage, beginTime, staticColInfo);
 734
 735                                                 // One collision found
 736                                                 found=true;
 737                                                 break;
 738                                         }
 739                                 }
 740                         }
 741                 }
 742                 else
 743                         // More than maxtest made, exit
 744                         return false;
 745         }
 746         return found;
 747 }
 748
 749 // ***************************************************************************
 750
 751 bool CMoveContainer::evalOnePrimitiveCollision (double beginTime, CMovePrimitive *primitive, uint8 worldImage, uint8 primitiveWorldImage,
 752                                                                            bool testMove, bool secondIsStatic, bool &/* testMoveValid */, CCollisionOTDynamicInfo *dynamicColInfo,
 753                                                                                 CVectorD *contactNormal)
 754 {
 755 //      H_AUTO(PACS_MC_evalOneCollision);
 756         H_AUTO(NLPACS_Eval_One_Primitive_Collision);
 757
 758         // Find its collisions
 759         bool found=false;
 760
 761         // Get the primitive world image
 762         CPrimitiveWorldImage *wI;
 763         if (primitive->isNonCollisionable())
 764                 wI=primitive->getWorldImage (0);
 765         else
 766                 wI=primitive->getWorldImage (primitiveWorldImage);
 767
 768         // Begin time must be the same as beginTime
 769         //nlassert (wI->getInitTime()==beginTime);
 770         if (wI->getInitTime() != beginTime)
 771         {
 772                 nlwarning("PACS: evalOnePrimitiveCollision() failure, wI->getInitTime() [%f] != beginTime [%f]", wI->getInitTime(), beginTime);
 773                 return false;
 774         }
 775
 776         // Element table
 777         CMoveElement    tableNotInserted[4];
 778         CMoveElement    *table[4];
 779
 780         // Single test ?
 781         bool singleTest=testMove;
 782
 783         // Is in world image
 784         if ((worldImage==primitiveWorldImage) && wI->isInWorldImageFlag())
 785         {
 786                 // Get move element table from the primitive
 787                 table[0]=wI->getMoveElement (0);
 788                 table[1]=wI->getMoveElement (1);
 789                 table[2]=wI->getMoveElement (2);
 790                 table[3]=wI->getMoveElement (3);
 791         }
 792         else
 793         {
 794                 // Set table pointers
 795                 table[0]=tableNotInserted+0;
 796                 table[1]=tableNotInserted+1;
 797                 table[2]=tableNotInserted+2;
 798                 table[3]=tableNotInserted+3;
 799
 800                 // Get cells
 801                 getCells (primitive, worldImage, primitiveWorldImage, table);
 802
 803                 // Force the test
 804                 singleTest=true;
 805         }
 806
 807         // For each move element
 808         for (uint i=0; i<4; i++)
 809         {
 810                 // Get the element
 811                 CMoveElement    *elm=table[i];
 812
 813                 // Element valid ?
 814                 if (elm)
 815                 {
 816                         // Check
 817                         nlassert (elm->Primitive==primitive);
 818                         // Primitive to the left
 819
 820                         // Lookup in X sorted list on the left
 821                         CMoveElement    *other=elm->PreviousX;
 822                         nlassert (other!=elm);
 823
 824                         while (other && (wI->getBBXMin() - other->Primitive->getWorldImage(worldImage)->getBBXMin() < _PrimitiveMaxSize) )
 825                         {
 826                                 // Other primitive
 827                                 CMovePrimitive  *otherPrimitive=other->Primitive;
 828                                 CPrimitiveWorldImage *otherWI=otherPrimitive->getWorldImage (worldImage);
 829                                 nlassert (otherPrimitive!=primitive);
 830
 831                                 // Continue the check if the other primitive is not int the modified list or if its pointer is higher than primitive
 832                                 if ( singleTest || ( (!otherWI->isInModifiedListFlag ()) || (primitive<otherPrimitive) ) )
 833                                 {
 834                                         // Look if valid in X
 835                                         if (wI->getBBXMin() < otherWI->getBBXMax())
 836                                         {
 837                                                 // Look if valid in Y
 838                                                 if ( (wI->getBBYMin() < otherWI->getBBYMax()) && (otherWI->getBBYMin() < wI->getBBYMax()) )
 839                                                 {
 840                                                         // If not already in collision with this primitive
 841                                                         if (!primitive->isInCollision (otherPrimitive))
 842                                                         {
 843                                                                 if (evalPrimAgainstPrimCollision (beginTime, primitive, otherPrimitive, wI, otherWI, testMove,
 844                                                                         primitiveWorldImage, worldImage, secondIsStatic, dynamicColInfo, contactNormal))
 845                                                                 {
 846                                                                         if (testMove)
 847                                                                                 return true;
 848                                                                         found=true;
 849                                                                 }
 850                                                         }
 851                                                 }
 852                                         }
 853                                 }
 854
 855                                 // Next primitive to the left
 856                                 other = other->PreviousX;
 857                         }
 858
 859                         // Lookup in X sorted list on the right
 860                         other=elm->NextX;
 861
 862                         // Primitive to the right
 863                         while (other && (other->Primitive->getWorldImage(worldImage)->getBBXMin() < wI->getBBXMax()) )
 864                         {
 865                                 // Other primitive
 866                                 CMovePrimitive  *otherPrimitive=other->Primitive;
 867                                 CPrimitiveWorldImage *otherWI=otherPrimitive->getWorldImage (worldImage);
 868                                 nlassert (otherPrimitive!=primitive);
 869
 870                                 // Continue the check if the other primitive is not in the modified list or if its pointer is higher than primitive
 871                                 if ( singleTest || ( (!otherWI->isInModifiedListFlag ()) || (primitive<otherPrimitive) ) )
 872                                 {
 873                                         // Look if valid in Y
 874                                         if ( (wI->getBBYMin() < otherWI->getBBYMax()) && (otherWI->getBBYMin() < wI->getBBYMax()) )
 875                                         {
 876                                                 // If not already in collision with this primitive
 877                                                 if (!primitive->isInCollision (otherPrimitive))
 878                                                 {
 879                                                         if (evalPrimAgainstPrimCollision (beginTime, primitive, otherPrimitive, wI, otherWI, testMove,
 880                                                         primitiveWorldImage, worldImage, secondIsStatic, dynamicColInfo, contactNormal))
 881                                                         {
 882                                                                 if (testMove)
 883                                                                         return true;
 884                                                                 found=true;
 885                                                         }
 886                                                 }
 887                                         }
 888                                 }
 889
 890                                 // Next primitive to the left
 891                                 other = other->NextX;
 892                         }
 893                 }
 894         }
 895
 896         return found;
 897 }
 898
 899 // ***************************************************************************
 900
 901 bool CMoveContainer::evalPrimAgainstPrimCollision (double beginTime, CMovePrimitive *primitive, CMovePrimitive *otherPrimitive,
 902                                                                                         CPrimitiveWorldImage *wI, CPrimitiveWorldImage *otherWI, bool testMove,
 903                                                                                         uint8 firstWorldImage, uint8 secondWorldImage, bool secondIsStatic, CCollisionOTDynamicInfo *dynamicColInfo,
 904                                                                                         CVectorD * /* contactNormal */)
 905 {
 906 //      H_AUTO(PACS_MC_evalPrimAgainstPrimCollision);
 907
 908         // Test the primitive
 909         double firstTime, lastTime;
 910
 911         // Collision
 912         CCollisionDesc desc;
 913         if (wI->evalCollision (*otherWI, desc, beginTime, _DeltaTime, _TestTime, _MaxTestIteration,
 914                                                                 firstTime, lastTime, *primitive, *otherPrimitive))
 915         {
 916                 // Enter or exit
 917                 bool enter = (beginTime<=firstTime) && (firstTime<_DeltaTime) && ((primitive->getTriggerType()&UMovePrimitive::EnterTrigger)
 918                         || (otherPrimitive->getTriggerType()&UMovePrimitive::EnterTrigger));
 919                 bool exit = (beginTime<=lastTime) && (lastTime<_DeltaTime) && ((primitive->getTriggerType()&UMovePrimitive::ExitTrigger)
 920                         || (otherPrimitive->getTriggerType()&UMovePrimitive::ExitTrigger));
 921                 bool overlap = (firstTime<=beginTime) && (lastTime>_DeltaTime) && ((primitive->getTriggerType()&UMovePrimitive::OverlapTrigger)
 922                         || (otherPrimitive->getTriggerType()&UMovePrimitive::OverlapTrigger));
 923                 bool contact = ( beginTime<((firstTime+lastTime)/2) ) && (firstTime<=_DeltaTime);
 924                 bool collision = contact && (primitive->isObstacle() && otherPrimitive->isObstacle ());
 925
 926                 // Return collision time
 927
 928                 if (testMove)
 929                         return contact;
 930
 931                 /**
 932                   * Raise Trigger !
 933                   * For collisionnable primitives, trigger are raised here (in reaction) because
 934                   * this is the moment we are sure the collision happened.
 935                   *
 936                   * For non collisionable primitves, the trigger is raised at collision time because without OT,
 937                   * we can't stop evaluating collision on triggers.
 938                   */
 939                 if (primitive->isNonCollisionable () && (enter || exit || overlap))
 940                 {
 941                         if (primitive->isTriggered (*otherPrimitive, enter, exit))
 942                         {
 943                                 // Add a trigger
 944                                 if (enter)
 945                                         newTrigger (primitive, otherPrimitive, desc, UTriggerInfo::In);
 946                                 if (exit)
 947                                         newTrigger (primitive, otherPrimitive, desc, UTriggerInfo::Out);
 948                                 if (overlap)
 949                                         newTrigger (primitive, otherPrimitive, desc, UTriggerInfo::Inside);
 950                         }
 951
 952                         // If the other primitive is not an obstacle, skip it because it will re-generate collisions.
 953                         if (!collision)
 954                                 return false;
 955                 }
 956
 957                 // OK, collision
 958                 if (contact || enter || exit || overlap)
 959                         newCollision (primitive, otherPrimitive, desc, contact, enter, exit, overlap, firstWorldImage, secondWorldImage, secondIsStatic,
 960                                                         dynamicColInfo);
 961
 962                 // Collision
 963                 return collision;
 964         }
 965         return false;
 966 }
 967
 968 // ***************************************************************************
 969
 970 void CMoveContainer::evalAllCollisions (double beginTime, uint8 worldImage)
 971 {
 972         H_AUTO(NLPACS_Eval_All_Collisions);
 973
 974         // First primitive
 975         CMovePrimitive  *primitive=_ChangedRoot[worldImage];
 976
 977         // For each modified primitive
 978         while (primitive)
 979         {
 980                 // Get the primitive world image
 981                 uint8 primitiveWorldImage;
 982                 CPrimitiveWorldImage *wI;
 983                 if (primitive->isNonCollisionable ())
 984                 {
 985                         wI=primitive->getWorldImage (0);
 986                         primitiveWorldImage=worldImage;
 987                 }
 988                 else
 989                 {
 990                         wI=primitive->getWorldImage (worldImage);
 991                         primitiveWorldImage=worldImage;
 992                 }
 993
 994                 CVectorD d0=wI->getDeltaPosition();
 995
 996                 // Find a collision
 997                 bool found=false;
 998                 bool testMoveValid=false;
 999
1000                 // Eval collision on the terrain
1001                 found|=evalOneTerrainCollision (beginTime, primitive, primitiveWorldImage, false, testMoveValid, NULL, NULL);
1002
1003                 // If the primitive can collid other primitive..
1004                 if (primitive->getCollisionMask())
1005                 {
1006                         // Eval collision in each static world image
1007                         std::set<uint8>::iterator ite=_StaticWorldImage.begin();
1008                         while (ite!=_StaticWorldImage.end())
1009                         {
1010                                 // Eval in this world image
1011                                 found|=evalOnePrimitiveCollision (beginTime, primitive, *ite, primitiveWorldImage, false, true, testMoveValid, NULL, NULL);
1012
1013                                 // Next world image
1014                                 ite++;
1015                         }
1016                 }
1017
1018                 CVectorD d1=wI->getDeltaPosition();
1019
1020                 // If the primitive can collid other primitive..
1021                 if (primitive->getCollisionMask())
1022                 {
1023                         // Eval collision in the world image if not already tested
1024                         if (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end())
1025                                 found|=evalOnePrimitiveCollision (beginTime, primitive, worldImage, primitiveWorldImage, false, false, testMoveValid, NULL, NULL);
1026                 }
1027
1028                 CVectorD d2=wI->getDeltaPosition();
1029
1030                 // No collision ?
1031                 if (!found)
1032                 {
1033                         //nlassert ((d0==d1)&&(d0==d2));
1034                         //nlassert (f1==f2);
1035
1036                         if (_Retriever&&testMoveValid)
1037                         {
1038                                 // Do move
1039                                 wI->doMove (*_Retriever, _SurfaceTemp, _DeltaTime, _DeltaTime, primitive->getDontSnapToGround());
1040                         }
1041                         else
1042                         {
1043                                 // Do move
1044                                 wI->doMove (_DeltaTime);
1045                         }
1046                 }
1047
1048                 // Next primitive
1049                 primitive=wI->getNextModified ();
1050         }
1051 }
1052
1053 // ***************************************************************************
1054
1055 void CMoveContainer::newCollision (CMovePrimitive* first, CMovePrimitive* second, const CCollisionDesc& desc, bool collision, bool enter, bool exit, bool inside,
1056                                                                    uint firstWorldImage, uint secondWorldImage, bool secondIsStatic, CCollisionOTDynamicInfo *dynamicColInfo)
1057 {
1058 //      H_AUTO(PACS_MC_newCollision_short);
1059
1060         nlassert ((dynamicColInfo && first->isNonCollisionable ()) || (!dynamicColInfo && first->isCollisionable ()));
1061
1062         if (dynamicColInfo)
1063         {
1064                 dynamicColInfo->init (first, second, desc, collision, enter, exit, inside, uint8(firstWorldImage), uint8(secondWorldImage), secondIsStatic);
1065         }
1066         else
1067         {
1068                 // Get an ordered time index. Always round to the future.
1069                 int index=(int)(ceil (desc.ContactTime*(double)_OtSize/_DeltaTime) );
1070
1071                 // Clamp left.
1072                 if (index<0)
1073                         index=0;
1074
1075                 // If in time
1076                 if (index<(int)_OtSize)
1077                 {
1078                         // Build info
1079                         CCollisionOTDynamicInfo *info = allocateOTDynamicInfo ();
1080                         info->init (first, second, desc, collision, enter, exit, inside, uint8(firstWorldImage), uint8(secondWorldImage), secondIsStatic);
1081
1082                         // Add in the primitive list
1083                         first->addCollisionOTInfo (info);
1084                         second->addCollisionOTInfo (info);
1085
1086                         // Insert in the time ordered table
1087                         //nlassert (index<(int)_TimeOT.size());
1088                         if (index >= (int)_TimeOT.size())
1089                         {
1090                                 nlwarning("PACS: newCollision() failure, index [%d] >= (int)_TimeOT.size() [%d], clamped to max", index, (int)_TimeOT.size());
1091                                 index = (int)_TimeOT.size()-1;
1092                         }
1093                         _TimeOT[index].link (info);
1094
1095                         // Check it is after the last hard collision
1096                         nlassert (_PreviousCollisionNode<=&_TimeOT[index]);
1097                 }
1098         }
1099 }
1100
1101 // ***************************************************************************
1102
1103 void CMoveContainer::newCollision (CMovePrimitive* first, const CCollisionSurfaceDesc& desc, uint8 worldImage, double beginTime, CCollisionOTStaticInfo *staticColInfo)
1104 {
1105 //      H_AUTO(PACS_MC_newCollision_long);
1106
1107         // Check
1108         nlassert (_Retriever);
1109         nlassert ((staticColInfo && first->isNonCollisionable ()) || (!staticColInfo && first->isCollisionable ()));
1110
1111         // Get the world image
1112         CPrimitiveWorldImage *wI;
1113         if (first->isNonCollisionable())
1114                 wI=first->getWorldImage (0);
1115         else
1116                 wI=first->getWorldImage (worldImage);
1117
1118         // Time
1119         double time=desc.ContactTime;
1120 /*
1121         if (time == _DeltaTime)
1122                 time -= _DeltaTime*FLT_EPSILON;
1123 */
1124
1125         // Check time interval
1126
1127         //nlassertex (beginTime<=time, ("beginTime=%f, time=%f", beginTime, time));
1128         //nlassertex (time<_DeltaTime, ("time=%f, _DeltaTime=%f", time, _DeltaTime));
1129
1130         if (beginTime > time)
1131         {
1132                 nlwarning("PACS: beginTime=%f > time=%f", beginTime, time);
1133         }
1134
1135         if (time >= _DeltaTime)
1136         {
1137                 nlinfo("PACS: time=%f >= _DeltaTime=%f", time, _DeltaTime);
1138         }
1139
1140
1141         // Time of the collision.
1142         time-=NELPACS_DIST_BACK/wI->getSpeed().norm();
1143         time=std::max(time, beginTime);
1144         double ratio=(time-beginTime)/(_DeltaTime-beginTime);
1145
1146 /*
1147         nlassert (ratio>=0);
1148         nlassert (ratio<=1);
1149 */
1150
1151         if (ratio < 0.0)
1152         {
1153                 nlwarning("PACS: ratio=%f < 0.0", ratio);
1154                 ratio = 0.0;
1155         }
1156
1157         if (ratio > 1.0)
1158         {
1159                 nlwarning("PACS: ratio=%f > 1.0", ratio);
1160                 ratio = 1.0;
1161         }
1162
1163         if (staticColInfo)
1164         {
1165                 // Make a new globalposition
1166                 UGlobalPosition endPosition=_Retriever->doMove (wI->getGlobalPosition(), wI->getDeltaPosition(),
1167                         (float)ratio, _SurfaceTemp, false);
1168
1169                 // Init the info descriptor
1170                 staticColInfo->init (first, desc, endPosition, ratio, worldImage);
1171         }
1172         else
1173         {
1174                 // Get an ordered time index. Always round to the future.
1175                 int index=(int)(ceil (time*(double)_OtSize/_DeltaTime) );
1176
1177                 // Clamp left.
1178                 if (index<0)
1179                         index=0;
1180
1181                 // If in time
1182                 if (index<(int)_OtSize)
1183                 {
1184                         // Build info
1185                         CCollisionOTStaticInfo *info = allocateOTStaticInfo ();
1186
1187                         // Make a new globalposition
1188                         UGlobalPosition endPosition=_Retriever->doMove (wI->getGlobalPosition(), wI->getDeltaPosition(),
1189                                 (float)ratio, _SurfaceTemp, false);
1190
1191                         // Init the info descriptor
1192                         info->init (first, desc, endPosition, ratio, worldImage);
1193
1194                         // Add in the primitive list
1195                         first->addCollisionOTInfo (info);
1196
1197                         // Insert in the time ordered table
1198                         //nlassert (index<(int)_TimeOT.size());
1199                         if (index >= (int)_TimeOT.size())
1200                         {
1201                                 nlwarning("PACS: newCollision() failure, index [%d] >= (int)_TimeOT.size() [%d], clamped to max", index, (int)_TimeOT.size());
1202                                 index = (int)_TimeOT.size()-1;
1203                         }
1204                         _TimeOT[index].link (info);
1205
1206                         // Check it is after the last hard collision
1207                         nlassert (_PreviousCollisionNode<=&_TimeOT[index]);
1208                 }
1209         }
1210 }
1211
1212 // ***************************************************************************
1213
1214 void CMoveContainer::newTrigger (CMovePrimitive* first, CMovePrimitive* second, const CCollisionDesc& desc, uint triggerType)
1215 {
1216         // Element index
1217         uint index=(uint)_Triggers.size();
1218
1219         // Add one element
1220         _Triggers.resize (index+1);
1221
1222         // Fill info
1223         _Triggers[index].Object0=first->UserData;
1224         _Triggers[index].Object1=second->UserData;
1225         _Triggers[index].CollisionDesc=desc;
1226         _Triggers[index].CollisionType = uint8(triggerType);
1227 }
1228
1229 // ***************************************************************************
1230
1231 void CMoveContainer::checkOT ()
1232 {
1233         // Check
1234         nlassert (_OtSize==_TimeOT.size());
1235
1236         // Check linked list
1237         for (uint i=0; i<_OtSize-1; i++)
1238         {
1239                 // Check link
1240                 nlassert ( _TimeOT[i].getNext() == (&(_TimeOT[i+1])) );
1241                 nlassert ( _TimeOT[i+1].getPrevious() == (&(_TimeOT[i])) );
1242         }
1243
1244         // Check first and last
1245         nlassert ( _TimeOT[0].getPrevious() == NULL );
1246         nlassert ( _TimeOT[_OtSize-1].getNext() == NULL );
1247 }
1248
1249 // ***************************************************************************
1250
1251 void CMoveContainer::clearOT ()
1252 {
1253         // Check
1254         nlassert (_OtSize==_TimeOT.size());
1255
1256         // clear the list
1257         uint i;
1258         for (i=0; i<_OtSize; i++)
1259                 _TimeOT[i].clear ();
1260
1261         // Relink the list
1262         for (i=0; i<_OtSize-1; i++)
1263                 // Link the two cells
1264                 _TimeOT[i].link (&(_TimeOT[i+1]));
1265 }
1266
1267 // ***************************************************************************
1268
1269 void CMoveContainer::removeModifiedFromOT (uint8 worldImage)
1270 {
1271         // For each changed primitives
1272         CMovePrimitive *changed=_ChangedRoot[worldImage];
1273         while (changed)
1274         {
1275                 // Remove from ot list
1276                 changed->removeCollisionOTInfo ();
1277
1278                 // Get the primitive world image
1279                 CPrimitiveWorldImage *wI;
1280                 if (changed->isNonCollisionable())
1281                         wI=changed->getWorldImage (0);
1282                 else
1283                         wI=changed->getWorldImage (worldImage);
1284
1285                 // Next primitive
1286                 changed=wI->getNextModified ();
1287         }
1288 }
1289
1290 // ***************************************************************************
1291
1292 CCollisionOTDynamicInfo *CMoveContainer::allocateOTDynamicInfo ()
1293 {
1294         return _AllocOTDynamicInfo.allocate ();
1295 }
1296
1297 // ***************************************************************************
1298
1299 CCollisionOTStaticInfo *CMoveContainer::allocateOTStaticInfo ()
1300 {
1301         return _AllocOTStaticInfo.allocate ();
1302 }
1303
1304 // ***************************************************************************
1305
1306 // Free all ordered table info
1307 void CMoveContainer::freeAllOTInfo ()
1308 {
1309         H_AUTO (NLPACS_Free_All_OT_Info);
1310
1311         _AllocOTDynamicInfo.freeBlock ();
1312         _AllocOTStaticInfo.freeBlock ();
1313 }
1314
1315 // ***************************************************************************
1316
1317 CMovePrimitive *CMoveContainer::allocatePrimitive (uint8 firstWorldImage, uint8 numWorldImage)
1318 {
1319         // Simply allocate
1320         return new CMovePrimitive (this, firstWorldImage, numWorldImage);
1321 }
1322
1323 // ***************************************************************************
1324
1325 void CMoveContainer::freePrimitive (CMovePrimitive *primitive)
1326 {
1327         // Simply deallocate
1328         delete primitive;
1329 }
1330
1331 // ***************************************************************************
1332
1333 CPrimitiveWorldImage    **CMoveContainer::allocateWorldImagesPtrs (uint numPtrs)
1334 {
1335         return new CPrimitiveWorldImage*[numPtrs];
1336 }
1337
1338 // ***************************************************************************
1339
1340 void CMoveContainer::freeWorldImagesPtrs (CPrimitiveWorldImage **ptrs)
1341 {
1342                 delete [] ptrs;
1343 }
1344
1345 // ***************************************************************************
1346
1347 CPrimitiveWorldImage    *CMoveContainer::allocateWorldImage ()
1348 {
1349         return new CPrimitiveWorldImage;
1350 }
1351
1352 // ***************************************************************************
1353
1354 void CMoveContainer::freeWorldImage (CPrimitiveWorldImage *worldImage)
1355 {
1356         delete worldImage;
1357 }
1358
1359 // ***************************************************************************
1360
1361 CMoveElement *CMoveContainer::allocateMoveElement ()
1362 {
1363         // Simply allocate
1364         return new CMoveElement;
1365 }
1366
1367 // ***************************************************************************
1368
1369 void CMoveContainer::freeMoveElement (CMoveElement *element)
1370 {
1371         // Simply deallocate
1372         delete element;
1373 }
1374
1375 // ***************************************************************************
1376
1377 void    UMoveContainer::deleteMoveContainer (UMoveContainer     *container)
1378 {
1379         delete (CMoveContainer*)container;
1380 }
1381
1382 // ***************************************************************************
1383
1384 UMovePrimitive *CMoveContainer::addCollisionablePrimitive (uint8 firstWorldImage, uint8 numWorldImage, const UMovePrimitive *copyFrom)
1385 {
1386
1387         // Allocate primitive
1388         CMovePrimitive *primitive=allocatePrimitive (firstWorldImage, numWorldImage);
1389
1390         // Add into the set
1391         _PrimitiveSet.insert (primitive);
1392
1393         // if copy from primitive is not null, copy attributes
1394         if (copyFrom != NULL)
1395         {
1396                 primitive->setPrimitiveType(copyFrom->getPrimitiveType());
1397                 primitive->setReactionType(copyFrom->getReactionType());
1398                 primitive->setTriggerType(copyFrom->getTriggerType());
1399                 primitive->setCollisionMask(copyFrom->getCollisionMask());
1400                 primitive->setOcclusionMask(copyFrom->getOcclusionMask());
1401                 primitive->setObstacle(copyFrom->getObstacle());
1402                 primitive->setAbsorbtion(copyFrom->getAbsorbtion());
1403                 primitive->setHeight(copyFrom->getHeight());
1404                 if (primitive->getPrimitiveType() == UMovePrimitive::_2DOrientedBox)
1405                 {
1406                         float   width=0.0f, height=0.0f;
1407                         copyFrom->getSize(width, height);
1408                         primitive->setSize(width, height);
1409                 }
1410                 else
1411                 {
1412                         primitive->setRadius(copyFrom->getRadius());
1413                 }
1414         }
1415
1416         // Return it
1417         return primitive;
1418 }
1419
1420 // ***************************************************************************
1421
1422 UMovePrimitive *CMoveContainer::addNonCollisionablePrimitive (const UMovePrimitive *copyFrom)
1423 {
1424
1425         // Allocate primitive
1426         CMovePrimitive *primitive=allocatePrimitive (0, 1);
1427
1428         // Set as noncollisionable
1429         primitive->setNonCollisionable (true);
1430
1431         // Add into the set
1432         _PrimitiveSet.insert (primitive);
1433
1434         // if copy from primitive is not null, copy attributes
1435         if (copyFrom != NULL)
1436         {
1437                 primitive->setPrimitiveType(copyFrom->getPrimitiveType());
1438                 primitive->setReactionType(copyFrom->getReactionType());
1439                 primitive->setTriggerType(copyFrom->getTriggerType());
1440                 primitive->setCollisionMask(copyFrom->getCollisionMask());
1441                 primitive->setOcclusionMask(copyFrom->getOcclusionMask());
1442                 primitive->setObstacle(copyFrom->getObstacle());
1443                 primitive->setAbsorbtion(copyFrom->getAbsorbtion());
1444                 primitive->setHeight(copyFrom->getHeight());
1445                 if (primitive->getPrimitiveType() == UMovePrimitive::_2DOrientedBox)
1446                 {
1447                         float   width=0.0f, height=0.0f;
1448                         copyFrom->getSize(width, height);
1449                         primitive->setSize(width, height);
1450                 }
1451                 else
1452                 {
1453                         primitive->setRadius(copyFrom->getRadius());
1454                 }
1455         }
1456
1457         // Return it
1458         return primitive;
1459 }
1460
1461 // ***************************************************************************
1462
1463 void CMoveContainer::removePrimitive (UMovePrimitive* primitive)
1464 {
1465
1466         // CMovePrimitive pointer
1467         CMovePrimitive *prim=(CMovePrimitive*)primitive;
1468
1469         // Get the primitive world image
1470         for (uint8 i=0; i<prim->getNumWorldImage (); i++)
1471         {
1472                 // World image
1473                 uint8 worldImage=prim->getFirstWorldImage ()+i;
1474
1475                 // Get primitive world image
1476                 CPrimitiveWorldImage *wI=prim->getWorldImage (worldImage);
1477
1478                 // In modified list ?
1479                 if (wI->isInModifiedListFlag ())
1480                 {
1481                         // Non collisionable primitive ?
1482                         if (prim->isNonCollisionable())
1483                         {
1484                                 // Remove from all world image
1485                                 removeNCFromModifiedList (prim, worldImage);
1486                         }
1487                         else
1488                         {
1489                                 // Remove from modified list
1490                                 removeFromModifiedList (prim, worldImage);
1491                         }
1492                 }
1493         }
1494
1495         // Remove from the set
1496         _PrimitiveSet.erase (prim);
1497
1498         // Erase it
1499         freePrimitive (prim);
1500 }
1501
1502 // ***************************************************************************
1503
1504 void CMoveContainer::removeNCFromModifiedList (CMovePrimitive* primitive, uint8 worldImage)
1505 {
1506         // For each world image
1507         uint i;
1508         uint worldImageCount = (uint)_ChangedRoot.size();
1509         for (i=0; i<worldImageCount; i++)
1510         {
1511                 // For each changed primitives
1512                 CMovePrimitive *changed=_ChangedRoot[i];
1513                 CPrimitiveWorldImage *previous=NULL;
1514                 CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
1515
1516                 while (changed)
1517                 {
1518                         // Get the primitive world image
1519                         CPrimitiveWorldImage *changedWI=changed->getWorldImage (worldImage);
1520
1521                         // Remove from ot list
1522                         if (changed==primitive)
1523                         {
1524                                 // There is a previous primitive ?
1525                                 if (previous)
1526                                         previous->linkInModifiedList (wI->getNextModified ());
1527                                 else
1528                                         _ChangedRoot[i]=wI->getNextModified ();
1529
1530                                 // Unlink
1531                                 wI->linkInModifiedList (NULL);
1532                                 wI->setInModifiedListFlag (false);
1533                                 break;
1534                         }
1535
1536                         // Next primitive
1537                         previous=changedWI;
1538                         changed=changedWI->getNextModified ();
1539                 }
1540
1541                 // Breaked ?
1542                 if (changed==primitive)
1543                         break;
1544         }
1545 }
1546
1547 // ***************************************************************************
1548
1549 void CMoveContainer::removeFromModifiedList (CMovePrimitive* primitive, uint8 worldImage)
1550 {
1551         // For each changed primitives
1552         CMovePrimitive *changed=_ChangedRoot[worldImage];
1553         CPrimitiveWorldImage *previous=NULL;
1554         CPrimitiveWorldImage *wI=primitive->getWorldImage (worldImage);
1555
1556         while (changed)
1557         {
1558                 // Get the primitive world image
1559                 CPrimitiveWorldImage *changedWI=changed->getWorldImage (worldImage);
1560
1561                 // Remove from ot list
1562                 if (changed==primitive)
1563                 {
1564                         // There is a previous primitive ?
1565                         if (previous)
1566                                 previous->linkInModifiedList (wI->getNextModified ());
1567                         else
1568                                 _ChangedRoot[worldImage]=wI->getNextModified ();
1569
1570                         // Unlink
1571                         wI->linkInModifiedList (NULL);
1572                         wI->setInModifiedListFlag (false);
1573                         break;
1574                 }
1575
1576                 // Next primitive
1577                 previous=changedWI;
1578                 changed=changedWI->getNextModified ();
1579         }
1580 }
1581
1582 // ***************************************************************************
1583
1584 void CMoveContainer::unlinkMoveElement  (CMoveElement *element, uint8 worldImage)
1585 {
1586         // Some checks
1587         nlassert (element->X<_CellCountWidth);
1588         nlassert (element->Y<_CellCountHeight);
1589
1590         // Unlink it
1591         CMoveCell &cell=_VectorCell[worldImage][element->X+element->Y*_CellCountWidth];
1592         cell.unlinkX (element);
1593         //cell.unlinkY (element);
1594 }
1595
1596 // ***************************************************************************
1597
1598 void CMoveContainer::reaction (const CCollisionOTInfo& first)
1599 {
1600 //      H_AUTO(PACS_MC_reaction);
1601
1602         // Static collision ?
1603         if (first.isCollisionAgainstStatic())
1604         {
1605                 // Check mode
1606                 nlassert (_Retriever);
1607
1608                 // Cast
1609                 const CCollisionOTStaticInfo *staticInfo=safe_cast<const CCollisionOTStaticInfo*> (&first);
1610
1611                 // Get the primitive world image
1612                 CMovePrimitive *movePrimitive=staticInfo->getPrimitive ();
1613                 CPrimitiveWorldImage *wI;
1614                 if (movePrimitive->isNonCollisionable ())
1615                         wI=movePrimitive->getWorldImage (0);
1616                 else
1617                         wI=movePrimitive->getWorldImage (staticInfo->getWorldImage());
1618
1619                 // Dynamic collision
1620                 wI->reaction ( staticInfo->getCollisionDesc (), staticInfo->getGlobalPosition (),
1621                                                 *_Retriever, staticInfo->getDeltaTime(), _DeltaTime, *staticInfo->getPrimitive (), *this, staticInfo->getWorldImage());
1622         }
1623         else
1624         {
1625                 // Cast
1626                 const CCollisionOTDynamicInfo *dynInfo=safe_cast<const CCollisionOTDynamicInfo*> (&first);
1627
1628                 // Get the primitives world image
1629                 CPrimitiveWorldImage *firstWI;
1630                 if (dynInfo->getFirstPrimitive ()->isNonCollisionable ())
1631                         firstWI=dynInfo->getFirstPrimitive ()->getWorldImage (0);
1632                 else
1633                         firstWI=dynInfo->getFirstPrimitive ()->getWorldImage (dynInfo->getFirstWorldImage());
1634
1635                 CPrimitiveWorldImage *secondWI;
1636                 if (dynInfo->getSecondPrimitive ()->isNonCollisionable ())
1637                         secondWI=dynInfo->getSecondPrimitive ()->getWorldImage (0);
1638                 else
1639                         secondWI=dynInfo->getSecondPrimitive ()->getWorldImage (dynInfo->getSecondWorldImage());
1640
1641                 // Dynamic collision
1642                 firstWI->reaction ( *secondWI, dynInfo->getCollisionDesc (), _Retriever, _SurfaceTemp, dynInfo->isCollision(),
1643                                                         *dynInfo->getFirstPrimitive (), *dynInfo->getSecondPrimitive (), this, dynInfo->getFirstWorldImage(),
1644                                                         dynInfo->getSecondWorldImage(), dynInfo->isSecondStatic());
1645
1646                 /**
1647                   * Raise Trigger !
1648                   * For collisionnable primitives, trigger are raised here (in reaction) because
1649                   * this is the moment we are sure the collision happened.
1650                   *
1651                   * For non collisionable primitves, the trigger is raised at collision time because without OT,
1652                   * we can't stop evaluating collision on triggers.
1653                   */
1654                 if (dynInfo->getFirstPrimitive ()->isCollisionable ())
1655                 {
1656                         if (dynInfo->getFirstPrimitive ()->isTriggered (*dynInfo->getSecondPrimitive (), dynInfo->isEnter(), dynInfo->isExit()))
1657                         {
1658                                 if (dynInfo->isEnter())
1659                                         newTrigger (dynInfo->getFirstPrimitive (), dynInfo->getSecondPrimitive (), dynInfo->getCollisionDesc (), UTriggerInfo::In);
1660                                 if (dynInfo->isExit())
1661                                         newTrigger (dynInfo->getFirstPrimitive (), dynInfo->getSecondPrimitive (), dynInfo->getCollisionDesc (), UTriggerInfo::Out);
1662                                 if (dynInfo->isInside())
1663                                         newTrigger (dynInfo->getFirstPrimitive (), dynInfo->getSecondPrimitive (), dynInfo->getCollisionDesc (), UTriggerInfo::Inside);
1664                         }
1665                 }
1666         }
1667 }
1668
1669 // ***************************************************************************
1670
1671 void CMoveContainer::setAsStatic (uint8 worldImage)
1672 {
1673
1674         // Add this world image in the static set of world image
1675         _StaticWorldImage.insert (worldImage);
1676 }
1677
1678 // ***************************************************************************
1679
1680 void CMoveContainer::duplicateWorldImage (uint8 source, uint8 dest)
1681 {
1682
1683         // Cell count
1684         uint cellCount=_CellCountWidth*_CellCountHeight;
1685
1686         // Clear dest modified list
1687         clearModifiedList (dest);
1688
1689         // Clear destination cells
1690         uint i;
1691         for (i=0; i<cellCount; i++)
1692         {
1693                 // Get first X
1694                 CMoveElement *elm;
1695                 while ((elm=_VectorCell[dest][i].getFirstX ()))
1696                 {
1697                         // Get primitive world image
1698                         CPrimitiveWorldImage *wI=elm->Primitive->getWorldImage (dest);
1699
1700                         // Remove the primitive
1701                         int i;
1702                         for (i=0; i<4; i++)
1703                         {
1704                                 if (wI->getMoveElement(i))
1705                                         wI->removeMoveElement (i, *this, dest);
1706                         }
1707                 }
1708         }
1709
1710         // Duplicate destination cells
1711         for (i=0; i<cellCount; i++)
1712         {
1713                 // Get first X
1714                 CMoveElement *elm=_VectorCell[source][i].getFirstX ();
1715                 while (elm)
1716                 {
1717                         // Get primitive world image
1718                         CPrimitiveWorldImage *wISource=elm->Primitive->getWorldImage (source);
1719                         CPrimitiveWorldImage *wIDest=elm->Primitive->getWorldImage (dest);
1720
1721                         // First time the primitive is visited ?
1722                         if (wIDest->getMoveElement (0)==NULL)
1723                         {
1724                                 wIDest->copy (*wISource);
1725                         }
1726
1727                         // Add at the end of the list
1728                         wIDest->addMoveElementendOfList (_VectorCell[dest][i], elm->X, elm->Y, elm->Primitive, *this);
1729
1730                         // Added ?
1731                         nlassert (wIDest->getMoveElement (0)!=NULL);
1732
1733                         // Next primitive
1734                         elm=elm->NextX;
1735                 }
1736         }
1737 }
1738
1739 // ***************************************************************************
1740
1741 UMoveContainer *UMoveContainer::createMoveContainer (double xmin, double ymin, double xmax, double ymax,
1742                 uint widthCellCount, uint heightCellCount, double primitiveMaxSize, uint8 numWorldImage,
1743                 uint maxIteration, uint otSize)
1744 {
1745
1746         // Create a CMoveContainer
1747         return new CMoveContainer (xmin, ymin, xmax, ymax, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
1748 }
1749
1750 // ***************************************************************************
1751
1752 UMoveContainer *UMoveContainer::createMoveContainer (UGlobalRetriever* retriever, uint widthCellCount,
1753         uint heightCellCount, double primitiveMaxSize, uint8 numWorldImage, uint maxIteration, uint otSize)
1754 {
1755
1756         // Cast
1757         nlassert (dynamic_cast<CGlobalRetriever*>(retriever));
1758         CGlobalRetriever* r=static_cast<CGlobalRetriever*>(retriever);
1759
1760         // Create a CMoveContainer
1761         return new CMoveContainer (r, widthCellCount, heightCellCount, primitiveMaxSize, numWorldImage, maxIteration, otSize);
1762 }
1763
1764 // ***************************************************************************
1765
1766 void UCollisionDesc::serial (NLMISC::IStream& stream)
1767 {
1768         stream.serial (ContactPosition);
1769         stream.serial (ContactNormal0);
1770         stream.serial (ContactNormal1);
1771         stream.serial (ContactTime);
1772 };
1773
1774 // ***************************************************************************
1775
1776 void UTriggerInfo::serial (NLMISC::IStream& stream)
1777 {
1778         stream.serial (Object0);
1779         stream.serial (Object1);
1780         stream.serial (CollisionDesc);
1781 }
1782
1783
1784
1785 // ***************************************************************************
1786 void CMoveContainer::addCollisionnablePrimitiveBlock(UPrimitiveBlock *pb,uint8 firstWorldImage,uint8 numWorldImage,std::vector<UMovePrimitive*> *primitives,float orientation,const NLMISC::CVector &position, bool dontSnapToGround /* = false*/, const NLMISC::CVector &scale /* = NLMISC::CVector(1.0f, 1.0f, 1.0f)*/)
1787 {
1788
1789         CPrimitiveBlock *block = NLMISC::safe_cast<CPrimitiveBlock *>(pb);
1790         // Reserve the pointer array
1791         if (primitives)
1792                 primitives->reserve (block->Primitives.size());
1793
1794         // For each primitive
1795         uint prim;
1796         for (prim=0; prim<block->Primitives.size(); prim++)
1797         {
1798                 // Create a collisionable primitive
1799                 UMovePrimitive *primitive = addCollisionablePrimitive (firstWorldImage, numWorldImage);
1800
1801                 // Ref on the block descriptor
1802                 CPrimitiveDesc &desc = block->Primitives[prim];
1803
1804                 // Set its properties
1805                 primitive->setPrimitiveType (desc.Type);
1806                 primitive->setReactionType (desc.Reaction);
1807                 primitive->setTriggerType (desc.Trigger);
1808                 primitive->setCollisionMask (desc.CollisionMask);
1809                 primitive->setOcclusionMask (desc.OcclusionMask);
1810                 primitive->setObstacle (desc.Obstacle);
1811                 primitive->setAbsorbtion (desc.Attenuation);
1812                 primitive->setDontSnapToGround(dontSnapToGround);
1813                 primitive->UserData = desc.UserData;
1814                 if (desc.Type == UMovePrimitive::_2DOrientedBox)
1815                 {
1816                         // ONLY ASSUME UNIFORM SCALE ON X/Y
1817                         primitive->setSize (desc.Length[0]*scale.x, desc.Length[1]*scale.x);
1818                 }
1819                 else
1820                 {
1821                         // ONLY ASSUME UNIFORM SCALE ON X/Y
1822                         nlassert (desc.Type == UMovePrimitive::_2DOrientedCylinder);
1823                         primitive->setRadius (desc.Length[0]*scale.x);
1824                 }
1825                 primitive->setHeight (desc.Height*scale.z);
1826
1827                 // Insert the primitives
1828
1829                 // For each world image
1830                 uint wI;
1831                 for (wI=firstWorldImage; wI<(uint)(firstWorldImage+numWorldImage); wI++)
1832                 {
1833                         // Insert the primitive
1834                         primitive->insertInWorldImage (uint8(wI));
1835
1836                         // Final position&
1837                         float cosa = (float) cos (orientation);
1838                         float sina = (float) sin (orientation);
1839                         CVector finalPos;
1840                         finalPos.x = cosa * desc.Position.x * scale.x - sina * desc.Position.y * scale.y + position.x;
1841                         finalPos.y = sina * desc.Position.x * scale.x + cosa * desc.Position.y * scale.y + position.y;
1842                         finalPos.z = desc.Position.z *scale.z + position.z;
1843
1844                         // Set the primtive orientation
1845                         if (desc.Type == UMovePrimitive::_2DOrientedBox)
1846                                 primitive->setOrientation ((float)fmod ((float)(desc.Orientation + orientation), (float)(2.0f*Pi)), uint8(wI));
1847
1848                         // Set the primitive global position
1849                         primitive->setGlobalPosition (finalPos, uint8(wI));
1850                 }
1851
1852                 // Feedback asked ?
1853                 if (primitives)
1854                 {
1855                         // Add the pointer
1856                         primitives->push_back (primitive);
1857                 }
1858         }
1859 }
1860
1861
1862 // ***************************************************************************
1863
1864 bool CMoveContainer::loadCollisionablePrimitiveBlock (const char *filename, uint8 firstWorldImage, uint8 numWorldImage, std::vector<UMovePrimitive*> *primitives, float orientation, const NLMISC::CVector &position, bool dontSnapToGround /*= false*/)
1865 {
1866
1867         // Check world image
1868         if ( (uint)(firstWorldImage+numWorldImage) > _ChangedRoot.size() )
1869         {
1870                 nlwarning ("Invalid world image number.");
1871                 return false;
1872         }
1873
1874         // Try to load the file
1875         CIFile file;
1876         if (file.open (filename))
1877         {
1878                 // Create the XML stream
1879                 CIXml input;
1880
1881                 // Init
1882                 if (input.init (file))
1883                 {
1884                         // The primitive block
1885                         CPrimitiveBlock block;
1886
1887                         // Serial it
1888                         file.serial (block);
1889
1890                         // add primitives
1891                         addCollisionnablePrimitiveBlock(&block, firstWorldImage, numWorldImage, primitives, orientation, position, dontSnapToGround);
1892
1893                         return true;
1894                 }
1895                 else
1896                 {
1897                         // Warning
1898                         nlwarning ("Can't init XML stream with file %s.", filename);
1899
1900                         return false;
1901                 }
1902         }
1903         else
1904         {
1905                 // Warning
1906                 nlwarning ("Can't load primitive block %s.", filename);
1907
1908                 return false;
1909         }
1910 }
1911
1912
1913 // ***************************************************************************
1914 void CMoveContainer::getPrimitives(std::vector<const UMovePrimitive *> &dest) const
1915 {
1916
1917         dest.resize(_PrimitiveSet.size());
1918         std::copy(_PrimitiveSet.begin(), _PrimitiveSet.end(), dest.begin());
1919 }
1920
1921
1922 // ***************************************************************************
1923 void UMoveContainer::getPACSCoordsFromMatrix(NLMISC::CVector &pos,float &angle,const NLMISC::CMatrix &mat)
1924 {
1925         pos = mat.getPos();
1926         CVector orient = mat.mulVector(NLMISC::CVector::I);
1927         orient.z = 0.f;
1928         orient.normalize();
1929         angle = orient.y >= 0.f ? ::acosf(orient.x)
1930                                                         : 2.f * (float) NLMISC::Pi - ::acosf(orient.x);
1931
1932 }
1933
1934 // ***************************************************************************
1935 bool CMoveContainer::evalNCPrimitiveCollision (double deltaTime, UMovePrimitive *primitive, uint8 worldImage)
1936 {
1937
1938         // New test time
1939         _TestTime++;
1940
1941         // Clear triggers
1942         _Triggers.clear ();
1943
1944         // Only non-collisionable primitives
1945         if (!primitive->isCollisionable())
1946         {
1947                 // Delta time
1948                 _DeltaTime=deltaTime;
1949
1950                 // Begin of the time slice to compute
1951                 double beginTime = 0;
1952                 double collisionTime = deltaTime;
1953
1954                 // Get the world image
1955                 CPrimitiveWorldImage *wI = ((CMovePrimitive*)primitive)->getWorldImage (0);
1956
1957                 CCollisionOTInfo *firstCollision = NULL;
1958                 do
1959                 {
1960                         //nlassert (beginTime < 1.0);
1961                         if (beginTime >= 1.0)
1962                         {
1963                                 nlwarning("PACS: evalNCPrimitiveCollision() failure, beginTime [%f] >= 1.0", beginTime);
1964                                 return false;
1965                         }
1966
1967                         // Update the primitive
1968                         wI->update (beginTime, deltaTime, *(CMovePrimitive*)primitive);
1969
1970                         CVectorD d0=wI->getDeltaPosition();
1971
1972                         // Eval collision again the terrain
1973                         bool testMoveValid = false;
1974                         CCollisionOTStaticInfo staticColInfo;
1975                         CCollisionOTDynamicInfo dynamicColInfoWI0;
1976                         CCollisionOTDynamicInfo dynamicColInfoWI;
1977
1978                         firstCollision = NULL;
1979
1980                         // If collision found, note it is on the landscape
1981                         if (evalOneTerrainCollision (beginTime, (CMovePrimitive*)primitive, worldImage, false, testMoveValid, &staticColInfo, NULL))
1982                         {
1983                                 firstCollision = &staticColInfo;
1984                         }
1985
1986                         // Eval collision again the static primitives
1987                         std::set<uint8>::iterator ite=_StaticWorldImage.begin();
1988                         while (ite!=_StaticWorldImage.end())
1989                         {
1990                                 // Eval in this world image
1991                                 if (evalOnePrimitiveCollision (beginTime, (CMovePrimitive*)primitive, *ite, worldImage, false, true, testMoveValid, &dynamicColInfoWI0, NULL))
1992                                 {
1993                                         // First collision..
1994                                         if (!firstCollision || (firstCollision->getCollisionTime () > dynamicColInfoWI0.getCollisionTime ()))
1995                                         {
1996                                                 firstCollision = &dynamicColInfoWI0;
1997                                         }
1998                                 }
1999
2000                                 // Next world image
2001                                 ite++;
2002                         }
2003
2004                         // Checks
2005                         CVectorD d1=wI->getDeltaPosition();
2006
2007                         // Eval collision again the world image
2008                         if (_StaticWorldImage.find (worldImage)==_StaticWorldImage.end())
2009                         {
2010                                 if (evalOnePrimitiveCollision (beginTime, (CMovePrimitive*)primitive, worldImage, worldImage, false, false, testMoveValid, &dynamicColInfoWI, NULL))
2011                                 {
2012                                         // First collision..
2013                                         if (!firstCollision || (firstCollision->getCollisionTime () > dynamicColInfoWI.getCollisionTime ()))
2014                                         {
2015                                                 firstCollision = &dynamicColInfoWI;
2016                                         }
2017                                 }
2018                         }
2019
2020                         // Checks
2021                         CVectorD d2=wI->getDeltaPosition();
2022                         nlassert ((d0==d1)&&(d0==d2));
2023
2024 //                      if (found)
2025 //                              nlstop;
2026
2027                         // Reaction
2028                         if (firstCollision)
2029                         {
2030                                 collisionTime = firstCollision->getCollisionTime ();
2031                                 reaction (*firstCollision);
2032                                 //nlassert (collisionTime != 1);
2033
2034                                 if (collisionTime == 1)
2035                                 {
2036                                         nlinfo("PACS: evalNCPrimitiveCollision() failure, collisionTime [%f] == 1", collisionTime);
2037                                         return false;
2038                                 }
2039                         }
2040                         else
2041                         {
2042                                 // Retriever mode ?
2043                                 if (_Retriever&&testMoveValid)
2044                                 {
2045                                         // Do move
2046                                         wI->doMove (*_Retriever, _SurfaceTemp, deltaTime, collisionTime, ((CMovePrimitive*)primitive)->getDontSnapToGround());
2047                                 }
2048                                 else
2049                                 {
2050                                         // Do move
2051                                         wI->doMove (_DeltaTime);
2052                                 }
2053                         }
2054
2055                         beginTime = collisionTime;
2056                 }
2057                 while (firstCollision);
2058         }
2059         else
2060                 return false;
2061
2062         return true;
2063 }
2064
2065
2066 } // NLPACS