2
// Copyright � 1997 - 2002, Paul C. Gregory
4
// Contact: pgregory@aqsis.org
6
// This library is free software; you can redistribute it and/or
7
// modify it under the terms of the GNU General Public
8
// License as published by the Free Software Foundation; either
9
// version 2 of the License, or (at your option) any later version.
11
// This library is distributed in the hope that it will be useful,
12
// but WITHOUT ANY WARRANTY; without even the implied warranty of
13
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14
// General Public License for more details.
16
// You should have received a copy of the GNU General Public
17
// License along with this library; if not, write to the Free Software
18
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22
\brief Implements the hierarchical occlusion culling class.
23
\author Andy Gill (billybobjimboy@users.sf.net)
28
#ifdef AQSIS_SYSTEM_WIN32
29
#pragma warning(disable : 4786)
32
#include "occlusion.h"
34
#include "imagebuffer.h"
40
START_NAMESPACE( Aqsis )
42
TqInt CqOcclusionTree::m_Tab = 0;
44
CqOcclusionTree::CqOcclusionTree(TqInt dimension)
45
: m_Parent(0), m_Dimension(dimension)
47
TqChildArray::iterator child = m_Children.begin();
48
for(; child != m_Children.end(); ++child)
52
CqOcclusionTree::~CqOcclusionTree()
54
TqChildArray::iterator child = m_Children.begin();
55
for(; child != m_Children.end(); ++child)
66
CqOcclusionTree::SplitNode(CqOcclusionTreePtr& a, CqOcclusionTreePtr& b)
68
SortElements(m_Dimension);
70
TqInt samplecount = m_SampleIndices.size();
71
TqInt median = samplecount / 2;
73
// Create the children nodes.
74
a = CqOcclusionTreePtr(new CqOcclusionTree());
75
b = CqOcclusionTreePtr(new CqOcclusionTree());
77
a->m_MinSamplePoint = m_MinSamplePoint;
78
b->m_MinSamplePoint = m_MinSamplePoint;
79
a->m_MaxSamplePoint = m_MaxSamplePoint;
80
b->m_MaxSamplePoint = m_MaxSamplePoint;
81
TqInt newdim = ( m_Dimension + 1 ) % Dimensions();
82
a->m_Dimension = b->m_Dimension = newdim;
84
TqFloat dividingplane = CqBucket::ImageElement(m_SampleIndices[median].first).SampleData(m_SampleIndices[median].second).m_Position[m_Dimension];
86
a->m_MaxSamplePoint[m_Dimension] = dividingplane;
87
b->m_MinSamplePoint[m_Dimension] = dividingplane;
89
TqFloat minTime = m_MaxTime, maxTime = m_MinTime;
90
TqInt minDofIndex = m_MaxDofBoundIndex, maxDofIndex = m_MinDofBoundIndex;
91
TqFloat minDetailLevel = m_MaxDetailLevel, maxDetailLevel = m_MinDetailLevel;
94
for(i = 0; i<median; ++i)
96
a->m_SampleIndices.push_back(m_SampleIndices[i]);
97
const SqSampleData& sample = CqBucket::ImageElement(m_SampleIndices[i].first).SampleData(m_SampleIndices[i].second);
98
minTime = MIN(minTime, sample.m_Time);
99
maxTime = MAX(maxTime, sample.m_Time);
100
minDofIndex = MIN(minDofIndex, sample.m_DofOffsetIndex);
101
maxDofIndex = MAX(maxDofIndex, sample.m_DofOffsetIndex);
102
minDetailLevel = MIN(minDetailLevel, sample.m_DetailLevel);
103
maxDetailLevel = MAX(maxDetailLevel, sample.m_DetailLevel);
105
a->m_MinTime = minTime;
106
a->m_MaxTime = maxTime;
107
a->m_MinDofBoundIndex = minDofIndex;
108
a->m_MaxDofBoundIndex = maxDofIndex;
109
a->m_MinDetailLevel = minDetailLevel;
110
a->m_MaxDetailLevel = maxDetailLevel;
112
minTime = m_MaxTime, maxTime = m_MinTime;
113
minDofIndex = m_MaxDofBoundIndex, maxDofIndex = m_MinDofBoundIndex;
114
minDetailLevel = m_MaxDetailLevel, maxDetailLevel = m_MinDetailLevel;
115
for(; i<samplecount; ++i)
117
b->m_SampleIndices.push_back(m_SampleIndices[i]);
118
const SqSampleData& sample = CqBucket::ImageElement(m_SampleIndices[i].first).SampleData(m_SampleIndices[i].second);
119
minTime = MIN(minTime, sample.m_Time);
120
maxTime = MAX(maxTime, sample.m_Time);
121
minDofIndex = MIN(minDofIndex, sample.m_DofOffsetIndex);
122
maxDofIndex = MAX(maxDofIndex, sample.m_DofOffsetIndex);
123
minDetailLevel = MIN(minDetailLevel, sample.m_DetailLevel);
124
maxDetailLevel = MAX(maxDetailLevel, sample.m_DetailLevel);
126
b->m_MinTime = minTime;
127
b->m_MaxTime = maxTime;
128
b->m_MinDofBoundIndex = minDofIndex;
129
b->m_MaxDofBoundIndex = maxDofIndex;
130
b->m_MinDetailLevel = minDetailLevel;
131
b->m_MaxDetailLevel = maxDetailLevel;
134
void CqOcclusionTree::ConstructTree()
136
std::deque<CqOcclusionTreePtr> ChildQueue;
137
ChildQueue.push_back(this/*shared_from_this()*/);
139
TqInt NonLeafCount = NumSamples() >= 1 ? 1 : 0;
140
TqInt split_counter = 0;
142
while (NonLeafCount > 0 && ChildQueue.size() < s_ChildrenPerNode)
144
CqOcclusionTreePtr old = ChildQueue.front();
145
ChildQueue.pop_front();
146
if (old->NumSamples() > 1)
151
CqOcclusionTreePtr a;
152
CqOcclusionTreePtr b;
153
old->SplitNode(a, b);
157
ChildQueue.push_back(a);
158
if (a->NumSamples() > 1)
165
ChildQueue.push_back(b);
166
if (b->NumSamples() > 1)
172
if(split_counter >1 )
176
TqChildArray::iterator ii;
177
std::deque<CqOcclusionTreePtr>::const_iterator jj;
178
for (ii = m_Children.begin(), jj = ChildQueue.begin(); jj != ChildQueue.end(); ++jj)
180
// Check if the child actually has any samples, ignore it if no.
181
if( (*jj)->NumSamples() > 0)
184
(*ii)->m_Parent = this/*shared_from_this()*/;
185
if ((*ii)->NumSamples() > 1)
187
(*ii)->ConstructTree();
193
while (ii != m_Children.end())
205
void CqOcclusionTree::InitialiseBounds()
207
if (m_SampleIndices.size() < 1)
210
const SqSampleData& sample = CqBucket::ImageElement(m_SampleIndices[0].first).SampleData(m_SampleIndices[0].second);
211
TqFloat minXVal = sample.m_Position.x();
212
TqFloat maxXVal = minXVal;
213
TqFloat minYVal = sample.m_Position.y();
214
TqFloat maxYVal = minYVal;
215
TqFloat minTime = sample.m_Time;
216
TqFloat maxTime = minTime;
217
TqInt minDofIndex = sample.m_DofOffsetIndex;
218
TqInt maxDofIndex = minDofIndex;
219
TqFloat minDetailLevel = sample.m_DetailLevel;
220
TqFloat maxDetailLevel = minDetailLevel;
221
std::vector<std::pair<TqInt, TqInt> >::iterator i;
222
for(i = m_SampleIndices.begin()+1; i!=m_SampleIndices.end(); ++i)
224
const SqSampleData& sample = CqBucket::ImageElement(i->first).SampleData(i->second);
225
minXVal = MIN(minXVal, sample.m_Position.x());
226
maxXVal = MAX(maxXVal, sample.m_Position.x());
227
minYVal = MIN(minYVal, sample.m_Position.y());
228
maxYVal = MAX(maxYVal, sample.m_Position.y());
229
minTime = MIN(minTime, sample.m_Time);
230
maxTime = MAX(maxTime, sample.m_Time);
231
minDofIndex = MIN(minDofIndex, sample.m_DofOffsetIndex);
232
maxDofIndex = MAX(maxDofIndex, sample.m_DofOffsetIndex);
233
minDetailLevel = MIN(minDetailLevel, sample.m_DetailLevel);
234
maxDetailLevel = MAX(maxDetailLevel, sample.m_DetailLevel);
236
m_MinSamplePoint[0] = minXVal;
237
m_MaxSamplePoint[0] = maxXVal;
238
m_MinSamplePoint[1] = minYVal;
239
m_MaxSamplePoint[1] = maxYVal;
242
m_MinDofBoundIndex = minDofIndex;
243
m_MaxDofBoundIndex = maxDofIndex;
244
m_MinDetailLevel = minDetailLevel;
245
m_MaxDetailLevel = maxDetailLevel;
247
// Set the opaque depths to the limits to begin with.
248
m_MaxOpaqueZ = FLT_MAX;
252
void CqOcclusionTree::UpdateBounds()
256
assert(m_SampleIndices.size() > 1);
258
TqChildArray::iterator child = m_Children.begin();
259
(*child)->UpdateBounds();
261
m_MinSamplePoint[0] = (*child)->m_MinSamplePoint[0];
262
m_MaxSamplePoint[0] = (*child)->m_MaxSamplePoint[0];
263
m_MinSamplePoint[1] = (*child)->m_MinSamplePoint[1];
264
m_MaxSamplePoint[1] = (*child)->m_MaxSamplePoint[1];
265
m_MinTime = (*child)->m_MinTime;
266
m_MaxTime = (*child)->m_MaxTime;
267
m_MinDofBoundIndex = (*child)->m_MinDofBoundIndex;
268
m_MaxDofBoundIndex = (*child)->m_MaxDofBoundIndex;
269
m_MinDetailLevel = (*child)->m_MinDetailLevel;
270
m_MaxDetailLevel = (*child)->m_MaxDetailLevel;
272
for(++child; child != m_Children.end(); ++child)
276
(*child)->UpdateBounds();
278
m_MinSamplePoint[0] = std::min(m_MinSamplePoint[0], (*child)->m_MinSamplePoint[0]);
279
m_MaxSamplePoint[0] = std::max(m_MaxSamplePoint[0], (*child)->m_MaxSamplePoint[0]);
280
m_MinSamplePoint[1] = std::min(m_MinSamplePoint[1], (*child)->m_MinSamplePoint[1]);
281
m_MaxSamplePoint[1] = std::max(m_MaxSamplePoint[1], (*child)->m_MaxSamplePoint[1]);
282
m_MinTime = std::min(m_MinTime, (*child)->m_MinTime);
283
m_MaxTime = std::max(m_MaxTime, (*child)->m_MaxTime);
284
m_MinDofBoundIndex = std::min(m_MinDofBoundIndex, (*child)->m_MinDofBoundIndex);
285
m_MaxDofBoundIndex = std::max(m_MaxDofBoundIndex, (*child)->m_MaxDofBoundIndex);
286
m_MinDetailLevel = std::min(m_MinDetailLevel, (*child)->m_MinDetailLevel);
287
m_MaxDetailLevel = std::max(m_MaxDetailLevel, (*child)->m_MaxDetailLevel);
293
assert(m_SampleIndices.size() == 1);
295
const SqSampleData& sample = Sample();
296
m_MinSamplePoint[0] = m_MaxSamplePoint[0] = sample.m_Position[0];
297
m_MinSamplePoint[1] = m_MaxSamplePoint[1] = sample.m_Position[1];
298
m_MinTime = m_MaxTime = sample.m_Time;
299
m_MinDofBoundIndex = m_MaxDofBoundIndex = sample.m_DofOffsetIndex;
300
m_MinDetailLevel = m_MaxDetailLevel = sample.m_DetailLevel;
303
// Set the opaque depths to the limits to begin with.
304
m_MaxOpaqueZ = FLT_MAX;
307
void CqOcclusionTree::PropagateChanges()
309
CqOcclusionTreePtr node = this/*shared_from_this()*/;
310
// Update our opaque depth based on that our our children.
313
if( node->m_Children[0] )
315
TqFloat maxdepth = node->m_Children[0]->m_MaxOpaqueZ;
316
TqChildArray::iterator child = node->m_Children.begin();
317
for (++child; child != node->m_Children.end(); ++child)
321
maxdepth = MAX((*child)->m_MaxOpaqueZ, maxdepth);
324
// Only if this has resulted in a change at this level, should we process the parent.
325
if(maxdepth < node->m_MaxOpaqueZ)
327
node->m_MaxOpaqueZ = maxdepth;
328
node = node->m_Parent/*.lock()*/;
337
node = node->m_Parent/*.lock()*/;
343
TqBool CqOcclusionTree::CanCull( CqBound* bound )
345
// Recursively call each level to see if it can be culled at that point.
346
// Stop recursing at a level that doesn't contain the whole bound.
347
std::deque<CqOcclusionTree*> stack;
348
stack.push_front(this);
349
TqBool top_level = TqTrue;
350
while(!stack.empty())
352
CqOcclusionTree* node = stack.front();
354
// Check the bound against the 2D limits of this level, if not entirely contained, then we
355
// cannot cull at this level, nor at any of the children.
356
CqBound b1(node->MinSamplePoint(), node->MaxSamplePoint());
357
if(b1.Contains2D(*bound) || top_level)
360
if( bound->vecMin().z() > node->MaxOpaqueZ() )
361
// If the bound is entirely contained within this node's 2D bound, and is further
362
// away than the furthest opaque point, then cull.
364
// If contained, but not behind the furthest point, push the children nodes onto the stack for
366
CqOcclusionTree::TqChildArray::iterator childNode;
367
for (childNode = node->m_Children.begin(); childNode != node->m_Children.end(); ++childNode)
371
stack.push_front(*childNode/*->get()*/);
380
//----------------------------------------------------------------------
383
CqBucket* CqOcclusionBox::m_Bucket = NULL;
385
bool CqOcclusionTree::CqOcclusionTreeComparator::operator()(const std::pair<TqInt, TqInt>& a, const std::pair<TqInt, TqInt>& b)
387
const SqSampleData& A = CqBucket::ImageElement(a.first).SampleData(a.second);
388
const SqSampleData& B = CqBucket::ImageElement(b.first).SampleData(b.second);
389
return( A.m_Position[m_Dim] < B.m_Position[m_Dim] );
393
CqOcclusionTreePtr CqOcclusionBox::m_KDTree; ///< KD Tree representing the samples in the bucket.
396
//----------------------------------------------------------------------
400
CqOcclusionBox::CqOcclusionBox()
404
//----------------------------------------------------------------------
408
CqOcclusionBox::~CqOcclusionBox()
413
//----------------------------------------------------------------------
414
/** Delete the static hierarchy created in CreateHierachy(). static.
416
void CqOcclusionBox::DeleteHierarchy()
423
//----------------------------------------------------------------------
424
/** Setup the hierarchy for one bucket. Static.
425
This should be called before rendering each bucket
426
*\param bucket: the bucket we are about to render
427
*\param xMin: left edge of this bucket (taking into account crop windows etc)
428
*\param yMin: Top edge of this bucket
429
*\param xMax: Right edge of this bucket
430
*\param yMax: Bottom edge of this bucket
433
void CqOcclusionBox::SetupHierarchy( CqBucket* bucket, TqInt xMin, TqInt yMin, TqInt xMax, TqInt yMax )
440
m_KDTree = CqOcclusionTreePtr(new CqOcclusionTree());
441
// Setup the KDTree of samples
442
TqInt numpixels = bucket->RealHeight() * bucket->RealWidth();
443
TqInt numsamples = bucket->PixelXSamples() * bucket->PixelYSamples();
444
for ( TqInt j = 0; j < numpixels; j++ )
446
// Gather all samples within the pixel
447
for ( TqInt i = 0; i < numsamples; i++ )
449
m_KDTree->AddSample(std::pair<TqInt, TqInt>(j,i));
452
// Now split the tree down until each leaf has only one sample.
453
m_KDTree->InitialiseBounds();
454
m_KDTree->ConstructTree();
457
m_KDTree->UpdateBounds();
460
static TqInt i__ = 0;
463
std::ofstream strFile("test.out");
464
strFile << "xmin = " << xMin << std::endl << "ymin = " << yMin << std::endl << "xmax = " << xMax << std::endl << "ymax = " << yMax << std::endl << std::endl;
465
strFile << "points = [" << std::endl;
467
CqOcclusionTree::m_Tab = 0;
468
m_KDTree->OutputTree("test.out");
469
std::ofstream strFile2("test.out", std::ios_base::out|std::ios_base::app);
470
strFile2 << "]" << std::endl;
477
TqBool CqOcclusionBox::CanCull( CqBound* bound )
479
return(m_KDTree->CanCull(bound));
483
void StoreExtraData( CqMicroPolygon* pMPG, SqImageSample& sample)
485
std::map<std::string, CqRenderer::SqOutputDataEntry>& DataMap = QGetRenderContext() ->GetMapOfOutputDataEntries();
486
std::map<std::string, CqRenderer::SqOutputDataEntry>::iterator entry;
487
for ( entry = DataMap.begin(); entry != DataMap.end(); ++entry )
490
if ( ( pData = pMPG->pGrid() ->FindStandardVar( entry->first.c_str() ) ) != NULL )
492
switch ( pData->Type() )
498
pData->GetFloat( f, pMPG->GetIndex() );
499
sample.Data()[ entry->second.m_Offset ] = f;
508
pData->GetPoint( v, pMPG->GetIndex() );
509
sample.Data()[ entry->second.m_Offset ] = v.x();
510
sample.Data()[ entry->second.m_Offset + 1 ] = v.y();
511
sample.Data()[ entry->second.m_Offset + 2 ] = v.z();
517
pData->GetColor( c, pMPG->GetIndex() );
518
sample.Data()[ entry->second.m_Offset ] = c.fRed();
519
sample.Data()[ entry->second.m_Offset + 1 ] = c.fGreen();
520
sample.Data()[ entry->second.m_Offset + 2 ] = c.fBlue();
526
pData->GetMatrix( m, pMPG->GetIndex() );
527
TqFloat* pElements = m.pElements();
528
sample.Data()[ entry->second.m_Offset ] = pElements[ 0 ];
529
sample.Data()[ entry->second.m_Offset + 1 ] = pElements[ 1 ];
530
sample.Data()[ entry->second.m_Offset + 2 ] = pElements[ 2 ];
531
sample.Data()[ entry->second.m_Offset + 3 ] = pElements[ 3 ];
532
sample.Data()[ entry->second.m_Offset + 4 ] = pElements[ 4 ];
533
sample.Data()[ entry->second.m_Offset + 5 ] = pElements[ 5 ];
534
sample.Data()[ entry->second.m_Offset + 6 ] = pElements[ 6 ];
535
sample.Data()[ entry->second.m_Offset + 7 ] = pElements[ 7 ];
536
sample.Data()[ entry->second.m_Offset + 8 ] = pElements[ 8 ];
537
sample.Data()[ entry->second.m_Offset + 9 ] = pElements[ 9 ];
538
sample.Data()[ entry->second.m_Offset + 10 ] = pElements[ 10 ];
539
sample.Data()[ entry->second.m_Offset + 11 ] = pElements[ 11 ];
540
sample.Data()[ entry->second.m_Offset + 12 ] = pElements[ 12 ];
541
sample.Data()[ entry->second.m_Offset + 13 ] = pElements[ 13 ];
542
sample.Data()[ entry->second.m_Offset + 14 ] = pElements[ 14 ];
543
sample.Data()[ entry->second.m_Offset + 15 ] = pElements[ 15 ];
547
// left blank to avoid compiler warnings about unhandled
557
void CqOcclusionTree::SampleMPG( CqMicroPolygon* pMPG, const CqBound& bound, TqBool usingMB, TqFloat time0, TqFloat time1, TqBool usingDof, TqInt dofboundindex, SqMpgSampleInfo& MpgSampleInfo, TqBool usingLOD, SqGridInfo& gridInfo)
559
// Check the current tree level, and if only one leaf, sample the MP, otherwise, pass it down to the left
560
// and/or right side of the tree if it crosses.
561
if(NumSamples() == 1)
564
SqSampleData& sample = Sample();
568
CqStats::IncI( CqStats::SPL_count );
569
SampleHit = pMPG->Sample(sample, D, sample.m_Time, usingDof );
573
TqBool Occludes = MpgSampleInfo.m_Occludes;
574
TqBool opaque = MpgSampleInfo.m_IsOpaque;
576
SqImageSample& currentOpaqueSample = sample.m_OpaqueSample;
577
static SqImageSample localImageVal;
579
SqImageSample& ImageVal = opaque ? currentOpaqueSample : localImageVal;
581
std::deque<SqImageSample>& aValues = sample.m_Data;
583
// return if the sample is occluded and can be culled.
586
if((currentOpaqueSample.m_flags & SqImageSample::Flag_Valid) &&
587
currentOpaqueSample.Data()[Sample_Depth] <= D)
593
CqStats::IncI( CqStats::SPL_hits );
596
TqFloat* val = ImageVal.Data();
597
const CqColor& col = MpgSampleInfo.m_Colour;
598
const CqColor& opa = MpgSampleInfo.m_Opacity;
607
// Now store any other data types that have been registered.
608
if(gridInfo.m_UsesDataMap)
610
StoreExtraData(pMPG, ImageVal);
613
// \note: There used to be a test here to see if the current sample is 'exactly'
614
// the same depth as the nearest in the list, ostensibly to check for a 'grid line' hit
615
// but it didn't make sense, so was removed.
617
// Update max depth values if the sample is opaque and can occlude
618
// If the sample depth is closer than the current closest one, and is opaques
619
// we can just replace, as we know we are in a treenode that is a leaf.
629
if(pMPG->pGrid()->usesCSG())
630
ImageVal.m_pCSGNode = pMPG->pGrid() ->pCSGNode();
632
ImageVal.m_flags = 0;
635
ImageVal.m_flags |= SqImageSample::Flag_Occludes;
637
if( gridInfo.m_IsMatte )
639
ImageVal.m_flags |= SqImageSample::Flag_Matte;
644
aValues.push_back( ImageVal );
648
// mark this sample as having been written into.
649
ImageVal.m_flags |= SqImageSample::Flag_Valid;
655
TqChildArray::iterator child;
656
TqChildArray::iterator end = m_Children.end();
657
for(child = m_Children.begin(); child != end; ++child)
662
if( (!usingDof || ((dofboundindex >= (*child)->m_MinDofBoundIndex) && (dofboundindex <= (*child)->m_MaxDofBoundIndex )) )
663
&& (!usingMB || ((time0 <= (*child)->m_MaxTime) && (time1 >= (*child)->m_MinTime)) )
664
&& (!usingLOD || ((gridInfo.m_LodBounds[0] <= (*child)->m_MaxDetailLevel) && (gridInfo.m_LodBounds[1] >= (*child)->m_MinDetailLevel)) )
665
&& (bound.Intersects((*child)->m_MinSamplePoint, (*child)->m_MaxSamplePoint)) )
667
if(bound.vecMin().z() <= (*child)->m_MaxOpaqueZ || !gridInfo.m_IsCullable)
669
(*child)->SampleMPG(pMPG, bound, usingMB, time0, time1, usingDof, dofboundindex, MpgSampleInfo, usingLOD, gridInfo);
677
/*void CqOcclusionTree::OutputTree(const char* name)
679
std::ofstream strFile(name, std::ios_base::out|std::ios_base::app);
682
"(" << m_Tab << ", " <<
683
"(" << m_MinSamplePoint[0] << ", " << m_MinSamplePoint[1] << "), " <<
684
"(" << m_MaxSamplePoint[0] << ", " << m_MinSamplePoint[1] << "), " <<
685
"(" << m_MaxSamplePoint[0] << ", " << m_MinSamplePoint[1] << "), " <<
686
"(" << m_MaxSamplePoint[0] << ", " << m_MaxSamplePoint[1] << "), " <<
687
"(" << m_MaxSamplePoint[0] << ", " << m_MaxSamplePoint[1] << "), " <<
688
"(" << m_MinSamplePoint[0] << ", " << m_MaxSamplePoint[1] << "), " <<
689
"(" << m_MinSamplePoint[0] << ", " << m_MaxSamplePoint[1] << "), " <<
690
"(" << m_MinSamplePoint[0] << ", " << m_MinSamplePoint[1] << ")" <<
694
TqChildArray::iterator child;
695
for(child = m_Children.begin(); child != m_Children.end(); ++child)
697
if (*child && (*child)->NumSamples() > 1)
700
(*child)->OutputTree(name);
707
END_NAMESPACE( Aqsis )