Vegastrike 0.5.1 rc1  1.0
Original sources for Vegastrike Evolved
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
Opcode::SweepAndPrune Class Reference

#include <Opcode.h>

Public Member Functions

 SweepAndPrune ()
 
 ~SweepAndPrune ()
 
bool Init (udword nb_objects, const AABB **boxes)
 
bool UpdateObject (udword i, const AABB &box)
 
void GetPairs (Pairs &pairs) const
 
void GetPairs (PairCallback callback, void *user_data) const
 

Detailed Description

Definition at line 66 of file Opcode.h.

Constructor & Destructor Documentation

SweepAndPrune::SweepAndPrune ( )

Constructor.

Definition at line 391 of file OPC_SweepAndPrune.cpp.

392 {
393 }
SweepAndPrune::~SweepAndPrune ( )

Destructor.

Definition at line 400 of file OPC_SweepAndPrune.cpp.

401 {
402 }

Member Function Documentation

void SweepAndPrune::GetPairs ( Pairs &  pairs) const

Definition at line 404 of file OPC_SweepAndPrune.cpp.

References Opcode::SAP_PairData::DumpPairs().

405 {
406  mPairs.DumpPairs(pairs);
407 }
void SweepAndPrune::GetPairs ( PairCallback  callback,
void *  user_data 
) const

Definition at line 409 of file OPC_SweepAndPrune.cpp.

References Opcode::SAP_PairData::DumpPairs().

410 {
411  mPairs.DumpPairs(callback, user_data);
412 }
bool SweepAndPrune::Init ( udword  nb_objects,
const AABB **  boxes 
)

Definition at line 414 of file OPC_SweepAndPrune.cpp.

References Opcode::SAP_PairData::AddPair(), Opcode::AXES_XZY, Opcode::CompleteBoxPruning(), DELETEARRAY, Opcode::AABB::GetMax(), Opcode::AABB::GetMin(), Pairs::GetNbPairs(), Pairs::GetPair(), RadixSort::GetRanks(), Pair::id0, Pair::id1, Opcode::SAP_PairData::Init(), Intersect(), Opcode::SAP_EndPoint::IsMax(), Opcode::SAP_Box::Min, Opcode::SAP_EndPoint::Next, null, OPASSERT, Opcode::SAP_EndPoint::Previous, Opcode::SAP_EndPoint::SetData(), RadixSort::Sort(), and Opcode::SAP_EndPoint::Value.

415 {
416  // 1) Create sorted lists
417  mNbObjects = nb_objects;
418 
419  mBoxes = new SAP_Box[nb_objects];
420 // for(udword i=0;i<nb_objects;i++) mBoxes[i].Box = *boxes[i];
421 
422  float* Data = new float[nb_objects*2];
423 
424  for(udword Axis=0;Axis<3;Axis++)
425  {
426  mList[Axis] = new SAP_EndPoint[nb_objects*2];
427 
428  udword i;
429  for(i=0;i<nb_objects;i++)
430  {
431  Data[i*2+0] = boxes[i]->GetMin(Axis);
432  Data[i*2+1] = boxes[i]->GetMax(Axis);
433  }
434  RadixSort RS;
435  const udword* Sorted = RS.Sort(Data, nb_objects*2).GetRanks();
436 
437  SAP_EndPoint* PreviousEndPoint = null;
438 
439  for(i=0;i<nb_objects*2;i++)
440  {
441  udword SortedIndex = *Sorted++;
442  float SortedCoord = Data[SortedIndex];
443  udword BoxIndex = SortedIndex>>1;
444 
445  OPASSERT(BoxIndex<nb_objects);
446 
447  SAP_EndPoint* CurrentEndPoint = &mList[Axis][SortedIndex];
448  CurrentEndPoint->Value = SortedCoord;
449 // CurrentEndPoint->IsMax = SortedIndex&1; // ### could be implicit ?
450 // CurrentEndPoint->ID = BoxIndex; // ### could be implicit ?
451  CurrentEndPoint->SetData(BoxIndex, SortedIndex&1); // ### could be implicit ?
452  CurrentEndPoint->Previous = PreviousEndPoint;
453  CurrentEndPoint->Next = null;
454  if(PreviousEndPoint) PreviousEndPoint->Next = CurrentEndPoint;
455 
456  if(CurrentEndPoint->IsMax()) mBoxes[BoxIndex].Max[Axis] = CurrentEndPoint;
457  else mBoxes[BoxIndex].Min[Axis] = CurrentEndPoint;
458 
459  PreviousEndPoint = CurrentEndPoint;
460  }
461  }
462 
463  DELETEARRAY(Data);
464 
465  CheckListsIntegrity();
466 
467  // 2) Quickly find starting pairs
468 
469  mPairs.Init(nb_objects);
470 
471  {
472  Pairs P;
473  CompleteBoxPruning(nb_objects, boxes, P, Axes(AXES_XZY));
474  for(udword i=0;i<P.GetNbPairs();i++)
475  {
476  const Pair* PP = P.GetPair(i);
477 
478  udword id0 = PP->id0;
479  udword id1 = PP->id1;
480 
481  if(id0!=id1 && boxes[id0]->Intersect(*boxes[id1]))
482  {
483  mPairs.AddPair(id0, id1);
484  }
485  else OPASSERT(0);
486  }
487  }
488 
489  return true;
490 }
bool SweepAndPrune::UpdateObject ( udword  i,
const AABB &  box 
)

Definition at line 536 of file OPC_SweepAndPrune.cpp.

References Opcode::SAP_PairData::AddPair(), Opcode::SAP_EndPoint::GetBoxID(), Opcode::AABB::GetMax(), Opcode::AABB::GetMin(), Opcode::SAP_EndPoint::InsertAfter(), Opcode::SAP_EndPoint::InsertBefore(), Intersect(), Opcode::SAP_EndPoint::IsMax(), Opcode::SAP_Box::Max, Opcode::SAP_Box::Min, Opcode::SAP_EndPoint::Next, OPASSERT, Opcode::SAP_EndPoint::Previous, Opcode::SAP_PairData::RemovePair(), and Opcode::SAP_EndPoint::Value.

537 {
538  for(udword Axis=0;Axis<3;Axis++)
539  {
540 // udword Base = (udword)&mList[Axis][0];
541 
542  // Update min
543  {
544  SAP_EndPoint* const CurrentMin = mBoxes[i].Min[Axis];
545  OPASSERT(!CurrentMin->IsMax());
546 
547  const float Limit = box.GetMin(Axis);
548  if(Limit == CurrentMin->Value)
549  {
550  }
551  else if(Limit < CurrentMin->Value)
552  {
553  CurrentMin->Value = Limit;
554 
555  // Min is moving left:
556  SAP_EndPoint* NewPos = CurrentMin;
557  OPASSERT(NewPos);
558 
559  SAP_EndPoint* tmp;
560  while((tmp = NewPos->Previous) && tmp->Value > Limit)
561  {
562  NewPos = tmp;
563 
564  if(NewPos->IsMax())
565  {
566  // Our min passed a max => start overlap
567  //udword SortedIndex = (udword(CurrentMin) - Base)/sizeof(NS_EndPoint);
568  const udword id0 = CurrentMin->GetBoxID();
569  const udword id1 = NewPos->GetBoxID();
570 
571  if(id0!=id1 && Intersect(box, mBoxes[id1])) mPairs.AddPair(id0, id1);
572  }
573  }
574 
575  CurrentMin->InsertBefore(NewPos);
576  }
577  else// if(Limit > CurrentMin->Value)
578  {
579  CurrentMin->Value = Limit;
580 
581  // Min is moving right:
582  SAP_EndPoint* NewPos = CurrentMin;
583  OPASSERT(NewPos);
584 
585  SAP_EndPoint* tmp;
586  while((tmp = NewPos->Next) && tmp->Value < Limit)
587  {
588  NewPos = tmp;
589 
590  if(NewPos->IsMax())
591  {
592  // Our min passed a max => stop overlap
593  const udword id0 = CurrentMin->GetBoxID();
594  const udword id1 = NewPos->GetBoxID();
595 
596  if(id0!=id1) mPairs.RemovePair(id0, id1);
597  }
598  }
599 
600  CurrentMin->InsertAfter(NewPos);
601  }
602  }
603 
604  // Update max
605  {
606  SAP_EndPoint* const CurrentMax = mBoxes[i].Max[Axis];
607  OPASSERT(CurrentMax->IsMax());
608 
609  const float Limit = box.GetMax(Axis);
610  if(Limit == CurrentMax->Value)
611  {
612  }
613  else if(Limit > CurrentMax->Value)
614  {
615  CurrentMax->Value = Limit;
616 
617  // Max is moving right:
618  SAP_EndPoint* NewPos = CurrentMax;
619  OPASSERT(NewPos);
620 
621  SAP_EndPoint* tmp;
622  while((tmp = NewPos->Next) && tmp->Value < Limit)
623  {
624  NewPos = tmp;
625 
626  if(!NewPos->IsMax())
627  {
628  // Our max passed a min => start overlap
629  const udword id0 = CurrentMax->GetBoxID();
630  const udword id1 = NewPos->GetBoxID();
631 
632  if(id0!=id1 && Intersect(box, mBoxes[id1])) mPairs.AddPair(id0, id1);
633  }
634  }
635 
636  CurrentMax->InsertAfter(NewPos);
637  }
638  else// if(Limit < CurrentMax->Value)
639  {
640  CurrentMax->Value = Limit;
641 
642  // Max is moving left:
643  SAP_EndPoint* NewPos = CurrentMax;
644  OPASSERT(NewPos);
645 
646  SAP_EndPoint* tmp;
647  while((tmp = NewPos->Previous) && tmp->Value > Limit)
648  {
649  NewPos = tmp;
650 
651  if(!NewPos->IsMax())
652  {
653  // Our max passed a min => stop overlap
654  const udword id0 = CurrentMax->GetBoxID();
655  const udword id1 = NewPos->GetBoxID();
656 
657  if(id0!=id1) mPairs.RemovePair(id0, id1);
658  }
659  }
660 
661  CurrentMax->InsertBefore(NewPos);
662  }
663  }
664  }
665 
666  return true;
667 }
The documentation for this class was generated from the following files: