3D Graphics using a Custom Animation Framework and the Three.js Graphics Library
3D Merge Sort Animation
Press "Restart" to sort a new random Array
Merge Sort Algorithm
The Merge Sort algorithm is one of the most basic "Divide-and-Conquer" algorithms. The input array is first divided in half, so for this 10-element array, each half has 5 elements. Then the 5-element sections are divided into a 3-element and 2-element section. The 3-element sections are divided into a 2-element and a 1-element section. Then even the 2-element sections are divided into 2 1-element sections.
Next comes the "Merging", where all these smaller divisions are progressively merged together, so that the smaller elements are placed in front of the larger elements. Essentially, two sections to be merged are "zippered" together, to form a combined sorted section. In this animation, you will see that first, elements #1 and #2 are merged, then this is merged with element #3. Next, elements #4 and #5 are merged, so that now we have 2 sorted sections: elements #1 through #3 sorted, and elements #4 through #5 sorted. Then, these two sections (#1 - #3) and (#4 - #5) are merged.
This exact process is repeated for the second half (elements #6 - #10) of the array. So before the final merge, we have 2 sections (#1 - #5), and (#6 - #10), which are each independently sorted. Finally, these two sections are merged, which results in a fully sorted array. Please click the "Restart" button, to see for yourself that the final step is the merging of these two sorted sections. The entire animation for sorting 10 elements takes less than 30 seconds.
Choosing reasonable values for the options to the Camera can be a hit-and-miss process. Then if you want to change the Camera options after you have created the drawing, you must call several methods such as camera.position.set, camera.lookAt, and camera.updateProjectionMatrix.
I also created some wrapper objects over the standard THREE.Object3D objects, such as a custom "Bar" class, which adds functions to allow you to color each side of a rectangular cube individually. The built-in THREE.CubeGeometry object does not allow access to its internal THREE.Face objects, nor does it create line objects representing the edges of the cube. In addition, even drawing the underlying grid is not a built-in feature, so a I added a utility function for creating the grid.
Then I decided to write a jQuery-UI control panel to allow the user to adjust some of the camera parameters on-the-fly. The most useful controls are for the Camera Angle and Camera Height. The Camera Angle control is adjusted by using your mouse and dragging (click and holding down while moving the mouse) along the red dot around the circle slider widget. The "Ortho" controls set the edges of the viewport.
Wow, that was a lot of work. But now that is done, it's really easy to write new programs to display your 3D objects, and manipulate the viewing parameters interactively.
Merge Sort Animation
Three.js has a basic built-in Animation class, but it is designed for a single Animation action. To display the actions performed by Merge Sort, I needed to execute a series of synchronous (in-order) animation tasks for each Merge operation.
Each of these off-the-shelf solutions, implements the generic Promise API with "deferred" objects and functions on these objects typically called "when". These libraries differ in their memory footprint and optional features. For the synchonous animations tasks required here, I chose to use "When.js", which is offers a good balance of features vs. complexity.
This was not the first time I needed to create my own library of custom animation features. I've learned a lot by previous programming experience with the updated graphics framework for Java, called JavaFX. I have written a similar program to this Merge Sort Animation in JavaFX, which had a lot of additional features, such as highlighting the repeated divisions in the array. The unfortunate part of programming in JavaFX, is that the final product is Java applet. When a user tries to run a Java Applet in your web page, the browser displays 2 ominous "Security Warnings", and most people wisely chose not to risk running a non-essential program (no matter how safe you tell them it is).
Custom Animation Framework
1. AnimationQueue: a wrapper to the Promise library, which allows addition of new animation tasks, and automatically executes any tasks remaining in the queue after they have reached completion. As the latest task in the queue is removed, it calls AnimationTask.update repeatedly, until its specified animationElapsedTime is reached.
2. AnimationTask: an object which defines the total elapsed time a task should be executed, and two internal arrays. One array is for the objects to be animated, and the second array is for the methods to be executed at each time step in the animation. Most importantly, the AnimationTask object calls the ".when" method of the Promise library at completion, which automatically signals the AnimationQueue method to "pop" (take off) the next task in the queue.
3. AnimationMethod: a class of methods, such as InterpolateMove, InterpolateRotate, InterpolateColor, TickMove, TickRotate, and TickColor, which allow specification of the precise change in each object for every time increment in the animation. To create a new AnimationMethod object, all you have to do is specify the properties of the object (such as position) at both the beginning and the end of the AnimationTask. The object itself automatically computes the properties at in-between times as the animation progresses. The AnimationTask object has an ".add" method, which requires a pair of AnimationMethod and THREE.Object3D objects to be simultanously added to AnimationTask's internal arrays.
Integrating the Merge Sort Algorithm into the Custom Animation Framework
The real flexibility designed in this system is that the AnimationTask object allows any number of objects to have individual properties changed at each time step in an animation. For example, in a single step in the "Merge" function, there are 3 separate AnimationTask objects.
1. The first Task moves the "Bar" ( the 3D rectangular object representing the value/height of the array element) forward.
2. The second Task slides this Bar to the left.
3. The really cool part is the third Task, which is the sum of multiple "AnimationMethod" objects. One is to return the moved Bar backward into the orginal line. Then, for each Bar that needs to be shifted to the right, an AnimationTask is added which specifies the beginning and end positions of the movement of each Bar to the right.
So from the top, the whole program consists of these processes:
1. Create the base THREE.js Scene and Camera objects and add the grid.
2. Assign random values (heights) to each of the Bars and add them to the Scene object. Call Scene.render() to draw the initial static graph onto the web page.
3. Create the AnimationQueue object.
4. Start the MergeSort method. The merge method calls the reorderBars function when needed, which adds all the tasks to the AnimationQueue.
5. Call AnimationQueue.start(), which automatically executes each AnimationTask in order.
Please press Restart, then sit back and enjoy the ride!