javor wrote:Following up the discussion from the "glitch pictures" thread:
As with the Nemoto & Omachi and the Macro-regions paper, the resulting acceleration structures are indeed very similar, but not the same. You certainly have a point criticizing how the paper is positioned, but our view on this is that the novelty is mainly in the combination of construction and traversal algorithms (and the resulting performance), not so much in the the geometric representation of the spatial index structures.
Then why do you say this in Section 1, Paragraph 2, of your paper?
In this paper, we demonstrate that efficient ray traversal on modern GPUs is also possible with a new type of acceleration structure, which combines characteristics of hierarchical grids and bounding volume hierarchies.
To me it looks like you guys clearly thought the acceleration structure itself was novel. The acceleration structure is EXCELL so I think that paper should be referenced or, at minimum, acknowledged in some fashion. The traversal algorithm you guys use IMHO is also similar to prior EXCELL algorithms. What is novel in your work IMHO is the construction method plus the fact it's optimized for a GPU architecture. I quote the "Adaptive cell division for ray tracing" (1991), B. Pradhan, A. Mukhopadhyay paper I referenced before in the other thread because I think it makes this more explicit:
2. PROPOSED DATA STRUCTURE
We assume that the entire object space is uniformly divided into cells by a three-dimensional "virtual" grid of predefined resolution. We call this grid virtual because the cells are not occupied by the objects in object space but by integer entries which guide the search through object space. The virtual grid is represented by a three-dimensional integer array with each cell represented by an element of the array. The space subdivision is done in the following manner: At the beginning the entire object space is enclosed within a box called the root-box on which we superimpose the virtual grid. ... Fig. 1 illustrates this subdivision in two dimensions ... In the case of quadtree division (two-dimensional version of oct-tree division) this box will be divided into four uniform quadrants ... Now notice that each box contains an integral number of cells along both the x- and y-axes. Thus, every cell is contained in exactly one box. We mentioned earlier that the virtual grid is an integer array. This is because the array element corresponding to a cell is filled with identification number of the box which contains the cell. ... The data structures for cell division described in the previous section are shown in Fig. 3. It shows the box-array, an array of pointers to box structures created during subdivision. A box is entered into this array when it can no longer be subdivided. A box is uniquely identified by an index of the array. ... Each box consists of cells which contain the index of this box structure in the box-array.
3. TRAVERSING THE DATA STRUCTURE
Traversing the data structure by a ray is reduced to traversing the virtual grid in object space. When a ray is fired, the first point in which it intersects the root-box is calculated. From this point onward the number of cell units traversed by the ray in both the x-and y-directions are maintained. Since cells are of uniform size, this can be obtained by dividing the actual distance traversed in x- and y-directions by respective cell dimensions in those directions. These cell units need not be whole numbers, since a ray may happen to cross a fraction of a cell. But the integer portions of the cell units yield indices of the cell the ray is currently traversing. Using these to index into the virtual grid we get the number of the box the ray is traversing. ... To find the next box, first we have to obtain the point at which the ray leaves the present box. Next, we have to calculate a point slightly away from the previous point along the direction of the ray. Glassner  employs a method in which the ray is intersected with all the six planes of the current box, and the nearest plane or planes are found by determining the smallest t values. This method consumes nine multiplication and nine addition operations, assuming that division and subtraction are equivalent to multiplication and addition, respectively. Lee  uses a target plane method in which 5 multiplications and 6 additions take place on average. But, in the worst case, this is slower than the Glassner's method. We employ another different method which is faster than the above two methods. We start by observing that any ray can potentially intersect, at most, three of the six planes of the current box, at the point where it leaves the box. We classify these six planes as lower x- plane, higher x-plane, lower y-plane, higher y-plane, lower z-plane, and higher z-plane. After determining the ray source u and the ray vector v, we find which three of these planes will possibly be intersected by the ray with smallest t by examining its ray vector. For example, if v has a negative x component then the lower x-plane, but not the higher x-plane, is to be tested for intersection. This method consumes five multiplications and six additions in the worst case, which is equal to the average case performance of Lee's method .
It looks to me like this describes the method you guys use at:
https://github.com/madmann91/hagrid/blo ... raverse.cu
This is also described in the paper "A new algorithm of space tracing using a CSG model" (1987), Kadi Bouatouch, Mohamed Ouali Madani, Thierry Priol, Bruno Arnaldi.
Still think it's a waste of time to read the prior work? Shit, now you made me do *your* work.
But this was fun because I found a lot of other papers about something else that I'm currently working on as a result so it's good.
AFAIK your construction algorithm *is* novel compared to prior published EXCELL work, plus it uses SAH, and it is implemented on a GPU, I have no doubt that you guys ended up reinventing a lot of this independently (it wouldn't be the first time it happened in the field; the grid voxel traversal algorithm was even independently conceived by at least 3 teams in the 1980s at roughly the same time frame in different areas of the globe!). But that's no excuse not to quote the prior art in the future now that you know that it exists. At least that's my POV. Still, it doesn't detract from your major achievement, like I said before.