Skip to main content

Posts

Showing posts from October, 2012

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 decompre

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 e

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

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}) &

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

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 Zahlenh