If you enjoyed the video, then be sure to support the channel by taking a look at CodeCrafters: app.codecrafters.io/join?via=DouglasDwyer I also want to mention that there's another way of doing collision solving - called constraint-based solving - that solves all contacts at once, rather than going through them iteratively. I want to try implementing a constraint-based solver in the future, since they are typically to be more stable (and can better support things like stacks of rigid bodies). But the iterative solver was a good, instructive step forward from my previous engine (which had no solver at all)!
I know you're probably joking, but that would actually be wild if possible. I've also noticed that most voxel games don't really have good animation, if any animation period.
it would be cool if voxel objects had internal stresses, so you can build a bridge, and if its not strong enough the bridge will break if a car drives over it.
6:11 It may be faster to store the object in a quad tree where you first start at the lowest collision resolution then gradually increase the resolution. This way you can only check collision between two voxels then if they are colliding you check collision between two eight voxel objects then check collision between two sixty four voxel objects gradually increasing the check resolution in this manner allows you to check far fewer voxels in total because you can use previous checks to disqualify voxels in the next check, it is also possible that you could combine this with the edges/corner system.
Doing something in 2D is a real-life cheat code usually. I am developing a voxel-based slicer for 3D printing that fits the layer shape to the model via a BFS run in the voxel space. The logic is really complex. The steps are simple but the influence of each line gets ambiguous really fast, but every step of it can be represented in 2D, since we don't really want parts that overlap in XY in the same layer anyway. My workflow has become, make a demo in Unity using every debug feature I can to make things more clear and then just add back the extra coordinate. Using a game engine (or your own visualization) to show debug info while developing something like this makes it so much easier, I do recommend that everyone does this when working on something complex in 3D.
Oh my gosh, how did you make this so amazing? The performance is incredible, and the physics calculations are top-notch! Your voxel engine is way ahead of mine. Great job!
You're doing an amazing job! I'm glad to be able to see your progression and I'm always in awe of what you're able to do. Keep up the good work and I'm excited to see where you go from here!
I'm loving where this is going, but I have one thing to suggest. In the case of trees falling down, the weight of the trunk will easily cause branches that land on the ground first to either break off, or move out of the way as the trunk heads to ground, but your trees just kind of float on the ground as if the branches and leaves are stronger than the trunk. I hope there's a way to improve upon this visual. Look forward to the next episode, even though I can't code a simple thing myself.
This is so cool, wonder if you plan to push this even further some time in future and add destruction under own weight (so that building can't stand on one corner pillar).
Yes, indeed, I'm aware, don't know many games that have this, example could be instruments of destruction, main reason I'm asking is I'm interested if you'd like to do it, or at least try :D
This is really neat. I was going to go with the approach of using marching cubes or something similar to make a mesh for collision for my voxel-ish engine. This is awesome because it keeps everything in the voxel domain from start to finish.
2:48 There are many ways to do collision detection, the easiest is just to check if there intersecting, however for the most accuracy you will want to detect the exact time of collision this is harder.
I would love to see a particle system added, might be useful for something like generating random height grass on continuous areas of grass. At least that is my first idea of what it could used for beyond the obvious smoke particles. Having grass that varies in height a lot makes scenes a lot more interesting visually for not much complexity on the user's end.
The very idea that my undercloced R9 390 would run Path Tracing in real time at 1600x900 resolution is Jawdropping. But it is a reality - you are mad man, so much respect to you! i am so shocked, i can't...
Seeing you chop down that tree made me think of something cool. What if you added mass to the voxels that varies depending on its type (kind of like Teardown's materials)? The wood voxels of that tree could have much higher mass values, allowing them to disperse more inertia, giving them a sense of weight (player killed if a heavy tree fell on them, or they fall slower as grav. accel. has to apply more force)
2:56 Not only is it the first step, but it is also the most important step, it does not matter how realistic the physics mathematics are performed, if the collision point cannot be found accurately then the physics engine will be broken.
One thing I want to see in a voxel physics engine is to have it implement the rotation-by-three-shears method for rotation within a cardinal plane (so every source voxel is preserved, there's no resampling averaging things) and have it translate objects by world grid increments. It would look very different but there might be some upsides to doing physics in such a homogenous and discrete world. :)
Have you looked at GJK/EPA? (Casey Muratori has a good video explaining GJK, both in his "Papers I Have Loved" talk, and his old video "Implementing GJK" where the former talks about it in more general terms, and the latter goes more into the details of how it works. Also, Kuju has a good video visualizing and explaining GJK. GJK is the base collision detection, EPA figures out how much it is overlapping, etc.) With GJK you may end up having to test less verticies/edges, as 1. you just check the verticies and 2. you use some clever tricks to figure out which ones to check. And if you end up doing this, you could gather the edge verticies to make a collision mesh, and just do the GJK on those, rather than directly on each voxel. Though you may have to subdivide the mesh if it isn't convex, as it has to be convex to work.
here's an idea if you throw something hard enought on the terrain or another object it could damage it , i know it's not simple to implement but it could be very funny. Love the video I hope to see more ^^
Corners need to be tested against any voxels on the surface with which they could possibly overlap. In practice, this means testing against the 8 voxel positions in the other object that surround a given voxel.
@@DouglasDwyer thanks. I was wondering how your engine would handle a situation like the two L shaped broken crates that the Teardown Twich Talk used as an example of a lot of corner contacts.
@@DouglasDwyer Yeah take your time man! This is already super impressive, and this probably wouldn't even be that necessary, just a nice touch that would be fun to play around with, and a fun problem to solve.
The 2D demo is available at github.com/DouglasDwyer/rigid_pixels There are some glitches remaining in it that I fixed in the 3D version, but you can definitely check it out.
amazing work as always Douglas! i have been wondering if you are planning on adding voxel density and such properties? it would be cool if leafs are easier to pass through or when a tree falls they wouldn't be able to keep the log up, looking forward to your response! keep up the great work.
I want to add object fracturing (sort of like Teardown) so that when high-speed collisions occur, the objects crumple or collapse. This should help leaves and branches break apart when the tree falls. I also want to make different types of voxels with varying friction/bounciness.
Simulating soft body voxels i think is usually hardware intensive. Minute papers had a video about a paper where people trained AI to handle the physics and made it an order of magnitude faster while being a very convincing fake simulation.
For me this project in the start was simply Oh another minecraft game. Then it became this wow this looks really good. I have just started learning graphics and C - for CV, then rust :) - and lmao was I wrong. This is so hard, this is so complicated. Hands down for you, not many people can do what you are doing. How old were you when you started this project? When did you start coding? A quick rundown of your path to this project would be highly praised I think.
I started working on this project in November 2021. I've been coding since probably about 2014. Maybe in the future I can do a video where I review the history of the project and my coding experience!
Hm, the interesting thing about what you're doing is that friction can be an emergent property, this is good because realistically friction isn't a real thing. You can simply have the interactions between small voxel surfaces on the objects cause it to have friction. Though, I recommend making the voxels use spheres for collision even though they're cubes, both because it can be more performant, and also because it will be softer and less jagged.
May I recommend attempting to go without ambient occlusion? AO is just an inaccurate representation of global illumination shadows. If you don't have GI shadows it's whatever, but if you do, you could start with making things in shadows pitch black before GI.
Thanks for the feedback. Can you describe what you mean by "making things in shadows pitch black before GI?" Are you just suggesting that the amount of ambient light be set to 0.0, so that the inside of buildings is completely pitch-black? I describe my lighting system in Devlog #19, but it uses ray marched direct shadows and then path traced shadows for AO/emissive voxels. This system is close to full GI, but it lacks multi-bounce.
Ya pretty much, anything in shadow doesn't get light from what's making the shadow, it wouldn't work well without multi bounce though... Perhaps one method for multibounce is to make everything emit light according to its brightness, with the material as a multiplier, and doing multiple passes. It would be self feeding but it would probably plateau.
I've been wondering is this more so to create a general purpose voxel engine, or you are going to make a game out of this? If you're making a game, what were thinking of doing? Shooter? Sandbox (Like Garry's Mod?) Or like a survival game? Also this is really cool. It's still an awesome project to watch!
That's a great question. My goal is to create a general purpose engine that allows people to create their own games and experiences through modding. The plan is to finish the core engine, and then build a small example game (I've been thinking a shooter) which can be used both as promotion for the engine and also an example for other games.
That's a great question. Indeed, I use a version of flood-fill/depth first search to find groups of voxels that aren't touching anything else. (The flood-fill algorithm is highly optimized to work with a custom binary voxel data structure.)
Great job! But I don't understand something. The assumption that when two objects collide, their edges will interact is understandable. But how does this help when calculating collisions with the global mesh, i.e. the terrain? After all, there are too many edges there, to check them all you will have to spend too many resources
I glossed over the details, but I use a 64-tree data structure (like an octree but subdivided by 4 on each level). I exploit the tree hierarchy during collision detection so that I am only checking areas where both objects have overlapping voxels.
Uhhh….Douglas, as you know I’ve been following you pretty much from the beginning, but I’m afraid I have to disagree with you one point: Your physics engine last year was **very** accurate. I am forever chopping trees down, only for them to float away in the sky. It’s a real problem. 😑 P.s. great work. It looks fantastic!
I found your videos as I was searching for optimizations to improve my own simple voxel game, and I am heavily thinking about switching over to ray marching. One thing I have always wondered about in your videos is how you are able to render objects not aligned to the grid, since your ray marching algorithms with their octrees and such seem like they should just work on grid aligned voxels. Also, I wonder how shadows work with these objects.
One thing i've always wanted to see is a 3d voxel game that locks everything to the world grid. So instead of smoothly moving cubes around, it would snap its position much like a 2d pixel art game. Same thing with decreases FPS anime style games. On top of making the animations low fps, also make the character movement low fps. I wonder what it would look like. Sorry, my comment isnt much about this video lol
I understand your suggestion fully. That said, I am not aware of any algorithm that can re-voxelize objects at arbitrary rotations while being fast enough to run in real time. In addition, I personally feel that re-voxelizing objects would look confusing and make it harder for users to predict an object's behavior. As such, I'm not planning to go for this route - but it's a creative suggestion :)
What exactly is the gameplay loop of this game you’re working on? I love the look of the medieval section you showed with the tree, I feel something like that could fill the hole left by Medieval Engineers if made right.
I am focusing on core engine technology right now - I am more of an engine programmer than a game designer, I confess. My ultimate goal is that people should be able to create their own games by writing mods for the engine. I was thinking of building a small first-person shooter game as a proof of concept.
That's a great question! I haven't had a chance to compare with Teardown yet. The performance of the connected component labeler (the code for finding disconnected parts of the terrain and turning them into rigid bodies) ended up being really fast. The actual rigid body simulation is fast too - but I have found one case where the collision detector visibly lags. This happens when I spawn ~100 small particle entities on top of a tree and then chop the tree down. It slows down because the system is doing many (between 15 to 30) collision iterations per tick for fast-moving objects, so that voxels don't clip through each other. I hope to optimize this case by making the simulation more stable, reducing the amount of iterations required, and multithreading the collision detector.
This is really cool, but the main thing I notice when playing the demo, is that once an object becomes it's own separate Rigidbody, you can no longer interact it, which is super weird feeling and jarring.
That's a good point. I'm not sure exactly what the gameplay will end up being like, but allowing for further destruction or building on separate rigid bodies would be good to have.
@@stephenwhite506 The moment of inertia is calculated by definition with a couple optimizations. From a high-level perspective, I calculate the inertia tensor for a single unit box. Then, I iterate over all voxels in the volume and sum the inertia tensors for every voxel. The inertia tensors are transformed using the parallel axis theorem and summed to create one final inertia tensor for the volume. In practice, it's a bit more complicated than that. For performance, I generate a 65536-entry lookup table containing the inertia tensor for every possible arrangement of 4x4 voxels. When calculating inertia, I iterate over my voxel data structure. I use the lookup table to get the inertia tensor for 4x4 voxels at a time, and sum that up (with the parallel axis theorem) for all relevant regions of the voxel volume. This process is also accelerated by my use of a hierarchical 64-tree for the voxel representation.
I use a "connected component labeling" algorithm (you can look this up on Wikipedia). The goal is to find isolated groups of voxels that are surrounded by nothing but air. I do this by running depth-first searches after the terrain is destroyed. If a depth-first search terminates without finding a valid path to a point 256 voxels away, then all voxels hit by the depth-first search are copied into a separate object. The depth-first searches are accelerated using binary bitmasks to search 64 voxels at a time.
@@DouglasDwyer wow, this entire project is very impressive! That's an interesting technique you described. how large can you go before performance becomes an issue?
Thanks for trying out the demo! As stated at the end of the video, the demo only works in Chrome, Edge, or Opera. Once Firefox releases support for WebGPU, it will work in Firefox too.
so why not first check a full object bounding volume collision, then do the accurate voxel collision detection, ie high level ray/collision culling first, you have much less stuff to test mutual collisions, and you already have separate object entities defined. in the engine.
Yep, I already do this! I glossed over the details, but there are broadphase and AABB checks. In addition, the voxel-voxel collision detection uses a sparse voxel tree structure to find nearby voxels. There's not really much "search" involved in finding voxels to collide.
Exxelent video as always. Is it possible to add a bit of reflection to objects to make them less flat? For example, a blue object should colour its nearest surrounding a little blue. That will make it looking a lot better!
Voxels take a lot to simulate on the smaller scale with on-the-market gaming computers... but what if there were some sort of arcade machine made specially to run voxels?
Hi, thanks for making the video! I was wondering in 2d do you only ever have to check corners with all other voxels? And do you do continuous collision detection, I saw it was mentioned in the Teardown talk but Denis didn't expand on it. Just checking if you knew more about it?
Really awesome question. There were three reasons for this: 1. I like doing game engine development, so pulling in another physics engine would be sort of "cheating" - I wouldn't be building my own engine anymore. Not that there's anything wrong with third-party engines - they're great - but it's more entertaining and satisfying to do it myself. 2. Avoiding excessive complexity and dependencies. By writing my own physics engine, I don't need to pull any big libraries into my project or figure out how to make them compile cross-platform. Further, if the physics ends up being buggy or I need to optimize/multithread, it's easy do so, because I understand the whole thing. 3. Voxels require custom code for efficiency anyway. This is the real reason - the tipping point - that made me code things from scratch. Engines like Bullet or PhysX are built to detect collisions between simple shapes (boxes, capsules, triangle meshes). They are not designed for collision detection between large voxel volumes, and it would be difficult to leverage the voxel data itself when using them. By writing a custom engine, it's easy to write collision detection routines against my own voxel data structures. That being said, I WOULD consider trying a third-party collision solver, if I ever wanted to try anything like a constraint-based physics solver.
@@DouglasDwyer Interesting, thanks for the detailed reply. I implemented Bullet in my voxel engine using compound shapes for strips of voxels but performance was not great and I had some other issues, so I removed it. I'm looking at ODE now, since that allows you to use your own collision detection which can be more optimised for voxels. I'm also considering PhysX since the documentation says "The purpose of the Custom Geometry feature is to allow the creation of application specific collision geometries (e.g. a voxel map)"
@@Adrian-ld4oz right, custom geometry is basically required if you want good performance. It's definitely possible to do, but it can be harder to debug and fix things when they go wrong.
That's a great question. Indeed, I use a version of flood-fill/depth first search to find groups of voxels that aren't touching anything else. (The flood-fill algorithm is highly optimized to work with a custom binary voxel data structure.)
@@DouglasDwyer thanks for the response. do you run this every time there is a change to the voxel occupancy bitmask thing? and how do you choose which voxel to use as the seed for the flood fill algo?
@@smangalang Yes, the algorithm is re-run for all user edits. Regarding a seed, the flood-fill algorithm involves multiple searches, so it can categorize every single connected component within the edited region. As such, the flood-fill algorithm is repeatedly run using a new voxel as the seed until all voxels in the edited region have been detected.
I understand why it's like that, but still, "real" rotating and moving in the voxel world wouldn't involve rotation of voxels themselves (just like how pixels don't rotate and move on a 2D screen when 2D objects are rotated and moved).
@@frozein nothing that complicated! I divide the world into chunks, and each chunk has an associated list of objects each frame. When ray marching, I loop over the object list for each chunk that is hit. I ray march any objects intersected by the ray before moving on. It's simple, but performs surprisingly well. My GTX 1660 can handle ~100 objects in a chunk before the frame rate drops below 60 FPS (this is with the path traced lighting turned on). For fewer, relatively big objects it's a great system!
Very cool! I was just wondering if you happened to make use of the Parry or Rapier crates when implementing this, and if so, how did that work out for you?
@@robinmattheussen2395 nope! While off-the-shelf physics engines can be handy, they're not that useful for large-scale voxel engines since for performance all of the collision detection needs to be custom anyway. As such, I can't comment on those crates :)
Would you ever consider making it so that voxel physics objects "fuse" back into the global octree after remaining motionless for a certain amount of time?
You dont need to solve for the velocity as far as I am aware. You can use the velocity verlet algorithm to generate the velocities every frame from the positions. This is what many researchers use in e.g. molecule simulations. Maybe that could speed up your system? Or are you using that already?
I will have to try the Verlet algorithm, but my worry is that it wouldn't work very well for velocity changes imposed by hard constraints or collisions. At least in the current version of my engine, velocity is used to change position and then position is further adjusted by the collision solver. I worry that those auxiliary adjustments could mess up the Verlet algorithm.
@@DouglasDwyer I think the velocity verlet algorithm (which is different from the verlet algorithm as far as i know) might actually work better than you think, as the velocity is computed from the position changes and NOT STORED. So the collision solver only solves for the positions and doesnt care for the velocities. Idk how your implementation works, maybe it wont work after all. Here is a video that helped me to understand the algorithm a bit better: th-cam.com/video/lS_qeBy3aQI/w-d-xo.htmlsi=dtd5SLFWN996xgZd
I have a somewhat silly question: If, rather than translating the rotation of voxel objects as if they were normal 3d models, we instead preserve the voxel alignments perfectly right angle to the terrain, would that help with performance of collision detection? And even lighting calculations? Like, don't rotate voxels, when rotating the object? It's difficult to put into words, and English is not my main, but what I mean is... to create a world of voxels in a voxel-field, ie, object edges "voxallate" when rotated instead of preserving their perfect line. In a way, object edges change "shape" when they are rotated and become voxellated to fit into the voxel grid.
I understand your suggestion fully. That said, I am not aware of any algorithm that can re-voxelize objects at arbitrary rotations while being fast enough to run in real time. In addition, I personally feel that re-voxelizing objects would look confusing and make it harder for users to predict an object's behavior. As such, I'm not planning to go for this route - but it's a creative suggestion :)
@@DouglasDwyer Thanks for the reply. For me, when I see a normally rotated object in a voxel world, it's always an immersion breaker. I expect voxelization instinctively, like what happens at a low-res 2d environment. Maybe that's because I'm old and I have internalized this behaviour since my childhood days with my c64. And perhaps, it might become a ilttle bit noisy at the edges if what I imagine is implemented. That being said... I think it might be achieved at a shader level, just for visuals.
I think Tooley's work is absolutely breathtaking! It's amazing what he has managed to achieve with Unreal Engine. I will definitely be trying Lay of the Land when it comes out.
Good point - I would like to add object fracturing (sort of like Teardown) so that high-speed impacts cause voxels to break into smaller parts. This should make the tree branches break off as the object falls. I don't have any plans for other sorts of deformation, though. That's a bit hard to do with a single, fixed voxel grid :)
I think Finite Element Analysis is mainly useful for modeling differential equations, but there's not really a differential equation to solve in this case.
@@DouglasDwyer finite element method simulation of 3d deformable solids / it's used to simulate plasticity and stuff. I suggest reading computer science paper "Real-Time Deformation and Fracture in a Game Environment" by Parker
One, small, problem I noticed... while this looks amazing, the voxels are being rotated off axis with their own world each. What if instead you rotated their points but still aligned all voxels to global grid axes positioning each voxel to global grid still?
If you enjoyed the video, then be sure to support the channel by taking a look at CodeCrafters: app.codecrafters.io/join?via=DouglasDwyer
I also want to mention that there's another way of doing collision solving - called constraint-based solving - that solves all contacts at once, rather than going through them iteratively. I want to try implementing a constraint-based solver in the future, since they are typically to be more stable (and can better support things like stacks of rigid bodies). But the iterative solver was a good, instructive step forward from my previous engine (which had no solver at all)!
can't wait for "Coding soft body physics for voxels"
Kirby super! I didnt expect youd be on a voxel video
@@quickestawab1 oh? where do you know me from?
I know you're probably joking, but that would actually be wild if possible.
I've also noticed that most voxel games don't really have good animation, if any animation period.
looking forward to the soft body dynamics next!
it would be cool if voxel objects had internal stresses, so you can build a bridge, and if its not strong enough the bridge will break if a car drives over it.
Thats a lot of comutation and why every realte game has to break it dpwn to large chunks.
6:11 It may be faster to store the object in a quad tree where you first start at the lowest collision resolution then gradually increase the resolution. This way you can only check collision between two voxels then if they are colliding you check collision between two eight voxel objects then check collision between two sixty four voxel objects gradually increasing the check resolution in this manner allows you to check far fewer voxels in total because you can use previous checks to disqualify voxels in the next check, it is also possible that you could combine this with the edges/corner system.
Doing something in 2D is a real-life cheat code usually. I am developing a voxel-based slicer for 3D printing that fits the layer shape to the model via a BFS run in the voxel space. The logic is really complex. The steps are simple but the influence of each line gets ambiguous really fast, but every step of it can be represented in 2D, since we don't really want parts that overlap in XY in the same layer anyway. My workflow has become, make a demo in Unity using every debug feature I can to make things more clear and then just add back the extra coordinate. Using a game engine (or your own visualization) to show debug info while developing something like this makes it so much easier, I do recommend that everyone does this when working on something complex in 3D.
Yes - I love Unity too, it is an awesome tool for that kind of thing.
this is amazing. and the fact that this can run in a browser is even more impressive!!!
Oh my gosh, how did you make this so amazing? The performance is incredible, and the physics calculations are top-notch! Your voxel engine is way ahead of mine. Great job!
0:11 that donut looks edible too(and editable)
You're doing an amazing job! I'm glad to be able to see your progression and I'm always in awe of what you're able to do. Keep up the good work and I'm excited to see where you go from here!
Thanks, I'm excited to see where things go as well!
absolutely goated
Agreed.
Hella impressive, you're making crazy progress!
I'm loving where this is going, but I have one thing to suggest. In the case of trees falling down, the weight of the trunk will easily cause branches that land on the ground first to either break off, or move out of the way as the trunk heads to ground, but your trees just kind of float on the ground as if the branches and leaves are stronger than the trunk.
I hope there's a way to improve upon this visual.
Look forward to the next episode, even though I can't code a simple thing myself.
This looks fantastic! I loved hearing about how you developed the physics for the engine.
this engine is going to contain more features than most full fledged voxel games do, nice job
7:45 Very nice, it would seem my advice was already in use!
This is so cool, wonder if you plan to push this even further some time in future and add destruction under own weight (so that building can't stand on one corner pillar).
That's a great idea, although it sounds challenging to implement :)
Yes, indeed, I'm aware, don't know many games that have this, example could be instruments of destruction, main reason I'm asking is I'm interested if you'd like to do it, or at least try :D
@@sgmvideos5175 I think Teardown can do this. Not in the base game, but there is a mod called "structural inegrity" or something.
This is really neat. I was going to go with the approach of using marching cubes or something similar to make a mesh for collision for my voxel-ish engine. This is awesome because it keeps everything in the voxel domain from start to finish.
Great Stuff as always Douglas! Keep it up!
Thank you!
2:48 There are many ways to do collision detection, the easiest is just to check if there intersecting, however for the most accuracy you will want to detect the exact time of collision this is harder.
Douglas drops another banger! keep it up, i've loved ur videos from the very beginning
I would love to see a particle system added, might be useful for something like generating random height grass on continuous areas of grass. At least that is my first idea of what it could used for beyond the obvious smoke particles. Having grass that varies in height a lot makes scenes a lot more interesting visually for not much complexity on the user's end.
I cannot wait to get a demo that allows me to interact with the world!
Amazing progress! I really enjoy how you go into the details and things you have learned along the way
The very idea that my undercloced R9 390 would run Path Tracing in real time at 1600x900 resolution is Jawdropping. But it is a reality - you are mad man, so much respect to you! i am so shocked, i can't...
Seeing you chop down that tree made me think of something cool. What if you added mass to the voxels that varies depending on its type (kind of like Teardown's materials)? The wood voxels of that tree could have much higher mass values, allowing them to disperse more inertia, giving them a sense of weight (player killed if a heavy tree fell on them, or they fall slower as grav. accel. has to apply more force)
That would be cool! Voxels do have an internal "material" but I haven't integrated it with the mass/inertia calculations yet.
Now how about internal forces? I see those trees falling over and, being made of voxels, I expect them to break further!
Haha, I would like to add object fracturing (sort of like Teardown) so that high-speed impacts cause voxels to break into smaller parts.
Yeah also leaves and branches on the tree should either break or not have collision because it makes the tree feel like a plastic toy
2:56 Not only is it the first step, but it is also the most important step, it does not matter how realistic the physics mathematics are performed, if the collision point cannot be found accurately then the physics engine will be broken.
One thing I want to see in a voxel physics engine is to have it implement the rotation-by-three-shears method for rotation within a cardinal plane (so every source voxel is preserved, there's no resampling averaging things) and have it translate objects by world grid increments. It would look very different but there might be some upsides to doing physics in such a homogenous and discrete world. :)
Very good stuff. I love voxel physics
Super impressive and helpful- this project looks awesome!!!
Me, seeing this for the first time: "Oh that's sick! Seems like an interesting -- IS THAT NUKE??!!"
These videos are very inspiring, could you also link some resources/papers you took inspiration from in the description of future videos?
Lay of the Land has nothing on you Sebastian Lauges of the voxel community. And "Unlike another popular voxel game" was my favorite part.
Have you looked at GJK/EPA?
(Casey Muratori has a good video explaining GJK, both in his "Papers I Have Loved" talk, and his old video "Implementing GJK" where the former talks about it in more general terms, and the latter goes more into the details of how it works. Also, Kuju has a good video visualizing and explaining GJK. GJK is the base collision detection, EPA figures out how much it is overlapping, etc.) With GJK you may end up having to test less verticies/edges, as 1. you just check the verticies and 2. you use some clever tricks to figure out which ones to check.
And if you end up doing this, you could gather the edge verticies to make a collision mesh, and just do the GJK on those, rather than directly on each voxel. Though you may have to subdivide the mesh if it isn't convex, as it has to be convex to work.
here's an idea if you throw something hard enought on the terrain or another object it could damage it , i know it's not simple to implement but it could be very funny.
Love the video
I hope to see more ^^
absolutely fantastic! bravo!
5:37 do we have to test the corners with all the other voxels or can we just test corners vs the surface voxels that are closest to the corner?
Corners need to be tested against any voxels on the surface with which they could possibly overlap. In practice, this means testing against the 8 voxel positions in the other object that surround a given voxel.
@@DouglasDwyer thanks. I was wondering how your engine would handle a situation like the two L shaped broken crates that the Teardown Twich Talk used as an example of a lot of corner contacts.
This is straight up magic.
Wow, I never knew Physics could be Nuked to smithereens (=voxels), but you just Nuked it! So educational! Also, well done voxelizing CS:Nuke!
Thanks! Although bear in mind that I did not make the Nuke map; somebody else voxelized it :)
Grid alined voxel water physics? AKA volume based water physics? Just an interesting suggestion
There are a lot of other things that I want to add first, but fluid dynamics like John Lin's would be really cool!
@@DouglasDwyer Yeah take your time man! This is already super impressive, and this probably wouldn't even be that necessary, just a nice touch that would be fun to play around with, and a fun problem to solve.
Keep it up! You are an inspiration.
Very very awesome.
Would love to see the demo of the 2d version you made too :D
The 2D demo is available at github.com/DouglasDwyer/rigid_pixels
There are some glitches remaining in it that I fixed in the 3D version, but you can definitely check it out.
amazing work as always Douglas! i have been wondering if you are planning on adding voxel density and such properties? it would be cool if leafs are easier to pass through or when a tree falls they wouldn't be able to keep the log up, looking forward to your response! keep up the great work.
I want to add object fracturing (sort of like Teardown) so that when high-speed collisions occur, the objects crumple or collapse. This should help leaves and branches break apart when the tree falls. I also want to make different types of voxels with varying friction/bounciness.
@@DouglasDwyer glad to know and good luck!
Simulating soft body voxels i think is usually hardware intensive. Minute papers had a video about a paper where people trained AI to handle the physics and made it an order of magnitude faster while being a very convincing fake simulation.
For me this project in the start was simply Oh another minecraft game. Then it became this wow this looks really good. I have just started learning graphics and C - for CV, then rust :) - and lmao was I wrong. This is so hard, this is so complicated. Hands down for you, not many people can do what you are doing. How old were you when you started this project? When did you start coding? A quick rundown of your path to this project would be highly praised I think.
I started working on this project in November 2021. I've been coding since probably about 2014. Maybe in the future I can do a video where I review the history of the project and my coding experience!
@@DouglasDwyer Yes that would be much appreciated!
New video! Let's go!
You are literally making teardown, but good
Hm, the interesting thing about what you're doing is that friction can be an emergent property, this is good because realistically friction isn't a real thing. You can simply have the interactions between small voxel surfaces on the objects cause it to have friction. Though, I recommend making the voxels use spheres for collision even though they're cubes, both because it can be more performant, and also because it will be softer and less jagged.
Also, the air friction should still be calculated as division because you can't feasibly simulate a bunch of very small air voxels.
great content! continue making videos 😁
I intend to do so :)
Flexible joints would be fun, I guess. could be used to join the branches of a tree in order to fold them when they touch the ground.
Teardown 2 looks pretty good 🔥🔥
May I recommend attempting to go without ambient occlusion? AO is just an inaccurate representation of global illumination shadows. If you don't have GI shadows it's whatever, but if you do, you could start with making things in shadows pitch black before GI.
Thanks for the feedback. Can you describe what you mean by "making things in shadows pitch black before GI?" Are you just suggesting that the amount of ambient light be set to 0.0, so that the inside of buildings is completely pitch-black? I describe my lighting system in Devlog #19, but it uses ray marched direct shadows and then path traced shadows for AO/emissive voxels. This system is close to full GI, but it lacks multi-bounce.
Ya pretty much, anything in shadow doesn't get light from what's making the shadow, it wouldn't work well without multi bounce though... Perhaps one method for multibounce is to make everything emit light according to its brightness, with the material as a multiplier, and doing multiple passes. It would be self feeding but it would probably plateau.
I've been wondering is this more so to create a general purpose voxel engine, or you are going to make a game out of this?
If you're making a game, what were thinking of doing? Shooter? Sandbox (Like Garry's Mod?) Or like a survival game?
Also this is really cool. It's still an awesome project to watch!
That's a great question. My goal is to create a general purpose engine that allows people to create their own games and experiences through modding. The plan is to finish the core engine, and then build a small example game (I've been thinking a shooter) which can be used both as promotion for the engine and also an example for other games.
Do you use floodfill to convert floating chunks into rigid bodies?
That's a great question. Indeed, I use a version of flood-fill/depth first search to find groups of voxels that aren't touching anything else. (The flood-fill algorithm is highly optimized to work with a custom binary voxel data structure.)
Why is the lighting so weirdly unstable and...? Screenspace influenced? Or something?
Great job! But I don't understand something. The assumption that when two objects collide, their edges will interact is understandable. But how does this help when calculating collisions with the global mesh, i.e. the terrain? After all, there are too many edges there, to check them all you will have to spend too many resources
I glossed over the details, but I use a 64-tree data structure (like an octree but subdivided by 4 on each level). I exploit the tree hierarchy during collision detection so that I am only checking areas where both objects have overlapping voxels.
Uhhh….Douglas, as you know I’ve been following you pretty much from the beginning, but I’m afraid I have to disagree with you one point:
Your physics engine last year was **very** accurate. I am forever chopping trees down, only for them to float away in the sky. It’s a real problem. 😑
P.s. great work. It looks fantastic!
Haha thanks. I too abhor when trees spontaneously float away in real life :)
Fans of indie voxel engines are eating GOOD right now
I found your videos as I was searching for optimizations to improve my own simple voxel game, and I am heavily thinking about switching over to ray marching. One thing I have always wondered about in your videos is how you are able to render objects not aligned to the grid, since your ray marching algorithms with their octrees and such seem like they should just work on grid aligned voxels. Also, I wonder how shadows work with these objects.
5:37 is the surface of a sphere covered in corners? Or is it okay to just test it as a radius from the sphere center?
The sphere's surface is treated as many corners. The sphere is represented like any other voxel object, so there's no special case in the code for it.
@@DouglasDwyer neat! Thank you for clearing that up
How you did realise energy of rotation (momentum)?
One thing i've always wanted to see is a 3d voxel game that locks everything to the world grid. So instead of smoothly moving cubes around, it would snap its position much like a 2d pixel art game.
Same thing with decreases FPS anime style games. On top of making the animations low fps, also make the character movement low fps. I wonder what it would look like. Sorry, my comment isnt much about this video lol
I understand your suggestion fully. That said, I am not aware of any algorithm that can re-voxelize objects at arbitrary rotations while being fast enough to run in real time. In addition, I personally feel that re-voxelizing objects would look confusing and make it harder for users to predict an object's behavior. As such, I'm not planning to go for this route - but it's a creative suggestion :)
John Lin's engine made me think it was possible though, as seen in this video th-cam.com/video/UBfRPqKuq2I/w-d-xo.html
but i might be wrong!
What exactly is the gameplay loop of this game you’re working on?
I love the look of the medieval section you showed with the tree, I feel something like that could fill the hole left by Medieval Engineers if made right.
I am focusing on core engine technology right now - I am more of an engine programmer than a game designer, I confess. My ultimate goal is that people should be able to create their own games by writing mods for the engine. I was thinking of building a small first-person shooter game as a proof of concept.
Looks great! How would you say the performance holds up in comparison to teardown when many rigid bodies are active at the same time?
That's a great question! I haven't had a chance to compare with Teardown yet. The performance of the connected component labeler (the code for finding disconnected parts of the terrain and turning them into rigid bodies) ended up being really fast. The actual rigid body simulation is fast too - but I have found one case where the collision detector visibly lags. This happens when I spawn ~100 small particle entities on top of a tree and then chop the tree down. It slows down because the system is doing many (between 15 to 30) collision iterations per tick for fast-moving objects, so that voxels don't clip through each other. I hope to optimize this case by making the simulation more stable, reducing the amount of iterations required, and multithreading the collision detector.
This is really cool, but the main thing I notice when playing the demo, is that once an object becomes it's own separate Rigidbody, you can no longer interact it, which is super weird feeling and jarring.
That's a good point. I'm not sure exactly what the gameplay will end up being like, but allowing for further destruction or building on separate rigid bodies would be good to have.
What about different physics parameters like friction and bouncyness?
Right now the friction and bounciness are a hard-coded constant, but in the future I will make them depend upon the voxel materials involved.
@@DouglasDwyer Nice. Another question, how do you calculate the moment of inertia for randomly shaped voxel objects?
@@stephenwhite506 The moment of inertia is calculated by definition with a couple optimizations. From a high-level perspective, I calculate the inertia tensor for a single unit box. Then, I iterate over all voxels in the volume and sum the inertia tensors for every voxel. The inertia tensors are transformed using the parallel axis theorem and summed to create one final inertia tensor for the volume.
In practice, it's a bit more complicated than that. For performance, I generate a 65536-entry lookup table containing the inertia tensor for every possible arrangement of 4x4 voxels. When calculating inertia, I iterate over my voxel data structure. I use the lookup table to get the inertia tensor for 4x4 voxels at a time, and sum that up (with the parallel axis theorem) for all relevant regions of the voxel volume. This process is also accelerated by my use of a hierarchical 64-tree for the voxel representation.
How do you detect when an object has been separated from the world and should become a physics object?
I use a "connected component labeling" algorithm (you can look this up on Wikipedia). The goal is to find isolated groups of voxels that are surrounded by nothing but air. I do this by running depth-first searches after the terrain is destroyed. If a depth-first search terminates without finding a valid path to a point 256 voxels away, then all voxels hit by the depth-first search are copied into a separate object. The depth-first searches are accelerated using binary bitmasks to search 64 voxels at a time.
@@DouglasDwyer wow, this entire project is very impressive! That's an interesting technique you described. how large can you go before performance becomes an issue?
Good job!
Can you make an in depth tutorial for the 2D version of the physics engine?
The browser demo doesn't seem to work in firefox.
Thanks for trying out the demo! As stated at the end of the video, the demo only works in Chrome, Edge, or Opera. Once Firefox releases support for WebGPU, it will work in Firefox too.
I love when people try to make basically minecraft but more realistic looking.
so why not first check a full object bounding volume collision, then do the accurate voxel collision detection, ie high level ray/collision culling first, you have much less stuff to test mutual collisions, and you already have separate object entities defined. in the engine.
Yep, I already do this! I glossed over the details, but there are broadphase and AABB checks. In addition, the voxel-voxel collision detection uses a sparse voxel tree structure to find nearby voxels. There's not really much "search" involved in finding voxels to collide.
holy shit ... awesome.
Exxelent video as always. Is it possible to add a bit of reflection to objects to make them less flat? For example, a blue object should colour its nearest surrounding a little blue. That will make it looking a lot better!
I want to add per-voxel reflections to the graphics engine in the future! With ray marching, it shouldn't be hard at all.
Voxels take a lot to simulate on the smaller scale with on-the-market gaming computers... but what if there were some sort of arcade machine made specially to run voxels?
Why not just use distance between two voxels to check for collisions/overlap?
Hi, thanks for making the video! I was wondering in 2d do you only ever have to check corners with all other voxels? And do you do continuous collision detection, I saw it was mentioned in the Teardown talk but Denis didn't expand on it. Just checking if you knew more about it?
oh shit.... insane 😲
Nice work Douglas, did you consider using a 3rd party engine e.g. Bullet or PhysX? What made you decide to write your own?
Really awesome question. There were three reasons for this:
1. I like doing game engine development, so pulling in another physics engine would be sort of "cheating" - I wouldn't be building my own engine anymore. Not that there's anything wrong with third-party engines - they're great - but it's more entertaining and satisfying to do it myself.
2. Avoiding excessive complexity and dependencies. By writing my own physics engine, I don't need to pull any big libraries into my project or figure out how to make them compile cross-platform. Further, if the physics ends up being buggy or I need to optimize/multithread, it's easy do so, because I understand the whole thing.
3. Voxels require custom code for efficiency anyway. This is the real reason - the tipping point - that made me code things from scratch. Engines like Bullet or PhysX are built to detect collisions between simple shapes (boxes, capsules, triangle meshes). They are not designed for collision detection between large voxel volumes, and it would be difficult to leverage the voxel data itself when using them. By writing a custom engine, it's easy to write collision detection routines against my own voxel data structures.
That being said, I WOULD consider trying a third-party collision solver, if I ever wanted to try anything like a constraint-based physics solver.
@@DouglasDwyer Interesting, thanks for the detailed reply. I implemented Bullet in my voxel engine using compound shapes for strips of voxels but performance was not great and I had some other issues, so I removed it. I'm looking at ODE now, since that allows you to use your own collision detection which can be more optimised for voxels. I'm also considering PhysX since the documentation says "The purpose of the Custom Geometry feature is to allow the creation of application specific collision geometries (e.g. a voxel map)"
@@Adrian-ld4oz right, custom geometry is basically required if you want good performance. It's definitely possible to do, but it can be harder to debug and fix things when they go wrong.
It would be cool to add deformation for three branches.
what did you end up doing to check if a chunk of voxels becomes disconnected to the environment?
That's a great question. Indeed, I use a version of flood-fill/depth first search to find groups of voxels that aren't touching anything else. (The flood-fill algorithm is highly optimized to work with a custom binary voxel data structure.)
@@DouglasDwyer thanks for the response. do you run this every time there is a change to the voxel occupancy bitmask thing? and how do you choose which voxel to use as the seed for the flood fill algo?
@@smangalang Yes, the algorithm is re-run for all user edits. Regarding a seed, the flood-fill algorithm involves multiple searches, so it can categorize every single connected component within the edited region. As such, the flood-fill algorithm is repeatedly run using a new voxel as the seed until all voxels in the edited region have been detected.
@@DouglasDwyer neat! thank you
Next step: simulate loads to break geometry, like Red Faction: Guerrilla does.
These physics kinda remind me of teardown
Where can i watch Dennis Gustafsson's talk?
You can find it here: th-cam.com/video/tZP7vQKqrl8/w-d-xo.html
I understand why it's like that, but still, "real" rotating and moving in the voxel world wouldn't involve rotation of voxels themselves (just like how pixels don't rotate and move on a 2D screen when 2D objects are rotated and moved).
How are you handling rendering for multiple objects, I assume some sort of BVH?
@@frozein nothing that complicated! I divide the world into chunks, and each chunk has an associated list of objects each frame. When ray marching, I loop over the object list for each chunk that is hit. I ray march any objects intersected by the ray before moving on.
It's simple, but performs surprisingly well. My GTX 1660 can handle ~100 objects in a chunk before the frame rate drops below 60 FPS (this is with the path traced lighting turned on). For fewer, relatively big objects it's a great system!
@@DouglasDwyer Ah nice, love a simple solution
Very cool! I was just wondering if you happened to make use of the Parry or Rapier crates when implementing this, and if so, how did that work out for you?
@@robinmattheussen2395 nope! While off-the-shelf physics engines can be handy, they're not that useful for large-scale voxel engines since for performance all of the collision detection needs to be custom anyway. As such, I can't comment on those crates :)
@DouglasDwyer Understandable, I was just curious. Still, really impressive stuff man!
Will one be able to reintegrate those objects into the world?
Would you ever consider making it so that voxel physics objects "fuse" back into the global octree after remaining motionless for a certain amount of time?
Yep, this is something that I implemented in my previous physics engine. I'll be re-adding it at some point in the future!
Voxels, let's goo!!
when soft=body physics for leaves and cloth simulation?
You dont need to solve for the velocity as far as I am aware. You can use the velocity verlet algorithm to generate the velocities every frame from the positions. This is what many researchers use in e.g. molecule simulations. Maybe that could speed up your system? Or are you using that already?
I will have to try the Verlet algorithm, but my worry is that it wouldn't work very well for velocity changes imposed by hard constraints or collisions. At least in the current version of my engine, velocity is used to change position and then position is further adjusted by the collision solver. I worry that those auxiliary adjustments could mess up the Verlet algorithm.
@@DouglasDwyer I think the velocity verlet algorithm (which is different from the verlet algorithm as far as i know) might actually work better than you think, as the velocity is computed from the position changes and NOT STORED. So the collision solver only solves for the positions and doesnt care for the velocities. Idk how your implementation works, maybe it wont work after all. Here is a video that helped me to understand the algorithm a bit better: th-cam.com/video/lS_qeBy3aQI/w-d-xo.htmlsi=dtd5SLFWN996xgZd
Awesome.
I am trying to get past the graphics phase (even though you can't ever, really) but I can't get the DDA down. Do you mind going through the basics?
P.S. I was talking about my game. Sorry!
I would recommend taking a look at lodev.org/cgtutor/raycasting.html
It's where I first learned DDA :)
@@DouglasDwyer I've seen this beforehand, but I'll look into it! Thank you!
I have a somewhat silly question: If, rather than translating the rotation of voxel objects as if they were normal 3d models, we instead preserve the voxel alignments perfectly right angle to the terrain, would that help with performance of collision detection? And even lighting calculations? Like, don't rotate voxels, when rotating the object?
It's difficult to put into words, and English is not my main, but what I mean is... to create a world of voxels in a voxel-field, ie, object edges "voxallate" when rotated instead of preserving their perfect line. In a way, object edges change "shape" when they are rotated and become voxellated to fit into the voxel grid.
I understand your suggestion fully. That said, I am not aware of any algorithm that can re-voxelize objects at arbitrary rotations while being fast enough to run in real time. In addition, I personally feel that re-voxelizing objects would look confusing and make it harder for users to predict an object's behavior. As such, I'm not planning to go for this route - but it's a creative suggestion :)
@@DouglasDwyer Thanks for the reply. For me, when I see a normally rotated object in a voxel world, it's always an immersion breaker. I expect voxelization instinctively, like what happens at a low-res 2d environment. Maybe that's because I'm old and I have internalized this behaviour since my childhood days with my c64.
And perhaps, it might become a ilttle bit noisy at the edges if what I imagine is implemented. That being said... I think it might be achieved at a shader level, just for visuals.
What do you think about "Lay of the land"?
I think Tooley's work is absolutely breathtaking! It's amazing what he has managed to achieve with Unreal Engine. I will definitely be trying Lay of the Land when it comes out.
The trees look really odd with how stiff they are; do you have any plans for deformation?
Good point - I would like to add object fracturing (sort of like Teardown) so that high-speed impacts cause voxels to break into smaller parts. This should make the tree branches break off as the object falls. I don't have any plans for other sorts of deformation, though. That's a bit hard to do with a single, fixed voxel grid :)
is finite element method a possibility for the future?
I think Finite Element Analysis is mainly useful for modeling differential equations, but there's not really a differential equation to solve in this case.
@@DouglasDwyer finite element method simulation of 3d deformable solids / it's used to simulate plasticity and stuff. I suggest reading computer science paper "Real-Time Deformation and Fracture in a Game Environment" by Parker
@@gibberish_demon I see. It's not something that I've studied before, so I'll take a look. Thanks for the suggestion!
One, small, problem I noticed... while this looks amazing, the voxels are being rotated off axis with their own world each. What if instead you rotated their points but still aligned all voxels to global grid axes positioning each voxel to global grid still?