Hatena::ブログ(Diary)

mirichiの日記 このページをアンテナに追加 RSSフィード

2017-01-08

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

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

理屈

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

f:id:mirichi:20170108101829p:image

これを塗りつぶすと左右の三角形に色が付くことになるのだが、塗りつぶした三角形でこれを描画するには真ん中の交点が必要となる。このレベルの形状なら簡単だが、複雑な形状になるとそれを計算するのは非常に難しくなるので、NanoVGではそのような手法を使わず、ステンシルバッファとTriangleFanを使う。

ステンシルバッファとはOpenGLやDirectXに昔からあるマスクを作るバッファである。フレームバッファと同様に1ピクセル単位で値を持ち、ポリゴンを描画して、条件により値を書き込むことができる。TriangleFanはググるとたくさん出てくるが、連続した三角形を少ない頂点数で描画する表現方法の一つである。

で、この2つをどう組み合わせるかというと、まず塗りつぶす頂点を順番に用意しておいて、おもむろにTriangleFanでステンシルバッファに描画する。描画条件として、左回りは-1、右回りは+1と設定する(逆かもしれないがどっちでもいい)。これにより、左右の両方で同じ回数描画された領域は0になる。最後に、形状を覆うサイズの矩形でステンシルバッファが0以外のところに色を描くと、綺麗に塗りつぶされた画像が作れる。この方式を非ゼロ回転数ルール(参考)と言うらしい。

もうちょい具体的に。

f:id:mirichi:20170108101830p:image

さきほどの画像を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

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

結果

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

f:id:mirichi:20170108101831p:image

2017-01-07

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

今まで放置していた色をつける機能を追加する。NanoVGではnvgStrokeColorでベタ塗りの色を指定して、nvgStrokePaintでグラデーションを設定できる。どちらも内部的にはNVGstate構造体のstrokeメンバにNVGpaint構造体を格納しているだけである。よってベタ塗りとグラデーションは関数こそ違うが設定は後勝ちとなる。NanoVGではベタ塗りも3種類あるグラデーションもすべて一つのNVGpaint構造体で表現できるようになっていて、この中身のパラメータをシェーダでごにょごにょ計算して色を生成する。

OreVGではラスタライザもRubyで書いているのでこのいかにも重そうな計算をピクセルごとにやるのはちょっと精神衛生上よろしくない。それぞれ分けることにする。

ラスタライザ

とりあえずOreVGクラスにインスタンス変数@paintを追加して、ベタ塗り用もしくはグラデーション用のオブジェクトを格納することにする。このオブジェクトはcalc_colorメソッドを持っていて、座標を渡すと色が返ってくるように作る。なのでラスタライザのtriangleは以下のようになる。

  private def triangle(x1, y1, x2, y2, x3, y3)
    rasterize(x1, y1, x2, y2, x3, y3) do |x, y|
      @image[x,y] = @paint.calc_color(x, y)
    end
    @triangles << [x1, y1, x2, y2, x3, y3]
  end

ベタ塗り

ベタ塗りの場合はstroke_colorメソッドで色を指定する。渡す値はDXRuby用の色配列ということにしておく。

  def stroke_color=(color)
    @paint = FillColor.new(color)
  end

FillColorクラスは渡された色を保持してcalc_colorで無条件に返すだけになる。

  class FillColor
    def initialize(col)
      @col = col
    end

    def calc_color(x, y)
      @col
    end
  end

簡単である。

線形グラデーション

線形グラデーションをするためにNanoVGと同様にlinear_gradientメソッドを作ってオブジェクトを返し、stroke_paintメソッドで設定するようにする。

  def linear_gradient(x1, y1, x2, y2, incol, outcol)
    LinearGradient.new(x1, y1, x2, y2, incol, outcol)
  end

  def stroke_paint(paint)
    @paint = paint
  end

このincolは(x1,y1)地点での色、outcolは(x2,y2)地点での色で、この間が中間色になる。この範囲外はそれぞれincol、outcol固定。これが水平、垂直だけなら簡単なのだが斜めにもグラデーションできてしまう仕様なのでそこだけちょっと考える必要がある。

  # 線形グラデーション
  class LinearGradient
    def initialize(x1, y1, x2, y2, incol, outcol)
      v = Vector.new(x2, y2) - Vector.new(x1, y1)
      @x1 = x1
      @y1 = y1
      @len = v.len
      @incol = incol
      @outcol = outcol
      @dx, @dy = v.normalize
    end

    def calc_color(x, y)
      # 渡された座標を0〜1にマッピング
      t = ((x - @x1) * @dx + (y - @y1) * @dy) / @len

      if t <= 0
        @incol # 0以下の色
      elsif t >= 1
        @outcol # 1以上の色
      else # 中間色算出
        @incol.zip(@outcol).map do |ary|
          ary[0] * (1-t) + ary[1] * t
        end
      end
    end
  end

ちなみにまだ作っていない機能に座標のアフィン変換があって、これで座標を変形するとグラデーションの座標も同様に変形しないといけないのだが、それは当然まだ入っていない。変形するタイミングはstroke_paintなのでそこの中を変更するだけになる。

結果

このように線形グラデーションができるようになる。あと円状のグラデーションと箱状のグラデーションがあるが、クラス追加するだけなのでたいして難しくないはず。

f:id:mirichi:20170103112139p:image

今回のコードはこちら

2017-01-06

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

今回は3次ベジェ曲線を作る。ベジェ曲線というのは始点終点であるアンカー2つと制御点を使って曲線を描画するアルゴリズムである。具体的にはベジェ曲線 - Wikipediaの下のほうの作図法を見てもらうとわかりやすい。また、3次ベジェ曲線体験ツールを作ったのでこれを動かしてもらえると実際どのように描画されるのかが目で見てわかる。アンカー、ハンドル、スライダーをドラッグようにしてあるのでどうすればどうなるかが理解しやすい。ちょっと小さくて使いにくいけど。

あと、ベジエ曲線について - s.h’s pageを見てもらえばいろいろと具体的なことがわかると思う。

tesselate_bezier

ベジェ曲線は任意の位置で2つのベジェ曲線に分割することができるので、NanoVGではこの特性を利用して再帰で二等分していって、直線で表現できるレベルまで細かくする。後は分割された点を配列に格納して直線として描画するだけである。この分割する関数がtesselate_bezierで、このようになる。

    def tesselate_bezier(x1, y1, x2, y2, x3, y3, x4, y4, level, type)
      return if level > 10
    
      dx = x4 - x1
      dy = y4 - y1
      d2 = ((x2 - x4) * dy - (y2 - y4) * dx).abs
      d3 = ((x3 - x4) * dy - (y3 - y4) * dx).abs
    
      if (d2 + d3) * (d2 + d3) < 0.25 * (dx * dx + dy * dy)
        point = Point.new(Vector.new(x4, y4))
        point.corner = type
        @points << point
        return
      end
  
      x12 = (x1 + x2) * 0.5
      y12 = (y1 + y2) * 0.5
      x23 = (x2 + x3) * 0.5
      y23 = (y2 + y3) * 0.5
      x34 = (x3 + x4) * 0.5
      y34 = (y3 + y4) * 0.5
      x123 = (x12 + x23) * 0.5
      y123 = (y12 + y23) * 0.5
      x234 = (x23 + x34) * 0.5
      y234 = (y23 + y34) * 0.5
      x1234 = (x123 + x234) * 0.5
      y1234 = (y123 + y234) * 0.5
    
      tesselate_bezier(x1, y1, x12, y12, x123, y123, x1234, y1234, level + 1, false)
      tesselate_bezier(x1234, y1234, x234, y234, x34, y34, x4, y4, level + 1, type)
    end
  end

大きな曲線を描画するとものすごく細かくなってしまうので、とりあえず10回で再帰を諦めるようになっている。最後の引数はcornerフラグに使われる。ベジェ曲線の途中では線の接続処理はしないという意味になる。このメソッドはSubPathクラスに追加した。ちなみに3次ベジェ曲線体験ツールの描画もこのメソッドを使っている。

ベジェ曲線描画用のコマンドクラスは

  class CmdBezierTo < Struct.new(:h1x, :h1y, :h2x, :h2y, :x, :y);end

となる。ユーザが呼ぶメソッドは

  def bezier_to(h1x, h1y, h2x, h2y, x, y)
    append_commands(CmdBezierTo.new(h1x, h1y, h2x, h2y, x, y))
    self
  end

で、flatten_pathsは

  private def flatten_paths
    @commands.each do |cmd|
      case cmd
      when CmdMoveTo
        @subpaths << SubPath.new # 新規サブパス追加
        point = Point.new(cmd)
        point.corner = true
        @subpaths.last.points << point
      when CmdLineTo
        point = Point.new(cmd)
        point.corner = true
        @subpaths.last.points << point
      when CmdBezierTo
        last = @subpaths.last.points.last.v
        @subpaths.last.tesselate_bezier(last.x, last.y, cmd.h1x, cmd.h1y, cmd.h2x, cmd.h2y, cmd.x, cmd.y, 0, true)
      when CmdClose
        @subpaths.last.closed = true
      end
    end

結果

ベジェ曲線を描画できるようになった。

f:id:mirichi:20170102142327p:image

また、

  def ellipse(cx, cy, rx, ry)
    append_commands(CmdMoveTo.new(cx-rx, cy))
    append_commands(CmdBezierTo.new(cx-rx, cy+ry*KAPPA90, cx-rx*KAPPA90, cy+ry, cx, cy+ry))
    append_commands(CmdBezierTo.new(cx+rx*KAPPA90, cy+ry, cx+rx, cy+ry*KAPPA90, cx+rx, cy))
    append_commands(CmdBezierTo.new(cx+rx, cy-ry*KAPPA90, cx+rx*KAPPA90, cy-ry, cx, cy-ry))
    append_commands(CmdBezierTo.new(cx-rx*KAPPA90, cy-ry, cx-rx, cy-ry*KAPPA90, cx-rx, cy))
    append_commands(CmdClose.new)
    self
  end

このようなメソッドで楕円を描画できるようにもなる。KAPPA90は

  KAPPA90 = 0.5522847493

と定義される定数で円に非常に近いベジェ曲線を描くための係数である。

f:id:mirichi:20170102142329p:image

今回のソースはこちら