Comparison of Octree Traversal Algorithms ========================================= Author: Vlastimil Havran Department of Computer Science and Engineering Faculty of Electrical Engineering Czech Technical University in Prague e-mail: havran@fel.cvut.cz Date: 05/Aug/1999 This text is additional material to the Ray Tracing News article on octrees in RTNv12v2 (http://www.acm.org/tog/resources/RTNews/html/rtnv12n2.html#art4). and follows the article on grid spatial data structures http://www.acm.org/tog/resources/RTNews/html/rtnv12n1.html#art3 (also http://www.acm.org/tog/resources/SPD/havran_stats.txt) in the sense that reported set of parameters parameters is the same, so octrees can be directly compared with hierarchical grids as well. Interested reader can find there also the invariants for these measurements and therefore we will not include these in this text. We present here statistics for ray tracing octrees based that was performed on SPD scenes. The algorithms were implemented in C++ in GOLEM rendering system (http://www.cgg.cvut.cz/GOLEM). Tests were conducted on an Intel Pentium II, 350MHz, 128 MBytes RAM, running the Linux operating system, compiler version egcs-1.1.2, compiler option -O2. The scenes are generated by using the default size for the Standard Procedural Databases (http://www.acm.org/tog/resources/SPD/overview.html). In addition, the "lattice" scene included in this package is also used, as well as our own "fluid" scene. This is a fluid simulation around a ball and it has a mirror in the back, so the whole scene is mirrored for the viewer. We used this scene for testing along with the SPD scenes, since it has a reasonable number of objects (2514 spheres and one polygon) and has many reflected rays. We report here set of parameters that can be expressed for octrees and for both uniform and hierarchical grids. They are reported in the following tables. The meaning of parameters is as follows: N_IN[-] .. the number of hierarchical cells(interior nodes) N_V[-] .. the number of elementary cells(leaves) in the hierarchy. These cells contain references to objects. N_EV[-] .. the number of empty elementary cells N_OIV[-] .. the number of references to objects in the elementary cells N_IT[-] .. the number of intersection tests per one ray N_TS[-] .. the number of traversal steps per one ray N_ETS[-] .. the number of elementary cells traversed per one ray N_EETS[-] .. the number of empty elementary cells traversed per one ray T_B[s] .. the time needed to construct the octree data structure T_TR[s] .. the time needed to ray trace the whole image, it includes both ray shooting and color evaluation according to the Phong shading model. Execution times were measured using "getrusage" function and process user time is reported. We do not use additional acceleration tricks such as mail boxes for objects, shadow cache, etc. The measurements should thus reflect the properties of octrees as the spatial data structures well. General notes: 1) The root node is in the depth zero (depth is in some articles also called level). 2) XXX-C means center subdivision; when subdividing the node into eight octants, the subdivision planes are positioned in the center of the bounding box; all the octants created are thus of the same size. 3) XXX-A means adaptive, cost estimate subdivision. The subdivision planes are not positioned in the center, but in the minimum of the cost function estimate along the appropriate axis. This cost function is according to the article: K. Y. Whang et al: {Octree-R: an adaptive octree for efficient ray tracing", IEEE TVCG, Vol. 1, No. 4, pp.343-349, 1995. or: MacDonald and Booth {Heuristics for Ray tracing Using Space Subdivision}, Visual Computer, pp.153-165, Vol 6, No. 6, 1990}. The $N$ positions between spatial and object median are evaluated using cost function and the one with the minimum cost is taken, we chose $N=10$. To be explicit, when the bounding box is of the size $a x b x c$ and the splitting plane is positioned perpendicular to the axis of size $a$ creating two children of sizes $ t x b x c $ and $ (a-t) x b x c $, then cost function estimate is: C = (left + cut) * (t * 2.0 * (b + c) + b * c) + (right + cut) * ((a-t) * 2.0 * (b + c) + b * c); , where $left$ and $right$ is the number of objects on the left and right of splitting plane respectively, and $cut$ is the number of objects straddling the splitting plane. The cost function estimate is evaluated independently for all three axes. 4) When assigning the objects to the suboctants or to leaves, the decision if to assign was implemented using bounding boxes of the objects; no exact object surface with the octant(axis-aligned bounging box) was used. 5) The termination criteria to declare the current node a leaf were taken the ones mostly used: a) when the number of objects reffered to the current octree node is smaller than or equal to a constant MO, then declare this node a leaf. We chose MO=1. b) when the depth of the node reached the maximum depth, then also declare the node a leaf. The maximum depth was set to 4,5,6, and 7, corresponding results are in the columns. Statistics: ========================================================================== Octree84-C ---------- We call by this name the implementation according to the article: A. S. Glassner: {Space Subdivision for Fast Ray Tracing}, IEEE CG&A, pp. 15-22, October 1984. The implementation has been changed in the sense the representation of the octree does not use hash table, but a node with eight pointers. The subdivision is in the center of the current bounding box as described above. maximum depth scene: 4 5 6 7 BALLS N_IN 57 117 304 1108 N_V 400 820 2129 7757 N_EV 300 570 1038 2905 N_OIV 9171 10946 15611 27288 N_IT 1787.00 577.70 209.60 94.75 N_TS 48.53 86.96 123.20 167.00 N_ETS 9.93 15.39 19.88 24.71 N_EETS 3.67 9.52 12.54 16.12 N_B[s] 0.14 0.16 0.20 0.29 N_TR[s] 626.60 227.70 121.80 102.30 FLUID N_IN 14 35 118 423 N_V 99 246 827 2962 N_EV 35 87 313 1164 N_OIV 2988 3731 5248 9355 N_IT 978.00 246.90 88.15 34.73 N_TS 15.79 22.12 32.09 48.18 N_ETS 3.63 4.48 5.68 7.42 N_EETS 0.78 0.95 1.37 2.44 N_B[s] 0.05 0.06 0.07 0.11 N_TR[s] 218.00 61.68 30.50 22.85 GEARS N_IN 265 1405 5837 28447 N_V 1856 9836 40860 199130 N_EV 652 4088 10334 28228 N_OIV 39440 85832 235526 879434 N_IT 157.50 71.38 44.22 39.13 N_TS 27.46 46.49 65.25 88.60 N_ETS 5.71 8.33 10.64 13.20 N_EETS 2.07 4.64 5.66 6.27 N_B[s] 0.27 0.46 0.97 2.69 N_TR[s] 316.10 247.00 260.60 339.50 LATTICE N_IN 585 4681 17993 56235 N_V 4096 32768 125952 393646 N_EV 0 7744 28732 52822 N_OIV 22112 49600 147494 502272 N_IT 28.60 13.80 11.07 10.82 N_TS 22.03 47.88 67.59 77.21 N_ETS 4.41 7.98 10.35 11.36 N_EETS 0.00 1.71 2.91 3.17 N_B[s] 0.23 0.39 0.76 1.90 N_TR[s] 64.53 56.37 61.37 65.65 MOUNT N_IN 232 1019 4716 22630 N_V 1625 7134 33013 158411 N_EV 777 3060 11720 45049 N_OIV 18107 34351 90456 324918 N_IT 42.53 23.72 18.30 18.52 N_TS 22.43 30.89 43.68 60.08 N_ETS 4.92 6.08 7.64 9.44 N_EETS 1.82 2.33 2.83 3.31 N_B[s] 0.17 0.25 0.49 1.30 N_TR[s] 38.70 32.40 34.76 41.19 RINGS N_IN 231 1216 6925 38648 N_V 1618 8513 48476 270537 N_EV 416 2127 10281 49888 N_OIV 22505 44555 133929 565631 N_IT 107.80 47.90 35.12 35.20 N_TS 32.34 53.74 81.90 120.80 N_ETS 6.93 9.92 13.38 17.65 N_EETS 2.91 4.98 6.69 8.29 N_B[s] 0.23 0.34 0.64 1.95 N_TR[s] 179.80 113.50 111.80 133.30 TEAPOT N_IN 227 1001 4100 18066 N_V 1590 7008 28701 126463 N_EV 777 3450 12327 38316 N_OIV 18845 34072 83551 295865 N_IT 184.00 78.30 45.63 40.02 N_TS 33.66 48.74 64.67 83.40 N_ETS 7.61 9.73 11.69 13.75 N_EETS 5.14 7.07 8.61 9.53 N_B[s] 0.18 0.29 0.47 1.14 N_TR[s] 50.55 33.17 30.72 34.12 TETRA N_IN 305 1369 6189 28413 N_V 2136 9584 43324 198892 N_EV 1072 4764 21100 80444 N_OIV 13312 32768 110592 512000 N_IT 120.00 63.58 46.77 47.07 N_TS 21.54 32.08 44.09 58.09 N_ETS 4.72 6.20 7.67 9.21 N_EETS 3.05 4.48 5.93 7.22 N_B[s] 0.10 0.17 0.40 1.56 N_TR[s] 7.27 6.34 6.79 8.00 TREE N_IN 53 101 186 352 N_V 372 708 1303 2465 N_EV 278 556 1054 1801 N_OIV 9029 9670 10915 13725 N_IT 8066.00 4201.00 2098.00 741.30 N_TS 63.48 113.60 169.00 219.30 N_ETS 13.10 20.24 27.16 32.74 N_EETS 3.67 9.91 17.67 23.33 N_B[s] 0.16 0.20 0.24 0.29 N_TR[s] 2907.00 1537.00 805.30 338.20 =========================================================================== Octree84-A ---------- We call by this name the implementation according to the article: A. S. Glassner: {Space Subdivision for Fast Ray Tracing}, IEEE CG&A, pp. 15-22, October 1984. The implementation has been changed in the sense the representation of the octree does not use hash table, but a node with eight pointers. The subdivision uses cost function estimate as described above. maximum depth scene: 4 5 6 7 BALLS N_IN 131 661 3077 15283 N_V 918 4628 21540 106982 N_EV 214 1202 4233 14059 N_OIV 10160 16289 42107 172506 N_IT 81.20 28.62 16.29 14.85 N_TS 27.73 40.09 52.18 64.91 N_ETS 6.63 8.35 9.83 11.21 N_EETS 3.23 4.62 5.48 6.00 N_B[s] 0.55 0.73 1.06 2.05 N_TR[s] 45.74 35.40 36.88 42.18 FLUID N_IN 96 414 1676 6709 N_V 673 2899 11733 46964 N_EV 176 844 2941 6844 N_OIV 5059 9850 28281 111566 N_IT 66.83 27.99 16.60 14.40 N_TS 25.20 37.40 51.29 62.20 N_ETS 5.95 7.64 9.32 10.49 N_EETS 1.83 2.87 3.97 4.49 N_B[s] 0.21 0.31 0.49 1.08 N_TR[s] 25.31 20.74 21.88 24.29 GEARS N_IN 349 1709 10301 59649 N_V 2444 11964 72108 417544 N_EV 580 1120 5300 20092 N_OIV 31144 95016 344580 1737482 N_IT 68.78 41.18 29.43 30.75 N_TS 23.50 31.33 46.99 66.50 N_ETS 5.15 6.18 8.11 10.24 N_EETS 2.60 2.69 2.92 3.24 N_B[s] 0.79 1.26 2.84 9.83 N_TR[s] 206.60 209.70 246.10 330.00 LATTICE N_IN 585 4681 18218 45496 N_V 4096 32768 127527 318473 N_EV 0 7133 33332 34508 N_OIV 18768 42789 121693 467745 N_IT 24.00 9.97 6.71 6.73 N_TS 22.33 46.89 62.82 64.34 N_ETS 4.47 7.82 9.73 9.87 N_EETS 0.00 2.65 4.55 4.60 N_B[s] 0.86 1.23 2.17 4.35 N_TR[s] 60.03 49.32 51.75 52.90 MOUNT N_IN 312 1534 7893 42826 N_V 2185 10739 55252 299783 N_EV 866 3615 14018 41862 N_OIV 21489 47351 150938 692664 N_IT 31.38 17.58 14.00 15.77 N_TS 22.61 29.26 38.53 51.66 N_ETS 4.86 5.77 6.90 8.34 N_EETS 1.99 2.51 2.91 3.14 N_B[s] 0.68 1.01 1.86 5.22 N_TR[s] 32.49 28.34 30.23 36.33 RINGS N_IN 347 2055 12898 73091 N_V 2430 14386 90287 511638 N_EV 406 1718 10688 41430 N_OIV 20867 54320 210965 1175184 N_IT 58.00 32.11 26.16 31.31 N_TS 30.24 44.74 70.31 103.40 N_ETS 6.58 8.55 11.67 15.29 N_EETS 3.39 3.92 5.01 5.84 N_B[s] 0.84 1.21 2.41 7.54 N_TR[s] 109.30 86.47 92.81 119.40 TEAPOT N_IN 330 1703 9055 49691 N_V 2311 11922 63386 347838 N_EV 853 3462 14005 49218 N_OIV 25332 59058 199511 922951 N_IT 106.30 51.53 36.74 37.72 N_TS 35.82 49.20 63.93 81.95 N_ETS 8.02 9.87 11.66 13.63 N_EETS 5.65 6.77 7.69 8.33 N_B[s] 0.88 1.27 2.36 6.61 N_TR[s] 34.77 27.65 28.56 33.27 TETRA N_IN 325 1485 6449 30617 N_V 2276 10396 45144 214320 N_EV 1116 5432 20976 77992 N_OIV 13792 34304 120336 587888 N_IT 99.56 45.46 23.03 25.08 N_TS 21.15 27.69 33.72 39.05 N_ETS 4.68 5.56 6.26 6.82 N_EETS 3.40 4.48 5.33 5.70 N_B[s] 0.38 0.61 1.25 3.82 N_TR[s] 6.48 5.31 5.05 5.57 TREE N_IN 71 278 1130 4300 N_V 498 1947 7911 30101 N_EV 231 837 3511 11205 N_OIV 9489 11352 17245 44516 N_IT 236.40 66.88 30.99 24.33 N_TS 31.83 37.13 42.18 45.84 N_ETS 8.38 9.13 9.75 10.16 N_EETS 5.34 6.01 6.64 6.95 N_B[s] 0.74 0.90 1.09 1.42 N_TR[s] 94.44 44.67 35.33 34.84 =============================================================================== Octree89-C ---------- We call by this name the implementation according to the article: H. Samet: {Implementing Ray Tracing with Octrees and Neighbor Finding}, C&G Vol. 13, No. 4, pp.445-460, 1989. The subdivision is in the center of the current bounding box as described above. maximum depth scene: 4 5 6 7 BALLS N_IN 57 117 304 1108 N_V 400 820 2129 7757 N_EV 300 570 1038 2905 N_OIV 9171 10946 15611 27288 N_IT 1805.00 567.80 212.50 93.67 N_TS 37.90 59.79 78.10 97.87 N_ETS 9.93 15.40 19.88 24.71 N_EETS 3.67 9.52 12.55 16.12 N_B[s] 0.12 0.16 0.19 0.27 N_TR[s] 627.00 206.30 97.29 67.47 FLUID N_IN 14 35 118 423 N_V 99 246 827 2962 N_EV 35 87 313 1164 N_OIV 2988 3731 5248 9355 N_IT 993.50 246.20 88.59 34.57 N_TS 13.08 16.90 22.12 29.55 N_ETS 3.63 4.48 5.68 7.43 N_EETS 0.78 0.96 1.37 2.44 N_B[s] 0.04 0.05 0.07 0.09 N_TR[s] 222.40 60.33 28.34 18.80 GEARS N_IN 265 1405 5837 28447 N_V 1856 9836 40860 199130 N_EV 652 4088 10334 28228 N_OIV 39440 85832 235526 879434 N_IT 153.40 72.33 43.96 39.27 N_TS 22.70 34.16 43.74 54.45 N_ETS 5.70 8.33 10.64 13.20 N_EETS 2.07 4.65 5.66 6.27 N_B[s] 0.25 0.38 0.69 1.91 N_TR[s] 302.70 229.00 236.30 303.40 LATTICE N_IN 585 4681 17993 56235 N_V 4096 32768 125952 393646 N_EV 0 7744 28732 52822 N_OIV 22112 49600 147494 502272 N_IT 28.91 13.70 11.06 10.83 N_TS 15.97 31.24 41.58 46.42 N_ETS 4.41 7.98 10.35 11.36 N_EETS 0.00 1.71 2.91 3.17 N_B[s] 0.18 0.34 0.65 1.64 N_TR[s] 60.72 45.22 47.68 50.58 MOUNT N_IN 232 1019 4716 22630 N_V 1625 7134 33013 158411 N_EV 777 3060 11720 45049 N_OIV 18107 34351 90456 324918 N_IT 43.00 23.50 18.44 18.44 N_TS 18.52 23.54 30.12 37.56 N_ETS 4.93 6.09 7.65 9.45 N_EETS 1.82 2.34 2.83 3.31 N_B[s] 0.15 0.22 0.42 1.05 N_TR[s] 35.96 28.27 28.90 32.07 RINGS N_IN 231 1216 6925 38648 N_V 1618 8513 48476 270537 N_EV 416 2127 10281 49888 N_OIV 22505 44555 133929 565631 N_IT 108.30 47.72 35.12 35.17 N_TS 25.53 38.01 52.46 70.23 N_ETS 6.94 9.92 13.38 17.65 N_EETS 2.91 4.98 6.69 8.30 N_B[s] 0.21 0.32 0.54 1.52 N_TR[s] 173.70 101.80 94.38 107.60 TEAPOT N_IN 227 1001 4100 18066 N_V 1590 7008 28701 126463 N_EV 777 3450 12327 38316 N_OIV 18845 34072 83551 295865 N_IT 184.50 78.06 45.77 39.95 N_TS 27.22 35.88 43.95 52.40 N_ETS 7.61 9.73 11.70 13.76 N_EETS 5.14 7.07 8.61 9.53 N_B[s] 0.19 0.25 0.45 0.92 N_TR[s] 46.44 27.16 22.97 23.92 TETRA N_IN 305 1369 6189 28413 N_V 2136 9584 43324 198892 N_EV 1072 4764 21100 80444 N_OIV 13312 32768 110592 512000 N_IT 120.90 63.66 47.05 47.35 N_TS 17.75 23.91 30.14 36.54 N_ETS 4.75 6.23 7.71 9.24 N_EETS 3.07 4.51 5.96 7.24 N_B[s] 0.09 0.16 0.34 1.16 N_TR[s] 6.60 5.23 5.24 5.90 TREE N_IN 53 101 186 352 N_V 372 708 1303 2465 N_EV 278 556 1054 1801 N_OIV 9029 9670 10915 13725 N_IT 8060.00 4205.00 2096.00 742.00 N_TS 51.49 80.13 107.80 130.10 N_ETS 13.10 20.24 27.16 32.74 N_EETS 3.67 9.91 17.67 23.34 N_B[s] 0.16 0.19 0.24 0.27 N_TR[s] 2887.00 1510.00 769.70 288.50 =============================================================================== Octree93-C ---------- We call by this name the implementation according to the article: I. Gargantini and H.H. Atkinson: {Ray Tracing and Octree: Numerical Evaluation of the First Intersection}, CGF, Vol. 12, No. 4, pp. 199-210, 1993 The subdivision is in the center of the current bounding box as described above. maximum depth scene: 4 5 6 7 BALLS N_IN 57 117 304 1108 N_V 400 820 2129 7757 N_EV 300 570 1038 2905 N_OIV 9171 10946 15611 27288 N_IT 1794.00 558.80 207.30 89.93 N_TS 20.58 31.68 40.86 50.67 N_ETS 15.65 20.68 26.45 32.34 N_EETS 9.42 14.86 19.25 23.99 N_B[s] 0.13 0.15 0.20 0.25 N_TR[s] 624.90 218.60 116.20 91.43 FLUID N_IN 14 35 118 423 N_V 99 246 827 2962 N_EV 35 87 313 1164 N_OIV 2988 3730 5247 9353 N_IT 978.80 238.80 82.28 31.21 N_TS 8.21 10.25 12.94 16.65 N_ETS 5.90 7.37 9.26 11.50 N_EETS 3.06 3.89 5.04 6.70 N_B[s] 0.04 0.05 0.07 0.10 N_TR[s] 223.50 61.33 29.87 22.00 GEARS N_IN 265 1405 5837 28447 N_V 1856 9836 40860 199130 N_EV 652 4088 10334 28228 N_OIV 39440 85832 235526 879434 N_IT 150.10 69.62 39.72 34.50 N_TS 12.86 18.71 23.42 28.49 N_ETS 8.82 11.40 14.68 18.78 N_EETS 5.23 7.80 9.95 12.30 N_B[s] 0.25 0.40 0.73 2.08 N_TR[s] 314.10 246.10 256.60 327.90 LATTICE N_IN 585 4681 17993 56235 N_V 4096 32768 125952 393646 N_EV 0 7744 28732 52822 N_OIV 22112 49600 147494 502272 N_IT 26.94 12.32 9.52 9.15 N_TS 10.13 17.68 22.60 24.52 N_ETS 7.40 12.46 15.41 16.58 N_EETS 3.29 6.67 8.75 9.46 N_B[s] 0.20 0.38 0.80 1.85 N_TR[s] 65.89 55.45 59.00 62.19 MOUNT N_IN 232 1019 4716 22630 N_V 1625 7134 33013 158411 N_EV 777 3060 11720 45049 N_OIV 18107 34351 90456 324918 N_IT 41.97 22.61 17.47 17.18 N_TS 10.80 13.37 16.64 20.23 N_ETS 7.35 9.09 11.58 14.44 N_EETS 4.34 5.46 6.95 8.62 N_B[s] 0.15 0.24 0.43 1.07 N_TR[s] 39.72 32.71 34.42 39.12 RINGS N_IN 231 1216 6925 38648 N_V 1618 8513 48476 270537 N_EV 416 2127 10281 49888 N_OIV 22505 44555 133929 565631 N_IT 108.00 47.48 34.87 34.80 N_TS 14.66 21.14 28.59 37.65 N_ETS 10.37 14.26 19.43 26.30 N_EETS 6.35 9.33 12.78 17.01 N_B[s] 0.20 0.31 0.57 1.66 N_TR[s] 181.10 112.10 108.80 126.30 TEAPOT N_IN 227 1001 4100 18066 N_V 1590 7008 28701 126463 N_EV 777 3450 12327 38316 N_OIV 18845 34072 83551 295865 N_IT 182.70 76.40 44.21 37.16 N_TS 14.79 19.23 23.31 27.36 N_ETS 9.75 12.02 14.34 17.11 N_EETS 7.30 9.40 11.33 13.17 N_B[s] 0.19 0.25 0.43 1.03 N_TR[s] 48.92 30.82 27.78 29.89 TETRA N_IN 305 1369 6189 28413 N_V 2136 9584 43324 198892 N_EV 1072 4764 21100 80444 N_OIV 13312 32768 110592 512000 N_IT 117.20 61.11 44.76 44.20 N_TS 9.59 12.70 15.82 18.98 N_ETS 6.18 7.66 9.11 10.80 N_EETS 4.53 5.99 7.45 8.93 N_B[s] 0.09 0.16 0.34 1.24 N_TR[s] 6.93 5.83 6.10 6.96 TREE N_IN 53 101 186 352 N_V 372 708 1303 2465 N_EV 278 556 1054 1801 N_OIV 9029 9670 10915 13725 N_IT 8057.00 4201.00 2092.00 738.00 N_TS 26.62 41.00 54.87 65.90 N_ETS 22.36 30.41 36.46 41.63 N_EETS 12.93 20.08 26.99 32.40 N_B[s] 0.16 0.20 0.24 0.28 N_TR[s] 2893.00 1501.00 785.80 317.60 =============================================================================== Octree93-A ---------- We call by this name the implementation according to the article: I. Gargantini and H.H. Atkinson: {Ray Tracing and Octree: Numerical Evaluation of the First Intersection}, CGF, Vol. 12, No. 4, pp. 199-210, 1993. The subdivision uses cost function estimate as described above. maximum depth scene: 4 5 6 7 BALLS N_IN 131 661 3077 15291 N_V 918 4628 21540 107038 N_EV 214 1202 4233 14103 N_OIV 10160 16289 42109 172555 N_IT 84.31 26.38 15.25 13.58 N_TS 12.95 16.64 19.75 22.53 N_ETS 9.45 11.41 13.33 15.27 N_EETS 6.10 7.77 9.16 10.39 N_B[s] 0.65 0.83 1.23 2.35 N_TR[s] 47.05 33.80 34.99 38.86 FLUID N_IN 96 414 1675 6706 N_V 673 2899 11726 46943 N_EV 176 844 2933 6834 N_OIV 5059 9850 28280 111558 N_IT 62.24 24.61 14.06 11.90 N_TS 11.81 15.36 18.72 20.85 N_ETS 9.31 11.42 13.25 14.57 N_EETS 5.30 6.87 8.33 9.24 N_B[s] 0.24 0.34 0.58 1.25 N_TR[s] 24.51 19.57 20.16 21.74 GEARS N_IN 349 1709 10301 59649 N_V 2444 11964 72108 417544 N_EV 580 1120 5300 20092 N_OIV 31144 95016 344580 1737490 N_IT 65.44 39.09 24.59 26.25 N_TS 11.70 14.29 17.89 22.09 N_ETS 7.11 8.96 11.85 15.51 N_EETS 4.63 5.60 7.17 9.16 N_B[s] 0.92 1.46 3.30 10.51 N_TR[s] 210.90 212.00 245.50 323.60 LATTICE N_IN 585 4681 18218 45496 N_V 4096 32768 127527 318473 N_EV 0 7133 33332 34508 N_OIV 18768 42789 121693 467745 N_IT 23.05 8.99 5.67 5.66 N_TS 10.27 17.62 21.50 21.80 N_ETS 7.71 11.25 12.55 12.67 N_EETS 3.44 6.48 8.06 8.14 N_B[s] 0.97 1.45 2.53 4.57 N_TR[s] 62.33 50.15 51.39 52.36 MOUNT N_IN 311 1531 7889 42809 N_V 2178 10718 55224 299664 N_EV 861 3605 14020 41864 N_OIV 21484 47338 150888 692494 N_IT 30.89 16.56 13.14 14.47 N_TS 10.71 12.72 15.07 17.89 N_ETS 7.07 8.30 10.01 12.40 N_EETS 4.28 5.15 6.21 7.52 N_B[s] 0.82 1.18 2.17 5.77 N_TR[s] 33.76 29.24 30.51 35.16 RINGS N_IN 347 2055 12900 73091 N_V 2430 14386 90301 511638 N_EV 406 1718 10700 41425 N_OIV 20867 54320 210963 1175103 N_IT 57.85 31.81 25.99 30.83 N_TS 13.98 18.65 25.54 33.30 N_ETS 9.17 12.56 17.68 24.00 N_EETS 6.00 7.96 11.06 14.64 N_B[s] 0.94 1.38 2.65 8.03 N_TR[s] 111.30 87.69 92.60 115.90 TEAPOT N_IN 330 1703 9053 49684 N_V 2311 11922 63372 347789 N_EV 853 3460 13985 49191 N_OIV 25332 59055 199518 922872 N_IT 103.20 47.91 33.59 33.90 N_TS 15.42 19.16 22.89 26.82 N_ETS 9.76 11.91 14.41 17.45 N_EETS 7.56 9.19 10.90 12.74 N_B[s] 1.02 1.46 2.68 7.25 N_TR[s] 33.05 25.33 25.67 29.27 TETRA N_IN 325 1485 6413 30521 N_V 2276 10396 44892 213648 N_EV 1116 5468 20784 77404 N_OIV 13792 34112 120048 587504 N_IT 97.06 44.97 24.08 28.24 N_TS 9.59 11.89 13.85 15.60 N_ETS 5.76 6.63 7.36 8.40 N_EETS 4.49 5.53 6.38 7.14 N_B[s] 0.45 0.70 1.42 4.17 N_TR[s] 6.21 5.09 4.94 5.60 TREE N_IN 71 278 1130 4301 N_V 498 1947 7911 30108 N_EV 231 837 3509 11205 N_OIV 9489 11352 17247 44514 N_IT 235.20 66.38 30.38 23.79 N_TS 14.83 16.37 17.64 18.46 N_ETS 11.23 12.05 12.67 13.12 N_EETS 8.21 8.95 9.57 9.96 N_B[s] 0.84 1.02 1.26 1.65 N_TR[s] 91.05 40.57 30.88 29.90 ============================================================================== Octree comparison ----------------- In the following table we report the best results for all the octrees above, so these can be compared for one scene at the same line. As in the previous article, we let the reader to make conclusion himself, we presented our opinion in our RTNews article. md .. the maximum depth setting for the best performance and octree algorithm. Octree method ----------------------------------------------------------------------- ------ Octree84-C Octree84-A Octree89-C Octree93-C Octree93-A scene: BALLS md = 7 md = 5 md = 7 md = 7 md = 5 N_IN 1108 661 1108 1108 661 N_V 7757 4628 7757 7757 4628 N_EV 2905 1202 2905 2905 1202 N_OIV 27288 16289 27288 27288 16289 N_IT 94.75 28.62 93.67 89.93 26.38 N_TS 167.00 40.09 97.87 50.67 16.64 N_ETS 24.71 8.35 24.71 32.34 11.41 N_EETS 16.12 4.62 16.12 23.99 7.77 N_B[s] 0.29 6.17 0.27 0.25 0.83 N_TR[s] 102.30 35.40 67.47 91.43 33.80 FLUID md = 7 md = 5 md = 7 md = 7 md = 5 N_IN 423 414 423 423 414 N_V 2962 2899 2962 2962 2899 N_EV 1164 844 1164 1164 844 N_OIV 9355 9850 9355 9353 9850 N_IT 34.73 27.99 34.57 31.21 24.61 N_TS 48.18 37.40 29.55 16.65 15.36 N_ETS 7.42 7.64 7.43 11.50 11.42 N_EETS 2.44 2.87 2.44 6.70 6.87 N_B[s] 0.11 2.54 0.09 0.10 0.34 N_TR[s] 22.85 20.74 18.80 22.00 19.57 GEARS md = 5 md = 5 md = 5 md = 5 md = 4 N_IN 1405 349 1405 1405 349 N_V 9836 2444 9836 9836 2444 N_EV 4088 580 4088 4088 580 N_OIV 85832 31144 85832 85832 31144 N_IT 71.38 68.78 72.33 69.62 65.44 N_TS 46.49 23.50 34.16 18.71 11.70 N_ETS 8.33 5.15 8.33 11.40 7.11 N_EETS 4.64 2.60 4.65 7.80 4.63 N_B[s] 0.46 0.79 0.38 0.40 0.92 N_TR[s] 247.00 206.60 229.00 246.10 210.90 LATTICE md = 5 md = 5 md = 7 md = 5 md = 4 N_IN 4681 4681 4681 4681 4681 N_V 32768 32768 32768 32768 32768 N_EV 7744 7133 7744 7744 7133 N_OIV 49600 42789 49600 49600 42789 N_IT 13.80 9.97 13.70 12.32 8.99 N_TS 47.88 46.89 31.24 17.68 17.62 N_ETS 7.98 7.82 7.98 12.46 11.25 N_EETS 1.71 2.65 1.71 6.67 6.48 N_B[s] 0.39 1.23 0.34 0.38 1.45 N_TR[s] 56.37 49.32 45.22 55.45 50.15 MOUNT md = 6 md = 5 md = 6 md = 5 md = 4 N_IN 1019 1534 1019 1019 1531 N_V 7134 10739 7134 7134 10718 N_EV 3060 3615 3060 3060 3605 N_OIV 34351 47351 34351 34351 47338 N_IT 23.72 17.58 23.50 22.61 16.56 N_TS 30.89 29.26 23.54 13.37 12.72 N_ETS 6.08 5.77 6.09 9.09 8.30 N_EETS 2.33 2.51 2.34 5.46 5.15 N_B[s] 0.25 1.01 0.22 0.24 1.18 N_TR[s] 32.40 28.34 28.27 32.71 29.24 RINGS md = 6 md = 5 md = 6 md = 4 md = 5 N_IN 6925 2055 6925 6925 2055 N_V 48476 14386 48476 48476 14386 N_EV 10281 1718 10281 10281 1718 N_OIV 133929 54320 133929 133929 54320 N_IT 35.12 32.11 35.12 34.87 31.81 N_TS 81.90 44.74 52.46 28.59 18.65 N_ETS 13.38 8.55 13.38 19.43 12.56 N_EETS 6.69 3.92 6.69 12.78 7.96 N_B[s] 0.64 1.21 0.54 0.57 1.38 N_TR[s] 111.80 86.47 94.38 108.80 87.69 TEAPOT md = 6 md = 6 md = 6 md = 6 md = 5 N_IN 4100 4100 4100 4100 1703 N_V 28701 28701 28701 28701 11922 N_EV 12327 12327 12327 12327 3460 N_OIV 83551 83551 83551 83551 59055 N_IT 45.63 45.63 45.77 44.21 47.91 N_TS 64.67 64.67 43.95 23.31 19.16 N_ETS 11.69 11.69 11.70 14.34 11.91 N_EETS 8.61 8.61 8.61 11.33 9.19 N_B[s] 0.47 0.47 0.45 0.43 1.46 N_TR[s] 30.72 30.72 22.97 27.78 25.33 TETRA md = 5 md = 6 md = 5(6) md = 5 md = 5 N_IN 1369 6449 1369 1369 6413 N_V 9584 45144 9584 9584 44892 N_EV 4764 20976 4764 4764 20784 N_OIV 32768 120336 32768 32768 120048 N_IT 63.58 23.03 63.66 61.11 24.08 N_TS 32.08 33.72 23.91 12.70 13.85 N_ETS 6.20 6.26 6.23 7.66 7.36 N_EETS 4.48 5.33 4.51 5.99 6.38 N_B[s] 0.17 1.25 0.16 0.16 1.42 N_TR[s] 6.34 5.05 5.23 5.83 4.94 TREE md = 7 md = 7 md = 7 md = 7 md = 7 N_IN 352 4300 352 352 4301 N_V 2465 30101 2465 2465 30108 N_EV 1801 11205 1801 1801 11205 N_OIV 13725 44516 13725 13725 44514 N_IT 741.30 24.33 742.00 738.00 23.79 N_TS 219.30 45.84 130.10 65.90 18.46 N_ETS 32.74 10.16 32.74 41.63 13.12 N_EETS 23.33 6.95 23.34 32.40 9.96 N_B[s] 0.29 1.42 0.27 0.28 1.65 N_TR[s] 338.20 34.84 288.50 317.60 29.90 ------------------ END