0:03 hello YouTube I'm Douglas and this is my
0:06 voxal game engine it's a video game
0:09 project that I'm coding where the entire
0:11 world is made out of tiny little fully
0:14 editable cubes this month I've been
0:16 working on an exciting new feature which
0:20 is realistic rigid body physics now
0:22 objects that are not part of the terrain
0:25 can move around slide bounce and collide
0:37 it's possible to drag objects around
0:40 using the mouse and interact with them
0:42 and if you delete part of the terrain
0:44 anything that becomes disconnected will
0:47 turn into a separate rigid body and be
0:49 simulated by the physics code meaning
0:51 that yes it's possible to chop a tree
0:54 down and watch it fall unlike another
0:56 popular block game those who have been
0:58 subscribed to my channel for a while now
1:00 you should totally subscribe if you
1:02 haven't we'll recall that I did
1:04 Implement a physics engine last year but
1:06 it was my very first attempt at ever
1:09 writing physics code and it was laggy
1:12 buggy and worst of all physically
1:15 inaccurate the first physics engine that
1:17 I wrote did not conserve energy or
1:20 momentum as objects hit each other and
1:22 moved through the scene which meant that
1:25 for example if you tossed one box at
1:27 another box the boxes would just hit
1:30 each other there would be no response no
1:31 momentum would be transferred to the
1:33 second box from the first and this made
1:36 the game a lot less interesting and fun
1:38 because you couldn't say stack one
1:41 object on top of another and then knock
1:44 it off um using a flying dut the plan
1:47 for this video is to describe the
1:49 architecture of the new physics engine
1:51 and I'll be going into detail about all
1:53 of the ways that I've improved the two
1:56 core components Collision detection and
1:58 response but before we dive into the
2:00 details I'd like to say a quick word
2:03 about today's sponsor Cod Crafters Cod
2:06 Crafters is an online education platform
2:09 built by experience software Developers
2:11 for experienced software developers it
2:14 has a whole bunch of cool project guides
2:16 that will walk you through how to build
2:19 a ubiquitous piece of software they're
2:21 adding new projects all the time too
2:23 since I joined for example they've added
2:25 a project that teaches you how to build
2:28 your own shell and another project that
2:29 teaches you how to build your own
2:31 scripting language interpreter they're a
2:33 really great resource and I'd highly
2:35 recommend them if you're say looking to
2:37 learn a new programming language but
2:40 don't have a project for it yet you can
2:42 check out code crafters for free today
2:46 by using the link in the description now
2:48 let's talk about Collision detection
2:50 Collision detection is the first step in
2:53 any physics engine and it involves
2:55 taking pairs of objects in the scene
2:57 figuring out where they overlap and then
3:00 producing a list of contact points point
3:02 and Associated data which can later be
3:05 used to move the objects apart and make
3:07 it look like they bounced in order to
3:09 make Collision detection fast there are
3:11 a couple of things you want to do for
3:15 one you want to check as few points as
3:17 possible for collisions because doing
3:19 less work obviously yields faster
3:22 results and in addition you want to
3:24 produce the fewest number of contacts
3:26 that describe your rigid bodies properly
3:28 because the fewer contacts there are the
3:31 less work the second step the Collision
3:33 solver will need to do in the context of
3:37 voxels This Means taking two voxal grids
3:39 one of which may be arbitrarily rotated
3:41 and translated with respect to the other
3:44 and figuring out which foxal touch in my
3:46 previous engine I would do this by
3:48 literally going through any pair of
3:50 voxal that were near one another and
3:53 running a precise separating axis test
3:54 this was problematic because it
3:57 generated a lot of contacts for example
4:00 a box sitting on the ground like this
4:02 would have contacts for every single
4:05 voxel on its bottom surface that meant
4:08 taking more time to run extra Collision
4:10 detection tests and it meant producing
4:13 more contact points to improve this I
4:15 turned to the game Tear Down for
4:17 inspiration tear Down's Collision
4:20 detection system is described in this
4:23 public Tech talk that the engine's
4:26 author Dennis Gustafson did and it's a
4:28 really enlightening talk I would highly
4:30 recommend watching it but the core idea
4:32 that tear down uses is that if you have
4:34 two polygons that are touching one
4:38 another either one polygon's Edge will
4:41 be touching another polygon's Edge or
4:43 one polygon's vertex will be touching
4:50 exterior so what this means is that it's
4:52 not necessary to include every voxel
4:54 during Collision detection let's start
4:58 off by defining corner and Edge voxal we
5:00 do this by considering the aent voxels
5:04 along any particular axis X Y or Z I
5:06 call a voxel a corner if it is not
5:10 surrounded on both sides by other voxels
5:13 for any axis so this would be a corner
5:16 but this would not be a corner similarly
5:19 I Define a voxel as an edge if it is
5:21 surrounded on both sides by others along
5:24 exactly one axis so this would be an
5:27 edge but this would not be an edge now
5:29 that we've defined corners and edges we
5:32 can leverage the fact that a corner or
5:34 an edge will always be involved in a
5:37 collision between two polyhedra to do
5:39 this my physics engine generates a
5:42 physics acceleration structure whenever
5:45 an object spawns and this acceleration
5:48 structure tracks the corner and Edge
5:51 voxels within the object then when it's
5:53 time to do Collision detection I test
5:56 the corner voxel of one object against
5:58 all the voxel of the other and vice
6:00 versa and then I test the the edges of
6:03 one object against the edges of the
6:05 other and this is great because you end
6:08 up testing fewer things and it also
6:11 generates far fewer contacts like Dennis
6:13 gustavson points out in the tear down
6:15 Tech talk a box sitting on the ground
6:18 like this only generates contacts
6:20 associated with the corner voxels and
6:22 this is a huge Improvement another
6:24 Improvement the talk mentions involves
6:27 figuring out whether voils themselves
6:29 are overlapping previously whenever my
6:31 engine figured out that two voxal were
6:34 closed together it would test them for
6:37 an actual Collision using a precise
6:40 boxbox separating axis test and this is
6:42 something I talk about more in a
6:44 previous video but the short of it is
6:47 this is an expensive but perfectly
6:49 accurate algorithm that will tell you
6:51 whether two boxes which are arbitrarily
6:54 rotated with respect to one another are
6:57 touching and this algorithm was good but
6:59 it turns out for voxels that are this
7:01 small you don't need that level of
7:03 accuracy and so what you can do instead
7:05 to test whether two voxal are
7:07 intersecting is take a voxel from one
7:10 volume transform it into the coordinate
7:12 system of the second volume that you're
7:15 testing and then check to see whether
7:17 any of the eight voxal which are closest
7:19 to that original voxel's transformed
7:22 Center Point are full if so we consider
7:25 a collision to have occurred this
7:27 approach skips all the work associated
7:29 with separating axis tests so it's much
7:33 faster and it does ignore the rotations
7:35 of the individual voxal themselves so
7:38 voxal end up behaving kind of like tiny
7:40 little spheres which isn't even a bad
7:42 thing it makes many objects sort of roll
7:45 or slide more than they normally
7:47 would with the Collision detection
7:50 system upgraded I turned my attention to
7:52 the Collision solver the point of the
7:54 Collision solver is to take all of the
7:56 contacts generated in the first step of
7:59 the physics code and then move objects
8:01 apart so that they're no longer
8:03 interpenetrating and ensure that they're
8:06 all moving with the correct velocities a
8:08 realistic Collision solver allows for
8:11 force to be transferred between objects
8:13 so if say this box on the left slides
8:15 over and hits these two boxes on the
8:18 right the other two boxes should start
8:20 moving with some amount of momentum that
8:22 was transferred during the Collision
8:23 this was the part that I really got
8:25 wrong in my previous physics engine
8:28 because it only simulated one object at
8:30 a time so during the simulation I would
8:33 take one object I would treat all other
8:35 objects in the scene as fixed and
8:37 unmoving I would update the position and
8:40 velocity of that one object and then I
8:42 would continue through one object at a
8:44 time and this meant in my previous
8:46 engine forces didn't transfer between
8:49 objects if you stacked like one box on
8:51 top of another it wouldn't be possible
8:53 to lift the top box up by applying a
8:56 force to the bottom box and this led to
8:58 a lot of um buggy and unrealistic
9:00 behavior for for example if you just put
9:03 a single tiny little voxal object on top
9:05 of a big tree the big tree would be sort
9:07 of pinned to the ground um you wouldn't
9:09 be able to move the big tree or lift it
9:11 up because of that one tiny voxel on top
9:14 of it so to learn how to do Collision
9:16 solving better I went ahead and I read a
9:18 book called game physics engine
9:20 development by Ian Millington and I'm
9:22 not sponsored but this is another really
9:25 excellent resource it makes all of the
9:28 math um very clear and intuitive and it
9:30 even comes with an example physics
9:32 engine implementation that you can
9:34 reference as you go through the book so
9:36 I read this book I figured out its
9:39 approach to Collision solving and then I
9:41 went ahead and I implemented that the
9:43 iterative solver is broken into two
9:46 parts position and velocity adjustment
9:48 and they both proceed in basically the
9:51 same way each algorithm takes a single
9:53 contact from the list of contacts that
9:55 were generated during Collision
9:57 detection and it figures out how to
10:00 change the object's position and or
10:02 velocities in order to make them no
10:04 longer interpenetrate and in order to
10:06 ensure momentum is transferred and this
10:08 math you can find in the book but it's
10:10 the same sort of math you would be doing
10:12 in a basic like physics one course it's
10:16 just conservation of momentum and energy
10:18 as you update the object's velocities
10:21 it's not too hard the real problem lies
10:23 in the fact that there isn't just one
10:26 contact but many when the physics solver
10:29 moves two objects apart to resolve one contact
10:29 contact
10:32 it may change the severity of other
10:34 contacts between the two objects since
10:37 solving multiple contacts simultaneously
10:39 is a very difficult challenge the
10:42 physics solver instead proceeds in an
10:44 iterative fashion it solves one contact
10:47 and then it goes through the list of
10:49 contacts and updates all the other ones
10:51 based upon however it changed the
10:54 position and velocities of the objects
10:56 involved then it chooses another contact
10:59 to solve usually the next worst contact
11:02 changes the objects so that that contact
11:05 is no longer a problem and then updates
11:07 all of the other contacts in the list
11:09 again so that the changes in position
11:11 and velocity are reflected in the
11:13 contact data the iterative solver
11:16 repeats this process looping over the
11:19 contact list again and again until all
11:22 contacts have been resolved and momentum
11:24 has been transferred for every single
11:27 one of them and that's an overview of
11:30 how my two-phase point based iterative
11:32 physics engine works the biggest thing
11:34 that was helpful for me in learning how
11:36 to do this was really leveraging my
11:38 resources using the tear down Tech talk
11:42 and millington's book and I also built a
11:45 small 2D version of this physics engine
11:47 before going into 3D and applying it to
11:50 my voxal game and that was a really big
11:52 help because 2D is a lot simpler to work
11:54 with and I was able to get a feel for
11:56 what the math should be like and what
11:58 bugs I'd encounter so that'd be my
11:59 biggest recommend recommendation if
12:02 you're interested in physics engines and
12:04 just starting out is to build something
12:06 in 2D because it'll be a lot easier and
12:08 it's honestly what I should have done uh
12:10 the first time I made a physics engine
12:12 rather than trying to go to 3D right
12:14 away if you want to try the engine out
12:16 for yourself there's a demo Linked In
12:19 the description you can play it online
12:21 in Chrome Edge or opera or you can
12:23 download a Native version of the demo
12:26 for best performance lastly if you have
12:28 any thoughts or questions be sure to
12:31 leave a like and a comment down below
12:32 I'd be more than happy to discuss your
12:35 ideas with you next up I'm planning to
12:38 work on a building system for my game to
12:40 allow users to finally create some cool
12:42 looking scenes so make sure to subscribe
12:44 in order to stay tuned for the next
