Wednesday 17 November 2010

Software Framework: OpenFrameworks

I'm going to take a software engineering point of view in this post. To come up with any type of model or simulation, it is a good idea to start with a software framework.

A software framework according to Wikipedia is 'an abstraction in which common code providing generic functionality can be selectively overridden or specialized by user code'. Software frameworks facilitate the development of software, and allow the developer to focus on the software requirements rather than the low level details of providing a working system that allows access to the hardware. This, in turn, reduces development time.
For the short term, it would more than likely increase the development time, as there is a learning curve involved which needs additional time. In the long run, once the framework is learned, future projects can be a lot quicker to complete, as the need to concern ourselves with the low level details is diminished.

There are several types of frameworks available for C++ such as SDL, OpenFrameworks, Qt, etc., I'll focus on OpenFrameworks today. A few projects made using OpenFrameworks is below (clicking on it will take you to the project site on OpenFrameworks):

OpenFrameworks is a library that is designed for 'creative coding'. The library is wrapped with glut which is a windowing library. This wrapping I feel is quite a good choice, as it works really well with OpenGL. The OpenGL red book bases its code on glut as well.

If you've used Processing, OpenFrameworks certainly draws parallels with it. The website that provides the reference to the commands of the framework is also very similar. Processing users would feel right at home, there's also a wiki that provides an orientation to OpenFrameworks that can be quite handy.
What I like about this framework is that it wraps several other libraries to provide a very good interface. OpenGL is used for the graphics, as I mentioned works well with glut. freeImage which is a popular library for image I/O and processing is also included. Even quicktime which is good for playing video.
I currently use SDL, but after having a look at OpenFrameworks, I'm considering using it. Looks like a very good framework to use, and the learning curve doesn't seem too high after having used Processing previously. At the same time, there is already a lot of articles and a whole community available for SDL. I'll discuss SDL in another post. OpenFrameworks does indeed look like a very good software framework indeed.

Wednesday 10 November 2010

Tube Strike: A changed Macro-System

The recent tube strike and a discussion with one of my professors has led me to think about micro and macro systems as a whole, and in turn simulations working within these constraints.

First of all, let me say a little about a normal working day and what happens during this time. We have a fully working transport system, a nice sunny day (or mostly grey, in London at least!), a phenomena, if you'd allow me to call it that, takes place i.e., commuting. Individuals work, that's how the economy and you, as an individual survive and provide for yourself, and your family. So, we have people who commute to and from work everyday. What happens during the commute? Each individual, makes an independent decision in order to reach their work destination. How they get there is based on personal choice, which is generally ruled by the amount of time it would take to get to work, the distance to workplace, and the number of changes that are required. This decision gets refined as the individual finds him / her self making the most efficient decision to reach the workplace.

Each individual takes these similar independent decisions becoming routine over time. Aggregating all these independent decisions together, we get people moving around, and a pattern develops as the micro-system stabilises, in which ways people move to commute to and from work. These hundreds of independent decisions are taking place within the constraints of a macro-system. The macro-system in play here is the transport system, and these individuals actually play by the rules set out by the macro-system in place here.

A macro-system can be defined here as a large system within which micro-systems are contained. Therefore, here, we have the transport system as the large macro-system, and the individuals as the micro-systems which are contained within this large system, and taking their independent decisions within the constraints set out by it.

Now, we have a tube strike, like the one on 3 November 2010. What happens here?! The large macro-system changes. Most tube lines don't work, sever delays on lines that do, more buses on routes, cycles being transported more frequently to fill up empty slots. This creates havoc in the micro-system, but it doesn't fail. In fact, what happens is that the micro-system adjusts the way it works within the new constraints set out by the macro-system in play, and then we have the same individuals making their renewed complete independent decisions, again taking into account the most efficient way to get to work by finding the lines / buses / boats that are working, and taking those transport links, or replacing it with cycles or cars. We now have a micro-system changing, but in a way that individuals still get to work, but using the new constraints set out by the macro-system at play, and they work within these constraints. Complaints? Yes....Impossible? No, not at all!

It's the laws of the macro-system here. Micro-systems are contained within it, and they will change in order to work within the constraints of the macro-system, or even be influenced by it. An analogy with Ecological Systems Theory can also be drawn, but I'll leave that for another post!

This is the problem I wonder about when I'm designing my model, I need these micro behaviours to work within the constraints of the macro-system at play. Do I model the macro-system first, or model the micro-system and build a macro-system around it? It's the chicken or egg problem again here!

Tuesday 8 June 2010

Pedestrian flow at Euston station

A public discussion held recently at City Hall by Art on the Underground, about London journeys shows a good application of simulation of crowds. As you can see in the images below, London Underground studies people's movements through tube stations to see how they can help by regulating passenger flows through the placement of tickets gates and in turn improving the congestion.

The image above shows passenger flow before improving the congestion, simulated using Legion. The green dots are people entering, and red dots people exiting.

The flow improves considerably as can be seen once the ticket gates and hall layout were changed. The congestion is reduced as it provides more of a two lane flow of exiting and entering pedestrians. More details about the public discussion can be found on Going Underground's Blog

Thursday 21 January 2010

Paper: Aggregate Dynamics for Dense Crowd Simulation (2009)

Ming Lin's latest work has been featured in the recent publication of SIGGRAPH Asia 2009. The author presents an innovative method that is able to simulate tens of thousands of agents at interative rates.

The work achieves these rates by combining a local behavioural model with a global planner such as Continuum Crowds or Adaptive elastic Roadmaps (AeRO).

Image taken from
Image taken from
The image above shows an overview of the algorithm. So how does this actually work?

First of all, as I mentioned this approach combines a local behaviour with a global planner. The global planner here computes the flow of agents around an environment. The steps are described below:
  • Each agent is given a position and a current velocity computed.
  • Using the global planner such as the roadmap based method or Continuum Crowds method, a preferred velocity is then computed for each agent.
  • The navigable area in the environment is divided into a discrete grid of cells. The flow of particle for each cell is computed, using the current velocity and density of agents in the cell.
  • For each agent, a new velocity is computed, by interpolating the flow velocity with the desired velocity weighted by the local density at each cell.
  • Velocities of agents are constrained in dense areas by the global particle flow. In coarser areas, the agent's velocity are influence less by the global flow, and more by the velocity for the cell.
  • Finally, collision detection is applied, as well as a minimum distance for each pair of individual agents, similar to the continuum crowds simulation.
Here's a video of the simulation:

Aggregate Dynamics for Dense Crowd Simulation

A good hybrid approach used here that decreases the computation time considerably to accomodate a very large number of agents at interactive rates. The Unilaterally Incompressibility Constraint (UIC) introduced here that allows the interpolation between the global and local approach is something that has interested me.