46 const scalar nearestDistSqr,
54 for (
direction dir = 0; dir < vector::nComponents; dir++)
56 scalar d0 = p0[dir] - sample[dir];
57 scalar d1 = p1[dir] - sample[dir];
59 if ((d0 > 0) != (d1 > 0))
64 else if (
mag(d0) <
mag(d1))
73 if (distSqr > nearestDistSqr)
90 const scalar nearestDistSqr,
109 if (octant & treeBoundBox::RIGHTHALF)
118 if (octant & treeBoundBox::TOPHALF)
127 if (octant & treeBoundBox::FRONTHALF)
136 const point mid(0.5*(min+max));
138 return overlaps(mid, other, nearestDistSqr, sample);
148 template <
class Type>
152 const treeBoundBox& bb,
156 List<DynamicList<label> > subIndices(8);
157 for (
direction octant = 0; octant < subIndices.size(); octant++)
159 subIndices[octant].setCapacity(indices.size()/8);
163 FixedList<treeBoundBox, 8> subBbs;
164 for (
direction octant = 0; octant < subBbs.size(); octant++)
166 subBbs[octant] = bb.subBbox(octant);
171 label shapeI = indices[i];
173 for (
direction octant = 0; octant < 8; octant++)
175 if (shapes_.overlaps(shapeI, subBbs[octant]))
177 subIndices[octant].append(shapeI);
183 for (
direction octant = 0; octant < subIndices.size(); octant++)
185 result[octant].transfer(subIndices[octant]);
191 template <
class Type>
195 const treeBoundBox& bb,
196 DynamicList<labelList>& contents,
200 const labelList& indices = contents[contentI];
206 bb.min()[0] >= bb.max()[0]
207 || bb.min()[1] >= bb.max()[1]
208 || bb.min()[2] >= bb.max()[2]
212 <<
"Badly formed bounding box:" << bb
220 divide(indices, bb, dividedIndices);
225 bool replaced =
false;
227 for (
direction octant = 0; octant < dividedIndices.size(); octant++)
229 labelList& subIndices = dividedIndices[octant];
231 if (subIndices.size())
235 contents[contentI].
transfer(subIndices);
236 nod.subNodes_[octant] = contentPlusOctant(contentI, octant);
243 label sz = contents.size();
245 contents[sz].transfer(subIndices);
246 nod.subNodes_[octant] = contentPlusOctant(sz, octant);
252 nod.subNodes_[octant] = emptyPlusOctant(octant);
261 template <
class Type>
265 DynamicList<indexedOctree<Type>::node>& nodes,
266 DynamicList<labelList>& contents
269 label currentSize = nodes.size();
274 for (label nodeI = 0; nodeI < currentSize; nodeI++)
279 octant < nodes[nodeI].subNodes_.size();
283 labelBits index = nodes[nodeI].subNodes_[octant];
289 else if (isContent(index))
291 label contentI = getContent(index);
293 if (contents[contentI].size() > minSize)
298 const node& nod = nodes[nodeI];
299 const treeBoundBox bb(nod.bb_.subBbox(octant));
301 node subNode(
divide(bb, contents, contentI));
302 subNode.parent_ = nodeI;
303 label sz = nodes.size();
304 nodes.append(subNode);
305 nodes[nodeI].subNodes_[octant] = nodePlusOctant(sz, octant);
315 template <
class Type>
318 DynamicList<node>& nodes,
319 DynamicList<labelList>& contents,
320 const label compactLevel,
324 List<labelList>& compactedContents,
328 const node& nod = nodes[nodeI];
332 if (level < compactLevel)
334 for (
direction octant = 0; octant < nod.subNodes_.size(); octant++)
336 labelBits index = nod.subNodes_[octant];
340 nNodes += compactContents
353 else if (level == compactLevel)
356 for (
direction octant = 0; octant < nod.subNodes_.size(); octant++)
358 labelBits index = nod.subNodes_[octant];
360 if (isContent(index))
362 label contentI = getContent(index);
364 compactedContents[compactI].transfer(contents[contentI]);
367 nodes[nodeI].subNodes_[octant] =
368 contentPlusOctant(compactI, octant);
372 else if (isNode(index))
385 template <
class Type>
392 const node& nod = nodes_[nodeI];
394 volumeType myType = UNKNOWN;
396 for (
direction octant = 0; octant < nod.subNodes_.size(); octant++)
400 labelBits index = nod.subNodes_[octant];
405 subType = calcVolumeType(getNode(index));
407 else if (isContent(index))
417 const treeBoundBox subBb = nod.bb_.subBbox(octant);
421 shapes_.getVolumeType(*
this, subBb.midpoint())
426 nodeTypes_.set((nodeI<<3)+octant, subType);
430 if (myType == UNKNOWN)
434 else if (subType != myType)
443 template <
class Type>
451 const node& nod = nodes_[nodeI];
453 direction octant = nod.bb_.subOctant(sample);
455 volumeType octantType = volumeType(nodeTypes_.get((nodeI<<3)+octant));
457 if (octantType == INSIDE)
461 else if (octantType == OUTSIDE)
465 else if (octantType == UNKNOWN)
470 else if (octantType == MIXED)
472 labelBits index = nod.subNodes_[octant];
477 volumeType subType = getVolumeType(getNode(index), sample);
481 else if (isContent(index))
484 return volumeType(shapes_.getVolumeType(*
this, sample));
492 "indexedOctree<Type>::getVolumeType"
493 "(const label, const point&)"
494 ) <<
"Sample:" << sample <<
" node:" << nodeI
495 <<
" with bb:" << nodes_[nodeI].bb_ <<
nl
496 <<
"Empty subnode has invalid volume type MIXED."
506 "indexedOctree<Type>::getVolumeType"
507 "(const label, const point&)"
508 ) <<
"Sample:" << sample <<
" at node:" << nodeI
509 <<
" octant:" << octant
510 <<
" with bb:" << nod.bb_.subBbox(octant) <<
nl
511 <<
"Node has invalid volume type " << octantType
519 template <
class Type>
523 const vector& outsideNormal,
527 if ((outsideNormal&vec) >= 0)
544 template <
class Type>
550 scalar& nearestDistSqr,
551 label& nearestShapeI,
555 const node& nod = nodes_[nodeI];
570 label subNodeI = getNode(index);
574 if (overlaps(subBb.
min(), subBb.
max(), nearestDistSqr, sample))
587 else if (isContent(index))
602 contents_[getContent(index)],
616 template <
class Type>
623 label& nearestShapeI,
628 const node& nod = nodes_[nodeI];
633 nod.bb_.searchOrder(ln.
centre(), octantOrder);
660 else if (isContent(index))
662 const treeBoundBox subBb(nodeBb.
subBbox(octant));
668 contents_[getContent(index)],
682 template <
class Type>
685 const label parentNodeI,
690 const node& nod = nodes_[parentNodeI];
691 labelBits index = nod.subNodes_[octant];
696 return nodes_[getNode(index)].bb_;
701 return nod.bb_.subBbox(octant);
708 template <
class Type>
711 const treeBoundBox& bb,
713 const bool pushInside
717 const vector perturbVec = perturbTol_*(bb.span());
719 point perturbedPt(pt);
726 for (
direction dir = 0; dir < vector::nComponents; dir++)
728 if (
mag(pt[dir]-bb.min()[dir]) <
mag(perturbVec[dir]))
731 scalar perturbDist = perturbVec[dir] + ROOTVSMALL;
732 perturbedPt[dir] = bb.min()[dir] + perturbDist;
734 else if (
mag(pt[dir]-bb.max()[dir]) <
mag(perturbVec[dir]))
737 scalar perturbDist = perturbVec[dir] + ROOTVSMALL;
738 perturbedPt[dir] = bb.max()[dir] - perturbDist;
744 for (
direction dir = 0; dir < vector::nComponents; dir++)
746 if (
mag(pt[dir]-bb.min()[dir]) <
mag(perturbVec[dir]))
748 scalar perturbDist = perturbVec[dir] + ROOTVSMALL;
749 perturbedPt[dir] = bb.min()[dir] - perturbDist;
751 else if (
mag(pt[dir]-bb.max()[dir]) <
mag(perturbVec[dir]))
753 scalar perturbDist = perturbVec[dir] + ROOTVSMALL;
754 perturbedPt[dir] = bb.max()[dir] + perturbDist;
761 if (pushInside != bb.contains(perturbedPt))
764 <<
"pushed point:" << pt
765 <<
" to:" << perturbedPt
766 <<
" wanted side:" << pushInside
767 <<
" obtained side:" << bb.contains(perturbedPt)
779 template <
class Type>
782 const treeBoundBox& bb,
785 const bool pushInside
789 const vector perturbVec = perturbTol_*bb.span();
791 point perturbedPt(pt);
802 if (faceID & treeBoundBox::LEFTBIT)
806 perturbedPt[0] = bb.min()[0] + (perturbVec[0] + ROOTVSMALL);
810 perturbedPt[0] = bb.min()[0] - (perturbVec[0] + ROOTVSMALL);
813 else if (faceID & treeBoundBox::RIGHTBIT)
817 perturbedPt[0] = bb.max()[0] - (perturbVec[0] + ROOTVSMALL);
821 perturbedPt[0] = bb.max()[0] + (perturbVec[0] + ROOTVSMALL);
825 if (faceID & treeBoundBox::BOTTOMBIT)
829 perturbedPt[1] = bb.min()[1] + (perturbVec[1] + ROOTVSMALL);
833 perturbedPt[1] = bb.min()[1] - (perturbVec[1] + ROOTVSMALL);
836 else if (faceID & treeBoundBox::TOPBIT)
840 perturbedPt[1] = bb.max()[1] - (perturbVec[1] + ROOTVSMALL);
844 perturbedPt[1] = bb.max()[1] + (perturbVec[1] + ROOTVSMALL);
848 if (faceID & treeBoundBox::BACKBIT)
852 perturbedPt[2] = bb.min()[2] + (perturbVec[2] + ROOTVSMALL);
856 perturbedPt[2] = bb.min()[2] - (perturbVec[2] + ROOTVSMALL);
859 else if (faceID & treeBoundBox::FRONTBIT)
863 perturbedPt[2] = bb.max()[2] - (perturbVec[2] + ROOTVSMALL);
867 perturbedPt[2] = bb.max()[2] + (perturbVec[2] + ROOTVSMALL);
873 if (pushInside != bb.contains(perturbedPt))
876 <<
"pushed point:" << pt <<
" on face:" << faceString(faceID)
877 <<
" to:" << perturbedPt
878 <<
" wanted side:" << pushInside
879 <<
" obtained side:" << bb.contains(perturbedPt)
892 template <
class Type>
895 const treeBoundBox& bb,
902 if (bb.posBits(pt) != 0)
904 FatalErrorIn(
"indexedOctree<Type>::pushPointIntoFace(..)")
905 <<
" bb:" << bb <<
endl
918 FixedList<direction, 3> faceIndices;
920 if (ptFaceID & treeBoundBox::LEFTBIT)
922 faceIndices[nFaces++] = treeBoundBox::LEFT;
924 else if (ptFaceID & treeBoundBox::RIGHTBIT)
926 faceIndices[nFaces++] = treeBoundBox::RIGHT;
929 if (ptFaceID & treeBoundBox::BOTTOMBIT)
931 faceIndices[nFaces++] = treeBoundBox::BOTTOM;
933 else if (ptFaceID & treeBoundBox::TOPBIT)
935 faceIndices[nFaces++] = treeBoundBox::TOP;
938 if (ptFaceID & treeBoundBox::BACKBIT)
940 faceIndices[nFaces++] = treeBoundBox::BACK;
942 else if (ptFaceID & treeBoundBox::FRONTBIT)
944 faceIndices[nFaces++] = treeBoundBox::FRONT;
957 else if (nFaces == 1)
960 keepFaceID = faceIndices[0];
967 keepFaceID = faceIndices[0];
968 scalar maxInproduct =
mag(treeBoundBox::faceNormals[keepFaceID] & dir);
973 scalar s =
mag(treeBoundBox::faceNormals[face] & dir);
974 if (s > maxInproduct)
985 point facePoint(pushPoint(bb, pt,
true));
990 if (keepFaceID == treeBoundBox::LEFT)
992 facePoint.x() = bb.min().x();
993 faceID = treeBoundBox::LEFTBIT;
995 else if (keepFaceID == treeBoundBox::RIGHT)
997 facePoint.x() = bb.max().x();
998 faceID = treeBoundBox::RIGHTBIT;
1000 else if (keepFaceID == treeBoundBox::BOTTOM)
1002 facePoint.y() = bb.min().y();
1003 faceID = treeBoundBox::BOTTOMBIT;
1005 else if (keepFaceID == treeBoundBox::TOP)
1007 facePoint.y() = bb.max().y();
1008 faceID = treeBoundBox::TOPBIT;
1010 else if (keepFaceID == treeBoundBox::BACK)
1012 facePoint.z() = bb.min().z();
1013 faceID = treeBoundBox::BACKBIT;
1015 else if (keepFaceID == treeBoundBox::FRONT)
1017 facePoint.z() = bb.max().z();
1018 faceID = treeBoundBox::FRONTBIT;
1024 if (faceID != bb.faceBits(facePoint))
1026 FatalErrorIn(
"indexedOctree<Type>::pushPointIntoFace(..)")
1027 <<
"Pushed point from " << pt
1028 <<
" on face:" << ptFaceID <<
" of bb:" << bb <<
endl
1029 <<
"onto " << facePoint
1030 <<
" on face:" << faceID
1031 <<
" which is not consistent with geometric face "
1032 << bb.faceBits(facePoint)
1035 if (bb.posBits(facePoint) != 0)
1037 FatalErrorIn(
"indexedOctree<Type>::pushPointIntoFace(..)")
1038 <<
" bb:" << bb <<
endl
1039 <<
"does not contain perturbed point "
1247 template <
class Type>
1257 parentNodeI = nodes_[nodeI].parent_;
1259 if (parentNodeI == -1)
1265 const node& parentNode = nodes_[parentNodeI];
1270 for (
direction i = 0; i < parentNode.subNodes_.size(); i++)
1272 labelBits index = parentNode.subNodes_[i];
1274 if (isNode(index) && getNode(index) == nodeI)
1281 if (parentOctant == 255)
1284 <<
"Problem: no parent found for octant:" << octant
1285 <<
" node:" << nodeI
1297 template <
class Type>
1300 const point& facePoint,
1306 label oldNodeI = nodeI;
1314 const direction X = treeBoundBox::RIGHTHALF;
1316 const direction Z = treeBoundBox::FRONTHALF;
1321 if ((faceID & treeBoundBox::LEFTBIT) != 0)
1327 else if ((faceID & treeBoundBox::RIGHTBIT) != 0)
1332 if ((faceID & treeBoundBox::BOTTOMBIT) != 0)
1338 else if ((faceID & treeBoundBox::TOPBIT) != 0)
1344 if ((faceID & treeBoundBox::BACKBIT) != 0)
1349 else if ((faceID & treeBoundBox::FRONTBIT) != 0)
1381 while (wantedValue != (octant & octantMask))
1387 if (wantedValue & X)
1407 if (wantedValue & Y)
1424 if (wantedValue & Z)
1444 walkToParent(nodeI, octant, parentNodeI, parentOctant);
1446 if (parentNodeI == -1)
1461 nodeI = parentNodeI;
1462 octant = parentOctant;
1468 octant ^= octantMask;
1476 const treeBoundBox subBb(subBbox(nodeI, octant));
1480 FatalErrorIn(
"indexedOctree<Type>::walkToNeighbour(..)")
1481 <<
"When searching for " << facePoint
1482 <<
" ended up in node:" << nodeI
1483 <<
" octant:" << octant
1484 <<
" with bb:" << subBb
1492 labelBits index = nodes_[nodeI].subNodes_[octant];
1496 labelBits node = findNode(getNode(index), facePoint);
1498 nodeI = getNode(node);
1499 octant = getOctant(node);
1505 const treeBoundBox subBb(subBbox(nodeI, octant));
1507 if (nodeI == oldNodeI && octant == oldOctant)
1509 FatalErrorIn(
"indexedOctree<Type>::walkToNeighbour(..)")
1510 <<
"Did not go to neighbour when searching for " << facePoint
1512 <<
" starting from face:" << faceString(faceID)
1513 <<
" node:" << nodeI
1514 <<
" octant:" << octant
1521 FatalErrorIn(
"indexedOctree<Type>::walkToNeighbour(..)")
1522 <<
"When searching for " << facePoint
1523 <<
" ended up in node:" << nodeI
1524 <<
" octant:" << octant
1535 template <
class Type>
1547 if (faceID & treeBoundBox::LEFTBIT)
1549 if (!desc.empty()) desc +=
"+";
1552 if (faceID & treeBoundBox::RIGHTBIT)
1554 if (!desc.empty()) desc +=
"+";
1557 if (faceID & treeBoundBox::BOTTOMBIT)
1559 if (!desc.empty()) desc +=
"+";
1562 if (faceID & treeBoundBox::TOPBIT)
1564 if (!desc.empty()) desc +=
"+";
1567 if (faceID & treeBoundBox::BACKBIT)
1569 if (!desc.empty()) desc +=
"+";
1572 if (faceID & treeBoundBox::FRONTBIT)
1574 if (!desc.empty()) desc +=
"+";
1587 template <
class Type>
1591 const point& treeStart,
1605 const treeBoundBox octantBb(subBbox(nodeI, octant));
1607 if (octantBb.posBits(start) != 0)
1610 <<
"Node:" << nodeI <<
" octant:" << octant
1611 <<
" bb:" << octantBb <<
endl
1617 const node& nod = nodes_[nodeI];
1619 labelBits index = nod.subNodes_[octant];
1621 if (isContent(index))
1623 const labelList& indices = contents_[getContent(index)];
1631 label shapeI = indices[elemI];
1634 bool hit = shapes_.intersects(shapeI, start, end, pt);
1641 hitInfo.setIndex(shapeI);
1642 hitInfo.setPoint(pt);
1651 point nearestPoint(end);
1655 label shapeI = indices[elemI];
1658 bool hit = shapes_.intersects(shapeI, start, nearestPoint, pt);
1666 hitInfo.setIndex(shapeI);
1667 hitInfo.setPoint(pt);
1684 const treeBoundBox octantBb(subBbox(nodeI, octant));
1687 bool intersected = octantBb.intersects
1703 hitInfo.setPoint(pt);
1712 point perturbedEnd(pushPoint(octantBb, end,
false));
1721 OFstream str(
"ray.obj");
1724 str <<
"l 1 2" <<
nl;
1726 WarningIn(
"indexedOctree<Type>::traverseNode(..)")
1727 <<
"Did not intersect ray from endpoint:" << end
1728 <<
" to startpoint:" << start
1729 <<
" with bounding box:" << octantBb <<
nl
1730 <<
"Re-intersecting with perturbed endpoint:" << perturbedEnd
1752 template <
class Type>
1756 const point& treeStart,
1757 const point& treeEnd,
1758 const label startNodeI,
1763 const vector treeVec(treeEnd - treeStart);
1766 label nodeI = startNodeI;
1771 Pout<<
"findLine : treeStart:" << treeStart
1772 <<
" treeEnd:" << treeEnd <<
endl
1774 <<
" octant:" << octant
1775 <<
" bb:" << subBbox(nodeI, octant) <<
endl;
1783 for (; i < 100000; i++)
1788 const treeBoundBox octantBb(subBbox(nodeI, octant));
1804 <<
" at current:" << hitInfo.rawPoint()
1805 <<
" (perturbed:" << startPoint <<
")" <<
endl
1806 <<
" node:" << nodeI
1807 <<
" octant:" << octant
1808 <<
" bb:" << subBbox(nodeI, octant) <<
endl;
1839 if (hitFaceID == 0 || hitInfo.rawPoint() == treeEnd)
1846 point perturbedPoint
1859 Pout<<
" iter:" << i
1860 <<
" hit face:" << faceString(hitFaceID)
1861 <<
" at:" << hitInfo.rawPoint() <<
nl
1862 <<
" node:" << nodeI
1863 <<
" octant:" << octant
1864 <<
" bb:" << subBbox(nodeI, octant) <<
nl
1865 <<
" walking to neighbour containing:" << perturbedPoint
1874 bool ok = walkToNeighbour
1891 const treeBoundBox octantBb(subBbox(nodeI, octant));
1892 Pout<<
" walked for point:" << hitInfo.rawPoint() <<
endl
1893 <<
" to neighbour node:" << nodeI
1894 <<
" octant:" << octant
1895 <<
" face:" << faceString(octantBb.faceBits(hitInfo.rawPoint()))
1896 <<
" of octantBb:" << octantBb <<
endl
1920 <<
"Got stuck in loop raytracing from:" << treeStart
1921 <<
" to:" << treeEnd <<
endl
1922 <<
"inside top box:" << subBbox(startNodeI, startOctant)
1927 WarningIn(
"indexedOctree<Type>::findLine(..)")
1928 <<
"Got stuck in loop raytracing from:" << treeStart
1929 <<
" to:" << treeEnd <<
endl
1930 <<
"inside top box:" << subBbox(startNodeI, startOctant)
1940 template <
class Type>
1952 const treeBoundBox& treeBb = nodes_[0].bb_;
1957 direction startBit = treeBb.posBits(start);
1960 if ((startBit & endBit) != 0)
1969 point trackStart(start);
1970 point trackEnd(end);
1975 if (!treeBb.intersects(start, end, trackStart))
1984 if (!treeBb.intersects(end, trackStart, trackEnd))
1992 labelBits index = findNode(0, trackStart);
1994 label parentNodeI = getNode(index);
2011 template <
class Type>
2015 const treeBoundBox& searchBox,
2019 const node& nod = nodes_[nodeI];
2020 const treeBoundBox& nodeBb = nod.bb_;
2022 for (
direction octant = 0; octant < nod.subNodes_.size(); octant++)
2024 labelBits index = nod.subNodes_[octant];
2028 const treeBoundBox& subBb = nodes_[getNode(index)].bb_;
2030 if (subBb.overlaps(searchBox))
2032 findBox(getNode(index), searchBox, elements);
2035 else if (isContent(index))
2037 const treeBoundBox subBb(nodeBb.subBbox(octant));
2039 if (subBb.overlaps(searchBox))
2041 const labelList& indices = contents_[getContent(index)];
2045 label shapeI = indices[i];
2047 if (shapes_.overlaps(shapeI, searchBox))
2049 elements.insert(shapeI);
2059 template <
class Type>
2062 const labelBits index
2070 label nodeI = getNode(index);
2072 const node& nod = nodes_[nodeI];
2074 for (
direction octant = 0; octant < nod.subNodes_.size(); octant++)
2076 nElems += countElements(nod.subNodes_[octant]);
2079 else if (isContent(index))
2081 nElems += contents_[getContent(index)].size();
2092 template <
class Type>
2104 labelBits index = nodes_[nodeI].subNodes_[octant];
2110 subBb = nodes_[getNode(index)].bb_;
2112 else if (isContent(index))
2114 subBb = nodes_[nodeI].bb_.subBbox(octant);
2117 Pout<<
"dumpContentNode : writing node:" << nodeI <<
" octant:" << octant
2125 label pointVertI = vertI;
2132 forAll(treeBoundBox::edges, i)
2134 const edge&
e = treeBoundBox::edges[i];
2136 str<<
"l " << e[0]+pointVertI+1 <<
' ' << e[1]+pointVertI+1 <<
nl;
2143 template <
class Type>
2153 template <
class Type>
2163 contents_(contents),
2168 template <
class Type>
2173 const label maxLevels,
2174 const scalar maxLeafRatio,
2175 const scalar maxDuplicity
2185 Pout<<
"indexedOctree<Type>::indexedOctree:" <<
nl
2186 <<
" shapes:" << shapes.size() <<
nl
2187 <<
" bb:" << bb <<
nl
2191 if (shapes.size() == 0)
2202 node topNode(
divide(bb, contents, 0));
2211 for (; nLevels < maxLevels; nLevels++)
2217 nEntries += contents[i].
size();
2222 Pout<<
"indexedOctree<Type>::indexedOctree:" <<
nl
2223 <<
" nLevels:" << nLevels <<
nl
2224 <<
" nEntries per treeLeaf:" << nEntries/contents.
size()
2226 <<
" nEntries per shape (duplicity):"
2227 << nEntries/shapes.size()
2236 nEntries > maxDuplicity*shapes.size()
2244 label nOldNodes = nodes.
size();
2247 label(maxLeafRatio),
2252 if (nOldNodes == nodes.
size())
2266 contents_.setSize(contents.
size());
2284 if (compactI == contents_.size())
2292 nodes_.transfer(nodes);
2300 nEntries += contents_[i].size();
2303 Pout<<
"indexedOctree<Type>::indexedOctree"
2304 <<
" : finished construction of tree of:" << shapes.typeName
2306 <<
" bb:" << this->bb() <<
nl
2307 <<
" shapes:" << shapes.size() <<
nl
2308 <<
" nLevels:" << nLevels <<
nl
2309 <<
" treeNodes:" << nodes_.size() <<
nl
2310 <<
" nEntries:" << nEntries <<
nl
2312 << scalar(nEntries)/contents.
size() <<
nl
2313 <<
" per shape (duplicity):"
2314 << scalar(nEntries)/shapes.size() <<
nl
2320 template <
class Type>
2336 template <
class Type>
2343 template <
class Type>
2346 const point& sample,
2347 const scalar startDistSqr
2350 scalar nearestDistSqr = startDistSqr;
2351 label nearestShapeI = -1;
2371 return pointIndexHit(nearestShapeI != -1, nearestPoint, nearestShapeI);
2375 template <
class Type>
2383 label nearestShapeI = -1;
2404 return pointIndexHit(nearestShapeI != -1, nearestPoint, nearestShapeI);
2409 template <
class Type>
2416 return findLine(
false, start, end);
2421 template <
class Type>
2428 return findLine(
true, start, end);
2432 template <
class Type>
2443 findBox(0, searchBox, elements);
2446 return elements.toc();
2451 template <
class Type>
2461 return nodePlusOctant(nodeI, 0);
2464 const node& nod = nodes_[nodeI];
2471 <<
"Cannot find " << sample <<
" in node " << nodeI
2483 return findNode(getNode(index), sample);
2485 else if (isContent(index))
2488 return nodePlusOctant(nodeI, octant);
2493 return nodePlusOctant(nodeI, octant);
2499 template <
class Type>
2511 if (nodeTypes_.size() != 8*nodes_.size())
2515 nodeTypes_.setSize(8*nodes_.size());
2516 nodeTypes_ = UNKNOWN;
2531 if (type == UNKNOWN)
2535 else if (type == MIXED)
2539 else if (type == INSIDE)
2543 else if (type == OUTSIDE)
2553 Pout<<
"indexedOctree<Type>::getVolumeType : "
2555 <<
" nodes_:" << nodes_.size()
2556 <<
" nodeTypes_:" << nodeTypes_.size()
2557 <<
" nUNKNOWN:" << nUNKNOWN
2558 <<
" nMIXED:" << nMIXED
2559 <<
" nINSIDE:" << nINSIDE
2560 <<
" nOUTSIDE:" << nOUTSIDE
2565 return getVolumeType(0, sample);
2570 template <
class Type>
2574 const bool printContents,
2578 const node& nod = nodes_[nodeI];
2581 os <<
"nodeI:" << nodeI <<
" bb:" << bb <<
nl
2583 <<
"n:" << countElements(nodePlusOctant(nodeI, 0)) <<
nl;
2594 label subNodeI = getNode(index);
2596 os <<
"octant:" << octant
2597 <<
" node: n:" << countElements(index)
2598 <<
" bb:" << subBb <<
endl;
2600 string oldPrefix = os.
prefix();
2601 os.
prefix() =
" " + oldPrefix;
2603 print(os, printContents, subNodeI);
2607 else if (isContent(index))
2609 const labelList& indices = contents_[getContent(index)];
2611 os <<
"octant:" << octant
2612 <<
" content: n:" << indices.
size()
2620 os <<
' ' << indices[j];
2627 os <<
"octant:" << octant <<
" empty:" << subBb <<
endl;
2634 template <
class Type>
2643 template <
class Type>