クリッパー

by syoyo

クリッパー(clipper)を angelina に実装してみました。
(バイナリは windows 用)

http://lucille.atso-net.jp/svn/angelina/geom/clipper/

クリッパーとは、クリップ処理を行うルーチンです。

lucille では、レイトレのための空間データ構造として、kd-tree や一様グリッドを用いています。
もし分割面やグリッドをまたぐようなポリゴンがある場合は、クリッピング処理はせずに、
同じポリゴンの情報を分割されうるすべての領域に登録しています。

とはいえ、この場合だと、kd-tree の場合は最適な解に達することができずに
うまく効率的に分割できないことがあったり
(cornell box のような至極単純なシーンで起こりやすいのでたちが悪い)、
また一様グリッドの場合でも、
ヒットしたポリゴンが実際に現在のグリッド内にあるかどうか
をチェックする必要が生じます。

前々からクリッピングの必要性は感じていましたが、なんかめんどくさそうだなー、
と思って手をつけずにいました。

今回クリッパーを実装しようと思い立ったきっかけは、
BSP を使わずとも、どの視点からもすでにソート済みのポリゴンリストを取り出せるという
なんともシュゴーな手法をグラキャドで
聴講したのがきっかけでした。

福重 真一、鈴木宏正
ポリゴン間のプライオリティ決定のための円環型データ構造
第 118 回 情報処理学会 グラフィクスとCAD研究発表会
http://www.okada-lab.org/GCAD/Sched/2004/prog118.txt

BSP に比べて、ソート時間がとても早くなる(というかそもそもソートの必要がない)
のですが、より多くのメモリ消費量の問題、
視点の制限、必ず正確なソートになるかなど、いくつかまだ問題はありそうですが、なかなか興味深い。

提案されているのはアルファのあるポリゴンレンダリングのための BSP の代案手法が
メインなのですが、これをレイトレに適した空間データ構造として実現するとなると…
と考えてみて、やはりまずはともあれクリッピングは必須だなという結論に達したのです。

とはいえ、実際にクリッパーを実装してみると、以外にも思っていたより
美しく処理できることができることがわかり、ちょっと感動。
やっぱ昔のひとはすげーよ。

今回実装したのは、有名な Sutherland-Hodgeman クリッピングアルゴリズムです。

Ivan E. Sutherland and Gary W. Hodgman,
Reentrant polygon clipping
Commun. ACM,
17(1), pp. 32-42, 1974
http://doi.acm.org/10.1145/360767.360802

詳細は Foley 本(邦訳「コンピュータグラフィックス 理論と実践」) にあります。

Foley 本では実装のアウトラインを示しているだけですが、
それでもコードを自分で補間するのは簡単にできるでしょう。

クリッピングといっても、凸ポリゴンか凹ポリゴンかでまた微妙に処理が異なるらしいのですが、

今回は、

o 入力ポリゴンは三角形に限定
o kd-tree の場合は 1 つの平面でクリップ
o 一様グリッドの場合は軸並行ボリュームの 6 平面でクリップ

という条件での三次元ポリゴンのクリップになります。

この場合ですと、入力される三角形ポリゴンは、最大でも 6
角形ポリゴン(全部の辺がクリップされる)までとなる(はず?)ので、
あらかじめ出力のバッファには二倍のポリゴンを保持するメモリを割り当てておけば十分になります。

クリップ処理部はこんなかんじになります。

typedef struct _vertex_t
{
      float x, y, z;
} vertex_t;

typedef struct _plane_t
{
      float x, y, z;
      float nx, ny, nz;       // normal
} plane_t;

void clip(vertex_t *in, vertex_t *out, int inLen, int *outLen,
    plane_t *clipPlane)
{
    int j;
    vertex_t *s, *p, i;
    vertex_t newv;
    *outLen = 0;
    s = &in[inLen - 1];     // start with last vertex.
    for (j = 0; j < inLen; j++) {
    p = &in[j];     // current vertex
    if (inside(p, clipPlane)) {
            if (inside(s, clipPlane)) {
                    output(p, outLen, out);
            } else {
                    intersect(&newv, s, p, clipPlane);
                    output(&newv, outLen, out);
                    output(p, outLen, out);
            }
    } else {
            if (inside(s, clipPlane)) {
                    intersect(&newv, s, p, clipPlane);
                    output(&newv, outLen, out);
            }
    }
    s = p;
}

bool inside(vertex_t *p, plane_t *b)
{
      vertex_t pb;
      float d;

      pb.x = p->x - b->x;
      pb.y = p->y - b->y;
      pb.z = p->z - b->z;

      // if ((p - b.pos) dot b.normal) >= 0, then p is inside
      d = pb.x * b->nx + pb.y * b->ny + pb.z * b->nz;

      if (d >= 0) return true;

      return false;           // not inside
}

void intersect(vertex_t *i, vertex_t *s, vertex_t *p, plane_t *b)
{
      vertex_t v;
      double vdotn;
      double sdotn;
      double d;

      double t;

      // direction
      v.x = p->x - s->x;
      v.y = p->y - s->y;
      v.z = p->z - s->z;

      vdotn = v.x * b->nx + v.y * b->ny + v.z * b->nz;
      if (fabs(vdotn) < 0.0001) {
              printf("error: vdotn is too small!\n");
              printf("  vdotn = %f\n", vdotn);
              exit(-1);
      }

      // d = plane equation
      d = -(b->x * b->nx + b->y * b->ny + b->z * b->nz);

      sdotn = s->x * b->nx + s->y * b->ny + s->z * b->nz;

      // t = ray parameter of intersection point.
      t = -(sdotn + d) / vdotn;
      assert(t >= 0.0);

      i->x = s->x + t * v.x;
      i->y = s->y + t * v.y;
      i->z = s->z + t * v.z;
}

void output(vertex_t *p, int *outLen, vertex_t *out)
{
        out[(*outLen)].x = p->x;
        out[(*outLen)].y = p->y;
        out[(*outLen)].z = p->z;
        // increment index
        (*outLen)++;
}

クリップ面が複数ある場合(たとえば軸並行ボリュームでクリップ)は、
以下のようにダブルバッファ構成にすればいいでしょうか。


static plane_t clipPlanes[6] = {
  { 0.0, 1.0, 0.0, 0.0, -1.0, 0.0 },      // top
  { -1.0, 0.0, 0.0, 1.0, 0.0, 0.0 },      // left
  { 0.0, -1.0, 0.0, 0.0, 1.0, 0.0 },      // bottom
  { 1.0, 0.0, 0.0, -1.0, 0.0, 0.0 },      // right
  { 0.0, 0.0, -1.0, 0.0, 0.0, 1.0 },      // back
  { 0.0, 0.0, 1.0, 0.0, 0.0, -1.0 },      // front
};

void volumeClip()
{
    int i;
    vertex_t *tmp;
    int bufLen;
    plane_t clipPlane;
    in = &(bufTri[0]);
    out = &(outTri[0]);
    bufLen = inLen;
    for (i = 0; i < 6; i++) {
        // clip!
        clip(in, out, bufLen, &outLen, &clipPlanes[i]);
        tmp = in;
        in = out;
        out = tmp;
        bufLen = outLen;
    }
    out = in;
}

あとは、クリップ面がポリゴンのエッジや面とほぼ重なりつつも平行になっている場合とか、
クリップされるばあいの交点の計算および交点位置の頂点パラメータの補間処理
などにおける数値演算誤差へのロバストな対応が必要になりそうです。

とところで、GPU に載っているハードウェアクリッパーって、どうなっているのかぁ。
最近の NV とかの GPU では、同時座標ラスタライズでクリッパーは不要になっているみたいですね。
ハードウェアでの実装云々は、論文を読むより特許を読んだほうが早いかな?

Advertisements