src/engine/eGrid.cpp

Go to the documentation of this file.
00001 /*
00002 *************************************************************************
00003 
00004 ArmageTron -- Just another Tron Lightcycle Game in 3D.
00005 Copyright (C) 2000  Manuel Moos (manuel@moosnet.de)
00006 
00007 **************************************************************************
00008 
00009 This program is free software; you can redistribute it and/or
00010 modify it under the terms of the GNU General Public License
00011 as published by the Free Software Foundation; either version 2
00012 of the License, or (at your option) any later version.
00013 
00014 This program is distributed in the hope that it will be useful,
00015 but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017 GNU General Public License for more details.
00018 
00019 You should have received a copy of the GNU General Public License
00020 along with this program; if not, write to the Free Software
00021 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00022   
00023 ***************************************************************************
00024 
00025 */
00026 
00027 #ifdef _MSC_VER
00028 // disable long debug symbol warning
00029 #pragma warning ( disable: 4786 )
00030 #endif
00031 
00032 #include "eGrid.h"
00033 #include "eTess2.h"
00034 
00035 #include "rTexture.h"
00036 #include "tEventQueue.h"
00037 #include "eTimer.h"
00038 #include "eWall.h"
00039 #include "eGameObject.h"
00040 #include "eCamera.h"
00041 
00042 #include "tMath.h"
00043 #include "nConfig.h" 
00044 
00045 #include "tRecorder.h"
00046 
00047 #include <vector>
00048 #include <set>
00049 
00050 #define SMALL_FLOAT 1E-30
00051 const REAL se_maxGridSize = 1E+15;      // this gives us way more space than OpenGL allows us to render
00052 
00053 // #define EPS 1E-2
00054 
00055 int se_debugExt=0;
00056 
00057 // counts how many edges we should attempt to simplify
00058 static int se_simplifyEdges = 0;
00059 
00060 // after one edge has been successfully simplified, simplify that many more,
00061 // it seems to pay
00062 static const int se_simplifyEdgesSuccess = 20;
00063 
00064 // after one edge has been inserted, try to simplify that many old ones
00065 static const int se_simplifyEdgesNew = 2;
00066 
00067 tDEFINE_REFOBJ( ePoint )
00068 tDEFINE_REFOBJ( eHalfEdge )
00069 tDEFINE_REFOBJ( eFace )
00070 
00071 
00072 REAL se_EstimatedRangeOfMult( const eCoord &a,const eCoord &b )
00073 {
00074     static eCoord turn(0,1);
00075     return fabs( b*a ) + fabs( b*( a.Turn( turn ) ) );
00076 }
00077 
00078 REAL st_GetDifference( const eCoord &a,const eCoord &b )
00079 {
00080     return (a-b).NormSquared();
00081 }
00082 
00083 eCoord    eTempEdge::Vec()         const{return halfEdges[0]->Vec();}
00084 eCoord&   eTempEdge::Coord(int i)  const{return *halfEdges[i]->Point();}
00085 ePoint    *eTempEdge::Point(int i) const{return halfEdges[i]->Point();}
00086 eFace     *eTempEdge::Face(int i)  const{return halfEdges[i]->Face();}
00087 eHalfEdge *eTempEdge::Edge(int i)  const{return halfEdges[i];}
00088 eWall     *eTempEdge::Wall()       const{return halfEdges[0]->GetWall();}
00089 
00090 void       eTempEdge::SetWall( eWall* W )    const
00091 {
00092     halfEdges[0]->ClearWall();
00093     halfEdges[0]->SetWall( W );
00094 }
00095 
00096 short se_bugRip=false;
00097 static nSettingItem<short> se_bugRipNet( "BUG_RIP", se_bugRip );
00098 
00099 inline void eHalfEdge::SetWall(eWall *w){
00100     if (!w)
00101         return;
00102 
00103     // emulate rip bug
00104     if ( se_bugRip )
00105     {
00106         // delete old wall
00107         if ( other && other->GetWall() && other->GetWall()->Splittable() )
00108             other->eWallHolder::SetWall( 0 );
00109 
00110         // set new wall
00111         eWallHolder::SetWall( w );
00112 
00113         w->CalcLen();
00114 
00115         return;
00116     }
00117 
00118     // get other wall
00119     eWall* otherWall = 0;
00120     if ( other )
00121         otherWall = other->GetWall();
00122 
00123     // ask for permission
00124     if ( otherWall && !w->RunsParallelActive( otherWall ) )
00125         return;
00126 
00127     eWall* thisWall = GetWall();
00128     if ( thisWall )
00129     {
00130         // ask this wall for permission
00131         bool allowed = w->RunsParallelActive( thisWall );
00132         if ( otherWall )
00133         {
00134             // inform wall, but don't insert it ( since it is impossible )
00135             w->RunsParallelActive( otherWall );
00136             // st_Breakpoint();
00137         }
00138         else if ( allowed && other )
00139         {
00140             // simply flip the wall and attach it to the other edge :-)
00141             w->Flip();
00142             other->eWallHolder::SetWall(w);
00143             //            return;
00144         }
00145     }
00146     else
00147     {
00148         eWallHolder::SetWall( w );
00149     }
00150 
00151     w->CalcLen();
00152 }
00153 
00154 void eHalfEdge::ClearWall( void )
00155 {
00156     eWallHolder::SetWall( NULL );
00157 }
00158 
00159 // destructor unlinking all pointers
00160 eHalfEdge::~eHalfEdge()
00161 {
00162     Unlink();
00163     RemoveFromHeap();
00164 }
00165 
00166 inline void eHalfEdge::Unlink()
00167 {
00168     if (point && this == point->edge)
00169     {
00170         if (prev && prev->other && prev->other)
00171             point->edge = prev->other;
00172         else if (other && other->next)
00173             point->edge = other->next;
00174         else
00175             point->edge = 0;
00176     }
00177     if (face && this == face->edge)
00178     {
00179         if (next)
00180             face->edge = next;
00181         if (prev)
00182             face->edge = prev;
00183     }
00184 
00185     if (next)
00186         next->prev = NULL;
00187     if (prev)
00188         prev->next = NULL;
00189     if (other)
00190         other->other = NULL;
00191 
00192     point   = NULL;
00193     face    = NULL;
00194     prev    = NULL;
00195     next    = NULL;
00196     other   = NULL;
00197 }
00198 
00199 
00200 
00201 // ********************************************
00202 
00203 // consistency checks:
00204 
00205 void eGrid::Check() const{
00206     //    return;
00207     if ( a )
00208     {
00209         tASSERT( a->Point() == B );
00210         tASSERT( a->other->Point() == C );
00211         tASSERT( b->Point() == C );
00212         tASSERT( b->other->Point() == A );
00213         tASSERT( c->Point() == A );
00214         tASSERT( c->other->Point() == B );
00215     }
00216 
00217 #ifdef DEBUG_EXPENSIVE
00218     if (!doCheck)
00219         return;
00220 
00221     int i;
00222     for (i = points.Len()-1; i>=0; i--)
00223         points(i)->Check();
00224 
00225     for (i = faces.Len()-1; i>=0; i--)
00226         faces(i)->Check();
00227 
00228     for (i = edges.Len()-1; i>=0; i--)
00229         edges(i)->Check();
00230 #endif
00231 }
00232 
00233 
00234 // **************************
00235 //          eDual
00236 // **************************
00237 
00238 eDual::~eDual()  // destructor
00239 {
00240     tASSERT(!edge);
00241 }
00242 
00243 bool eDual::Check(int type)
00244 {
00245     if (type)
00246     {
00247         tASSERT(!edge ||  this == static_cast<eDual*>(edge->face));
00248     }
00249     else
00250     {
00251         tASSERT(!edge ||  this == static_cast<eDual*>(edge->point));
00252     }
00253 
00254     tASSERT( ID < 0 || !edge || edge->ID>=0);
00255 
00256     return true;
00257 }
00258 // basic consistency check; type is 0 for points and 1 for faces.
00259 inline void eDual::Unlink(int type)
00260 {
00261 
00262 }
00263 // removes itself from the edges' pointers. type is 0 for points and 1 for edges.
00264 
00265 
00266 
00267 
00268 // **************************
00269 //          ePoint
00270 // **************************
00271 
00272 void ePoint::Print(std::ostream &s) const
00273 {
00274     s << "(" << x << ", " << y << ")";
00275 }
00276 
00277 // replaces all known pointers to *this with pointers to *P.
00278 void ePoint::Replace(ePoint *P)
00279 {
00280     tControlledPTR< ePoint > keep( this );
00281 
00282     //  if (!(*this==*P))
00283     //    tERR_WARN("Unequal points are going to get exchaned!");
00284 
00285     eHalfEdge *run = edge;
00286     const eHalfEdge *stop = run;
00287 
00288     *static_cast<eCoord *>(P) = *this;
00289 
00290     do
00291     {
00292         tASSERT(run && run->Point() == this);
00293         run->SetPoint(P);
00294 
00295         run = run->other->next;
00296 
00297     }
00298     while (stop != run);
00299 
00300     edge = NULL;
00301 }
00302 
00303 void ePoint::Unlink()
00304 {
00305     if (!edge)
00306         return;
00307 
00308     eHalfEdge *run = edge;
00309     const eHalfEdge *stop = run;
00310 
00311     do
00312     {
00313         tASSERT(run && run->Point() == this &&
00314                 (!run->next || !run->next->next || run == run->next->next->next)) ;
00315         run = run->next;
00316         if (run)
00317             run= run->next;
00318         if (run)
00319             run = run->other;
00320     }
00321     while (run && stop != run);
00322 
00323     edge = NULL;
00324 }
00325 
00326 // **************************
00327 //          eFace
00328 // **************************
00329 
00330 // database of eFace replacements made during grid restructuring
00331 typedef std::vector< tJUST_CONTROLLED_PTR<eFace> > eReplacementStorageBase;
00332 class eReplacementStorage : public eReplacementStorageBase
00333 {
00334 };
00335 
00336 void se_LinkFaces( tControlledPTR< eFace >& old, eFace* replacement )
00337 {
00338     tASSERT( old != replacement );
00339 
00340     // we only need to store an eFace if it is referenced by something different than
00341     // the pointer we got it by
00342     if ( old->GetRefcount() > 1 )
00343     {
00344         eReplacementStorage& storage = old->GetReplacementStorage();
00345         storage.push_back( replacement );
00346     }
00347 }
00348 
00349 typedef std::pair< eFace*, REAL > eFaceScorePair;
00350 typedef std::set< const eFace* > eFaceVisitedSet;
00351 
00352 struct eFaceReplacementArgument
00353 {
00354     eCoord coord, direction, lastDirection;
00355     eFaceVisitedSet visited;
00356 };
00357 
00358 eFaceScorePair se_FindBestReplacement( const eFace *old, eFaceReplacementArgument& arg )
00359 {
00360     // return invalid return if the face was already visited
00361     if ( arg.visited.find( old ) != arg.visited.end() )
00362         return eFaceScorePair( 0, -se_maxGridSize );
00363 
00364     // register face as visited
00365     arg.visited.insert( old );
00366 
00367     // find entry in replacement map
00368 
00369     {
00370         // real work starts here
00371         // get the vector of replacements
00372         const eReplacementStorage& storage = old->GetReplacementStorage();
00373 
00374         // iterate it
00375 
00376         // the currently best face/insideness pair
00377         std::pair< eFace*, REAL > best( 0, -100000 );
00378         for( eReplacementStorage::const_iterator i = storage.begin(); i != storage.end(); ++i )
00379         {
00380             // the current face/insideness pair
00381             eFaceScorePair current; // ( 0, -100000 );
00382 
00383             // the current face
00384             eFace* face = *i;
00385 
00386             // is it inside the grid?
00387             if ( face->IsInGrid() )
00388             {
00389                 // enter it directly
00390                 current.first = face;
00391                 current.second = face->Insideness( arg.coord, arg.direction, arg.lastDirection );
00392             }
00393             else
00394             {
00395                 // no, we have to look for a replacement recursively
00396                 current = se_FindBestReplacement( face, arg );
00397             }
00398 
00399             if ( current.second > best.second && current.first )
00400                 best = current;
00401         }
00402 
00403         return best;
00404     }
00405 }
00406 
00407 eReplacementStorage& eFace::GetReplacementStorage() const
00408 {
00409     if ( !replacementStorage )
00410         replacementStorage = tNEW( eReplacementStorage );
00411 
00412     return *replacementStorage;
00413 }
00414 
00415 eFace* eFace::FindReplacement( const eCoord& coord, const eCoord& direction, const eCoord& lastDirection ) const
00416 {
00417     // check if we don't need an replacement
00418     tASSERT( !this->IsInGrid() );
00419 
00420     // set of already visited faces
00421     eFaceReplacementArgument arg;
00422     arg.coord = coord;
00423     arg.direction = direction;
00424     arg.lastDirection = lastDirection;
00425 
00426     // delegate search to recursive function
00427     return se_FindBestReplacement( this, arg ).first;
00428 }
00429 
00430 eFace* eFace::FindReplacement( const eCoord& coord, const eCoord& direction ) const
00431 {
00432     // check if we don't need an replacement
00433     tASSERT( !this->IsInGrid() );
00434 
00435     // set of already visited faces
00436     eFaceReplacementArgument arg;
00437     arg.coord = coord;
00438     arg.direction = direction;
00439 
00440     // delegate search to recursive function
00441     return se_FindBestReplacement( this, arg ).first;
00442 }
00443 
00444 eFace* eFace::FindReplacement( const eCoord& coord ) const
00445 {
00446     // check if we don't need an replacement
00447     tASSERT( !this->IsInGrid() );
00448 
00449     // set of already visited faces
00450     eFaceReplacementArgument arg;
00451     arg.coord = coord;
00452 
00453     // delegate search to recursive function
00454     return se_FindBestReplacement( this, arg ).first;
00455 }
00456 
00457 eFace::~eFace()
00458 {
00459     Unlink();
00460     //  se_EraseFace( this );
00461 
00462     delete replacementStorage;
00463 }
00464 
00465 eFace::eFace (eHalfEdge *e1,eHalfEdge *e2,eHalfEdge *e3 )
00466         :replacementStorage( 0 )
00467 {
00468     Create( e1, e2, e3 );
00469 }
00470 
00471 eFace::eFace (eHalfEdge *e1,eHalfEdge *e2,eHalfEdge *e3, tControlledPTR< eFace >& old )
00472         :replacementStorage( 0 )
00473 {
00474     Create( e1, e2, e3 );
00475     se_LinkFaces( old, this );
00476 }
00477 
00478 eFace::eFace (eHalfEdge *e1,eHalfEdge *e2,eHalfEdge *e3, tControlledPTR< eFace >& old1, tControlledPTR< eFace >& old2 )
00479         :replacementStorage( 0 )
00480 {
00481     Create( e1, e2, e3 );
00482     se_LinkFaces( old1, this );
00483     se_LinkFaces( old2, this );
00484 }
00485 
00486 void eFace::Create (eHalfEdge *e1,eHalfEdge *e2,eHalfEdge *e3)
00487 {
00488 #ifdef DEBUG 
00489     tASSERT( edge == 0 );
00490 
00491     tASSERT(e1->other);
00492     tASSERT(e2->other);
00493     tASSERT(e3->other);
00494 
00495     tASSERT(e1->Point() == e3->other->Point());
00496     tASSERT(e2->Point() == e1->other->Point());
00497     tASSERT(e3->Point() == e2->other->Point());
00498 
00499     //  tASSERT(*e1->Point() != *e2->Point());
00500     //  tASSERT(*e3->Point() != *e2->Point());
00501     //  tASSERT(*e1->Point() != *e3->Point());
00502 
00503     tASSERT((*e1->Point() - *e2->Point()).NormSquared() < se_maxGridSize*100);
00504     tASSERT((*e3->Point() - *e2->Point()).NormSquared() < se_maxGridSize*100);
00505     tASSERT((*e1->Point() - *e3->Point()).NormSquared() < se_maxGridSize*100);
00506 #endif
00507 
00508     nextProcessed = NULL;
00509 
00510     e1->SetFace(this);
00511     e2->SetFace(this);
00512     e3->SetFace(this);
00513 
00514     e1->next = e2;
00515     e2->next = e3;
00516     e3->next = e1;
00517     e1->prev = e3;
00518     e2->prev = e1;
00519     e3->prev = e2;
00520 
00521     e1->Point()->edge = e1;
00522     e2->Point()->edge = e2;
00523     e3->Point()->edge = e3;
00524 
00525     edge = e1;
00526 
00527 #ifdef DEBUG
00528     REAL area = -(*e1->Point() - *e2->Point()) * (*e1->Point() - *e3->Point());
00529     if( area <= -EPS )
00530     {
00531         con << "Face " << *this << " has wrong orientation (area: " << area << ").\n";
00532     }
00533 #endif
00534 }
00535 
00536 void eFace::Unlink(){
00537     if (edge)
00538     {
00539         eHalfEdge *run = edge;
00540         const eHalfEdge *stop = run;
00541 
00542         do
00543         {
00544             tASSERT(run->Face() == this);
00545             run->SetFace(NULL);
00546 
00547             run = run->next;
00548         }
00549         while (stop != run);
00550 
00551         edge = NULL;
00552     }
00553 }
00554 
00555 // ckeck if the given point lies inside this face; return value positive if it is inside and negative if outside
00556 REAL eFace::Insideness(const eCoord& pos, const eCoord& direction, const eCoord& lastDirection ) const
00557 {
00558     // TODO: bounding box check
00559 
00560     eCoord min, max;
00561 
00562     eHalfEdge *run = edge;
00563     if (!run)
00564         return -1000000000;
00565 
00566     REAL ret = 1000000000;
00567 
00568     eCoord *last_p = run->Point();
00569     run = run->next;
00570     const eHalfEdge *stop = run;
00571 
00572     do
00573     {
00574         tASSERT(run && run->Face() == this);
00575         eCoord *p = run->Point();
00576         eCoord ed=*last_p - *p;
00577         eCoord cc= pos - *p;
00578 
00579         REAL val = ed*cc;
00580         // REAL tol = 10 * EPS/(ed.Norm() + EPS*1000);
00581         REAL tol = 10 * EPS;
00582         REAL retDir = direction*ed;
00583         REAL retLastDir = lastDirection*ed;
00584         val += tol*(retDir + tol*retLastDir);
00585         if ( val < ret )
00586         {
00587             ret = val;
00588         }
00589 
00590         last_p = p;
00591         run = run->next;
00592     }
00593     while (run && stop != run);
00594 
00595     return ret;
00596 }
00597 
00598 REAL eFace::Insideness(const eCoord& c, const eCoord& direction ) const
00599 {
00600     return Insideness( c, direction, eCoord() );
00601 }
00602 
00603 REAL eFace::Insideness(const eCoord& c ) const
00604 {
00605     return Insideness( c, eCoord(), eCoord() );
00606 }
00607 
00608 // ckeck if the given point lies inside this face (edges included)
00609 bool eFace::IsInside(const eCoord &c) const
00610 {
00611     // flags storing whether there is a point of the triangle with bigger/smaller coordinates
00612     // than the test coords
00613     bool xLower=false, xHigher=false, yLower=false, yHigher=false;
00614 
00615     eHalfEdge *run = edge;
00616     if (!run)
00617         return false;
00618 
00619     eCoord *last_p = run->Point();
00620     run = run->next;
00621     const eHalfEdge *stop = run;
00622 
00623     do
00624     {
00625         tASSERT(run && run->Face() == this);
00626         eCoord *p = run->Point();
00627         eCoord ed=*last_p - *p;
00628         eCoord cc= c - *p;
00629 
00630         if ( p->x <= c.x + EPS )
00631             xLower = true;
00632         if ( p->x >= c.x - EPS )
00633             xHigher = true;
00634         if ( p->y <= c.y + EPS )
00635             yLower = true;
00636         if ( p->y >= c.y - EPS )
00637             yHigher = true;
00638 
00639         if (ed*cc<-EPS)
00640             return false;
00641 
00642         last_p = p;
00643         run = run->next;
00644     }
00645     while (run && stop != run);
00646 
00647     // test if the point is in the bounding rectangle of the triangle
00648     return xLower && xHigher && yLower && yHigher;
00649 }
00650 
00651 void eCoord::Print(std::ostream &s)const{ s << "(" << x << "," << y << ")"; }
00652 void eHalfEdge::Print(std::ostream &s)const{ s << "[" << *Point() << "->" << *other->Point() << "]"; }
00653 void eFace::Print(std::ostream &s)const{ s << "[" << *edge->Point() << "->" << *edge->next->Point() << "->" << *edge->next->next->Point() << "]"; }
00654 void eCoord::Read(std::istream &s)
00655 {
00656     char c;
00657     s >> c;
00658     tASSERT( c == '(' );
00659     s >> x;
00660     s >> c;
00661     tASSERT( c == ',' );
00662     s >> y;
00663     s >> c;
00664     tASSERT( c == ')' );
00665 }
00666 
00667 
00668 // **************************
00669 //          eGrid
00670 // **************************
00671 
00672 /*
00673  * Return the winding number closest to direction dir
00674  */
00675 int eGrid::DirectionWinding(const eCoord&dir)
00676 {
00677     return axis.NearestWinding(dir);
00678 }
00679 
00680 /*
00681  * Return the direction associated with a winding number
00682  */
00683 eCoord eGrid::GetDirection(int winding)
00684 {
00685     return axis.GetDirection(winding);
00686 }
00687 
00688 /*
00689  * Define the number of winding to be used on this grid
00690  */
00691 void eGrid::SetWinding(int number)
00692 {
00693     axis.Init(number);
00694 }
00695 
00696 /*
00697  * Define the number of winding and their values.
00698  * When the normalize flag is set, the values are normalized.
00699  */
00700 void eGrid::SetWinding(int number, eCoord directions[], bool normalise)
00701 {
00702     axis.Init(number, directions, normalise);
00703 }
00704 
00705 /*
00706  * change/turn currentWinding by 'direction' steps
00707  */
00708 void eGrid::Turn(int &currentWinding, int direction)
00709 {
00710     axis.Turn(currentWinding, direction);
00711 }
00712 
00713 
00714 static eHalfEdge *leakEdge =NULL;
00715 static ePoint    *leakPoint=NULL;
00716 
00717 static int se_drawLineTimeout = 10000;
00718 static tSettingItem<int> se_drawLineTimeoutConf("DRAWLINE_TIMEOUT", se_drawLineTimeout);
00719 
00720 ePoint * eGrid::DrawLine(ePoint *start, const eCoord &end, eWall *w, bool change_grid){
00721     // for every edge we add, allow to simplify
00722     se_simplifyEdges += se_simplifyEdgesNew;
00723 
00724     // prepare a teporary edge so we always know what the wall we are placing looks like
00725     tStackObject< eTempEdge > toBePlaced( *start, end, w );
00726     //tJUST_CONTROLLED_PTR< eWall > wal( w );
00727 
00728     // sanity check
00729     if ( !finite( end.x ) || !finite( end.y ) )
00730         return start;
00731 
00732     Range(end.NormSquared());
00733     int restart=1;
00734     //  eEdge *todo=tNEW(eEdge) (start,end,wal);
00735 
00736 
00737     // now the loop: go from source to destination,
00738     // "rotate" the edges we cross out of our way (if possible)
00739     // or cut them in half.
00740 
00741     tJUST_CONTROLLED_PTR<eHalfEdge> currentEdge  = NULL;
00742     // the edge we are currently considering.
00743     // the line we are to draw starts at currentEdge->Point()
00744     // and goes into currentEdge->Face().
00745 
00746 
00747     REAL left_test,right_test;
00748     int exactly_onLeft=0;
00749 
00750     tASSERT(start->edge);
00751 
00752 #ifdef DEBUG
00753     bool foundCurrentEdge;
00754     static const int laststarts_max = 10;
00755     ePoint *laststarts[laststarts_max];
00756 #endif
00757 
00758     eCoord dir=eCoord(1,1); // the direction we are going
00759 
00760     int timeout = se_drawLineTimeout;
00761 
00762     // distance to end to know when we are going backwards
00763     REAL distToEnd = ( *start - end ).NormSquared();
00764     ePoint * lastStart = start;
00765 
00766     bool goon=1;
00767     while (goon && dir.NormSquared()>0){
00768 #ifdef DEBUG
00769         static int count = 0;
00770         count++;
00771         //    if (count == 40)
00772         //      st_Breakpoint();
00773 #endif
00774 
00775         dir=end-*start; // the direction we are going
00776 
00777         // check if we got closer to the end, if not, accelerate timeout and set breakpoint
00778         REAL newDistToEnd = dir.NormSquared();
00779         // std::cout << distToEnd << ", " << newDistToEnd << "\n";
00780         if ( newDistToEnd > distToEnd && start != lastStart )
00781         {
00782             //st_Breakpoint();
00783             timeout -= 100;
00784         }
00785         distToEnd = newDistToEnd;
00786         lastStart = start;
00787 
00788 #ifdef DEBUG
00789         for (int i = laststarts_max-1; i>=1; i--)
00790             laststarts[i] = laststarts[i-1];
00791 
00792         laststarts[0] = start;
00793 
00794         if (timeout < 10)
00795             st_Breakpoint();
00796 #endif
00797 
00798         if (timeout-- < 0)
00799         {
00800             requestCleanup = true;
00801             return start;  // give up.
00802         }
00803 
00804 #ifdef DEBUG
00805         Check();
00806 #endif
00807 
00808         // first, we need to find the first eFace:
00809         //    int i;
00810 
00811 #ifdef DEBUG
00812         //    if (doCheck && start->id == 4792)
00813         //      st_Breakpoint();
00814 #endif
00815 
00816         tASSERT(restart || currentEdge);
00817 
00818         if (restart){
00819             exactly_onLeft = -1;
00820 
00821             eHalfEdge *run  = start->edge;
00822             tASSERT(run);
00823             eHalfEdge *stop = run;
00824 
00825             eCoord lvec = run->Vec();
00826             eCoord rvec;
00827             left_test = lvec * dir;
00828 
00829             eHalfEdge *best = NULL;
00830             REAL best_score = -100;
00831 
00832             currentEdge = NULL;
00833 
00834             while (run)
00835             {
00836                 eHalfEdge *next = run->next->next;
00837                 tASSERT(next->next = run);
00838                 next = next->other;
00839 
00840                 tASSERT(next->Point() == start);
00841 
00842                 right_test = left_test;
00843                 rvec = lvec;
00844                 lvec = next->Vec();
00845                 left_test = lvec * dir;
00846 
00847                 if (right_test <= 0 && left_test >= 0)
00848                 {
00849                     bool good = rvec * lvec < 0 && right_test < 0;
00850                     if (good)
00851                         next = NULL;
00852 
00853                     if (good || !currentEdge)
00854                     {
00855                         currentEdge = run;
00856 
00857                         // are dir and lvec exactly on one line?
00858                         exactly_onLeft=(left_test<=EPS * EPS * se_EstimatedRangeOfMult(lvec,dir));
00859                     }
00860                 }
00861 
00862                 REAL score = right_test * left_test;
00863                 if (right_test < 0 && left_test < 0)
00864                     score *= -1;     // here, - * - still is -.....
00865 
00866                 if (!best || score > best_score  && rvec * lvec < 0
00867                    )
00868                     best = run;
00869 
00870                 run = next;
00871                 if (run == stop)
00872                     run = NULL;
00873             }
00874 
00875 #ifdef DEBUG
00876             foundCurrentEdge = currentEdge;
00877             //      tASSERT(run || currentEdge);
00878 #endif
00879 
00880 
00881             if (!currentEdge && best)
00882             {
00883                 if (restart >= 3)
00884                 {
00885                     requestCleanup = true;
00886                     // give up.
00887                     // st_Breakpoint();
00888                     return start;
00889                 }
00890 
00891                 start = Insert(*start, best->Face());
00892                 restart ++;
00893                 continue;
00894 
00895                 currentEdge = best;
00896             }
00897 
00898             if (!currentEdge)
00899                 tERR_ERROR_INT("Point " << *start << " does not have a eFace in direction "
00900                                << dir << "!");
00901             // I know this bug happens a lot more often than"
00902             //  " I'd like to. Don't send a bug report!");
00903 
00904             restart=0;
00905         }
00906 
00907         if (start != currentEdge->Point())
00908             tERR_ERROR_INT("currentEdge not correct!");
00909 
00910         eHalfEdge *rightFromCurrent = currentEdge->next;
00911         eHalfEdge *leftFromCurrent  = rightFromCurrent->next;
00912         tASSERT (currentEdge == leftFromCurrent->next);
00913         // are we finished?
00914 
00915         if (exactly_onLeft<0)
00916         {
00917             eCoord lvec = leftFromCurrent->Vec();
00918             exactly_onLeft =  dir * lvec < EPS * EPS * se_EstimatedRangeOfMult(lvec, dir);
00919         }
00920 
00921         eCoord left_point_to_dest = end - *(leftFromCurrent->Point());
00922         eCoord lvec               = rightFromCurrent->Vec();
00923 
00924         REAL test = lvec * left_point_to_dest;
00925         if(test<0){
00926             // endpoint lies within current eFace; cut it into three and be finnished.
00927 
00928             // XXX have to check that we didnt start from a edge that jumps
00929             // to another field. If thats the case, then recall drawLine on the
00930             // other field
00931             goon=0;
00932 
00933             /*
00934               Should this figure get distorted, align the :
00935 
00936               :   C        a        B
00937               :   #################
00938               :   #\           _/#
00939               :   # \ cc   bb_/ #
00940               :   #  \     _/  #
00941               :   #   \  _/  ##
00942               : b #   D\/   #
00943               :   #    /  ##  c
00944               :   # aa/  #
00945               :   #  / ##
00946               :   # / #
00947               :   #/##
00948               :   ##
00949               :   A
00950 
00951 
00952             */
00953 
00954             ePoint *A=currentEdge->Point();
00955 
00956             if ((*A) == end){
00957 #ifdef DEBUG
00958                 Check();
00959 #endif
00960                 return A;
00961             }
00962             else{
00963                 eHalfEdge* a=rightFromCurrent;
00964                 eHalfEdge* b=leftFromCurrent;
00965                 eHalfEdge* c=currentEdge;
00966 
00967                 ePoint*    B=a->Point();
00968                 ePoint*    C=b->Point();
00969 
00970                 if ((*B) == end)
00971                 {
00972                     c->SetWall(toBePlaced.Wall());
00973                     return B;
00974                 }
00975 
00976                 if ((*C) == end)
00977                 {
00978                     tASSERT( b->other );
00979                     b->other->SetWall(toBePlaced.Wall());
00980                     return C;
00981                 }
00982 
00983                 if(!exactly_onLeft)
00984                 {
00985                     ePoint*    D=tNEW(ePoint(end));
00986 #ifdef DEBUG
00987                     Check();
00988 #endif
00989                     tControlledPTR< eFace > oldFace = ZombifyFace(a->Face());
00990 
00991                     // no problem: D really lies within current eFace.
00992                     // just split it in three parts:
00993 
00994                     eHalfEdge *aa = tNEW(eHalfEdge) (A, D);
00995                     eHalfEdge *bb = tNEW(eHalfEdge) (B, D);
00996                     eHalfEdge *cc = tNEW(eHalfEdge) (C, D);
00997 
00998                     //    aa->SetOther(   tNEW(eHalfEdge) (D));
00999                     //      bb->SetOther(   tNEW(eHalfEdge) (D));
01000                     //    cc->SetOther(   tNEW(eHalfEdge) (D));
01001 
01002                     AddFaceAll(tNEW(eFace) (b,aa,cc->other, oldFace ));
01003                     AddFaceAll(tNEW(eFace) (bb,aa->other,c, oldFace ));
01004                     AddFaceAll(tNEW(eFace) (bb->other,a,cc, oldFace ));
01005 
01006                     aa->SetWall(toBePlaced.Wall());
01007 
01008 #ifdef DEBUG
01009                     Check();
01010 #endif
01011                     return D;
01012                 }
01013                 else // exactly_onLeft
01014                 {
01015                     /*
01016                       Should this figure get distorted, align the ":"
01017 
01018                       Bad luck, D lies on eEdge b. We are going to need
01019                       the other triangle touching b.
01020 
01021 
01022                       :          C
01023                       :          #
01024                       :         ####
01025                       :        # #  ##
01026                       :       #  #    ##
01027                       :  e2  #   #      ##
01028                       :     #    #        ##  a
01029                       :    #   D X          ##
01030                       : E #      #            ##
01031                       :   #      # b            ##
01032                       :    #     #                ## B
01033                       :     #    #              ##
01034                       :     #    #            ##
01035                       :      #   #          ##
01036                       :  e1   #  #        ##
01037                       :       #  #      ##   c
01038                       :        # #    ##
01039                       :         ##  ##
01040                       :         ####
01041                       :          #
01042                       :          A
01043 
01044                       Make four new faces around D. 4 new half 
01045                       segments DA, DB, DC and DE are created.
01046                       :          C
01047                       :          #
01048                       :         #|##
01049                       :        # |  ##
01050                       :       #  | DC ##
01051                       :  e2  #   |      ##
01052                       :     #    | D      ##  a
01053                       :    #  ___X____      ##
01054                       : E #__/   |    \___    ##
01055                       :   #  DE  |     DB \___  ##
01056                       :    #     |            \___## B
01057                       :     #    | DA           ##
01058                       :     #    |            ##
01059                       :      #   |          ##
01060                       :  e1   #  |        ##
01061                       :       #  |      ##   c
01062                       :        # |    ##
01063                       :         #|  ##
01064                       :         #|##
01065                       :          #
01066                       :          A
01067 
01068                     */
01069 
01070                     tASSERT(b->other);
01071 
01072                     // eFace *G=b->other->face;
01073 
01074                     // tASSERT(G);
01075 
01076                     eHalfEdge *e1=b->other->next;
01077                     eHalfEdge *e2=e1->next;
01078                     tASSERT(e2);
01079                     ePoint *E=e2->point;
01080                     tASSERT(E);
01081                     // easy: edge is just right
01082                     if (*E == end)
01083                     {
01084                         e2->other->SetWall(toBePlaced.Wall());
01085                         return E;
01086                     }
01087 
01088                     // ask walls for permission to lay a parallel wall
01089                     //                                  if ( b->GetWall() && wal && !wal->RunsParallel( b->GetWall() ) )
01090                     //                                          return start;
01091                     //                                  if ( b->other->GetWall() && wal && !wal->RunsParallel( b->other->GetWall() ) )
01092                     //                                          return start;
01093 
01094                     // ask edge if it is splittalbe
01095                     if ( !b->Splittable() )
01096                         return start;
01097 
01098                     // create endpoint
01099                     ePoint*    D=tNEW(ePoint(end));
01100 #ifdef DEBUG
01101                     Check();
01102 #endif
01103                     // delete faces inside quad ABCE and connect A...E with new
01104                     // ePoint D.
01105 
01106                     tControlledPTR< eFace > oldFace_b = ZombifyFace( b->Face());
01107                     tControlledPTR< eFace > oldFace_bOther = ZombifyFace( b->other->Face() );
01108 
01109                     eHalfEdge *DC, *DA;
01110                     b->Split( DC, DA, D );
01111                     KillEdge(b);
01112                     DC = DC->other;
01113 
01114                     tASSERT( DC->Point() == D );
01115                     tASSERT( DA->Point() == D );
01116                     tASSERT( DC->other->Point() == C );
01117                     tASSERT( DA->other->Point() == A );
01118 
01119                     eHalfEdge *DE=tNEW(eHalfEdge) (D,E);
01120                     eHalfEdge *DB=tNEW(eHalfEdge) (D,B);
01121                     DA->other->SetWall(toBePlaced.Wall());
01122 
01123                     AddFaceAll(tNEW(eFace) (DE,e2,DA->other, oldFace_bOther ) );
01124                     AddFaceAll(tNEW(eFace) (DC,e1,DE->other, oldFace_bOther ) );
01125                     AddFaceAll(tNEW(eFace) (DB,a ,DC->other, oldFace_b ) );
01126                     AddFaceAll(tNEW(eFace) (DA,c ,DB->other, oldFace_b ) );
01127 
01128 #ifdef DEBUG
01129                     Check();
01130 #endif
01131                     return D;
01132                 }
01133             }
01134             // finnished!
01135         }
01136 
01137 
01138         else{
01139             // some definitions and trivial tests:
01140 
01141             eHalfEdge* c = currentEdge;
01142             eHalfEdge* e = rightFromCurrent;
01143             eHalfEdge* d = leftFromCurrent;
01144 
01145             eFace  *F = c->Face();
01146             ePoint *C = c->Point();
01147 
01148             if (*C == end){
01149 #ifdef DEBUG
01150                 Check();
01151 #endif
01152                 return C;
01153             }
01154             //      eHalfEdge *dummy=NULL;
01155 
01156 
01157             ePoint *D = d->Point();
01158 
01159             if (*D == end){
01160                 d->other->SetWall(toBePlaced.Wall());
01161 
01162 #ifdef DEBUG
01163                 Check();
01164 #endif
01165                 return D;
01166             }
01167 
01168             ePoint *B= e->Point();
01169 
01170             if (*B == end){
01171                 c->SetWall(toBePlaced.Wall());
01172 
01173 #ifdef DEBUG
01174                 Check();
01175 #endif
01176                 return B;
01177             }
01178 
01179             // if dir is parallel with eEdge c:
01180 
01181             /*
01182               if(exactly_onLeft){
01183               todo->Split(d,dummy);
01184               delete todo;
01185               todo=dummy;
01186               start=todo->p[0];
01187               restart=1;
01188               }
01189                
01190               else
01191             */
01192             {
01193                 if (!e->other || !e->other->Face())
01194                 {
01195                     // tERR_ERROR_INT ("Left Grid!");
01196                     // z-man: no need for an error! We can go on!
01197                     // nevertheless, should you get here in the debugger, I would
01198                     // ask you to follow the rest of this code block carefully
01199                     // and send me a trace ( which lines were visited, which pointers
01200                     // were set ) of it.
01201                     st_Breakpoint();
01202 
01203                     // grid rift or outer rim?
01204                     bool rift = false;
01205 
01206                     if ( !e->other )
01207                     {
01208                         // all gridded edges have other correctly set. Even the outer ones.
01209                         rift = true;
01210                     }
01211 
01212                     // get the wall of the halfopen edge
01213                     eWall* wall = e->GetWall();
01214                     if ( !wall && e->other )
01215                         wall = e->other->GetWall();
01216 
01217                     // no wall or splittable wall? This is not the outer edge, it is a rift.
01218                     if ( !wall || wall->Splittable() )
01219                         rift = true;
01220 
01221                     // wall is useless when e is not complete; forgt about it.
01222                     if ( !e->other )
01223                         wall = 0;
01224 
01225                     if ( rift )
01226                     {
01227                         // a rift! topology police to the rescue ( after eliminating
01228                         // the witnesses, of course )!
01229                         toBePlaced.Wall()->SplitByActive( wall );
01230                         return start;
01231                     }
01232                     else
01233                     {
01234                         // line to be drawn hit the outer edge.
01235                         // should not happen either; Range() should have prevented it.
01236                         // grow one step anyway:
01237                         Grow();
01238 
01239                         // test again
01240                         if (!e->other || !e->other->Face())
01241                         {
01242                             // still no luck? a case for the topology police.
01243                             toBePlaced.Wall()->SplitByActive( 0 );
01244                             return start;
01245                         }
01246                     }
01247                     // z-man: Thanks for debugging, this is all I need.
01248                 }
01249 
01250                 {
01251                     eFace  *G=e->other->Face();
01252 
01253                     eHalfEdge* b = e->other->next;
01254                     eHalfEdge* a = b->next;
01255                     tASSERT(a->next == e->other);
01256 
01257                     ePoint *A = a->Point();
01258 
01259                     /* we have the following Situation:
01260 
01261                     Should this figure get distorted, align the ":"
01262 
01263                     :         A
01264                     :         #
01265                     :        # ##
01266                     :   a   #  [eFace G]
01267                     :      #       ##
01268                     :     #       X  ##  b
01269                     :    #   e   /     ## 
01270                     : D ########/######### B
01271                     :   #      /(new eWall)
01272                     :   #     /      #
01273                     :   #    /  [eFace F]
01274                     :   #   /    #
01275                     : d #  /   # c 
01276                     :   # /  #
01277                     :   #/ #
01278                     :   ##   
01279                     :   C
01280                             
01281                     */
01282 
01283 
01284                     eCoord dd=*C-*D;
01285                     eCoord aa=*A-*D;
01286                     eCoord bb=*A-*B;
01287                     eCoord cc=*C-*B;
01288 
01289                     REAL scale = aa.NormSquared() + bb.NormSquared() +
01290                                  bb.NormSquared() + cc.NormSquared();
01291 
01292                     tASSERT(scale > 0);
01293                     //tASSERT(aa.NormSquared() > scale *SMALL_FLOAT);
01294                     //tASSERT(bb.NormSquared() > scale *SMALL_FLOAT);
01295                     //tASSERT(dd.NormSquared() > scale *SMALL_FLOAT);
01296                     //tASSERT(cc.NormSquared() > scale *SMALL_FLOAT);
01297 
01298 #ifdef DEBUG
01299                     Check();
01300 #endif
01301 
01302                     if (change_grid && e->Movable() && aa*dd>scale*.0001 && cc*bb >scale*.0001){
01303                         /*
01304 
01305                         if the angles CDA and ABC are less than 180deg, we can 
01306                         just "turn" eEdge e:
01307 
01308 
01309                         :         A
01310                         :[eFace F]#
01311                         :        #|##  [eFace G]
01312                         :   a   # |  ## b
01313                         :      # |     ##
01314                         :     #  |       ##
01315                         :    #  |    X     ## 
01316                         : D #   |   |        # B
01317                         :   #  |   |(new eWall)
01318                         :   #  e  |      #
01319                         :   # |  |     #
01320                         :   # | |    #
01321                         : d #| |   # c 
01322                         :   #||  #
01323                         :   #| #
01324                         :   ##   
01325                         :   C
01326 
01327                         */
01328                         if (*A == *C)
01329                         {
01330                             start = A;
01331                             restart = 1;
01332                             continue;
01333                         }
01334 
01335 
01336                         tControlledPTR< eFace > oldF = ZombifyFace(F);
01337                         tControlledPTR< eFace > oldG = ZombifyFace(G);
01338                         KillEdge(e);
01339 
01340                         e=tNEW(eHalfEdge) (C,A);
01341                         F=tNEW(eFace)     (a,d,e, oldF, oldG);
01342                         G=tNEW(eFace)     (b,e->other,c, oldF, oldG);
01343 
01344                         AddFaceAll(F);
01345                         AddFaceAll(G);
01346 
01347                         eCoord ee=*A-*C;
01348                         REAL x_test=ee*dir;
01349                         if (x_test>=0){
01350                             exactly_onLeft=(x_test<=EPS * EPS * se_EstimatedRangeOfMult(ee,dir));
01351                             currentEdge = c;
01352                             tASSERT(currentEdge->ID >= 0);
01353                         }
01354                         else{
01355                             exactly_onLeft=-1;
01356                             currentEdge = e;
01357                             tASSERT(currentEdge->ID >= 0);
01358                         }
01359 
01360 #ifdef DEBUG
01361                         Check();
01362 #endif
01363 
01364                     }
01365 
01366                     /* if not, we hace to introduce a new ePoint E: the cut between our
01367                        new eWall and eEdge e.
01368 
01369                             
01370                        :        A
01371                        :        ##
01372                        :        #\##
01373                        :         # \###
01374                        :         #  \  ##
01375                        : [eFace G]#  \   ## [eFace GG]
01376                        :          #   \    ###
01377                        :           #   aa     ##
01378                        :       a   #     \      ## b
01379                        :            #     \       ### 
01380                        :            #      \   CC    ##
01381                        :             #      \ /        ## 
01382                        :           D ## dd ##E### bb #### B [BD = e]
01383                        :            #      /(new eWall)
01384                        : [eFace F] #     /      #
01385                        :          #   cc     # [eFace FF]
01386                        :         #   /    #
01387                        :      d #  /   # c 
01388                        :       # /  #
01389                        :      #/ #
01390                        :     #/#   
01391                        :    ##
01392                        :   C
01393                             
01394 
01395                     */
01396 
01397                     else{
01398                         // calculate the coordinates of the intersection ePoint E:
01399                         ePoint *E;
01400                         eHalfEdge *bb,*cc,*dd;
01401 
01402                         if (*C == *A)
01403                         {
01404                             start = A;
01405                             restart = 1;
01406                             continue;
01407                         }
01408 
01409                         REAL ar = .5f;
01410 
01411                         {
01412                             eHalfEdge *newtodo;
01413                             ePoint *CC = tNEW(ePoint(end));
01414                             tStackObject< eTempEdge > todo (C, CC);
01415                             E=tNEW(ePoint) (e->IntersectWithCareless(todo.Edge(0)));
01416 
01417                             ar = e->Ratio(*E);
01418 
01419                             //        REAL br = todo.Edge(0)->Ratio(*E);
01420                             //        tASSERT(-.1f < ar && ar < 1.1f);
01421                             //        tASSERT(-.1f < br && br < 1.1f);
01422 
01423 
01424                             tASSERT(E->NormSquared() < se_maxGridSize*100);
01425                             todo.Edge(0)->Split(cc,newtodo,E);
01426                             KillEdge(newtodo);  // not needed. Make sure it gets deleted.
01427                         }
01428 
01429                         if (toBePlaced.Wall())
01430                         {
01431 #ifdef DEBUG
01432                             tASSERT(toBePlaced.Wall()->Splittable());
01433                             Check();
01434 #endif
01435 
01436                             // inform walls about the reason of their split
01437                             if ( !e->Movable() )
01438                             {
01439                                 eWall *other = e->GetWall();
01440                                 if ( other )
01441                                 {
01442                                     toBePlaced.Wall()->SplitByActive( other );
01443                                 }
01444                                 other = e->other->GetWall();
01445                                 if ( other )
01446                                 {
01447                                     toBePlaced.Wall()->SplitByActive( other );
01448                                 }
01449                             }
01450 
01451                             eWall *wa, *wb;
01452                             toBePlaced.Wall()->Split(wa, wb, eCoord::V(*start, *E, end));
01453 
01454                             // place the first bit of wall
01455                             cc->SetWall(wa);
01456 
01457                             // modify the temp edge to be placed to represent the rest of the wall
01458                             toBePlaced.SetWall( wb );
01459                             toBePlaced.Coord(0) = *E;
01460                         }
01461 
01462                         REAL arreal = ar;
01463                         if (ar > .99999f)
01464                             ar = .99999f;
01465                         if (ar < .00001f)
01466                             ar = .00001f;
01467                         *E = *B + (*D - *B) * ar;
01468 
01469                         if (*E == *D || (arreal >= 1.0f && !d->other->GetWall()))
01470                         {
01471                             d->other->SetWall(cc->GetWall());
01472                             KillEdge(cc);
01473                             start = D;
01474                             restart = 1;
01475                             continue;
01476                         }
01477 
01478                         if (*E == *B || (arreal <= 0.0f && !c->GetWall()))
01479                         {
01480                             c->SetWall(cc->GetWall());
01481 
01482                             KillEdge(cc);
01483                             start = B;
01484                             restart = 1;
01485                             continue;
01486                         }
01487 
01488 
01489 
01490                         e->other->Split(dd,bb,E);
01491 
01492                         F->CorrectArea();
01493                         G->CorrectArea();
01494                         tControlledPTR< eFace > oldF = ZombifyFace(F);
01495                         tControlledPTR< eFace > oldG = ZombifyFace(G);
01496                         KillEdge(e);
01497 
01498 
01499                         start = E;
01500 
01501                         bool aeq = false, ceq = false;
01502 
01503                         if (*A == *E)
01504                         {
01505                             if (A==leakPoint)
01506                                 st_Breakpoint();
01507 
01508                             A->Replace(E);
01509                             KillPoint(A);
01510 
01511                             a->other->SetWall(dd->GetWall());
01512                             a->SetWall(dd->other->GetWall());
01513                             b->SetWall(bb->other->GetWall());
01514                             b->other->SetWall(bb->GetWall());
01515                             KillEdge(dd);
01516                             KillEdge(bb);
01517                             dd = a->other;
01518                             bb = b->other;
01519                             aeq = true;
01520 
01521                             se_LinkFaces( oldG, oldF );
01522                         }
01523 
01524                         if (*C == *E)
01525                         {
01526                             tASSERT(!aeq);
01527 
01528                             C->Replace(E);
01529                             KillPoint(C);
01530 
01531                             d->other->SetWall(dd->other->GetWall());
01532                             d->SetWall(dd->GetWall());
01533                             c->other->SetWall(bb->other->GetWall());
01534                             c->SetWall(bb->GetWall());
01535 
01536                             KillEdge(dd);
01537                             KillEdge(bb);
01538                             KillEdge(cc);
01539                             dd = d;
01540                             bb = c;
01541                             ceq = true;
01542 
01543                             se_LinkFaces( oldF, oldG );
01544                         }
01545 
01546                         if (!ceq)
01547                         {
01548                             F=tNEW(eFace) (d,cc,dd->other, oldF );
01549                             eFace *FF=tNEW(eFace) (c,bb->other,cc->other, oldF );
01550 
01551                             AddFaceAll(F);
01552                             AddFaceAll(FF);
01553                         }
01554 
01555                         eHalfEdge *aa=NULL;
01556 
01557 
01558                         if (!aeq)
01559                         {
01560                             aa = tNEW(eHalfEdge) (E,A);
01561 
01562                             eFace *GG=tNEW(eFace) (b,aa->other,bb, oldG );
01563                             G=tNEW(eFace) (a,dd,aa, oldG );
01564                             AddFaceAll(G);
01565                             AddFaceAll(GG);
01566                         }
01567                         else
01568                         {
01569                             start = E;
01570                             restart = true;
01571                             continue;
01572                         }
01573 
01574 #ifdef DEBUG
01575                         Check();
01576 #endif
01577                         if (end == *E)
01578                             return E;
01579 
01580                         //          start = E;
01581                         eCoord ea=*A-*E;
01582                         dir   = end - *E;
01583                         REAL x_test=ea*dir;
01584 
01585                         tASSERT (aa);
01586                         if (x_test>=0){
01587                             currentEdge=bb;
01588                             tASSERT(currentEdge->ID >= 0);
01589                             exactly_onLeft=(x_test<=EPS*EPS*se_EstimatedRangeOfMult(ea,dir));
01590                             // if (exactly_onLeft) std::cerr << "Achtung 3!\n";
01591                         }
01592 
01593                         else{
01594                             currentEdge=aa;
01595                             tASSERT(currentEdge->ID >= 0);
01596                             exactly_onLeft=-1;
01597                         }
01598                     }
01599                 }
01600             }
01601         }
01602     }
01603 
01604     tERR_ERROR_INT("We shound never get here!");
01605     return NULL;
01606 }
01607 
01608 
01609 // **************************
01610 //          eHalfEdge
01611 // **************************
01612 
01613 
01614 
01615 
01616 // splitting
01617 bool eHalfEdge::Splittable() const
01618 {
01619     eWall *w = GetWall();
01620     if (!w && other)
01621         w = other->GetWall();
01622     return !w || w->Splittable();
01623 }
01624 
01625 // split eEdge at s;
01626 void eHalfEdge::Split(eHalfEdge *& e1,eHalfEdge *& e2,ePoint *s)
01627 {
01628     tASSERT(other);
01629 
01630     e1=tNEW(eHalfEdge) (Point(),s);
01631     e2=tNEW(eHalfEdge) (s,other->Point());
01632 
01633     if (GetWall())
01634     {
01635         if (!GetWall()->Splittable())
01636             tERR_ERROR_INT("I told you not to split that!");
01637         // first, split the eWall structure:
01638         eWall *w1,*w2;
01639         GetWall()->Split(w1,w2,Ratio(*s));
01640 
01641         // we use the base class' function to set walls so we don't alarm the topology police
01642         e1->eWallHolder::SetWall(w1);
01643         e2->eWallHolder::SetWall(w2);
01644         w1->CalcLen();
01645         w2->CalcLen();
01646     }
01647     if (other->GetWall())
01648     {
01649         if (!other->GetWall()->Splittable())
01650             tERR_ERROR_INT("I told you not to split that!");
01651         // first, split the eWall structure:
01652         eWall *w1,*w2;
01653         other->GetWall()->Split(w2,w1,1-Ratio(*s));
01654 
01655         // the topology police would crash right here.
01656         e1->other->eWallHolder::SetWall(w1);
01657         e2->other->eWallHolder::SetWall(w2);
01658         w1->CalcLen();
01659         w2->CalcLen();
01660     }
01661 }
01662 
01663 
01664 #define SIMPLIFY
01665 #ifdef SIMPLIFY
01666 
01667 // test if a point is movable
01668 bool Movable( const ePoint* p )
01669 {
01670     eHalfEdge* run = p->Edge();
01671     eHalfEdge* stop =run;
01672 
01673     // run through all edges from this point
01674     do
01675     {
01676         // one of the edges contains a wall, abort:
01677         if ( !run->Movable() )
01678             return false;
01679 
01680         // advance to next edge from this point
01681         run = run->Other();
01682         if ( run )
01683             run = run->Next();
01684     }
01685     while ( run && stop != run );
01686 
01687     // no obstacles found.
01688     return true;
01689 }
01690 
01691 
01692 // test how far you can move a point in a certain direction without giving the
01693 // face adjacent to the given half-edge negative area
01694 void ClampMovement( const ePoint* p, eCoord& dir, const eHalfEdge* e )
01695 {
01696     eHalfEdge* next = e->Next();
01697     // get two of the side vectors of the face
01698     eCoord oppositeEdge = next->Vec();
01699     eCoord adjacentEdge = e->Vec();
01700 
01701     // calculate current surface area
01702     REAL area = oppositeEdge * adjacentEdge;
01703 
01704     // calculate the influence of the proposed movement on the surface area
01705     REAL areaChange = dir * oppositeEdge;
01706 
01707     // allow it if the change increases the area
01708     if ( areaChange >= 0 )
01709         return;
01710 
01711     // allow it if the change keeps the area positive
01712     if ( area + areaChange >= 0 )
01713         return;
01714 
01715     // if the current surface area is already negative, forbid the change
01716     if ( area < 0 )
01717     {
01718         dir = eCoord(0,0);
01719         return;
01720     }
01721 
01722     // clamp the desired movement
01723     REAL clampFactor = - area / areaChange;
01724     tASSERT( clampFactor >=0 && clampFactor <= 1 );
01725 
01726     // clamp
01727     dir = dir * clampFactor;
01728 }
01729 
01730 // test how far you can move a point in a certain direction without giving any
01731 // of the adjacent faces a negative area
01732 void ClampMovement( const ePoint* p, eCoord& dir )
01733 {
01734     eHalfEdge* run = p->Edge();
01735     eHalfEdge* stop =run;
01736 
01737     // run through all edges from this point
01738     do
01739     {
01740         // get the max mobility of the edge
01741         ClampMovement( p, dir, run );
01742 
01743         // advance to next edge from this point
01744         run = run->Other();
01745         if ( run )
01746             run = run->Next();
01747     }
01748     while ( run && stop != run );
01749 }
01750 
01751 bool eFace::CorrectArea()
01752 {
01753     REAL area = edge->next->Vec() * edge->Vec();
01754     if (area >= 0)
01755         return false;
01756 
01757     eHalfEdge *run = edge;
01758 
01759     // find the longest edge ( preferably with wall )
01760     eHalfEdge *longest = NULL;
01761     REAL       length  = -1;
01762     bool       wall    = false;
01763 
01764     for (int i=2; i>=0; i--)
01765     {
01766         REAL runLength   = run->Vec().NormSquared();
01767 
01768         // test if moving the point opposite to run would move walls
01769         if (!Movable( run->next->next->Point() ) )
01770             continue;
01771 
01772         bool runWall     = !run->Movable();
01773         if ( runLength > length || runWall )
01774         {
01775             // abort if the triangle has two walled sides
01776             if ( wall && runWall )
01777             {
01778                 // however, this should never, ever happen.
01779                 st_Breakpoint();
01780                 return false;
01781             }
01782 
01783             wall    = runWall;
01784             length  = runLength;
01785             longest = run;
01786         }
01787         run = run->next;
01788     }
01789 
01790     // no luck?
01791     if ( !longest )
01792         return false;
01793 
01794     run = longest;
01795     eCoord &A = *run->Point();
01796     run       =  run->next;
01797     eCoord &B = *run->Point();
01798     run       =  run->next;
01799     eCoord &C = *run->Point();
01800     ePoint* pC = run->Point();
01801 
01802     // now, C is the point opposite to the longest edge.
01803     eCoord MoveDir = (B-A);
01804     MoveDir = MoveDir.Turn(0, -area * 1.01/MoveDir.NormSquared() );
01805 
01806     // move C as little as possible into the desired direction
01807     if ( MoveDir.NormSquared() > 0 )
01808     {
01809         eCoord Cnew = C + MoveDir;
01810 
01811         while ( Cnew.x == C.x && Cnew.y == C.y )
01812         {
01813             // try displacing by MoveDir and enlarge MoveDir
01814             Cnew = C + MoveDir;
01815             MoveDir = MoveDir * 2;
01816         }
01817 
01818         // clamp the movement so it does not make the situation worse
01819         // for other faces
01820         ClampMovement( pC, MoveDir );
01821 
01822         // store result
01823         C = C + MoveDir;
01824     }
01825     else // give up
01826         return false;
01827 
01828     REAL newarea = edge->next->Vec() * edge->Vec();
01829     tASSERT(newarea >= area);
01830 
01831     // check if treatment was successful
01832     return newarea > area;
01833 }
01834 
01835 bool eHalfEdge::Simplify(eGrid *grid)
01836 {
01837     if (GetWall() && GetWall()->Deletable() && face)
01838     {
01839         ClearWall();
01840     }
01841 
01842     if (other && other->GetWall() && other->GetWall()->Deletable() && other->face)
01843     {
01844         other->ClearWall();
01845     }
01846 
01847     if (GetWall() || !other || other->GetWall() || !face || !other->face)
01848         return false;
01849 
01850     ePoint  *to_be_removed=point; // we'll remove this ePoint
01851     ePoint  *stay=other->point;   // and redirect all his edges to this ePoint
01852 
01853     // first, we find the faces that are going to be modified:
01854     // they are neighbours of the ePoint we'll remove.
01855 
01856     eHalfEdge *run = this->other->next;
01857     do{
01858         //    eFace *F = run->face; // eFace to be modified
01859         tASSERT(run->other);
01860 
01861 
01862 
01863 
01864         /*
01865 
01866 
01867 
01868 
01869           C  this
01870           A ------------ --------------- stays
01871           Next    |
01872           | 
01873           |r 
01874           |u   
01875           |n    
01876           |     
01877           |
01878           B
01879 
01880 
01881 
01882 
01883         */
01884 
01885 
01886         // if any of the to-be-modified edges is a eWall, abort the operation.
01887         if (run->GetWall() || run->other->GetWall() || !run->face)
01888             return false;
01889 
01890         eHalfEdge *Next = run->other->next;
01891         eCoord &A = *Next->other->point;
01892         eCoord &B = *run->other->point;
01893         eCoord &C = *stay;
01894 #ifdef DEBUG
01895         //    eCoord &D = *to_be_removed;
01896         //    eCoord leftvec_b  = B-D;
01897         //    eCoord rightvec_b = A-D;
01898         //    REAL orientation_b=leftvec_b*rightvec_b;
01899 #endif
01900 
01901 
01902         // if the eFace is to be modified (and not deleted), check
01903         // if it will flip orientation; if yes, abort.
01904 
01905         eCoord leftvec = B-C;
01906         eCoord rightvec= A-C;
01907 
01908         REAL orientation=leftvec*rightvec;
01909 
01910         if (orientation <= 0)
01911             return false;
01912 
01913         // test if the face contains a gameobject or is otherwise referenced; abort if that is the case
01914         // four references are nominal: three from the edges, one from the grid
01915         if ( !Next->face || Next->face->GetRefcount() > 4 )
01916             return false;
01917 
01918         //    tASSERT(orientation_b > 0);
01919 
01920         run = Next;
01921     }
01922     while (run && run->other &&  !(this == run->other->next));
01923 
01924     // dangerously close to the rim....
01925     if (!run || !run->other)
01926         return false;
01927 
01928     // Allright! everything is safe.
01929 #ifdef DEBUG
01930     grid->Check();
01931 #endif
01932 
01933     eHalfEdge *a  = next;
01934     eHalfEdge *aa = a->next;
01935     ePoint *A     = aa->Point();
01936 
01937     eHalfEdge *b  = other->next;
01938     eHalfEdge *bb = b->next;
01939     ePoint *B     = bb->Point();
01940 
01941     if (a->GetWall() || a->other->GetWall())
01942         return false;
01943 
01944     if (aa->GetWall() || aa->other->GetWall())
01945         return false;
01946 
01947     if (b->GetWall() || b->other->GetWall())
01948         return false;
01949 
01950     if (bb->GetWall() || bb->other->GetWall())
01951         return false;
01952 
01953     tControlledPTR< eHalfEdge > keep( this );
01954 
01955     int idrec = ID;
01956     tRecorderSync< int >::Archive( "_GRID_SIMPLIFY_REAL", 8, idrec );
01957 
01958     // the faces that will be removed
01959     tControlledPTR< eFace > killed1 = grid->ZombifyFace( face );
01960     tControlledPTR< eFace > killed2 = grid->ZombifyFace( other->face );
01961 
01962     // all faces that will replace them get added to their replacement list
01963     run = this->other->next->other->next;
01964     do{
01965         tASSERT(run->other);
01966 
01967         //       eHalfEdge *Next = run->other->next;
01968         eFace *F = run->face; // eFace to be modified
01969         tASSERT( F != killed1 );
01970         tASSERT( F != killed2 );
01971         if( F )
01972         {
01973             se_LinkFaces( killed1, F );
01974             se_LinkFaces( killed2, F );
01975         }
01976 
01977         run = run->other->next;
01978     }
01979     while (run && run->other &&  !(this == run));
01980 
01981     stay->Replace(to_be_removed);
01982 
01983     // kill everything that goes away:
01984     //  grid->KillFace( killed1 );
01985     //  grid->KillFace( killed2 );
01986     grid->KillPoint(stay);
01987 
01988     grid->KillEdge(this);
01989 
01990     to_be_removed->edge = aa->other;
01991     A            ->edge = a->other;
01992     B            ->edge = b->other;
01993 
01994     // sew the edges of the faces that are going to disappear together:
01995     a->other->SetOther(aa->other);
01996     b->other->SetOther(bb->other);
01997 
01998     grid->KillEdge(a);
01999     grid->KillEdge(aa);
02000     grid->KillEdge(b);
02001     grid->KillEdge(bb);
02002 
02003     return true;
02004 }
02005 
02006 void eGrid::SimplifyNum(int e){
02007 #ifdef DEBUG
02008     Check();
02009 #endif
02010 
02011     if (e>=0 && e < edges.Len()){
02012         eHalfEdge *E=edges(e);
02013 #ifdef DEBUG
02014         eHalfEdge *Esave=E;
02015 #endif
02016         if ( !E || !E->other )
02017             return;
02018 
02019         // this point will be removed. Make sure it is none of the points on the outer rim.
02020         ePoint * toBeRemoved = E->other->Point();
02021         if ( toBeRemoved == A || toBeRemoved == B || toBeRemoved == C )
02022             return;
02023 
02024         tRecorderSync< int >::Archive( "_GRID_SIMPLIFY", 8, e );
02025 
02026         if ( E->Simplify(this) )
02027         {
02028             se_simplifyEdges += se_simplifyEdgesSuccess;
02029         }
02030 
02031 #ifdef DEBUG
02032         tASSERT(Esave);
02033 
02034         Check();
02035 #endif
02036     }
02037 }
02038 
02039 #endif // SIMPLIFY
02040 
02041 void eGrid::SimplifyAll(int count){
02042     if (requestCleanup)
02043     {
02044         requestCleanup = false;
02045         for (int i=faces.Len()-1; i>=0; i--)
02046             requestCleanup |= faces(i)->CorrectArea();
02047     }
02048 
02049 
02050     static int counter=0;
02051 
02052     // try to simplify at least one edge
02053     se_simplifyEdges++;
02054 
02055     for(;count>0 && se_simplifyEdges>0;count--,se_simplifyEdges--){
02056         counter--;
02057 
02058         if (counter<0 || counter>=edges.Len())
02059             counter=edges.Len()-1;
02060 
02061         SimplifyNum(counter);
02062     }
02063 }
02064 
02065 
02066 
02067 eGrid *currentGrid = NULL;
02068 
02069 eGrid* eGrid::CurrentGrid(){return currentGrid;}
02070 
02071 void eGrid::Create(){
02072     currentGrid = this;
02073 
02074     if (!A)
02075         Clear();
02076 
02077     base=eCoord(20,100);
02078 
02079 #ifdef DEBUG
02080     doCheck = true;
02081 #endif
02082     requestCleanup = false;
02083 
02084 
02085     A=tNEW(ePoint) (base.Turn(1,0));
02086     B=tNEW(ePoint) (base.Turn(-.5,.87));
02087     C=tNEW(ePoint) (base.Turn(-.5,-.87));
02088 
02089     a=tNEW(eHalfEdge) (B,C,tNEW(eWall(this)));
02090     b=tNEW(eHalfEdge) (C,A,tNEW(eWall(this)));
02091     c=tNEW(eHalfEdge) (A,B,tNEW(eWall(this)));
02092 
02093     a->other->next = c->other;
02094     a->other->prev = b->other;
02095     b->other->next = a->other;
02096     b->other->prev = c->other;
02097     c->other->next = b->other;
02098     c->other->prev = a->other;
02099 
02100     AddFaceAll(tNEW(eFace) (a,b,c));
02101 
02102     maxNormSquared=base.NormSquared();
02103 
02104 #ifdef DEBUG
02105     Check();
02106 #endif
02107 
02108 }
02109 
02110 
02111 void eGrid::Clear(){
02112     eHalfEdge::ClearPathData();
02113 
02114     base=eCoord(0,100);
02115     maxNormSquared=0;
02116 
02117     int i;
02118     for(i=faces.Len()-1; i>=0; i--)
02119     {
02120         faces(i)->Unlink();
02121         RemoveFace(faces(i));
02122     }
02123     for(i=points.Len()-1; i>=0; i--)
02124     {
02125         points(i)->Unlink();
02126         RemovePoint(points(i));
02127     }
02128     for(i=edges.Len()-1; i>=0; i--)
02129     {
02130         edges(i)->Unlink();
02131         RemoveEdge(edges(i));
02132     }
02133 
02134 
02135     A=B=C=NULL;
02136     a=b=c=NULL;
02137 
02138     eGameObject::DeleteAll( this );
02139 
02140     //  se_faceReplacements.clear();
02141 }
02142 
02143 void eGrid::Grow()
02144 {
02145 #ifdef DEBUG
02146     Check();
02147 #endif
02148 
02149     if ( maxNormSquared > se_maxGridSize )
02150         return;
02151 
02152     base = base.Turn(-4,0);
02153     maxNormSquared=base.NormSquared();
02154 
02155     a->ClearWall();
02156     b->ClearWall();
02157     c->ClearWall();
02158 
02159     ePoint *newA=tNEW(ePoint) (base.Turn(1,0));
02160     ePoint *newB=tNEW(ePoint) (base.Turn(-.5,.87));
02161     ePoint *newC=tNEW(ePoint) (base.Turn(-.5,-.87));
02162 
02163     eHalfEdge *newa=tNEW(eHalfEdge) (newB,newC,tNEW(eWall(this)));
02164     eHalfEdge *newb=tNEW(eHalfEdge) (newC,newA,tNEW(eWall(this)));
02165     eHalfEdge *newc=tNEW(eHalfEdge) (newA,newB,tNEW(eWall(this)));
02166 
02167     eHalfEdge *AnewB=tNEW(eHalfEdge) (A,newB,NULL);
02168     eHalfEdge *AnewC=tNEW(eHalfEdge) (A,newC,NULL);
02169     eHalfEdge *BnewA=tNEW(eHalfEdge) (B,newA,NULL);
02170     eHalfEdge *BnewC=tNEW(eHalfEdge) (B,newC,NULL);
02171     eHalfEdge *CnewA=tNEW(eHalfEdge) (C,newA,NULL);
02172     eHalfEdge *CnewB=tNEW(eHalfEdge) (C,newB,NULL);
02173 
02174     AddFaceAll(tNEW(eFace) (a->other,BnewA,CnewA->other));
02175     AddFaceAll(tNEW(eFace) (b->other,CnewB,AnewB->other));
02176     AddFaceAll(tNEW(eFace) (c->other,AnewC,BnewC->other));
02177 
02178     AddFaceAll(tNEW(eFace) (newa,AnewC->other,AnewB));
02179     AddFaceAll(tNEW(eFace) (newb,BnewA->other,BnewC));
02180     AddFaceAll(tNEW(eFace) (newc,CnewB->other,CnewA));
02181 
02182     a=newa;
02183     b=newb;
02184     c=newc;
02185 
02186     A=newA;
02187     B=newB;
02188     C=newC;
02189 
02190     a->other->next = c->other;
02191     a->other->prev = b->other;
02192     b->other->next = a->other;
02193     b->other->prev = c->other;
02194     c->other->next = b->other;
02195     c->other->prev = a->other;
02196 
02197 #ifdef DEBUG
02198     Check();
02199 #endif
02200 }
02201 
02202 void eGrid::Range(REAL NormSquared){
02203     if (A==NULL)
02204         Create();
02205     //    tERR_ERROR_INT("Wanted to insert something into the nonexistant grid!");
02206 
02207     // the magic factor of 4 is chosen so that no points can be added outside of the
02208     // current tiangle abc added by Grow().
02209     while (NormSquared * 4 > maxNormSquared && maxNormSquared < se_maxGridSize )
02210         Grow();
02211 }
02212 
02213 void eTempEdge::CopyIntoGrid(eGrid *grid)
02214 {
02215     if (Point(0) != Point(1)){
02216         ePoint *newp = grid->Insert(*Point(0));
02217         tASSERT( newp );
02218         eWall *w = Edge(0)->GetWall();
02219         w->Insert();
02220         tASSERT(w->Splittable());
02221         //    Edge(0)->GetWall() = NULL;
02222         //    w->edge       = NULL;
02223         //    Edge(0)->SetWall(NULL);
02224         grid->DrawLine(newp, *Point(1), w);
02225     }
02226 }
02227 
02228 eTempEdge::eTempEdge(const eCoord& a, const eCoord &b, eWall *w){
02229     halfEdges[0] = tNEW(eHalfEdge(tNEW(ePoint)(a),tNEW(ePoint)(b),w));
02230     halfEdges[1] = halfEdges[0]->Other();
02231 }
02232 
02233 eTempEdge::eTempEdge(ePoint *a, ePoint *b, eWall *w){
02234     halfEdges[0] = tNEW(eHalfEdge(a, b ,w));
02235     halfEdges[1] = halfEdges[0]->Other();
02236 }
02237 
02238 
02239 
02240 eTempEdge::~eTempEdge()
02241 {
02242     halfEdges[0]->Unlink();
02243 }
02244 
02245 
02246 
02247 
02248 eHalfEdge::eHalfEdge(ePoint *p):ID(-1),next(NULL), prev(NULL), other(NULL)
02249 {
02250     origin_ = PATH_NONE;
02251 
02252     point = p;
02253     face  = 0;
02254 }
02255 
02256 
02257 eHalfEdge::eHalfEdge(ePoint *a, ePoint *b, eWall *w)
02258         :ID(-1),next(NULL), prev(NULL), other(NULL)
02259 {
02260     tASSERT( a !=  b);
02261 
02262     origin_ = PATH_NONE;
02263 
02264     SetPoint(a);
02265     SetOther(new eHalfEdge(b));
02266     SetWall(w);
02267 }
02268 
02269 // get the intersection point of two edges:
02270 // stupid intersection without checks; returned point
02271 // does not allways lie within the two edges
02272 eCoord eHalfEdge::IntersectWithCareless(const eHalfEdge *e2) const
02273 {
02274     eCoord vec  = *other->Point()     -     *Point();
02275     eCoord e2vec= *e2->other->Point() - *e2->Point();
02276     eCoord e2_t = *Point()     - *e2->Point();
02277 
02278     REAL inv = (vec*e2vec);
02279     if (fabs(inv) > EPS * se_EstimatedRangeOfMult( vec, e2vec ) )
02280     {
02281         // return intersection poin
02282         return (*Point()-vec*((e2_t*e2vec)/inv));
02283     }
02284     else
02285     {
02286         // lines lie almost parallel; return "inverse center of gravity" ( the swapped
02287         // weighting is intentional, the smaller line should have a bigger influence )
02288         REAL m1 = vec.Norm();
02289         REAL m2 = e2vec.Norm();
02290         if ( m1 + m2 <= 0 ) // sanity check weights
02291             m1=m2=1;
02292         return ((*Point() + *other->Point())*m2 + (*e2->Point() + *e2->other->Point())*m1)*(.5/(m1+m2));
02293     }
02294 }
02295 
02296 // the same, but with checks: if the two edges don't intersect,
02297 // NULL is returned.
02298 ePoint * eHalfEdge::IntersectWith(const eHalfEdge *e2) const
02299 {
02300     eCoord vec  = *other->Point()     -     *Point();
02301     eCoord e2vec= *e2->other->Point() - *e2->Point();
02302     eCoord e2_t = *Point()     - *e2->Point();
02303 
02304     REAL div=(vec*e2vec);
02305 
02306     if (div==0) return NULL;
02307 
02308     eCoord ret=*Point()-vec*((e2_t*e2vec)/ div);
02309 
02310 
02311     REAL v=Ratio(ret);
02312     if (v<0 || v>1) return NULL;
02313     v=e2->Ratio(ret);
02314     if (v<0 || v>1) return NULL;
02315 
02316     return tNEW(ePoint) (ret);
02317 
02318 }
02319 
02320 // inserts an eEdge into the grid
02321 void eHalfEdge::CopyIntoGrid(eGrid *grid, bool change_grid){
02322     tASSERT(other);
02323     ePoint *start = grid->Insert(*Point());
02324     grid->DrawLine(start, *other->Point(), GetWall(), change_grid);
02325 }
02326 
02327 //bool eHalfEdge::Simplify(int dir);
02328 // try to get rid of this eEdge; return value: can we delete it?
02329 
02330 
02331 bool eHalfEdge::Check() const{
02332 #ifdef DEBUG
02333     if (other && other->next)
02334         tASSERT(other->next->Point() == Point());
02335     if (next)
02336         tASSERT(next->Face() == Face());
02337     if (next)
02338         tASSERT(this == next->prev);
02339     if (prev)
02340         tASSERT(this == prev->next);
02341 
02342     if (ID>=0)
02343     {
02344         tASSERT(!Point() || Point()->ID >=0);
02345         tASSERT(!Face()  || Face()->ID  >=0);
02346         tASSERT(!next    || next->ID    >=0);
02347         tASSERT(!prev    || prev->ID    >=0);
02348         tASSERT(!other   || other->ID   >=0);
02349     }
02350 #endif
02351 
02352     // only the three outer edges are allowed to have missing faces
02353     if ( !face )
02354     {
02355         eWall* wall = GetWall();
02356         if ( !wall && other )
02357             wall = other->GetWall();
02358         tASSERT( wall );
02359 
02360         tASSERT( !wall->Splittable() );
02361         // the outer walls are unsplittable ( and right now are the only unsplittable
02362         // walls; all real walls need to be split sometimes when laid out. )
02363     }
02364 
02365     return true;
02366 }
02367 
02368 
02369 
02370 void eGrid::AddFace    (eFace     *f)
02371 {
02372     if (f->ID >= 0)
02373         return;
02374 
02375     faces.Add(f, f->ID);
02376 
02377     if (f->CorrectArea())
02378         requestCleanup = true;
02379 }
02380 
02381 void eGrid::RemoveFace (eFace     *f)
02382 {
02383     if (f->ID < 0)
02384         return;
02385 
02386     faces.Remove(f, f->ID);
02387 }
02388 
02389 void eGrid::AddEdge    (eHalfEdge *e)
02390 {
02391     if (e->ID >= 0)
02392         return;
02393 
02394     tASSERT(e->Other() && *e->Point() != *e->Other()->Point());
02395 
02396     edges.Add(e, e->ID);
02397 
02398     int idrec = e->ID;
02399     tRecorderSync< int >::Archive( "_GRID_ADD_EDGE", 8, idrec );
02400 }
02401 
02402 void eGrid::RemoveEdge (eHalfEdge *e)
02403 {
02404     if (e == leakEdge)
02405         st_Breakpoint();
02406 
02407     if (e->ID < 0)
02408         return;
02409 
02410     int idrec = e->ID;
02411     tRecorderSync< int >::Archive( "_GRID_REMOVE_EDGE", 8, idrec );
02412 
02413     edges.Remove(e, e->ID);
02414 }
02415 
02416 void eGrid::AddPoint   (ePoint    *p)
02417 {
02418     if (p->ID >= 0)
02419         return;
02420 
02421     points.Add(p, p->ID);
02422 
02423 #ifdef DEBUG_DISTORT
02424     // debug facility: distort grid
02425     static eCoord distortion(1,0);
02426     distortion = distortion.Turn(.6,.8);
02427     *p = *p + distortion;
02428 #endif
02429 }
02430 
02431 void eGrid::RemovePoint(ePoint    *p)
02432 {
02433     if (p == leakPoint)
02434         st_Breakpoint();
02435 
02436     if (p->ID < 0)
02437         return;
02438 
02439     points.Remove(p, p->ID);
02440 }
02441 
02442 void eGrid::KillFace (eFace*      f)
02443 {
02444     tControlledPTR< eFace > keep( f );
02445     RemoveFace(f);
02446     f->Unlink();
02447 }
02448 
02449 tControlledPTR< eFace > eGrid::ZombifyFace (eFace*      f)
02450 {
02451     tControlledPTR< eFace > keep( f );
02452     RemoveFace(f);
02453     f->Unlink();
02454     return keep;
02455 }
02456 
02457 void eGrid::KillEdge (eHalfEdge*  e)
02458 {
02459     tControlledPTR< eHalfEdge > keep( e );
02460     RemoveEdge(e);
02461     tControlledPTR< eHalfEdge > o ( e->other );
02462 
02463     e->Unlink();
02464 
02465     if (o)
02466     {
02467         KillEdge(o);
02468     }
02469 }
02470 
02471 void eGrid::KillPoint(ePoint*     p)
02472 {
02473     tControlledPTR< ePoint > keep( p );
02474     RemovePoint(p);
02475     p->Unlink();
02476 }
02477 
02478 void eGrid::AddFaceAll (eFace     *f)
02479 {
02480     eHalfEdge *run = f->edge;
02481     for(int j=0;j<=2;j++){
02482         AddEdge(run);
02483         AddEdge(run->other);
02484         AddPoint(run->Point());
02485         run = run->next;
02486     }
02487     tASSERT (run == f->edge);
02488 
02489     AddFace(f);
02490 }
02491 
02492 
02493 
02494 ePoint * eGrid::Insert(const eCoord& x, eFace *start){
02495 #ifdef DEBUG
02496     Check();
02497 #endif
02498     Range(x.NormSquared());
02499 
02500     eFace *f = FindSurroundingFace(x, start);
02501     if (!f)
02502         return NULL;
02503 
02504     /*
02505       for(int i=faces.Len()-1;i>=0;i--)
02506       {
02507          eFace *f = faces(i);
02508          if (f->IsInside(x)){
02509 
02510     */
02511 
02512     eHalfEdge *run = f->edge;
02513     int j;
02514     for(j=0;j<=2;j++){
02515         if (*run->Point() == x)
02516             return run->Point();
02517         run = run->next;
02518     }
02519     tASSERT (run == f->edge);
02520 
02521 #ifdef DEBUG
02522     // check again ( possibly with breakpoint )
02523     for(j=0;j<=2;j++){
02524         if (*run->Point() == x)
02525             return run->Point();
02526         run = run->next;
02527     }
02528     tASSERT (run == f->edge);
02529 #endif
02530 
02531     return DrawLine(f->edge->Point(), x);
02532     /*
02533       break;
02534          }
02535       }
02536       return NULL; 
02537     */
02538 }
02539 
02540 const eCoord se_zeroCoord(0,0);
02541 
02542 
02543 eFace * eGrid::FindSurroundingFace(const eCoord &pos, eFace *currentFace) const{
02544     if (faces.Len()<1)
02545         return NULL;
02546 
02547     if (!currentFace || currentFace->ID < 0 || currentFace->ID >= faces.Len() || faces(currentFace->ID) != currentFace)
02548         currentFace=faces(0);
02549 
02550     int timeout=faces.Len()+2;
02551 
02552     while (currentFace && timeout >0 && !currentFace->IsInside(pos)){
02553         timeout--;
02554 
02555         eHalfEdge *run   = currentFace->Edge(); // runs through all edges of the face
02556         eHalfEdge *best  = NULL;                // the best face to leave
02557         eHalfEdge *first = NULL;
02558         eHalfEdge *in    = NULL;
02559         REAL bestScore   = 0;
02560 
02561 
02562         // look for the best way out
02563         while(run != first)
02564         {
02565             if (run == in)
02566             {
02567                 run = run->Next();
02568                 continue;
02569             }
02570 
02571             if ( run->Other() && run->Other()->Face() )
02572             {
02573                 eCoord vec=pos - (*run->Point()); // the vector to our destination
02574 
02575                 REAL score = run->Vec() * vec;
02576 
02577                 if (score > bestScore)
02578                 {
02579                     best      = run;
02580                     bestScore = score;
02581                 }
02582             }
02583 
02584             if (!first)
02585                 first = run;
02586 
02587             run = run->Next();
02588         }
02589 
02590         if (best)
02591         {
02592             in = best->Other();
02593             tASSERT(in);
02594 
02595             currentFace = in->Face();
02596             timeout--;
02597         }
02598         else
02599         {
02600             timeout = 0;
02601             //                  st_Breakpoint();
02602         }
02603     }
02604 
02605     if (timeout<=0){ // normal way failed
02606 #ifdef DEBUG
02607         con << "WARNING! FindSurroundingFace failed.\n";
02608 #endif
02609         // do it the hard way:
02610         for(int i=faces.Len()-1;i>=0;i--)
02611             if(faces(i)->IsInside(pos)){
02612                 currentFace=faces(i);
02613                 i=-1;
02614             }
02615     }
02616 
02617     return currentFace;
02618 }
02619 
02620 void eGrid::AddGameObjectInteresting    (eGameObject *o){
02621     gameObjectsInteresting.Add(o, o->interestingID);
02622 }
02623 
02624 void eGrid::RemoveGameObjectInteresting (eGameObject *o){
02625     gameObjectsInteresting.Remove(o, o->interestingID);
02626 }
02627 
02628 void eGrid::AddGameObjectInactive       (eGameObject *o){
02629     gameObjectsInactive.Add(o, o->inactiveID);
02630 }
02631 
02632 void eGrid::RemoveGameObjectInactive    (eGameObject *o){
02633     gameObjectsInactive.Remove(o, o->inactiveID);
02634 }
02635 
02636 
02637 /*
02638 
02639 
02640 void eEdge::calc_Len() const{
02641   REAL len2=(*p[0] - *p[1]).NormSquared();
02642   *reinterpret_cast<REAL *>(reinterpret_cast<void *>(&len))=sqrt(len2);
02643 }
02644 
02645 
02646 void ePoint::InsertIntoGrid(){
02647   if (f.Len()==0){
02648     for(int i=eFace::faces.Len()-1;i>=0;i--)
02649       
02650       if (eFace::faces(i)->IsInside(*this)){
02651         for(int j=0;j<=2;j++){
02652           if (*eFace::faces(i)->p[j]==*this){
02653             ePoint *same=eFace::faces(i)->p[j];
02654             same->Replace(this);
02655             delete same;
02656             return;
02657           }
02658         }
02659         eFace::faces(i)->p[0]->DrawLineTo(this);
02660         return;
02661       }
02662   }
02663 }
02664 
02665 
02666 
02667       eHalfEdge *run  = start->edge;
02668       tASSERT(run);
02669       const eHalfEdge *stop = run;
02670 
02671       do
02672         {
02673           
02674           run = run->other->next;
02675         }
02676       while (stop != start);
02677 
02678 */
02679 
02680 
02681 eGrid::eGrid()
02682         :        requestCleanup(false),
02683         A(NULL), B(NULL), C(NULL),
02684         a(NULL), b(NULL), c(NULL),
02685         maxNormSquared(-1),
02686         base(100,100)
02687 {
02688     currentGrid = this;
02689 }
02690 
02691 
02692 eGrid::~eGrid()
02693 {
02694     if (currentGrid == this)
02695         currentGrid = NULL;
02696 }
02697 
02698 static REAL s_rangeSquared;
02699 static eFace *s_start = NULL;
02700 static eFace *s_processed = NULL;
02701 
02702 // call WallProcessor for all walls around pos
02703 static void ProcessWallsRecursive               ( eGrid::WallProcessor*         proc,
02704                                      const eCoord&                              pos     ,
02705                                      REAL                                               range,
02706                                      eFace*                                     start,
02707                                      eFace*                                     from,
02708                                      int                                                depthLeft )
02709 {
02710     tASSERT( start );
02711 
02712     if ( depthLeft < 0 )
02713         return;
02714 
02715     if ( start->nextProcessed )
02716         return;
02717 
02718     start->nextProcessed = s_processed;
02719     s_processed = start;
02720 
02721 
02722     eHalfEdge* leave = start->Edge();
02723     for ( int i = 2; i>=0; --i )
02724     {
02725         if ( leave->Other() && leave->Other()->Face() )
02726         {
02727             eCoord normal = leave->Vec().Conj();
02728             REAL normalLen = normal.Norm();
02729             if ( normalLen <= 0 )
02730                 continue;
02731             normal *= 1/ normalLen;
02732 
02733             eCoord Pos1 = normal.Turn( *leave->Point() - pos );
02734             eCoord Pos2 = normal.Turn( *leave->Other()->Point() - pos );
02735 
02736             tASSERT( fabs( Pos1.y - Pos2.y ) <= fabs( Pos1.y ) + fabs ( Pos2.y ) + .1f * .1f );
02737 
02738             // start test: the line through the edge "leave" must come closer than "range" to "pos"
02739             // and we have to be on the correct side
02740             if ( Pos1.y > -range && Pos1.y <= range*.01f )
02741             {
02742                 // check for real hit
02743                 if ( Pos1.x * Pos2.x < 0 ||
02744                         Pos1.NormSquared() < s_rangeSquared ||
02745                         Pos2.NormSquared() < s_rangeSquared )
02746                 {
02747                     // recurse
02748                     if ( NULL == leave->Other()->Face()->nextProcessed )
02749                         ProcessWallsRecursive( proc, pos, range, leave->Other()->Face(), start , depthLeft - 1 );
02750 
02751                     // process this wall
02752                     if ( leave->GetWall() )
02753                         (*proc) ( leave->GetWall() );
02754                     if ( leave->Other()->GetWall() )
02755                         (*proc) ( leave->Other()->GetWall() );
02756                 }
02757             }
02758         }
02759         leave = leave->Next();
02760     }
02761 }
02762 
02763 // call WallProcessor for all walls around pos
02764 void eGrid::ProcessWallsInRange         ( WallProcessor*        proc,
02765                                    const eCoord&                pos     ,
02766                                    REAL                         range,
02767                                    eFace*                       start )
02768 {
02769     int i;
02770 
02771     start = FindSurroundingFace( pos, start );
02772     if ( !start )
02773         return;
02774 
02775     s_rangeSquared = range * range;
02776     s_start = start;
02777     s_processed = start;
02778 
02779     // process the gridded walls
02780     ProcessWallsRecursive( proc, pos, range, start, NULL, 100 );
02781 
02782 #ifdef DEBUG_OLD
02783     // make sure all walls were processed
02784 
02785     // process the not gridded walls
02786     for ( i = edges.Len()-1; i>=0; --i )
02787     {
02788         const eHalfEdge *leave = edges(i);
02789 
02790         if ( !leave->Other() || !leave->Face() || !leave->Other()->Face() )
02791             continue;
02792 
02793         eCoord normal = leave->Vec().Conj();
02794         REAL normalLen = normal.Norm();
02795         if ( normalLen <= 0 )
02796             continue;
02797         normal *= 1/ normalLen;
02798 
02799         eCoord Pos1 = normal.Turn( *leave->Point() - pos );
02800         eCoord Pos2 = normal.Turn( *leave->Other()->Point() - pos );
02801 
02802         tASSERT( fabs( Pos1.y - Pos2.y ) <= fabs( Pos1.y + Pos2.y +.1f ) * .1f );
02803 
02804         // start test: the line through the edge "leave" must come closer than "range" to "pos"
02805         if ( Pos1.y < range && Pos1.y > -range )
02806         {
02807             // check for real hit
02808             if ( Pos1.x * Pos2.x < 0 ||
02809                     Pos1.NormSquared() < s_rangeSquared ||
02810                     Pos2.NormSquared() < s_rangeSquared )
02811             {
02812                 if ( !leave->Face()->nextProcessed || !leave->Other()->Face()->nextProcessed )
02813                 {
02814                     st_Breakpoint();
02815                 }
02816 
02817                 if ( leave->Face()->nextProcessed &&  !leave->Other()->Face()->nextProcessed )
02818                 {
02819                     while ( s_processed != start )
02820                     {
02821                         eFace* next = s_processed->nextProcessed;
02822                         s_processed->nextProcessed = NULL;
02823                         s_processed = next;
02824                     }
02825 
02826                     start->nextProcessed = NULL;
02827                     s_processed = leave->Face();
02828                     leave->Face()->nextProcessed = start;
02829 
02830                     st_Breakpoint();
02831 
02832                     ProcessWallsRecursive( proc, pos, range, leave->Face(), NULL, 100 );
02833 
02834                     while ( s_processed != start )
02835                     {
02836                         eFace* next = s_processed->nextProcessed;
02837                         s_processed->nextProcessed = NULL;
02838                         s_processed = next;
02839                     }
02840 
02841                     start->nextProcessed = NULL;
02842                     s_processed = NULL;
02843 
02844                 }
02845             }
02846         }
02847     }
02848 #endif
02849 
02850     while ( s_processed && s_processed != start )
02851     {
02852         eFace* next = s_processed->nextProcessed;
02853         s_processed->nextProcessed = NULL;
02854         s_processed = next;
02855     }
02856 
02857     start->nextProcessed = NULL;
02858     s_processed = NULL;
02859 
02860     // process the not gridded walls
02861     for ( i = wallsNotYetInserted.Len()-1; i>=0; --i )
02862     {
02863         eWall* w= wallsNotYetInserted(i);
02864         const eHalfEdge *leave = w->Edge();
02865 
02866         eCoord normal = leave->Vec().Conj();
02867         REAL normalLen = normal.Norm();
02868         if ( normalLen <= 0 )
02869             continue;
02870         normal *= 1/ normalLen;
02871 
02872         eCoord Pos1 = normal.Turn( *leave->Point() - pos );
02873         eCoord Pos2 = normal.Turn( *leave->Other()->Point() - pos );
02874 
02875         tASSERT( fabs( Pos1.y - Pos2.y ) <= fabs( Pos1.y + Pos2.y +.1f ) * .1f );
02876 
02877         // start test: the line through the edge "leave" must come closer than "range" to "pos"
02878         if ( Pos1.y < range && Pos1.y > -range )
02879         {
02880             // check for real hit
02881             if ( Pos1.x * Pos2.x < 0 ||
02882                     Pos1.NormSquared() < s_rangeSquared ||
02883                     Pos2.NormSquared() < s_rangeSquared )
02884             {
02885                 (*proc) ( w );
02886             }
02887         }
02888 
02889     }
02890 }
02891 

Generated on Sat Mar 15 22:55:44 2008 for Armagetron Advanced by  doxygen 1.5.4