-
Notifications
You must be signed in to change notification settings - Fork 0
/
havran_stats_grids.txt
857 lines (750 loc) · 46.2 KB
/
havran_stats_grids.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
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