中点線分アルゴリズム
スキャンラインの材料とすべく
「コンピュータグラフィックス 理論と実践」を参照して線分アルゴリズムを書いてみた。
中点線分アルゴリズムはBresenhamアルゴリズムの亜種で
右と右上のピクセルのどちらを選択するかの判断を
両ピクセルの中点位置で線分の陰関数を解いて判定する。
(x0, y0)から(x1, y1)に線分をひくとして
dx=x1-x0
dy=y1-y0
とすると
本に載っているのは、
dx > dy && dx > 0 && dy > 0 の時のみで他の場合は
対称性を利用して同様に書けると書いてある。
要するに以下の8パターンが必用になる。
- dx > dy && dx > 0 && dy > 0
- dx > dy && dx > 0 && dy < 0
- dx > dy && dx < 0 && dy > 0
- dx > dy && dx < 0 && dy < 0
- dx < dy && dx > 0 && dy > 0
- dx < dy && dx > 0 && dy < 0
- dx < dy && dx < 0 && dy > 0
- dx < dy && dx < 0 && dy < 0
始点と終点を入れ替えるなどの方法を取ると2パターンかそこら4パターンに減らせるのだけど、ポリラインに描画パターンを適用するなどの使い方をするときに都合が悪くなるような気がするのでベタに8パターン。
しかし、まじめに8パターン書くのは避けたいのでtemplateを乱用してみた。
でも、短くはならなかった。
これをベースにアンチエイリアス付きの線分描画アルゴリズムである
Gupta-SproullアルゴリズムとかWu's lineアルゴリズムに進む。
#ifndef _DRAW_LINE_H #define _DRAW_LINE_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; typedef unsigned long DWORD; DWORD white= 0xFFFFFFFF; DWORD red= 0xFFFF0000; DWORD green= 0xFF00FF00; DWORD blue= 0xFF0000FF; DWORD cyan= 0xFF00FFFF; DWORD magenta=0xFFFF00FF; DWORD yellow= 0xFFFFFF00; DWORD black= 0xFF000000; DWORD gray= 0xFF7F7F7F; enum AXIS { AXIS_X , AXIS_Y }; struct Vector2 { int x; int y; Vector2(int _x, int _y) : x(_x), y(_y) {} }; struct FCounter { int couner; FCounter(int _counter) : couner(abs(_counter)){} bool isEnd() { return couner<=0; } void increment() { --couner; } }; struct Locator { unsigned char *pixel; int pixelBytes; int rowStride; Locator(unsigned char *_pixel, int _pixelBytes, int _rowStride) : pixel(_pixel), pixelBytes(_pixelBytes), rowStride(_rowStride) {} void set(DWORD color){ *(DWORD*)pixel=color; } template<AXIS axis> void increment(); template<AXIS axis> void decrement(); }; template<> void Locator::increment<AXIS_X>(){ pixel+=pixelBytes; } template<> void Locator::increment<AXIS_Y>(){ pixel+=rowStride; } template<> void Locator::decrement<AXIS_X>(){ pixel-=pixelBytes; } template<> void Locator::decrement<AXIS_Y>(){ pixel-=rowStride; } template<int CHANNELS> struct Image { unsigned char *raw; int w; int h; Image(unsigned char *_raw, int _w, int _h) : raw(_raw), w(_w), h(_h) {} void setPixel(const Vector2 &point, DWORD color) { if(point.x<0 || point.y<0 || point.x>=w || point.y>=h){ return; } unsigned char *pixel = &raw[((point.y * w) + point.x) * CHANNELS]; *(DWORD*)pixel=color; } unsigned char *get(const Vector2 &point) { return &raw[((point.y * w) + point.x) * CHANNELS]; } Locator getLocation(const Vector2 &point) { return Locator(get(point), CHANNELS, CHANNELS * w); } }; //! simple void simpleLine(Image<4> &image , const Vector2 &from , const Vector2 &to) { int step=from.x < to.x ? +1 : -1; for(int x=from.x; x!=to.x; x+=step) { image.setPixel( Vector2( x , static_cast<int>( std::floor( static_cast<double>(to.y-from.y) / static_cast<double>(to.x-from.x) * (x-from.x) + from.y + 0.5))) , white); } } //! Digital Differencial Analyzer algorithm void DDALine(Image<4> &image , const Vector2 &from , const Vector2 &to) { int step=from.x < to.x ? +1 : -1; double m =static_cast<double>(to.y-from.y) / static_cast<double>(to.x-from.x) * static_cast<double>(step); double y=static_cast<double>(from.y); for(int x=from.x; x!=to.x; x+=step, y+=m) { image.setPixel(Vector2(x, y), white); } } //! MidPoint algorithm template<class COUNTER , class INCREMENT_MAJOR, class INCREMENT_MINOR, class ADVANCE_MINOR> void midPointLine_(Locator pointer , int d, int incMajor, int incMinor , COUNTER counter , INCREMENT_MAJOR incrementMajor , INCREMENT_MINOR incrementMinor, ADVANCE_MINOR determine , DWORD color) { // start pointer.set(color); // loop for(; !counter.isEnd(); counter.increment()) { if(determine(d)){ d+=incMinor; incrementMinor(pointer); incrementMajor(pointer); } else{ d+=incMajor; incrementMajor(pointer); } pointer.set(color); } } void midPointLine(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; } int cmpdxdy=abs(dx)-abs(dy); if(cmpdxdy>=0){ // MAJOR X if(dx>0){ if(dy>0){ // [0] dx > dy && dx>0 && dy>0 midPointLine_( image.getLocation(from) , 2*(dy)-(dx), 2*(dy), 2*((dy)-(dx)) , 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 midPointLine_( image.getLocation(from) , 2*(dy)-(-dx), 2*(dy), 2*((dy)-(-dx)) , 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 midPointLine_( image.getLocation(from) , 2*(-dy)-(dx), 2*(-dy), 2*((-dy)-(dx)) , 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 midPointLine_( image.getLocation(from) , 2*(-dy)-(-dx), 2*(-dy), 2*((-dy)-(-dx)) , 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 midPointLine_( image.getLocation(from) , 2*(dx)-(dy), 2*(dx), 2*((dx)-(dy)) , 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 midPointLine_( image.getLocation(from) , 2*(-dx)-(dy), 2*(-dx), 2*((-dx)-(dy)) , 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 midPointLine_( image.getLocation(from) , 2*(dx)-(-dy), 2*(dx), 2*((dx)-(-dy)) , FCounter(dy) , lmd::bind(&Locator::increment<AXIS_Y>, lmd::_1) , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1) , (lmd::_1 < 0) , yellow ); } else{ // [7] dx < dy && dx<0 && dy<0 midPointLine_( image.getLocation(from) , 2*(-dx)-(-dy), 2*(-dx), 2*((-dx)-(-dy)) , FCounter(dy) , lmd::bind(&Locator::decrement<AXIS_Y>, lmd::_1) , lmd::bind(&Locator::decrement<AXIS_X>, lmd::_1) , (lmd::_1 > 0) , gray ); } } } } void drawLine(Image<4> &image , const Vector2 &from , const Vector2 &to) { //simpleLine(image, from, to); //DDALine(image, from, to); midPointLine(image, from, to); } #endif // _DRAW_LINE_H
