# February 2011

Warning! Some information on this page is older than 5 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

# Bit Tricks with Modulo

Sat
26
Feb 2011

I like to emphasize that programming is not so similar to maths as some people say. We are used to thinking about numbers in decimal numeral system and the operations that seem most natural for us are arithmetic computations like additions, multiplication and division. On the other hand, computer works with numbers stored in binary system and bitwise operations are most efficient and natural for it. Another difference is modulo operation (the remainder after division) - a function not so frequently used in math classes, but very important in programming. That's what I'd like to talk about here.

Modulo in C++ can be done using % operator, but just as division, it is quite slow. So when doing a common operation of cycling between subsequent numbers from a limited range:

`x2 = (x1 + 1) % n;`

few alternatives have been developed for some special cases, using bitwise operations.

First, when the divisor is a power of 2, we can use bitwise and (operator &) to mask only least significant bits of the addition result. But this optimization can be done automatically by the compiler (at least my Visual C++ 2010).

`// 7 = 0b111, so it masks 3 least significant bits.// Equal to (x1 + 1) % 8x2 = (x1 + 1) & 7;`

When we only cycle between two values - 0 and 1 - we can use XOR (operator ^):

`// Equal to (x1 + 1) % 2, for values 0, 1.x2 = x1 ^ 1;`

Finally, when we cycle between three values - 0, 1, 2 (like when indexing x, y, z components of a 3D vector), we can use the trick invented by Christer Ericson (at the end of the linked page). I came across it recently on Twitter and that's what inspired me to write this article.

`// Equal to (x1 + 1) % 3, for values 0, 1, 2.x2 = (1 << x1) & 3;`

# Automated Level Design Compo

Thu
24
Feb 2011

Last week an unusual competition took place on Warsztat, called Automated Level Design Compo (link to the forum thread, in Polish). Krzysiek K. coded a program that loads voxel maps in his text file format, renders them and allows to actually play such voxel games, including collision, physics and collecting some 3D models placed in the virtual world. Our task, as compo participants, was to code a small console program that takes random seed number and destination file name as its parameters and generates such voxel map. The theme for this edition was "flying islands". Here are some links related to this event:

I posted my entry and took 3rd place out of 5. Coding a voxel map generator was fun, because hacking with some math and being able to immediately see its visual results is one of the best things for someone fascinated in games and graphics programming, next to seeing your code running efficiently :) I took a screenshot from each compo entry. Mine is the 3rd one - the one with the forest (player's task on my map is to collect all mushrooms). Voxel technology is interesting. That's also why I play Minecraft a bit recently :)

Comments | #events #voxels #warsztat #competitions

# Naprawiacz nazw plików - My Little Tool

Fri
18
Feb 2011

Here I publish a small C# program that I developed for some specific needs of my father, but some of you may also find useful. It recursively searches selected directory for files and subdirectiores which names are too long or contain some non-ANSI characters, especially Russian cyryclic or Polish diacritic letters. It then presents the list and lets you manually rename or delete selected items, as well as automatically rename all selected items to convert these special letters to their English transcription.

This program can be useful if you collect some ebooks or other documents and need to store, pack or catalog these files in some way that doesn't like long names or nonstandard characters. The whole GUI is in Polish. The program requires .NET Framework 4. Source code in C# is attached. I think this code can be good entry point to write other similar programs that look for files and directories that meet some specific criteria.

Naprawiacz_nazw_plikow_bin.zip (EXE file)
Naprawiacz_nazw_plikow_src.zip (C# source code)

Now the Polish version:

Chciałbym opublikować mały program w C#, który napisałem dla specyficznych potrzeb mojego taty, ale może okazać się przydatny także innym. Program rekurencyjnie przeszukuje wskazany katalog w poszukiwaniu plików i podkatalogów, których nazwy są zbyt długie lub zawierają znaki spoza zakresu ANSI, szczególnie cyrylicę i polskie znaki diakrytyczne. Następnie prezentuje listę, na której można ręcznie zmieniać nazwy i usuwać wybrane elementy, a także automatycznie zmienić nazwy wszystkich zaznaczonych elementów konwertując te zestawy liter na ich transkrypcje po angielsku.

Ten program może się przydać, jeśli zbierasz ebooki czy inne dokumenty, a chcesz je zapisywać, pakować czy katalogować za pomocą takich programów, które nie radzą sobie ze zbyt długimi nazwami albo niestandardowymi znakami. Interfejs programu jest w języku polskim. Program wymaga zainstalowanego .NET Framework 4. Do archiwum dołączam kod źródłowy w C#. Myślę, że ten kod może być dobrym punktem wyjścia do pisania innych podobnych programów, które wyszukują pliki i katalogi spełniające podane kryteria.

# FX Batch Compiler 1.1

Thu
17
Feb 2011

4 years ago I've coded a program to visually support batch compilation of multiple HLSL shaders using the console fxc.exe compiler from DirectX SDK. I called it FX Batch Compiler and it's open source, under GNU GPL license, written in C#. Now I've updated it to new version 1.1. So if you use Direct3D, check it to see if it can be useful for you. I use it sometimes in my projects.

Features:

• Write compilation scripts in a simple language by specifying parameters for fxc.exe.
• Compile multiple shaders at time.
• Compile only shaders that need rebuild checked by file modification time.
• Review success or failure, warning and error count and compiler output for every task.
• Compile single HLSL source file with different parameters and preprocessor macros.

# XNA Math and Access Violation

Wed
16
Feb 2011

XNA Math is a great math library bundled with DirectX SDK. I've written about it here: Introduction to XNA Math, XNA Math Cheat Sheet. Recently I've started coding some small raytracer using this library (especially XMVECTOR type) and I came across an error:

Google didn't display many results when asked about this error in connection with "XNA Math" or "XMVECTOR", but I found a topic on our Polish gamdev forum: xnamath i dziwne crashe. Directed to other web places from there, I discovered that, just as I thought, this bug comes from misaligned address of the vector. XMVECTOR on PC is an alias for SSE __m128 type, which has to be always aligned to 16-byte boundary. Compiler seems to know about this alignment requirement and respects it whenever XMVECTOR is defined on the stack, passed as function parameter or returned from a function, but not when the vector is a member of some dynamically allocated class or struct. So this won't work:

`struct Scene {    XMVECTOR dir_to_light;};Scene *scene = new Scene();scene->dir_to_light = XMVector3Normalize(    XMVectorSet(1.5f, 1.f, -2.f, 0.f)); // Crash!`

Adding special alignment declaration supported by Visual C++ - __declspec(align(16)) - doesn't help. it looks like operator new always aligns allocated objects to 8 bytes and there is no way to change this behavior other than redefining it to use your own custom memory allocator.

So I suppose the most simple and convenient way to walk around this problem is to use more "casual" types for storing vectors - the ones that do not use SSE and do not require alignment, like XMFLAOT3 (which is just struct with float x, y, z). Anyway XMVECTOR is designed to optimize computations when compiler is able to place it in the CPU registers. So my solution looks like this:

`struct Scene {    XMFLOAT3 dir_to_light;};Scene *scene = new Scene();XMVECTOR dir_to_light = XMVector3Normalize(    XMVectorSet(1.5f, 1.f, -2.f, 0.f));XMStoreFloat3(&scene->dir_to_light, dir_to_light);...XMVECTOR dir_to_light = XMLoadFloat3(&scene->dir_to_light);XMVECTOR n_dot_l = XMVectorSaturate(XMVector3Dot(normal, dir_to_light));`

# Finding Polygon of Plane-AABB Intersection

Tue
15
Feb 2011

While doing volumetric rendering according to the article Volume Rendering Techniques (Milan Ikits, Joe Kniss, Aaron Lefohn, Charles Hansen, Chapter 39 of "GPU Gems" book), I came across a problem of calculating intersection between a plane and an AABB (axis-aligned bounding box), which forms a 3- to 6-vertex polygon. The solution is actually described in the article, but here I'd like to share my implementation (using D3DX).

The solution is based on finding points of intersection between the plane and every edge of the box. So we first need a ray-to-plane intersection code. My function for this is based on: Ray-Plane Intersection.

`// OutVD > 0 means ray is back-facing the plane// returns false if there is no intersection because ray is perpedicular to planebool ray_to_plane(const D3DXVECTOR3 &RayOrig, const D3DXVECTOR3 &RayDir, const D3DXPLANE &Plane, float *OutT, float *OutVD){    *OutVD = Plane.a * RayDir.x + Plane.b * RayDir.y + Plane.c * RayDir.z;    if (*OutVD == 0.0f)        return false;    *OutT = - (Plane.a * RayOrig.x + Plane.b * RayOrig.y + Plane.c * RayOrig.z + Plane.d) / *OutVD;    return true;}`

Now having a segment A-B between two points, we can calculate ray_to_plane intersection where RayOrig=A, RayDir=B-A and we get parameter T. The segment is a subset of the infinite ray. The intersection point lies on this segment when 0 <= T <= 1. The position of this point is A+T*B. Now it's time for plane-box intersection code:

`// Maximum out_point_count == 6, so out_points must point to 6-element array.// out_point_count == 0 mean no intersection.// out_points are not sorted.void calc_plane_aabb_intersection_points(const D3DXPLANE &plane,    const D3DXVECTOR3 &aabb_min, const D3DXVECTOR3 &aabb_max,    D3DXVECTOR3 *out_points, unsigned &out_point_count){    out_point_count = 0;    float vd, t;    // Test edges along X axis, pointing right.    D3DXVECTOR3 dir = D3DXVECTOR3(aabb_max.x - aabb_min.x, 0.f, 0.f);    D3DXVECTOR3 orig = aabb_min;    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_min.x, aabb_max.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_min.x, aabb_min.y, aabb_max.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_min.x, aabb_max.y, aabb_max.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    // Test edges along Y axis, pointing up.    dir = D3DXVECTOR3(0.f, aabb_max.y - aabb_min.y, 0.f);    orig = D3DXVECTOR3(aabb_min.x, aabb_min.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_max.x, aabb_min.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_min.x, aabb_min.y, aabb_max.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_max.x, aabb_min.y, aabb_max.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    // Test edges along Z axis, pointing forward.    dir = D3DXVECTOR3(0.f, 0.f, aabb_max.z - aabb_min.z);    orig = D3DXVECTOR3(aabb_min.x, aabb_min.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_max.x, aabb_min.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_min.x, aabb_max.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;    orig = D3DXVECTOR3(aabb_max.x, aabb_max.y, aabb_min.z);    if (ray_to_plane(orig, dir, plane, &t, &vd) && t >= 0.f && t <= 1.f)        out_points[out_point_count++] = orig + dir * t;}`

But that's not all. Returned points are not sorted! If we don't sort them, we may in some cases end up with a mess like this:

Here comes another clever algorithm - the one for sorting vertices (counter?)clockwise. I came up with it on my own and it's a bit similar to the algorithm for finding a convex hull. We are given a set of points that all lie in a single plane and already form a convex polygon. We want to sort them clockwise "around some center point". Beginner could probably think here about calculating such center point, then for each vertex calculating and comparing some angle using atan2, of course in degrees ;)

But that's not the solution. What we need here is a way to tell whether one vector is more "to the right" then the other, relative to some reference point. Whether one vector lies on the right-hand side of the other can be easily told in 2D using the sign of a scalar returned by 2D cross-product: a.x*b.y - b.x*a.y. In 3D it's not that easy. My idea is to use 3D cross-product. It returns 3D vector, but has similar property - it is anticommutative, which means: cross(a,b) == -cross(b,a). Now if only I could tell whether the direction of the resulting vector is "right" or "opposite"... That's what the sign of dot product means! I'm just going to use dot product between the cross product result and the normal vector of the plane. Eureka! Now I have all necessary parts. I choose first vertex as a reference. I also use lambda expression from C++0x (supported in Visual C++ 2010) to more conveniently pass custom comparator to std::sort STL algorithm (otherwise I would have to write a functor). Here is the final solution:

`#include <algorithm>void sort_points(D3DXVECTOR3 *points, unsigned point_count, const D3DXPLANE &plane){    if (point_count == 0) return;    const D3DXVECTOR3 plane_normal = D3DXVECTOR3(plane.a, plane.b, plane.c);    const D3DXVECTOR3 origin = points[0];    std::sort(points, points + point_count, [&](const D3DXVECTOR3 &lhs, const D3DXVECTOR3 &rhs) -> bool {        D3DXVECTOR3 v;        D3DXVec3Cross(&v, &(lhs - origin), &(rhs - origin));        return D3DXVec3Dot(&v, &plane_normal) < 0;    } );}`