Home ||| Art ||| Programming
Modding
This downloadable content was created as a means to showcase multiple disciplines: Programming, Art, Animation and Game Design.
Home ||| Art ||| Programming
Raster to Vector
Introduction
I created this project while working at a data company. While I was there, it became necessary to come up with a way to convert the raster files we were downloading into vector files for use in QGIS, which is a program for displaying geographical data.
The Problem
Raster data takes the form of a grid, with each cell containing a value. Vector data is usually much smaller, in this case it is just a list of X,Y coordinates that can be connected by a line to form a shape. The hardest part of the conversion from raster to vector is determining the order of the coordinates, as they must be ordered from start to finish in order to connect them correctly.
The Solution
At the time, I didn't know much about graphics programming and I came up with a CPU bound solution. First, the image is scanned line by line, and each line is divided into segments depending on the colour of each pixel, like so:
Then, for each colour, we create an index for a list of shape objects. Starting with the first line from our raster image, create shapes for each segment found and put those shapes in their corresponding index.For each subsequent line, we compare the segments in the line to the shapes we are building. Each shape keeps track of the last segment added. If the segment we are comparing connects to the last segment added in any of the shapes, we add that segment to the shape. In this way, we build each shape line by line.
As we build each shape, we keep track of the coordinates of each segment. Each segment consists of a pair of X, Y coordinates (x1, y1, x2, y1. y is always the same since it is on the same line).A shape can be described as an equal number of coordinate lists. This means that we can trace a line up and down a shape, keeping track of the coordinates along the way:
This means for every “down” list, there is an “up” list as well. Each shape in our collection has a list of these down and up lists. When we add a segment to a shape, we add the left coordinate of the segment to the down list, and the right coordinate to the up list. In doing so, we keep track of the order of coordinates to pass to the function to make our vector shape.Once every line has been read, parsed and sorted into shapes, we simply build a string of coordinates for each shape, starting at the top of its first down list and ending at the top of its last up list.
Edge Cases
As we add segments, we need to deal with certain cases that happen when a segment does not connect to just one segment above it. If a segment does not connect to anything, we start a new shape.If a segment connects to two other segments, it is either a merge or a loop. In the case of a merge, the segment has connected to two or more shapes. These shapes need to be merged together and their lists combined.
In the case of a segment connecting to two or more segments that belong to the same shape, a loop is created. The shape has a shape within it or a hole, and the inner edges of the loop become disconnected and form their own shape.
Home ||| Pixel Art ||| Programming
Octree Boids
Introduction
This project was done in my final year of university as a joint project between myself and Sam Costigan. The forest geometry was made by Sam, while I combined a flocking algorithm with an octree collision algorithm to optimize the calculation between the boids. The project is written in C++ and the graphics are made with the OpenGL library.
Flocking
This is a common algorithm that mimics the behviour of birds. The basic premise is to give boids (which are represented by the triangles) the ability to detect other boids in the area, and then have them maintain cohesion, alignment and separation.
When doing so, the initial implementation looks like this:
I modified the algorithm to have a tree like structure. The boids now only try to maintain cohesion and alignment with the boids that are above them in the tree, with a single boid as the leader.
The boids still all reference each other when checking for separation, creating an (On2) algorithm. For each boid that is added, the total number of boids must be looped over again to check for distance.
Oct-tree
This is where I combine this algorithm with another algorithm that is often used in collision checking. The simulation area is divided into 8 cubes. Each cube tracks how many boids are in it. If the cube contains above a predetermined number of boids (4 in this case), the cube is subdivided into 8 more cubes. These cubes become the child nodes of the cube surrounding it.
Once all the boids have been sorted into their respective nodes, or the node size has reached its limit, the boids only have to check the distance to the sides of the cube they are in, or the other boids in the cube. If it is closer to the side, it has to check the boids in the neighboring nodes, but otherwise it just has to check the boids in its own node.
Home ||| Pixel Art ||| Programming
Solvix
Introduction
Solvix is a tool for simulating 2d fluid dynamics. This tool is a personal project I created to help with improving my knowledge in C++ and graphics programming, as well as provide a convenient way of simulating certain types of animation that are otherwise tedious to do.
Fluid Dynamics
Most GPU fluid simulations like dye, smoke, gas, etc. are driven on implementations of the Navier-Stokes fluid equation. This equation dictates that the fluid field must go through several steps to simulate fluids:
1. Pressure: As forces propagate, they create acceleration in areas of the field they push on
2. Advection: The values in the field must be carried along the force vectors present at their point in the field.
3. Diffusion: Values in the field will bleed into their surroundings, according to the viscosity of the field.
4. External Forces: We must add an injection of values into the field to stimulate it and watch it evolve over time.
Implementation
We do this incrementally to see the fluid move over time. We use a 2D array to hold our values and represent the fluid field. The row and column index of each cell is the X, Y value of the cell. This array is used as a texture (a texture is an array of N dimensions, 2 in this case) for the GPU to work with. In my solution, we have a separate texture to hold the velocity of each cell and the amount of dye in each cell.We do each step in reverse order due to matrix mathematics, with the pressure (step1) after both advection and diffusion in order to clear divergence problems within the field. We start by adding forces that we want to inject into the field
Next we move onto diffusion. Each cell receives value from the surrounding cells, including negative values from surrounding cells that have less value. The amount of value received depends on the rate of diffusion/the viscosity of the field.
For advection, we need to take the velocity of the same cell in the previous increment and trace it backwards. From this position, we need to get the value of the cells surrounding this point and interpolate the average, then write that value to our current cell.
When we make changes to the field with diffusion and advection, we need to make sure that the incompressibility of the fluid is maintained. For instance, if a cell is surrounded by inward forces, those forces cannot have their values consumed by the cell and their components must be evenly distributed. Similarly a cell surrounded by outward forces cannot distribute more than the sum of its value.
In order to remove this imbalance, we need to subtract the divergence from our velocity field to arrive at a divergence – free velocity field. The divergence of a cell is the amount by which it is out of balance. It can be calculated using this method:
The field of divergence is equal to the field of the pressure across the current velocity field. For each cell this equation can be written as:
(p[Left] + p[Right] + p[Up] + p[Down])- 4 * p[Center] = divergence(velocity)
Since P is unknown, we have to solve for every cell in the field at once as a system of simultaneous equations. For efficiency, we use a Jacobi method to solve this. First we rearrange the equation to have P(center) on one side:
p[Center] = (p[Left] + p[Right] + p[Up] + p[Down] – divergence(velocity))/4
Then we find our divergence(velocity) for the last field using the operation in the last image. Now, starting from 0, we repeat this operation enough times to get an accurate answer, i.e: 20. Each time we replace P(center) with the answer we got from the last iteration. At the beginning of the process, P for the left, right, up and down cells will also be 0, but will change over time according to the cells surrounding them, and so on. Eventually, all cells will converge in on the right answer.Now that P has been found, all we have to do is subtract the divergence of P from the current velocity field:
divergence-free Vx = Vx – (p[right] – p[left])
divergence-free Vy = Vy – (p[up] – p[down])
And we get our final velocity field free of divergence. We should do the projecttion step once after diffusion and once after advection to get the most accurate simulation, although in my solution I only do it once after advection and it seems to work fine. We only need to do this step for the velocity field, as the dye field can just store dye as a number as high as it needs to go, until it is distributed later.
Other Additions:
If we add a simple mono-directional force and some dye on top to our simulation, the result can look quite uniform:
In order to add some aesthetic interest, we can add vorticity:
We do this by taking advantage of the divergence of the field to find local areas of curling, and then boosting those the vectors in those areas to exaggerate the curls. Since we need to use divergence, we do this step after the diffusion step, before we clear the divergence.First we find the divergence of each cell, like before. We then save this value into a texture to create a divergence field. Then in our original velocity field, we can find the divergence numbers arround each cell and use them to modifiy the velocity in the cell, using this method:
dx:=abs(curl(x + 0, y - 1)) - abs(curl(x + 0, y + 1));
dy:=abs(curl(x + 1, y + 0)) - abs(curl(x - 1, y + 0));
len:=sqrt(sqr(dx)+sqr(dy))+1e-5;
dx:=vorticity/len*dx;
dy:=vorticity/len*dy;
xvelocity[x,y]:=xvelocity[x,y]+timestep*curl(x,y)*dx);
yvelocity[x,y]:=yvelocity[x,y]+timestep*curl(x,y)*dy);
Finally, I made this project with usability in mind. The imgui library is a common developer UI and I used it here to add controls to the simulation. I also used a library called gif-h to export simulations as a .gif recording for use in other programs to trace over. You can watch the video at the top of the page for a full explanation of the controls.
Introduction
World Cloud is a concept website based around the idea of an easily accessible news aggregation site. News sources from across the internet that are reporting on similar subjects are organized into clusters. These clusters are given a name based on the subject, and these names are organized into a word cloud. This website was built specifically for my portfolio, as a way of demonstrating my ability over several services required for running websites.
Creating the concept
My initial intentions for World Cloud came from a desire to know more about the world around me. I felt an undercurrent of data and events that seemed just out of reach, one that could show me what was really going on beyond what was filtered to me by social media.My ultimate dream would be a place capable of not only gathering data, but also finding connections between them, and presenting them in a way that is accessible and human readable. However, I needed to keep the scope small for what I intended to be a portfolio piece.In the end, I decided on a miniature of this idea. I wanted to get more sides to stories that were served to me on the internet. If there was something being reported on, I wanted to know if there was any followup information, or anything contradictory that might not receive any attention. In essence, the idea was to get all angles on a news story to be presented equally alongside each other.
Making the word cloud
For this project, I wanted to touch on all elements of web design, but I also wanted to include at least one complex system built from scratch. There are word cloud libraries available for JavaScript, and I would use them in a real project, but for demonstration purposes I chose to make my own.
The two obstacles needed to be overcome was to decide on which style of packing algorithm I wanted to pursue, and how to deal with collision checking. As most programmers know, checking for collision in simulations naively usually creates On2 scenarios, where each object must check every other object to make sure they are not touching.A packing algorithm is one that deals with efficiently using a limited space. Many of these algorithms exist, but it is considered an open problem in mathematics to create one that can be considered to be the best in all scenarios.
World Cloud uses a spiraling algorithm. We place the first word in the center, then set a direction to move in. Then, we place the second word in the center, test for overlaps, and nudge the new word in the direction we set earlier. Finally, we increment the direction and repeat the process until all words are placed.This algorithm produces the least efficient use of space in packing algorithms, but still creates a satisfying word cloud for our purposes, and is the simpler and faster method.
As words are added, each one needs to check for collision with other words. As a spin on normal collision checking techniques, I decided on using a grid system to discretely place words. Since the words must be placed on a grid, we can mark grid cells as being occupied. This way, words only have to check the grid cells they are on top of in order to see if they are currently colliding with another word.I created a debug mode for the word cloud in order to add one word at a time, checking the logic at each step.
There were a lot of edge cases and optimization tests in my word cloud implementation, and there would be many more to come as I got into the world of resizing for mobile. But for now, I needed to connect my word cloud algorithm to some real data.Since I needed to keep the website costs free, my backend options were limited. For the news articles themselves, I used NewsAPI which returns a list of articles from thousands of sources when given a search parameter. Since we want to gather as many articles as possible, I send seven requests, each with a different search keyword, for example "Science," "Economics," "Sports," etc.
The above image shows the flow of data and the services involved with automating it. We start with the data pipeline that gets data from NewsAPI. Once the articles are downloaded, they need to be organized, which is the job of the pipeline.Once the data is received, articles that don't have required features (e.g: Author, title, timestamp) are removed, as well as duplicates and spam. Then, all articles are run through a weighted policy model to sort them into clusters based on like terms. These clusters are given to another weighted policy model to give each cluster a name based on the titles of the articles within. This process is done using models from the scikitlearn library, which is a python machine learning repository.The pipeline exists as a Docker image that is run every 3 hours. An Azure container is responsible for pulling the image and running it on its container, from which the output is saved to an Azure storage blob as a small JSON file. When accessing the website, the Vercel server requests the file from the Azure storage and serves it alongside the normal HTML document.
Now that we have our formatted data and our word cloud, putting them together creates these clouds of information that can easily be glanced over to get the latest story. By clicking on a cluster, the articles are revealed on the right hand side. In this way, if something is being reported on, all articles on that subject are placed alongside each other, and any additional information omitted by one story can in theory be given by another.
Working with React
React is necessary for making reactive interfaces. We need to wait for certain elements to reveal their size and for data to arrive before drawing things. In the case of World Cloud, the word cloud is dependent on the size of the window and the "words" are dependent on the downloaded data. For this reason, we need to use React's State and Effect functions to be able to render UI elements that depend on other conditions.
The entire word cloud component is called inside of an async function, which waits for the data to return before passing it to the word cloud component. The above diagram is a simplified version of the execution process.Once we have the data, we need to determine the size we are working with. Using a React Effect, we can run code after the first render is complete. After the first render is complete, we can create a resize observer that checks for window resizing. If the window is resized, we can update a React Stateful variable. When a React Stateful variable is updated, the window is re-rendered. Thankfully, the creation of a window counts as a resize, so the resize observer triggers on the first render, aka the same render it was created.Now that we are on the second render, the size of all the elements that were created on the first render are available to us. We are using a canvas element to denote the size available to the word cloud (and to be able to draw on it in debug mode), so we send the dimensions of the canvas element to the word cloud function. The word cloud function is called during an Effect at the end of the second render, so we can interact with various variable references in the code outside of the render time (again, this is a simplified diagram). Once the word cloud function is complete, we update the state again with the word cloud data, so we can render one last time to display the word cloud on screen.There is more to the word cloud component, like statefully clicking on words and keeping track of which words have been clicked on, and which is currently selected, but the main process is roughly outlined here.
Possible features and imrovements
The inspiration for this project was borne from a feeling of being corralled in the digital landscape. Algorithms are designed to place a loudspeaker on certain topics, and one widely reported story shown in one place may not garner much attention elsewhere. World Cloud is a tiny attempt to boost topics that I would not have otherwise seen in the places I usually frequent, and in that small matter, some success has been found. However, the feeling remains, since news articles are still owned by large multimedia corporations, and simple news reporting is not the full picture of the world.If I were to continue building World Cloud, I would first start to look for more sources. The current article gathering system is limited to only a few requests per day, and these requests can only look back a short distance into the past. Building up a more robust series of services, and thoroughly experimenting on different frameworks of data collection would be an important first step to improving the quality of information shown on World Cloud.Another useful addition would be to upgrade the historical and database capability of World Cloud to be able to show the history of news cycles over time. By saving data to a database and creating a relational system for topical clusters, we can add a timeline as a setting to allow for visualizing events over a user specified amount of time.Lastly, a login system to allow users to create personalized World Clouds. blocking certain websites and filtering or searching for certain topics would be a useful way to extend the functionality of World Cloud, by allowing users to quickly glance for updates at subjects they are interested in.