Comparison of hierarchical grids ================================ Authors: Vlastimil Havran and Filip Sixta Department of Computer Science and Engineering Faculty of Electrical Engineering Czech Technical University in Prague e-mail: havran@fel.cvut.cz Date: 06/20/1999 This text is additional material to the Ray Tracing News article on hierarchical (nested) grids in RTNv12v1 (http://www.acm.org/tog/resources/RTNews/html/rtnv12n1.html#art3). We present here some statistics based on measurements 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. The scenes are generated by using the default size settings 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 increased the set of invariants for SPD scenes and ray tracing algorithms that should be set the same if the ray tracing algorithm is implemented without bugs. A subset of these invariants is presented in the SPD documentation. These invariant parameters have to be the same regardless the acceleration technique used: PrimaryRay[-] .. the number of primary rays cast from the eye, for resolution 513x513 it is 2639169 UsedIntPrimRay[s] .. the number of primary rays hitting objects ScnCoverage[%] .. the portion of the screen which is covered by the rays hitting objects, that is: screen coverage = UsedIntPrimRay / PrimaryRays ShadowRay[-] .. the number of shadow rays cast UsedIntShadRay[-] .. the number of shadow rays hitting an object (not reaching a point light) SecondaryRay[-] .. the number of secondary rays cast (reflected+refracted) UsedIntSecRay[-] .. the number of secondary rays hitting an object Summary information: AllRays .. the number of all rays cast IntersRequired[-] .. the total number of intersection that have to be computed AllRays = PrimaryRay + ShadowRay + SecondaryRay IntersRequired = UsedIntPrimRay + UsedIntShadRay + UsedIntSecRay Scenes ------------------------------------------------------------ balls gears lattice mount rings teapot tetra tree scene box size 24.0 4.0 1.044 2.16 19.68 8.00 2.0 100 24.0 4.0 1.044 2.16 19.27 8.00 2.0 100 1.36 4.0 1.044 2.16 19.68 3.19 2.0 3.16 Invariants ------------------ PrimaryRay[-] 263169 263169 263169 263169 263169 263169 263169 263169 UsedIntPrimRay[-] 263169 245332 261170 173685 263169 161546 49950 169907 ScnCoverage [%] 100 93.22 99.24 66 100 61.38 18.98 64.56 ShadowRay[-] 959244 2088012 1180774 361037 1077336 406340 46262 1110323 UsedIntShadRay[-] 285178 1057557 943159 74555 510719 34757 5538 47506 SecondaryRay[-] 179884 494338 243210 710436 312879 226235 0 0 UsedIntSecRay[-] 134368 365338 178786 472351 175688 67688 0 0 Summary: AllRays[-] 1402297 2845519 1687153 1334642 1653384 895744 309431 1373492 IntersRequired[-] 682715 1668227 1383115 720591 949576 263991 55488 217413 It is important to verify these invariants when implementing an acceleration technique, we devoted it much time when debugging. When checking the implementation we recommend to start with the summary information first presented. We established set of parameters that can be expressed 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 N_V[-] .. the number of elementary cells 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 auxiliary data structures 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 the spatial data structures well. ============================================================================= Uniform Grid ------------- In this comparison we also present the results for non-hierarchical grids, since it is interesting to compare them with hierarchical ones. Grid resolution setting is important and should be done with care. Let xsize, ysize, and zsize be the size of the scene box for all three axes. There are several methods to set the resolution and thus the number of voxels. a) regular - all three sides of the scene box are subdivided to the same number of voxels. When the number of objects is N, then the resolution at all three sides is xres = yres = zres = D . (N^(1/3)) , where D is voxel density. Usually, D = 1.0 . b) Woo's method - we call this method according to the author of article, where it was described: A.Woo: "Ray tracing Polygons Using Spatial Subdivision", in proceedings of Graphics Interface proceedings, pp. 184--191, 1992. // the maximum size of the bounding box float maxsize = MAX(xsize, ysize, zsize); float V = D * N; float L = pow(V, 1/3); // the resolution in three axes xres = (int) ( xsize/maxsize * L ); if (xres < 1) xres = 1; yres = (int) ( ysize/maxsize * L ); if (yres < 1) yres = 1; zres = (int) ( zsize/maxsize * L ); if (zres < 1) zres = 1; c) Heterogeneous grids - very similar to b), but different formulas are applied. The method was described by Klimaszewski, article is cited below. float V = D * N; xres = (int) (pow(V * xsize * xsize/(ysize * zsize), 1/3 ) + 0.5); if (xres < 1) xres = 1; yres = (int) (pow(V * ysize/((float)xres * zsize), 0.5 ) + 0.5); if (yres < 1) yres = 1; zres = (int) (V / ((float)xres * yres) + 0.5); if (zres < 1) zres = 1; The articles usually suppose voxel density D = 1.0 . The regular resolution setting is typically worse than the other resolution setting methods when the scene box is not of cubic shape. Woo's and heterogeneous have similar behavior. We therefore report resolution for two densities and customary resolution setting, which results in high number of voxels and according to our experiments is suboptimal (we have been experimenting with the resolution to find out the best one at several iterations). The traversal algorithm uses 3DDDA and needs four comparison per one traversal step. Woo's D = 1.0 Woo's D = 10.0 Customary setting (xres,yres,zres) (xres,yres,zres) (xres,yres,zres) --------------------------------------------------- scene BALLS Resolution (46,46,3) (103,103,7) (152,152,9) N_IN 0 0 0 N_V 6348 74263 207936 N_EV 4208 63393 184204 N_OIV 10240 19966 33909 N_IT 358.66 72.54 41.48 N_TS 5.69 12.40 17.32 N_ETS 5.69 12.40 17.32 N_EETS 3.00 9.27 13.93 T_B[s] 0.19 0.3 0.39 T_TR[s] 244.7 56.54 38.52 FLUID Resolution (27,6,15) (57,14,32) (114,28,64) N_IN 0 0 0 N_V 2430 25536 204288 N_EV 389 3588 36166 N_OIV 4736 25223 172914 N_IT 580.71 143.70 56.33 N_TS 4.66 9.57 18.55 N_ETS 4.66 9.57 18.55 N_EETS 1.13 2.55 7.14 T_B[s] 0.07 0.2 0.96 T_TR[s] 234.2 64.53 32.13 GEARS Resolution (32,33,9) (71,71,18) (98,98,25) N_IN 0 0 0 N_V 9504 90738 240100 N_EV 6080 66531 194920 N_OIV 39344 110029 171316 N_IT 39.76 22.82 17.52 N_TS 6.84 13.83 18.95 N_ETS 6.84 13.83 18.95 N_EETS 3.62 9.19 14.62 T_B[s] 0.38 0.83 1.13 T_TR[s] 201 198.2 192.3 LATTICE Resolution (20,20,20) (44,44,44) (59,59,59) N_IN 0 0 0 N_V 8000 85184 205379 N_EV 0 38016 102640 N_OIV 32152 90368 160819 N_IT 20.67 9.26 8.81 N_TS 5.09 10.56 13.70 N_ETS 5.09 10.56 13.70 N_EETS 0.00 5.09 7.51 T_B[s] 0.38 0.85 1.27 T_TR[s] 54.68 34.92 34.21 MOUNT Resolution (20,20,20) (44,44,42) (35,35,35) N_IN 0 0 0 N_V 8000 81312 42875 N_EV 6502 71924 37246 N_OIV 21746 51144 38922 N_IT 19.01 13.17 13.32 N_TS 8.85 18.43 15.01 N_ETS 8.85 18.43 15.01 N_EETS 4.97 11.93 9.60 T_B[s] 0.26 0.48 0.4 T_TR[s] 28.99 25.96 25.15 RINGS Resolution (21,20,21) (44,43,44) (60,60,60) N_IN 0 0 0 N_V 8820 83248 216000 N_EV 6264 66753 178930 N_OIV 27666 71303 127217 N_IT 45.29 23.36 21.48 N_TS 11.78 24.51 33.71 N_ETS 11.78 24.51 33.71 N_EETS 7.33 18.84 27.22 T_B[s] 0.35 0.61 0.98 T_TR[s] 129.8 84 83.7 TEAPOT Resolution (28,29,11) (61,61,25) (80,80,30) N_IN 0 0 0 N_V 8932 93025 192000 N_EV 7226 83721 175514 N_OIV 22982 52781 75105 N_IT 33.65 15.13 13.30 N_TS 14.98 32.50 41.24 N_ETS 14.98 32.50 41.24 N_EETS 12.25 29.60 38.08 T_B[s] 0.3 0.51 0.65 T_TR[s] 28.68 18.86 18.76 TETRA Resolution (16,16,16) (35,35,35) (40,40,40) N_IN 0 0 0 N_V 4096 42875 64000 N_EV 3104 37311 56696 N_OIV 12556 35936 44696 N_IT 20.64 10.01 9.17 N_TS 7.43 15.97 18.24 N_ETS 7.43 15.97 18.24 N_EETS 5.83 14.36 16.63 T_B[s] 0.13 0.27 0.34 T_TR[s] 5.54 3.89 3.86 TREE Resolution (52,52,3) (117,118,5) (60,60,60) N_IN 0 0 0 N_V 8112 69030 216000 N_EV 5400 55191 212179 N_OIV 11102 22407 14322 N_IT 727.62 246.08 355.45 N_TS 7.60 15.45 56.36 N_ETS 7.60 15.45 56.36 N_EETS 4.50 11.67 45.36 T_B[s] 0.22 0.33 0.33 T_TR[s] 1517 483 781.3 =========================================================================== Recursive Grid --------------- Recursive grid is the implementation according to the article: David Jevans and Brian Wyvill: "Adaptive voxel subdivision for ray tracing", in Proceedings of Graphics Interface '89, pp.164-172, June 1989. The resolution at each level was set using Woo's method. Parameters: RMD = maximum depth of recursive grids - how many grids can be nested. RHT = heterogeneous grids are used (ON/OFF) (RMD/RHT) (RMD/RHT) (RMD/RHT) (RMD/RHT) ------------------------------------------------------------ 2/+ 3/+ 2/- 3/- scene BALLS N_IN 49 1531 69 2636 N_V 16821 38877 22955 98022 N_EV 8867 11519 16788 38752 N_OIV 34255 117525 53604 281347 N_IT 25.67 16.94 101.46 43.32 N_TS 14.29 16.87 42.79 51.16 N_ETS 11.66 13.02 36.78 40.33 N_EETS 7.04 7.49 26.67 29.36 T_B[s] 0.13 0.39 0.2 0.78 T_TR[s] 35.76 36.73 103.4 93.45 FLUID N_IN 14 590 20 669 N_V 5460 23787 6873 41718 N_EV 1670 2043 2406 4279 N_OIV 24134 562303 29856 783101 N_IT 37.37 26.73 46.07 30.58 N_TS 10.69 13.32 14.75 18.34 N_ETS 8.57 9.93 12.21 14.25 N_EETS 2.58 2.72 5.07 5.59 T_B[s] 0.08 1 0.08 1.38 T_TR[s] 24.26 23.79 26.96 26.77 GEARS N_IN 1673 19645 1797 34239 N_V 48443 298119 93160 936652 N_EV 13694 17422 21370 29194 N_OIV 313791 2527805 637988 7482646 N_IT 27.18 27.72 39.85 35.97 N_TS 11.42 14.27 16.01 19.89 N_ETS 8.66 10.03 12.77 14.65 N_EETS 4.36 4.47 6.77 6.81 T_B[s] 0.73 5.06 1.32 13.97 T_TR[s] 182.6 214.9 226.9 267.8 LATTICE N_IN 289 289 513 513 N_V 11568 11568 22573 22573 N_EV 0 0 0 0 N_OIV 62836 62836 79525 79525 N_IT 34.87 34.87 35.78 35.78 N_TS 6.40 6.40 7.29 7.29 N_ETS 5.30 5.30 5.93 5.93 N_EETS 0.00 0.00 0.00 0.00 T_B[s] 0.17 0.16 0.25 0.25 T_TR[s] 81.86 82.05 82.58 82.62 MOUNT N_IN 1163 10573 1243 11483 N_V 37987 143477 59239 325479 N_EV 13215 16203 20507 29192 N_OIV 185273 769408 254246 1580681 N_IT 15.97 15.51 14.94 15.01 N_TS 11.45 12.42 11.94 12.79 N_ETS 9.74 10.19 10.22 10.69 N_EETS 5.08 5.11 5.49 5.51 T_B[s] 0.5 1.98 0.58 3.31 T_TR[s] 28.34 30.28 27.71 29.82 RINGS N_IN 1369 2094 1472 1778 N_V 28536 35503 48210 56166 N_EV 8373 8895 13786 15992 N_OIV 94511 113662 134511 151105 N_IT 30.88 30.46 27.75 27.67 N_TS 18.25 18.51 20.65 20.71 N_ETS 14.72 14.84 16.82 16.86 N_EETS 7.77 7.80 9.66 9.67 T_B[s] 0.3 0.39 0.39 0.41 T_TR[s] 114 113.9 110.2 110.3 TEAPOT N_IN 784 6334 874 8285 N_V 32372 110582 51585 256923 N_EV 15180 22961 25726 45287 N_OIV 135576 691621 185307 1469609 N_IT 18.16 17.53 18.78 18.83 N_TS 18.75 19.67 22.91 24.03 N_ETS 16.66 17.13 20.63 21.31 N_EETS 12.99 13.09 16.95 17.09 T_B[s] 0.36 1.55 0.46 2.93 T_TR[s] 21.69 22.67 23.59 25.09 TETRA N_IN 1057 1565 1057 3105 N_V 31768 40404 41024 94272 N_EV 14220 14220 16160 21036 N_OIV 117056 218944 181488 477408 N_IT 21.32 21.49 23.00 22.69 N_TS 12.29 12.34 12.63 12.83 N_ETS 9.97 10.00 10.32 10.43 N_EETS 6.83 6.83 7.01 7.04 T_B[s] 0.32 0.47 0.42 1.04 T_TR[s] 7.18 7.23 7.37 7.52 TREE N_IN 5 501 11 882 N_V 16818 32376 20725 69226 N_EV 11586 19476 18741 48059 N_OIV 21978 63640 34881 169916 N_IT 19.86 12.03 95.20 31.60 N_TS 13.65 14.62 39.40 44.32 N_ETS 12.25 12.88 36.50 39.41 N_EETS 7.76 8.26 28.18 31.17 T_B[s] 0.13 0.28 0.13 0.54 T_TR[s] 46.13 33.91 207.4 98.55 =============================================================================== HUG (Hierarchy of uniform grids) -------------------------------- HUG is the implementation of the methods presented in the papers: F. Cazals, G. Drettakis, and C. Puech: "Filtering, Clustering and Hierarchy Construction: A New Solution for Ray-Tracing Complex Scenes", Computer Graphics Forum (Eurographics 95), Vol. 14, No. 3, pp. 371--382, 1995. F. Cazals and C. Puech: "Bucket-like space partitioning data-structures with applications to ray-tracing", in proceedings of 13th ACM Symposium on Computational Geometry", pp. 11-20, 1997. The resolution at each level was set using Woo's method. Parameters: HNG[-] .. number of groups in HUG (called filter-level in the original paper) HCN[s] .. connectivity parameter, when connectivity is larger, more distant objects can be in a common cluster. (HNG/HCN) (HNG/HCN) (HNG/HCN) (HNG/HCN) (HNG/HCN) ---------------------------------------------------------------------------- 2/0 3/0 4/0 3/0.05 3/-0.05 scene BALLS N_IN 7 9185 8730 9363 7846 N_V 7754 92 792 92 1019 N_EV 5734 10 307 10 477 N_OIV 14606 13804 14161 13894 14255 N_IT 18.80 29.10 135.62 16.13 32.93 N_TS 8.63 9.56 10.12 9.68 9.23 N_ETS 5.84 1.39 2.65 1.39 1.38 N_EETS 4.11 0.10 0.91 0.10 0.33 T_B[s] 0.4 0.43 0.4 0.42 0.4 T_TR 34.01 60.58 147.8 50.98 62.21 FLUID N_IN 6 6 6 6 6 N_V 2522 2520 2520 2520 2448 N_EV 1748 1739 1739 1739 1674 N_OIV 6294 6392 6392 6392 6384 N_IT 43.39 43.09 43.09 43.09 43.98 N_TS 7.54 7.38 7.38 7.38 7.36 N_ETS 4.59 4.43 4.43 4.43 4.41 N_EETS 2.39 2.33 2.33 2.33 2.30 T_B[s] 0.18 0.17 0.17 0.18 0.18 T_TR[s] 28.82 28.62 28.76 28.59 28.8 GEARS N_IN 125 125 13073 125 125 N_V 12024 12024 4096 12024 12024 N_EV 4284 4284 1408 4284 4284 N_OIV 80094 80094 80086 80094 80094 N_IT 32.89 32.89 26.49 32.89 32.89 N_TS 7.06 7.06 9.04 7.06 7.06 N_ETS 3.72 3.72 2.50 3.72 3.72 N_EETS 1.50 1.50 0.08 1.50 1.50 T_B[s] 1.04 1.02 1.07 1 1.02 T_TR[s] 242.1 242.1 325.1 242.1 242.1 LATTICE N_IN 1 1 1 130 1 N_V 6859 4913 6859 4876 4913 N_EV 0 0 0 7 0 N_OIV 38620 39585 38620 39573 39585 N_IT 25.07 32.39 25.07 32.41 32.39 N_TS 5.87 5.39 5.87 5.40 5.39 N_ETS 4.87 4.39 4.87 4.35 4.39 N_EETS 0.0 0.0 0.0 0.0 0.0 T_B[s] 0.3 0.27 0.27 0.28 0.29 T_TR[s] 71.62 84.9 71.31 84.48 84.02 MOUNT N_IN 1 1 1 8444 1 N_V 900 216 64 1726 216 N_EV 573 110 22 1279 110 N_OIV 16452 12629 10931 20857 12629 N_IT 51.78 106.90 219.03 28.60 106.90 N_TS 5.62 4.05 3.20 14.89 4.05 N_ETS 4.63 3.06 2.20 5.93 3.06 N_EETS 1.66 0.83 0.26 3.85 0.83 T_B[s] 0.16 0.16 0.16 0.44 0.16 T_TR[s] 62.31 117 223.7 54.5 116.7 RINGS N_IN 1730 149 1815 37 149 N_V 9546 5031 2632 2212 5031 N_EV 2283 0 0 0 0 N_OIV 32197 33195 27870 23698 33195 N_IT 25.71 650.19 1515.63 654.03 650.19 N_TS 12.91 5.11 7.14 4.76 5.11 N_ETS 8.01 2.36 2.85 2.08 2.36 N_EETS 4.24 0.00 0.00 0.00 0.00 T_B[s] 0.45 0.36 0.38 0.32 0.37 T_TR[s] 116.3 549.2 2355 509.4 551.5 TEAPOT N_IN 931 3030 5564 3028 2494 N_V 12946 9503 7021 9379 8567 N_EV 8463 5479 3671 6840 5082 N_OIV 39007 39265 38962 33428 36262 N_IT 22.60 23.69 27.02 24.85 26.54 N_TS 16.40 14.90 14.87 15.34 14.43 N_ETS 14.28 11.59 9.97 11.79 11.48 N_EETS 11.63 9.11 7.42 9.54 9.16 T_B[s] 0.53 0.53 0.56 0.56 0.5 T_TR[s] 25.61 30.13 37.83 28.99 31.9 TETRA N_IN 1 1 1 10 1 N_V 4096 4096 4096 4096 4096 N_EV 3017 3017 3017 3017 3017 N_OIV 16396 16396 16396 16396 16396 N_IT 28.89 28.89 28.89 28.78 28.89 N_TS 8.09 8.09 8.09 9.84 8.09 N_EETS 5.64 5.64 5.64 5.64 5.64 T_B[s] 0.24 0.23 0.22 0.25 0.23 T_TR[s] 7.22 7.19 7.31 8.14 7.24 TREE N_IN 7 3430 825 3430 9 N_V 8116 5247 7389 5247 7872 N_EV 6619 4339 5839 4339 6034 N_OIV 12585 12824 13181 12824 13260 N_IT 12.03 10.88 17.64 10.88 290.55 N_TS 5.78 5.33 5.38 5.33 4.58 N_ETS 3.19 1.83 2.21 1.83 2.06 N_EETS 2.52 1.27 1.68 1.27 1.54 T_B[s] 0.48 0.52 0.53 0.52 0.52 T_TR[s] 38.48 39.01 53.34 38.81 557.2 =============================================================================== Adaptive grids --------------- This is the implementation of hierarchical grids according to the article: Kryzsztof S. Klimaszewski and Thomas W. Sederberg: "Faster Ray Tracing Using Adaptive Grids", IEEE CG&A, Vol. 17, No. 1, pp.42--51, Jan-Feb 1997. The resolution at each level was set using Woo's method. Parameters: f[-] .. threshold to merge two candidates, if A/(A_1+A_2) < f, then merge the candidates, where A_1 and A_2 are the surface areas of the candidates, A is the surface area of potential resulting cluster. m[-] .. the maximum ratio of the surface area of the cluster box and the box of the whole scene o[bool] .. if to construct orphan grid for objects from underpopulated clusters (ON/OFF) We also report other parameters that are specific for adaptive grids: N_ORP[-] .. the number of orphans N_BB[-] .. the number of interior nodes of the hierarchy N_BIT[-] .. the number of intersection tests with the interior nodes of BVH Note that the setting for the first column degrades the adaptive grid approach to BVH. (f, m, o) (f, m, o) (f, m, o) (f, m, o) ------------------------------------------------------------------ ----------- 1,0/0,1/- 1,5/0,1/- 1,5/0,5/- 2,0/0,1/- scene BALLS N_IN 5568 1492 1492 1492 N_ORP 5448 1 1 1 N_BB 4495 1 1 1 N_V 7143 18080 18080 18080 N_EV 24 4634 4634 4634 N_OIV 17597 29994 29994 29994 N_IT 43.98 14.90 14.90 14.90 N_BIT 91.27 1.00 1.00 1.00 N_TS 93.90 11.29 11.29 11.29 N_ETS 67.74 8.80 8.80 8.80 N_EETS 0.01 4.98 4.98 4.98 T_B[s] 1.32 2.78 2.89 2.79 T_TR[s] 824.8 29.99 30.59 30.51 GEARS N_IN 5458 6866 9078 6866 N_ORP 65 1 1 1 N_BB 48 6 2 6 N_V 47638 63318 77924 63318 N_EV 1267 1744 1382 1744 N_OIV 209537 261772 303850 261772 N_IT 32.46 32.29 30.30 32.30 N_BIT 6.01 2.81 1.37 2.81 N_TS 14.72 13.28 9.77 13.28 N_ETS 10.01 8.25 5.45 8.25 N_EETS 0.30 0.65 0.10 0.65 T_B[s] 7.39 6.11 8.83 5.88 T_TR[s] 390 330.5 302.2 330 MOUNT N_IN 5737 2936 2021 2867 N_ORP 5691 7 2 5 N_BB 4632 13 2 11 N_V 6912 29064 27545 28869 N_EV 110 8030 9716 8001 N_OIV 24240 99323 87508 99053 N_IT 75.08 18.81 16.10 19.11 N_BIT 146.37 4.79 1.76 4.30 N_TS 147.32 15.82 17.44 15.11 N_ETS 105.85 10.77 14.57 11.85 N_EETS 0.02 4.69 8.39 4.45 T_B[s] 2.17 2.52 2.72 2.54 T_TR[s] 1432 59.97 42.88 59.05 RINGS N_IN 1079 2800 2800 2800 N_ORP 15 1 1 1 N_BB 191 16 16 16 N_V 10830 19015 19015 19015 N_EV 266 748 748 748 N_OIV 46443 79419 79419 79419 N_IT 26.77 33.47 33.47 33.47 N_BIT 14.12 5.36 5.36 5.36 N_TS 22.36 15.07 15.07 15.07 N_ETS 16.05 9.58 9.58 9.58 N_EETS 0.01 0.04 0.04 0.04 T_B[s] 1.27 1.79 1.76 1.82 T_TR[s] 244.3 167.9 167.2 167.7 TEAPOT N_IN 5810 2996 2072 3062 N_ORP 2622 7 0 14 N_BB 2273 13 1 20 N_V 27324 33461 31365 33625 N_EV 1164 8167 10485 8180 N_OIV 172608 135606 113922 137024 N_IT 40.89 19.77 19.11 20.28 N_BIT 74.66 3.28 0.96 3.62 N_TS 77.80 14.65 15.28 15.03 N_ETS 52.74 11.19 12.21 10.95 N_EETS 0.09 4.14 7.34 4.03 T_B[s] 2.91 3.18 3.33 3.16 T_TR[s] 439.3 41.41 27.68 43.04 TETRA N_IN 3545 940 1077 940 N_ORP 4096 0 0 0 N_BB 3087 8 1 8 N_V 2629 12010 13437 12010 N_EV 0 4348 5612 4348 N_OIV 8192 47944 52024 47944 N_IT 35.27 16.01 17.19 16.01 N_BIT 60.56 1.88 0.66 1.88 N_TS 60.56 9.47 13.29 9.47 N_ETS 45.92 7.46 10.33 7.46 N_EETS 0.00 3.23 7.21 3.23 T_B[s] 1.44 1.17 1.41 1.19 T_TR[s] 148.1 8.64 7.78 8.71 TREE N_IN 8292 642 642 642 N_ORP 8148 1 1 1 N_BB 6898 1 1 1 N_V 5556 17700 17700 17700 N_EV 1 11125 11125 11125 N_OIV 16451 23938 23938 23938 N_IT 16.97 3.70 3.70 3.70 N_BIT 45.72 1.00 1.00 1.00 N_TS 45.72 9.92 9.92 9.92 N_ETS 30.62 9.04 9.04 9.04 N_EETS 0.00 7.12 7.12 7.12 T_B[s] 1.54 1.48 1.43 1.46 T_TR[s] 446.9 18.4 18.32 18.38 The orphanage grids in the adaptive grids ---------------------------------------------------------- We tested orphanage grids (the grids for objects which were not included into the clusters) and it is helpfull for one SPD scene - lattice. The other scene create only one orphan at most, so orphanage grid is useless. (f, m, o) (f, m, o) (f, m, o) (f, m, o) (f, m, o) (f, m, o) 1,0/0,1/- 1,5/0,1/- 1,5/0,5/- 2,0/0,1/- 1,5/0,1/+ 1,5/0,5/+ FLUID N_IN 1392 396 396 396 333 333 N_ORP 1004 77 77 77 77 77 N_BB 787 60 60 60 1 1 N_V 8551 7160 7160 7160 7288 7288 N_EV 331 2024 2024 2024 2024 2024 N_OIV 30901 21389 21389 21389 21501 21501 N_IT 29.75 13.49 13.49 13.49 27.41 27.41 N_BIT 46.89 1.87 1.87 1.87 1.00 1.00 N_TS 48.85 8.91 8.91 8.91 13.03 13.03 N_ETS 32.93 6.11 6.11 6.11 8.91 8.91 N_EETS 0.25 2.35 2.35 2.35 2.35 2.35 T_B[s] 0.86 0.71 0.7 0.72 0.7 0.71 T_TR[s] 203.2 18.68 18.86 18.76 27.6 27.72 LATTICE N_IN 6904 765 205 130 189 199 N_ORP 8281 762 14 13 762 14 N_BB 6123 600 8 29 27 1 N_V 5342 7782 9514 8471 8767 9519 N_EV 0 1140 1842 1536 1790 1851 N_OIV 16562 21543 29953 21942 22176 29941 N_IT 100.44 30.39 26.01 25.17 27.72 26.05 N_BIT 152.67 11.91 1.11 4.29 4.48 1.00 N_TS 152.67 25.86 11.43 16.84 27.06 11.54 N_ETS 122.79 20.95 9.75 13.95 22.87 9.76 N_EETS 0.00 2.89 2.02 1.67 9.39 2.13 T_B[s] 3.54 0.97 1.56 0.96 1 1.44 T_TR[s] 1997 261.6 84.85 129.6 149.3 84.86 ============================================================================== Grids comparison In the following table we report the best results for all the grid methods mentioned, so the methods can be compared for one scene at the same line. For uniform grid we selected the grid with customary resolution setting that achieves best timings. We let the reader to make conclusion himself, we presented our opinion in our RTNews article. Grid type ---------------------------------------------------- ------ RecGrid HUG AdaGrid Uniform scene Grid Customary BALLS N_IN 1531 7 1492 0 N_V 38877 7754 18080 207936 N_EV 11519 5734 4634 184204 N_OIV 117525 14606 29994 33909 N_IT 16.94 18.80 14.90 41.48 N_TS 16.87 8.63 11.29 17.32 N_ETS 13.02 5.84 8.80 17.32 N_EETS 7.49 4.11 4.98 13.93 T_B[s] 0.39 0.4 2.79 0.39 T_TR[s] 36.73 34.01 30.51 38.52 FLUID N_IN 590 6 396 0 N_V 23787 2522 7160 204288 N_EV 2043 1748 2024 36166 N_OIV 562303 6294 21389 172914 N_IT 26.73 43.39 13.49 56.33 N_TS 13.32 7.54 8.91 18.55 N_ETS 9.93 4.59 6.11 18.55 N_EETS 2.72 2.39 2.35 7.14 T_B[s] 1 0.18 0.72 0.96 T_TR[s] 23.79 28.82 18.76 32.13 GEARS N_IN 19645 125 6866 0 N_V 298119 12024 63318 240100 N_EV 17422 4284 1744 194920 N_OIV 2527805 80094 261772 171316 N_IT 27.72 32.89 32.30 17.52 N_TS 14.27 7.06 13.28 18.95 N_ETS 10.03 3.72 8.25 18.95 N_EETS 4.47 1.50 0.65 14.62 T_B[s] 5.06 1.04 5.88 1.13 T_TR[s] 214.9 242.1 330 192.3 LATTICE N_IN 289 1 130 0 N_V 11568 6859 8471 205379 N_EV 0 0 1536 102640 N_OIV 62836 38620 21942 160819 N_IT 34.87 25.07 25.17 8.81 N_TS 6.40 5.87 16.84 13.70 N_ETS 5.30 4.87 13.95 13.70 N_EETS 0.00 0.00 1.67 7.51 T_B[s] 0.16 0.3 0.96 1.27 T_TR[s] 82.05 71.62 129.6 34.21 MOUNT N_IN 10573 1 2867 0 N_V 143477 900 28869 42875 N_EV 16203 573 8001 37246 N_OIV 769408 16452 99053 38922 N_IT 15.51 51.78 19.11 13.32 N_TS 12.42 5.62 15.11 15.01 N_ETS 10.19 4.63 11.85 15.01 N_EETS 5.11 1.66 4.45 9.60 T_B[s] 1.98 0.16 2.54 0.4 T_TR[s] 30.28 62.31 59.05 25.15 RINGS N_IN 2094 1730 2800 0 N_V 35503 9546 19015 216000 N_EV 8895 2283 748 178930 N_OIV 113662 32197 79419 127217 N_IT 30.46 25.71 33.47 21.48 N_TS 18.51 12.91 15.07 33.71 N_ETS 14.84 8.01 9.58 33.71 N_EETS 7.80 4.24 0.04 27.22 T_B[s] 0.39 0.45 1.82 0.98 T_TR[s] 113.9 116.3 167.7 83.7 TEAPOT N_IN 6334 931 3062 0 N_V 110582 12946 33625 192000 N_EV 22961 8463 8180 175514 N_OIV 691621 39007 137024 75105 N_IT 17.53 22.60 20.28 13.30 N_TS 19.67 16.40 15.03 41.24 N_ETS 17.13 14.28 10.95 41.24 N_EETS 13.09 11.63 4.03 38.08 T_B[s] 1.55 0.53 3.16 0.65 T_TR[s] 22.67 25.61 43.04 18.76 TETRA N_IN 1565 1 940 0 N_V 40404 4096 12010 64000 N_EV 14220 3017 4348 56696 N_OIV 218944 16396 47944 44696 N_IT 21.49 28.89 16.01 9.17 N_TS 12.34 8.09 9.47 18.24 N_ETS 10.00 7.42 7.46 18.24 N_EETS 6.83 5.64 3.23 16.63 T_B[s] 0.47 0.24 1.19 0.34 T_TR[s] 7.23 7.22 8.71 3.86 TREE N_IN 501 7 642 0 N_V 32376 8116 17700 216000 N_EV 19476 6619 11125 212179 N_OIV 63640 12585 23938 14322 N_IT 12.03 12.03 3.70 355.45 N_TS 14.62 5.78 9.92 56.36 N_ETS 12.88 3.19 9.04 56.34 N_EETS 8.26 2.52 7.12 45.36 T_B[s] 0.28 0.48 1.46 0.33 T_TR[s] 33.91 38.48 18.38 781.3 ------------------ END