DOOM-3-BFG/neo/renderer/BoundsTrack.cpp

/*
===========================================================================

Doom 3 BFG Edition GPL Source Code
Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 

This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").  

Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Doom 3 BFG Edition Source Code.  If not, see <http://www.gnu.org/licenses/>.

In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code.  If not, please request a copy in writing from id Software at the address below.

If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.

===========================================================================
*/

#pragma hdrstop
#include "../idlib/precompiled.h"


#undef min			// windef.h macros
#undef max

#include "BoundsTrack.h"

/*

We want to do one SIMD compare on 8 short components and know that the bounds
overlap if all 8 tests pass

*/

// shortBounds_t is used to track the reference bounds of all entities in a
// cache-friendly and easy to compare way.
//
// To allow all elements to be compared with a single comparison sense, the maxs
// are stored as negated values.
//
// We may need to add a global scale factor to this if there are intersections
// completely outside +/-32k
struct shortBounds_t {
	shortBounds_t() {
		SetToEmpty();
	}

	shortBounds_t( const idBounds & b  ) {
		SetFromReferenceBounds( b );
	}

	short	b[2][4];		// fourth element is just for padding

	idBounds ToFloatBounds() const {
		idBounds	f;
		for ( int i = 0 ; i < 3 ; i++ ) {
			f[0][i] = b[0][i];
			f[1][i] = -b[1][i];
		}
		return f;
	}

	bool	IntersectsShortBounds( shortBounds_t & comp ) const {
		shortBounds_t test;
		comp.MakeComparisonBounds( test );
		return IntersectsComparisonBounds( test );
	}

	bool	IntersectsComparisonBounds( shortBounds_t & test ) const {
		// this can be a single ALTIVEC vcmpgtshR instruction
		return test.b[0][0] > b[0][0]
			&& test.b[0][1] > b[0][1]
			&& test.b[0][2] > b[0][2]
			&& test.b[0][3] > b[0][3]
			&& test.b[1][0] > b[1][0]
			&& test.b[1][1] > b[1][1]
			&& test.b[1][2] > b[1][2]
			&& test.b[1][3] > b[1][3];
	}

	void MakeComparisonBounds( shortBounds_t & comp ) const {
		comp.b[0][0] = -b[1][0];
		comp.b[1][0] = -b[0][0];
		comp.b[0][1] = -b[1][1];
		comp.b[1][1] = -b[0][1];
		comp.b[0][2] = -b[1][2];
		comp.b[1][2] = -b[0][2];
		comp.b[0][3] = 0x7fff;
		comp.b[1][3] = 0x7fff;
	}

	void SetFromReferenceBounds( const idBounds & set ) {
		// the maxs are stored negated
		for ( int i = 0 ; i < 3 ; i++ ) {
			int minv = floor( set[0][i] );
			b[0][i] = std::max( -32768, minv );
			int maxv = -ceil( set[1][i] );
			b[1][i] = std::min( 32767, maxv );
		}
		b[0][3] = b[1][3] = 0;
	}

	void SetToEmpty() {
		// this will always fail the comparison
		for ( int i = 0 ; i < 2 ; i++ ) {
			for ( int j = 0 ; j < 4 ; j++ ) {
				b[i][j] = 0x7fff;
			}
		}
	}
};



// pure function
int FindBoundsIntersectionsTEST( 
	const shortBounds_t			testBounds,
	const shortBounds_t * const	boundsList,
	const int					numBounds,
	int * const					returnedList ) {

	int hits = 0;
	idBounds	testF = testBounds.ToFloatBounds();
	for ( int i = 0 ; i < numBounds ; i++ ) {
		idBounds	listF = boundsList[i].ToFloatBounds();
		if ( testF.IntersectsBounds( listF ) ) {
			returnedList[hits++] = i;
		}
	}
	return hits;
}

// pure function
int FindBoundsIntersectionsSimSIMD( 
	const shortBounds_t			testBounds,
	const shortBounds_t * const	boundsList,
	const int					numBounds,
	int * const					returnedList ) {

	shortBounds_t	compareBounds;
	testBounds.MakeComparisonBounds( compareBounds );

	int hits = 0;
	for ( int i = 0 ; i < numBounds ; i++ ) {
		const shortBounds_t & listBounds = boundsList[i];
		bool	compare[8];
		int		count = 0;
		for ( int j = 0 ; j < 8 ; j++ ) {
			if ( ((short *)&compareBounds)[j] >= ((short *)&listBounds)[j] ) {
				compare[j] = true;
				count++;
			} else {
				compare[j] = false;
			}
		}
		if ( count == 8 ) {
			returnedList[hits++] = i;
		}
	}
	return hits;
}



idBoundsTrack::idBoundsTrack() {
	boundsList = (shortBounds_t *)Mem_Alloc( MAX_BOUNDS_TRACK_INDEXES * sizeof( *boundsList ), TAG_RENDER );
	ClearAll();
}

idBoundsTrack::~idBoundsTrack() {
	Mem_Free( boundsList );
}

void idBoundsTrack::ClearAll() {
	maxIndex = 0;
	for ( int i = 0 ; i < MAX_BOUNDS_TRACK_INDEXES ; i++ ) {
		ClearIndex( i );
	}
}

void	idBoundsTrack::SetIndex( const int index, const idBounds & bounds ) {
	assert( (unsigned)index < MAX_BOUNDS_TRACK_INDEXES );
	maxIndex = std::max( maxIndex, index+1);
	boundsList[index].SetFromReferenceBounds( bounds );
}

void	idBoundsTrack::ClearIndex( const int index ) {
	assert( (unsigned)index < MAX_BOUNDS_TRACK_INDEXES );
	boundsList[index].SetToEmpty();
}

int		idBoundsTrack::FindIntersections( const idBounds & testBounds, int intersectedIndexes[ MAX_BOUNDS_TRACK_INDEXES ] ) const {
	const shortBounds_t	shortTestBounds( testBounds );
	return FindBoundsIntersectionsTEST( shortTestBounds, boundsList, maxIndex, intersectedIndexes );
}

void	idBoundsTrack::Test() {
	ClearAll();
	idRandom	r;

	for ( int i = 0 ; i < 1800 ; i++ ) {
		idBounds b;
		for ( int j = 0 ; j < 3 ; j++ ) {
			b[0][j] = r.RandomInt( 20000 ) - 10000;
			b[1][j] = b[0][j] + r.RandomInt( 1000 );
		}
		SetIndex( i, b );
	}

	const idBounds testBounds( idVec3( -1000, 2000, -3000 ), idVec3( 1500, 4500, -500 ) );
	SetIndex( 1800, testBounds );
	SetIndex( 0, testBounds );

	const shortBounds_t	shortTestBounds( testBounds );

	int intersectedIndexes1[ MAX_BOUNDS_TRACK_INDEXES ];
	const int numHits1 = FindBoundsIntersectionsTEST( shortTestBounds, boundsList, maxIndex, intersectedIndexes1 );

	int intersectedIndexes2[ MAX_BOUNDS_TRACK_INDEXES ];
	const int numHits2 = FindBoundsIntersectionsSimSIMD( shortTestBounds, boundsList, maxIndex, intersectedIndexes2 );
	idLib::Printf( "%i intersections\n", numHits1 );
	if ( numHits1 != numHits2 ) {
		idLib::Printf( "different results\n" );
	} else {
		for ( int i = 0 ; i < numHits1 ; i++ ) {
			if ( intersectedIndexes1[i] != intersectedIndexes2[i] ) {
				idLib::Printf( "different results\n" );
				break;
			}
		}
	}

	// run again for debugging failure
	FindBoundsIntersectionsTEST( shortTestBounds, boundsList, maxIndex, intersectedIndexes1 );
	FindBoundsIntersectionsSimSIMD( shortTestBounds, boundsList, maxIndex, intersectedIndexes2 );

	// timing
	const int64 start = Sys_Microseconds();
	for ( int i = 0 ; i < 40 ; i++ ) {
		FindBoundsIntersectionsSimSIMD( shortTestBounds, boundsList, maxIndex, intersectedIndexes2 );
	}
	const int64 stop = Sys_Microseconds();
	idLib::Printf( "%i microseconds for 40 itterations\n", stop - start );
}



class interactionPair_t {
	int		entityIndex;
	int		lightIndex;
};

/*

keep a sorted list of static interactions and interactions already generated this frame?

determine if the light needs more exact culling because it is rotated or a spot light
for each entity on the bounds intersection list
	if entity is not directly visible, determine if it can cast a shadow into the view
		if the light center is in-frustum 
			and the entity bounds is out-of-frustum, it can't contribue
		else the light center is off-frustum
			if any of the view frustum planes can be moved out to the light center and the entity bounds is still outside it, it can't contribute
	if a static interaction exists
		continue
	possibly perform more exact refernce bounds to rotated or spot light

	create an interaction pair and add it to the list


all models will have an interaction with light -1 for ambient surface
sort the interaction list by model
do
	if the model is dynamic, create it
	add the ambient surface and skip interaction -1
	for all interactions
		check for static interaction
		check for current-frame interaction
		else create shadow for this light

*/