スキャンラインへの道

なんとなく開始。
とりあえず最初のパーツとして2次元の三角形描画からはじめる。
GL_TRIANGLESのような頂点配列処理を想定して書いてみる。

三角形その１

ピクセル毎に2次元外積で三角形の内外を判定して描画するコード。
手元の本の最初に載っていた方法。
陰関数を各ピクセルについて解く方法に近いか。

#include <cassert>
#include <cmath>
#include <vector>
#include <sstream>
#include <fstream>
#include <limits>
#include <boost/random.hpp>
#include <boost/algorithm/minmax.hpp>
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>

#define SCREEN_W  (480)
#define SCREEN_H  (480)

//------------------------------------------------------------//
// RGB24 image
//------------------------------------------------------------//
struct Pixel24
{
  unsigned char r;
  unsigned char g;
  unsigned char b;

  Pixel24()
  {}

  Pixel24(int _r, int _g, int _b)
  : r(_r), g(_g), b(_b)
  {}
};

class Image24
{
  std::vector<Pixel24> raw_;
  int w_;
  int h_;

public:
  Image24(int w, int h)
  : w_(w), h_(h)
  {
    raw_.resize(w * h, Pixel24(0, 0, 0));
  }

  Pixel24* raw(){ return &raw_[0]; }
  int width(){ return w_; }
  int height(){ return h_; }

  void writePPM6(const char *filepath)
  {
    std::ofstream io(filepath, std::ios::binary);
    if(!io){
      return;
    }
    // header
    io << "P6\n" << w_ << ' ' << h_ << '\n' << "255\n";
    // raw data
    io.write((const char*)&raw_[0], raw_.size()*3);
  }
};

//------------------------------------------------------------//
// Vertex
//------------------------------------------------------------//
struct Vertex
{
  float x;
  float y;
  float z;

  Vertex(float _x, float _y, float _z)
  : x(_x), y(_y), z(_z)
  {
  }

  Vertex operator-(const Vertex &rhs)const
  {
    return Vertex(x-rhs.x, y-rhs.y, z-rhs.z);
  }

  static double cross2D(const Vertex &lhs, const Vertex &rhs)
  {
    return lhs.x * rhs.y - lhs.y * rhs.x;
  }
};
std::ostream &operator<<(std::ostream &os, const Vertex &rhs)
{
  return os
    << "[" << rhs.x << ',' << rhs.y << ',' << rhs.z << "]";
}

//------------------------------------------------------------//
// Triangle2D
//------------------------------------------------------------//
struct Triangle2D
{
  const Vertex &v0;
  const Vertex &v1;
  const Vertex &v2;

public:
  Triangle2D(const Vertex &_v0, const Vertex &_v1, const Vertex &_v2)
  : v0(_v0), v1(_v1), v2(_v2)
  {}

  bool isInclude(const Vertex &v)
  {
    double determine=Vertex::cross2D(v-v0, v1-v0);
    if(determine>0){
      return Vertex::cross2D(v-v1, v2-v1)>0 && Vertex::cross2D(v-v2, v0-v2)>0;
    }
    else if(determine<0){
      return Vertex::cross2D(v-v1, v2-v1)<0 && Vertex::cross2D(v-v2, v0-v2)<0;
    }
    else{
      return false;
    }
  }
};
std::ostream &operator<<(std::ostream &os, const Triangle2D &rhs)
{
  return os
    << "TRI(" << rhs.v0 << rhs.v1 << rhs.v2 << ")";
}

//------------------------------------------------------------//
// draw
//------------------------------------------------------------//
void drawPixelCrossTriangle(
    Pixel24 *image, int w, int h, Vertex *v, Pixel24 *color)
{
  // clipping
  int minX=
    std::max(0, 
        static_cast<int>(
          std::floor(std::min(v[0].x, std::min(v[1].x, v[2].x)))));
  int maxX=
    std::min(SCREEN_W-1, 
        static_cast<int>(
          ceil(std::max(v[0].x, std::max(v[1].x, v[2].x)))));
  int minY=
    std::max(0, 
        static_cast<int>(
          floor(std::min(v[0].y, std::min(v[1].y, v[2].y)))));
  int maxY=
    std::min(SCREEN_H-1, 
        static_cast<int>(
          ceil(std::max(v[0].y, std::max(v[1].y, v[2].y)))));

  Triangle2D triangle(v[0], v[1], v[2]);

  // each pixel
  for(int y=minY; y<=maxY; ++y){
    Pixel24 *pixel=&image[w*y+minX];
    for(int x=minX; x<=maxX; ++x, ++pixel){
      if(triangle.isInclude(Vertex(x, y, 0))){
        *pixel=color[0];
      }
    }
  }
}

void drawPixelCross(Pixel24 *image, int width, int height,
  Vertex *vertexArray, Pixel24 *colorArray, int triangleCount)
{
  Vertex *pCurrentTriangle=vertexArray;
  Pixel24 *pCurrentColor=colorArray;

  // each triangle
  for(int i=0; i<triangleCount; 
      ++i, pCurrentTriangle+=3, pCurrentColor+=3)
  {
    drawPixelCrossTriangle(image, width, height, 
        pCurrentTriangle, pCurrentColor);
  }
}

//------------------------------------------------------------//
// test
//------------------------------------------------------------//
void test1(Vertex *vertexArray, Pixel24 *colorArray, 
    int triangleCount, const char *filepath)
{
  Image24 image(SCREEN_W, SCREEN_H);
  boost::timer t;

  drawPixelCross(
      image.raw(), image.width(), image.height(),
      vertexArray, colorArray, triangleCount);

  std::cout << t.elapsed() << "sec.\n";
  image.writePPM6(filepath);
  std::cout << "write " << filepath << std::endl;
}

int main(int argc, char **argv)
{
  if(argc<2){
    std::cout << "usage: " << argv[0] << " {triangle count}\n";
    return 1;
  }

  std::cout << "setup...";
  // random vertex array
  std::vector<Vertex> vertexArray;
  int triangleCount=boost::lexical_cast<int>(argv[1]);
  {
    boost::variate_generator<
      boost::mt19937, 
      boost::uniform_real<> > rand(
          boost::mt19937(3898), 
          boost::uniform_real<>(0, std::max(SCREEN_W, SCREEN_H)));
    for(int i=0; i<triangleCount; ++i){
      vertexArray.push_back(Vertex(rand(), rand(), rand()));
      vertexArray.push_back(Vertex(rand(), rand(), rand()));
      vertexArray.push_back(Vertex(rand(), rand(), rand()));
    }
  }

  // random color array
  std::vector<Pixel24> colorArray;;
  {
    boost::variate_generator<
      boost::mt19937, 
      boost::uniform_smallint<> > rand(
          boost::mt19937(75913), 
          boost::uniform_smallint<> (0, 255));
    for(int i=0; i<triangleCount; ++i){
      colorArray.push_back(Pixel24(rand(), rand(), rand()));
      colorArray.push_back(Pixel24(rand(), rand(), rand()));
      colorArray.push_back(Pixel24(rand(), rand(), rand()));
    }
  }
  std::cout << "done\n";

  test1(&vertexArray[0], &colorArray[0], triangleCount, "test1.ppm");
  return 0;
}

三角形の描画そのものと直接関係ないコードのせいで長くなった・・・
drawPixelCrossTriangle関数が本体。

$ ./release/sample 10000
setup...done
6.84sec.
write test1.ppm

さすがに遅い。

ToDo

• 行と三角形の交点を求めて間を埋める
• 縦方向にブレゼンハム・アルゴリズムを使って行と三角形の交点を求めて間を埋める