Wrapping Up!

It's the end of the semester, and so the end of the time we allotted to work on Sphericles. A lot has changed regarding its inner workings and performance since the last post: lower poly spheres, enhancements to LOD, less updates, etc. In the end it became what we set out to make, but like with all engineering there's tradeoffs - in this post I hope to go over all of them and what they've taught us.
But first, it's time to present it to the world!

Sphericles

Sphericles is an audiovisual experiment where you can fly around a space full of user-created objects hunting for "Sphericles", an object that is different from the rest. We've made it as simple as possible to add objects, and the entire thing is done through the editor, giving the user total creative control. We've made tutorials on how to make objects, and we'd be honored if people played with it/made things. NOTE: It requires you to install Unreal 4, which is fortunately free now!

Click these to learn more and see it in action!

INTRODUCTION

HOW TO ADD OBJECTS

GITHUB PAGE


Wrap Ups:

Design

From a design standpoint, it's *there*. We set out to make an interactive audiovisual experience where you fly around, see interesting user-created objects, and try to find the "one" object known as Sphericles.
The only thing I'm not pleased with is that I'd have liked to have more objects, but weaker computers could not run it. Also it was a stretch but I'd have liked to implement a editing tool to simplify the creation and distribution process.

Technology

Working with Unreal 4 was a lot of fun. I'd used it before, so I was pretty comfortable. It was Amier's first time with it, but he caught on extremely quickly and started churning out content. We programmed the entire project in the Blueprint interface, a visual-flow-chart system. Through this we implemented the player, the gamemode, and most importantly the Caplet concept, allowing us to make creative objects out of spheres by dynamically generating between them, and made it fast despite using only the Blueprints.

Sound

Sounds were also interesting. Due to a hard limit (maybe not a hard limit, but it would stop playing sounds) in UE4, we had to limit how many sounds were playing at once. We did this by using a hard-coded distance-check. If the player is within that distance play the sound, and use an attenuation set at run-time to set the volume lower the farther the player is. If the framerate of the user wasn't high enough, the sounds would choke as well. So to keep the creative capabilities robust this demanded more performance improvements. Smart pre-caching of certain values saved some time here.

Caplets

Implementing the objects was an interesting task as well. Each object was comprised of a caplet collection, which contained a list of the edges (which contained vertices that were the spheres). Each frame a tube would be generated between each edge, filling out the object. The math of this is discussed in a slightly unoptimized fashion in previous blog posts.

In order to allow the objects to move, make noise, grow, shrink, and be active we implemented a series of arrays for each sphere that contained locations to move to, sizes to grow/shrink to, and change color. Each frame we interpolate between these and update the outward position/color/size of the sphere. We managed to make it very fast by modulating through the array instead of using a ton of branching to check if our index is past the end, and keeping things relative to the parent object.

Optimizations

Computationally that was expensive, so we came up with tons of interesting ways to limit the amount of "updating" we did in a frame. We limited it by first checking if the object was on-screen, and then by updating less if the object was farther away. We had to remove the hyper-accurate form of on-screen checking, where we update the spheres that were on screen even if other parts of the caplet collection were off screen. However, this took numSpheres number of visibility tests, for which the overhead was not worth it. The LOD-updating algorithm was also not good enough, since it was a CPU optimization it didn't change the performance much on older and less powerful hardware. The image quality hit it took also wasn't worth the meager boosts it gave.

In the end the most important optimizations we made were pre-caching EVERYTHING used more than a couple times, implementing LOD for the amount of triangles in each tube, the visibility checks, and lowering the amount of polygons in the spheres. The spheres we'd been using up until the last week were UE4's default spheres, which had 700-900 triangles! I hopped into blender and made a much simpler UV sphere and integrated it. It's lighting is much more poor, but at least the program can run fast enough on old PCs to even have lighting and anti-aliasing with a reasonable frame-rate.

So you're probably wondering why it's so slow in the first place, to require all these cut-corners and optimizations in 2015 - as were we. We pulled up the profiler and started recording data. We saw most of our time was spent in stalls and generically marked overhead times - and we realized it was the Blueprint interface.
We learned that the Blueprint interface compiles to byte-code which is run on a virtual machine. One of the UE4 engineers said he Blueprint interface executes instructions up to 10 times slower. We were pretty crushed to learn we essentially programmed our entire project in a slightly slower javascript, but at the same time impressed we got so much out of it.
If we could start over we'd implement it all in C++.

Cool Things

We implemented Caplets into Unreal 4, and allowed the objects to move around do interesting things. We also implemented a global scaling factor to scale all the objects to be bigger, as well as passive rotations with a hack-y solution for what I think was gimbal lock. The object's sound fade in and out, and their sound is altered in a custom way to make the experience of flying around more responsive to what you are actually looking at vs. what is near you. Adding objects is also super simple!

The craziest thing to me is that we accomplished everything here in spite of using the Blueprint interface. When we got the first caplet collection object working, drawing tubes, changing color, sizes, and sounds, the framerate was 15 frames per second, for only one object.
Now it can run hundreds and get good framerates with lighting/anti-aliasing on mid-range computers from 2010.

Regrets 

We should have used C++ instead of the Blueprint interface. It was hip, cool, and alluring, so we fell for it. It's a shame, because we had already implemented the entire project and couldn't afford to do a full re-write a week before the "end" of the project. You know what they say though, you can never trust an engineer who hasn't had to deal with a poor initial design choice.

We think an editor would have made the project much more usable. It would allow us to package it and distribute it as a single file instead of distributing the project and requiring users to download UE4. However omitting it saved time and allowed us to spend time making the Blueprint implementation fast enough to be respectable.

We also should have been a little more active in the blog. We changed and rewrote entire systems so often that a blog post made on optimizations would become immediately obsolete.



Anyway, thanks for going on this journey with us, download it off Github and add some objects! Send me your changes through Github and I may add your custom object to the project as a whole!

Performance Boost and Adding Your Own Objects!

Hey all! It's been a while since the last update. Since then we've put in lerping between the rest of the qualities the spheres have, and have been working with sounds and performance.

Amier's handling the sound, and I'm taking care of the performance.

So without further ado:

Performance!

        When I last blogged about the development, Sphericles ran in-editor around 30 fps. For one object. Even if you weren't looking at it. That's pretty awful. So I popped open the Unreal 4 profiler tool and analyzed which of my calls were taking the highest % of each frame.

         What I found was very helpful. I was calculating a transformation twice and doing silly things, and on top of that I was forming the transform for the caplet triangles into a non-offset space (since they must be relative to the caplet collection object!) and then forming another transform, and going through my entire list of tris and transforming each, again. 

         I'm pretty sure that's a crime worthy of the death penalty. Anyway I consolidated all the transforming into one transform that is applied to each tri once, which improved the framerate to 60 fps for one object. I stuck a couple more in, and seemed satisfied. That is, until later when I put 50 in at once. The framerate fell below 5 fps. I was mortified, since this program needs to work on weaker pcs, and it didn't even work on my monster of a pc! So, I got creative, and stopped it from updating it's logic at the right times and decreased the number of triangles per caplet with distance. This bumped it up to an almost constant 70 fps, unless you are viewing every single object, in which case it falls to around 40 fps. So, how did I achieve those two optimizations you may ask? Well I'll tell you!

Smart Updating

        By taking the position of a caplet sphere and the camera, I can form a vector from the caplet sphere to the camera. By taking the dot product of the forward vector and this vector, I can get the cosine of the angle between the two! So, if the dot product is less than -0.6, do not run the interpolation logic nor update the caplet sphere's triangles. Also, if there are less than 2 triangles per connection between caplet spheres, I also stop the update logic. 

LOD Optimization

        This was slightly more difficult, but not by too much. Here I needed to draw less triangles based on how far away the caplet sphere is. The "how" was simple: increase the step of the "phi" (remember back to calculating the caplet's connections, I step through phi in spherical coords and draw triangles between the vectors tangent to both spheres). This causes less triangles, and worse image quality, but at the right distances it's invisible. The part of this that gave trouble was finding a good equation for the LOD. I chose Distance*natural-log(Distance)*small-constant, because I needed something similar to a quadratic falloff, so my LOD value would increase a lot as I can see more detail, but be effectively nothing past a certain distance. Dist*Ln(Dist)*const was perfect because it gave behavior similar to Dist*Dist, but not as harsh. 

        The end result of both these techniques is a very smoothly running piece of software, perfectly ready to be used by more people after a couple more performance enhancements. This brings me to the next topic: User generated content! One of the goals of the project is to allow users to make their own content, so we need to support this. The professor we are developing this under says we don't need a true editor interface since unreal's blueprint system along with the functions we made make it easy if not easier to do it there. After some refactoring with inexperienced UE4 users in mind, adding a new object is as simple as making a single blueprint and typing it's name in another clearly marked  blueprint. For example, here's a short video of the process:

Adding Objects To Sphericles!


Have fun!

Interpolating between Positions and Radii

Having completed the technology to fill in the space between spheres, the next step is to build the systems to let the spheres move and change size!

If you think back to the original project idea, you'll remember we intend to implement an interface through which to make shapes comprised of spheres, where the user can set keyframes for sounds, colors, sizes, and positions!

So, to begin the process Amier used the Blueprint interface to make a "man".

It was simple to do - in the Event Blueprint section of the previously mentioned Caplet Collection collection, OnEventBeginPlay (called when the game starts) is triggered, and I call our "add caplet" function several times with parameters that describe the man.

To allow movement, I began by making an array of vectors (which are used by UE4 to represent any 3 dimensional float) that will represent the positions of the object, and to scale the Caplet I made an array of floats.
Then, inside the Caplet object I added two functions and modified an existing one (scale):

Interp
This is called by the Caplet Collection in tick for each Caplet. It takes in the delta time since the last tick, and keeps track of a floating point variable called 'time'. Time is incremented by delta time, and if it is greater than 1 the current indices in the position and scale arrays are incremented, and time set to 0. The indices are also kept within their bounds here as well.
Finally, Move and Scale are called.

Interp's Implementation


Move
This is called by Interp. It is relatively simple, but made ugly by the blueprint's constraints with regards to branching statements. The algorithm checks if the current position index is greater than the Positions Array's length - 1.
If so, simply set the current position to the current index (since the index starts at 0, and is guaranteed to have a value of at most array length-1). If not, that means interpolation must occur between the current index and the next index.

So, how to lerp between two points mathematically? Just for fun I wanted to derive it myself, without "cheating" and looking at notes/books/internet.
At first, I came up with this:
float Lerp(float a, float b, float t)
{ return (b-a)*t + a; }

While it took about 5 seconds to come up with and implement, unfortunately this was not safe for floating points, which I realized after my precision flew out the window. I quickly switched to one a bit more safe:
float Lerp(float a, float b, float t)
{ return (1-t)*a + t*b; }

To apply this to vectors, you need to perform it per each component between the two vectors.
So, I achieved the interpolated position between two vectors and some time t in [0,1] and the code looks like this.

At this point, you need to consider the edge case where the index is at the last position - there needs to be support to allow smooth interpolation from the end of the array to the beginning. I placed another branch to check if the current index is the final one and if so, lerp to the initial member of the array.

I want the user to be able to add more positions relative the the caplet collection object, and the blueprint functions to set position are limited to adding offsets (not good for interpolating cause they compound, unless you subtract the difference from the new interpolated value and the previous one and offset by that much, which gets complex). So using functions that set the actor's location in world space, I interpolate all the positions using the relative space, and offset by the position of the root Caplet Collection's world position, achieving a correct final result.

The final method.



Scale
Scale used to be a function called when the Caplet was created to force its set radius to match the rendered one, and as such had relative offsets/scales which would compound if called each frame. So, I reworked it and using the same algorithms I applied in Move, I achieved an interpolating radius.

Scale's Implementation


Click here for a quick video of it in action!

Caplets

What Next?

In order to make an editor for the user to create their own shapes, we needed to make some sort of object comprised of smaller ones. We decided the best way to do it was to take spheres, and connect them with tubes, like in this photo. Using a name suggested by Professor Jarek, we'll call them Caplets.

To implement it, we started with the basics: how to make a tube or "skin" between spheres? By finding the planes tangent to both spheres, we can draw triangles and fill out the space, like this.

MATH

Summoning my old high school geometry skills and Processing, I was able to build a quick test.
The secret was using spherical coordinates: By drawing some quick lines, I was able to solve for Theta, and using spherical coords means we have all the information we need.

Solving for Theta

Converting that to xyz coords gives a vector (let's call it R) that points to from the center of a sphere to the point where the tangent plane intersects. By normalizing and multiplying by the radius of a sphere, and then adding it to the center's position you get the point of intersection. By incrementing Phi you can get the next point on each sphere, and the rest is history.

There was a large snag though: the formula I used is only valid in two dimensions, or when both spheres share the same Z and Y values. To fix this, calculate the vector formed by subtracting the two sphere's centers, and use that vector as a basis to form a rotation matrix. Transforming the calculated R's of each triangle with this before adding to their respective centers adjusts for this and fixes everything. 

Implementation!

In order to implement it into UE4, I began by looking into ways to draw custom geometry like quads or triangles. After seeing a lot of disheartening forum posts saying it was either impossible due to UE4's architecture or I would need to extend their geometrical primitive class and implement it myself, I found hints of a Plug-In by Epic themselves that does this. I found it and it works like a charm.

Now, to support all the things we want it to I did a lot of architect-ing. I made an object called Caplet Collection, and a Caplet object.  The Caplet Collection has a function that allows it to add Caplets as components using another as a parent if desired, and an Edge list that keeps track of the connections/order. Every update, it iterates through the Edge list and draws the Caplets.

The final blueprint Part 1 Part 2

Next post will be me combining the work down on the caplet spheres with the sound/collision work done on the SphereBP we've been using up till now, and hopefully initial work on a working editor!

A Different kind of Tone

Today was yet another Saturday working on Sphericles. Our previous (and really first productive meeting) was mainly getting things physically set up  and introducing the basic functionality of UE4 - especially the flow charts.

Getting to work today, now that I had known how to manage things better, was a lot less painful and a lot more fun. Now that we had a crude rudimentary model of, well, a crude rudimentary model of what we wanted, it was time to start applying what I learned by messing around in UE4 to help create what Sphericles is supposed to do.

Last week, chime sounds were played on contact with the spheres, but we want something a bit more dynamic than chimes. The idea is to get different kinds of tones to play for different kinds of spheres. At first, I tried to see if we could just change the pitch of some standard tone, but this didn't really lead to much distinction as I had hoped. I tried also to see if there would be any luck in procedurally constructing sounds from within UE4. No luck. I just decided, at that point, that the easiest solution would be to produce all notes as their own tones and mix and match notes to create chords from within a UE4 Sound Cue. Generating tones in Audacity, I was able to recreate all 12 the notes centered around A440Hz:

C, C-sharp, D, E-flat, E, F, F-sharp, G, G-sharp, A, B-flat, and B

Finally, I assigned an audio cue to randomly mix two tones to produce a chord to play for each sphere. Attenuation was assigned so that sound volume depends on distance from the audio source.

Checking in with Graphics and Gameplay Work, 2/1/15

I gave myself some projects to better understand UE4's shader system.
They call them Materials, and are applied to meshes through a drop-down
menu. Using a flow-chart-like interface you can take inputs like normals
 and positions and apply mathematical operations to them, and then
output them.

Flow Chart

It ends up looking like this.

I told the sphere objects to randomly choose from some of my other
test-materials, and when they spawn randomly around the environment they
choose a random material at creation, which which ends up looking like this.

I also added collision between the player and the physical mesh, so
touching it will delete it. Later I'll add the option for effects/sound
to play when it is destroyed.

Amier also added lots and lots of gameplay related work - he'll post about it soon :)

Steps Towards First Prototype

Today we began working on an initial playable version that shows a hint of what we're trying to accomplish. Through entirely blueprint interfaces we've implemented our Pawn and a Sphere Actor and prepped both for collision. Currently we're learning how to use shaders in UE4 by checking out Unreal's amazing Math Hall demo - Math Hall.