verlet integration

little fun with gaming physic, written using Three.js, the 3D library built ontop of HTML5 and WebGL. Physics engines like ODE or PhysX support a wide range of simulation: rigid body, soft body objects… While those engines are powerful, they are somewhat weak in scalability, e.g: to simulate the flag below, we need to create an array of hundreds of objects, which may not really feasible on small devices.

This demo tries its own physical calculation called Verlet integration: numerical method to apply Newton’s second law of motion to a system of point masses. Verlet integration, despite its complicated formal description, is simple enough to be calculated and executed in real time on the low end mobile devices.

The demo works best on Chrome but it should work on any browser that supports <canvas> (try dragging the flag to add some motion).

signals and slots

C makes U hang yourself;
C++ even gives U a rope object to hang;
C# scourges U using a rope wrapper!

rarely talk about programming unless it comes to some new idea or something fun. However, in this article, I’m going to summarize a part of experiences in my career, about important concepts that I’ve learned and used: signals and slots. First appear and remain as fundamental concepts in the Qt library (“Qt” pronounced “cute” – which is so cute as a cross-platform application framework), the concepts has been adapted and developed into some other libraries (such as boost) and are being proposed as next standards for C++ language.

Please note that we’re talking C/C++ here, although signals & slots has been brought to many other languages (Java, Python, Ruby, JavaScript, etc.) Every coin has two sides and C/C++ is no exception, it has its own advantages and disadvantages (depend on types of applications). But the thing I like about C/C++ is that its half – civilized nature made it a strong language: the balance between abstraction and comprehensiveness has always been considered as core factor.

Noone want to build general applications using Assembly, and noone want to write lengthy code just for some simple features. To adhere the doctrine, strong – abstraction concepts must be introduced to capture grammar of the language, and simple, clear syntax that would make the code concise and comprehensive.

I came to signals & slots as solution to problems I’ve met when leading the CMS project, a DVRs managing software (client & server) with complicated GUI: a few screens, each screen can have a dozen tabs, each tabs can have hundreds of controls. Events on one control can affect other controls on other tab or screen, events can be user inputs as well as various signals come from dozens of (managed) network client machines.

The overwhelmingly – complicated communications surpass every MPM (message passing method), then signals & slots appeared as a saviour solution. To be simple, signals & slots is a very efficient mean of interaction between objects within a process space. I personally think it would be the next metaphor extension added to C/C++ language. Structure of this post would be as follow:

1. Introduction to signals & slots, from raw to abstract concepts.

2. ISO C++ compliant and cross – compiler, cross – flatform problems (would discuss about delegate and how function pointer has evolved from C to C++).

3. Different implementations of signals & slots: Qt, boost, sigslot, libsigc++

1.   INTRODUCTION

Flow of code is no more than a series of function call, and to perform asynchronous function call, traditional C programming use callback. A callback is a pointer to a function, so if you want a processing function to notify you about some event, you pass a pointer to another function (the callback) to the processing function. Callbacks have two fundamental flaws: firstly, they are not type-safe, we can never be certain that the processing function will call the callback with the correct arguments. Secondly, the callback is strongly coupled to the processing function since the processing function must know which callback to call. In C, to define function pointer, you would write something like this:

float (*my_func_ptr)(int, char *);
typedef float (*MyFuncPtrType)(int, char *);
MyFuncPtrType my_func_ptr;

When move to C++, things are a bit more complicated (note the weird syntax ->* to call a member function through pointer).

float (SomeClass::*my_memfunc_ptr)(int, char *);
my_memfunc_ptr = &SomeClass::some_member_func;
SomeClass *x = new SomeClass;
(x->*my_memfunc_ptr)(6, "Another Arbitrary Parameter");

Though a very strong concept in C, function pointer add little to the language C++. The only two uses of member function pointer in C++ are:

  • Demonstrate the tricky syntax of the language.

  • Help in implementation of delegate.

Now, imagine slots as invisible communication channels, every object can register to listen to some channels by providing delegates (pointer to a member function). The delegate would be invoked when slot is “filled” with a signal. The signals and slots mechanism is type safe: signature of a signal must match signature of the receiving slot. Signals and slots are loosely coupled: a class which emits a signal neither knows nor cares which slots receive the signal. To summarize the benifits:

  • Syntactically neater: signals & slots make for very readable code: you define the signals, you define the slots, then you wire them up.

  • Inherently robust: when either end of a signal/slot connection is destroyed, the connection is automatically removed. It is therefore impossible to emit a signal and have it arrive at a class that has already been deleted. Best of all, you don’t need to write any cleanup code.

  • Easier code reuse: since the thing that has to type-agree is the signal and the slot, not the whole class interface, it is much easier to plug together disparate classes that had never initially been intended to work in that way.

2.   DELEGATE

To summarize section 1: pointer is the root of all evils. Function pointer is the physical of callback method traditionally used in C programming. When evolved to C++, the C++ standard committee failed to address how to define function pointer to a single C++ object. With common-sense knowledge, we know that it take two elements to represent the thing: first is the address of the object itself (the implicit pointer this), second is pointer to the object’s member functions. The undefined land leads to different implementations across various compilers.

Contrary to common belief, the actual physical storage of pointer differs between various compilers, and even differs between types of pointer, e.g: pointer to a single – inheritance object, an multiple – inheritance one or virtual inheritance. The table below shows how many bytes it take to store pointers on different compilers (just make use of the operator sizeof). Then to calculate the actual member function’s address, each compiler uses one kind or another of offset:

struct BorlandMFP
{
        CODEPTR m_func_address;
        int delta, vindex;
};
if (vindex==0) adjustedthis = this + delta;
else adjustedthis = *(this + vindex –1) + delta;
C++
compiler
void*
pointer
function
pointer
single
inheritance
multiple
inheritance
virtual
inheritance
MS VC++ 4 4 4 8 12
GNU G++ 4 4 8 8 8
Borland C++ 4 4 12 12 12

So, delegate is just the new name for pointer to (an object’s) member function. The hard part really is that: since each compiler stores different type of pointers differently, there’s need for a way to store delegate in a universal manner: cross compilers and cross flatforms. Various techniques have been proposed by excellent programmers. Please refer to the articles below for specific techniques. I personally would prefer the method of Quynh Nguyen, an engineer at Global Cybersoft (Vietnam) Ltd.

3.   IMPLEMENTATIONS

To make those obscured concepts above clearer, I would go into some detailed implementations of signals & slots with the emphasize on the sigslot library, for this is really a compact lib: everything is contained in just one header file. Suppose you have a server that would receive some signal from network (tcp socket), then parse the received data and trigger some processing (display on GUI, store to disk…). We would define the “network signal” as follow (please note any number of parameters can be defined, we use an int and a char* here just for the example):

// the temmplate ‘signal2’ denote for
// a signal with 2 parameters

signal2<int, char*>m_netSig;

Then, at the place you want to process that event, e.g some class CDisplayForm, you would need to provide a function to process the signal:

DisplayForm::OnNetSig (int cmd, char* data)
{
  // the delegate would be invoked
  // when the signal is recieved

}

Please note that multiple objects can register to a same signal slot (and vice versa), e.g some class CRecordThread would also need to log that event to database. Then the listening objects would just register with the signal slot using a connect function:

// we pass the function pointer
// here to be called later

m_netSig.connect (this, &CDisplayForm::OnNetSig);

When the network signal arrive, e.g in some class CAsyncSocket, we would fire the signal and get it populated to all connected objects:

// emit the signal with it’s data
m_netSig.emit (NETSIG_DATA_RECEIVE, xmlStr);

Then the CDisplayForm and CRecordThread object would both receive the signal. Please note that when either end of the communication channel go out of scope, the connection is automatically removed, you don’t have to write any cleanup code. Just define the signal, the slot and wire them up! Any unrelated classes can be wired up in this type-safe manner without any pre-defined relation within them.

Speaking as an ex-hardware designer, I’d like software components to have pins around their edges, like ICs, so they can be ‘wired up’, but otherwise should be well behaved… I don’t want to know how that pin is wired internally – I just want to know that it will work when I send a signal into it.
(Sarah Thompson – sigslot library)

CMS 2.0 released

Some typical UI features:

Data & input validation using XPath

Custom-drawn combobox (with check-box item)

Custom-drawn grid with tens of thousand cells

Simple vector object editing

Custom-draw tree with loading effect

he CMS project, in which I’m the team leader, has come to it’s second phase, with major features completed. Although I felt tired with the on-going work, it’s my most beloved product. CMS (short for Central Management System) serves as a gateway through which clients manage the DVR Servers (Digital Video Recorder). The product demonstrates many technologies & programming techniques, just to name a few:

  • IOCP (IO completion port): the multi-threaded IOCP server has proved to be very efficient, hundreds of concurrent connections won’t rise CPU usage to higher than 5%. However, the connections are stateless, it’s best that we would add a state-machine to better control the traffic.

  • TCP + XML communication: we devise a draft protocol like XML-RPC or SOAP, which bases on TCP rather than HTTP.

  • XML data storage: all network command & data is presented in XML. With version-numbered XML, we hope to solve the backward compatibility problem ever existed with so many releases of our main DVR products.

  • XML processing is made easy thank to the wonderful TinyXML and TinyXPath libraries. I must emphasize that XPath makes XML processing much more feasible, it greatly reduces the number of LOC (line of code) and procedural complexity.

  • A sophisticated client MFC GUI demonstrates various GUI programming techniques, almost every tricks with MFC GUI has been gathered in this product: heavy custom-draw controls, flicker-freed rendering, advanced input validation…

  • Some borrowed concepts from other flatforms: the elegant “signal & slot” are added to handle complicated interaction between GUI’s elements (in addition to MFC’s message queue mechanism).

I have some lessons learned after the project:

  • It’s a MUST that you have a team with members of the same professional level. This would make sure the members would easily understand each others and share a common culture.

  • C/C++ is still a MUST for real time programming tasks (it’s “half-civilized nature” makes it a strong language). And the use of some matured flat-form: boost, wxWidget… would greatly help the developing process.

  • It’s only by the desire for creation & creativity that programmer would offer an excellent product. The culture of a developing team is somewhat like honey-bees, who collect pollen little by little to make honey and wax.

I’ve been involved in many projects, some is more interesting, some is more difficult than this one. But this is the first one that I’d made, everything from A to Z. It’s now time to leave I3 but I must say this is the project that I loved and two years at I3 was a special time in my career! Looking at the screenshots below, you would see that CMS is very rich in it’s designs about information presentation.