Gupta-Sproullアルゴリズム

ousttrue2009-02-24

さらに
「コンピュータグラフィックス　理論と実践」を参照して書いてみた。
前回の中点線分アルゴリズムを拡張してアンチエイリアス機能を追加した
Gupta-Sproullアルゴリズム。

動作原理は、ブレゼンハム的に線のピクセルを求めたのちに
ピクセルと線分の中心位置の距離に応じて透明度を変化させるというもの
(遠くなると薄くなる)。

この時1ピクセルの濃さだけを変化させると単に薄くなってしまいなめらかに
ならないのでその上下のピクセル(線分の傾き<1の場合)も線分からの距離に応じた濃さで描画する。
そうすると隣接ピクセルから線分までの最大距離が1.5になるので事前に0〜1.5の距離に応じた透明度テーブルを用意しておいて値を決めていく。
(線の太さ1の場合)

ただこの透明度テーブルが問題のようで、
元の論文には4bit(16階調)のものしか載っていないらしい。
フルカラーでやるにはそれでは不十分なのでもっと細かいものを用意する必用があるが
今回はここで発見した24階調のテーブルを使ってみた。
http://gurge.com/blog/2006/11/29/gupta-sproull-antialiased-lines/
「後でわしに感謝することになるだろうよ」
ということが書いてある(多分)。

感謝w

いずれにしろこの透明度テーブルは、
線の太さと濃さの階調に依存するので自前で用意できないと別のパターンでは使え無い。
妥当なものを計算で出す方法がわかるとよいのだけれど・・・

一応ソースコード。細部はわりといいかげん。
どうしても主軸X or Y * X軸+- * Y軸+- の8パターンが入ると長ったらしい
コードになる。なんとかならないものか・・・

#ifndef _DRAW_LINE_H
#define _DRAW_LINE_H

#include "image.h"

#include <cmath> // floor
#include <stdlib.h> // abs
#include <algorithm> // std::max

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp> 
namespace lmd=boost::lambda;

struct FCounter
{
  int couner;
  FCounter(int _counter) : couner(abs(_counter)){}
  bool isEnd() { return couner<=0; }
  void increment() { --couner; }
};

UINT32 Filter(const int index)
{
  const static UINT32 table[]={ 
    0xffc7c7c7 , 0xffc6c6c6 , 0xffc2c2c2 , 0xffbcbcbc
    , 0xffb3b3b3 , 0xffa9a9a9 , 0xff9c9c9c , 0xff8e8e8e
    , 0xff7f7f7f , 0xff707070 , 0xff626262 , 0xff545454
    , 0xff464646 , 0xff3a3a3a , 0xff2f2f2f , 0xff252525
    , 0xff1c1c1c , 0xff151515 , 0xff0e0e0e , 0xff090909
    , 0xff050505 , 0xff030303 , 0xff010101 , 0xff000000 
  };
  return table[index];
}

int Round(double t)
{
  const static double denom=24.0/1.5;
  return floor(t*denom);
}

void intensifyPixel(Locator pointer, const Vector2 &offset, double distance)
{
  pointer.set(offset, Filter(Round(fabs(distance))));
}

template<class COUNTER
, class INCREMENT_MAJOR, class INCREMENT_MINOR, class ADVANCE_MINOR>
void
GuptaSproullLine_(Locator pointer
    , int d, int incMajor, int incMinor
    , int dMajor, double invDenom, double two_v_dMajor_invDenom
    , const Vector2 &positiveOffset, const Vector2 &negativeOffset
    , COUNTER counter
    , INCREMENT_MAJOR incrementMajor
    , INCREMENT_MINOR incrementMinor, ADVANCE_MINOR determine
    , UINT32 
    )
{
  // start
  double v=0;
  intensifyPixel(pointer, Vector2(0, 0), v);
  intensifyPixel(pointer, positiveOffset, two_v_dMajor_invDenom-v);
  intensifyPixel(pointer, negativeOffset, two_v_dMajor_invDenom+v);

  // loop
  double two_v_dMajor=0;
  for(; !counter.isEnd(); counter.increment())
  {
    if(determine(d)){
      two_v_dMajor=d-dMajor;
      d+=incMinor;
      incrementMinor(pointer);
    }
    else{
      two_v_dMajor=d+dMajor;
      d+=incMajor;
    }
    incrementMajor(pointer);

    intensifyPixel(pointer, Vector2(0, 0), v);
    intensifyPixel(pointer, positiveOffset, two_v_dMajor_invDenom-v);
    intensifyPixel(pointer, negativeOffset, two_v_dMajor_invDenom+v);
  }
}

void GuptaSproullLine(Image<4> &image, const Vector2 &from, const Vector2 &to)
{
  int dx=to.x-from.x;
  int dy=to.y-from.y;

  if(dx==0){
    // vertical line or point
    Locator pointer=image.getLocation(dy>0 ? from : to);
    pointer.set(white);
    for(FCounter counter(dy); !counter.isEnd(); 
        counter.increment(), pointer.increment<AXIS_Y>())
      pointer.set(white);
    return;
  }
  if(dy==0){
    // horizontal line
    Locator pointer=image.getLocation(dx>0 ? from : to);
    pointer.set(white);
    for(FCounter counter(dx); !counter.isEnd(); 
        counter.increment(), pointer.increment<AXIS_X>())
      pointer.set(white);
    return;
  }

  double invDenom=1.0/(2.0*sqrt(dx*dx+dy*dy));
  int cmpdxdy=abs(dx)-abs(dy);
  if(cmpdxdy>=0){
    // MAJOR X
    if(dx>0){
      if(dy>0){
        // [0] dx > dy && dx>0 && dy>0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(dy)-(dx), 2*(dy), 2*((dy)-(dx))
            , dx, invDenom, 2.0*dx*invDenom , Vector2(0, 1), Vector2(0, -1)
            , FCounter(dx)
            , lmd::bind(&Locator::increment<AXIS_X>, lmd::_1)
            , lmd::bind(&Locator::increment<AXIS_Y>, lmd::_1)
            , (lmd::_1 > 0)
            , white
            );
      }
      else{
        // [1] dx > dy && dx>0 && dy<0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(dy)-(-dx), 2*(dy), 2*((dy)-(-dx))
            , dx, invDenom, 2.0*dx*invDenom , Vector2(0, -1), Vector2(0, 1)
            , FCounter(dx)
            , lmd::bind(&Locator::increment<AXIS_X>, lmd::_1)
            , lmd::bind(&Locator::decrement<AXIS_Y>, lmd::_1)
            , (lmd::_1 < 0)
            , red
            );
      }
    }
    else{
      if(dy>0){
        // [2] dx > dy && dx<0 && dy>0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(-dy)-(dx), 2*(-dy), 2*((-dy)-(dx))
            , dx, invDenom, 2.0*dx*invDenom , Vector2(0, 1), Vector2(0, -1)
            , FCounter(dx)
            , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1)
            , lmd::bind(&Locator::increment<AXIS_Y>, lmd::_1)
            , (lmd::_1 < 0)
            , green
            );
      }
      else{
        // [3] dx > dy && dx<0 && dy<0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(-dy)-(-dx), 2*(-dy), 2*((-dy)-(-dx))
            , dx, invDenom, 2.0*dx*invDenom , Vector2(0, -1), Vector2(0, 1)
            , FCounter(dx)
            , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1)
            , lmd::bind(&Locator::decrement<AXIS_Y>, lmd::_1)
            , (lmd::_1 > 0)
            , blue
            );
      }
    }
  }
  else if(cmpdxdy<0){
    // MAJOR Y
    if(dx>0){
      if(dy>0){
        // [4] dx < dy && dx>0 && dy>0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(dx)-(dy), 2*(dx), 2*((dx)-(dy))
            , dx, invDenom, 2.0*dy*invDenom , Vector2(1, 0), Vector2(-1, 0)
            , FCounter(dy)
            , lmd::bind(&Locator::increment<AXIS_Y>, lmd::_1)
            , lmd::bind(&Locator::increment<AXIS_X>, lmd::_1)
            , (lmd::_1 > 0)
            , cyan
            );
      }
      else{
        // [5] dx < dy && dx>0 && dy<0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(-dx)-(dy), 2*(-dx), 2*((-dx)-(dy))
            , dx, invDenom, 2.0*dy*invDenom , Vector2(-1, 0), Vector2(1, 0)
            , FCounter(dy)
            , lmd::bind(&Locator::decrement<AXIS_Y>, lmd::_1)
            , lmd::bind(&Locator::increment<AXIS_X>, lmd::_1)
            , (lmd::_1 < 0)
            , magenta
            );
      }
    }
    else{
      if(dy>0){
        // [6] dx < dy && dx<0 && dy>0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(dx)-(-dy), 2*(dx), 2*((dx)-(-dy))
            , dx, invDenom, 2.0*dy*invDenom , Vector2(-1, 0), Vector2(1, 0)
            , FCounter(dy)
            , lmd::bind(&Locator::increment<AXIS_Y>, lmd::_1)
            , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1)
            , (lmd::_1 < 0)
            , yellow
            );
        image.setPixel(to, yellow);
      }
      else{
        // [7] dx < dy && dx<0 && dy<0
        GuptaSproullLine_(
            image.getLocation(from) , 2*(-dx)-(-dy), 2*(-dx), 2*((-dx)-(-dy))
            , dx, invDenom, 2.0*dy*invDenom , Vector2(1, 0), Vector2(-1, 0)
            , FCounter(dy)
            , lmd::bind(&Locator::decrement<AXIS_Y>, lmd::_1)
            , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1)
            , (lmd::_1 > 0)
            , gray
            );
        image.setPixel(to, gray);
      }
    }
  }
}

void drawLine(Image<4> &image , const Vector2 &from , const Vector2 &to)
{
  GuptaSproullLine(image, from, to);
}

#endif // _DRAW_LINE_H

参考

http://courses.ece.uiuc.edu/ece390/archive/archive-f2000/mp/mp4/anti.html
http://www.mat.univie.ac.at/~kriegl/Skripten/CG/node35.html