Repository navigation
Log
Report log: updates most likely Wednesday / before other meetings / when i have some mayor changes
I am quite happy with the results of the cache analysis evaluation. It was quite surprising that wider node and leaf sizes have less cache misses for wide traversal. (reason for this is most likely that the tree is more compact and therefore the different paths trough the tree are automatically more similar)
For now there are no new features planned. The only type of changes to expect are bugfixes and improved quality of life, and new matplotlib plots.
Main effort right now is going into writing the thesis (separate repository) and gathering all the data.
- fixed counter of unique vertices per leaf node (theoretical space improvement due to vertex duplication's in leafs)
The loads from the heap are exactly the same for single ray and wide traversal, just difference ordering.
Size of the node (in cache lines):
- N4 : 2
- N8 : 4
- N12 : 6
- N16 : 7
Additional Size of triangle data for leaf nodes (in cache lines):
- L4 = 3
- L8 = 5
- L12 = 7
- L16 = 9
For the wide renderer we have approximately the same amount of loads from the stack and the cache. (only for 4N4L)
What is loaded from the stack?
- the ray data (array with 256 entries, each ray is 10 floats, aligned as 64 byte <- performance wise its even / very slightly slower than without padding, so from now on i do it without padding. Comparison of results: NoPadding, WithPadding)
- the elements from the stack that stores all the nodes that still have to be tested. (40 arrays of 256 arrays of int32) This are 640 cache lines.
What a best case scenario would look like with the following assumptions: No cache lines can be reused from the step before. 50 step average, 16*16 work group:
- From the todo stack we have a 15/16 hit rate when every ray has the same amount of elements in the stack. Since every step 2 access to the array per ray (once writing it, then some when later loading it again) we have #rays * #steps * 2 loads, of witch we have 1/16 misses in the best case where all rays go the same path in the bvh. -> total 1600 misses
- For the ray data we basically load 256 cache lines every step. With our assumption that we dont keep data from the step before this is a total of 12800 misses (100% miss rate). This is not that pessimistic since we have 256 cache lines per thread.
So in total we approximately have 14400 misses for the stack. For the cache size 256 that fits our assumption we have an average of 14727 misses. I assume that the extra misses we get from diverging bvh traversal counteract the extra hits we get due to some cache lines that are still left from the step before.
With 512 cache size we have only 651 misses, because it has enough space to contain all the data from the rays.
This graph could be improved by not padding the ray to 64 byte, then we could fit all rays in 160 cache lines instead of 256, (see above links for difference in graphs)
The 8*8 graph: (more stack efficient, but less heap efficient) pdf
The 32*32 graph: (more heap efficient, but less stack efficient) pdf
Mostly out of date info, summary in next weeks post
Single ray traversal, the average amount of cache misses per ray. The cache is reset for each 256 ray group
256 rays have 6904 cache misses average for camera0 and 8891 for camera1
Right now we see a spike every 16 rays due to the way we loop trough the work group. This could be improved by changing the order. There is no observable change when the cache is "full".
Update: with improved order it looks like this CacheMissPlot
Camera0 miss: 6546.7584
Camera1 Miss: 8953.8099
Overall it has slightly less cache misses (But without spikes). Performance is definitely better.
The results can vary per run since the pointer and therefore the cache Ids are not deterministic.
UPDATE2: mistake in cache reset lead to wrong values.
New graph looks like this. (larger spike for first ray)
Update3 Following changes are (will be) made: separate heap and stack cache misses, separate primary and secondary rays
New graphs for different cache sizes:
Only shows heap values since stack is basically 100% hit rate.
Next graphs show how the different algorithms perform with different cache sizes. Its done with N4L4 and a 16 x 16 workgroup Hitrate, Misses
(todo for those plots: small arrows for min max)
More detailed plots with separated heap and stack misses, for different Nodes sizes.
Whats interesting here is that for single ray traversal the stack hit rate basically stays very high while the heap hit rate is really bad with smaller stack. For the wide renderer it is the opposite, here the heap hit rate stays relatively stable, and the stack hit rate decreases.
There was once again a bug with what i put into cachesimulator.
Size of the node (in cachelines):
- N4 : 2
- N8 : 4
- N12 : 6
- N16 : 7
Additional Size of triangle data for leaf nodes (in cachelines):
- L4 = 3
- L8 = 5
- L12 = 7
- L16 = 9
after this post we ignore wide v0 and only look at wide v1.
- reordered single ray traversal to first do all primary rays of the workgroup and then all the secondary rays.
- Added unit testing with catch2 for the cache simulator.
Last weeks analysis only looked at how many unique nodes where loaded per step, but i didnt tough about a direct comparison of how many nodes single ray traversal loades compared to wide traversal.
This has the following assumptions:
- Single ray traversal does not cache reuse nodes from previous ray.
- Wide ray traversal doesnt have cache to reuse nodes from previous steps. (in theory it could rarely happen that different rays intersect the same node at different steps, but this is not accounted for with our numbers).
Every data point represents one work group. For the wide renderer this means that the number of unique nodes is divided by the ray count. For single ray traversal we treat the rays as if they where in workgroups and compute the average, max and min node / leaf intersection count. The data points are then sorted by the averages (both wide and single ray). 16x16 workGroups, with ~4k image -> 32k samples.
So overall the wide renderer significantly reduces the amount of nodes and leafs that have to be loaded into the cache. The wide renderer also seems to have more stable numbers with only very view exceptions
Work in progress.
Workgroup is refilled when its at least 50% empty.
Primary ray works with one small bug (one pixel is wrong for every thread, not sure where and why)
Temporary stop, not sure if i continue.
For N4L4:
- Node loaded data = nodesize = 128 B -> 2 cachelines
- Leaf loaded data = nodesize and triangleSize = 128B and 144 B (944) -> 2 + 3 cachelines
The Amd and Intel cpu both 512 cachelines in L1 (per core). The Amd cpu has 8192 cachelines in L2 (per core), the Intel cpu "only" 4096
All data about cache misses is outdated / wrong
Simulated cache: 8 way associative. Tree PLRU as replacement strategy. https://en.wikipedia.org/wiki/Pseudo-LRU
The cache itself is implemented, now all the possible load and store operations need to notify the cache simulator.
The measurements must be done with the fast renderer since the instrumented one has a slightly different data structure. The option is implemented with templates so its compile time for only one renderer and doesnt cost anything when its deactivated.
The following things will be traced with the cache simulator:
- the heap loads and stores for nodes and triangles.
- from the stack we load everything that is larger than a few cachelines and where the load location can change (example: the stack that stores the nodes we still have to traverse).
Verified that the cache works how i specified it. (fixed huge error with multi threading)
-
The hit rates of the cache simulator are kinda fabricated since i have to decide what to "load".
-
When only comparing node and leaf loads the wide traversal is way better. It can even work with a very small cache. With only 32 cachelines the wide traversal has a hitrate of ~80% and single traversal a hitrate of 10% (N4L4). But like said above, this only counts node and triangle loads.
-
With the additional stack loads for wide traversal (from the overhead to manage 256 rays at once) we have more cache loads and can no longer compare the hit rate of the two traversal modes. I think the fairest metric to compare them is the number of cache misses.
-
There is no change in cache miss rate depending on the number of rays.
With for N4L4 single ray traversal has slightly less misses than wide traversal (256 cachelines, 16x16 workgroups), but the wide renderer performs significantly better with smaller cache and larger nodes.
- Refactored template structure to no longer use the .cpp
follow up to last week, implemented instrumented renderer.
Comparison of the graphs for work group analysis with the new and old version with two different camera positions:
Time for each workgroup, (normalized so its per ray) plot
Overall its nothing unexpected, it takes slightly more steps to finish,
The spikes in the primary ray part for camera 0 most likely come from the visible floor.
Performance of the 3 render versions: normal renderer, wide renderer V0 and wide renderer V1.
- V0 : The results of the node intersection can result in a leaf intersection for the same ray in the same step.
- V1 : Results of the node intersection are only used in the next step
Wide traversal relative to single ray traversal
So the general result is that the wide versions can handle the larger node and leafsizes better (N4L4 is still fastest, the plot could probably be improved... (small numbers for actual times would be possible))
We had the assumption that the reason why the single ray traversal is slower for N16L16 compared to wide ray traversal is related to cache behavior. Its seems that for single ray traversal the nodes from the last step are still in the cache for smaller configurations like N4L4. Larger nodes generally mean that we load more (wasted) data while traversing the tree, and this could push out the nodes from the beginning of the traversal.
Our approach to validate this assumption is to pad every value that is loaded, and then observe how the performance changes with different padding.
Parts that are padded:
- every triangle position float. So p0.x, p1.x, ... is transformed to p0.x, padding, p1.x, padding, ...
- every node bounds float. (like above)
(Both of them result in ispc complaining about Coalesced 4 gathers, but the performance impact is not that sever).
For maximal padding (64 additional floats, so the cacheline is filled) we would need to use ispc with 64 bit addressing for our node array that is than 4 GB after padding. Since it doesnt seem to be necessary to load 64 times the data this is not done jet. EDIT: small mistake on my side, the cacheline can only fit 16 floats...
For now the paddings i want to test: 0 (no padding), 1, 2, 5, 10, 20. This is with N4 to 16 and L4. The leafsize is fix since it change the times that much. (Padding of over 15 doesnt make sense since 16 floats already fill one cacheline)
Wide traversal relative to single ray traversal
So our assumption seems correct that the single ray traversal is more affected by the padding than the wide traversal.
- idea to do all leafnodes that are on the stack at once (for each ray) is slower. (it is faster when when all timers are on...)
- Multiple performance improvements for wide raytracer and quite some refactoring.
- Improved some plots + refactoring matplotlib code.
- Fixed some counter overflows. Turns out
uint64_t sum = std::accumulate(vec.begin(), vec.end(), 0)sums up over an int (the type of the 0) and than converts that int to uint64_t.
- previous version: One step does the following: first the node intersection, than the leaf intersection. If a ray has to do a leaf intersection after the node intersection this is done in the same step.
- new Version: Here the node and leaf intersections are strictly separated in each step, so the result of step x is only used in step x+1.
Major implementation difference: with the previous version keeping track of what work each ray has to do was done in place(one array for nodes, one for leafs), while the new version will fit both nodes and leafs in one array, but i still needs two arrays since it cannot be done in place.
The current implementation of the new version is slower. The interesting part is that leafs only take 50% of the time compared to the previous implementation.
- Old version: totalTime 0.872, leafTime 1.054, nodeTime 5.922
- New Version: totalTime 0.891, leafTime 0.519, nodeTime 6.605
It would be possible to store the triangle data in the space of the aabb data. (with N12 you can fit 8 triangles in the space needed for 12 aabbs). Otherwise the space for the aabb is unused and kinda wasted. Or should i separate normal nodes and leafnodes? then i would have 2 vectors, might try different things.
Tried it out and N12L8 performance decreased from 0.83 to 0.86 seconds on my intel cpu. I expected that the removal of the extra indirection improves performance, but seems that i was wrong.
Wide traversal works and we have the same intersection results as with the previous traversals. Additional Data i collect (for both primary and secondary):
-
total number of nodes / leafs done in every step
-
number of unique nodes / unique leafs done in every step
-
the numbers presented in the whisker plot changed a bit since: Before we computed the estimated termination of a ray by adding node and leaf intersections together. In reality one step first computes the nodes, and then the leafs. So every leaf intersection after a node intersection only takes one "step". UPDATE: i will try and compare this version with a new version where i only test 1 ray in a step (either as leaf or as node)
Might be interesting to see how strong the effect of different camera positions is.
How the data is combined:
- for performance values the average of the results of each camera is used (so average of mean).
- for the data collection: do average of all values since they are already average over every ray.
- exception: depth images. For now i only do them for the first camera and ignore the rest. (they are not that important)
- The wide renderer data and the whisker plots are needed for each camera separately.
- fixed some small mistakes with the intersection counters. (shadow rays would stop after first tri hit instead of finishing the batch, and every normal ray had one aabb intersection with the root node in the beginning)
- multiple small fixes so that both images (data collection and performance) are identical again. The data collection render previously used the stored normals instead of calculating them from the triangle edges.
- Primary rays that hit no target now dont cast secondary rays for the wide renderer.
- increased stack size for the rays to 36 (from 32). The second camera for lumberyard crashed with 32. Took longer than expected to find the source ... since debug mode would take hours on the scene and debugging with release was extremely confusing.
- current time: 0.23 seconds for N4L4
- Overall it works. It is faster than the normal traversal, but slower than normal traversal without timers.
- Improved performance and memory usage.
- fixed mistake which caused secondary rays to do closest hit instead of anyhit. (This only affected wide traversal, and had minimal performance impact)
Added templating to the ispc traversal algorithms using jinja2 (python templating engine)
This improves performance significantly (from 0.28 to 0.23 seconds) The performance improvement originate from two parts.
- constant loop length
- one calculation less to calculate address to fetch memory
tri[triId + index + leafMemory * 6). Intex is the loop variable that can be unrolled, triId is the id to the first triangle in the leafnode, and leafmemory is the variable we can convert to a constant.
Result of looking at assembly: ispc is not smart enough to understand the structure and do efficient memory access. Therefore the constant version is sadly the best thing to do. (code gen yeay)
Also removed the early stop when loading memory for memory tests... It just doesnt make sense anymore to have memory tests. (not sure about the results but it might be like that because i dont "use" the memory and it is optimized away?).
Leaf times before removing: (all N4)
- L4 memory 4 = 0.9
- L4 memory 8 = 1.44
- L4 memory 12 = 1.49
- L4 memory 16 = 1.54 There is nothing our function approximation would do for us with that result. (i suspect that it might not have loaded the memory we wanted it to load)
Leaf times after removing: (all N4)
- L4 memory 4 = 0.82
- L4 memory 8 = 1.34
- L4 memory 12 = 1.75
- L4 memory 16 = 2.18 This now does the triangle computation with just zeroes.
Those are the SUM of the threads, so the overall impact is not that large.
One thing we can learn from the above times that it might be worth to save the number of leafs(nodes) so we can loop over less when a node isnt full (only relevant for N/L larger than 4)
The possible speedup from this can be seen from our current memory tests that just do the same calculations with zeroes. So if we have L16 and 50% of our leafs only have 4 or less triangles then we can approximately double the performance of half our leafnodes.
Possible approaches: either save size directly or store it indirectly in the floats (as NAN).
-
The approach to store NAN floats seems to generate to much overhead to be worth it. First problem is that you cannot break or return from a foreach in ispc, and it is slow to do continue on each lane.
-
Second idea with this is to use the last float as NAN and the second last float as the number of loop we want to do. This would require me to generate combinations of loop and memory variables and i hate it... I tried the approach with the old not constant ispc method (so loop count and memory as parameter) and it improved the performance slightly compared to the version that always tests all aabb/triangles. UPDATE: I can obviously also store the data as if the node was smaller, so we can access everything in soa order without knowing the target node size.
-
Tried it to directly store the size and it hat similar performance compared to the above approach.
Before: saving node order for each octant (sign of each ray direction axis) Now: saving node order for each Face (largest ray direction)
It seems like the timers are more expensive than i expected. Last time i tested it the overall traversal was not as optimized as now so the timer overhead didnt have that big of an impact.
Removing the timers to calculate the triangle intersection time currently improves performance from 0.975 seconds to 0.857 seconds on my pc.
- small performance improvement by precalculating the code to choose the node order. TODO: need to verify this again. For wide traversal it doesnt seem to be worth?
- improved memory size of nodes
- Started to use NaN instead of hard coded values for special floats that have a meaning.
Added option to not save the distance to tested aabbs.
It gives small performance improvements for some scenes, but only for small branching factors. (lumberyard has a small improvement for N4L4, very small improvement for N8L8 and took slightly longer with N16L16)
I tried to improve performance of the ispc intersect method. The code that was used for the memory test was also used for the normal performance measurements. So each intersection always loops over the target node size (or memory size) and also loaded the memory.
Name explanation: *MemorySize: the amount of memory a node uses. In general there are only multiples of 4 (sse) and 8(avx) allowed. A node / leaf that has a target width of 6 is padded with zeroes so it takes as much memory as if it had a width of 8.
In ispc we loop MemorySize times: foreach(index = 0 ... MemorySize )
and for triangles we stop the loop directly after loading the memory if we go over the leafsize.
I was not able to improve the performance of this. Things i tried: EDIT: i did some mistakes here because i didnt have the real node size available.... so the next two points are just for the target branching factor
- Looping over the actual node size.
foreach(index = 0 ... nodeSize)This would lead to loops that are not a multiple of the intrinsic gangsize. (i think thats the reason it is slightly slower) - Looping over the next smaller multiple of 4 / 8. (so if we have SSE, a target node size of 12 and a node with 5 elements the loop would go over 8 elements)
The only thing that improved the performance was to set the memory size in the code, but since ISPC doesnt support templates im not sure how to implement this. (N4L4 with sse improved from 1.00 seconds to 0.87).
Ispc allows C like macros but that would be extremely unreadable. Code generation with python would be the easiest for me.
More to this in the next weeks entry.
Added new option to bvh builder that further splits possible leaf nodes. (depending on sah) It reduces the number of leaf intersections but slightly increases the node intersections. Overall performance is better.
There are now 3 options: Performance at the example of N4L4 on my pc for lumberyard interior:
- 1.02 seconds without leaf splits. Average number of leaf triangles: 3.94. Average Node children: 3.05. Sah of 123
- 1.01 seconds with only splits that dont generate new nodes. Average number of leaf triangles: 2.8. Average Node children: 3.8. Sah of 121
- 0.97 seconds for all leaf splits. Average number of leaf triangles: 2.57. Average Node children: 3.64. Sah of 118.
The reason the option to split everything is the fastest comes form the actual intersection counts. While the node intersections go from 45.3 to 47.3 the leaf intersections go form 7.08 to 5.3. The option to only split leafnodes without generating new nodes doesnt change the node intersections, and improves the leaf intersections from 7.08 to 6.9
(lumberyard interior with work group of 8x8) Small visualization of Primary and Secondary Rays
- changed triangle intersection (now the normal and position calculation is done after the bvh intersection).
- overall slight performance improvements to bvh intersect.
- fixed one initialization mistake that let the first node intersection to be positive for some aabb. The performance impact depended on the node size.
- some more optimizations (improved ray memory, hemisphere sampling, and the work stack)
- retired sah builder with bucket since the results where significantly worse that without.
- refactored config reading.
- transitioned to matplotlib instead of pgfplot(inside latex). It is way faster and easier to work with.
AMD Ryzen Threadripper 1950X 16-Core Processor (cpu might change later to one that also supports avx natively)
Results seem consistent with openmp multithreading.
added OpenMp multithreading for the performance test.
Changed the loop to go over workgroups like 8x8 (configurable in the options, only 8, 16, and 32 is supported)
calculation of node factors for sah, Values are for my laptop Result
The cost of one node is calculated by dividing the total node time by the number of node intersections. The same is done for leafs and with both the node factor is calculated.
For both lumberyard scenes. I also included the success ratio of intersections
Here a pdf to visualize it a bit: Analysis Result Pdf
And the raw tables: (also contain N8 values and secondary rays) Lumberyard Exterior Lumberyard Interior
- improved folder structure of the results a bit. (easier portable now)
- implemented subdivision that allows arbitrary (int) factors
The way it works: (pseudo code, sub means the number of triangles that are added for each triangle)
void subdivision(int sub):
if sub == 0:
<add triangle>
if sub >= 3:
<split this triangle into 4 by creating 3 new vertex at the middle of each edge>
<for each of the new triangles call subdivision with the remaining sub>
else if sub == 2:
<split this triangle into 3 by placing an vertex in the middle of the triangle>
<for each of the new triangles call subdivision with sub = 0>
else if sub == 1:
<split this triangle into 2 by splitting longest edge>
<for each of the new triangles call subdivision with sub = 0>
This method gives us triangles that are about the same size since we mostly do the 4 split that results in 4 triangles with exactly the same size. This zip has images of how the subdivision looks like for sponza up to subdivision 21 (here it means original triangle count * 21)
- refactored python data manager to support subdivision. (not finished jet)
- spent quite some time looking at data and fighting against latex
- added rendering code to give triangles different shades of grey
-
i decided to do the performance tests on my laptop. (i7 4700HQ @2400GHz) It supports avx and sse. To avoid throttling with avx and other effects that may be caused by turbo i set the frequency to 1.80GHz according to task manager (75% in the windows energy settings). Reasons to use laptop: more consistent results and overall more convenient since i do not use the laptop for anything else.
-
fixed some mistakes that lead to larger ram usage than necessary.
-
found the reason for a crash with huge triangle counts. ISPC uses 32 bit addressing by default. Now since scenes like sanMiguel have many triangles we can get past this limit during our tests. The issue is caused from padding during the memory tests. When using a leafsize of 2 with a leaf memory size of 8 (due to padding) we need 4 times more memory than without padding. In addition we do the memory tests and increase the memorysize to 16,24, and 32. At 32 it crashes (16 times the memory needed to represent the triangles). For now i will start with a leafsize of 4 (so i have comparison values for sse). The ispc addressing can be changed to 64 bit but that would affect performance so i will avoid that for now.
-
i verified again that for nodes its significantly faster to do the computation with only zeroes instead of some early continue. For triangles its the other way around. The triangle computation is costly enough that its faster to early exit instead of calculating with zeroes. This mostly influences the compute time of configurations where an ISPC gang is not fully filled (example L4 or L6 for avx).
-
It seems like i need more data points to get useful functions depending on triangle count.
-
i looked for more models. I found 10 more scans very similar to the gallery with 1 million triangles and 500k vertices.
-
Idea i have to test: Subdivide the scene to generate multiple triangle counts. This should reduce the noise that comes from camera position and scene complexity and also give us more data points. (a triangle can be split in 2,3,4, ... many variations, since it would be a simple subdivide without surface changes)
Cost factors These are with SSE
- Improved secondary rays. (optimized traversal for anyhit)
- performance results are now median of 5, and the first run is thrown away
- Improved bvh performance.
- added new scenes.
- The performance tests of last result where with sse4. The sse2 in the pdf was just a mistake where i forgot the 2 from avx2. During our meeting i thought you meant sse4-x2.
- tried a version without gather warnings for triangle output. Its slightly slower (or equal) than what i had before.
- implemented first version of cost and memory factor calculations
Performance analysis on AVX and SSE. Results changed a bit since last week due to performance improvements. Performance tests where done with an Intel 6700K.
Second Performance Analysis Result Pdf
- added the concept of node memory and leaf memory. A node will always take this much space no matter the branching factor or fullness. (same for triangle points for a leaf). Unneeded memory is filled with 0.
- extended area to do tests. AVX tests 8 now goes up to 64 and SSE up to 32. (both Nodesize and Leafsize)
- did one sponza test with up 64N and 64L. N over 48 doesnt make sense, while L just degrades linear.
(i think most results from last weeks log entry are now outdated)
- moved memory that was used as ispc output from heap to stack.
- aabbs are now saved inside the node and not in a separate vector. (i avoided it last week because it required templates to allow different branching factors)
- added padding after each value in the Structure of arrays. (this only affects nodes / leafnodes that are not full)
- it was harder than expected to include the padded memory efficiently. For aabb tests it seems to be the fastest to just do the normal computation with the padded memory (its 0). For the triangle intersection i do the following:
cif(index > leafSize)
{
surfaceNormal += p0;
surfaceNormal += p1;
surfaceNormal += p2;
continue;
}
p are the points of the triangles, and surfaceNormal the location we temporary store the correct normals. This means the memory is for sure loaded and used with minimal computational overhead. surfaceNormal is a local varying variable. It would not be comparable to do the same with an output array since no matter the number of triangles we always only have one closest hit. (only the input memory increases with leafsize)
- added step size in config for branching factor and leafsize (to test 4 8 12 16 ... for L and N)
- performance tests automatically test each L N configuration for all possible larger memory sizes. So for N8L8 we test memory sizes of mB8mL8, mB16mL8, mB8mL16, and mB16mL16. yeay now we have 4 axis...
Performance results of the new renderer for sponza. Tested with avx (8 lanes) and sse (4 lanes): Performance Analysis Result Pdf
Implemented new fast ray tracer that does not collect unnecessary data and also is more data efficient with nodes and triangles. Uses ispc for triangle intersections and aabb intersections.
- Image now is just ambient occlusion.
- Triangles consist of 3 points and no texture or normal. This leads to a slightly different result since we cannot use the stored normals. Transparency is also missing.
- good memory layout for ispc. All triangle info is in one extra array and all aabb info is in an other extra array. This allows different branching factors / leafsizes while still keeping the nodes small and without scattered memory. Exact structure of the triangle: float vector with the following order: first all point0.x of all triangles in the leaf. Then the same for y,z, then point1 and so on. After each completed leaf i pad to 32bit. The same approach is done for the aabb. I also did tests with padding after each variable. It seems to improve performance in case of N8L8, but i did not test the others. (In the case of N8L8 the blocks are already padded to 8 if the leaf / node is full)
left is new, right is old (both rendering ambient occlusion with 50 samples)
- working ISPC with visual studio build tools. It calls a batch file that calls the ispc compiler. Only compiles ispc files when the source changes or the target files are missing.
- Ispc triangle tests works. Getting the output right was the main issue. Im still not really happy since i want to get the varying information to the uniform part without creating an array for each triangle.
- improved performance by using SoA memory layout for triangle points.
- added aabb - ray test with Ispc. no issues here, coherent memory input and only minimal output (minimum distance to the aabb for each aabb where the intersection was positive). It also returns true if at least one aabb was hit.
Now instead of saving the split Tree i save the needed traversal order for every possible ray. New approach needs similar memory when optimized, with the advantage of less computations (and way less branches) during raytracing.
-
Previous: saved a binary tree that represents the hierarchy of the splits, and at what axis the split occurred. For every split it saved a tuple of 3 numbers: (Axis of split, id of the left "child", id of right "child") When there was no split the id was negative and represented the id of the child node, a positive id would represent the id of the next tuple. For each node intersection we had to traverse this binary tree to get the correct order of nodes to test. The direction of the ray decided if we go to the left or ride side of a split.
-
Now: There are 8 different possible ray directions. We can ignore 4 of those directions because they are the mirror of one of the other 4.(opposite node order). For each of those possible 4 directions we calculate the node order and save it. This means we need to save 4 numbers per split, where each number represents the child node id. This means in theory we only need 4 bits (we support a branching factor of 2 to 16) per number leading to 2 bytes per split. (currently they are just saved as uint8_t)
-
Implementation details: A binary code represents the ray direction. For an example ray of x = positive, y = negative, z = positive: each axis represents one bit. So the code would be 10. Now we just traverse the childnodes in the order saved at 010. If the leftmost digit would be 1 then we invert the first 2 bits and take the reverse order of this new code.
- fixed bug during model loading that would give objects without texture the texture with the largest id. Now they are rendered white again. (error caused by -1 comparison to size_t)
- Changed hash function for ambient occlusion rays a bit. There where some visible lines. Increased factor before hash to fix it.
- fixed hemisphere sampling. Would return (0,0,0) vector when the y part of normal was very close to 1 or -1. (i previously caught the = 1 case, but it also occurred for numbers very close to 1)
- Optimized aabb - ray intersection. The version used in the ispc raytracer example was faster than my glm version.
- Optimized triangle - ray intersection. The version used in the ispc raytracer example was faster what was in the pbrt book.
Analysis Result Pdf with updated cache graphs to use 32 byte per child
Interesting configurations:
- N2L1, N4L4,
- N3L1, N3L2, N3L4
- N5LX, N7LX
Most important results and decision reasons are in the pdf.
Rest of this log entree is what i have done this week and some random analysis thoughts (overlaps a bit with the pdf).
Now allows easy and quick management of variables to observe.
Different variable types:
- Normal variables. Examples: Primary node intersections
- Cost variables (leaf values are multiplied by leaf Cost factor and Node values by node factor). examples: cost factor, sah, epo
- Normalized Variables. Those values are already normalized to be between 0 and 1 so we dont collect the maximum value to normalize the averageTable Example: waste factor
- Variables multiplied by branching factor.
- Variables multiplied by leaf size.
- Variables that describe the loaded cache lines (currently only for nodes)
To add a new variable to observe only two strings have to be added to to the right lists.
- Added many variables -> all can be seen in the "Plots of other Values link"
- Added new line graphs to the Latex document to directly compare different branching factors and leafsizes
Nomenclature:
- Nx = Node size of x (same as branching factor of x)
- Lx = Leaf size of x
Interesting general observations:
-
Leaf size is not that important, but it seems to be better to choose even numbers. It might have to do with the scenes because those results are not all the same.
-
N3 is always better (or the same) as N2. (N2 is really bad so i often exclude it for graphs to get a more reasonable colorbar scale)
-
Sah seems to be independent of scene geometry, while the Epo reflects the additional costs of the scene geometry for the final render. This means i mostly ignore the Epo since we are not interested in scene specific optimizations. EDIT: not sure how usefull sah is because it cost comes to a large part from the leafCost, even tough the #Leaf intersections is way lower than the #Node intersections.
-
The reason for the band in some scenes is the average leaf depth.
- N2L1 and N4B4 for the standard versions
- N3L1 and N3L4 because b3 seems really beneficial
- At least one B5 because over 5 is a step in aabb intersections
- Probably one B7 since its only slightly worse than b6 in aabb intersections
- The only usable metric to choose the leaf size is the Sah and the number of primitive intersections. Both graphs look very similar. (like said above, even numbers seem better)
Summary: added computation of waste Factor, Epo, full tree Sah, and Ambient Occlusion
Most of the time was spent on implementing the End-point overlap. (according to https://users.aalto.fi/~laines9/publications/aila2013hpg_paper.pdf )
The complex part is the to get the surface area of a triangle inside an Aabb. I calculate the part of the triangle that is inside the aabb. Then i calculate the surface of the resulting (convex) polygon.
This has to be done for every triangle / node combination where the triangle is NOT inside the subtree of the node. In order to efficiently calculate it i traverse the bvh (like a raytracer) and continue to each child if the current node either added surface area to the Epo, or the triangle is part of this subtree.
First i implemented an recursive approach that was to slow to be usable. (fastest version had 45 seconds for sponza with b = 8 and l = 8).
Then i translated it to an iterative approach with queue and optimized that a bit more (mostly tried to reduce branches). The current version solves said sponza problem in about 0.5 seconds. Rungholt with the worst settings (branch = 2 and leaf = 1) takes ~20 seconds. This is usable.
Both the Sah and the Epo are calculated with a factor of 1 for triangle and leafsize. I save those values separated for leafs and nodes, so we can visualize different costs without recalculating everything.
Added ambient occlusion. The sample count is configurable in the config and the shadows can now also be disabled in the config.
For ambient occlusion i currently use the id of the pixel as hash to sample the hemisphere. For now the ambient occlusion ray has no distance limit but its configurable in the scenes (all scenes are kinda differently scaled).
The differences between a sample factor of 1 and 20 are minimal (besides ~4.8 times longer render time). The image obviously looks better, but the analysis results are basically the same. The reason for this is most likely that a normal image already consists of 2073600 rays and if every ray hits a surface also 2073600 shadow rays.
Example values from sponza branch = 4 and leaf = 4:
1 ambient occlusion sample:
shadow node intersections: 19.665
shadow waste factor: 0.719049
shadow leaf intersections: 3.43462
20 ambient occlusion samples:
shadow node intersections: 19.6472
shadow waste factor: 0.719071
shadow leaf intersections: 3.43068
And an image how it looks on the lizard guy. Normal shadows disabled but light still on.
Currently calculated like this: (with values per ray)
(leafIntersectionCount + nodeIntersectionCount - 1) / (nodeIntersectionCount * branchingFactor)
This formula seems to give the desired value. (the difference between the waste factor and the aabb intersection rate is that the waste factor assumes that every node has "full" children).
Those spots dont appear in the newest plots. The only difference is that i save the distance to already tested nodes and dont traverse them when the ray found a closer triangle.
It might have to do with an unlucky node placement?
Update: i looked into an example of rungholt branch = 10 and leaf = 13. It appears to be unlucky node placement that leads to larger structures being rendered in the older version. I think this can be seen as a worst case (or best case) difference.
Comparison image to better understand the difference: node count at depth level 1. Left is with distance comparison, right one is old version. (normalization for left is 4, for right its 5)
Depth level 2. Normalization for left is 10, for right its 13
This basically goes on on all depth levels but is harder to observe. The effect we saw on the plot was for the leaf intersections. For both the normalization is 21.
- Removed Triangles without surface before building bvh
- Added render mode that additionally stores the distance to the aabb in the render queue and later does not continue intersecting its children when the ray already found a closer triangle.
- replaced all dynamic_cast with static_cast -> small performance improvement. I have to use casts because bvh is build in a way it could support different node and primitive types. Might change that later since many things expects aabbs and triangles and it would be hard to add more types.
- added epo, sah and wastefactor to the pdf and python datamanager
Working raytracer for BVHs with many options:
-Arbitrary branching factor
-Arbitrary leafsize
-A "few" more in the config.txt
More on how to compile and run the Project is in the Readme
The most recent addition was the choosing a new axis and sorting for each Split. Now that it works correctly it seems to be mandatory for larger branching factors. (but results seem a bit odd) Left one can choose a new axis for each split, right one makes all splits along the same axis.
Analysis on results of sorting for each split: all bvh with the same leafsize have very similar or even identical leafnodes. This happens because the sah cost function doesnt change with different branching factors. As an example: there is no difference between 3 splits that create 4 children or 1 split that creates 2 children that are each split again.
Multiple scenes can now run in parallel.
Single scene with more than one branch factor / leafsize combination is also run parallel batches of 4.