Laplace growth & Dielectric Breakdown Model with a fast simulation algorithm (Lightning creation)

   1764   5   4
User Avatar
Member
13 posts
Joined: Sept. 2016
Offline
Greetings!

I have been working a lot in the previous month on my VEX skills and learned a lot about programming in general. On my path to become a VEXpert (haha..), I wanted to create a sim, based on an algorithm. The idea came after watching Entagmas video about space colonization.
So I have decided to make a dream become real and check for algorithms on lightning creation. I have found some “easy” methods, but at the end, there were those two things called "Laplace growth“ and ”DBM = Dielectric breakdown model“. As a former physics student, I wanted to make it real and implement the effect into Houdini.
On my research, I have found a ”fast and easy" algorithm for the DBM on this page: http://gamma.cs.unc.edu/FRAC/laplacian_large.pdf [gamma.cs.unc.edu]

Implementing the algorithm will take a while, because of the special thematic it describes (how does a lightning evolve, and what exactly is the DBM?), but I have first results and added the “core” to Houdini as a solver.

The general DBM algorithm is working as followed:
1) Calculate the electric potential φ on a regular grid according to some boundary condition.
2) Select a grid cell as a ‘growth site’ according to φ.
3) Add the growth site to the boundary condition.


especially:

1) Insert a point charge at the origin,
2) Locate the candidate sites around the charge. On a
square 2D (3D) grid, these would be the eight (twenty-
six) neighbors,
3) Calculate the potential at each candidate site according
to Eqn. 10.
4) Randomly select a growth site according to Eqn. 12.
5) Add a new point charge at the growth site.
6) Update the potential at all the candidate sites according
to Eqn. 11.
7) Add the new candidate sites surrounding the growth site.
8) Calculate the potential at new candidate sites using Eqn.
10.


In my Solver, I have created the boundary conditions for each of the given steps. I have some groups, some attributes, some arrays, calculations and so on.

My lightning follows a path randomly chosen based on the distance to my endpoint, and thats why it, in its current state, doesn't fork. The probability calculation, well both equation 10) and 12) are not yet implemented. I did not fully understand both equations, but after searching for help by my friends, I am able to calculate the potential of each candidate site correctly now, and to calculate the probability “weight”.

After implementing both equations, I will need to overcome one of my biggest problems. I need to work out a method, which allows me to randomly choose a point based on its “weight” of becoming a growing site. This is something I'm currently working out and searching for on the internet. I had a simple idea, which would work with 10-20 points, but won't with 1,5m or more..
In case, there are some math brains outside there, or in case someone knows a site or an expression in VEX which can help, let me know please

Beside of that, I will also need to figure out a good way to render out my lighting, and to not work on a huge grid of 256^3 (~16,8m points), but to only add points to my scene if they are treated as a potential growth candidate.


I will update this post as soon as I am getting forward with the equation. Until now, I have spent nearly 3-4 days on reading about Laplace and DBM, also understanding the faster algorithm, and ~1 day to create my current Houdini scene.

Greetings,
Gyula

ps.: Image shows the current “lightning” on a 2D grid.
Edited by kulli - Nov. 25, 2017 15:28:48

Attachments:
Bildschirmfoto 2017-11-25 um 21.28.18.png (401.6 KB)

Check out my profile: https://vimeo.com/user750491 [vimeo.com] Feel free to leave a comment if you like a video :)
User Avatar
Member
13 posts
Joined: Sept. 2016
Offline
Well, a short update on my project.

I have started a few times from zero because of circumstances of ineffective solvers. Its really hard to work on points, and I need to wisely manage groups, arrays and my attributes.

Easy example: In case I want to get the highest/smallest potential of my candidates group, I need to save those potential on a point called “array point” and to run a max/min function on the array in an extra point wrangle. Save the values on the same point, get another wrangle for my candidates and get those values returned with the point function.
I would like to do this in only one wrangle without an extra array, but didn't found a solution until now. I will check for one later, I really want to get my algorithm to work before optimizing.

The next great step was implementing the correct equation for calculating the chance and the potential on each candidate. Therefore, I needed a few days and additional books like “Fractal dimension of dielectric breakdown,” Physical Review Letters, vol. 52, pp. 1033–1036, 1984. but it helped and am getting better results.

My next step is to solve the problem of weighted randomness and implementing it in Houdini. This took me already some hours of research and I watched some (great) videos about probability and how to calculate them, but I still need a little more to fix the problem. In case I find a solution, I will be able to put a fast end on this project and to work with the algorithm for several Laplace growth effects.

Last but not least, a new image showing my last result running the solver. I have changed my setup and I am now working on a grid with the first point charge in the middle of my circle. End the end, it should look like on of these [csdl-images.computer.org] images. To be exact, the middle one b) is using the same algorithm..

Greetings, Gyula

ps.: I can't get rid of the feeling, this would be way easier to implement in python. I really need to start working with it in Houdini!

Attachments:
laplace_2.png (406.2 KB)

Check out my profile: https://vimeo.com/user750491 [vimeo.com] Feel free to leave a comment if you like a video :)
User Avatar
Member
13 posts
Joined: Sept. 2016
Offline
Two days gone,

I have finally overcame the biggest issue, the weighted randomness. I have created my own method for picking a random point based on its chance. E.g.: Point A got a 20% chance, Point B got 30% and Point C got 50%. Its obvious, that point C would be chosen as many times as Point A + Point B. And Point A would be chosen only twice if I roll the dice 10 times.
Thats easy and nothing new, but imagine I want to calculate the chance based on the distance to {0,0,0}? Sure, I get distance, and can save it for every point, but now those points further should be selected more often than points near to {0,0,0}. And in case, one of my points got selected, the whole bunch of chances need to be recalculated. (In case I have my first 10k selection, the chance for selecting points near to {0,0,0} will increase.
So, after figuring it out, I have implemented it into the algorithm and finally, I got those results I wanted to see.

Here it is, a small image of Laplacian Growth! I want to point out, that this is a 2D model with a Grid running only 40k points. I will need to optimize the memory usage again to save sim time, but again, as I mentioned before, this is a physically correct model of Laplacian Growth and the Dielectric Breakdown Model!

Next step is to bring it into a form of worth presenting and to start working on my 3D lightning model.

Greetings,
Gyula

Attachments:
Laplacian_growth_2.png (201.1 KB)

Check out my profile: https://vimeo.com/user750491 [vimeo.com] Feel free to leave a comment if you like a video :)
User Avatar
Member
2545 posts
Joined: Sept. 2007
Online
Having your results and write-ups is excellent. Thanks for sharing them!
I'm o.d.d.
User Avatar
Member
13 posts
Joined: Sept. 2016
Offline
goldleaf
Having your results and write-ups is excellent. Thanks for sharing them!

Thank you for your nice comment, you are welcome!

It's been a few days since I updated this project, but I had to do some other stuff and needed another research about the physical part of the algorithm. Finally, I am sure, that everything is fine with my algorithm and the tweaking has ended. I managed to run the simulations 4-5 times faster than before and I got really nice results.
It's really interesting how the they change in depending on the chance calculated in step 4), which can be regulated with N. I have attached a new image showing my results.

I am going to render all three simulations to showcase the difference and I will do another, more artistically one. Like ice crystals on the window or on the ice cube, something in this direction

Beside of that, there are still few steps to do for my original lightning goal. I have noticed (after a looooong time) that the algorithm works as it is, but I really can't regulate where to grow or not to grow, or which direction to choose. The short way: My lightning won't hit the tower without further tweaking.
This will be the next step, and at the end, I will have a nice project file with a lot of regulators to fast simulate any kind of laplacian growth

Greetings, Gyula!

Attachments:
Dendrit_N_Difference.jpeg (282.7 KB)

Check out my profile: https://vimeo.com/user750491 [vimeo.com] Feel free to leave a comment if you like a video :)
User Avatar
Member
13 posts
Joined: Sept. 2016
Offline
Hey,

this is my (hopefully) last post regarding to this Project. I have successfully finished, as mentioned before, the Solver, and was also able to create a digital asset with different options:

1) Create a Grid (2D or 3D) which will work as the point cloud for the pattern to grow. The user also can plug in a given point cloud (Created on a geo surface e.g.), but those points shouldn't be placed randomly all over and should at least have an even distance to each other for being physically accurate (although I find results with at least a little randomness visually more powerful!)
2) Create Obstacles like boxes or spheres or other geometry. (The user simply needs to plug them in). Different values can be set for the rejection effect. This allows the user to optimize the simulation
3) Create a point as “aiming location”. This way, the user can add a point and set different values for the amount of attraction. Being able to do so will lead a lightning or other sim in the given direction.

This is it! A video about the creation can be found here [vimeo.com]. Another one showing a lightning bolt [vimeo.com].

There are a ton of other possibilities for the pattern. I am experimenting in a 3D growth behavior and a RBD object breaking apart according to the growth pattern (This is gonna be a nice one!).

Greetings,
Gyula
Check out my profile: https://vimeo.com/user750491 [vimeo.com] Feel free to leave a comment if you like a video :)
  • Quick Links