BVH builder question (possible bug?)
stasilo opened this issue · 23 comments
Hi Erich!
Wonderful work and an inspiration for what can be done using webgl! If you don't mind I'd like to pick your brain a bit regarding your BVH implementation.
For the last couple of months I've been building my own ray tracer using picogl (a small helper lib for webgl2).
I've spent some time trying to implement a working BVH acceleration structure before I found your work. I've tried porting your BVH implementation to my project but when doing so I'm running into a weird bug that I've spent the last 4 weeks trying to solve, to no avail. I'm hoping maybe you have at some point run into something similar and maybe can point me in the right direction.
I started out rewriting your code to be engine-agnostic (basically using gl-matrix vectors and a few other small changes) but during the bug hunt I've regressed to copying your implementation as much as-is as possible in the hope that the bug will disappear; both the builder code and the actual stack implementation in the shader (SceneIntersect()). It has not :/ I've even regressed to using your threejs gltf model loader code. The issue still persists!
As far as I can tell there is a problem with the BVH construction as soon as the number of triangles exceeds the magic number 1025. Please see the attached screenshots.
The first shot is when the number of triangles is around 1000. The other one is when the no. of triangles is greater than 1025 (around 4k iirc). The black boxes are caused by a loop counter check which discards the fragment in the SceneIntersect() stack loop if the loop counter has exceeded 300 iterations. If the loop counter check is omitted an infinite loop usually crashes the browser. Models with a tri count below 1025 are rendered correctly (and really fast! thanks to your bvh code!).
This thing is driving me mad and I would be truly, truly grateful if you could point me in the right direction. I would gladly provide my project code if you'd like (though I completely understand if you do not have the time or energy to sift through my code).
Also, please excuse me for opening an issue in order to ask this question - I couldn't find any other way to contact you. Hope that is okay!
Best regards,
Jakob Stasilowicz
@stasilo
Hi Jakob!
I will be glad to look through your project code. What's the best way to share it with me? Do you have a repo like mine that I could clone? Or maybe you could make a public 'Gist' on GitHub to share the relevant files? I can't tell from just looking at the rendered output, although the 1025 triangle issue is a good suspect. I've tested my shader code up to a million triangles, and although it takes a long time to compile, it eventually runs. It may be a texture problem - I use three.js's DataTexture which automatically sets up a floating point 2-dimensional texture with room for 4 floats on each of the texture slots, which are RGBA channels. I changed to using a larger texture size, 4096x4096 * 4 channels RGBA which gives plenty of room, even for millions of triangles. Moving the sampler pointer around the texture is finnicky, you have to have the correct step size (1 / 4096) and the right row/col combination. Is your project also to run in WebGL? I'll take a look.
I feel your pain because there is very little information out there (even on the huge internet) for how to build BVHs step-by-step (not just some research white-paper), let alone how to make it all happen on the GPU! I was lucky enough to be able to grab the minified (uglified) shader BVH intersection code from Antimatter.js and reverse engineer it to help get me started. If it wasn't for that nudge in the right direction (both code-wise and algo-conception-wise) I probably wouldn't even have a working GPU BVH for my project!
I hope I can help!
Hi again Erich,
thanks for the quick response and offering to help! I really, really appreciate it! I agree it's really hard to find good information regarding BVH structures, especially in the context of webgl(2) :(
I've uploaded my code here: https://github.com/stasilo/raytracer-bvh-debug.
The relevant source files for this issue are:
src/index.js (webgl state, textures, model loading etc. is handled here)
src/bvh/* (model parsing, all bvh related stuff)
src/shaders/raytracer.glsl.js (the main shader)
This version is as much as possible your BVH builder and shader code with minimal changes (using threejs vectors etc.). I'm hoping I'm missing something really obvious in the sampler pointer stuff as you mentioned, or something equally trivial :)
The project is set up using webpack & npm for module handling. To build and run it just clone the repo and do npm install and then npm run start to start a watching dev server on port 8080.
I've set up the project so that the bug is triggered when you run it. I'm limiting the number of triangles manually to 1200 on line 56 in src/bvh/index.js:
let triangles = faces.slice(0, 1200)
This image should be rendered when visiting http://localhost:8080/?sampleCount=10:
As I mentioned previously all models with a tri count below 1025 seem to be rendered correctly. As the no of tris increases above 1025 the issue gets progressively worse.
Once again, many thanks for taking the time to help me out! And please let me know if you have any questions.
Jakob
Hello Jakob, thank you for sharing all the files and for the detailed info! I am downloading everything and will start trying stuff out tonight. I must admit I'm kind of a newbie to webpack and npm and the more modern web services. My development environment consists of Visual Studio Code with integrated 'live' server and that's pretty much it. I just dump everything on this repo after I get it working. I will follow your build instructions and see if I can get your project up and running on my computer. What I would like to do is when I make a change in the source code, it automatically refreshes and re-compiles. That way I can quickly try things out to see if they're working. I'm assuming you have a similar setup, even with the webpack and npm systems in play. If I run into any issues, you might need to hand-walk me through some setup on my end, but hopefully I can just get everything working quickly.
I will post back soon!
-Erich
Hi again, I tried npm install inside the terminal of Visual Studio Code after I cloned everything: that appeared to work. However when I then typed npm run start, it started to work, and then gave me the following errors and refused to compile/build. I tried reinstalling Node.js on my computer, then I restarted my computer. I downloaded GitHub desktop, cloned your repo, then opened it inside GitHub desktop. Then it gave me the option of opening the cloned project in my Visual Studio Code editor from GitHub desktop, which I use all the time and am comfortable with, so I did that. Then I did the npm stuff but I can't seem to get past that setup step. Do I need to install anything else for the SASS stuff to work? I navigated to http://localhost:8080/ but it gave me the same errors in the browser console.
As I mentioned, I don't normally use npm and modules so any help would be appreciated. :)
Hi again Erich and sorry for the trouble!
I work as a web developer, otherwise I would never have the energy to bother with the configuration hell that is webpack + npm :)
I think your particular issue can be resolved simply by deleting the node_modules directory in the project root and doing npm install again (this is a common issue when upgrading node/npm but having node_modules deps installed with the older version).
The webpack dev server started on port 8080 has hot reload functionality in the same vein the bundled VS code dev server.
Please let me know if this doesn't work, then I'll remove the sass stuff (not really necessary, I just used an old boiler plate I had laying around) and push the changes as soon as I get home from work.
Once again, thanks!
Jakob
@stasilo
Hi, thank you for the tech support! Lol. Yes that did the trick, it is now compiling and refreshing automatically when I make changes to the code inside my Visual Studio Code editor. The bunny.obj was crashing my webgl context however, so I changed it to load octahedron.obj which has a minimal set of triangles for me to do some initial testing. I can see the checkerboard ground and the sphere, but I can't see the octahedron. Where in the source files do I specify the loaded model's transform? I need to change its scale and position. Just to make sure, you are first loading the .obj model, then applying the transform to its geometry (each of its triangles), whether rotating, translating, or scaling, and then passing that final data along to the BVH builder, right? In other words, the BVH builder has to know where the model's triangles will be in final world space, not object space that is in the .obj file on disk. Just wanted to make sure you were doing it in that order.
A couple of things I noticed from first glance even before running the example are:
- you had stackLevels[24 * 4] when it only needs to be stackLevels[24]
each of those stack levels represent a binary split of the model's entire bounding box, so it's 2 to the power of stackLevels, which is roughly 16,000,000 boxes - plenty enough for even the most demanding scenes. - the hitBvhBBox function is out-of-date - I realized I had made an error on first implementation and I have updated this function on my repo a couple of months back while working with n2k3 on his GltfViewer example. I went ahead and changed your copy of that function - now it should not only work correctly for all models, it also should go a lot faster :)
- your struct for the bvh node is currently:
struct BvhNode { // [id, node0 offset, node1 offset] vec3 meta; vec3 minCoords; vec3 maxCoords; };
vs. mine, which was:
struct BoxNode { float branch_A_Index; vec3 minCorner; float branch_B_Index; vec3 maxCorner; };
I've read in various places that it's good practice to line up data in memory so that you have multiples of 4, for example 4 floats in a row. In my case - float, vec3(float, float, float) which matches the texture layout of float RGBA: float, float, float, float.... and so on. So in my layout, the texture pointer only needs to look at 2 RGBA slots (float, float, float, float - float, float, float, float) to get all the data it needs, whereas in your layout, assuming you changed it to be RGB data texture without the A - your texture pointer needs to look at 3 RGB slots, vec3, vec3, vec3 to get what it needs. There is no padding, so it has 9-floats boundaries, when the recommended is multiples of 4, so maybe something like vec3, vec3, vec3, vec3. Now I'm no expert on GPU memory, I just tried to follow common layout practice. I could be off and it doesn't matter for textures. But the fact remains that my data is slightly more packed into 2 RGBA slots than yours which is spread among 3 RGB slots. Could make a difference down the line with huge models - the less moving around that the sampler pointer has to do, the better.
Once I get the octahedron showing up, I can better determine where the problem is.
Thanks again!
Haha, you're welcome! :)
The model transform is specified at the top of getObjModelTriangleVertexData() in src/bvh/index.js and is applied before the data is passed to the BVH builder. It's a bit hacky and unclear - my plan was to clean this up when I got the BVH stuff working..... :)
I think the actual obj model parsing and translation stuff should be correct as I have managed to render a translated and scaled bunny correctly without the use of a BVH (~2000 tris, I think, damn it's slow though :)).
Regarding the stack levels and hitBvhBBox() - these are remnants of me hammering parameters and trying 10 different implementations of aabb intersection functions in despair after 4 weeks of beating my head bloody against this bug. I must have forgotten to restore the stack levels and I'm guessing I've also tried a similar implementation of the intersection test that you're describing, but finally used your function as a means to eliminate any possible bugs caused by that particular piece of code. Would love to see your version and compare it to the countless ones I've tried though! :)
Many, many thanks!
Jakob
@stasilo
Ah thanks! I will try it out. I also just updated my comment above about data layout. Didn't want you to miss that now older comment. ;)
Will be back soon!
Ah thanks! :)
I should mention that amongst the things I've tried is using your exact texture packing layout (even your exact GetBvhBox() function) and variations thereof. It didn't seem to make a difference for the issue I'm experiencing, though I have no doubt using your layout is more efficient, especially with larger models!
Sorry that the code currently doesn't contain this btw - I resetted my git working copy with that version out of pure anger during the weekend (and also because it was a mess) :)
Ok copy that! :-)
btw I totally understand your frustration with things not working - I have been in the trenches before with seemingly no way out. I code for fun (a passion hobby you could say) but I can't imagine doing this for a boss with a deadline looming over me! I don't think I would last long.
What has worked though is that I go and improve something different, in the same project (lighting for example, or materials, etc.), or even not the same project, then return later when I am patient enough to look through the code line by line with a 'new' set of eyes. I usually spot something I missed, or am willing to try something new, no matter how ridiculous, that I hadn't been willing to try before when I was feeling frustrated. Sometimes the ridiculous thing makes the bug show up repeatedly and I can squash it with my foot! Haha.
Hasn't worked every single time, but enough where I try it myself from time to time.
Be back soon :)
@stasilo
There seems to be an issue with the DataTexture creation. I tried increasing the textureSize resolution from 1024 to 2048 and it took over 30 seconds for the app to start. Next I increased it to 4096 and it crashed. This is all with the low-poly octahedron model too. Using THREE.DataTexture, I was able to create any size in my project without it skipping a beat - maybe half a second. Looking closer... I have to go to work soon, but I'll investigate more when I return tonight. :)
Now at least able to create 2048 and 4096 size data textures. All models display except for bunny.obj which still crashes my browser. Will keep looking in the morning
Hi again Erich!
what was the cause of the texture size issue? The first thought in my mind was maybe it's due to the extensive console.dir logging printing out triangle and bvh data, but I'm not sure.
Strange that the bunny model causes issues on your system. I've rendered that particular model without crashes on both chrome and firefox running on both win and mac os without problems (well except for the bug :))
Will check back and write a more extensive answer when I get home from work! :)
Hi @stasilo
The texture issue I think was caused by the way the array was setup. Here's how it was originally:
let bvhDataPadded = [ ...bvhData, ...Array(dataTextureSize*dataTextureSize*3 - bvhData.length) .fill(0) ]; let triangleDataPadded = [ ...triangleData, ...Array(dataTextureSize*dataTextureSize*3 - triangleData.length) .fill(0) ]; let triangleTexture = app.createTexture2D(new Float32Array(triangleDataPadded), dataTextureSize, dataTextureSize,
Here's what I changed it to:
`let triangleDataPadded = new Float32Array(dataTextureSize * dataTextureSize * 3);
let bvhDataPadded = new Float32Array(dataTextureSize * dataTextureSize * 3);
for (let n = 0; n < triangleData.length; n++) {
triangleDataPadded[n] = triangleData[n];
}
for (let n = 0; n < bvhData.length; n++) {
bvhDataPadded[n] = bvhData[n];
}
let triangleTexture = app.createTexture2D(triangleDataPadded, dataTextureSize, dataTextureSize, {...`
The name-suffix 'padded' doesn't really apply anymore I guess, but this seems to resolve the issue, at least on my system. Before, I couldn't bump the texture size up without it stalling. I must admit I don't understand what your code was doing before with the '...' before bvhData in the declaration of bvhDataPadded. I'm not familiar with that code syntax. I'm also unsure why just passing the float32 array directly to the createTexture2D function works smoother on my system.
The Bunny not rendering is definitely related to the bug, I'm just not sure how yet. I have a couple of more things I thought of trying, so I'll let you know if anything pans out. Talk to you soon! :)
Hi again Erich!
The arrow syntax is the new es6 spread operator and here means basically spread out the contents of the arrays into a new flattened 1d array. So maybe the issue here was related to the fact that my code creates 4 huge arrays in total whereas your version only uses 2? ("I'll optimize that later" :)) But not sure either!
When you say the other models display do you mean they all render without any issues!? :)
Btw, regarding work, it started as a passion/hobby for me as well, and I've worked briefly as a journalist and as a teacher before starting programming professionally, but that was probably the best decision I've ever made! :) Would probably not want to do graphics coding professionally though, as you say, way too stressful when deadlines need to be met. But I think web development has a good fun/hard/new things to learn/stress ratio, especially if you do both back-end and front-end stuff! :)
@stasilo
Ah ok I think I understand better the -> arrow syntax, but does that mean that the ... (three dots in a row) essentially says "make a new array"? I suppose I can watch a tutorial on YouTube to brush up on the new ES6 stuff.
Yes the other models render ok, but not the skull.obj - I can't get that one to show up without crashing the context also. Speaking of models, I have narrowed the problem down I think:
I tried a lot of different scenarios and ideas, some of them provided a little more efficiency, some did not make any difference and look the same so far as rendered output is concerned. For instance I changed the bvhHitTriangle and bvhHitBox functions to perform like my original functions and return just a float t value, the distance to intersection, if any. I optimized those a little to be just pure distance finders because they are hot functions inside the bvh loop (for instance, you don't really need the normal of the bvh box nodes and the associated branching if statements to find that info).
The bad news is the bug persists, even with all these avenues I went down. However the good news is that I spotted a discrepancy this evening that could be the key to solving the problem. I loaded the bunny model in my three.js pathtracing framework and in your framework at the same time and I set the model transform to be exactly the same. I then console.logged the resulting triangle data array and the aabb array (the ones that are passed through to the data textures on the GPU) and found that not only do they differ, there are different numbers of total triangles reported! Same model, same dimensions, same bvh builder (I made sure line by line), same algos. So somewhere along the way, the data is getting mangled in your system, and when the resulting bvh is off, it stalls and crashes probably because it has some degenerate box nodes and triangles that lead to endless searches which the GPU cannot resolve. The triangle data starts out ok, both are similar to the 10th decimal place precision, but by the 20th or so triangle, they start to differ greatly, and they never converge after that. What I suspect is that whereas I use Three.js' built-in OBJLoader, which has been worked on for years by various contributors, gets all the data correctly (vertices can be indexed, re-used to save space, or not, in the .obj file, and polys can have more than 3 vertices, all sorts of nasty corner cases), maybe the loader that you're using is not as robust and possibly gives incorrect triangle data. I'm not sure how to test out this theory though, because I know you don't want to be tied to three.js, but maybe if we can somehow use that loader or another more robust one out there on npm, I think the problem might magically be resolved.
I'll keep investigating but I think it's definitely something worth looking into.
Have a good night! :)
Hi again Erich!
Very interesting! As you say, the three obj loader is probably light years ahead of whatever I'm using, and very "battle tested", still though, the diff is weird, especially since I have successfully rendered the bunny using the same code without a BVH struct:
And unfortunately I did experience the same bug when using your model loader code (which uses the three gltf loader) to render the duck model (the original screenshots I posted in this thread)!? This just keeps getting weirder and weirder :)
But maybe the issue is caused by a combination of weird things, out of which you now have solved some? How is the hand model rendered on your side? This is what happens when I try to render it:
And once again, thank you so much for helping me out! If you ever visit Sweden/Stockholm I owe you, at least, a beer :)
@stasilo
Wow, that 1st image is a very pretty rendering! Man I thought I had figured out the issue until you mentioned that the same thing happened with the gltf loader! There are still 2 possibilities where I noticed some discrepancies/suspects:
In the buildBvh(triangleData) function when you do the final loop:
`let flatBvh = [];
for (let n = 0; n < buildNodes.length; n++) {
flatBvh[9 * n + 0] = -1; // padding
flatBvh[9 * n + 1] = buildNodes[n].idRightChild;
flatBvh[9 * n + 2] = buildNodes[n].idLeftChild;
flatBvh[9 * n + 3] = buildNodes[n].minCorner.x;
flatBvh[9 * n + 4] = buildNodes[n].minCorner.y;
flatBvh[9 * n + 5] = buildNodes[n].minCorner.z;
flatBvh[9 * n + 6] = buildNodes[n].maxCorner.x;
flatBvh[9 * n + 7] = buildNodes[n].maxCorner.y;
flatBvh[9 * n + 8] = buildNodes[n].maxCorner.z;
}`
It should in fact read:
`let flatBvh = [];
for (let n = 0; n < buildNodes.length; n++) {
flatBvh[9 * n + 0] = -1; // padding
flatBvh[9 * n + 1] = buildNodes[n].idLeftChild;
flatBvh[9 * n + 2] = buildNodes[n].idRightChild;
flatBvh[9 * n + 3] = buildNodes[n].minCorner.x;
flatBvh[9 * n + 4] = buildNodes[n].minCorner.y;
flatBvh[9 * n + 5] = buildNodes[n].minCorner.z;
flatBvh[9 * n + 6] = buildNodes[n].maxCorner.x;
flatBvh[9 * n + 7] = buildNodes[n].maxCorner.y;
flatBvh[9 * n + 8] = buildNodes[n].maxCorner.z;
}`
The leftChild and rightChild were mixed up, which makes a big difference in the tight hitWorld function with bvh inside that function in the shader later. Could you try things with that small change and see if there's any difference?
Lastly, inside the the same bvh/index.js file, in the function getObjModelTriangleVertexData(mesh), starting with the 'let vertices = mesh.vertices' part, and going all the way to 'return triangles', I'm not sure about what the code is doing, and more importantly if it is in fact doing exactly what you're intending it to do with all the corner cases in obj/gltf files. I would assume that any ObjLoader or gltfLoader you could find on the internet and use in your project would, if they were battle-tested, be able to correctly spit out just a list of triangles so you don't have to have that code in there and don't have to worry about all that. So something might be getting changed from the time you use your chosen loader, to the triangle array after it passes through those 50 lines of code you have in there. That must be where things are changing. I can't think of any other way that if we use the same model, same transform, same gltf loader, that the triangle data and resulting bvh boxes would differ that much.
Hopefully one of those things will turn out to be the issue.
I don't see the hand.obj in your repo anywhere, could you maybe upload it so I can get it too? Then I'll let you know what happens when I try rendering it. Thanks!
Yes if my wife and I ever travel to Sweden, I will look you up! Would love to chat :)
Hi again Erich and sorry for the late response!
I've uploaded the hand model and a few others to the repo (I accidentally placed models in the dist dir which is ignored by git... :))
Regarding idLeftChild and idRightChild, no triangles are rendered when I switch them; maybe you changed some corresponding code in the shader on your side?
If you don't mind, could you do a pull request on my repo with your changes? I will try switching to a different loader that handles indexing and branch off of your code. I think it's weird however that the bunny is rendered without a bvh if there's an error in how the triangles are constructed from the obj model data? I'm starting to think maybe there's a bug in how picogl constructs large data textures, or something in that vein. Maybe I will just rewrite everything from scratch, starting from triangle and bvh handling. I'm starting to think that's the only solution :/
@stasilo
Hi Jakob! Yes I forgot that I had updated the shader to reflect the changes with the rightChild/leftChild - sorry about that! Yes I'll make a pull request later tonight so we can be on the same page code-wise. :)
It could be how picogl creates data textures - that is a possibility because I haven't worked with that library before. Although it might be in that step (those 50 or so lines of code that I pointed out previously) that could be saving the .obj vertex data in a different manner than my bvh builder expects.
I'll do the PR first and we'll see what can be done from there. :)
Hi again Erich!
Ok, so I rewrote the model loader code once again using the threejs gltf model loader - but to no avail, still the same bug.
So, I started digging into the picogl code base and discovered a .data() function to update the bound texture data, and some other stuff, which I started messing around with. When I did this I received an webgl state error message saying something about RGBA16F, which struck me as odd as I was sure I had set the internal format to RGBA32F. So, I checked the relevant code:
let bvhDataTexture = app.createTexture2D(bvhDataPadded, dataTextureSize, dataTextureSize, {
type: gl.FLOAT,
interalFormat: gl.RGB32F,
format: gl.RGB,
generateMipmaps: false,
minFilter: gl.NEAREST,
magFilter: gl.NEAREST,
wrapS: gl.CLAMP_TO_EDGE,
wrapT: gl.CLAMP_TO_EDGE,
flipY: false
});
And HOLY shit, it doesn't say internalFormat: but interalFormat:!!!! When I added this single little extra "n" and checked my reloaded browser:
I'm 50% happy as hell and 50% devastated on account of how much time a single "n" has cost me the last two months... Unbelievable... :)
So sorry for wasting your time with this and a HUGE thanks for your help, I don't think I would've solved this without it (would probably have given up :))
@stasilo
LOL! (I did actually laugh out loud when I read your post above!) I guess that's one of the blessings/curses of JavaScript, you can get away with some small errors (unlike the C language for example), but that means sometimes it will silently error and nobody will have any idea of what went wrong! Ha
I'm so glad that you found the source of the bug - it was starting to drive me crazy too! I was about to dive into those 50 or so lines of code where you make the triangle and bvh arrays because I was 'convinced' that's where the problem had to be! After that I was going to download picogl myself, read the docs, and look line by line at the way they set up data textures and textures in general for WebGL2. Good to know it wasn't their fault, or the .obj loader coder's fault - ha ha.
No problem or worries about time spent hunting for the bug. I always learn something new or go down a path that is a little out of my normal comfort zone - so nothing is time wasted imho. Along the way I learned a couple of new things about ES6 from the way you set up your system - I might use some of those newer features down the line. Also, I learned how to use NPM and modules and my terminal inside of VSCode, lol! (well, just scratched the surface, but still ;) ).
Good catch! Best of luck to you on your project. Oh btw I recently found a GitHub user with a couple of path tracing repos, one is traditional like you have, and the other is voxel-based, like Minecraft, but path traced. He, like you, is trying to do things framework-engine-agnostic, and actually does everything from scratch in WebGL2 (no webgl libs), which sounds like a lot of work, but actually it isn't that bad or long at all - his source files are pretty straightforward. I was thinking you might enjoy seeing how he set up some of his systems without using frameworks/rendering libraries. The only lib he uses is glmatrix like you have. Here's the links: path tracer and voxel path tracer.
If I ever visit Sweden, I will give you call and we can chat over drinks about the infamous 'n'! :-D
Take care,
-Erich
I coded quite a bit of c and java in my teens and dynamic typing is what I love about js, the productivity gain outweighs the issues, generally I think, assuming there are no missing n's ;D Actually thinking about trying out https://flow.org/ for my project - not as intrusive as setting up typescript, seems like a nice middle ground. Not sure it would have caught this bug though, I'll have to dig through the docs :)
Thank you and the best of luck to you too! I'll check back and see what you come up with, so far it's really impressive :) And thanks for the links! I've been looking for a clean voxel path tracer implementation, seems like impressive realtime voxel demos are all over twitter lately... :)
Please do, would love to chat! You can reach me at {firstname}.{lastname} at gmail.com, or @kewba on twitter :) And once again, thanks for all the help!
All the best,
Jakob Stasilowicz