Glitch Pictures anyone?

[ultimatemau]

Trying to implement 'Irregular grids'. Almost there.

Looking good! I might give this a try myself . Are you looking at: http://www.kalojanov.com/data/irregular_grid.pdf ?

[jbikker]

Correct.

[ziu]

Looking good! I might give this a try myself . Are you looking at: http://www.kalojanov.com/data/irregular_grid.pdf ?

That is an interesting paper! While it does have some similarities to macro-regions it looks a lot more similar to this old algorithm that dynamically increases and decreases the size of each of the grid's voxels depending on the amount of rays entering it and the amount of primitives to be intersected inside the voxel (i.e. the load). The difference with the irregular grid paper above is there the SAH is pre-computed and the voxels are resized as a pre-processing step instead of being dynamically re-computed during rendering like in the old paper (that I link below):
http://graphicsinterface.org/wp-content ... 1986-9.pdf

It is a shame Nemoto & Omachi's (1986) paper was not linked in that article since it seems a lot more relevant than most of the things it references. There are also more recent references with macro-regions e.g. "Macro 64-regions for uniform grids on GPU" (2014), Eugene M. Taranta II, Sumanta N. Pattanaik. The proximity clouds references are kinda pointless. Although it is also a space skipping technique it's different.

Also: The data structure used in the "GPU Ray Tracing using Irregular Grids" paper (uniform grid/bounding volume hybrid) looks really similar to that proposed in the paper "Adaptive cell division for ray tracing" (1991), B. Pradhan, A. Mukhopadhyay. (see Fig. 3). or "A new algorithm of space tracing using a CSG model" (1987), Kadi Bouatouch, Mohamed Ouali Madani, Thierry Priol, Bruno Arnaldi. (see Figure 4). Link:
https://hal.inria.fr/inria-00075942/document

This data structure is also described in "The EXCELL Method for Efficient Geometric Access to Data" (1982), M. Tamminen. (see Figures 2, 5).

So this paper lacks essential references. Plus it has too many pointless BVH and kd-tree references. This part of the paper, the related work and the references, could use some improvement.

Their grid construction algorithm could also be faster. Looking at their 'emit_new_refs', for example, it uses a per primitive loop to generate the prim and cell ids, which will have poor workload distribution in scenes with dissimilar sized primitives. We solve that in our paper:
https://www.academia.edu/13928983/Effic ... hitectures

It is nice that the article comes with code and the algorithms are interesting (though not completely novel) also the results speak for themselves. The solution also has quite nice rendering performance!

It is nice to see people working on grids. They have been IMHO under explored in the present literature so this paper is very welcome!

[javor]

Hi, I tried to create a new topic and post a reply there several times already, but without success. Sorry for carrying this thread further off-topic.

It is great to see that our paper received attention from members of the forum. Myself and Arsene will be happy help anyone who is interested in experimenting in this direction.

To address Vasco's concerns:

So this paper lacks essential references. Plus it has too many pointless BVH and kd-tree references. This part of the paper, the related work and the references, could use some improvement.

The Nemoto & Omachi and Taranta et al. citations are certainly an oversight on our side, thanks for pointing this out. I was not aware of the first paper, and have no excuse for forgetting to cite the Macro/Micro regions papers. When writing the paper, we considered positioning the paper only as a grid-based ray tracing method, but decided against that. Personally, I think that pointing the reader towards the state-of-the-art ray tracing approaches on current hardware is more important than differentiating our method from algorithms tested so far back in time. If it was up to me, we would also leave out the comparison with macro-regions, which was forced on us by the primary reviewer. We are aware that a multitude of similar approaches exist and have been tried before. The important point is that the particular combination of techniques we implemented delivers surprisingly good performance from a type of acceleration structure, which, as you said, does not see a lot of attention.

Their grid construction algorithm could also be faster. Looking at their 'emit_new_refs', for example, it uses a per primitive loop to generate the prim and cell ids, which will have poor workload distribution in scenes with dissimilar sized primitives. We solve that in our paper:
https://www.academia.edu/13928983/Effic ... hitectures

The construction speed is indeed the part where we expect to see improvements in the future, however, I would look elsewhere for optimization opportunities. Overall the initial two-level grid construction is the fastest part of the build process, and most of the time is spent merging and expanding cells. Also, the first level grid we create is too sparse for the suggested technique to work, which is why Arsene did not include it in the implementation. Of course, we are happy to be proven wrong!

[ziu]

The Nemoto & Omachi and Taranta et al. citations are certainly an oversight on our side, thanks for pointing this out. I was not aware of the first paper, and have no excuse for forgetting to cite the Macro/Micro regions papers. When writing the paper, we considered positioning the paper only as a grid-based ray tracing method, but decided against that. Personally, I think that pointing the reader towards the state-of-the-art ray tracing approaches on current hardware is more important than differentiating our method from algorithms tested so far back in time. If it was up to me, we would also leave out the comparison with macro-regions, which was forced on us by the primary reviewer. We are aware that a multitude of similar approaches exist and have been tried before. The important point is that the particular combination of techniques we implemented delivers surprisingly good performance from a type of acceleration structure, which, as you said, does not see a lot of attention.

Hey Javor,
Well some of the references I mentioned are obscure and rather dated. So I can certainly understand how they could have been overlooked.
But it is essential that you guys reference the EXCELL (Tamminen et al.) data structure papers in future publications. It is the exact same acceleration structure even if the construction method might not be the same. You guys quote already Cleary and McDonald and Booth which are also quite old and IMHO less apropos. So it doesn't make sense to ignore the references of the guys who actually describe the same data structure. I've searched the literature some more afterwards. Jensen mentions using EXCELL in the early 1980s in the RTNews archives and it seems to have been fairly commonly used back then (e.g. it's also referenced in Bouatouch's papers). For whatever reason both later favored kd-tree data structures. My guess is this was due either to hardware limitations back then or due to improvements to kd-tree SAH methods which made them faster. For example, regarding hardware, back in the 1980s it was common to use an hashtable to store the grid due to memory limitations but today quite often we just use a plain array because memory is much more plentiful and pointer chasing degrades performance. Back then the memory wall barrier characteristics were a lot different. Hardware memory latency was comparatively better versus instruction latency so the algorithms reflect that.

The construction speed is indeed the part where we expect to see improvements in the future, however, I would look elsewhere for optimization opportunities. Overall the initial two-level grid construction is the fastest part of the build process, and most of the time is spent merging and expanding cells. Also, the first level grid we create is too sparse for the suggested technique to work, which is why Arsene did not include it in the implementation. Of course, we are happy to be proven wrong!

Well in that case you guys would indeed be better off looking at the kd-tree (morton) or macrocell related literature for improvements in build times. But looking at Figure 5 in your paper you spend like 40% of construction time building the initial grid on average. San Miguel in particular has a lot of dissimilar sized triangles. In our experience this can be done up to 9x faster for such scenes. It's a shame we can't compare your build times with a state of the art high-quality GPU BVH or kd-tree like (Karras and Aila 2013) since their code is AFAIK not publicly available. Still it seems to me, from reading your paper, that you guys have achieved state of the art rendering performance, which is the main focus of your algorithms. So kudos for that!

So it's interesting to see you guys show it's possible to have good rendering rates with a grid based acceleration structure. I suspected as much from looking at the late 1980/early 1990s literature but I couldn't convince people on arguments alone. The thing is, what burned a lot of people back then, was that hierarchical grids have a lot of edge cases where the memory consumption exploded or the performance didn't go up no matter how much you increased the grid resolution so it kind of put people off grids for ever. Typically this involved scenes with nested geometry akin to the Hairball scene we use today. The Standard Procedural Databases "Shells" scene is the example typically used back then.

[papaboo]

SPTD_glitch.png (609.76 KiB) Viewed 1010 times

Messed up a transform while cleaning up my implementation of A Spherical Cap Preserving Parameterization for Spherical Distributions. I call it the Blackhole Sun effect.