Wednesday, 17 August 2011

Calculate Catmull-Rom splines using forward differencing

Update: Here's a little JavaScript canvas example to give you some sourcecode...

Splines are a nice for interpolation of all kinds of stuff. A very nice, thorough (Bezier) spline documentation with lots of examples can be found here.
Catmull-Rom splines are handy, because they always pass through their control points. No fiddling with tangents and stuff. You give up some control over the curve though. This is what they look like:


The formula for this type of spline is:

p(t) = 0.5 * (1, t, t2, t3)  *
[  0
2
0
0 ]
[Pa]
[ -1
0
1
0 ]
*
[Pb]
[  2
-5
4
-1 ]
[Pc]
[ -1
3
-3
1 ]

[Pd]

The interpolation parameter t runs from [0,1] and t=0 gives you Pb, t=1 gives you Pc. Pa and Pd influence the curve.
If you simplify the formula something along these lines:

p(t) = 0.5 * ( (Pd - 3*Pc + 3*Pb - Pa) * t3 + (-Pd + 4*Pc - 5*Pb + 2*Pa) * t2 + (Pc-Pa) * t + 2*Pb)

Now you can evaluate that formula for increasing values of t and once for P(a,b,c,d)x and P(a,b,c,d)y. This gives you new vectors you can use to draw lines or whatnot.

Now this formula is somewhat computationally intensive, but there's a better way to do it. You can use forward differencing to simplify the computations going on in the loop. This page describes the process quite well for Bezier curves.

A little canvas experiment

Here's some basecode for simple canvas animations:
<html>
<head>
<script type="text/javascript">
onload = function() {
  //get canvas element
  var canvas = document.getElementById('canvasexperiment');
  //get drawing context from canvas element
  var ctx = canvas.getContext("2d");

  if (!canvas || !canvas.getContext) {
    alert("No canvas or context. Your browser sucks!");
    return;
  }

  var imgd = false;
  var width = canvas.width;
  var height = canvas.height;

  //Try to create image data from scratch
  //If that doesn't work, try to load it from the context
  //If that fails too, create an array of the same size and pray
  if (ctx.createImageData) {
    imgd = ctx.createImageData(width, height);
  } else if (ctx.getImageData) {
    imgd = ctx.getImageData(0, 0, width, height);
  } else {
    imgd = {'width' : width, 'height' : height, 'data' : new Array(width*height*4)};
  }
  //get actual pixel data
  var pix = imgd.data;

  //run display loop function every 100ms
  setInterval(function() {
    var i = 0;
    for (var y = 0; y < height; y++) {
      //do some random stuff with pixel data
      var r = Math.random() * 255;
      var g = Math.random() * 255;
      var b = Math.random() * 255;
      var a = 128;
      for (var x = 0; x < width; x++, i += 4) {
        pix[i  ] = r;
        pix[i+1] = g;
        pix[i+2] = b;
        pix[i+3] = a;
      }
    }
    //write image data to canvas
    ctx.putImageData(imgd, 0, 0);
  }, 100);
}
</script>
</head>
<body>
<canvas id="canvasexperiment" width="128" height="512"></canvas>
</body>
</html>
When you put this into a HTML file and load it in your browser it should look like this:

Edit: Also note this shim for smooth animation.

Monday, 8 August 2011

Using CriticalSections to synchronize shared resource access

When developing multi-threaded applications you can never be sure when and in which order threads run, so you have to synchronize access to shared resources. Otherwise, for example, one thread could modify a piece of data while another thread reads or modifies it. This can give you inconsistent data or, especially when resource allocation/deallocation is involved, crashes.

Threads and thread synchronization is a vast topic and handled differently on every OS. There is POSIX threads (Pthreads) for Unixes and the Thread API for Windows. C++0x is supposed to have a std::thread class, but support (at least in Visual Studio 2010 - shame on you MS) is missing. But there are other portable thread implementations, notably boost::thread and TinyThread++. Use those if you can, licenses permit derivative work for non-commercial and commercial usage without having to contribute sources back.

Now to CriticalSections. They are supposed to be faster than Mutexes on Windows, because they use processor-level functions rather than OS-level functions, but they can only be used by threads of the same process.
The following code shows how a critical section (SynchronizedData::_cs) can be used to provide synchronized access to a resource(SynchronizedData::_data).
class SynchronizedData
{
public:
    int _data;
    CRITICAL_SECTION _cs;

    SynchronizedData()
       : _data(0) {
        InitializeCriticalSection(&_cs);
    };

    bool lock() {
        __try {
            EnterCriticalSection(&_cs);
            return true;
        }
        __finally {
            LeaveCriticalSection(&_cs);
        }
        return false;
    };

    void unlock() {
        LeaveCriticalSection(&_cs);
    }

    ~SynchronizedData() {
        DeleteCriticalSection(&_cs);
    };
};

class SomeThread
{
    HANDLE _handle; //thread handle of object
    bool _run; //true while the thread is running. set to false to exit threadLoop()
    SynchronizedData & _sdata; //shared data object reference
    
public:
    int increaseCount; //just here to count how many times this object has increased the data

    SomeThread(SynchronizedData & sdata)
       : _handle(NULL), _run(true), _sdata(sdata), increaseCount(0) {
        //create new thread passing this object as a parameter
        CreateThread(NULL, 0, _handle, &this, 0, NULL);
    };

    DWORD WINAPI threadLoop(LPVOID parameter) {
        //we get the this pointer of the object that created the thread here (s.a.)
        SomeThread * thread = (SomeThread *)parameter;
        if (NULL != thread) {
            while(_run) {
                //try to lock resource for us
                if (thread->_sdata.lock()) {
                    //resource locked. we can use it
                    thread->_sdata._data++;
                    //finally unlock resource again
                    thread->_sdata.unlock();
                    increaseCount++;
                }
                Sleep(100);
            }
        }
    };

    void stop() {
        if (_run) {
            //set _run to false to gracefully quit threadLoop()
            _run = false;
            //and wait for the thread to quit
            WaitForSingleObject(_handle, INFINITE);
            //close thread handle
            CloseHandle(_handle);
        }
    }

    ~SomeThread() {
        stop();
    };
}; 
int main() {
    //create data
    SynchronizedData sdata;
    //create threads and run them
    SomeThread thread1(sdata);
    SomeThread thread2(sdata);
    //idle around in this thread, printing the value of data every second
    while(true) {
        //try to lock resource for us
        if (sdata.lock()) {
            //resource locked. we can use it
            printf("data: %d, thread1 count: %d, thread2 count: %d\n", sdata._data, thread1.increaseCount, thread2.increaseCount);
            //finally unlock resource again
            sdata.unlock();
        }
        Sleep(1000);
    }
    //before exiting stop threads
    thread1.stop();
    thread2.stop();
    return 0;
}

Writing a DLL containing C++ classes

Putting functions into a DLL is a good thing. It helps you to reuse stuff, save space on updates, save build time etc. To write a DLL the proper way you have to keep some things in mind though. Those hints are basically the "best-practice" from this page.

A DLL is a library, a collection of data and/or code. To use a DLL, on Windows (on Unixes this is a bit different) you need a .h file(s) declaring the functions and classes contained in the DLL (if any),  a .lib file containing stubs for the functions in the DLL, possibly a .def file containing the exported functions and the actual .dll file containing the code and data.

When writing a DLL you will want to export some functions from the DLL you want make available to the outside. Those you need to declare with __declspec(dllexport):
class __declspec(dllexport) CC {
    void foo();
};
Now the problem with that is that the compiler does name mangling - it gives the functions/classes a unique name - but how it does this depends on the compiler and its version. A DLL compiled by one compiler can thus not be used with a different compiler. UNLESS you define the functions as extern "C" and their call type as APIENTRY. The problem with that again is, that those are C functions. APIENTRY is also usually __stdcall, meaning those can't be (non-static) class members - Not what you want unless you have "all static" classes.
The workaround is using a virtual base class for your class and providing an object creation/destruction function:
class CCInterface { //notice: no __declspec(dllexport) here
    virtual void foo() = 0;
    virtual void Release() = 0;
};

class CC { //notice: no __declspec(dllexport) here either
    void foo() {//do something};
    void Release() {delete this;};
};

extern "C" CCInterface * APIENTRY createCC() {
    return new CC;
}
This is also more or less the way COM works, which is in turn why all compilers support this. The downside is that you can not put the creation function into the interface and you need to explicitly call the release function. You could get around the Release call by using an auto_ptr or use the AutoClosePtr from the original document.

When you create a class that is a singleton you can get around having to call Release() by destroying the object when the DLL is detached from the last process:
static int attached = 0;
static CC * instance = NULL;

extern "C" CCInterface * APIENTRY getCCInstance() {
    if (NULL == instance) {
        instance = new CC;
    }
    return instance;
};

BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpReserved)
{
    //Perform actions based on the reason for calling.
    switch(fdwReason) {
        case DLL_PROCESS_ATTACH:
        case DLL_THREAD_ATTACH:
            attached++;
            break;
        case DLL_PROCESS_DETACH:
        case DLL_THREAD_DETACH:
            //Delete instance when the last process/thread detaches.
            if (0 >= --attached && NULL != instance) {
                delete instance;
                instance = NULL;
            }
            break;
    }
    return TRUE; //Successful DLL_PROCESS_ATTACH.
}
You could also use an auto_ptr for that purpose.

Saturday, 6 August 2011

Compiling videoInput in Visual Studio 2010

Update: This is old. OpenCV has a pretty decent working camera interface by now. Use that instead. If you still want the DirectShow libs I re-uploaded them for you. Follow the link, Luke.

First of all thanks to Theodore Watson for making the videoInput library! It is pretty handy for using webcams etc.
Compiling it for windows can be "tricky" though. The included instructions are not completely correct and miss some important issues. I tried to make my instructions for Visual Studio 2010 in the same style, but a bit more elaborate. Cross your fingers as YMMV, as usual. Here goes:

REQUIREMENTS
  1. Install the Express Edition of 2010 (I tried this on VS2010 Professional).
  2. In the orginal "\videoInputSrcAndDemos\libs\DShow" directory eg. the "basetsd.h" file is b0rked (it doesn't fit winnt.h). Download the adjusted DirectShow libs. Replace or overwrite the "DShow" folder with this. It should save you the stuff mentioned in the "COMPILER ERRORS" section.
  3. First try compiling without this! The Windows SDK installed with VS2010 (at least Professional) should suffice to compile. If you have the Express Edition you might need to install the Windows SDK (choose the appropriate platform). This is >1GB. Yes, I know. I'm sorry, but this saves you having to download the rancid DirectShow and DirectX SDK from 2005.
  4. Preparing the souce code and project settings. Use the project from the VS2008 directory, copy it somewhere and adjust it. Important stuff:
  • Make sure that the "C/C++"->"Preprocessor"->"Preprocessor Definitions" are:
    "WIN32;_DEBUG;_LIB" for Debug and
    "WIN32;NDEBUG;_LIB" for Release
  • Make sure your remove the lines:
    "#define DEBUG 1"
    "#define _DEBUG 1"
    from the start of videoInput.cpp. They make absolutely no sense and produce linker errors.
  • Make sure "Code Generation"->"Runtime Library" is set to use the SAME version of the VS-DLLs in Debug and Release. So either:
    "Multi-threaded DLL" and "Multi-threaded Debug DLL" or
    "Multi-threaded" and "Multi-threaded Debug"
    Don't mix them unless you know what you want to do.
  • Make sure you build differently named libs. Set "General"->"Target name" to:
    "$(ProjectName)" for Release and
    "$(ProjectName)d" for Debug
    This will give you a "videoInput.lib" and "videoInputd.lib" you can keep in the same folder.

    VC++2010 SETTINGS
    • INCLUDE PATHS
      Make sure the standard VC include dirs come first, then the Platform SDK, then the other stuff like the DirectX SDK (if you have this).

    COMPILER ERRORS
    • If you get a compiler error error C2146 for winnt.h:
      The problem may be the include order. Make sure the standard VC include dirs come first, then the Platform SDK, then the other stuff.
      If that doesn't help, try renaming/deleting the file "basetsd.h" from the /libs/DShow/Include folder. It may not be compatible with the winnt.h file you're using...
    • If you get a compiler error C4430 in ctlutil.h:
      The problem here is that this member operator function does not have a return type:
      operator=(LONG);
      Change it to:
      COARefTime& operator=(LONG);
      Read about it here.

    LINKER SETTINGS FOR MAKING STATIC LIB
    • Make sure you have your Additional Dependecies in "ProjectSettings"->"Librarian"->"General" set to:
      "dxguid.lib ole32.lib strmiids.lib uuid.lib"
    • And "Link Library Dependencies": set to "yes".
      When it compiles you will get a LOT of warnings but it should build fine - nice static lib.

    LINKER SETTINGS FOR USING COMPILED LIB
    • If you get an error about atlthunk.lib add this to your ProjectSettings->Linker->Command Line:
      '/NODEFAULTLIB:"atlthunk"'
    • The compilation instructions for VS2008 state you should add:
      '/NODEFAULTLIB:"LIBCMT"' to the Linker Settings.
      This is not necessary if you make sure that you have paid attention to 4.