Tips/tricks related to Computer Graphics, GPUs and other programming

If you are interested in Android development, I highly recommend checking out Romain Guy’s post (Romain is an Android dev at Google) on profiling and optimizing an application.


All applications should ideally take at most 16 ms to execute one frame, achieving a smooth  framerate of 60 frames per second. Romain goes over some crucial new tools like systrace and TraceView which work with Android Jellybean (4.1 and 4.2)

I had a Samsung Galaxy Captivate for 2 years before I upgraded to a HTC One X. While both phones are pretty good, the lack of software updates is extremely frustrating.


Samsung took forever to release Gingerbread (version 2.3) for the Captivate. By the time they released it people were already running Ice cream sandwich (4.0) ROMS on it. I got frustrated and switched to an ICS ROM, though playing around with ROMS can be another headache.


As for the One X, it is a gorgeous phone with a wonderful screen, but HTC promised a Jelly Bean (4.1) update by the end of 2012, and here we are in 2013. It is simply frustrating for users who want to be on the bleeding-edge (yes you can root your phone and install a new ROM, but I was unable to since AT&T has heavily locked down their phones). 


In the meantime Google released the Nexus 4 in 2012, which came with 4.2 (will the One X ever get 4.2? Probably not). Even the 2-year old Nexus S got updated to 4.1 quickly (though it won’t be getting 4.2). 


I place the blame on the carriers, since HTC has released the JB update for worldwide phones. AT&T and other carriers like to load the phones with a lot of crappy apps which you can’t get rid of. I just want a pure and straightforward Android experience. It also doesn’t help that manufacturers like HTC and Samsung like to modify Android themselves to make it more distinct, but in my opinion it only slows down the Android experience and doesn’t add a lot. 


As for tablets, the same rule applies. Get a Nexus 7 or a Nexus 10.


There is a reason why Apple preferred to have total control over the iPhone software experience – and which is why you should get a Nexus device, free from the constraints of manufacturers and clueless carriers.

There is an interesting post on AltDevBlogADay showing how one can write a software rasterizer:


Anyone interested in graphics should have some understanding as to how the graphics pipeline works and how the rasterizer works. Knowledge of math (especially linear algebra) helps greatly.

BezierView using WebGL

My lab (SurfLab) manages a program called BezierView which is used for rendering different kinds of Bezier surfaces (triangular, tensor-product, rational, etc.). BezierView has not been updated for a few years, so me and a few other colleagues decided to update the program using WebGL instead.

Now instead of downloading BezierView to your own computer and running a .exe file, you can just run it online through a webpage. You can find the still-being-updated version here. For now you can view tensor-product, triangular and rational patches along with polyhedra. It is being currently updated to include a better interface and to have support for all types.

There are some shortcomings to writing BezierView in WebGL – the most obvious one is that Javascript is much slower compared to C/C++. And the online version cannot handle huge files which the offline version can. And since WebGL is based on OpenGL ES 2.0, we cannot take advantage of the tessellator engine in modern graphics cards to evaluate parametric patches on the GPU (which results in a significant speedup). So all the evaluation is done on the CPU and the resultant vertices sent to the GPU. I guess we’ll have to wait for OpenGL ES 4.0 (or WebCL to be finalized – a Javascript implementation of OpenCL).

BezierView was developed using the excellent Three.js library. I highly recommend using it if you are developing a WebGL application.

The source code is available on GitHub.

You can find BezierView here.

Virtual Reality Projects

Back in Spring of 2009 (almost 3 years ago!), I took a very interesting Virtual Reality course offered by Dr. Benjamin Lok in my department. The course basically involves creating Virtual Reality projects. I ended up creating 4 which took a lot of work but which in the end were worth the effort. Here are the four projects I worked on (click on the links for more detailed info/video):


  1. Using ARToolkit to demonstrate how touch-screens work:  

    We had to come up with a way to use ARToolkit (Augmented Reality). I thought of attaching some AR markers to a Nintendo DS and demonstrating how 3 different kinds of touch-screens work (resistive, capacitive and infrared). Written in C

  2. Virtual Reality experience: Rescuing someone from a fire:

    Now we started getting into the heavy stuff. We had to create a Virtual Reality 3D experience using a Head-Mounted Display, object tracking and small space. At the suggestion of my teammate, colleague and friend we ended up using the Ogre 3D Engine for the project. We also used Google SketchUp models and wrote the program in C++.

  3. VR experience: Target practice on a military base:

    This was my favorite project. We (me and my colleague Aritra Nath) created “virtual” shooting, where we attached a marker to a Nintendo Wiimote (which was in a gun shell, and you pressed the trigger to shoot). We had an actual barrier in the real-world which was nearly pixel-accurate in the virtual world (well, not quite). Used Ogreand Sketchup again.

  4. New VR Interface for doing 3D landscaping around a house:

    The 4th project involved creating a VR experience where the user could “create” new content. My team ended up creating a way to do 3D landscaping only using fingers and a wiimote. Used the same tools as before.

I consider myself lucky that I was able to take such a course. Though it was kind of grueling at times (especially since all the teams had to share the virtual reality hardware), it was also fun and rewarding at the end.

It has been a while since I have written a data structure from scratch (had to write B-Trees for an Advanced Data Structures course 2 years ago), so I decided to refresh my memory by quickly writing up Binary Search Trees in Python. Making sure you are familiar with data structures always helps with interviews too.

You can access the file here. I have only tested this for integers, so might need a little bit of work for other data types. The following methods have been implemented:

  • add(data)
  • remove(data)
  • Traversals:

  • preorder()
  • inorder()
  • postorder()
  • bfTraversal() (Breadth-first traversal)
  • Helper methods:

  • isLeaf(node) – checks if a node is a leaf
  • lcAncestor(value1, value2) – finds the least common ancestor of two nodes with values value1 and value2
  • printAllPaths() – prints all the possible paths from the root to the leaves

I won’t go over how a BST works, but hopefully the code is self-explanatory.

If there are any questions let me know – hope people find it useful.

GitHub Repository here

I’ve been meaning to get into OpenCL for a while, so I thought I would write a simple program which would evaluate Bicubic Bezier patches (surfaces) in parallel.
I also wanted to program in Python more, so I decided to use PyOpenCL. You can find more info about the OpenCL implementation in Python from the link.

I am not going to go over what a Bezier patch is and how it can be evaluated. There is a straightforward equation for evaluating one which I will be showing later on, but for more info about Bezier patches you can find other info online.

Let’s begin.

Read the rest of this entry »