No Such Blog or Diary

1024x1024 の画像回転プログラム SDL+OpenGL 版（もちろん回転は自前）．Java でアルゴリズムを確かめた後にノートＰＣ上でC++移植していたため 10fps しか出てなかった．しかし，メインマシンに移したら 40fps で動くではないか．ＯｐｅｎＧＬ速いなぁ，そしてノートはやっぱ遅いんだなぁ．さーて任意の画像を白黒で回転できるようにしよう．

どうせ画像を回転させるなら png でも読み込ませようと考えて， libpng を使ってみることに．面倒なのでフルカラー png のみをひとつの大きな位置次元配列に展開する関数を作った．

// full color PNG を一列のバッファにして返す
int readPNG(const char *fname, unsigned char**buf, int *iHeight, int *iWidth, bool *bAlpha, int *iRowbytes)
{
    const int number = 8;
    unsigned char header[number];
    FILE *fp = fopen(fname, "rb");
    if (!fp) return -1;
    fread(header, 1, number, fp);
    bool is_png = !png_sig_cmp(header, 0, number);   // Signature check
    if (!is_png) return -1;
    png_structp png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
    if (!png_ptr) return -1;
    png_infop info_ptr = png_create_info_struct(png_ptr);
    if (!info_ptr){
        png_destroy_read_struct(&png_ptr,
           (png_infopp)NULL, (png_infopp)NULL);
        return -1;
    }
    png_infop end_info = png_create_info_struct(png_ptr);
    if (!end_info){
        png_destroy_read_struct(&png_ptr, &info_ptr,
          (png_infopp)NULL);
        return -1;
    }    
    png_init_io(png_ptr, fp);                 // init
    png_set_sig_bytes(png_ptr, number);       // inform libpng read-bytes
    png_read_info(png_ptr, info_ptr);         // get info    
    png_uint_32 width, height;
    int bit_depth, color_type, interlace_type;
    int compression_type, filter_method;
    png_get_IHDR(png_ptr, info_ptr, &width, &height, &bit_depth, &color_type, &interlace_type, &compression_type, &filter_method);
    int channels = png_get_channels(png_ptr, info_ptr);
    int rowbytes = png_get_rowbytes(png_ptr, info_ptr);
    switch(color_type){
    case PNG_COLOR_TYPE_RGB:             // RGB only
    case PNG_COLOR_TYPE_RGB_ALPHA:
        break;
    case PNG_COLOR_TYPE_GRAY:
    case PNG_COLOR_TYPE_PALETTE:
    case PNG_COLOR_MASK_PALETTE:
        //    case PNG_COLOR_MASK_COLOR:
    case PNG_COLOR_MASK_ALPHA:
        return -1;
    }
    if(bit_depth!=8) return -1;
    *buf = new unsigned char[rowbytes*height];
    unsigned char **rows = new unsigned char*[height];
    for(int i = 0; i < height; i++){
        rows[i] = &(*buf)[i*rowbytes];
    }
    png_read_image(png_ptr, rows);
    png_read_end(png_ptr, end_info);
    png_destroy_read_struct(&png_ptr, &info_ptr, &end_info);
    *iHeight = height;
    *iWidth = width;
    *bAlpha = color_type == PNG_COLOR_TYPE_RGB_ALPHA;
    *iRowbytes = rowbytes;
    delete rows;
    return 0;
}

コンパイルは png.h をインクルードしてから -lpng12 -lz -lm をつければいいはず．

ちなみに，Cygwin には mingw の libpng がないのでソースから作る必要があるっぽい．cygwin の libpng を使ったらプログラムが止まらなくなったりしたし．作るのは普通どおりにただ cygwin 使うなと指定してやれば良いみたい．

CFLAGS="-Wall -O3 -funroll-loops -mno-cygwin" ./configure --libdir=/lib/mingw/ --includedir=/usr/include/mingw/
make
make install

Javaではいささか遅すぎるので， SDL + OpenGL で書き直し．

とりあえず，SDL日本語ドキュメントを参照しつつてきとうに組んでみた．画像表示部分には OpenGL を使うので，そっちもてきとうに調べるべし．ちなみに，SDL を入れて C++ でコンパイルしようとしたら SDL_audio.h の 97 行目で文句を言われたので，

 <- void (SDLCALL *filters[10])(struct SDL_AudioCVT *cvt, Uint16 format);
 -> void (SDLCALL *filters)(struct SDL_AudioCVT *cvt, Uint16 format);

こんな書き換えをしてやった．audio 使わない限り大丈夫でしょう．

んで，プログラムの感じは以下のとおりで．まず main 関数は SDL の初期化(VIDEOのみ)をして GL の属性を指定して，Window を作ったら他の初期化をしてからループしてメッセージ処理と描画処理をする．

int main(int argc,char *argv[])
{
     /* SDL初期化 */ 
    if(SDL_Init(SDL_INIT_VIDEO)<0){
        cerr << "SDL Initialization failed." << endl; 
        exit(-1);
    }
    SDL_GL_SetAttribute( SDL_GL_RED_SIZE, 8 );
    SDL_GL_SetAttribute( SDL_GL_GREEN_SIZE, 8 );
    SDL_GL_SetAttribute( SDL_GL_BLUE_SIZE, 8 );
    SDL_GL_SetAttribute( SDL_GL_DEPTH_SIZE, 1 );
    SDL_GL_SetAttribute( SDL_GL_DOUBLEBUFFER, 1 );
    /* 画面作成 */
    int flags = SDL_OPENGL;// | SDL_FULLSCREEN;
    screen = SDL_SetVideoMode(WindowSizeX,WindowSizeY,ColorDepth,flags);
    if(screen == NULL){    
        cerr << "Window Creation failed." << endl; 
        SDL_Quit();
        exit(-2);
    }
    init();
    /* メインループ */
    do{
        processEvent();
        updateScreen();
    } while(!done); 
    SDL_Quit();
    return 0;  
}

メッセージ処理はいつもの Windows のと変わるはずも無く．

int processEvent()
{
    SDL_Event e;
    if (SDL_PollEvent(&e) != 0){  // event がある？
        switch(e.type){
        case SDL_QUIT:
            done = true;
            break;
        case SDL_KEYDOWN:
            switch(e.key.keysym.sym){
            case SDLK_1:                 // アルゴリズム選択
                rotType = 1;
                break;
            case SDLK_2:
                rotType = 2;
                break;
            case SDLK_3:
                rotType = 3;
                break;
            case SDLK_4:
                rotType = 4;
                break;
            case SDLK_p:                 // 描画・非描画フリップ
                painting = !painting;
                break;
            case SDLK_u:                // 描画スキップ
                stepsPerDraw++;
                break;
            case SDLK_d:
                if(stepsPerDraw>1) stepsPerDraw--;
                break;
            case SDLK_f:                 // fps を描画
                fpsDrawFlag = true;
                break;
            case SDLK_q:
            case SDLK_ESCAPE:
                done = true;
                break;
            }
            break;
        }
    }
}

描画部分は fps を計算しつつ適当にと．ゲームなら fps の固定のための wait があるでしょう．

int updateScreen()
{
    static int steps = 0;
    static int time = SDL_GetTicks();
    if(steps%stepsPerDraw==0)
        drawImage();
    rotate();
    steps++;
    int t = SDL_GetTicks();
    if(t - time >= 1000 / freqFPSUpdate){
        totalSteps-=stepsHist[sp];
        totalMillis-=millisHist[sp];
        stepsHist[sp] = steps;
        millisHist[sp] = (int)(t - time);
        totalSteps+=stepsHist[sp];
        totalMillis+=millisHist[sp];
        sp = (sp + 1) % millisHistLength;
        steps = 0;
        fps = totalSteps * 100000 / totalMillis; // fps*100です
        time = t;
    }
}

OpenGL での描画はこんな感じで．glDrawPixels でフレームバッファをダイレクトに転送．その際，GL_LUMINANCE で輝度情報のみにしているが，GL_RGB とかにすると3byte / 1 ドット でカラーの転送とかできる．

画像転送後には文字列を描画している．

void drawImage()
{
    static char str[64]={0};
    static char *s1 = str;
    sprintf(s1, "%d.%d fps (skip %d) algo-%d", fps/100, fps%100, stepsPerDraw-1, rotType);
    if(painting){
        glClear(GL_COLOR_BUFFER_BIT);
        //glDrawPixels(ImageWidth , ImageHeight, GL_BLUE, GL_UNSIGNED_BYTE , rotatedPixels);
        glDrawPixels(ImageWidth , ImageHeight, GL_LUMINANCE, GL_UNSIGNED_BYTE , rotatedPixels);
        //glFlush();
        drawString(s1);
        SDL_GL_SwapBuffers();
    } else {
        if(fpsDrawFlag){
            glClear(GL_COLOR_BUFFER_BIT);
            fpsDrawFlag = false;
            drawString(s1);
            SDL_GL_SwapBuffers();
        }
    }
}

んで，文字列の描画には ASCII だけでいいなら glut のビットマップフォントが使えるのでそれを使う．font_init で各キャラクタの書き方を指定しておいて，あとでglCallListsで使う．font_init のループでは文字のASCIIコードに対してその文字の描画コードを対応付けているので，glCallLists でASCIIコード列であるところの文字列を渡すとうまい具合に文字が表示できる(リスト生成時にスクランブルしとくと楽しいかも)．ちなみに，日本語も使えるようにするにはここら辺が参考になるかも．

void font_init()
{
    base = glGenLists(128);
    for(int i=0;i<128;i++){
        glNewList(base+i, GL_COMPILE);
        glutBitmapCharacter(GLUT_BITMAP_HELVETICA_18, i);
        glEndList();
    }
    glListBase(base);
}
void drawString(const char *out, float r=1.0f, float g=1.0f, float b=1.0f)
{
     glPushAttrib(GL_ALL_ATTRIB_BITS);
     glColor3f(r, g, b);
     glRasterPos2i(whiteSpace/2, WindowSizeY-statusFieldY+5);
     glCallLists( strlen(out) , GL_BYTE, out);
     glPopAttrib();
}

あとはまあ，初期化部分ののこりをば．glOrtho のことろは 2D の描画の座標とスクリーン上の座標のスケールをあわせるためのもの．これをやっとかないと glRasterPos2i で予想以上に座標が動きすぎる．

void init()
{
     glViewport(0,0, WindowSizeX, WindowSizeY);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity(); 
    glOrtho(0.0, (GLdouble) WindowSizeX , 0.0, (GLdouble) WindowSizeY , -1.0, 1.0);
    glRasterPos2i(whiteSpace, whiteSpace);
    fps = 0;
    steps = 0;
    totalSteps = 0;
    totalMillis = 0;
    for(int i = 0; i < millisHistLength; i++){
        stepsHist[i] = 0;
        millisHist[i] = 0;
    }
    sp = 0;
    font_init();
    glDisable( GL_DEPTH_TEST );
    glDisable( GL_LIGHTING );
}

んで，最後にコンパイルはこんな感じで．オプションが長い．．．

g++ ImageRotator.cpp -o ImageRotator `sdl-config --cflags --libs` -lglut32 -lopengl32 -lglu32 -mno-cygwin -O3

とりあえず動くものをここにおいておこう．インクルードが <SDL/SDL.h> でなく <SDL.h> でないとだめかも．

少し前に画像の周りを黒く塗っておいて if を使わなければ速いだろうと予想したのだが，結果としてうまくいかん．各行の元画像からのコピーができる両端を先に計算しておくタイプのほうが速い．よくよく考えると，両端の計算は縁の長さ程度のオーダーですむ上に，その領域から外れている部分は黒く塗りつぶすことが確定しているので元画像へのアクセス不要．一方，縁を黒く塗りつぶして大きくした画像を使った場合は，縁の計算がいらない代わりに黒い部分も元画像にアクセスするためキャッシュが効かない状況では不利．

キャッシュをちゃんと考えないといけない問題で下手に番兵を使うと痛い目を見るいい例だな．以後気をつけよう．

今回のプログラムの課題は 1024x1024 の画像を1度ずつ回転させろとこのこと．速度重視で秒間に何回まわせるかを追求する．で，早速速度度外視の Java でアルゴリズムの検証をば．

まず，ピクセルは回転先画像の各ピクセルからから元の画像の対応するピクセルをコピーすれば穴はなくなると．んで，対応するピクセルが存在するかの判定を毎回するのは馬鹿なので，各行に対して対応するピクセルが存在する範囲をあらかじめ求めておいてジャンプを減らすと．これをやると 16fps から 19fps に速度アップ（でもあまり大きく上がらないなぁ．）

もうひとつ，普通に走らせていると90度ごとに fps が遅くなることに気づく．これは，90度回転あたりで row major に格納されているデータを column major でアクセスし，キャッシュミスが大量に発生することによる．ということで，キャッシュを当てやすくするように90度回転したデータをも保持しておいて，角度の近いほうからコピーするように改善．これで結構速度が安定してきた．

あとは，メモリを倍喰うけど元画像の周りに黒塗りの領域を作っておいて if の判定自体をなくしてしまうのと，これに伴って90度回転以外の中間画像も作っておいてキャッシュを当てやすくする．んで，効果が確認できたら速度重視のC++に移ると．

なんとなく Linux でも Windows でも動くGUI プログラムを作りたかったので wxWidgets をインストール．Windows でも cygwin(MinGW) から使うので，展開後に ./configure; make; make install .　まあ，結果として問題なく動くのだが，configure の途中でWindows の find が呼ばれてこけたのは少々痛い．パスの順番を cygwin 優先にして解決したけど，find とか sort とか windows につけるなよと思う．

とりあえず，フレームを出すだけのプログラムとコンパイルコマンドを書いておこう．

// g++ hello.cpp -o hello `wx-config --cxxflags --libs` -mwindows
#include "wx/wxprec.h"
#ifndef WX_PRECOMP
    #include "wx/wx.h"
#endif
 
class MyApp : public wxApp
{
public:
    virtual bool OnInit();
};
  
IMPLEMENT_APP(MyApp)
  
bool MyApp::OnInit()
{
    // create the main application window
	wxFrame *frame = new wxFrame(NULL,
                                 -1,
                                 wxT("Hello"),
                                 wxPoint(100, 100),
                                 wxSize(600, 480));
    frame->Show(true);
    return true;
}