2012-10-24

Interesting ideas in CACM (Vol.55, No.9)


I found two interesting ideas in CACM, Vol.55, No.9.

1. DieHard

Many C++ program's crash bugs are caused by small out of bound access. So, if a memory allocator gives a slightly large memory chunk,  also  randomize the heap allocation. Then many bugs become non-deterministic, Heisenberg bug.

This is a nightmare for developers who should fix this kind of bugs. Because, it is hard to catch the bug.

However, for some users, this might be better. If one just restarts the program, the crash may be gone if they are lucky.

You can find this idea entitled DieHard from Microsoft research. Although, I don't think randomly hiding bugs are analogy of Seat belts or Airbags. I found this idea interesting, but I prefer deterministic bugs as a developer. Also I prefer to fix the bugs rather than hiding them.

http://queue.acm.org/detail.cfm?id=2333133

2. CriptDB

I heard some methods that you can search encrypted data without decrypt it or search a compressed data without decompress it. I don't understand the details, but the basic idea is having a kind of data onto map function. For example, I have a database which contains English text. I encrypt this database by translating German. So if anyone who don't know German can not read the database. If I want to search a word ``mountain'', then ``mountain'' is encrypted as ``Berg'', the I search the word ``Berg''. The story is also not so simple, however, the basic idea seems like this.

http://dl.acm.org/citation.cfm?doid=2330667.2330691

2012-10-23

Graph theory for railfans: A side story of Authors in a Markov matrix


This is a side story of ``Authors in a Markov matrix: Which author inspires the people most?'' What relationship do railfans and Graph theory have? is the theme of this story. (Japanese version)

My colleague Dietger asked me, ``Do you know how to traverse the all the edges in a graph?'' I asked back, ``Isn't it a Hamiltonian path problem?''

He answered, ``No. Hamiltonian path is the problem to traverse all the nodes only once. Instead of the nodes, I want to know how to visiting all the edges once.'' I intuitively answered, ``Can we solve it on the dual graph?'' But this was wrong. Figures 1, 2, 3 show the what is the face-vertex dual graph, and Figure 3 shows there is no edge dual graph.  For instance, in a triangle mesh, vertices are connected via edges, faces are also connected via edges. Therefore, vertex (node) and face can be (so called) dual. Then, what is the connection between edges? There is no connection between edges, or edges themselves are connection. This is  the difference between face/vertex and edge.
Figure 1: Duality of face and vertex: faces to a dual graph.
Figure 2: Duality of face and vertex: a dual graph to faces.
Figure 3: Edge's duality?
``What kind of application do you think of, if any?'', I asked him. He explained me that this is his friend's problem. His friend is working for a railway company. He needs to check all the railway track in his country regularly with a special train. How efficient he can check the railway is an important problem. This is called a Chinese postman problem in graph theory. Mei Ko Kuan, a Chinese mathematician, is one of the early researcher of this problem, so the name of the problem comes from that. This is related with the Euler path problem (one-stroke problem). Now you see the connection between graph theory and railway.

I recall a similar problem that was presented at PTT (Programming tools and techniques) long time ago. PTT is a kind of club that the people are interested in computer programming. In some reason, there are many railfans also. Kasai presented ``Longest One-way-ticket Problem'' at PTT.  ``Longest Oneway-ticket Problem'' is a problem to find the longest one way ticket you can buy. He thought about the JR (Japan Railway) ticket. http://www.swa.gr.jp/lop/index.html

Kasai tried two different methods: linear programming and brute-force method. The both solution are the same. But, he needed some techniques to simplify the problem for the brute-forth method, e.g., graph simplification and graph subdivision. The result is shown here. http://www.swa.gr.jp/lop/lop_res.html
referred from http://www.swa.gr.jp/lop/lop_res.html
Kasai also explained the algorithm in details (in Japanese). He used a commercial linear programming solver, that was quite expensive in 2000. However, five years later, he revised the method and show how to solve the problem on a personal computer with a free liner programming solver, GLPK (GNU Linear Programming Kit).

I am also surprised that a person compute this longest one way ticket by hand, he started this hobby around 1960s. His hand computed result is quite similar with Kasai's result. Is this person a genius, or human brain has such a incredible ability? I am impressed.

By the way, I believe railfans are all over the world. There is a special TV channel for railfans in Germany. I wonder that the German channel tried such kind of experience. Kasai used Japanese geographic constraint to simplify the graph. He divided whole Japan graph to sub-graphs since Japan is consists of islands. The connection between islands are very limited. Has anyone computed the German longest one way ticket? Or European longest one way ticket? If you know such page, please write me a comment.

2012-10-10

Authors in a Markov matrix: Which author do people find most inspiring? (6)


In mathematics, we usually only think about these node numbers.  The numbers are only used to distinguish the nodes. When we apply the idea of a graph to a concrete problem, these numbers corresponds to different kinds of objects. Let me show two examples to give you some idea.

Example 1: Nodes represent authors

Assume we are describing the following authors:
  • William Shakespeare
  • Lewis Carroll
  • Raymond Smullyan
  • Martin Gardner
There could be many different opinions about what kinds of relationships these authors have. Here I assume Shakespeare inspires Carroll, and Carroll inspires Smullyan and Gardner. Such graph can be shown in Figure 6.
Figure 5. Graph example 1. Each node is an English author.

Example 2: Nodes represent train stations

Assume each node represents a train station. The followings are stations in Berlin, Germany.
  • Weinmeisterstr
  • Alexanderplatz
  • Hackescher Markt
  • Jannowitzbruecke
When two stations are next to each other (the next station), we connect them with an edge that represents a ``neighbor'' relation. The graph is shown in Figure 7. By the way, the S-Bahn (city train) in Berlin is frequently under construction and some intervals may sometimes have no train service, or may only have service in one direction. (The other direction usually has a bus connection.)  When the train only goes in one direction, the graph should use directed edges.
Figure 7. Graph example 2. Each node is a train station.
There is one important thing to note here. Whatever a node represents, the shape of these graphs of Figure 4, 5, 6, 7 (Figure 4, 5 are found the former blog entry) are the same shape. The structure of the graphs are identical. When the structure of the graphs is the same, we consider they are the same graph in mathematics. Despite the meaning of the nodes, graph theory only considers the structure of the graph.

You may think it is odd that I said the relation of English authors and the relation of train station are the same in the sense of a graph.  I am often surprised that there are so many similar patterns in this world. There are problems that look totally unrelated, but sometimes the same pattern is hidden deep within them. If you can find a pattern in your problem, and if you can connect it to a known pattern, you might be able to solve your problem. Even your problem is very new and nobody has solved it yet, you then have a chance to find a solution. Mathematics is a powerful tool for finding common patterns in this sense. Of course, you might not be able to find a similar pattern, or may find a pattern that you think is similar, but turns out to be a completely different problem.

The most fundamental pattern in mathematics involves something you can count. People, dogs, cities, stars, musical notes, churches... these objects have one common property: you can count them. For mathematics, they are all the same in this sense of being countable. Therefore, when you have learned how to add numbers once, you have no problem adding any number of people, or number of dogs, or number of stars, and so on. Of course, stars and dogs do not have much common in a sense, but mathematics picks one property and focuses on that.  In that sense, they are the same. A graph is a mathematical object that only cares about the relationship between nodes. If you only see the nodes and edges, they look dull and dry.  At this point you need your imagination. These nodes can be: web pages, friends, cities, phones, oil bases, and so forth. They have the common property of individual objects that have relationships between them.

How can we write down the relationships between nodes? Being able to writing this down is important. If we have a method to represent a graph by writing it down, then we can store them.  Especially if we have a unique representation (a notation) of a graph, we can ``compare'' two graphs. It is a difficult problem to compare arbitrary graphs. To make this problem simpler, the order of node should be unique. For instance, if each node has a unique name or number then we can sort the nodes of a graph. If the relationship is the same between two graphs, these graphs have the exactly the same notation. The next section describes how we could write down a description of a graph to be able to compare them.

So, the next blog, I will show you how to write down a graph.

How to get the camera parameters from OpenGLperspective/modelview matrix? (2)


Get camera parameters from the OpenGL modelview matrix

OpenGL modelview matrix includes model related operations, therefore, the scene was scaled, translated, or rotated, these effects are also in there. There is no way to separate these operation from the pure camera parameters from the matrix only. Here we assume the model operation is identity. If your renderer separated the model operations and camera parameters, you need to undo the model operation with your implementation dependent way. Our renderer has separation of them, so we needed to undo the effect.

The elements of OpenGL modelview matrix is the following. If you want to know the details of the each element, please refer my other blog (http://shitohichiumaya.blogspot.de/2011/01/what-matrix-glulookat-generates-1.html)
\begin{eqnarray*}
 \left[
  \begin{array}{cccc}
   x_x & y_x & z_x & 0 \\
   x_y & y_y & z_y & 0 \\
   x_z & y_z & z_z & 0 \\
   -(\vec{x} \cdot \vec{e}) &
    -(\vec{y} \cdot \vec{e}) &
    -(\vec{z} \cdot \vec{e}) & 1 \\
  \end{array}
 \right]
\end{eqnarray*}
Let rewrite this matrix with replacing the 4th row with \(a,b,c\).
\begin{eqnarray*}
 \left[
  \begin{array}{cccc}
   x_x & y_x & z_x & 0 \\
   x_y & y_y & z_y & 0 \\
   x_z & y_z & z_z & 0 \\
   a   & b   & c   & 1 \\
  \end{array}
 \right]
\end{eqnarray*}
This matrix has camera basis, the only problem is the eye position. This is in the 4th row, 1-3 columns as shown in the following. (Here, the matrix and vector are written in the column vectors \(\vec{x}, \vec{y}, \vec{z}, \vec{e}\))
\begin{eqnarray*}
 \left[
  \begin{array}{ccc}
   & & \\
   \vec{x} & \vec{y} & \vec{z}\\
   & & \\
  \end{array}
 \right]
 \left[
  \begin{array}{c}
   \\
   \vec{e} \\
   \\
  \end{array}
 \right]
 & = &
 \left[
  \begin{array}{c}
   a \\
   b \\
   c \\
  \end{array}
 \right]
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
 \left[
  \begin{array}{c}
   \\
   \vec{e} \\
   \\
  \end{array}
 \right]
 & = &
 \left[
  \begin{array}{ccc}
   & & \\
   \vec{x} & \vec{y} & \vec{z}\\
   & & \\
  \end{array}
 \right]^{-1}
 \left[
  \begin{array}{c}
   a \\
   b \\
   c \\
  \end{array}
 \right]
\end{eqnarray*}
is the eye position. The implementation example in C++ of those is the
following.

/// get camera parameters from
/// the OpenGL modelview matrix
///
/// \param[out] eyepos  eye position
/// \param[out] viewdir viewing direction
/// \param[out] updir   up direction vector
void gl_get_camera_parameters_from_modelview_matrix(
    Vector3d & eyepos,
    Vector3d & viewdir,
    Vector3d & updir)
{
    GLdouble mat[16];
    glGetDoublev(GL_MODELVIEW_MATRIX, mat);

    Vector3d xdir(0.0, 0.0, 0.0);
    Vector3d ydir(0.0, 0.0, 0.0);
    Vector3d zdir(0.0, 0.0, 0.0);

    xdir[0] = mat[0];  ydir[0] = mat[1];  zdir[0] = mat[2];
    xdir[1] = mat[4];  ydir[1] = mat[5];  zdir[1] = mat[6];
    xdir[2] = mat[8];  ydir[2] = mat[9];  zdir[2] = mat[10];

    // This is a, b, c components.
    Vector3d bvec(-mat[12], -mat[13], -mat[14]);

    Matrix33d basis_mat(xdir[0], xdir[1], xdir[2],
                        ydir[0], ydir[1], ydir[2],
                        zdir[0], zdir[1], zdir[2]);
    // This matrix should not be singular.
    // invert() gives matrix inverse.
    bool const is_inv = basis_mat.invert();
    assert(is_inv);

    eyepos  = basis_mat * bvec;
    viewdir = -zdir;
    updir   =  ydir;
}


For simplicity again, I omitted the error checks.

Conclusion

In this blog, I showed
  • How to get perspective camera parameters from the OpenGL perspective matrix.
  • How to get other camera parameters (i.e., camera position, view direction, and eye position) from the OpenGL modelview matrix.
There is not so much case that this is needed, but I think some people may find this is interesting.

How to get the camera parameters from OpenGLperspective/modelview matrix? (1)

Abstract

This is a computer graphics and programming story. While ago, I wrote about a matrix that is generated by a OpenGL function, gluLookat. (http://shitohichiumaya.blogspot.de/2011/01/what-matrix-glulookat-generates-1.html) Why did I write that story? Because I was developing a renderer that is independent from the OpenGL, but some point, I need to overlay OpenGL generated image and our renderer's image. I think not a lot of people need to write a own renderer, therefore, this blog entry maybe not so much refereed. However, there are quite a lot of people visited this page. I don't know what kind of people visiting this pages, I am a bit surprised. This time, our customer has a special system and they need to compute the inverse of the OpenGL functions. Their input is OpenGL's Projection/Modelview matrix and the output is camera parameters. This is more special cases, but, the problem itself may be interested in.

Introduction

There are interesting visualization system in this world. This time, my customer told us, ``We don't know where our camera is, but we know the matrices. Could you compute your rendering system's camera parameter out of them?'' I was a bit surprised this story, how a system which can manipulate camera doesn't know the camera position? But the story is not so simple. This software is a commercial huge system. One of the software layer can not see the camera parameter because it is simply the system is complex. But they use OpenGL and it is possible to access the perspective/modelview matrices at their software layer. Therefore, they just asked us to extract the camera parameters from these matrices.

This is quite a rare case, though, it is also an interesting puzzle: given OpenGL projection/modelview matrices, how to get the camera parameters? Maybe there are a few people who find this interesting.

Get camera parameter from the OpenGL perspective matrix.

This section, we talk about how to get perspective camera parameters from the OpenGL perspective matrix.

In OpenGL, gluPerspective generates the perspective matrix. (Please refer the OpenGL manual in details.)

void gluPerspective(GLdouble fovyd,  GLdouble aspect,
                    GLdouble zNear, GLdouble zFar);
  • fovyd: Specifies the field of view angle, in degrees, in the y direction. Note: this is degrees, not radian.
  • aspect: Specifies the aspect ratio that determines the field of view in the x direction. The aspect ratio is the ratio of x (width) to y (height).
  • zNear: Specifies the distance from the viewer to the near clipping plane (always positive).
  • zFar: Specifies the distance from the viewer to the far clipping plane (always positive).
According to the OpenGL manual, the generated perspective matrix is the following.

\begin{eqnarray*}
 \left[
  \begin{array}{cccc}
   \frac{fr}{asp}  & 0  & 0 & 0  \\
   0               & fr & 0 & 0  \\
   0               & 0  & \frac{z_f + z_n}{z_n - z_f} & -1 \\
   0               & 0  & \frac{2 z_f z_n}{z_n - z_f} & 0  \\
  \end{array}
  \right]
\end{eqnarray*}
where \(fr = \frac{1}{\tan(\frac{fovy}{2})}\), \(fovy\) is in radian of  \(fovyd\), \(asp\) is aspect ratio, \(z_n\) is the near clipping plane distance, \(z_f\) is the far clipping plane distance. For simplicity, we rewrite the perspective matrix as the following.
\begin{eqnarray*}
 \left[
  \begin{array}{cccc}
   aa & 0  & 0  & 0  \\
   0  & bb & 0  & 0  \\
   0  & 0  & cc & -1 \\
   0  & 0  & dd & 0  \\
  \end{array}
  \right]
\end{eqnarray*}
\begin{eqnarray*}
 asp  &=& \frac{bb}{aa}\\
 fovy &=& 2 \arctan(\frac{1}{bb})\\
 z_f  &=&\frac{c-1}{c+1} z_n
\end{eqnarray*}
Here, let \(kk = \frac{c-1}{c+1}\), we get
\begin{eqnarray*}
 z_n &=& \frac{dd(1-kk)}{2k}\\
 z_f &=& \frac{dd(1-kk)}{2}.
\end{eqnarray*}
Note \(z_n \neq 0\).



My implementation example of those in C++ is the following.


/// get perspective camera parameters
/// from the OpenGL projection matrix
///
/// \param[out] fovy_rad     field of view in radian
/// \param[out] aspect_ratio aspect ratio
/// \param[out] clip_min     clipping min distance
/// \param[out] clip_max     clipping max distance
void gl_get_camera_parameter_from_perspective_matrix(
    double & fovy_rad,
    double & aspect_ratio,
    double & clip_min,
    double & clip_max)
{
    GLdouble mat[16];
    glGetDoublev(GL_PROJECTION_MATRIX, mat);

    GLdouble const aa = mat[0];
    GLdouble const bb = mat[5];
    GLdouble const cc = mat[10];
    GLdouble const dd = mat[14];

    aspect_ratio = bb / aa;
    fovy_rad     = 2.0f * atan(1.0f / bb);

    GLdouble const kk = (cc - 1.0f) / (cc + 1.0f);
    clip_min = (dd * (1.0f - kk)) / (2.0f * kk);
    clip_max = kk * clip_min;
}

For simplicity, I omitted the division by zero check. Of course when OpenGL has been correctly set up, then this should be OK. Though, personally I would put some assertions.

2012-10-06

The connection 0 and other


A boy (T.) is working on 7. The question is what two numbers make 7. The material using here is shown in Figure 1. This is called ``Zahlenhaus''. One house has two rooms and each room has some people. How many people are in the house? is the question and the students think about addition.
Figure 1. Zahlenhaus: 7 = 4 + 3
Figure 2. Zahlenhaus: Questions
Beside the house figure, there is a equation (Figure 2), usually missing one part. For example,

  • 7 = 3 + ?
  • 7 = 4 + ?.

The leaner fills in ?. T. has no problem to fill in those questions.

However, he doesn't understand the following.

  • 7 = 0 + ?

By the way, this is a easy case. Since he understands what he doesn't understand. I, myself, have a problem to find when I lost in a mathematics book. If I know where I lost, it is rather easy to return to the track. But, in many cases, I didn't know where I lost. Then I first need to find out where to return in the book.

OK, let's back to the Zahlenhaus. In this case, there is no one in the left room. I asked him, ``How many people in the right room?'' He did not answer a while, then, said, ``2 + 5'', then, ``3 + 4''. I have a problem. T. answered,

  • 7 = 0 + 2 + 5.

This is mathematically correct. I didn't said we can only use one number for one room since one house can be represented two numbers, why one room should be only one number assigned? At the first place, I asked seven is what and what? This is a practice. You can answer seven is seven. It is not a math, this is rather a game.

Because of this implicit rule, which is one room only has one number, 7 = 0 + 2 + 5 is not correct. Zahlenhaus has no three rooms. If this Zahlenhaus has three rooms, this is correct. But, isn't it more confusing that the calculation depends on the number of the room?

I recall about a book by Charles Dodgson (Lewis Carroll), the title is ``Through the Looking-Glass, and What Alice Found There.'' The following is a conversation when Alice met the King.
``... Just look along the road, and tell me if you can see either of  them.''
``I see nobody on the road,'' said Alice.
``I only wish I had such eyes,'' the king remarked in a fretful tone. ``To be able to see Nobody!'' [Quote 1]
There is nobody in one of the rooms in the Zaehlenhause. How do you show nobody is there. This is not a simple concept, human being took a lot of time to find zero. ``There is nobody'' means ``There are zero people.'' It is not ``There aren't zero people.'' If ``There aren't zero people,'' there should be somebody since it is negation of zero people's existence. We are talking about zero people exist. If this was his problem, it would be a tough problem for me. But, I found it is OK for him that if zero people exist in the room, he can write 0. I am not sure he thinks zero people's existence means 0 or he thinks 0 is another name of ``nobody''.

Then, is the problem that one room can be represented by one number? ``Normally'' we use as less number as possible since this makes easier to compare the results. It is more difficult to compare 1 + 1 + 1 + 1 + 1 + 1 + 1 with 1 + 1 + 1 + 1 + 1 + 1 than to compare 7 and 6. Therefore, lazy mathematician ``normally'' writes 0 + 7 as 7. ``Normally'' style is chosen since it is shorter or simpler. But ``normality'' and ``correctness'' are sometimes not the same, and ``correctness'' is more important in mathematics.

I thought, ``Alice again.'' I tried to tell my friends that how mathematical the Alice books are.
``Can you do Addition?'' the White Queen asked. ``What's the one and one and one and one and one and one and one and one and one and one?''
``I don't know,'' said Alice. ``I lost count.''
``She ca'n't do Addition,'' the Red Queen interrupted. ``Can you do Subtraction?' Take nine from eight.'
``Nine from eight I ca'n't, you know.'' Alice replied very rapidly: ``but ---''
``She ca'n't do Subtraction,'' said the White Queen. ``Can you do Division? Divide a loaf by a knife -- what's the answer to that?'' [Quote 2]
If a room of Zahlenhaus has more numbers, it becomes the White Queen's question. Still the White Queen is correct. Any natural numbers are sum of ones. How can I explain this to him?

I asked T., if you want to buy an ice cream that costs two Euro. You have one Euro, how much do you ask to your mother? ``One Euro'', he answered. Then, if you don't have any, zero Euro you have? ``Two Euro'', he answered. If you need 7 Euro, but, you have zero Euro, how much do you ask?  He thought a while and answered, ``I don't know''. You don't know? ``One plus six?'', he answered. His answers are following,
  • 2 = 1 + 1
  • 2 = 0 + 2
  • 7 = 1 + 6
  • 7 = 0 + ? I don't know.
I don't know that what kind of model he has in his brain. Why does he think he doesn't know at the last case?

To make sure, I repeat this.
  • You want one Euro. You have zero. You want? ``one'', OK.
  • You want two Euro. You have zero. You want? ``two'', OK.
  • You want three Euro. You have zero. You want? ``three'', OK.
  • You want seven Euro. You have zero. You want? ``seven?'' Yes.
After this, T. answered the questions of 0 + x correctly. But I didn't understand what was his problem. I still wonder, he really understood this. Maybe it is difficult that the numbers are all the same as numbers. It is a level of abstraction. one and two are surely different, but, as a number, for example, made by ones, you can add them... all numbers shears these properties. By the way, If you work on mathematics, you will forget the numbers. Nowadays, numbers are for computers.

Quote 1

This quote is in Chapter 7, The Lion and the Unicorn, Through the Looking Glass and What Alice Found There. by Lewis Carroll.

The text is taken from ``The Annotated Alice, the definitive edition,'' edited by Martin Gardner, Penguin books, page 234, ISBN-13: 978-0140289299.

Quote 2

This quote is in Chapter 9, Queen Alice, Through the Looking Glass and What Alice Found There. by Lewis Carroll.

The text is taken from ``The Annotated Alice the definitive edition,'' pp. 265-266, Penguin books, ISBN-13: 978-0140289299.