As many of you know, in recent years I have been working at Noesis Technologies in charge of the technology. We have been very excited these days because we are ready to release our first public software, our internal user interface technology released as a middleware called NoesisGui. This week we are starting to roll out the SDK to participants in the private beta program and as many of you have asked questions about technical details I though it would be a good idea posting here a brief overview of the technology complexities we faced in NoesisGui.

At the beginning of the development of NoesisEngine, in 2009, we were evaluating different options we had for the user interface and neither of them really satisfied us. We were looking for a GUI that was fully portable, flash-like and fully GPU accelerated. We discussed and decided to develop, in parallel with the rest of our projects, our own technology for rendering user interfaces. One of the big troubles we were aware of was the editor. We didn’t have the resources to implement an editor so we started to evaluate using an already established format. Our first option was parsing swf files but we really didn’t like that option because flash without action script is useless and we didn’t want to interpret action script because we were looking for a native c++ solution. Apart from that, swf is a binary proprietary format and depending on a proprietary tool for editing our resources didn’t appeal us at all. Other options were equally insufficient for us: qt, xul, wxWidgets, windows form, etc. And then we discovered xaml. Xaml is an open declarative xml-based language format developed by Microsoft. Xaml is used extensively in several Microsoft products like WPF, Silverlight or the Metro UI. Thanks to its great versatility, we finally chose xaml for NoesisGui. There are excellent editors like Microsoft Expression Blend, Visual Studio, Kaxaml or XamlPad and being a xml format it can be edited by hand allowing easy integration with external tools and pipelines.

And that is basically NoesisGui, a xaml interpreter that renders using hardware graphics. Let’s dive into the details.

Xaml Interpreter

Xaml is a declarative xml-based format with lots of quite interesting features like routed events and dependency properties. It is so powerful that you can even write user interfaces with animations, reactions to events or visual transitions without touching a single line of code.

The first step performed to visualize a xaml in NoesisGui is converting it to our native format. In Noesis we have an universal object model based on reflection and every object loaded at runtime must be stored in that format. This conversion is usually performed offline and the result is an optimal binary blob that loads super fast on each target platform.

At runtime we maintain two trees. The first one represents the logic part and it is the one you interact with. This tree is stored directly inside the binary blob. The second tree stores the visual representation. It contains the nodes you see on screen. This tree is the result of expanding the logic tree with visual templates. For example, a button depending on its skin may be represented with a rounded rect or with an ellipsoid. This template mechanism is what allows skinning and it is usually applied at load time. When the visual tree is ready it contains all the instructions to render itself on screen. The rendering part is done by our vector graphic library. This is where the interesting stuff begins.

Vector Graphics Library

VGL is our SVG-compliant renderer. We experimented with different implementations like openvg and direct2d although we finally opted for an implementation on top of our directx /opengl gpu renderer. This ended up being the most portable and flexible solution. In this implementation all calculations run inside the gpu through different shaders. A combinatory of approximately one hundred shaders is needed to cover all cases.

The most important challenge faced here was that everything can be animated. For example, geometries may need tessellation on each frame or ramp stop points may be animated. To improve the stress in the communication between cpu and gpu different caching and compression mechanisms were implemented. For example, ramps are heavily compressed on the cpu side and geometry vertices are stored in float16 whenever possible.

Another important aspect to consider is minimizing the number of batches that are sent to the graphics card. For that purpose our vector library uses a very aggressive batching mechanism. You can draw elements in the order you desire because this algorithm will sort the primitives to minimize the number of draw calls.

Tessellation

After the visual tree is updated we need to generate primitives compatible with the gpu, that is, triangles. This is performed in two steps:

• Flattening: where curves are converted into straight segments.
• Triangulation: where contours coming from the flattening step are converted into triangles.

The triangulation step is critical and can easily become a bottleneck. We tried different implementations:

• An implementation using the stencil buffer. We discarded this technique because it is very fill-rate hungry and caching the results in images was not memory efficient. Besides that we were already using the stencil buffer for other purposes.
• We tried more gpu alternatives but we found all of them too complex and unable to implement all the svg features. And for portability purposes we did not want to use complex shaders.
• After all the mentioned problems we ended up using a pure cpu solution and implemented a polygon tessellation algorithm based on libtess but with several memory optimizations. This chosen solution allowed us to cache static geometry very efficiently.

Threading Architecture

The task of rendering a single frame on NoesisGui is subdivided into many small jobs that are processed by a task scheduler:

• All the logic always happens in the thread of the caller. Logic actions that change the visual representation (for example clicking a button) are packed in a job.
• The job that calculates the new visual representation needs each changed path to be tessellated. A job for each tessellation is created.
• Render commands are sent to the GPU with a job.

Dependencies between jobs form a graph that represents the full frame execution. The more cores are available in the host the faster that graph is consumed. All this complexity is hidden from the point of view of the sdk client that receives a single API with two asynchronous methods, Update() and Render().

For the task scheduler we use tbb, an Intel library that also comes with an interesting scalable allocator.

Antialiasing

High visual quality is a very important aspect where we compete with traditional software rasterizers that render with an almost perfect antialiasing algorithm. NoesisGui offers two solutions for fighting aliasing:

• NoesisGui is compatible with MSAA surfaces. We take into account sub-pixel information to properly flatten curves, render glyphs or displace paths. MSAA is usually very fast on modern gpus although not so fast on mobile devices. Also MSAA requires a lot of more memory. That is why we experimented with other options.
• When a MSAA surface is not available or when MSAA is too inefficient we extrude the contours of the path to get an approximation of pixel coverage on each pixel. This technique is mentioned in the CodeItNow blog. The problem with this technique is that shapes are slightly altered.

Definitely, antialiasing is an unsolved problem which needs more experiments to get 100% satisfactory results when MSAA is disabled. What is really frustrating here is that this problem could be easily solved if we had access in the pixel shader to the pixel coverage calculated by the rasterizer.

Font rendering

The appearance of fonts is crucial to improve the quality of any GUI. Freetype is the third-party we are using for rendering font glyphs. We experimented with different text rendering techniques to end up implementing the following ones:

• We opted for disabling hinting as much as possible because it deforms the aspect of the font. In NoesisGUI only vertical hinting is considered and horizontal sub-pixel displacements are allowed. The reasoning behind this is perfectly explained in a document from the excellent AGG project.
• When rendering on LCD displays sub-pixel font rendering technology is used. This technique can be implemented in hardware as detailed in beyond3d forums.
• As the rest of paths, stroking can be applied to text. For example, by stroking text without filling the interior, you can achieve an outline effect.

Conclusion

I have highlighted the most interesting features of NoesisGUI. Of course, we offer the rest of features you would expect in a decent sdk (like profiling information, memory hooking or filesystem abstraction) and that I am not mentioning here because I do not want to bore you.

After all the time working on this part of Noesis engine, we are confident that NoesisGui is one of the most powerful, if not the most, GUIs for real-time applications. We encourage you to test it and give us feedback. Beta program is already available for free! And as always, comments are welcome here or in my twitter account.

  
Follow @noesisengine

Follow @EntTwit

Whoops, long time since my last post! It’s been exciting days this last year working very hard in different projects starting an own small business with my partners. Next week we are going to shed light on at least one of them.

I have several draft articles pending to be published here. As soon as I have time I will recover energy for this blog.

Meanwhile, you can follow me on my twitter account: @EntTwit

The Art of Multiprocessor Programming
Author: Maurice Herlihy & Nir Shavit
Pages: 508
Published: 2008

Multiprocessor is everywhere now. After a period of uncertainty and fear we are starting to grasp multiprocessor architectures. We have started to forget about threads and started to think about tasks / jobs to decompose algorithms. The book The Art of Multiprocessor Programming will help you to have a solid background to implement a powerful multithreading architecture in your application.

The book is written as a textbook and each chapter at the end includes exercises that practice the presented concepts. In spite of the fact that this book may seem too academic in some sections, it is written and structured precisely. Java language is used in all samples although there is an appendix at the end of the book which describes the basic techniques using C# and C++ (using POSIX Threads). This book is definitely not for copying code but it is to understand deep details. After reading you should be prepared to start implementing these techniques yourself although I would recommend to use a good middleware (like TBB). Both actions are complementary to this book.

The book is structured in three parts. The content of the first part is definitions of mutual exclusion, fairness, memory models, shared memory and it may be hard to read. The second part is dedicated to real implementation. Firstly, basic tools like spin locks, monitors and semaphores are studied and implemented. Next, high-level containers are implemented using different techniques (mutexes, lock-free algorithms, etc): linked lists, concurrent queues, concurrent stacks, concurrent hashes, skip lists and priority queues. The chapter 16 is quite interesting. It is dedicated to futures and scheduling. Implementations like the Cilk Scheduler are described and implemented. The last part of the book (although included in the practice section) is dedicated to further experimental techniques like Transactonal Memory. It is good to see a working implementation of it.

I strongly recommend this book for the core programmers of your team, for those who will be in direct contact with the multithreading architecture. Although I would prefer a version of the book in C and I found some bugs and errors (probably due to being the first revision) I have not found other better book.

Rating: 7 / 10

I have dedicated the last few days of work to face a problem that is getting bigger and bigger. Although we have a quite modular codebase, use interfaces whenever possible to hide implementation details and apply most of the recipes recommended in classic books, our linking times have started to be a problem in some of our libraries. Linking times is not the only problem. Our binary sizes are becoming really fat.

After a thoroughly study with the help of tools like Sizer, Symbol Sort (I strongly recommend reading the articles associated to this tool: 1, 2, 3, 4, 5, 6 and passing all them to your co-workers) we discovered lot of code bloating generated by improper template usage. The template is a powerful tool that can be easily misused although I am not against using it. We use template metaprogramming in lots of places like reflection, annotations, uri-like dependency properties, serialization and more places where it is worth it. The problem with templates is that normally declarations and definitions go in the same header file. With that structure a compiler is normally forced (although some compilers allow customization) to generate template instances in each obj file. Redundancy is eliminated in the linking phase, of course taking time. This is one of the faces of template bloating. The other face appears when you templatize functions when it is not strictly necessary. And you pay for it in the final size of your binaries.

Trying to solve all this, we applied a solution that although yet not standard seems to work in all compilers we tested: exporting explicit template instantiations. This technique applies when you have a template that is to be instantiated for only a few known types. Those instantiations are exported from a dll. This allows even hiding big functions in the .cpp without having to show them in the header. With this solution you have the best of both worlds: short functions can be inlined by the compiler and large functions instead of being instantiated in each compilation unit are referenced as an exported symbol. By the way, a special behavior of Visual Studio (to me, it is a bug) has the effect of non inlining functions being defined outside the class when exporting the template. We had to move our definitions (that we usually have pseudo hidden in a .inl file) to inside the class declaration.

We applied this strategy in several places reducing the bloatage by a considerable factor. For example, the vector library seems an ideal target because you normally only instantiate that library for a few types (float, double, int) and “big” functions like Invert() for 4×4 matrices can be hidden and exported from the dll. Another good candidate is std::string (instances for chat and wchar_t). Although, at least in MSVC, this job is already being done by the crt (not tested in other platforms).

I hope you find this useful. Thanks for reading and welcome to all the new subscribers since my last post!

Documentation is the part of the development process where usually less time and money is invested. Few resources implies a poor infrastructure for something that, as the project gets bigger and bigger, becomes a very important part of the overall process.

I want to share in this post the approach we are following for a project I have been involved with for over two years. This project (I will be able to give details about it very soon) is mainly a framework composed of libraries to be used by other companies. Basically, a work from developers to developers, clearly a context where documentation becomes very important.

The main objectives we tried to achieve with this architecture:

• Documentation must be located in the code repository. This means that each development branch has its own documentation that is integrated in the same way that the code.
• Documentation generation must be part of the building process. We use our build pipeline for everything: compile versions, test versions, compile data packages, generate installers, distribute symbols and, of course, build documentation. This means that the source of the documentation must be a very basic representation, easy to edit, that later is converted to a pdf, doc, html by the building process. This point implies that the documentation can be easily distributed to clients or even generated by themselves.
• Access to current documentation must be integrated into the development environment. In the same way I can review bugs in the bugtracker, stories in the task manager and browse the source code I must be able to read the current documentation from a web browser without having to rebuilt it manually.

We make the distinction between two kind of documentation: API Documentation and Technical Articles.

API documentation are those documents where class usage is described: description for each function, for each parameter, enumerations, etc. Doxygen seems the perfect fit for this purpose. But after several projects using it we opted for not using it in this project because we considered it a waste of time. Doxygen may be really useful to generate documentation for a library that is distributed without sources but one of the pillars of our development philosophy is to always provide source code to clients. This way, they can choose how to compile it: one dll, several dlls, one lib… and tweak the different configurations. Another good rule that we follow is that code must document itself. Doxygen would force us to write code like this:

class MemoryManager: public MemoryAllocator
{
    /// Allocates memory on a specified alignment boundary
    /// \param size Size in bytes of the block requested by the user
    /// \param alignment The alignment value, which must be an integer power of 2
    /// \return A pointer to the new allocated block of memory
    /// \remarks Thread-safe
    virtual void* AlignedAlloc(size_t size, size_t alignment) = 0;
}

Quite redundant code, don’t you think? Obviously AlignedAlloc() allocates memory that is aligned on a boundary, I do not need a comment for that! The same for the function parameters. So we ended up writing documentation for only the parts that are really confusing or need a clarification (for example, the fact that AlignedAlloc() is thread-safe) and using the source code as the documentation itself for both the interface and the implementation. We augment this documentation by using unit tests that serve as example usage for each class. We know this decision is a controversial one and may be in the future we return back to using Doxygen or something similar. But for now, it is working fine.

A technical article is like a manual that describes the architecture and philosophy of a specific part of the framework. They provide information to a deeper level than the mere description of classes provided by the API documentation. We usually link to technical articles from API documents.

Although a wiki seems an ideal candidate for writing technical articles we rejected it because it didn’t satisfy the points enumerated above. Years ago and inspired by the Gentoo Documentation Project I used DocBook for a similar purpose. I wrote about it in a previous article: Documentation using XML. And although the results were quite satisfactory I didn’t want to return to that solution, mainly because a XML format is hard to write, edit, maintain, etc. I think we found a better solution: reStructuredText. reStructuredText is part of the DocUtils suite and from very simple what-you-see-is-what-you-get plaintext markup it generates quite good looking documents. Another bonus feature that finally inclined the balance towards reStructuredText is that it perfectly integrates with Trac which we have been using since the beginning. Trac is a suite that integrates wiki, bugtracking, source code browsing and task management in a single web program. I like to see trac as a free alternative to FogBuz. Trac supports both its own wiki format and reStructuredText allowing us to integrate the documentation located in the repository as part of our wiki infrastructure satisfying the last point mention above. Time will say if this infrastructure will suffice.

Want to comment how do you solve the documentation issues in your project? Please do so. Comments are open. Thanks for reading.

Imagine, for example, a generic object factory where object instances are created using unique identifiers. The classical solution here is having a shared-by-all-code header where all the identifiers are declared in a C enumeration. This solution, apart from creating a serious physical dependency where adding a new identifier to the enumeration forces a recompilation for all the project, is unfeasible in modular architectures where modules are isolated. In those architectures having a global header is not an option.

One viable solution may be using strings as identifiers. But strings are heavy objects, hard to compare and prone to typing errors because miswritten symbols would be detected at run-time instead of compile-time. Other equally insufficient solutions to this problem include FourCC and esoteric template tricks for generating a hash at compile time (desist from it, it is not possible to solve this 100% with templates because strings cannot be used as template parameters and anyway hashing a string is not collision-free. More information in this usenet thread). Mick West proposes more solutions in his Practical Hash IDs article.

What follows is an implementation that has been working nicely for me and that satisfactorily fits the requirements for simulating compile-time strings. First let me show you two examples of the usage:

namespace
{
DECLARE_SYMBOL(CubeMesh)
DECLARE_SYMBOL(SphereMesh)
DECLARE_SYMBOL(DuckMesh)
}
 
void CollectNodes(Ptr<Node>& node)
{
    Ptr<Mesh> mesh0 = CreateObject(S(CubeMesh));
    node->Add(mesh0);
 
    Ptr<Mesh> mesh1 = CreateObject(S(SphereMesh));
    node->Add(mesh1);
 
    Ptr<Mesh> mesh2 = CreateObject(S(DuckMesh));
    node->Add(mesh2);
}

namespace
{
DECLARE_SYMBOL(FirstMessage)
DECLARE_SYMBOL(SecondMessage)
DECLARE_SYMBOL(ThirdMessage)
}
 
void ProcessMessage(const Message& msg)
{
    if (msg.id == S(FirstMessage))
    {
       /// ...
    }
    else if (msg.id == S(SecondMessage))
    {
       /// ...
    }
    else if (msg.id== S(ThirdMessage))
    {
       /// ...
    }
}

A symbol represents a compile-time string. They must be declared before being used. The macro for declaring a symbol is hiding an inline function with a static inside itself:

#define DECLARE_SYMBOL(id)\
    inline Symbol __GetSymbol##id() throw()\
    {\
        static size_t sym;\
        if (sym == 0)\
        {\
            sym = GetIdFromString(#id);\
        }\
        return Symbol(sym);\
    }

The function GetIdFromString() hashes the string, stores it in an internal table and returns the table position for that string (the Symbol class is a simple wrapper around the identifier). This is done only the first time the symbol is requested. For future requests the static ID is returned. This adds a little overhead against using simple integers as symbols. Beware of local static initializations: they are not thread-safe. That is the reason of the manual comparison against 0. GetIdFromString() must be thread-safe for this code to work.

The S macro simply invokes the local function previously generated:

#define S(id) __GetSymbol##id()

And there you have it. Compile-time strings with negligible (in case you are doing anything more that simply comparing symbols) overhead. In case you need 100% efficient code you could pre-generate a table with the symbols being used by your project (searching for all DECLARE_SYMBOL blocks) and substitute each S() with a really unique identifier generated at compile-time. And that would be so easy if the preprocessor could be extended in a standard way…

Hope this makes sense. Thank you for reading.

1. Practical Hash IDs
2. FourCC
3. Compile-time string hash generator

Andrew Glassner’s Notebook
Author: Andrew Glassner
Pages: 304
Published: 1999

During periods in which I need to stay focused in hard technical problems I try to avoid reading dense books because they distract me from my work. I found this book in my bookshelf, in the stack of unread books , and decided to skim it a little bit. “This book is about having fun with computer graphics”, that’s the beginning of this book written by Andrew Glassner (editor of the mythical The Graphics Gems series, when the gem series were not a virus, and the classic Principles of Digital Image Synthesis among others). As soon as I started to read the first chapter I couldn’t stop.

I was expecting to find a book very similar to the Jim Blinn series, the Jim Blinn’s Corner. And although the structure and the origin is the same, a compilation of articles published by Glassner in a column of the bimonthly magazine IEEE Computer Graphics & Applications, this book is radically different to other books about graphics and mathematics. No formulas, no algorithms, no code in this book. Instead, you will learn about origami and the platonic solids and the teapotahedrom, how to organize the LCD segments of a digital display, the phenomenon of moiré patterns, designing tiles that are aperiodic (I didn’t know it was possible) or even how to layout box designs in a single piece of cardboard. After reading this chapter, the next time you unpack a box from Amazon you will pay attention to those little details that usually pass unnoticed.

Apart from the old revised chapters you can find columns that were never published too. Disparate topics, but all of them related to graphics and 3D in some sense. The visual quality of the book is excellent with all the pages in full color and the style of the author is even better. Andrew Glassner is among the best writers in the Computer Graphics field.

I give my full recommendation to this book. Andrew Glassner’s Notebook will appeal to both novice readers and experienced mathematicians.

Rating: 8 / 10

Since the first day I saw content from Planet51 I knew it was going to rock. I am emotionally attached to this movie because I worked in the Videogame for a few months and because I have worked in the past with several member of the technical team that is behind the movie. I know first hand they are very talented people.

And finally, the trailer is now live: Planet51 trailer!

Congratulations to all the team. All the best for them.

If you can do without that information the following code will help you to save a few bytes, even halving the size of the byte-code in the best cases.

Although not documented in the DirectX SDK, this CodeGem is not an undocumented hack. The Direct3D shader code format is documented in the MSDN, so it probaly won’t change in future revision of DirectX v9.0 (if there is going to be any more…)

D3DPtr<ID3DXBuffer> StripComments(const D3DPtr<ID3DXBuffer>& code)
{
    // Calculates the new size (without comments)
    int* codeData = static_cast<int*>(code->GetBufferPointer());
    unsigned int sizeInWords = code->GetBufferSize() / 4;
    unsigned int strippedSizeInWords = sizeInWords;
 
    for (unsigned int i = 0; i < sizeInWords; i++)
    {
        if ((codeData[i] & 0xffff) == D3DSIO_COMMENT)
        {
            int commentSize = codeData[i] >> 16;
            strippedSizeInWords -= 1 + commentSize;
            i += commentSize;
        }
    }
 
    // Creates a new buffer with the original code but omitting the comments
    D3DPtr<ID3DXBuffer> strippedCode;
    V(D3DXCreateBuffer(strippedSizeInWords * 4, strippedCode.GetPtrForInit()));
 
    int* strippedCodeData = static_cast<int*>(strippedCode->GetBufferPointer());
    size_t offset = 0;
 
    for (unsigned int i = 0; i < sizeInWords; i++)
    {
        if ((codeData[i] & 0xffff) == D3DSIO_COMMENT)
        {
            int commentSize = codeData[i] >> 16;
            i += commentSize;
        }
        else
        {
            strippedCodeData[offset++] = codeData[i];
        }
    }
 
    return strippedCode;
}

• Launchy. Launchy is a keystroke launcher that clones the behaviour of Quicksilver in Mac OS. With this tool you will say goodbye to your start menu and desktop icons. Everything is now accessible from a few keystrokes: folders, applications and even websites, all with a simple alt + space. The perfect complement for Launchy is StartKiller, a tool for removing the Start button from the taskbar. To me, Launchy is as revolutionary as 4DOS was back in MS-DOS days. How much time did you save? (bonus: and now that you can have a 100% clean desktop it is time to use a decent wallpaper…).
• AutoHotkey. Whatever can not be done with a few launchy keystrokes most likely can be programmed with an AutoHotkey macro. AutoHotkey incorporate a powerful script language that will allow you to automate almost anything: instant access to disk folders, internet tabs, activate tray programs, change visual studio layouts, send email, check calendar, etc.
• xplorer². xplorer² is a file manager with enough features to say good bye to Windows Explorer (Microsoft, admit it, it is not designed for advanced file manipulation). Although there is a professional version, the free lite version is enough to me, especially the Tabbed dual-pane interface feature. With AutoHotkey you can easily redirect Win + E to xplorer².

And that closes out my small contribution to reduce energy wastage in the world . I am sure you can share more gems like these. One more time, thanks for reading.