ベクタグラフィックスその8

大物としては最後になる塗りつぶし機能。NanoVGではベジェ曲線だろうがなんだろうが囲まれた部分を指定の色やグラデーションで塗りつぶすことができる。塗りつぶした三角形なら簡単に描画できるが、形状が不定のものをどうやって塗りつぶすかという問題である。

理屈

直線4本を連続で描画してこのような図形を作るとする。

これを塗りつぶすと左右の三角形に色が付くことになるのだが、塗りつぶした三角形でこれを描画するには真ん中の交点が必要となる。このレベルの形状なら簡単だが、複雑な形状になるとそれを計算するのは非常に難しくなるので、NanoVGではそのような手法を使わず、ステンシルバッファとTriangleFanを使う。
ステンシルバッファとはOpenGLやDirectXに昔からあるマスクを作るバッファである。フレームバッファと同様に1ピクセル単位で値を持ち、ポリゴンを描画して、条件により値を書き込むことができる。TriangleFanはググるとたくさん出てくるが、連続した三角形を少ない頂点数で描画する表現方法の一つである。
で、この2つをどう組み合わせるかというと、まず塗りつぶす頂点を順番に用意しておいて、おもむろにTriangleFanでステンシルバッファに描画する。描画条件として、左回りは-1、右回りは+1と設定する(逆かもしれないがどっちでもいい)。これにより、左右の両方で同じ回数描画された領域は0になる。最後に、形状を覆うサイズの矩形でステンシルバッファが0以外のところに色を描くと、綺麗に塗りつぶされた画像が作れる。この方式を非ゼロ回転数ルール(参考)と言うらしい。
もうちょい具体的に。

さきほどの画像をTriangleFanで描画すると、ステンシルバッファに123を結ぶ三角形と134を結ぶ三角形が描画される。123は左回り、134は右回りとなり、両方が描画されるエリアは0になるので色が置かれない。なるほどうまいことできている。

実装する

NanoVGではアンチエイリアス用バックエンドのためにちょと面倒なコードがあるが、今のところアンチエイリアスする機能が無いのでそのへんは省く。まずfill。

  def fill
    flatten_paths
    expand_fill(0, :miter, 2.4)
    render_fill
  end

strokeと似た感じ。次にexpand_fill。

  def expand_fill(w, line_join, miter_limit)
    calculate_joins(w, line_join, miter_limit)
    
    # 頂点生成
    @subpaths.each do |subpath|
      ([subpath.points.last] + subpath.points).each do |p0|
        subpath.verts << p0.v
        subpath.verts << p0.v
      end
    end
  end

色々計算はするけど特に使うこともなく全部の点を素直に結ぶ。んでrender_fill。

  private def render_fill
    s = Array.new(@image.height){Array.new(@image.width){0}} # ステンシルバッファ

    # ステンシルバッファにマスクを描画する
    @subpaths.each do |subpath|
      bp = Vector.new(subpath.verts[0].x, subpath.verts[0].y)
      subpath.verts[1..-1].each_cons(2).with_index do |ary|
        p0, p1 = ary
        stencil_triangle(bp.x, bp.y, p0.x, p0.y, p1.x, p1.y, s)
      end
    end

    # ステンシルバッファのマスクを適用した描画
    @subpaths.each do |subpath|
      @image.height.times do |y|
        @image.width.times do |x|
          @image[x, y] = @paint.calc_color(x, y) if s[y][x] != 0
        end
      end
    end
  end

ステンシルバッファは単純に配列の配列で作る。TriangleFanと同じように頂点を指定してstencil_triangleを呼ぶことで配列の配列にマスクデータを構築する。その後にImage全体でマスクが0以外の場所に色を書き込む。stencil_triangleはこんな感じに。

  private def stencil_triangle(x1, y1, x2, y2, x3, y3, s)
    cross = (x3-x2) * (y2-y1) - (x2-x1) * (y3-y2)
    if cross > 0.0
      rasterize(x2, y2, x1, y1, x3, y3) do |x, y|
        s[y][x] -= 1
      end
    else
      rasterize(x1, y1, x2, y2, x3, y3) do |x, y|
        s[y][x] += 1
      end
    end
    @triangles << [x1, y1, x2, y2, x3, y3]
  end

三角形がどっち回りかによってステンシルバッファを足したり引いたりする。

結果

今回のコードはこちら。このアルゴリズムはベジェ曲線でも囲まれた部分だけ塗ることができるので、こんな感じの描画ができるようになった。塗りつぶしの色はベタ塗りでもグラデーションでも普通に対応できる。