Coding rigid body physics for voxels [Voxel Devlog #20]
Вставка
- Опубліковано 16 вер 2024
- Try CodeCrafters for free today: app.codecrafte...
Online demo: github.com/Dou...
Additional voxel models: tinyurl.com/mt...
Using voxels in a rigid body simulation yields amazing results! It's possible to compute mass and moment of inertia exactly, as well as perform collision detection for arbitrary concave shapes, so the simulation is very accurate. This devlog highlights my new rigid body physics code and explains the two important pieces - collision detection and solving.
Music used in the video:
LoxBeats - Endless Summer
Lukrembo - Butter
Lakey Inspired - Blue Boi
Artificial.Music - Celestial Gold
HOME - High Five
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)!
looking forward to the soft body dynamics next!
can't wait for "Coding soft body physics for voxels"
You
Kirby super! I didnt expect youd be on a voxel video
@@quickestawab5045 oh? where do you know me from?
@@Kirby_Super i know u from skunktronix’s streams
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.
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.
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.
absolutely goated
Agreed.
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!
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).
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.
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!
this engine is going to contain more features than most full fledged voxel games do, nice job
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
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...
Hella impressive, you're making crazy progress!
0:11 that donut looks edible too(and editable)
This looks fantastic! I loved hearing about how you developed the physics for the engine.
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!
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.
Douglas drops another banger! keep it up, i've loved ur videos from the very beginning
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.
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. :)
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.
7:45 Very nice, it would seem my advice was already in use!
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.
Very good stuff. I love voxel physics
Amazing progress! I really enjoy how you go into the details and things you have learned along the way
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.
I cannot wait to get a demo that allows me to interact with the world!
absolutely fantastic! bravo!
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.
Lay of the Land has nothing on you Sebastian Lauges of the voxel community. And "Unlike another popular voxel game" was my favorite part.
Super impressive and helpful- this project looks awesome!!!
New video! Let's go!
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.
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.
This is straight up magic.
oh shit.... insane 😲
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!
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.
Me, seeing this for the first time: "Oh that's sick! Seems like an interesting -- IS THAT NUKE??!!"
Awesome.
You are literally making teardown, but good
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 :)
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!
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.
holy shit ... awesome.
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.
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.
Keep it up! You are an inspiration.
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 ua-cam.com/video/UBfRPqKuq2I/v-deo.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.
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 :)
Teardown 2 looks pretty good 🔥🔥
These videos are very inspiring, could you also link some resources/papers you took inspiration from in the description of future videos?
Good job!
Fans of indie voxel engines are eating GOOD right now
great content! continue making videos 😁
I intend to do so :)
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.
Next step: simulate loads to break geometry, like Red Faction: Guerrilla does.
I love when people try to make basically minecraft but more realistic looking.
This is predy cool.
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.
the goat
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.
Voxels, let's goo!!
These physics kinda remind me of teardown
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.
Why is the lighting so weirdly unstable and...? Screenspace influenced? Or something?
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?
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.
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: ua-cam.com/video/lS_qeBy3aQI/v-deo.htmlsi=dtd5SLFWN996xgZd
It would be cool to add deformation for three branches.
ooh cmon, how long until 3d noita! aaaah
How you did realise energy of rotation (momentum)?
Are you planning on making this engine open source and possibly work on an editor? Would be super cool cus rn theres barely any actual voxel game engines out there to use to build games with so you have to make ur own engine which explains y theres so little amount of voxel games out there.
I am planning to release the engine as a "platform" where people can make their own games. It will come with a modding toolkit that will allow for writing game plugins in Rust.
bros making teardown from scratch
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
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 :)
Why not just use distance between two voxels to check for collisions/overlap?
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.
when soft=body physics for leaves and cloth simulation?
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
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.
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!
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.
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.
Where can i watch Dennis Gustafsson's talk?
You can find it here: ua-cam.com/video/tZP7vQKqrl8/v-deo.html
Teardown 2, electric blue glue
Will one be able to reintegrate those objects into the world?
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.
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?
Can you turn this into an addon for godot engine. A voxel engine inside of godot would be really cool. Godot already uses C++ C#
teardown already exists lil bro
edit: nvm u mentioned it in the video mb
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?
Bro you're remaking teardown but is the code more efficient? And if it is can you tell us how you did it?
I haven't done a performance comparison, but the graphics, lighting, and world management system are different in comparison to Teardown. I've gotten this far through lots of trial and error as well as looking at how other people have done voxels :)
I have a question even Teardown fails at.
Can your game handle a pile of debris (or similar size debris is between 30 to 140 voxels in Teardown) that has 40 debris in it?
Also, wasn't sure if Teardown tech talk went into its physics engine, well dang, might as well continue the streak of making a Teardown but in 2D recreation without watching the devs talk about how their physics system works. My game does use cellular automata rulesets due to performance limitations with my language so I can't do it 1:1 anyway. But still would've been useful for making optimization ideas. frick.
The physics solver does better with few larger objects than many smaller objects. I have found that it tends to visibly lag when ~100 entities are together and physically interacting. I am working on optimizing those cases now! It seems to mainly be the collision detector that is the bottleneck.
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.
Teardown but with less destruction