Delaunay Triangulation

This blog has been dead for nearly two years. Wow. Graduation, grad school, new countries, new people. Although quite a lot of things have changed since the last time I touched this blog, my passion to learn, try out new things and share my experiences remains unchanged. At least, I still believe so.

What I'm about to write about today is regarding a review that I carried out on a handful of Delaunay triangulation algorithms. If you have heard that term before, you probably must know something about computational geometry, meshing or graphics in general. Good for you. If not, no big deal, just keep on reading.

Barring all the mathematical definitions, a triangulation of a set of points is basically a method of connecting all of the points by forming triangles. For a set of points on a 2D plane, this is very similar to the "connect-the-dots" exercise that you did in primary school. For a set of points in higher dimensional space, one would need tetrahedrons and other higher dimensional simplices to connect the points.

A triangulation of a set of 2D points

A Delaunay triangulation is a special type of triangulation, which ensures that the circumcircle of any triangle in the Delaunay triangulation does not contain any points inside it. In other words, if you select any triangle in the triangulation and draw a circle which passes through the 3 vertices of that triangle, then there will be no other points inside that circle. Named after Boris Delaunay, this method generally tends to avoid skinny triangles, and the resulting triangulations have some useful mathematical properties. The way I see it, they just become more aesthetically pleasing. 

What I'm going to share with you today is an analysis that I carried out on a few different algorithms for producing these Delaunay triangulations, given a set of 2D points. This work was done as a part of my final project of the 18.335 - Introduction to Numerical Methods class I took at MIT in Fall 2013. In particular, I implemented the "Incremental" and "Divide-and-Conquer" algorithms for Delaunay triangulation in MATLAB, and then compared the expected and worst-case computational costs observed with theoretical estimates found in the literature.

The complete report is available HERE. 

I hope at least one of you will find it useful. :)

Streamline

So it has taken nearly three months for me to actually write something on this blog, mainly because I was really busy with my uni work. Whatever blogging I managed to do, was for my travel blog and not this. I'm back in Sri Lanka now for the Christmas holidays, and thought of kick-starting this page, for real. :)

I'm really into tech stuff, specially into programming. In fact, I even wrote my first Windows 8 app two days ago. I have been developing for Android for over a year now, so I thought of writing about one of my Android apps as a start. Streamline's the name.

Streamline can be said to be an educational app, although it was intended to be just for fun. It allows you to simulate the flow of a liquid around any object that is drawn on the screen. The app can produce a plot of the velocity field or even better, it can show an animation of a set of particles that move with the flow. 

Although the image on the right shows just one object, you can actually draw more than one object, and the particles will flow between them. Once the simulation is on, you can tap anywhere on the screen to add a "blob" of particles at that point, and then you can watch the blob get carried away with the flow.

Particles will always be generated at certain edges of the screen depending on the incidence angle of the incoming flow. So for an angle of attack of 0 degrees, particles will be created at the left edge of the screen and flow to the right, and for an angle of 45, particles will be created at the left and bottom edges, and they would flow to the top-right of the screen. There is also the option of generating particles at the surface of the object you draw, but these particles will be slightly different in colour to the ones generated at the edges of the screen. This was done to easily distinguish the particles coming from the object surface and those in the main flow. 

The app also has a "Streamline" mode, where the actual streamlines in the flow are displayed, instead of moving particles. As additional features, you could change the colour of the incoming particles and the rate at which they are generated. 

Streamline can also produce a colour contour plot of pressure in the flow, where low pressure regions are coloured in blue and high pressure regions  in red. The pressure is calculated using Bernoulli's principle, where the fast moving regions of the flow have a lower pressure and vice versa.

Speaking of the history of the app and the details of the code, I was inspired by one of the lectures given for the 16.100 Aerodynamics course at MIT. Streamline is actually a practical implementation of the Vortex Panel Method which was taught to us in class. However, this is only a very basic type of fluid simulation because the Vortex Panel Method computes an ideal flow. Being more specific, it computes an incompressible Potential flow, where the effects of compressibility and viscosity have been ignored. So don't expect to see any boundary layer separations or anything of the sort.

You'll probably notice that as the number of vertices in the object you draw increases, the time taken for the app to solve the flow also increases, specially when you have more than about 200 points. This is because the Vortex Panel Method requires the inversion of an NxN matrix, for a problem with N vertices in the geometry drawn. And the inversion of a 200x200 matrix isn't the type of problem that an ARM processor, or any processor for that matter, particularly prefers. Getting the numbers into the matrix that was required to be inverted was probably the hardest part of this project. Actually, it was getting the numbers into the right locations in the matrix. The rest of the work was mainly to render the user interface and animations as smooth as possible. 

The entire application was designed and coded by myself within about 2 or 3 weeks, during my Christmas vacation last year. I believe that I have made Streamline as user friendly and smooth as possible, but any feedback on the app will be greatly valued.

I guess this would do for my first post on this blog. Hope to see you soon with some other project of mine. :)