Writing a Physics Engine from scratch - collision detection optimization
Writing a Physics Engine from scratch - collision detection optimization
Github repository https://github.com/johnBuffer/VerletS…
Content
0 -> value integration is a fantastic tool to
2.94 -> easily simulate simple physique
4.62 -> interactions
5.759 -> in the video I did to demonstrate how
8.22 -> easy it is to create a very basic physic
10.5 -> engine I use the naive algorithm to find
13.139 -> collisions between objects
15.059 -> this allowed to handle a few thousands
17.58 -> objects at a reasonable frame rate but
19.98 -> what if we want to simulate way more in
22.74 -> this video I will present a simple way
24.779 -> to greatly improve the performance of
26.82 -> the simulation
29.46 -> this is a technique I use in all my
31.74 -> projects involving physics be it very
33.96 -> integration or impulse based solvers
38.28 -> foreign
48.539 -> the aim of the simulation is to minimize
51.059 -> the overlaps between objects two objects
54 -> overlap if the distance between their
56.039 -> centers is smaller than the sum of their
58.62 -> radius
61.079 -> the value of the overlap is computed by
63.42 -> subtracting the distance between the
65.4 -> objects from the sum of their radius
67.68 -> then we move them along the axis defined
70.799 -> by their centers each object is moved
73.74 -> half the overlap
77.939 -> here is an illustration of this
80.46 -> principle applied to multiple objects
87.06 -> in this example the initial overlaps
89.759 -> were quite important
91.68 -> thing alliteration is not sufficient to
93.72 -> fix them we can either perform multiple
96 -> iterations or we can try to minimize
99.119 -> these overlaps in the first place by
101.579 -> using sub steps resulting in much
103.92 -> smaller objects movements between
105.659 -> physics frames and thus much smaller
108.299 -> overlaps all of the simulations of this
111.24 -> video will be using eight sub steps
113.28 -> meaning that the physics solver we run
116.1 -> at 480 Hertz this is how I enable sub
120.24 -> stepping in my code
125.939 -> foreign
131.3 -> [Music]
136.16 -> way of detecting overlaps is to iterate
139.2 -> on all the objects and for each of them
141.66 -> to iterate on all the users check the
144.9 -> distance and move them apart if they are
147 -> to close
148.02 -> while valid this algorithm is very slow
150.84 -> because the number of checks to perform
153.06 -> is equal to the number of objects
155.28 -> squared
157.8 -> this algorithm could be written like
160.02 -> this
178.879 -> let's run a simulation where we
181.379 -> continuously add objects and stop it as
184.2 -> soon as the frame rate drops under 60
186.3 -> FPS and see how much objects it can
189.18 -> handle this way
192.599 -> foreign
192.89 -> [Music]
202.64 -> as you can see the simulation can only
205.62 -> handle a few objects what's really
207.959 -> inefficient with this approach is that
210.48 -> we perform a lot of useless checks
212.4 -> between objects that are very far away
216.06 -> in order to vastly reduce the number of
218.76 -> collision checks we have to introduce
221.159 -> the notion of space partitioning one of
224.28 -> the simplest structure is the fixed grid
227.7 -> acceleration space is divided in square
230.4 -> cells for maximum performance I will use
233.34 -> objects all having the same radius and
236.159 -> set the cell size to the object's
238.319 -> diameter
239.94 -> first we have to add the objects into
242.58 -> the grid to do so each object's index is
246 -> added into the cell above which
247.98 -> subterries
249.659 -> at the end of the process it each cell
252.06 -> stores the list of its contained objects
256.979 -> then to find collisions we iterate on
260.1 -> all the cells and compute the distances
262.44 -> between all the current sales objects
264.6 -> and the ones Associated to the
267.12 -> surrounding cells to remove any
269.82 -> boundaries check we don't iterate on the
272.639 -> cells On the Border
274.32 -> foreign
276.72 -> this algorithm could be written like
278.94 -> this
296.8 -> [Music]
310.86 -> foreign
317.67 -> [Music]
323.64 -> [Music]
335.6 -> let's run the simulation again and see
338.52 -> how much objects this new algorithm can
340.979 -> handle
342.59 -> [Music]
345.12 -> foreign
348.19 -> [Music]
363.5 -> [Music]
368.68 -> [Music]
375.12 -> foreign
378.13 -> [Music]
389.46 -> it's already much better the simulation
392.4 -> can no handle around 16 times more
395.039 -> objects we can improve performance
397.44 -> further as we will see later but now
400.38 -> that we can learn bigger simulations we
402.78 -> can have some fun taking advantages of a
405.96 -> very powerful characteristics of these
407.819 -> simulations they are deterministic
413.12 -> this means that a specific initial state
416.22 -> will always produce the same results
418.68 -> when the simulation is executed on it
427.4 -> [Music]
428.639 -> with more objects we can animate the
431.4 -> creation of an image
433.02 -> to do so we execute the simulation the
435.78 -> first time see where each object lands
438.66 -> on the picture and assign them the color
441.18 -> of the underlying pixel
444.96 -> foreign
450.259 -> the simulation with the objects having
453.3 -> their color set since the simulation
456.3 -> will always produce the same result all
459.66 -> the objects will return to their
461.28 -> previous places with the right clause
469.38 -> volar we have a very nice chicken thanks
472.62 -> to Modern Hardware we have a lot of
474.9 -> corals that we can use to speed up our
477.06 -> computations even if we drastically
479.4 -> improved the collisions detection stage
481.74 -> of our simulation using fixed Grid it's
484.62 -> still the most time consuming part of
486.539 -> the solver one straightforward way of
489.24 -> multi-threading the simulation is to
491.4 -> split the collisions detection by
493.199 -> dividing the Grid in several parts and
496.139 -> assign each one thread with two threads
499.02 -> it would look like this
509 -> let's check the performance with 10
511.56 -> threads
530.01 -> [Music]
534.779 -> foreign
565.22 -> as you may have noticed the objects are
568.68 -> sometimes acting a bit like a food this
571.68 -> is because friction is not taken into
573.72 -> account in this very simple solver
583.66 -> [Music]
588.74 -> using multi-threading we multiplied the
591.899 -> number of objects by 5. now that we have
595.2 -> more than 100K objects let's try to
598.92 -> generate a high definition chicken
601.98 -> we start by running the simulation
607.05 -> [Music]
610.8 -> set the colors of the objects
613.32 -> and run it again just as before
618.93 -> [Music]
631.58 -> it seems that we got a very nice KFC
635.04 -> chicken but that's not exactly what we
637.32 -> wanted the problem here is that data
639.899 -> Rift is occur when multiple threads are
642.12 -> working on the same cells as the
643.86 -> boundaries of their zones to fix this we
646.92 -> separate each thread Zone in two and
649.86 -> solve collisions in two passes ensuring
652.68 -> that no cells are being processed by two
654.959 -> threads at the same time
656.94 -> with this change implemented let's run
659.64 -> the simulation again and see if it works
690.94 -> [Music]
701.76 -> this is much better and that's it we now
705.3 -> have a deterministic multi-threaded
707.399 -> basic physics solver
727.98 -> foreign
Source: https://www.youtube.com/watch?v=9IULfQH7E90