More Data Structures Animations

After refactoring my data structure animation code at the start of the year, it has become significantly easier to add more animations.  So far I have added:

  • merge sort
  • singly linked lists
  • queues (both array and linked list implementations)
  • stacks (both array and linked list implementations)

I have also fixed many bugs in my basic animation objects and spent some time to style the animations.

The other big feature I added was the ability to put in controls and interactive elements.  The animations are written in Processing.js.  The interactive elements are standard HTML elements.  To accomplish this I used the method suggested on the Processing.js site.  That is I built a number of javascript functions that then made function calls to my processing.js object.  This method is fairly easy to do.  In your canvas tag for your sketch you need to add an id.

<canvas id="dsanim" data-processing-sources="..."></canvas>

You will then want to add the following bindJavaScript() function (note the use of the id from the canvas tag to get access to the appropriate sketch):

// javascript reference to our sketch
var pjs = undefined;
var bound = false;
// bind JS to the p5 sketch for two way communication
function bindJavaScript() {
  if(Processing) { pjs = Processing.getInstanceById("dsanim"); }
  if (pjs !== undefined && pjs.bindJavaScript !== undefined) {
    bound = true; }
  if(!bound) setTimeout(bindJavaScript, 250);

You can then  call any function from your sketch by accessing it through the pjs object.

For example, in my linked lists sketches I have a function called insert() that will perform the animation of adding a node to the front of the linked list.  I did not want an interactive element to be able to disrupt the animation part way through as it can cause errors.  Thus, I also added a function called midStep() that returns true, if it is in the middle of an animation routine (for insertion for example).  Both midStep() and insert() are processing.js functions.  With the above bindJavaScript() function, the pjs variable is associated with the sketch and thus, I can call these from a JavaScript function:

function insert(){
    var v = document.getElementById('val').value;
    if(v != ""){

All I need to do is then associate this function with an interactive element and it will trigger the appropriate function call in my processing.js sketch.

You can check out the sketches here.  I plan to add more over the course of the next year as I’m teaching Data Structures and Animations this year.

Please file an issue if you spot a bug.  I tried to get as much out as I can.  In particular I tend to not test on windows at all, so if you are looking at it on a window’s machine and its not working please let me know.

Also, I know that I had initially chosen some colours that were not at all visible on some monitors.  if it looks like part of the animation is missing something, please let me know.  Thanks in advance.


Fixing My Processing.js Data Structure Animations

Over the holidays, I spent some time fixing some code for a processing.js data structures and algorithms animation project that I had been working on.  Check out the results here:

Now, a bit of a story about the code.  About 2 years ago, I wrote some code to do some animations of sorting algorithms while I was learning Processing.js.  The idea was to build a library of these animations that my students can use as reference. I wanted to add animations for all the data structures and algorithms we covered in my data structures class. Although I was able to implement two simple sorts using my previous code, I had quite quickly realized that there were two big flaws in the way I had designed my code.  The first is that the animations were frame based.  I basically went and changed the frame rate in my sketch to get the animation to play at the speed I wanted… not a good idea but it was something that was easy to code with pjs so I had done it that way. The bigger problem however was that I had written a state transitioning mess of a program.

The way that Processing works is that there is a single draw() function that is repeatedly called to produce an animation.  The way that I have coded my animation was to have different states for each of my objects and depending on what I wanted to show, I would modify the state of that object.  So if the array was swapping the values of two elements, the array object would be in a swapping state. The drawing and animation was pretty simple.  Change the state, change what animation to play. However, when it came time to code the actual sort animations though, I realized I had a problem.  Translating the procedural sorts into a series of state transitions of the various animation objects was difficult to do.  When completed the animation code was a big mess and does not in any way resemble the sorting algorithm. For example here is the original mess that drew the bubble sort animation (don’t cringe too much… it was a first attempt :P)

  void draw(){

          if(currJ_ >= sortLength_){

As you can see it does not in any way resemble a bubble sort… no loops, just a nasty series of state transitions. After completing the animation for bubble and insertion I posted my code to github and just left it as is… I always wanting to go back to add more but the thought of translating something more complicated into that mess made my head hurt.

Sometime in the fall I was talking with my friend Phil about the mess I made with my code and trying to think of a way to fix it or possibly even rewriting it. He pointed out that what I needed was really an animation system… something that you can record and play back. Essentially the idea is that you would run through a standard algorithm as is on some given piece of data. During the process of running through the algorithm, the system would “record” the states the animation objects should go through. Displaying the animation was simply playing back the recorded steps. My new design involves 3 new objects (they are not yet complete .. but complete enough for sorting algorithms).

  • Animation step – one discrete step in an animation. I wanted a way to allow for the ability to step through an algorithm. Each step may involve modifying multiple objects or even modifying one object in more than one way but it is taken as one whole step.
  • Animation Instruction – an instruction sent to an object that changes the object’s state in some way… The way it is currently implemented is a series of instructions represented by a constant, and parameters to the instructions which are all done as integers. Its not the best way to do this… but for now it works.
  • Animation – contains a list of animation objects (things that are drawn), and a list of animation steps.

In any case… this method works. Here is the function that creates the bubble sort animation:

void bubble(int array[],int sz){
    int i,j;
    int tmp;
        for(j=0;j array[j+1]){

You can actually see the bubble sort algorithm in here… the animation steps and animation instructions are simply like “print” functions except that they state what should be drawn instead. Each of the addInstruction() calls passes in the index of the animation object to modify and the instruction (SET, SETFONTCOLOUR, etc.) and parameters of the instructions. its not perfect but its way better than the original.  The animation has also been fixed to be time based.  Furthermore, while it is not currently implemented,  it will be possible to allow a step through of the animation also.

I have updated both animations for insertion and bubble sort using this new animation system.  I have also implemented the animation of selection sort and quicksort.  Both were not really hard to do (though I admit that I would want to tweak the quick sort a bit as it isn’t quite as accurate as I would like). Hopefully others will find these animations useful.  Let me know if there is an error or something that is unclear with how the animation is done.

Sharing is awesome!

Earlier I wrote about making a zelda sword using  When I first created the model, there were some problems with it.  The sword did not appear to have an edge… you have to turn it to see the sharp edge.  It looked very much like a box.  The grooves that I had put into the sword hilt also did not appear to show very well.  I thought maybe it was a rendering problem or the shininess of the material or something and tweaked it for a bit but the problem persisted.

One of the things that I had done after I first finished my sword was I shared it with my industry partner… this is easy in….its like google docs, just hit share and say who with. 

About a day later, my industry partner had applied a normal modifier to my model and fixed my sword!  It actually had sharp edges and proper ridges.

To me … this really showed how useful it is to work collaboratively in the cloud.  For me to share my scene was easy… no fiddling with ftp, attempts to attach large files to emails etc.  My industry partner was able to look at the exact thing that I had been working on (including all my most recent attempts at fixing my problem…).  He could then fix it.  Immediately after this, I was able to see what he had done and use that solution to fix the rest of model.   I knew from the start what Ben’s vision for had always been… but to actually see it in action… now that’s cool



Trying out

This summer my industry partner and I presented on at SIGGRAPH 2013. It was a project that we had prototyped in CDOT and one that I had found to be very compelling to work on. As with many projects that begin their life at an academic institution, the work to turn the prototype into a commercial product is done by the industry partner. The smoothing out of the bugs, the improvements to the feature set etc. etc. etc.

I had not really used since preparing for the SIGGRAPH presentation this summer and I was curious as to the improvements that have been made since I last used it. A student of mine was creating a model of the Master Sword from Legend of Zelda. It inspired me, to try my hand at creating the same sword inside

I used this image that I found of the sword as my reference:


And here is my model (I don’t have materials yet though…). Too bad doesn’t allow iframes though… would have been neat to just stick the embed code right in my blog 🙂

First I’ll start by saying that I’m not really a 3D artist so any ugliness in the model is all due to my lack of skill, not a problem with the application. It wouldn’t look different if I had used another tool. The application was fairly stable in july but now it is even more so. I really liked the way the frame selection option adjusted my viewport when I had to do detailed work. The ability to select loop edges was really handy for this shape (adding edge on blade, creating the groves on the hilt, etc.). One of the things that I have always loved about is the idea that this isn’t a toy project. It actually works in a manner similar to professional grade tools with features like subobject editing. I’m really amazed to see how much more so it has become in the last few months.

Thank you to my teachers

Recently I got a tweet from a former student saying that they really liked my Data Structures class. It was really good to hear that and filled me with warm fuzzy feelings. It also got me to think about all the wonderful teachers in my academic career. There have been so many. I don’t know if I have ever expressed my gratitude at the time but I think it would be good for them to know (although I’m not sure if any of them will ever see this blog… but they say that nothing ever gets erased on the internet so maybe). So here is a small list of teachers/professors/instructors who have made a difference in my schooling.

Dr. Dekang Lin – My thesis advisor. The one who spent countless hours trying to explain grammars and parsers to me. You have taught me so much and provided me so much support. I thank you from the bottom of my heart.

Dr. Helen Cameron (Univeristy of Manitoba) – who was very tough but incredibly fair. I never worked so hard to get things done as when I had two courses with you in the same semester.

Dr. John Bate (University of Manitoba) – I never directly used what you taught me (digital logic) but it was the course that made me really understand how computers work.

Al Marshal (University of Manitoba) – my own data structures prof… clear, concise with a sense of humor too.

Dr. Bill Kocay (University of Manitoba) – my other data structures prof who helped me to understand all about suitcases 🙂

Dr. Neil Arnason (University of Manitoba) – who helped me out a lot when I started teaching and made it easy for a newbie like me to transition into this career

Dr. John Anderson (University of Manitoba) – who gave me my worst grade on my transcript but you were my first CS prof and you always did a fantastic job teaching… and you know I mean it when I say this since you gave me my worst mark 😛

Dr. Russel (University of Manitoba) – The mandarin classes were awesome.

Mr. Doug Silzer (Cedarbrae Collegiate, Scarborough Ontario) – who taught me to reason through problems and never gave me a straight answer.   Thinking through to a solution is important after all :).

Mr. French – who taught history and not French :P.   Your class was amazing

Mr. Horkoff (Ken Seaford Jr. High) – a teacher who grew my love of science.

Mr Thies (Ken Seaford Jr. High) – a teacher who taught me to do my homework even when I thought I knew what I was doing already because a good student do their homework. I believe that were it not for this enforcement of homework doing, I would not have been able to so easily continue my studies at higher levels.

An ESL teacher in Meadows School in Brandon Manitoba (sorry I forgot your name, it was long ago, I was really really young, and I was only there for 3 months)  who taught me that the “th” sound required the sticking out of the tongue to be properly pronounced. “The” not “De” :).

Miss Jenny Smith – awesome exchange teacher from England who taught at James Nisbett in Winnipeg for one year. You were awesome.

So, if anyone reads this and knows any of my former teachers, please pass on my message of gratitude.  You have my thanks. – Web based 3D Content Creation Tool

Today I am writing about the official release of a project that is near and dear to me: is a web based 3D content creation tool.  That is, it is a tool that lets you create 3D scenes and animations.  Popular desktop based 3D content creation tools include products such as 3DS Max, Maya, Blender etc. is different from these tools in that it is completely cloud based.  To access the tool, a user needs only to go to their site and log in.  All work is saved on the cloud.  Furthermore because is built in the cloud, it is possible to easily share your scene with other users and allow them to alter it with you in real time (think google docs). also gives access to server side rendering, meaning that you won’t need to actually have a strong beefy computer to render a scene as that work is offloaded to the server, making it possible to create fantastic images even with a modest computer.

So… why do I care about this project?  I mean, I’m not an 3D artist.. I can barely model a bucket.  The reason I care is because CDOT (and my team in particular) was involved with the original client side prototype.  It is amazingly gratifying to see it completed and on its way to a commercial release.

In the end this is really a story about students.  I will be the first to admit that before I worked for Seneca I had a very large university bias… ie that college was second best.  This probably couldn’t be helped given the fact given my background.  (Lets just say that I had typical Asian parents – heck it was over a month of  “I can’t believe you aren’t going to study pharmacy!”… “why would you ever go into computer science?”…”how will you ever not starve?” … “are you sure about this computer thing?”  when I changed my major to go into computer science in my first year… best decision ever btw).  I began working at Seneca while I was completing my masters.  I chose Seneca because I had a sense from the interview that it was more than what I expected from a college.

I began doing applied research at Seneca about 5 years ago.  It wasn’t something I expected to do.  My first project was to work with something that eventually became known as WebGL and thus began my jouney into the world of web based 3D graphics. Over the course of the last few years, the work that our multiple research teams at CDOT (Centre for Development of Open Technology) has shown me how much our students are capable of doing.   In fact it was during our presentation on the implementation of 3D functionality in Processing.js at SIGGRAPH where we met Ben Houston of Exocortex, our industry partner for prototype.

Ben was one of the most involved industry partners I worked with.  He had a vision of what was needed and how best to achieve that.  His guidance for the students involved with the project has been phenomenal.  I’m sure that it was a good learning opportunity for them.

Lastly, I want to thank all the students who were involved.  I’m incredibly proud of all of you.  Jesse,  you are amazing and hardworking.  You have always been impressive with the speed at which you code.  I’m very happy that you are now working full time on this project.  David thanks for your work on the initial design.  Hasan and Vince… I think you guys really helped support the team during the thinnest part of its development and did a lot of good work on the prototype.  Dylan, Jacky, Andrei, Kalid, Michael, Mark for their work on subobject editing prototype.  Norbert, Jordan, Mohammed, Kabilan and Ruth for some of the documentation work.  You remind me that college is not second best constantly.  Thank you all.

Videos as notes

Years ago I taught IPC144 at Seneca College and had made up a really nice set of notes for my students.  I remember spending hours doing it, drawing diagrams, writing up the words to hopefully make the course easier to understand.  Its been years since I taught to course but I am once again teaching it and when I went to look for those notes, I found that I had managed to somehow erase all traces of them.  So … what to do…

Initially I was going to just rewrite the notes… put it on a github wiki so that I won’t lose it again.  This seemed like a good idea but then I started thinking about it a bit more… The first semester students have the textbook from the book store.  Then they have the notes on the comon ipc site… if I add my own that would be three different sets of reading.  Now, while I think that it is a good idea for students to read, I don’t know that it would be tremendously helpful for them to just read the same thing over and over with 3 different authoring styles.  Realistically, I also don’t think students will read all 3 sets of notes.  I’d be happy if they read one.  So I thought about how I could remake my notes in a way that would make it more likely that my students will use it for prep.   This is when I decided I’d make some videos instead of more notes.

So far I have only made 6 of them (all around setting up your computer, using a text editor etc) but I plan to do more.  I admit… I’m a bit nervous about it.  I think it goes back to that debate of whether or not to put your lecture notes on the web or not… If you put your notes on the web, will your students still come to class?  And then I thought to my own studies… the answer was… yes.  I went to class regardless of whether or not the notes were online… Notes can only say so much.  The lecture details things that are not in the notes or perhaps things that are not completely clear through the reading.  It was about interacting with the prof and your fellow classmates.  Besides… if my 5 min video can replace my 40 min lecture… I’m probably doing something very very wrong in my lecture.

What I plan to do over the course of the term is to make a number of short videos (no more than 5 min each) on the topics we are covering.   I am not looking to replace my lectures.  The way I am seeing these videos and the way I want my students to think about the videos is to view them like videos of video game boss kills.  You watch the video and then try to do it yourself in game.  The videos show you what to expect.  Similarly, you watch the videos on course material to get a basic grasp of what is happening.  You come to class to refine that knowledge and practice problems on that topic.

Making the videos

I start off by deciding on the topic I want to make a video for and figure out how I would talk about it.   I also try very hard not to go off topic or do asides as I want to make videos that are to the point.  I screen capture what I want using snapz and a mic in real time(I run a vm when I need to show something windows specific and screen capture it that way).  I could have used something like imovie to voice over a video after I make it but I found that it was just as hard to do that than to do it during the capture. I might try writing a small script next time but I hate sounding like I’m reading.

Popcorn.js + subtitling

One of the students in my class has a hearing impediment and I didn’t want him to miss out.  I checked out youtube’s automatic close captioning of the 6 videos I made and they were hillarious but not accurate or useful.  Thus, I decided I would need to caption it myself.  Now… the way that I’m doing it right now is extremely manual.  If anyone has a better idea on how to do it, I would love to hear from you!   What I do is I type out what I’m saying during the video (I do remove my um’s and ah’s and small misspeaks though) approximately one statement per line. then I watch the video and I figure out the time in the video when I  finish saying the statement and make a note of it with each statement.

I have a generic html document that looks like this:

<script src="popcorn-complete.min.js"></script>
Popcorn( function(){
var popcorn ="#video", [ ""], {controls:1});
  "start": ,
  "end": ,
  "target": "subtitle-div",
  "text": ""
    <div id="left-panel" style="width:640px;">
    <div id="video" style="width:640px; height:440px;"></div>
    <div id="subtitle-div" style="font-size:large;width:640px;"></div>
    <div id="right-panel">
    <div id="top-right"></div>
 <div id="bottom-right"></div>

To create the captioning, I repeat the .footnote block and add in the text from the text file I created.  I then fill in the end times (start time for each is same as previous block’s end time.)  The reason I’m not doing this with popcornmaker is because I wanted to have it laid out more like a web page than a video.  I also am using popcorn to add links to things that I refer to in the video to make it super cool 🙂

Anyhow, if you you can check it out here and here.