XMas-Tree-Explosions (X-Mas Tree animation - celebrating New Year's Eve)

Current version: v2.5, see changes in the end of this file

License (sort of)

I don't want to bother with an actual license here, but rather ask you to respect the following basic rules:

1. If you want to use my cylindrical coordinates, go ahead. As these coordinates on their own don't make an animation (and I don't have any ownership on Matt's original coordinates), they are totally free to use as long as you don't break any licensing terms that Matt might have on them.

2. If you want to (re-)use my normalization to cylindrical coordinates it would be nice if you gave credit because technically speaking this algorithm is my own creation. If you want to avoid this and are fine with coding yourself (and want an even better result) look for official and proven algorithms elsewhere (Wikipedia for example).

3. If you want to improve this animation, go ahead and do as you please. It would be nice if you gave credit, though. But I don't claim that this is the ultimate explosion/fireworks animation and I would be very pleased to see that I inspired other creatives.

4. If you want to reuse the idea behind my distance-matrix in any form or shape, go ahead. That might have been a novel idea (I don't even know), but nothing I can really claim ownership on (or I wouldn't feel comfortable doing at least). Give credit if you want.

5. Don't distribute or use my scala code if you can't add something substantial to it yourself. If you improve the code, see point 3. If you just regenerate the seeds and want to see the results yourself, that is fine. If you run the code on your own seeds in order to submit your animation, there has to be something novel either about your seeds or the result.

6. If you made one of the mentioned tree-illumination simulators and are on the lookout for sample animations you can freely use any samples you find here that aren't of my latest iteration! I would really ask you to not put the latest iteration out there because that are the ones I might submit. So, currently you can freely use any v1 animations. Clearly, I can't prevent anyone from running any of my latest creations on any simulator, but I don't like the idea of them being one preset sample on any of the simulators. Please give credit by linking to this project such that visitors of your simulator can find my description and the generating code. All animation files in the root-folder are v1 that I left there for legacy reasons in case anyone linked to these files prior to my v2 update.

Guide

I finally decided to create a guide on how to use this generator as I know the tricks myself but they aren't obvious here and there.

1. Generate the normalized coordinates:
   1. take coordinates in x,y,z-format and load them into the first sheet of normalize_coordinates.ods
   2. in sheet two, set F1 and G1 to 1, then set F1 to the value of J1 (paste as number)
   3. then adjust G1 slightly (to something within [.95, 1]) to see which points reach out of the cylinder first
   4. use the ids of these points on sheet three to let the spreadsheet move the center
   5. if done correctly, applying the same steps as in step 1.ii on sheet four will result in a smaller rescaling factor in F1 and again adjusting G1 will cause opposing points to reach out of the cylinder first.
   6. set F1 again to 1 and copy the columns F to H into whatevery file you want. don't copy the upper "header columns" and stop at whichever id your initial data set did. the sheet supports up to 1000 entries, Matt's coordinates stop at 500. H1 lists the highest z-value in the normalized data set.
2. Generate the seeds:
   1. input the coordinates from step 1.vi into the second sheet of rand_seed.ods where it says GIFT. this spreadsheet is modeled for exactly 500 entries and 40 seeds, you might have to adjust this manually
   2. set the threshold in B2 to whatever radius you like most
   3. set the seeding frame number in B1 to your number of seeding frames
   4. on sheet one, let the application recalculate all numbers until they show numbers that you like. my criteria are:
      1. I1 is below the threshold (configurale on sheet two) and is shown in green (if conditional formatting works), that means that all events happen close enough to SOME LEDs to be visible at all
      2. H1 ends in (1) or (TRUE), that means that all x-y-coordinate-pairs are inside the cylinder and that the threshold condition is met
      3. check the "Frame"-diagram to see if there are large temporal gaps in between the events
      4. check the "Hue"-diagram to see how similar the colors will be, if the points are distributed well across the diagonal, there will be a lot of different colors
      5. check the untitled diagram to see what colors will be visible at what frames. x is time, y is color/hue
   5. if you are fine with your seeds, copy column W of sheet one to a file (usually called "seeds.csv") and copy column CJ of sheet two to another file (usually called "dists.csv")
3. Run the Animator-class:
   1. most options that you might want to change from one run to the next are configurable from command line. it is usually not necessary to modify the code if you are not trying to change the way the animation works
   2. the following command line parameters are supported:
      • -d=<filename> specify the distance-matrix file, defaults to "dists.csv"
      • -s=<filename> specify the seeds file, defaults to "seeds.csv"
      • -o=<filename> specify the output file, defaults to "explosions.csv"
      • -l=<number> specify the number of seeding frames aka the animation-length, defaults to 150
      • -i=<number> specify the seeding interval, the number of frames per seeding frame, defaults to 12
      • -e=<number> specify the length in frames of an expansion phase, defaults to 20
      • -f=<number> specify the length in frames of a fading phase, defaults to 180
      • -r=<number> specify the radius of an explosion in tenth (e.g. 5 means 0.5), defaults to 0.5
      • -b disables the pattern collision avoidance (aka enables the birthday paradox on patterns), defaults to on
      • -c disables the flickering (causes a constant fading), defaults to on
   3. the scala code will simply error out on any false useage, I haven't bothered with making it fool-proof
   4. you can combine distance-matrices and seeds that you haven't generated in the same run, this will keep the timings and color sequence of the seeds file but adapt the spacial information of the dists table

Concept

The idea of this animation is to somewhat combine Christmas and New Year's Eve by showing little colorful explosions on The Tree. I already had this idea (or at least a very similar one) last year but I hadn't wanted to fiddle with python as I can code in python but it's not my language of choice. Now that we only have to produce csv-files I can use the tools I excel at and just submit the resulting file.

The flaw in the GIFT-format (and why that is a good thing, this time around)

Matt mentioned several times in his video that the LEDs could form any kind of shape and although we don't have other shapes to work with right now, flexibility is great. But the format that he defined to store the 3D-positions of each LED-light isn't exactly adapting to the different possible shapes in the same way. Based on the coordinates in the standupmaths Git-repo, all x- and y-coordinates are capped at -1 and 1. As those points in space aren't distributed equally, the y-coordinates in fact never touch these limits at all. In contrast the coordinates that the Harvard-repo offers are less normalized as here the y-coordinates are capped at -1 and 1, while having the x-coordinates scale accordingly, leaving some LEDs at x-coordinates below -1 or above 1. That's not normalized! Because if we switch from a tree-shape to something like a wall-mounted shape (where there is almost no depth/y-variance, the x-coordinates would be all over the place. If we want normalization, we have to define rules that apply to every direction. On that note, having the z-coordinate start at zero is great, but it hasn't got an upper limit. That again is not normalized! It is applicable to this shape but if the GIFT-format should apply to any random shape, we can't make assumption based on the shape we are concerned with today. An actual normalized format would make sure that all three coordinates are capped at -1 and 1 and that the two directions with less variance would be scaled accordingly and probably centered.

Now, as we are talking about a tree-shape this year (again), we can definitely make use of this format, as having all three coordinates normalized adds other issues: If we had a bounded (unit) cube, approximately 50% of the space would feature no LEDs and hence attempting to animate anything in these sparse locations would have no visual outcome. So, although I have to say, that the GIFT-format isn't universal enough to cover all shapes of LED-light-arrangements, it is usable for this exact scenario.

Applying a second normalization

So, as I said, the format fits our needs, but the given points don't form a cone. Or - to be more precise - the points might, but the format allows other shapes as well, because the coordinate-space forms a quadratic prism and not a cone. Furthermore, there are irregularities as they are human-mounted on the tree. So, what I do first is rearranging the given points to form a cylinder. The basic idea: Ignore the z-coordinate and project all points onto a plane, then find the smallest circumscribed circle to cover all the points. Based on the center of this cylinder, all the points would be (slightly) shifted compared to the given 0/0/0-origin. But if we ignore that the upper half of the cylinder is mostly empty, we can create almost any patterns in this cylinder and likely hit at least some LEDs. The smaller the bounding shape is the more likely it is to hit something by randomly shooting in the given space. For a cone-shaped tree a cylinder is a good approximation, but I can only do this, because the shape is fixed in this scenario. If we had another shape to work with, I would have to modify this step! That is the point were I am grateful for the GIFT-format as it perfectly fits the use-case. Side note: You could also try to find the smallest bounding cone. The problem is that this gets tougher in two ways. First, the base circle will probably be larger then the base circle of my cylinder in order to find the cone with the least volume. Because if you used the smallest circle as its base, the slopes would never meet at one point while still including all LEDs. That is a complex problem to solve. The second issue is that generating (uniformly distributed) random points in a cone means you have to take the different widths at different heights into account. That is probably the easier of the two problems, but I didn't wanted to bother with the first problem and - as you see later - I won't even generate random points in a circle even if this is just as easy as uniformly distributing points in a cone. If you want to do this, go ahead, I prefer easier formulas at the expense of regenerating the data if it doesn't fit my needs.

Now, there are algorithms to find the smallest circumscribed circle, but honestly I was too lazy to bother with them. I rather created a spreadsheet that probably took me longer but was more fun (and likely could be more performant if I wanted to normalize another set of points, it just requires some manual editing). The spreadsheet can perform more than one operation depending on the kind of "defect" in the input data, but most of the time you want to use all in combination. First, the spreadsheet can do the standard normalization that the GIFT-formatted points should already come in, so, scaling all x- and y-coordinates to [-1, 1] and moving the lowest point to z=0. But then, the spreadsheet can also find the point(s) with the largest x-y-distance to the z-axes (with some manual help). That lets me rescale the points to form a cylinder with radius 1. Scaled to form a cylinder the points technically are still normalized based on the GIFT-format-definition, no point can exceed the range of -1 to 1 while still being close enough to the z-axes. But the points likely are also shifted. That results in the situation that the necessary down-scaling is larger then it would have to be. So (with some tweaking of the scaling factor) you can find three points that have the largest distance to the z-axes, input their ids into another sheet and let the spreadsheet determine their center point and shift all points to this new origin. Again, scaling to get a cylinder with radius 1 and my custom tree-specific normalization step is done. And, it might not be perfect but pretty close to perfect. The necessary down-scaling indeed is lower (1/1.11 instead of 1/1.16). And if I change the last rescaling factor only by a little, there are two points sticking out of the cylinder that are located in two opposing octants (I chose to use octants instead of quadrants to get a better feeling for where the outer most points lie, to be able to select three points for the shifting that are as far apart from each other as possible), indicating that the center should be pretty much dead on.

Alternatively, implement Welzl's algorithm and input the points sorted by their distance to the z-axes (in descending order) to get the most performance, if I got Wikipedia right. (source)

Defining the "seed" of my effect

So, the idea of my effect is some form of explosion pattern. At random points in time at random locations in this cylinder an explosion with a random color will take place. Explosions are divided into two phases: At first each explosion will increase in size. Starting with a specific 3D-location (the explosion's "seed", if you will) a sphere of some color will grow over some frames. Then, after the sphere reached its maximum size, the sphere will stay at its position but slowly fade to black again.

To accomplish this I created a spreadsheet that generates a bunch or random numbers and already preprocesses them a little. The spreadsheet generates:

• a random time frame to start an explosion. The animation is split into 100 seeding-frames (the resulting animation will definitely have more than 100 frames, that's just the "frequency" at which explosions can start), several explosions can in theory start in the same frame. You could increase the "resolution" if you either want a longer animation or afterwards shorten the actual animation-speed.
• a random x-coordinate and a random y-coordinate. That means that some points can be outside of the cylinder. I chose to re-calculate the seeds until this doesn't occur (because I don't want to bother with more complex formulas) but you could also just outright ignore any seeds that are outside the cylinder. I would advise against just using them, because that would cause the portions of the tree that point to the corners of the coordinate-system to show more animations than the portions facing the edges and also will have more "incomplete" patterns.
• a random z-coordinate. The z-coordinate clearly has to be scaled to the actual height of the cylinder. That's where an actual normalized format would be beneficial, but as I said, it would cause other issues here and there for this shape. All random coordinates can't lie in the outer 0.2 in each direction. So, x and y are capped at [-.8, .8] and z is capped at [.2, max_height-.2]. That is done to reduce the number of incomplete patterns further. Still, the cone shape will cause some explosions in the upper (empty) space that will either don't show up at all or only on the very edges of the tree. That's another reason why I chose to re-generate the random values until I got 25 valid entries.
• a random hue. The initial color of each explosion will be at most saturation and value (in HSV-color space) because the fading phase of each explosion will already introduce darker colors. There's no reason to produce almost invisible effects and then let them fade on top of the already dark starting point.
• The spreadsheet then uses those random numbers and the (two times) normalized coordinates to generate intensities for the three base colors and a distance matrix for all coordinates and the generated seed locations. Using this distance matrix (and a visual representation of the time distribution of the seeds) I again regenerate the random values until all explosions touch SOME LEDs and the explosions aren't clustered too much in time. This is the final output-format of my spreadsheets. That in fact means that the actual code that generates the animation never uses coordinates in the first place. It only uses the distance-matrix and the time- and color-imformation. All the normalization and distance-calculation is done before passing the data to the animator.

Calculating the actual color-table for the tree

Now, we are at the point were spreadsheets can't help me any further. Because now I have to calculate the color values of each LED and every frame given both of my inputs. And that means to process 500 coordinates and 25 explosion seeds together with temporal and spacial distances and color fading effects. Furthermore, each of the seeding frames will be followed by some number of "evolution-frames" where the animation will undergo a fixed and (for these frames) uninterrupted process of steps to form the wanted animation. But the basic problem is just that LibreOffice only has 1024 columns but you need 1501 for all the color codes for all the 500 LEDs. And LibreOffice in general just don't likes to be used for tables (with formulas) of these sizes.

The problem for generating animation is that I don't really know the update frequency of the new algorithm. Last year's algorithm pretty much ran at some speed mostly defined by the animation's computational load. If you had to compute a lot, the animation would slow down. But this year the RaspberryPi just reads in lines and pushes these numbers out to the lights. The Harvard-code file contains an fps-declaration but the script never actually sleeps for this amount of time, so either someone tested the script and annotated the observed execution-speed or this declaration is deceptive and the script runs at a different speed. To not overshoot, I will work with the assumption of an animation-frequency of 30fps. If the RPi is faster you can always integrate a sleep command (to cover the difference between a 30-th of a second and the time it takes to process one frame), or if it is slower, the animation will just take a bit longer. But given that the Harvard script says "approx. 60fps" at one point, I think the RPi should be capable of 30fps at a minimum.

This will cause the animation to start quite abruptly, but I decided to design the animation as an infinite loop. Each explosion can last long enough for another explosion to already start (ideally I want to have at least three explosions happen at any given point in time, including the ones that are already fading away), so in order to have an infinite loop, right at the start several explosions have to be at different stages in their life-cycle right away.

What happens if two explosions appear close to each other? Well, I have to define this as my seeding doesn't prevent this from happening and we need some deterministic behavior in case this happens. So, as simple as that, we add up all their color values. Obviously capping them at 255. Meaning if a yellow explosion happens near a blue one, we will get some white areas. But that's how light works, so that's totally fine.

Now all we need are a few parameters for the actual algorithm to generate the color-table out of the input files. If we know how long an explosion can last at most, we first duplicate the last few seeds and prepend them to the start of the time scale. That is done to simplify the generation of the individual color-values at the wrapping point were the animation will start back from the beginning. We just start early, compute a few frames while discarding the results, then start actually logging the values but redo the frames that we already calculated in the beginning to get this infinite loop (the first frames can't have any fading patterns, we only get those if there are seeds before that point in time). Then, I want to see the explosions expand for two thirds of a second (meaning 20 frames) and fade over the time of at least 5 seconds (150 frames). The size or an explosion should be .5 in radius. (Yes, that is quite large, but my seeding process warned me of a lot of seeding attempts that didn't show up when using a smaller radius. If I used a more shape-aware random seeding the problem might have been not that severe, but as I can't test the animation myself, I went with the safe way of larger patterns.) The only missing parameter is the number of frames per seeding. If one pattern stays visible for about 6 seconds, and we have one new seed every four seeding frames (on average), and we target three visible explosions all the time, we need a new explosion about every 2 seconds, resulting in one seeding-frame every .5 seconds. Making the whole animation last 1500 frames or 50 seconds (100 potential seedings) if executed at 30fps, resulting in the animation to loop roughly every minute. You could easily make longer animations by adding more seeding-frames with more seeding-events. But that is only a proof-of-concept. And as I don't have such a tree at hand, I guess some of the parameters could make use of further tweaking once I saw the actual animation on the tree.

The actual generating code is rather boring. For each frame, for each LED and for each seeding-event, check the temporal and spacial distance and add some color-component to this light's output if needed. Then, cap each light component at 255 in case this limit is exceeded. Then, print the data into a file and we're done. I could use python, but I chose to use scala because of my greater familiarity with this language. If this project wouldn't require parsing two files to write a third, I would have included a link to an online-editor/-execution tool, but that won't really work here. If you want to tweak the parameters, you have to have scala installed.

Update v2

After several simulators came to life and I was able to judge my animations visually I made a bunch of adjustments to my parameters. Still, I have no information on the animation speed. I'll still use 30fps as my assumption/target going forward.

The new v2 animations are meant to run for exactly one minute. The seeds are shifted such that the first seeding frame is actually used by at least one explosion and at the end of the animation is a maximum gap such that the looped animation starts rather smooth with as few fading explosions as possible. That change really was just a shift/wrap in the time information, the seeds aren't manipulated any further. If you look at an infinitely looping animation other than the starting point nothing changed.

I decided to have one explosion every 1.5 seconds (on average), hence, increasing the effect density so to speak. Most of the tree is off most of the time, so having more active effects overall improves the visual quality. And the explosions take longer to completely fade. As I use a linear fading, that means that (especially in a not completely dark environment) the fading will appear to end quicker than that but at least the colors stay visible for longer than before. In addition to the more seeds I increased the seeding frequency (or decreased the interval between two seedings), hence, increased the temporal resolution of the seeding. Again, to improve the visual quality by letting the explosions start more "randomly". Still, the resolution isn't exactly high, there are 16 different seeding frames while one effect takes place, to give you a feeling for the resolution and the options for two effects to fall together in time. But I am quite happy with the results.

Based on an issue/feature with one of the simulators that appeared to let the LEDs flicker instead of shining with a constant brightness - what might be intentional or a bug in the update routine, but I can't tell for sure - I decided to integrate this effect on purpose. Every fading explosion will flicker slightly. (Credit goes to @leukipp.) But only one eighth of the maximum brightness to prevent (most) health issues. But neither am I a doctor nor do I suffer any form of epilepsy, so I can't really quarantee that this animation is perfectly safe. If in doubt, rather watch the v1 animations on any non-flickering simulator.

And I added other forms of quality measures to my spreadsheet. But with the new simulators I discovered that these numerical quality measures can only tell you so much. Sure, I could add even more diagrams to the spreadsheet that show me the spacial and temporal effects even better (or in combination), but at the end this is all personal preference. And I rather watch the animation in a simulator than checking my numbers for critical thresholds that in the end let the animation appear to predictable.

Update v2.5

Several small (but some important) changes this time.

First, I finally conform with the format in the Harvard-repo by choosing upper case column headers. The pull request isn't through yet, but we will have an officlal format definition soon that would make my headers break the runner code. To act pre-emptively here and to no longer be the odd one out, I adjusted my format.

Second, I introduced some logic that will make perfectly simulaneous patterns impossible (by user choice) if there aren't too many effects in the intermediate representation. This code segment will never activate on dense effects as these would be made far too rhythmical. For my choice of parameters, preventing perfectly simultaneous events usually only introduces slight adjustments to very few events keeping the overall pattern more or less unchanged.

Lastly, I modified the scala code such that most options can be set from command line. See Guide for instructions.