[EDT] – Computer Science Rearing Its Ugly Head

Click here to see the final version of the logo, with the resolution reduced in half. Remember, this is intended to be displayed on a vertically hung TV (so you might have to tilt your head to the left to see it)!

Here’s How I Did It

Because I wanted the lines to be directly controlled by the edge of the logo, and not pass through it, I needed to make a list of points that the logo existed at. Easy enough. I looped through the pixels, and checked the alpha layer. If the alpha of a pixel was not 0, but one of the pixels around it is close to 0, we are at an edge of the letter. I stored all of the x, y coordinates of these pixels. This resulted in 25,000 pixels, or 50,000 members of my array. I then set a “particle” to launch from the edges or the middle region, let its trail persist, and had it die when it reached a letter. Voila, lines that converge on the letters EDP.

Here’s the problem: a list of 50,000 elements is inherently inefficient. Especially if I’m iterating through that list 60 times a second. But I had to, because I had to constantly check to see if any of my particles had collided with the logo. 

Problem #1:

When I build my list of edge pixels, it’s not built in a particularly useful order. Picture pixels are stored left-to-right and up-to-down. So when I scanned for my edge pixels, this is how they’re stored. Their position in the array doesn’t correlate to whether or not they are an outer or inner edge of the letter, or even what letter they’re associated with.

Solution #1:

Well, I could find a way to cleverly sort this list. Because the letters function approximately as circles, I considered sorting the array so pixels closest to each other were closest to each other in the array. Then I could at least know where I was in a letter based on the position of the array. Alas, this is a sorting problem. I should know how to do this effectively. But I didn’t have enough time to try it and be wrong about it. (If you are curious about how to do this effectively, my alma mater has a generous resource on sorting techniques: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/sorting.html )

As a result, I controlled the spawning of my particles so that I could make sure they interacted with the letters correctly. I had them start on the edges of the frame only. Great. Except these letters have holes in them that these particles would never get to coming from the outside. To solve this, I’d prefer to start the line on one point on the inside of the letter and end it on another. But I didn’t have the information to know which points these are. What I could do is create an imaginary box that surrounds the entire logo and tells particles to spawn inside of that region just as much, if not more, than the edges. Maybe the particles will spawn inside my letters, but they’ll die before they leave. So I drew the logo over top all over the lines to cover up these mistakes. It’s not perfect. But it works.

Problem #2:

I am checking 50,000 elements 60 times a second. That’s 300,000 elements a second. And I’m checking each of those elements against a particle in my system. My system could have 100 particles. Luckily, I only allow the program to loop through the edge-detection list once a frame, but it’s still a lot. That’s 3,000,000 comparisons a second. And the program noticeably lags when it encounters that burden.

Solution #2:

My father happens to be a data storage engineer, so I know there exists clever solutions to minimize which elements of this list I need to compare against each time. For one, somehow, my list ended up having duplicate pixels. I don’t know how. But I made sure to have my program loop through the array and delete any duplicates. I also could have easily divided the list into three parts (by letter, essentially) and then only compare to one letter’s pixels depending on the position of the particle and its likelihood to be interacting with that letter.

But when on a time crunch, the easier, more intuitive solutions, become more appealing. So why not just lower the resolution of collision detector? So I went in and deleted every other pixel. Suddenly, my 3,000,000 comparisons per second problem became a 1,500,000 comparisons per second. 

I then decided that allowing the program to have 100 particles going at a time was unnecessary. So I made the program stop producing particles after it had 50 going. (Particles are deleted once they collide with the letter, so it’s still allowed to make more. It’s just not allowed to have 50 going at once.) My program only had 750,000 comparisons a second. I can live with sub-million comparison territory. I can also live with the program not lagging when it reaches a minute in.

Computer Science is Creativity

Don’t get me wrong, CS is probably one of the most creative STEM fields. Every time I program something, I feel the part of my brain going that goes when I’m composing. It’s strange. But doing both the creativity of art and the creativity of CS at the same time is a TRIP. One I enjoyed. And one that gave me a good night’s sleep afterwards.

– Dewey

Leave a Reply

Your email address will not be published. Required fields are marked *