1 | #include <stack> |
---|
2 | #include <algorithm> |
---|
3 | #include <queue> |
---|
4 | #include "Environment.h" |
---|
5 | #include "Mesh.h" |
---|
6 | #include "KdTree.h" |
---|
7 | |
---|
8 | |
---|
9 | |
---|
10 | |
---|
11 | KdNode::KdNode(KdInterior *parent):mParent(parent) |
---|
12 | { |
---|
13 | if (parent) |
---|
14 | mDepth = parent->mDepth+1; |
---|
15 | else |
---|
16 | mDepth = 0; |
---|
17 | } |
---|
18 | |
---|
19 | KdTree::KdTree() |
---|
20 | { |
---|
21 | mRoot = new KdLeaf(NULL, 0); |
---|
22 | environment->GetIntValue("KdTree.Termination.maxDepth", mTermMaxDepth); |
---|
23 | environment->GetIntValue("KdTree.Termination.minCost", mTermMinCost); |
---|
24 | environment->GetFloatValue("KdTree.Termination.maxCostRatio", mMaxCostRatio); |
---|
25 | environment->GetFloatValue("KdTree.Termination.ct_div_ci", mCt_div_ci); |
---|
26 | environment->GetFloatValue("KdTree.splitBorder", mSplitBorder); |
---|
27 | |
---|
28 | char splitType[64]; |
---|
29 | environment->GetStringValue("KdTree.splitMethod", splitType); |
---|
30 | |
---|
31 | mSplitMethod = SPLIT_SPATIAL_MEDIAN; |
---|
32 | if (strcmp(splitType, "spatialMedian") == 0) |
---|
33 | mSplitMethod = SPLIT_SPATIAL_MEDIAN; |
---|
34 | else |
---|
35 | if (strcmp(splitType, "objectMedian") == 0) |
---|
36 | mSplitMethod = SPLIT_OBJECT_MEDIAN; |
---|
37 | else |
---|
38 | if (strcmp(splitType, "SAH") == 0) |
---|
39 | mSplitMethod = SPLIT_SAH; |
---|
40 | else { |
---|
41 | cerr<<"Wrong kd split type "<<splitType<<endl; |
---|
42 | exit(1); |
---|
43 | } |
---|
44 | |
---|
45 | splitCandidates = new vector<SortableEntry>; |
---|
46 | } |
---|
47 | |
---|
48 | bool |
---|
49 | KdTree::Construct() |
---|
50 | { |
---|
51 | // first construct a leaf that will get subdivide |
---|
52 | KdLeaf *leaf = (KdLeaf *) mRoot; |
---|
53 | |
---|
54 | mStat.nodes = 1; |
---|
55 | |
---|
56 | mBox.Initialize(); |
---|
57 | |
---|
58 | MeshContainer::const_iterator mi; |
---|
59 | for ( mi = leaf->mObjects.begin(); |
---|
60 | mi != leaf->mObjects.end(); |
---|
61 | mi++) { |
---|
62 | mBox.Include((*mi)->GetBox()); |
---|
63 | } |
---|
64 | |
---|
65 | cout <<"box:"<< mBox<<endl; |
---|
66 | |
---|
67 | |
---|
68 | mRoot = Subdivide(TraversalData(leaf, mBox, 0)); |
---|
69 | |
---|
70 | return true; |
---|
71 | } |
---|
72 | |
---|
73 | KdNode * |
---|
74 | KdTree::Subdivide(const TraversalData &tdata) |
---|
75 | { |
---|
76 | |
---|
77 | KdNode *result = NULL; |
---|
78 | |
---|
79 | priority_queue<TraversalData> tStack; |
---|
80 | // stack<STraversalData> tStack; |
---|
81 | |
---|
82 | tStack.push(tdata); |
---|
83 | AxisAlignedBox3 backBox, frontBox; |
---|
84 | |
---|
85 | |
---|
86 | while (!tStack.empty()) { |
---|
87 | |
---|
88 | #if 0 |
---|
89 | if ( GetMemUsage() > maxMemory ) { |
---|
90 | // count statistics on unprocessed leafs |
---|
91 | while (!tStack.empty()) { |
---|
92 | EvaluateLeafStats(tStack.top()); |
---|
93 | tStack.pop(); |
---|
94 | } |
---|
95 | break; |
---|
96 | } |
---|
97 | #endif |
---|
98 | |
---|
99 | TraversalData data = tStack.top(); |
---|
100 | tStack.pop(); |
---|
101 | |
---|
102 | KdNode *node = SubdivideNode((KdLeaf *) data.mNode, |
---|
103 | data.mBox, |
---|
104 | backBox, |
---|
105 | frontBox |
---|
106 | ); |
---|
107 | if (result == NULL) |
---|
108 | result = node; |
---|
109 | |
---|
110 | if (!node->IsLeaf()) { |
---|
111 | |
---|
112 | KdInterior *interior = (KdInterior *) node; |
---|
113 | // push the children on the stack |
---|
114 | tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1)); |
---|
115 | tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1)); |
---|
116 | |
---|
117 | } else { |
---|
118 | EvaluateLeafStats(data); |
---|
119 | } |
---|
120 | } |
---|
121 | |
---|
122 | return result; |
---|
123 | |
---|
124 | } |
---|
125 | |
---|
126 | |
---|
127 | |
---|
128 | bool |
---|
129 | KdTree::TerminationCriteriaMet(const KdLeaf *leaf) |
---|
130 | { |
---|
131 | // cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl; |
---|
132 | return |
---|
133 | (leaf->mObjects.size() < mTermMinCost) || |
---|
134 | (leaf->mDepth >= mTermMaxDepth); |
---|
135 | |
---|
136 | } |
---|
137 | |
---|
138 | |
---|
139 | int |
---|
140 | KdTree::SelectPlane(KdLeaf *leaf, |
---|
141 | const AxisAlignedBox3 &box, |
---|
142 | float &position |
---|
143 | ) |
---|
144 | { |
---|
145 | int axis = -1; |
---|
146 | |
---|
147 | switch (mSplitMethod) |
---|
148 | { |
---|
149 | case SPLIT_SPATIAL_MEDIAN: { |
---|
150 | axis = box.Size().DrivingAxis(); |
---|
151 | position = (box.Min()[axis] + box.Max()[axis])*0.5f; |
---|
152 | break; |
---|
153 | } |
---|
154 | case SPLIT_SAH: { |
---|
155 | int objectsBack, objectsFront; |
---|
156 | float costRatio; |
---|
157 | bool mOnlyDrivingAxis = false; |
---|
158 | if (mOnlyDrivingAxis) { |
---|
159 | axis = box.Size().DrivingAxis(); |
---|
160 | costRatio = BestCostRatio(leaf, |
---|
161 | box, |
---|
162 | axis, |
---|
163 | position, |
---|
164 | objectsBack, |
---|
165 | objectsFront); |
---|
166 | } else { |
---|
167 | costRatio = MAX_FLOAT; |
---|
168 | for (int i=0; i < 3; i++) { |
---|
169 | float p; |
---|
170 | float r = BestCostRatio(leaf, |
---|
171 | box, |
---|
172 | i, |
---|
173 | p, |
---|
174 | objectsBack, |
---|
175 | objectsFront); |
---|
176 | if (r < costRatio) { |
---|
177 | costRatio = r; |
---|
178 | axis = i; |
---|
179 | position = p; |
---|
180 | } |
---|
181 | } |
---|
182 | } |
---|
183 | |
---|
184 | if (costRatio > mMaxCostRatio) { |
---|
185 | // cout<<"Too big cost ratio "<<costRatio<<endl; |
---|
186 | axis = -1; |
---|
187 | } |
---|
188 | break; |
---|
189 | } |
---|
190 | |
---|
191 | } |
---|
192 | return axis; |
---|
193 | } |
---|
194 | |
---|
195 | KdNode * |
---|
196 | KdTree::SubdivideNode( |
---|
197 | KdLeaf *leaf, |
---|
198 | const AxisAlignedBox3 &box, |
---|
199 | AxisAlignedBox3 &backBBox, |
---|
200 | AxisAlignedBox3 &frontBBox |
---|
201 | ) |
---|
202 | { |
---|
203 | |
---|
204 | if (TerminationCriteriaMet(leaf)) |
---|
205 | return leaf; |
---|
206 | |
---|
207 | float position; |
---|
208 | |
---|
209 | // select subdivision axis |
---|
210 | int axis = SelectPlane( leaf, box, position ); |
---|
211 | |
---|
212 | if (axis == -1) { |
---|
213 | return leaf; |
---|
214 | } |
---|
215 | |
---|
216 | mStat.nodes+=2; |
---|
217 | mStat.splits[axis]++; |
---|
218 | |
---|
219 | // add the new nodes to the tree |
---|
220 | KdInterior *node = new KdInterior(leaf->mParent); |
---|
221 | |
---|
222 | node->mAxis = axis; |
---|
223 | node->mPosition = position; |
---|
224 | node->mBox = box; |
---|
225 | |
---|
226 | backBBox = box; |
---|
227 | frontBBox = box; |
---|
228 | |
---|
229 | // first count ray sides |
---|
230 | int objectsBack = 0; |
---|
231 | int objectsFront = 0; |
---|
232 | |
---|
233 | backBBox.SetMax(axis, position); |
---|
234 | frontBBox.SetMin(axis, position); |
---|
235 | |
---|
236 | MeshContainer::const_iterator mi; |
---|
237 | |
---|
238 | for ( mi = leaf->mObjects.begin(); |
---|
239 | mi != leaf->mObjects.end(); |
---|
240 | mi++) { |
---|
241 | // determine the side of this ray with respect to the plane |
---|
242 | AxisAlignedBox3 box = (*mi)->GetBox(); |
---|
243 | if (box.Max(axis) > position ) |
---|
244 | objectsFront++; |
---|
245 | |
---|
246 | if (box.Min(axis) < position ) |
---|
247 | objectsBack++; |
---|
248 | } |
---|
249 | |
---|
250 | |
---|
251 | KdLeaf *back = new KdLeaf(node, objectsBack); |
---|
252 | KdLeaf *front = new KdLeaf(node, objectsFront); |
---|
253 | |
---|
254 | // replace a link from node's parent |
---|
255 | if ( leaf->mParent ) |
---|
256 | leaf->mParent->ReplaceChildLink(leaf, node); |
---|
257 | |
---|
258 | // and setup child links |
---|
259 | node->SetupChildLinks(back, front); |
---|
260 | |
---|
261 | for (mi = leaf->mObjects.begin(); |
---|
262 | mi != leaf->mObjects.end(); |
---|
263 | mi++) { |
---|
264 | // determine the side of this ray with respect to the plane |
---|
265 | AxisAlignedBox3 box = (*mi)->GetBox(); |
---|
266 | |
---|
267 | if (box.Max(axis) >= position ) |
---|
268 | front->mObjects.push_back(*mi); |
---|
269 | |
---|
270 | if (box.Min(axis) < position ) |
---|
271 | back->mObjects.push_back(*mi); |
---|
272 | |
---|
273 | mStat.objectRefs -= leaf->mObjects.size(); |
---|
274 | mStat.objectRefs += objectsBack + objectsFront; |
---|
275 | } |
---|
276 | |
---|
277 | delete leaf; |
---|
278 | return node; |
---|
279 | } |
---|
280 | |
---|
281 | |
---|
282 | |
---|
283 | void |
---|
284 | KdTreeStatistics::Print(ostream &app) const |
---|
285 | { |
---|
286 | app << "===== KdTree statistics ===============\n"; |
---|
287 | |
---|
288 | app << "#N_RAYS Number of rays )\n" |
---|
289 | << rays <<endl; |
---|
290 | app << "#N_DOMAINS ( Number of query domains )\n" |
---|
291 | << queryDomains <<endl; |
---|
292 | |
---|
293 | app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; |
---|
294 | |
---|
295 | app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n"; |
---|
296 | |
---|
297 | app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; |
---|
298 | for (int i=0; i<7; i++) |
---|
299 | app << splits[i] <<" "; |
---|
300 | app <<endl; |
---|
301 | |
---|
302 | app << "#N_RAYREFS ( Number of rayRefs )\n" << |
---|
303 | rayRefs << "\n"; |
---|
304 | |
---|
305 | app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" << |
---|
306 | rayRefs/(double)rays << "\n"; |
---|
307 | |
---|
308 | app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" << |
---|
309 | rayRefs/(double)Leaves() << "\n"; |
---|
310 | |
---|
311 | app << "#N_MAXOBJECTREFS ( Max number of rayRefs / leaf )\n" << |
---|
312 | maxObjectRefs << "\n"; |
---|
313 | |
---|
314 | app << "#N_NONEMPTYRAYREFS ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" << |
---|
315 | rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n"; |
---|
316 | |
---|
317 | app << "#N_LEAFDOMAINREFS ( Number of query domain Refs / leaf )\n" << |
---|
318 | objectRefs/(double)Leaves() << "\n"; |
---|
319 | |
---|
320 | // app << setprecision(4); |
---|
321 | |
---|
322 | app << "#N_PEMPTYLEAVES ( Percentage of leaves with zero query domains )\n"<< |
---|
323 | zeroQueryNodes*100/(double)Leaves()<<endl; |
---|
324 | |
---|
325 | app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<< |
---|
326 | maxDepthNodes*100/(double)Leaves()<<endl; |
---|
327 | |
---|
328 | app << "#N_PMINCOSTLEAVES ( Percentage of leaves with minCost )\n"<< |
---|
329 | minCostNodes*100/(double)Leaves()<<endl; |
---|
330 | |
---|
331 | app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<< |
---|
332 | addedRayRefs<<endl; |
---|
333 | |
---|
334 | app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<< |
---|
335 | removedRayRefs<<endl; |
---|
336 | |
---|
337 | // app << setprecision(4); |
---|
338 | |
---|
339 | // app << "#N_CTIME ( Construction time [s] )\n" |
---|
340 | // << Time() << " \n"; |
---|
341 | |
---|
342 | app << "===== END OF KdTree statistics ==========\n"; |
---|
343 | |
---|
344 | } |
---|
345 | |
---|
346 | |
---|
347 | |
---|
348 | void |
---|
349 | KdTree::EvaluateLeafStats(const TraversalData &data) |
---|
350 | { |
---|
351 | |
---|
352 | // the node became a leaf -> evaluate stats for leafs |
---|
353 | KdLeaf *leaf = (KdLeaf *)data.mNode; |
---|
354 | |
---|
355 | if (data.mDepth > mTermMaxDepth) |
---|
356 | mStat.maxDepthNodes++; |
---|
357 | |
---|
358 | if ( (int)(leaf->mObjects.size()) < mTermMinCost) |
---|
359 | mStat.minCostNodes++; |
---|
360 | |
---|
361 | |
---|
362 | if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs) |
---|
363 | mStat.maxObjectRefs = leaf->mObjects.size(); |
---|
364 | |
---|
365 | } |
---|
366 | |
---|
367 | |
---|
368 | |
---|
369 | void |
---|
370 | KdTree::SortSplitCandidates( |
---|
371 | KdLeaf *node, |
---|
372 | const int axis |
---|
373 | ) |
---|
374 | { |
---|
375 | splitCandidates->clear(); |
---|
376 | |
---|
377 | int requestedSize = 2*node->mObjects.size(); |
---|
378 | // creates a sorted split candidates array |
---|
379 | if (splitCandidates->capacity() > 500000 && |
---|
380 | requestedSize < (int)(splitCandidates->capacity()/10) ) { |
---|
381 | delete splitCandidates; |
---|
382 | splitCandidates = new vector<SortableEntry>; |
---|
383 | } |
---|
384 | |
---|
385 | splitCandidates->reserve(requestedSize); |
---|
386 | |
---|
387 | // insert all queries |
---|
388 | for(MeshContainer::const_iterator mi = node->mObjects.begin(); |
---|
389 | mi < node->mObjects.end(); |
---|
390 | mi++) { |
---|
391 | AxisAlignedBox3 box = (*mi)->GetBox(); |
---|
392 | |
---|
393 | splitCandidates->push_back(SortableEntry(SortableEntry::MESH_MIN, |
---|
394 | box.Min(axis), |
---|
395 | (void *)*mi) |
---|
396 | ); |
---|
397 | |
---|
398 | |
---|
399 | splitCandidates->push_back(SortableEntry(SortableEntry::MESH_MAX, |
---|
400 | box.Max(axis), |
---|
401 | (void *)*mi) |
---|
402 | ); |
---|
403 | } |
---|
404 | |
---|
405 | stable_sort(splitCandidates->begin(), splitCandidates->end()); |
---|
406 | } |
---|
407 | |
---|
408 | |
---|
409 | float |
---|
410 | KdTree::BestCostRatio( |
---|
411 | KdLeaf *node, |
---|
412 | const AxisAlignedBox3 &box, |
---|
413 | const int axis, |
---|
414 | float &position, |
---|
415 | int &objectsBack, |
---|
416 | int &objectsFront |
---|
417 | ) |
---|
418 | { |
---|
419 | |
---|
420 | SortSplitCandidates(node, axis); |
---|
421 | |
---|
422 | // go through the lists, count the number of objects left and right |
---|
423 | // and evaluate the following cost funcion: |
---|
424 | // C = ct_div_ci + (ol + or)/queries |
---|
425 | |
---|
426 | int ol = 0, or = node->mObjects.size(); |
---|
427 | |
---|
428 | float minBox = box.Min(axis); |
---|
429 | float maxBox = box.Max(axis); |
---|
430 | float boxArea = box.SurfaceArea(); |
---|
431 | |
---|
432 | |
---|
433 | |
---|
434 | float minBand = minBox + mSplitBorder*(maxBox - minBox); |
---|
435 | float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox); |
---|
436 | |
---|
437 | float minSum = 1e20; |
---|
438 | |
---|
439 | for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin(); |
---|
440 | ci < splitCandidates->end(); |
---|
441 | ci++) { |
---|
442 | |
---|
443 | switch ((*ci).type) { |
---|
444 | case SortableEntry::MESH_MIN: |
---|
445 | ol++; |
---|
446 | break; |
---|
447 | case SortableEntry::MESH_MAX: |
---|
448 | or--; |
---|
449 | break; |
---|
450 | } |
---|
451 | |
---|
452 | if ((*ci).value > minBand && (*ci).value < maxBand) { |
---|
453 | AxisAlignedBox3 lbox = box; |
---|
454 | AxisAlignedBox3 rbox = box; |
---|
455 | lbox.SetMax(axis, (*ci).value); |
---|
456 | rbox.SetMin(axis, (*ci).value); |
---|
457 | |
---|
458 | float sum = ol*lbox.SurfaceArea() + or*rbox.SurfaceArea(); |
---|
459 | |
---|
460 | // cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl; |
---|
461 | // cout<<"cost= "<<sum<<endl; |
---|
462 | |
---|
463 | if (sum < minSum) { |
---|
464 | minSum = sum; |
---|
465 | position = (*ci).value; |
---|
466 | |
---|
467 | objectsBack = ol; |
---|
468 | objectsFront = or; |
---|
469 | } |
---|
470 | } |
---|
471 | } |
---|
472 | |
---|
473 | float oldCost = node->mObjects.size(); |
---|
474 | float newCost = mCt_div_ci + minSum/boxArea; |
---|
475 | float ratio = newCost/oldCost; |
---|
476 | |
---|
477 | #if 0 |
---|
478 | cout<<"===================="<<endl; |
---|
479 | cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox) |
---|
480 | <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl; |
---|
481 | #endif |
---|
482 | return ratio; |
---|
483 | } |
---|
484 | |
---|
485 | int |
---|
486 | KdTree::CastRay( |
---|
487 | Ray &ray |
---|
488 | ) |
---|
489 | { |
---|
490 | int hits = 0; |
---|
491 | |
---|
492 | stack<RayTraversalData> tStack; |
---|
493 | |
---|
494 | float maxt = 1e6; |
---|
495 | float mint = 0; |
---|
496 | |
---|
497 | |
---|
498 | if (!mBox.GetMinMaxT(ray, &mint, &maxt)) |
---|
499 | return 0; |
---|
500 | |
---|
501 | if (mint < 0) |
---|
502 | mint = 0; |
---|
503 | |
---|
504 | maxt += Limits::Threshold; |
---|
505 | |
---|
506 | Vector3 entp = ray.Extrap(mint); |
---|
507 | Vector3 extp = ray.Extrap(maxt); |
---|
508 | |
---|
509 | KdNode *node = mRoot; |
---|
510 | KdNode *farChild; |
---|
511 | float position; |
---|
512 | int axis; |
---|
513 | |
---|
514 | while (1) { |
---|
515 | if (!node->IsLeaf()) { |
---|
516 | KdInterior *in = (KdInterior *) node; |
---|
517 | position = in->mPosition; |
---|
518 | axis = in->mAxis; |
---|
519 | |
---|
520 | if (entp[axis] <= position) { |
---|
521 | if (extp[axis] <= position) { |
---|
522 | node = in->mBack; |
---|
523 | // cases N1,N2,N3,P5,Z2,Z3 |
---|
524 | continue; |
---|
525 | } else { |
---|
526 | // case N4 |
---|
527 | node = in->mBack; |
---|
528 | farChild = in->mFront; |
---|
529 | } |
---|
530 | } |
---|
531 | else { |
---|
532 | if (position <= extp[axis]) { |
---|
533 | node = in->mFront; |
---|
534 | // cases P1,P2,P3,N5,Z1 |
---|
535 | continue; |
---|
536 | } else { |
---|
537 | node = in->mFront; |
---|
538 | farChild = in->mBack; |
---|
539 | // case P4 |
---|
540 | } |
---|
541 | } |
---|
542 | // $$ modification 3.5.2004 - hints from Kamil Ghais |
---|
543 | // case N4 or P4 |
---|
544 | float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis); |
---|
545 | tStack.push(RayTraversalData(farChild, extp, maxt)); |
---|
546 | extp = ray.GetLoc() + ray.GetDir()*tdist; |
---|
547 | maxt = tdist; |
---|
548 | } else { |
---|
549 | // compute intersection with all objects in this leaf |
---|
550 | KdLeaf *leaf = (KdLeaf *) node; |
---|
551 | ray.leaves.push_back(leaf); |
---|
552 | |
---|
553 | MeshContainer::const_iterator mi; |
---|
554 | for ( mi = leaf->mObjects.begin(); |
---|
555 | mi != leaf->mObjects.end(); |
---|
556 | mi++) { |
---|
557 | MeshInstance *mesh = *mi; |
---|
558 | if (!mesh->Mailed() ) { |
---|
559 | mesh->Mail(); |
---|
560 | //ray.meshes.push_back(mesh); |
---|
561 | hits += mesh->CastRay(ray); |
---|
562 | } |
---|
563 | } |
---|
564 | |
---|
565 | if (hits && ray.GetType() == Ray::LOCAL_RAY) |
---|
566 | if (ray.intersections[0].mT <= maxt) |
---|
567 | break; |
---|
568 | |
---|
569 | // get the next node from the stack |
---|
570 | if (tStack.empty()) |
---|
571 | break; |
---|
572 | |
---|
573 | entp = extp; |
---|
574 | mint = maxt; |
---|
575 | RayTraversalData &s = tStack.top(); |
---|
576 | node = s.mNode; |
---|
577 | extp = s.mExitPoint; |
---|
578 | maxt = s.mMaxT; |
---|
579 | tStack.pop(); |
---|
580 | } |
---|
581 | } |
---|
582 | |
---|
583 | |
---|
584 | return hits; |
---|
585 | } |
---|
586 | |
---|