source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/CHCPlusPlusTraverser.cpp @ 3065

Revision 3065, 6.9 KB checked in by mattausch, 16 years ago (diff)

found bug with near plane intersection: q? why did it work with vbo rendering? (probably because of tighter bounds ...)

Line 
1#include "CHCPlusPlusTraverser.h"
2#include "RenderState.h"
3
4using namespace std;
5
6namespace CHCDemoEngine
7{
8
9
10CHCPlusPlusTraverser::CHCPlusPlusTraverser()
11{
12}
13
14
15void CHCPlusPlusTraverser::HandleQueryResult(OcclusionQuery *query)
16{
17        // wait until result available
18        const int visible = query->GetQueryResult() > mVisibilityThreshold;
19
20        // multiquery
21        if (query->GetSize() > 1)
22        {
23                // failed query: query individual nodes
24                if (visible)
25                {
26                        for (size_t i = 0; i < query->GetSize(); ++ i)
27                        {
28                                BvhNode *node = query->GetNodes()[i];
29
30                                mIQueue.push_back(node);
31                                node->SetLastQueriedFrame(mFrameId);
32                        }
33                }
34                else // query successful: update classifications
35                {
36                        for (size_t i = 0; i < query->GetSize(); ++ i)
37                        {
38                                BvhNode *node = query->GetNodes()[i];
39                                node->IncTimesTestedInvisible();
40                                node->SetVisible(false);
41                                node->SetLastQueriedFrame(mFrameId);
42                        }
43
44                        mStats.mNumQueryCulledNodes += query->GetSize();
45                }
46        }
47        else // single query
48        {
49                BvhNode *node = query->GetFrontNode();
50
51                node->SetLastQueriedFrame(mFrameId);
52
53                // failed query: query individual nodes
54                if (visible)
55                {
56                        // node was previously invisible
57                        if (!node->IsVisible())
58                        {
59                                // reset flag
60                                node->SetTimesTestedInvisible(0);
61                                node->SetAssumedVisibleFrameId(mFrameId + mAssumedVisibleFrames);
62                        }
63                        else
64                        {       // randomize first invokation
65                                node->SetAssumedVisibleFrameId(mFrameId + Random(mAssumedVisibleFrames + 1));
66                        }
67
68                        mBvh->MakeParentsVisible(node);
69                        TraverseNode(node);
70                }
71                else
72                {
73                        node->IncTimesTestedInvisible();
74                        ++ mStats.mNumQueryCulledNodes;
75                }
76
77                node->SetVisible(visible);
78        }
79}
80
81
82void CHCPlusPlusTraverser::Traverse()
83{
84        int waitedForQueries = 0;
85        int returnedQueries = 0;
86
87        //-- PART 1: process finished occlusion queries
88        while (!mDistanceQueue.empty() || !mQueryQueue.empty())
89        {
90                bool resultAvailable = false;
91
92                while (!mQueryQueue.empty() &&
93                           (mDistanceQueue.empty() || (resultAvailable = mQueryQueue.front()->ResultAvailable())))
94                {
95                        while (!resultAvailable && !mVQueue.empty())
96                        {
97                                BvhNode *node = mVQueue.front();
98                                mVQueue.pop();
99                               
100                                OcclusionQuery *query = IssueOcclusionQuery(node);
101
102                                mQueryQueue.push(query);
103                                resultAvailable = mQueryQueue.front()->ResultAvailable();
104                        }
105                       
106                        //++ returnedQueries; if (!resultAvailable) ++ waitedForQueries;
107                       
108                        OcclusionQuery *query = mQueryQueue.front();
109                        mQueryQueue.pop();
110
111                        // waiting for query result
112                        HandleQueryResult(query);
113                }       
114
115                //-- PART 2: hierarchical traversal
116                if (!mDistanceQueue.empty())
117                {
118                        BvhNode *node = mDistanceQueue.top();
119                        mDistanceQueue.pop();
120       
121                        if (mBvh->IsWithinViewFrustum(node))
122                        {
123                                // for near plane intersecting bounding box possible
124                                // wrong results => skip occlusion query
125                                if (mBvh->IntersectsNearPlane(node))
126                                {
127                                        // update node's visited flag
128                                        node->SetLastVisitedFrame(mFrameId);
129                                        node->SetVisible(true);
130                                        mBvh->MakeParentsVisible(node);
131
132                                        TraverseNode(node);
133                                }
134                                else
135                                {               
136                                        // identify previously visible nodes
137                                        const bool wasVisible = node->IsVisible() && (node->GetLastVisitedFrame() == mFrameId - 1);
138                                       
139                                        // identify nodes that we cannot skip queries for
140                                        const bool queryFeasible = (!wasVisible || (node->IsVirtualLeaf() &&
141                                                (node->GetAssumedVisibleFrameId() <= mFrameId)));
142
143                                        // node was not recently tested => reset flag
144                                        if (node->GetLastVisitedFrame() != mFrameId - 1)
145                                                node->SetTimesTestedInvisible(0);
146
147                                        // update node's visited flag
148                                        node->SetLastVisitedFrame(mFrameId);
149                                       
150                                        // skip testing previously visible interior nodes
151                                        if (queryFeasible)
152                                        {
153                                                if (!wasVisible)
154                                                {
155                                                        QueryPreviouslyInvisibleNodes(node);
156                                                }
157                                                else
158                                                {
159                                                        mVQueue.push(node);
160                                                }
161                                        }
162                                        else
163                                        {
164                                                if (node->IsVirtualLeaf())
165                                                {
166                                                        node->SetVisible(true);
167                                                        mBvh->MakeParentsVisible(node);
168                                                }
169                                                else // reset visibility classification
170                                                {
171                                                        node->SetVisible(false);
172                                                }
173                                        }
174                                       
175                                        // always traverse a node if it was previously visible
176                                        if (wasVisible)
177                                                TraverseNode(node);
178                                }
179                        }
180                        else
181                        {
182                                // for stats
183                                ++ mStats.mNumFrustumCulledNodes;
184                        }
185                }
186
187                // distance queue empty: feed the remaining multiqueries to
188                // be able to proceed traversal
189                if (mDistanceQueue.empty())
190                {
191                        IssueMultiQueries();
192                }
193        }
194
195        // render the rest of the objects
196        if (mUseRenderQueue) ApplyRenderQueue();
197
198
199        //////////////
200        //-- issue remaining previously visible node queries
201
202        while (!mVQueue.empty())
203        {
204                BvhNode *node = mVQueue.front();
205                mVQueue.pop();
206
207                OcclusionQuery *query = IssueOcclusionQuery(node);
208                mQueryQueue.push(query);
209        }
210
211        while (!mQueryQueue.empty())
212        {
213                OcclusionQuery *query = mQueryQueue.front();
214                mQueryQueue.pop();
215
216                HandleQueryResult(query);
217        }
218
219        //cout << "returned queries: " << returnedQueries << " waited for queries: " << waitedForQueries << " (=" << 100.0f * waitedForQueries / returnedQueries << "%)" << endl;
220}
221
222
223void CHCPlusPlusTraverser::QueryPreviouslyInvisibleNodes(BvhNode *node)
224{
225        mIQueue.push_back(node);
226
227        if (mIQueue.size() > mMaxBatchSize)
228        {
229                IssueMultiQueries();
230        }
231}
232
233
234OcclusionQuery * CHCPlusPlusTraverser::GetNextMultiQuery(BvhNodeContainer &iqueue)
235{
236        OcclusionQuery *query = mQueryHandler.RequestQuery();
237
238        float pFail = 1.0f;
239        float maxBatchVal = 0.0f;
240        float newPBatch = 1.0f;
241        float newBatchVal;
242
243        // issue next query
244        while (!iqueue.empty())
245        {
246                BvhNode *node = iqueue.back();
247
248                // node was already part of a mulitquery => avoid recursion
249                if (node->GetLastQueriedFrame() == mFrameId)
250                        newPBatch = 0;
251                else
252                newPBatch *= mVisibilityPredictor.GetProbability(node);
253
254                if (query->GetNodes().empty())
255                {
256                        // single node will never cause a wasted query
257                        newBatchVal = 1.0f;
258                }
259                else
260                {
261                        int newSize = query->GetSize() + 1;
262                        newBatchVal = newSize / (1.0f + (1.0f - newPBatch) * newSize);
263                }
264
265                if (newBatchVal <= maxBatchVal)
266                        break;
267
268                iqueue.pop_back();
269                query->AddNode(node);
270
271                maxBatchVal = newBatchVal;
272        }
273
274        //cout <<"size: " << query->GetSize() << endl;
275        IssueOcclusionQuery(*query);
276
277        return query;
278}
279
280
281static inline bool lt(BvhNode *a, BvhNode *b)
282{
283        return a->GetTimesTestedInvisible() < b->GetTimesTestedInvisible();
284}
285
286
287void CHCPlusPlusTraverser::IssueMultiQueries()
288{
289        if (mUseMultiQueries)
290        {
291                // sort queries by #times invisible
292                sort(mIQueue.begin(), mIQueue.end(), lt);
293
294                while (!mIQueue.empty())
295                        mQueryQueue.push(GetNextMultiQuery(mIQueue));
296        }
297        else
298        {
299                BvhNodeContainer::const_iterator it, it_end = mIQueue.end();
300
301                for (it = mIQueue.begin(); it != it_end; ++ it)
302                        mQueryQueue.push(IssueOcclusionQuery(*it));
303
304                mIQueue.clear();
305        }
306}
307
308
309}
Note: See TracBrowser for help on using the repository browser.