/*****************************************************************************
 * $Id: eng_sort.cc,v 1.9 2006/11/17 06:30:35 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Class containing sorted Objects in back-to-front order.
 * @verbatim
 * ------------------------------------------------------------------------------
 * Choice of sorting algorithms, net performance:
 * Two sorting algorithms were chosen: std::sort() and std::multimap.
 * STL implements them as quicksort and red/black tree, resp.
 * When user selects high LOD, sorting must be done every frame.
 * std::sort() on a STL vector is 25x faster than inserting to a std::multimap (gcc 4.1).
 * But at lower LOD, frames can be skipped, so std::multimap is used, because
 * it yields faster net performance from its ability to quickly remove
 * invisible Objects which reduces calls to visibility tests (slow operation).
 * Side-note: Insertion sort is the fastest for "almost sorted" piles.
 * ------------------------------------------------------------------------------
 * Sorting by distance, Object::GetDistance():
 * By intent, the value from Object::GetDistance() is used directly for sorting.
 * Unlike visibility testing, Object's radius isn't a factor for sorting.
 * Objects are supposed to calculate, on their own, their farthest eye Z coordinate.
 * This is for flexibility.  Objects have specific shapes.  Eg, the sort routine
 * shouldn't add radius (like visibility tests do) to a Billboard because
 * it is flat in the context of distance sorting.
 * ------------------------------------------------------------------------------
 * Preventing invalid pointers to Objects or too remote Objects in sorted pile:
 * They're removed from the sorted pile by "sort disrupted" events.
 * As the Locus moves, outgoing Quadrants are "shrunk" by destroying their Objects.
 * The two main kinds of Objects are Fixed and Dyna.
 * Fixed objects only transition out of the sorted pile when the Locus moves.
 * Dynas additionally can transition out of the sorted pile if they transition
 * into a Quadrant outside the Locus (Dynas are too remote and shouldn't be drawn).
 * ------------------------------------------------------------------------------
 * Subtlety: Objects contained by ObjectGroups (and associated shadow Quadrants)
 * are directly excluded by (hidden from) the render loop.  Since only
 * the visibility of the ObjectGroup was tested here, this is why
 * grouped Objects still need to call Visible() in their Draw() method.
 * ------------------------------------------------------------------------------
 * Subtlety: Depends on Locus separating Omnis and non-Omnis and linking Omnis
 * into one special Quadrant (old way had the same Omnis linked in every Quadrant
 * which required sorting/rendering to filter-out duplicate Omnis to render them once).
 * ------------------------------------------------------------------------------
 * @endverbatim
 *//*
 * LEGAL:   COPYRIGHT (C) 2006 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define ENG_SORT_CC 1
#include "eng.hh"
#include "gfx_sort.hh"
#include "eng_sort.hh"

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////  Sorter  ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

Sorter* Sorter::msInstance;  // TODO per-View

/*****************************************************************************
 * Ctor/dtor.
 *****************************************************************************/
Sorter::Sorter( void )
:   mSortAlgorithm(eSortAlgorithm_TREE),  // default to tree (faster unless max LOD)
	mSortCommand(eSortCommand_SORT)    
{
	// Listen for events that disrupt the sorted Objects.
	gEngineEvent.mEyeChange.Listen( Listener_Sorter_EyeChange );
	gEngineEvent.mLocusChange.Listen( Listener_Sorter_LocusChange );
    // Reuse the same listener function for all Dyna events.
	gEngineEvent.mDynaChangeConstructing.Listen( Listener_Sorter_DynaChange );
	gEngineEvent.mDynaChangeDestructing.Listen(  Listener_Sorter_DynaChange );
	gEngineEvent.mDynaChangeQuadrant.Listen(     Listener_Sorter_DynaChange );
	gEngineEvent.mVisibilityChange.Listen( Listener_Sorter_VisibilityChange );
	gEngineEvent.mLodUserChange.Listen( Listener_Sorter_LodUserChange );

	msInstance = this;
}
Sorter::~Sorter()
{
	// (program is exiting: gEngineEvent is gone)
	msInstance = NULL;
}

/*****************************************************************************
 * Get instance of Sorter for the current 3D View.
 *****************************************************************************/
Sorter&
Sorter::GetInstance( void )
{
	return *msInstance;
}

/*****************************************************************************
 * Sort Objects in Locus which are visible.
 * Switches to faster sorting algorithm according to LOD.
 * @return True if sorting was done.
 *****************************************************************************/
bool
Sorter::Sort( void )
{
DEBUG_CODE( gEng.SetCurrentObjectName("") );

    // Skip sorting unless a "sort disrupted" event occurred such as:
    // - Eye did a pitch/yaw (roll doesn't affect Z distance)
    // - Locus changed (a different set of quadrants must be sorted)
	if ( mSortCommand == eSortCommand_SKIP )
	{
		ENGINE_STATS_CODE( ++gEng.mStats.mSortingSkip; )
		return false;
	}

	// Clear the pile.
    if ( mSortAlgorithm == eSortAlgorithm_TREE )
    	mPileTree.clear();
    else
    {
        mPileQuicksort.clear();
        mPileQuicksort.reserve( gWorld.mLocus.GetObjectCnt() + 100 );
    }

	// Build a container to be sorted.
	// It shall have pointers to visible Objects in the Locus.
    // For each Quadrant in the Locus.
	for ( QuadrantItr itrQuadrant = gWorld.mLocus.mQuadrants.begin();
          itrQuadrant != gWorld.mLocus.mQuadrants.end();
          ++itrQuadrant )
	{
		// Skip non-visible Quadrants.
		QuadrantPtr quadrant = *itrQuadrant;  CHECK_TYPESIG( quadrant, TYPESIG_QUADRANT );
		if ( quadrant->IfVisible() )
		{
			// For each Object in this visible Quadrant.
			const Dlist<Object>& objDlist = quadrant->GetObjectDlist();
			for ( const Dlink<Object>* dlink = objDlist.ForStart();
			      objDlist.ForTest(dlink);
			      objDlist.ForNext(dlink) )
			{
				// Put this Object into sorted pile.
				ObjectPtr obj = dlink->mObj;
CHECK_TYPESIG( obj, TYPESIG_OBJECT );
DEBUG_CODE( gEng.SetCurrentObjectName( obj->GetName() ); )
                const fp distance = obj->GetDistance();
                // Test distance first to bypass the slow visibility test.
				if ( distance >= MIN_OBJECT_SORT_DISTANCE  // if in front
                  && obj->Visible() )
				{
                    if ( mSortAlgorithm == eSortAlgorithm_TREE )
    					mPileTree.insert( make_pair( distance, obj ) );
                    else
    					mPileQuicksort.push_back( DistObj( distance, obj ) );
				}
			}
		}
	}
DEBUG_CODE( gEng.SetCurrentObjectName("") );

    // Sort STL vector using quicksort (unless pile is a STL multimap).
    if ( mSortAlgorithm == eSortAlgorithm_QUICKSORT )
        std::sort( mPileQuicksort.begin(), mPileQuicksort.end() );

	// Skip sorting on the next frames (until disrupted).
    if ( ! gEng.IfMaxLodUser() )
        mSortCommand = eSortCommand_SKIP;

	ENGINE_STATS_CODE( ++gEng.mStats.mSortingDone; )
	ASSERT( mPileTree.size() <= gWorld.mLocus.GetObjectCnt() );
	ASSERT( mPileQuicksort.size() <= gWorld.mLocus.GetObjectCnt() );

    return true;  // sorting was done
}

/*****************************************************************************
 * Render sorted Objects in Locus.
 * The sorted pile contains only visible Objects.
 *****************************************************************************/
void
Sorter::Draw( void )
{
DEBUG_CODE( gEng.SetCurrentObjectName(""); )

    // Sort Objects.  Sorting may be skipped on some frames.
    const bool freshSort = Sort();

    // Render sorted Objects.
    //
    // Sorting Objects in STL vector using std::sort() is faster than
    // inserting into a STL multimap, but here their advantages reverse:
    // STL multimap can quickly remove invisible Objects to skip redundant visibility tests.
    ENGINE_STATS_CODE( gEng.mStats.mObjectsDrawn = 0; )
    if ( mSortAlgorithm == eSortAlgorithm_TREE )
    {
        for ( PileTreeIterator itr = mPileTree.begin(); itr != mPileTree.end(); /*NOP*/ )
    	{
    		// Render this Object.
            // If this is a frame after sorting was done, visibility tests
            // have become stale.  Recompute visibility tests to reduce overdraw.
    		ObjectPtr obj = GetObject( itr );
CHECK_TYPESIG( obj, TYPESIG_OBJECT );
DEBUG_CODE( gEng.SetCurrentObjectName( obj->GetName() ); )
            if ( freshSort || obj->Visible() )
            {
        		obj->Draw();
                ++itr;
                ENGINE_STATS_CODE( ++gEng.mStats.mObjectsDrawn; )
            }
            else
            {
                // This Object has turned invisible.  Remove it to skip
                // calling its Visible() again (it'd return false henceforth).
                // STL subtlety: Advance the iterator to the following Object
                // (keeping it valid) before erasing this Object.
                PileTreeIterator itrErase = itr;
                ++itr;
                mPileTree.erase( itrErase );
            }
        }
    }
    else // quicksort
    {
        for ( PileQuicksortIterator itr = mPileQuicksort.begin(); itr != mPileQuicksort.end(); ++itr )
    	{
    		ObjectPtr obj = GetObject( itr );
CHECK_TYPESIG( obj, TYPESIG_OBJECT );
DEBUG_CODE( gEng.SetCurrentObjectName( obj->GetName() ); )
            if ( freshSort || obj->Visible() )
            {
        		obj->Draw();
                ENGINE_STATS_CODE( ++gEng.mStats.mObjectsDrawn; )
            }
            // Removing an invisible Object from STL sequence container is too slow.
            // Must leave it even though it'll cause a redundant visibility test
            // on subsequent skipped frames (doesn't matter if sorting every frame).
        }
    }

#if GFXSYS_OPENGL
	// Boost FPS by posting redisplay (continuous rendering).
	if ( gEng.GetSpeed() >= eSpeed_FAST ) glutPostRedisplay();
#endif

DEBUG_CODE( gEng.SetCurrentObjectName(""); )
}

/*****************************************************************************
 * When an event occurs that disrupts the sorted Objects,
 * remember to re-sort Objects on the next frame.
 *****************************************************************************/
void
Sorter::Disrupt( void )
{
    mSortCommand = eSortCommand_SORT;  // force re-sorting
}

/*****************************************************************************
 * Switch the sort algorithm.
 *****************************************************************************/
void
Sorter::SetAlgorithm( eSortAlgorithm sortAlgorithm )
{
	if ( mSortAlgorithm != sortAlgorithm )  // no change?
	{
		mSortAlgorithm = sortAlgorithm;
		Disrupt();  // switching algorithm is a disruption
	}
}

/*****************************************************************************
 * Listen for events that disrupt the sorted Objects:
 * - changes to view angle (Eye rotation) which affects distances of Objects
 * - construction/destruction of Objects
 * - Locus moving into other Quadrants (changes presence of Objects in pile).
 *****************************************************************************/
static void
Listener_Sorter_EyeChange( EngineEvents::eEyeChange eyeChange )
{
	// Rolling and translation don't affect relative sort order.
    // All other cases (pitching, yawing, arbitrary changes to Eye's matrix).
	switch ( eyeChange )
	{
		case EngineEvents::eEyeChange_ROLL:
        case EngineEvents::eEyeChange_TRANSLATE_X_POS:
        case EngineEvents::eEyeChange_TRANSLATE_Y_POS:
        case EngineEvents::eEyeChange_TRANSLATE_Z_POS:
        case EngineEvents::eEyeChange_TRANSLATE_X_NEG:
        case EngineEvents::eEyeChange_TRANSLATE_Y_NEG:
            // NOP.  These cases don't disrupt the sorted pile.
		break;

		default:
		case EngineEvents::eEyeChange_PITCH:
		case EngineEvents::eEyeChange_YAW:
        case EngineEvents::eEyeChange_TRANSLATE_Z_NEG:
            Sorter::GetInstance().Disrupt();
		break;
	}
}
static void
Listener_Sorter_LocusChange( void )
{
    Sorter::GetInstance().Disrupt();
}
static void 
Listener_Sorter_DynaChange( DynaPtr dyna )
{
    Sorter::GetInstance().Disrupt();
}
static void 
Listener_Sorter_VisibilityChange( void )
{
    Sorter::GetInstance().Disrupt();
}
static void 
Listener_Sorter_LodUserChange( void )
{
    // Switch to appropriate sort algorithm.
	// Max LOD requires sorting every frame: quicksort is fastest for this case.
    if ( gEng.IfMaxLodUser() )
		Sorter::GetInstance().SetAlgorithm( Sorter::eSortAlgorithm_QUICKSORT );
	else
		Sorter::GetInstance().SetAlgorithm( Sorter::eSortAlgorithm_TREE );
}

/*****************************************************************************
 * Debug: Press 'S' on keyboard.
 *****************************************************************************/
void
SorterCycleSortAlgorithm( void )
{
	static Sorter::eSortAlgorithm algorithm = Sorter::eSortAlgorithm_TREE;
	if ( algorithm == Sorter::eSortAlgorithm_TREE )
	{   // tree --> quicksort
		*gStreamDebug << "sort algorithm: quicksort \n";
		Sorter::GetInstance().SetAlgorithm( (algorithm = Sorter::eSortAlgorithm_QUICKSORT) );
	}
	else
	{   // quicksort --> tree
		*gStreamDebug << "sort algorithm: tree \n";
		Sorter::GetInstance().SetAlgorithm( (algorithm = Sorter::eSortAlgorithm_TREE) );
	}
}
