traverseFunctions.js 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431
  1. import { LOADED, FAILED } from './constants.js';
  2. function isDownloadFinished( value ) {
  3. return value === LOADED || value === FAILED;
  4. }
  5. // Checks whether this tile was last used on the given frame.
  6. function isUsedThisFrame( tile, frameCount ) {
  7. return tile.__lastFrameVisited === frameCount && tile.__used;
  8. }
  9. // Resets the frame frame information for the given tile
  10. function resetFrameState( tile, frameCount ) {
  11. if ( tile.__lastFrameVisited !== frameCount ) {
  12. tile.__lastFrameVisited = frameCount;
  13. tile.__used = false;
  14. tile.__inFrustum = false;
  15. tile.__isLeaf = false;
  16. tile.__visible = false;
  17. tile.__active = false;
  18. tile.__error = 0;
  19. tile.__childrenWereVisible = false;
  20. tile.__allChildrenLoaded = false;
  21. }
  22. }
  23. // Recursively mark tiles used down to the next tile with content
  24. function recursivelyMarkUsed( tile, frameCount, lruCache ) {
  25. resetFrameState( tile, frameCount );
  26. tile.__used = true;
  27. lruCache.markUsed( tile );
  28. if ( tile.__contentEmpty ) {
  29. const children = tile.children;
  30. for ( let i = 0, l = children.length; i < l; i ++ ) {
  31. recursivelyMarkUsed( children[ i ], frameCount, lruCache );
  32. }
  33. }
  34. }
  35. function recursivelyLoadTiles( tile, depthFromRenderedParent, renderer ) {
  36. // Try to load any external tile set children if the external tile set has loaded.
  37. const doTraverse =
  38. tile.__contentEmpty && (
  39. ! tile.__externalTileSet ||
  40. isDownloadFinished( tile.__loadingState )
  41. );
  42. if ( doTraverse ) {
  43. const children = tile.children;
  44. for ( let i = 0, l = children.length; i < l; i ++ ) {
  45. // don't increment depth to rendered parent here because we should treat
  46. // the next layer of rendered children as just a single depth away for the
  47. // sake of sorting.
  48. const child = children[ i ];
  49. child.__depthFromRenderedParent = depthFromRenderedParent;
  50. recursivelyLoadTiles( child, depthFromRenderedParent, renderer );
  51. }
  52. } else {
  53. renderer.requestTileContents( tile );
  54. }
  55. }
  56. // Helper function for recursively traversing a tile set. If `beforeCb` returns `true` then the
  57. // traversal will end early.
  58. export function traverseSet( tile, beforeCb = null, afterCb = null, parent = null, depth = 0 ) {
  59. if ( beforeCb && beforeCb( tile, parent, depth ) ) {
  60. if ( afterCb ) {
  61. afterCb( tile, parent, depth );
  62. }
  63. return;
  64. }
  65. const children = tile.children;
  66. for ( let i = 0, l = children.length; i < l; i ++ ) {
  67. traverseSet( children[ i ], beforeCb, afterCb, tile, depth + 1 );
  68. }
  69. if ( afterCb ) {
  70. afterCb( tile, parent, depth );
  71. }
  72. }
  73. // Determine which tiles are within the camera frustum.
  74. // TODO: this is marking items as used in the lrucache, which means some data is
  75. // being kept around that isn't being used -- is that okay?
  76. export function determineFrustumSet( tile, renderer ) {
  77. const stats = renderer.stats;
  78. const frameCount = renderer.frameCount;
  79. const errorTarget = renderer.errorTarget;
  80. const maxDepth = renderer.maxDepth;
  81. const loadSiblings = renderer.loadSiblings;
  82. const lruCache = renderer.lruCache;
  83. const stopAtEmptyTiles = renderer.stopAtEmptyTiles;
  84. resetFrameState( tile, frameCount );
  85. // Early out if this tile is not within view.
  86. const inFrustum = renderer.tileInView( tile );
  87. if ( inFrustum === false ) {
  88. return false;
  89. }
  90. tile.__used = true;
  91. lruCache.markUsed( tile );
  92. tile.__inFrustum = true;
  93. stats.inFrustum ++;
  94. // Early out if this tile has less error than we're targeting but don't stop
  95. // at an external tile set.
  96. if ( ( stopAtEmptyTiles || ! tile.__contentEmpty ) && ! tile.__externalTileSet ) {
  97. const error = renderer.calculateError( tile );
  98. tile.__error = error;
  99. if ( error <= errorTarget ) {
  100. return true;
  101. }
  102. // Early out if we've reached the maximum allowed depth.
  103. if ( renderer.maxDepth > 0 && tile.__depth + 1 >= maxDepth ) {
  104. return true;
  105. }
  106. }
  107. // Traverse children and see if any children are in view.
  108. let anyChildrenUsed = false;
  109. const children = tile.children;
  110. for ( let i = 0, l = children.length; i < l; i ++ ) {
  111. const c = children[ i ];
  112. const r = determineFrustumSet( c, renderer );
  113. anyChildrenUsed = anyChildrenUsed || r;
  114. }
  115. // If there are children within view and we are loading siblings then mark
  116. // all sibling tiles as used, as well.
  117. if ( anyChildrenUsed && loadSiblings ) {
  118. for ( let i = 0, l = children.length; i < l; i ++ ) {
  119. const c = children[ i ];
  120. recursivelyMarkUsed( c, frameCount, lruCache );
  121. }
  122. }
  123. return true;
  124. }
  125. // Traverse and mark the tiles that are at the leaf nodes of the "used" tree.
  126. export function markUsedSetLeaves( tile, renderer ) {
  127. const stats = renderer.stats;
  128. const frameCount = renderer.frameCount;
  129. if ( ! isUsedThisFrame( tile, frameCount ) ) {
  130. return;
  131. }
  132. stats.used ++;
  133. // This tile is a leaf if none of the children had been used.
  134. const children = tile.children;
  135. let anyChildrenUsed = false;
  136. for ( let i = 0, l = children.length; i < l; i ++ ) {
  137. const c = children[ i ];
  138. anyChildrenUsed = anyChildrenUsed || isUsedThisFrame( c, frameCount );
  139. }
  140. if ( ! anyChildrenUsed ) {
  141. // TODO: This isn't necessarily right because it's possible that a parent tile is considered in the
  142. // frustum while the child tiles are not, making them unused. If all children have loaded and were properly
  143. // considered to be in the used set then we shouldn't set ourselves to a leaf here.
  144. tile.__isLeaf = true;
  145. } else {
  146. let childrenWereVisible = false;
  147. let allChildrenLoaded = true;
  148. for ( let i = 0, l = children.length; i < l; i ++ ) {
  149. const c = children[ i ];
  150. markUsedSetLeaves( c, renderer );
  151. childrenWereVisible = childrenWereVisible || c.__wasSetVisible || c.__childrenWereVisible;
  152. if ( isUsedThisFrame( c, frameCount ) ) {
  153. const childLoaded = ( ! c.__contentEmpty && isDownloadFinished( c.__loadingState ) ) || c.__allChildrenLoaded;
  154. allChildrenLoaded = allChildrenLoaded && childLoaded;
  155. }
  156. }
  157. tile.__childrenWereVisible = childrenWereVisible;
  158. // If there are no children then all the children should be considered loaded. However if it's
  159. // an external tile set then we must wait until the children have loaded.
  160. tile.__allChildrenLoaded = children.length === 0 ? ! tile.__externalTileSet : allChildrenLoaded;
  161. }
  162. }
  163. // Skip past tiles we consider unrenderable because they are outside the error threshold.
  164. export function skipTraversal( tile, renderer ) {
  165. const stats = renderer.stats;
  166. const frameCount = renderer.frameCount;
  167. if ( ! isUsedThisFrame( tile, frameCount ) ) {
  168. return;
  169. }
  170. const parent = tile.parent;
  171. const parentDepthToParent = parent ? parent.__depthFromRenderedParent : - 1;
  172. tile.__depthFromRenderedParent = parentDepthToParent;
  173. // Request the tile contents or mark it as visible if we've found a leaf.
  174. const lruCache = renderer.lruCache;
  175. if ( tile.__isLeaf ) {
  176. tile.__depthFromRenderedParent ++;
  177. if ( tile.__loadingState === LOADED ) {
  178. if ( tile.__inFrustum ) {
  179. tile.__visible = true;
  180. stats.visible ++;
  181. }
  182. tile.__active = true;
  183. stats.active ++;
  184. } else if ( ! lruCache.isFull() && ( ! tile.__contentEmpty || tile.__externalTileSet ) ) {
  185. renderer.requestTileContents( tile );
  186. }
  187. return;
  188. }
  189. const errorRequirement = ( renderer.errorTarget + 1 ) * renderer.errorThreshold;
  190. const meetsSSE = tile.__error <= errorRequirement;
  191. const includeTile = meetsSSE || tile.refine === 'ADD';
  192. const hasModel = ! tile.__contentEmpty;
  193. const hasContent = hasModel || tile.__externalTileSet;
  194. const loadedContent = isDownloadFinished( tile.__loadingState ) && hasContent;
  195. const childrenWereVisible = tile.__childrenWereVisible;
  196. const children = tile.children;
  197. let allChildrenHaveContent = tile.__allChildrenLoaded;
  198. // Increment the relative depth of the node to the nearest rendered parent if it has content
  199. // and is being rendered.
  200. if ( includeTile && hasModel ) {
  201. tile.__depthFromRenderedParent ++;
  202. }
  203. // If we've met the SSE requirements and we can load content then fire a fetch.
  204. if ( includeTile && ! loadedContent && ! lruCache.isFull() && hasContent ) {
  205. renderer.requestTileContents( tile );
  206. }
  207. // Only mark this tile as visible if it meets the screen space error requirements, has loaded content, not
  208. // all children have loaded yet, and if no children were visible last frame. We want to keep children visible
  209. // that _were_ visible to avoid a pop in level of detail as the camera moves around and parent / sibling tiles
  210. // load in.
  211. // Skip the tile entirely if there's no content to load
  212. if (
  213. ( meetsSSE && ! allChildrenHaveContent && ! childrenWereVisible && loadedContent )
  214. || ( tile.refine === 'ADD' && loadedContent )
  215. ) {
  216. if ( tile.__inFrustum ) {
  217. tile.__visible = true;
  218. stats.visible ++;
  219. }
  220. tile.__active = true;
  221. stats.active ++;
  222. }
  223. // If we're additive then don't stop the traversal here because it doesn't matter whether the children load in
  224. // at the same rate.
  225. if ( tile.refine !== 'ADD' && meetsSSE && ! allChildrenHaveContent && loadedContent ) {
  226. // load the child content if we've found that we've been loaded so we can move down to the next tile
  227. // layer when the data has loaded.
  228. for ( let i = 0, l = children.length; i < l; i ++ ) {
  229. const c = children[ i ];
  230. if ( isUsedThisFrame( c, frameCount ) && ! lruCache.isFull() ) {
  231. c.__depthFromRenderedParent = tile.__depthFromRenderedParent + 1;
  232. recursivelyLoadTiles( c, c.__depthFromRenderedParent, renderer );
  233. }
  234. }
  235. } else {
  236. for ( let i = 0, l = children.length; i < l; i ++ ) {
  237. const c = children[ i ];
  238. if ( isUsedThisFrame( c, frameCount ) ) {
  239. skipTraversal( c, renderer );
  240. }
  241. }
  242. }
  243. }
  244. // Final traverse to toggle tile visibility.
  245. export function toggleTiles( tile, renderer ) {
  246. const frameCount = renderer.frameCount;
  247. const isUsed = isUsedThisFrame( tile, frameCount );
  248. if ( isUsed || tile.__usedLastFrame ) {
  249. let setActive = false;
  250. let setVisible = false;
  251. if ( isUsed ) {
  252. // enable visibility if active due to shadows
  253. setActive = tile.__active;
  254. if ( renderer.displayActiveTiles ) {
  255. setVisible = tile.__active || tile.__visible;
  256. } else {
  257. setVisible = tile.__visible;
  258. }
  259. }
  260. // If the active or visible state changed then call the functions.
  261. if ( ! tile.__contentEmpty && tile.__loadingState === LOADED ) {
  262. if ( tile.__wasSetActive !== setActive ) {
  263. renderer.setTileActive( tile, setActive );
  264. }
  265. if ( tile.__wasSetVisible !== setVisible ) {
  266. renderer.setTileVisible( tile, setVisible );
  267. }
  268. }
  269. tile.__wasSetActive = setActive;
  270. tile.__wasSetVisible = setVisible;
  271. tile.__usedLastFrame = isUsed;
  272. const children = tile.children;
  273. for ( let i = 0, l = children.length; i < l; i ++ ) {
  274. const c = children[ i ];
  275. toggleTiles( c, renderer );
  276. }
  277. }
  278. }