-
Notifications
You must be signed in to change notification settings - Fork 171
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
BVH builder question (possible bug?) #28
Comments
@stasilo 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:
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 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
This image should be rendered when visiting 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! |
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 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! |
@stasilo A couple of things I noticed from first glance even before running the example are:
Once I get the octahedron showing up, I can better determine where the problem is. |
Haha, you're welcome! :) The model transform is specified at the top of 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 Many, many thanks! |
@stasilo 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! :-) 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. Be back soon :) |
@stasilo |
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! 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
Here's what I changed it to: `let triangleDataPadded = new Float32Array(dataTextureSize * dataTextureSize * 3);
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 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. |
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
It should in fact read:
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! |
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 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
And HOLY shit, it doesn't say 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 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 |
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, |
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
The text was updated successfully, but these errors were encountered: