ぬの部屋(仮)
nu-no-he-ya
  •     123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
    1234567
    891011121314
    15161718192021
    22232425262728
           
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
         12
    3456789
    10111213141516
    17181920212223
    242526272829 
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
        123
    45678910
    11121314151617
    18192021222324
    25262728   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    15161718192021
    293031    
           
         12
    3456789
    10111213141516
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
          1
    2345678
    9101112131415
    16171819202122
    232425262728 
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
  • CUDAで直線を書くことを考える(1)(考えるだけ)

    前置き

    ブレゼンハムを並列化するには?と思ったのだが、そもそもブレゼンハムは、「シングルスレッドで高速化するためには全部整数演算にすればいいんだ」というアルゴリズムなので(多分)、並列化とは相性が悪そうなんじゃないかと言うことで、とりあえず普通の数学的な式をそのまま使用してみる。

    なお私はCUDA入門者なのであまり人様の参考になるようなことは書けない。

    ベースとなる直線のプログラム(C++)

    #include <iostream>
    #include<vector>
    #include<algorithm>
    
    #pragma warning(disable:4996)
    
    //! @brief PBM(1byte,テキスト)を書き込む
    //! @param [in] fname ファイル名
    //! @param [in] width 画像の幅
    //! @param [in] height 画像の高さ
    //! @param [in] p 画像のメモリへのアドレス
    //! @details 1画素1Byteのメモリを渡すと、0,1テキストでファイル名fnameで書き込む
    void pbmP1_Write(const char* const fname, const int width, const int height, const unsigned char* const p) { // PPM ASCII
    
      FILE* fp = fopen(fname, "wb");
      fprintf(fp, "P1\n%d\n%d\n", width, height);
    
      size_t k = 0;
      for (size_t i = 0; i < (size_t)height; i++) {
        for (size_t j = 0; j < (size_t)width; j++) {
          fprintf(fp, "%d ", p[k] ? 0 : 1);
          k++;
        }
        fprintf(fp, "\n");
      }
    
      fclose(fp);
    }
    
    const std::uint8_t white = 255;
    const std::uint8_t black = 0;
    
    
    //! @brief 与えられたピクセル座標が線分の方程式の上ならそのピクセルを塗りつぶす
    //! @param pimage 書き込み先
    //! @param width 画像サイズ
    //! @param height 画像サイズ
    //! @param sx 始点
    //! @param sy 始点
    //! @param ex 終点
    //! @param ey 終点
    //! @param pixelx 処理するピクセル
    //! @param pixely 処理するピクセル
    void multiline_core(std::uint8_t* pimage, int width, int height, int sx, int sy, int ex, int ey, int pixelx, int pixely) {
      double a = (ey - sy) / double(ex - sx);//傾き
      double b = sy - a * sx;//切片
    
    
      int pos = pixely * width + pixelx;
    
      if (pos < 0 || pos >= width * height)return;
    
      double y = int(a * pixelx + b);
    
      if (pixely < std::min(sy, ey))return;
      if (pixelx < std::min(sx, ex))return;
      if (pixely > std::max(sy, ey))return;
      if (pixelx > std::max(sx, ex))return;
    
      if (y == pixely) {
        pimage[pos] = black;
      }
    
    }
    //! @brief 全ての画素について、そのピクセルが直線上にあるかをテストする
    //! @param image 書き込み先
    //! @param width 画像サイズ
    //! @param height 画像サイズ
    //! @param sx 始点
    //! @param sy 始点
    //! @param ex 終点
    //! @param ey 終点 void multiline( std::vector<std::uint8_t>& image, int width, int height, int sx, int sy, int ex, int ey) { //全てのピクセルについて直線上にあるかをチェック for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { multiline_core( image.data(), width, height, sx, sy, ex, ey, x, y); } } }
    int main()
    {
    
      int width = 100;
      int height = 50;
    
      int sx = 98; // 線分の始点・終点を設定
      int sy = 48;
      int ex = 1;
      int ey = 3;
      
      std::vector<std::uint8_t> image(width * height * 1, white);
    
      multiline(image, width, height, sx, sy, ex, ey);
    
      pbmP1_Write("c:\\test\\a.pbm", width, height, image.data());
    
    }
    

    普通に考えると「あるピクセルの隣のピクセルを塗る」という考え方でループするのだが、1ピクセル1スレッドで並列化する場合は「このピクセルは塗るべきか?をそれぞれのピクセルに対してチェックする」という考え方をすれば、ループする必要はない。

    次回

    上記プログラムをCUDAで実装する。