Quadtree Visualization for my Gravity Simulation
Vložit
- čas přidán 2. 03. 2023
- Let me start with saying that CZcams compression didn't really like this one, sorry for that.
This video shows the dynamic quadtree implementation I made for use in the Barnes-Hut Algorithm.
In this simulation 2^18 or 262144 particles were simulated.
Calculated using the Barnes-Hut algorithm, which was programmed using c++ and Cuda.
Color in the simulation is based on speed.
#simulation #programming #gravity - Zábava
youtube compression truly doing no justice
I imagine a gravity simulation would be a pathological case for any grid hashing function, so you really have to use a hierarchical subdivision of some kind.
I love octrees / n-dimensional octrees.
They make space all cut up and nice to work with.
I will act like I understand this comment( I don’t).
@@tyn_joueurswitch1505 Such a function would be optimal if all entities were equally spread out across all of space. With a gravity sim they may start that way but they will eventually all clump together into a single or small number of grid cells.
Wow, it's amazing! Great visualization
Cool stuff man. Good luck on your projects
Very cool, I haven't seen ones that resize like that and its pretty cool
Idk what all this means but i like the colours
Do you perhaps have a nice reference on building quadtrees on GPU? Cheers, nice videos :)
I'm currently building the quadtree on the CPU, and then sending it to the gpu for the force calculations. I'm also still looking for a nice reference on building quadtrees on the gpu lol
Did you change the color of the bodies depending on there force? Is so how did u implement that?
no, the color is just based on the speed the particles are moving at. I cycled through the colors using HSL.
used cuda? is that for speeding it up with parallel-processing? Im not familiar at all with cuda, how slow is it without the enhancement?
Cuda is a toolkit by Nvidia that allows you to write code for their GPUs. The force calculations were executed on a RTX 2070 max q.
mm mm mmm that sweet sweet youtube compression. I bet this is really cool otherwise though!
Very nice work, by the way....Question from someone that hasn't understood a bit from school till now: does this run real time? or else how long it takes to render? please tell us: thanks in advance
spliting the calculation using quad tree and running it on CUDA, my guess is that this can in theory run in real time.
This sim ran at around 10 fps I think
@@zarro110 10 fps is not bad at all considering the particle numbers. I recently learned that FMM algorithm can drop the calculation down to O(N) instead of O(N log N). Might take a long while before I get how it works.
@@zarro110 I see, I see, ok, thanks for answering, sorry to bog you, but on what sort of machine? But from your answer I get that it is not (easily run at) real time, thanks again
@@alvarobyrne I did this with my laptop with a GeForce RTX 2070 Max-Q and a i7-10750H
What graphics library did you use?
I draw everything using Allegro5
How do you get such high fps with that many particles? I thought the quadtree method would start causing time complexity problems at maybe 2000 particles? How did you get 200,000??
The video is not real time. It can run this many particles on around 10 FPS. I don't know about time complexity problems at 2000 particles, as quadtrees are often used to do stuff like collisions on big groups of objects.
I wrote my own quadtree structure that makes use of linked lists for quick insertions.
Are you rebuilding the tree each frame or do you have some updating logic going on ?
I'm fully rebuilding the tree each frame
@@zarro110 May I ask why did you choose to do that ?
Do you think there would be no performance benefit of some updating logic or ?
Also is this real-time and how many frames if so ?
@@rafmy-0788 I think real-time was 10 fps or so. The quadtree is constantly changing size and all of the particles are in constant motion. I'm doubtful that there is much that can be reused for an performance gain. I haven't tested that however
How long did the simulation take?
I can't remember exactly, but i do know it was longer than it should have. With this amount of particles the simulation is fast enough to do about 10 fps, but I hadn't optimized the drawing of the tree at all. As i didn't do any culling on the drawing of the tree, once a couple particles shot off the tree grew a lot and the drawing took a long time. the last couple frames took 30 seconds per frame or so, and that time was mostly spend drawing the tree.
Edit: I also had a memory leak in the drawing of the tree lol, so that also had a big influence on performance.
@@zarro110 C be like: I also had a memory leak lol
How does the quadtree actually speed things up, i'm curious what the algorithm does
The quadtree allows to make approximations for longer distances, reducing the amount of calculations that have to be made per particle. There are many resources on the Barnes-Hut algorithm that you can look up if you're interested.
Im a fellow programmer, and im wondering if I could take a look at the code behind your quadtree? Im currently building a 2D physics engine, which needs a extremely fast remove and insert for quadtrees.
Go and write one?
I’m learning C and I’m wondering how much knowledge is required to make physics sims like this.
Edit: this guy is a fruad.
I would suggest starting with a simple brute force algorithm, which can be pretty fast for a couple hundred objects and not too hard to implement.
Start raw and small, learn the libraries then build complexity.
This project is all about optimization. Fundamentals of a gravity similation is very easy.
@@sayochikun3288 yes, cache friendly physics updates
Boid expressions > Mandelbrot sets, heptopod nonlinear expressions...
Can you show the code?
The code is quite a mess and not that readable
hello sir ,,Wich song this is . I like it thank you ,and love from india 💐
Darude Sandstorm
@@zarro110 lol
Icelandic Arpeggios czcams.com/video/R6LZhcE_ygw/video.html
you can search “Icelandic Arpeggios”
Is this Hamiltonian or General relativity -Gravitational field- ; did you know I have to use Mathematica and MatLab to solve these complex partial differential geodesic equations ;
But now i have one year of studying C++/C; first time is just joke;(i thinks C++ is just Fortran or Python) after realize how is beautiful this language.
In one year I realize 80% of hard principles and problems of C++; only i need to deeev in Concurrency and Graphics API ;
This is better than sex
Barnes-Hut algorithm ?
Just google it man, jeez XD