Y-101

This is the result of one of my last student projects, i.e., coming up with a concept of an innovative hockey stick. Of course, my part was the product visualization.

Darc Library

The Darc Library is a slightly modified wrapper of the former Protox project. It now contains Protox as well as a bunch of other modules filled with more or less useful stuff that has accumulated over the years. It currently consists of the following modules.

▶Darc Global definitions, typedefs, enumerations and helper functions.

▶Geometry Basic geometry types like vectors, matrices, triangles, segments, planes etc.

▶Math Strictly mathematical stuff, usually generalized classes for the Geometry module.

▶Protox Windows and DirectX stuff.

The whole thing can be explored ▷here, nicely formatted with doxygen.

Prime Factorization

This script uses a brute force approach.

Number	Primes

Matrix to Euler Angles

Every orientation in 3D space can be described using the product \(T\) of three rotation matrices, usually around the main axes \(R_X\), \(R_Y\) and \(R_Z\). Given such a matrix \(T\), it is often necessary to decompose it into three seperate angles - the Euler Angles. These can be used as input arguments for a sequence of basic rotation operations, so that the following equation holds:

\begin{align} T = R_i(\alpha_0) R_j(\alpha_1) R_k(\alpha_2) \end{align}

The choice of \(i, j, k\) determines the rotation convention. One common possibility would be Yaw-Pitch-Roll (XYZ, depending on the local coordinate system) but the following implementation works for arbitrary conventions.

Mathematics

The decomposition of \(T\) depends highly on the definition (internal implementation) of \(R_i\) so make sure you know what your matrix class is doing. The standard definition of rotation matrices around X, Y and Z looks like this:

\begin{align} R_X=\begin{pmatrix} 1 & 0 & 0 \\ 0 & A & -B \\ 0 & B & A \end{pmatrix} \end{align}

\begin{align} R_Y=\begin{pmatrix} C & 0 & D \\ 0 & 1 & 0 \\ -D & 0 & C \end{pmatrix} \end{align}

\begin{align} R_Z=\begin{pmatrix} E & -F & 0 \\ F & E & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align}

Here \(A, C, E\) denote the cosine and \(B, D, F\) the sine of the unknown Euler Angles. Let's take a look at \(T\) for the convention YXY.

\begin{align} T=R_{YXY}= \begin{pmatrix} CC-DDA & DB & CD+DAC \\ DB & A & -CB \\ -CD-DAC & CB & -DD+CCA \end{pmatrix} \end{align}

Apparently the element (indexing starting with 0) at \(T(1,1)\) is the cosine of the Euler Angle \(\alpha_1\) for the middle rotation matrix \(R_X\). This is true for all of the 12 possible conventions. However the location of this pivot element is not always the same. The coordinates are determined by the first and third rotation component by using the simple conversion \(X \rightarrow 0\), \(Y \rightarrow 1\) and \(Z \rightarrow 2\). The next step is to compute \(\alpha_0\) and \(\alpha_2\) using the elements horizontal and vertical of the pivot. Knowing \(A\) one can easily compute \(\alpha_1\) and therefore \(B\). You can now use the horizontal neighbors of the pivot element to get \(\alpha_2\) and the vertical neighbors to get \(\alpha_0\). Since the applied convention uses the same axis for the first and third rotation there are no \(E, F\) components in this matrix.

Gimbal Lock

Now what happens if \(B\) is close to zero in the above case? This means a so called Gimbal Lock has occured because the divisions in the row and column of the pivot element are undefined. This can happen if the orientation of \(T\) is so that one angle becomes ambiguous which means it can be set to any value, e.g., \(\alpha_0 = 0\). Since one Euler Angle is now zero the corresponding rotation matrix yields \(R_i=I\) and the new reduced transformation matrix looks like this:

\begin{align} T=R_{XY}= \begin{pmatrix} C & 0 & D \\ DB & A & -CB \\ -DA & B & CA \end{pmatrix} \end{align}

Interpreting the axes as coordinates again a new pivot element is found at \(T(0,1)\), which is always zero. Once again it's horizontal neighbors can be used to determine the remaining Euler Angle \(\alpha_2\). Keep in mind that the order of cosine and sine elements may vary depending on the convention applied. As previously mentioned there are 12 possibilities.

:: CODE BLOCK ::

\(R_X\) - pivot	\(R_Y\) pivot	\(R_Z\) pivot
Y-X-Y	X-Y-X	X-Z-X
Y-X-Z	X-Y-Z	X-Z-Y
Z-X-Y	Z-Y-X	Y-Z-X
Z-X-Z	Z-Y-Z	Y-Z-Y

Listing: A - "Conventions"

If you want to construct an Euler Angle decomposition for a special convention just follow these instructions to extract the necessary equations. I recommend a symbolic calculation, e.g., in MatLab to make this task easier.

City Gen

City Gen was a group project of 2008 based on OpenGL using advanced techniques, mainly Shader (implemented Phong shading) and L-Systems. It demonstrates the procedural generation of a virtual city with regard to several environmental parameters.

The scene consists of an initially planar mesh which can be modeled using the elevation tool by simply brushing over the target area. Brush diameter and pressure can be adapted. Figure A shows the subsequent steps in particular the application of the population map, the automatic generation of streets and finally the extraction of the blue blocks representing buildings and other structures.

Examples 1 to 3 show possible output after the street generation. The street generator uses a two phase L-System. In a preprocessing step up to 3 population centers are calculated. These centers are then connected using a "highway"-style L-System. Finally each street node spawns new street segments based on the population density, terrtain height and conflicting street segments. New street segments vary in length and angle and are placed so that they fit best into the existing street network for example by avoiding dead ends.

A more detailed description may follow in the future. For now, take a look at the source which will be made accessible if requested.

Binary Filter

Have you ever wondered how the sequence of natural numbers looks like if you filter out all the numbers that don't match a given number of ones or zeros in its binary representation? Well, i did, a while ago and that's why i came up with this little piece of code, the Binary Filter. Although it may not seem like it, the solution for this particular problem was somewhat tricky to obtain, hence i decided to share it with the world.

The key idea to my solution is the observation that the problem "Give me all numbers with \(k\) ones in its binary representation" is very similar to calculating the binomial coefficient. Consider the following table containing all 5 digit numbers with 3 ones.

:: TABLE BLOCK ::

\(i\)	\(N_{10}\)	\(N_2\)
0	28	11100
1	26	11010
2	25	11001
3	22	10110
4	21	10101
5	19	10011
6	14	01110
7	13	01101
8	11	01011
9	7	00111

Listing: A - "Binary Filter in action"

Naturally, the number of items equals the binomial coefficient 5 over 3.
In order to calculate the correct number at an index \(i \in [0,9]\), we need to know how many ones are at the top and how many zeros are at the bottom for the first column. This happens to be the quotient of \(3 \over 5\) times the binomial coefficient 5 over 3. This is true for any combination of \(n\) and \(k\). Finally, after knowing whether we're in the upper or lower half of the table, we can dismiss the first column and analyze the remaining \(n-1\) columns.

The Code

As usual, here the necessary code snippets for your own project. You're going to need an implementation of the binomial coefficient. Instead of using the standard version, you might want to use this optimized version without explicitly calling the factorial function.

:: CODE BLOCK ::

int binomial(int _n, int _k)
{
    if(_k < _n-_k) _k = _n-_k;
    int c = 1;

    for(int i=0; i<_k; ++i){
        c = c*(_n-i);
        c = c/(i+1);
    }

    return c;
}

Listing: B - "Binomial Coefficient"

And finally the actual binary filter function in a recursive implementation. The function will return the \(i\)-th, \(n\) digit number with \(k\) ones in its binary representation. The order of values is descending.

:: CODE BLOCK ::

int bfilter(int _n, int _k, int _i)
{
    if(_n < =0) return 0;

    //Number of "1"s
    int n_x = (_k*binomial(_n, _k))/_n;

    //_i is in "1" block
    if(_i < n_x){
        return pow(2, (_n-1)) + bfilter(_n-1, _k-1, _i);
    }
    //_i is in "0" block
    else{
        return bfilter(_n-1, _k, _i-n_x);
    }
}

Listing: C - "Binary Filter"

Check out the ▷docs for further information.

ParaView Plugins

Today, I'm going to show you how to compile your own plugins for ParaView 3.8.0 on Windows using CMake 2.8.4, QT 4.6.3 and Visual Studio 2008. Other combinations may work as well but I cannot guarantee that, therefore I suggest you stick to the ones I used.

▶QT Installer Although this is not required for simple plugins I highly recommend you use QT because it is much easier to design an appealing user interface using the editor rather than scripting them drily using XML files. Go ▷here and download and install the qt-win-opensource-4.6.3-vs2008.exe file.

▶CMake You're going to need CMake in order to generate the VS project. I used Version 2.8.4 but anything later than that should be fine. Go ▷here and download the Win32 installer.

▶ParaView Of course you're going to need the actual software. I used Version 3.8.0 so either get that version to play safe or use a newer one. In either case make sure the versions of your ParaView installer and the Development installation match. Click ▷here to download ParaView.

▶ParaView Development In addition to ParaView you're going to need the ParaView ▷development binaries in order to compile your plugin. Remember this has to be the same version as your ParaView installation. Also your plugin will only work for this specific version of ParaView.

CMake

Before you can generate your Visual Studio project you will have to prepare a bunch of files in order to tell the plugin how it's supposed to interact with ParaView. Put the files in the same folder. The most important one is CMakeLists.txt which can look like this.

:: CMAKE BLOCK ::

cmake_minimum_required(VERSION 2.6)

PROJECT(MyTestFilter)

FIND_PACKAGE(ParaView REQUIRED)
INCLUDE(${PARAVIEW_USE_FILE})

ADD_PARAVIEW_PLUGIN(
    MyTestFilterSMPlugin
    "1.0"
    SERVER_MANAGER_XML MyTestFilter.xml
    SERVER_MANAGER_SOURCES vtkMyTestFilter.cxx
    GUI_RESOURCE_FILES MyTestFilterGUI.xml
)

CMakeLists.txt

This tells CMake that we're about to create a plugin with the name MyTestFilterSMPlugin, Version 1.0, and using the respective Server Manager (Configuration), source (VTK code) and GUI files. The filenames are case sensitive here. Now lets take a look at the other 3 files.

Server Manager Configuration

:: XML BLOCK ::

<ServerManagerConfiguration>
  
  <ProxyGroup name="filters">
    <SourceProxy name="MyTestFilter"
                    class="vtkMyTestFilter">

      <InputProperty
        name="Input"
        command="SetInputConnection">

        <ProxyGroupDomain name="groups">
          <Group name="sources"/>
          <Group name="filters"/>
        </ProxyGroupDomain>

        <DataTypeDomain name="input_type">
          <DataType value="vtkPolyData"/>
        </DataTypeDomain>
      </InputProperty>

    </SourceProxy>
  </ProxyGroup>
  
</ServerManagerConfiguration>

MyTestFilter.xml

This example shows the server manager configuration for a filter plugin, that takes ▷vtkPolyData as input. Depending on the implementation of your plugin these attributes can change. For example you can specify multiple outputs or different input types like String, Vector or ComboBox even without using QT.

GUI Resource File

Finally you need to tell the plugin where it's supposed to be located once loaded into ParaView. Using the resource file you can specify the name and the category of the plugin. The following example will put the filter in the Extensions group, however it will be grayed out unless you select a valid ▷vtkPolyData object as input.

:: XML BLOCK ::

<ParaViewFilters>
   <Category name="Extensions" menu_label="&Extensions">
      <Filter name="MyTestFilter" />
   </Category>
</ParaViewFilters>

MyTestFilerGUI.xml

So much for the setup files. Of course CMake is going to ask for a code file to generate the project from so let's take a quick look at that.

VTK Code

So this is where the real fun starts. Every ParaView plugin must be implemented as an extended ▷vtkAlgorithm since it must be usable within the VTK pipeline. The VTK class (and only this class!) should have the prefix vtk. I dont know whether this is mandatory but for some reason this convention avoids many nasty bugs.

This is the header file for a simple filter plugin that processes ▷vtkPolyData. Note that the input type must match the extended class. You might want to take a look at the VTK ▷documentation at this point.

:: XML BLOCK ::

#ifndef _vtkMyTestFilter_h
#define _vtkMyTestFilter_h

#include "vtkPolyDataAlgorithm.h"

class VTK_EXPORT vtkMyTestFilter :
          public vtkPolyDataAlgorithm
{
public:
  static vtkMyTestFilter *New();
  vtkTypeRevisionMacro(vtkMyTestFilter,vtkPolyDataAlgorithm);
  void PrintSelf(ostream& os, vtkIndent indent);

  int RequestInformation([...]);
  int RequestData([...]);
  int FillInputPortInformation([...]);
  int FillOutputPortInformation([...]);

protected:
  vtkMyTestFilter();
  ~vtkMyTestFilter();

private:
  vtkMyTestFilter(const vtkMyTestFilter&);
  void operator = (const vtkMyTestFilter&);
};

#endif

vtkMyTestFilter.h

Despite the confusing details the general setup is rather simple. The plugin sets the number of input and output ports and the respective data types. This is important because other plugins will only work (connect to the pipeline) if the data types match.

The next function is the core of the algorithm. This is where all the data processing is to be implemented. In case of our simple test plugin the most basic implementation would look something like this. The filter takes the input and passes it on to the output without doing anything.

:: CODE BLOCK ::

int vtkMyTestFilter::RequestData([...])
{
    vtkPolyData *input = vtkPolyData::GetData([...]);
    vtkPolyData *output = vtkPolyData::GetData([...]);

    output->CopyStructure(input);

    return 1;
}

int RequestData([...]);

That's it. Put all the files in the same folder, fire up CMake, select the Paraview Development directory and QT and you're done. When you start the Visual Studio project, set it to "Release" mode and compile the DLL. In case of linker errors check the settings for the correct library paths (especially QT) and remove the Python stuff. That did the trick in my case.