OpenGL入門2——曲線生成アルゴリズム
7386 ワード
線生成アルゴリズム>
一、DDAアルゴリズム
デジタル微分分析器(digital differential anlyzer,DDA)法は線分走査変換アルゴリズムである.
線分の始点座標が(xstart,ystart)、終点座標が(xend,yend)であると仮定し、線分の傾きがmであり、水平方向の増分がdxであり、垂直方向の増分がdyである.
(1)、アルゴリズムの要約
1*、線分の2つのエンドポイントのピクセル位置を入力して、エンドポイントの位置間の水平と垂直の差はパラメータdx,dyに与えられます.
2*、x方向、y方向の増分であると判断し、どちらが大きいか(この方向の変化が速い)、dx、dyの絶対値が大きいかを決定するパラメータsteps(サイクル実行回数)の値.
3＊線分に沿って次の画素位置を生成するステップ毎に必要なオフセット量を決定し、画素位置(x 0,y 0)からステップステップステップを繰り返す.
ステップ毎のインクリメントの決定ルール:
dx絶対値がdyの絶対値より大きく、xstartがxendより小さい場合: x、y方向の増分値はそれぞれ1とmである.
dx絶対値がdyの絶対値より大きく、xstartがxendより大きい場合: x、y方向の増分値はそれぞれ−1と−mである.
dx絶対値がdyの絶対値より小さく、xstartがxendより小さい場合: x、y方向の増分値はそれぞれ1/mと1である.
dx絶対値がdyの絶対値より小さい場合、xstartはxendより大きい: x、y方向の増分値はそれぞれ−1／mと−1である.
(2)、アルゴリズムの説明
DDA法による画素位置の計算は,直線方程式を用いて直接計算したものよりも速い.しかし、浮動小数点増分の連続的な重ね合わせにおいて、整誤差の蓄積により、長い線分に対して計算された画素位置は実際の線分から逸脱し、この過程での整動作と浮動小数点演算はまだ十分に時間がかかります.デルタmと1/mを整数と小数に分離することにより、すべての計算を整数動作に簡略化してDDAアルゴリズムの性能を改善することができる.
二、Bresenham線画のアルゴリズム
Bresenham線画アルゴリズムはBresenhamによって提案された正確で効果的なラスター線生成アルゴリズムであり、このアルゴリズムはインクリメンタル整数のみを用いて計算される.このアルゴリズムはまた、円および他の曲線を示すためにも使用できる.
このアルゴリズムは、沿線経路方向のサンプリング位置Xk＋1において、DlowerとDupperを使用して、2つの画素と数学的な線経路の偏差を識別し、2つの画素のうちどちらがより線経路に近いかを決定し、その後、より線経路に近い画素を描画する.
(1)、アルゴリズムの要約
|m|<1時のBresenham線画のアルゴリズム:
1*、線分の2つの端点を入力し、左端点を(x 0,y 0)に保存します.
2*、(x 0,y 0)をフレームキャッシュに入れて、最初の点を描きます.
3*、定数dx、dy、2 dy、および2 dy-2 dxを計算し、決定パラメータの最初の値を得る:p 0=2 dy-dx;
4*、k=0から、沿線の各Xkにおいて、検査を行います.
Pk<0の場合、次の描画点が(Xk＋1、Yk)であり、Pk＋1=Pk+2 dyである.
そうでなければ、次の描画点は(Xk＋1、Yk＋1)であり、Pk＋1＝Pk＋2 dy−2 dxである.
5*、ステップ4を繰り返し、dx-1回を共有します.
(2)、アルゴリズム実装(傾き0＜k＜1.0)
＜円生成アルゴリズム＞
三、中点円画のアルゴリズム
(1)、背景
デカルト座標系または極座標系の円方程式と円の対称性を利用して円を描くのは、やはり効率が悪く、時間がかかります.デカルト座標系の円方程式を使って円を描くためには、乗算と平和平方根演算が必要です.極座標の円方程式を使って円を描くには、乗算と三角演算が必要です.これらの演算は時間がかかります.
ラスターシステムのBresenham線画アルゴリズムを円画アルゴリズムに移植し、画素と円の距離の二乗を比較することによって平方根演算を回避することができる.
しかし、より優れたアルゴリズム:中点描画円アルゴリズムは、二乗演算をせずに直接距離を比較することができる.このアルゴリズムの基本的な考えは、中心が円境界内かそれとも外側かを決定するために、2つの画素間の中間位置を検査することである.この方法は他の円錐曲線により容易に適用され,整数円半径に対して,中間点法はBresenham円描画アルゴリズムと同じ画素位置を生成する.また、中点検査を行う場合は、任意の円錐断面曲線に沿って決定される画素位置は、その誤差が画素間隔の1/2以内に制限されます.
(2)、概要
中点描画円アルゴリズムのステップ:
1*、円半径rと円心(Xc,Yc)を入力し、円周(円心が原点)上の最初の点を得る.(x 0,y 0)=(0,r).
2*、決定パラメータの初期値を計算します.p 0=5/4-rです.
3*、各Xk位置で、k=0から次のテストを完了します.もしPk<0、円心が(0,0)の円の次の点が(Xk+1,Yk)で、Pk+1=Pk+2 Xk+1+1でなければ、円の次の点が(Xk+1,Yk-1)で、Pk+1=Pk+2 X+1 + 1-2 Yk+1は、2 Xk+1=2 Xk+2、2 Yk+1=2 Yk-2です.
4*、他の7つの八分円の中の対称点を決定します.
5*、算出されたピクセル位置(x,y)ごとに、円心(Xc,Yc)の円パスに移動し、座標値を描きます.x=x+Xc,y=y+Yc;
6*、x>=yまで、ステップ3からステップ5を繰り返します.
(3)、アルゴリズムの説明
四、中点楕円アルゴリズム
(1)、アルゴリズムの要約
中点楕円アルゴリズムのステップ:
1*、楕円のx軸半径rx、y軸半径ryと楕円中心(xc、yc)を入力して、楕円(中心が原点)の上の最初の点を得ます.(x 0,y 0)=(0,ry)
2*、計算エリア1における決定パラメータの初期値:p 10=ry^2 - rx^2*ry+(rx^2)/4
3*、エリア1の各xk位置で、k=0から次のテストを行います.p 1 k<0なら、中心に沿って(0,0)の楕円の次の点は(xk+1, yk)そして、P 1 k+1=p 1 k+2*ry^2*xk+1+ry^2でなければ、楕円形の次の点に沿って(xk+1,yk-1)で、p 1 k+1=p 1 k+2*ry^2*x+1-2*rx^2*2*kk+1+1 ry^2で、2*ry^2 2***rx^2*yk+1=2*rx^2*kk-2*rx^2まで、2*ry^2*x==2*ry^2*yまでです.
4*、領域1で計算された最後の点(x 0,y 0)を使って、領域2のパラメータの初期値:p 20=ry^2(x 0+1/2)^2+rx^2*(y 0-1)^2-rx^2*ry^2を計算します.
5*、領域2の各y k位置において、k=0から以下のテストを行います.p 2 k>0の場合、中心に沿って(0,0)の楕円の次の点は(xk,yk-1)で、p 2 k+1=p 2 k-2 rx^2*k+rx^2、そうでなければ、楕円に沿った次の点は(x+1 k+1、k+1、p+1、k+1、p+2 k+1、p+1、k+1、p+1、p+2 k+1、k+2 x+1、p+1、p+1、k+1、p+1、k+1、k+2、p+2、p+2、p+1、k+1、p+2、p+2、p+2計算します.y=0まで
6*、他の3つの象限の中の対称点を確定します.
7*、計算した各ピクセル位置(x,y)を中心の楕円軌道に移動し、座標値に従って点を描きます.x=x+xc、y=y+yc.
(2)、アルゴリズムの説明
一、DDAアルゴリズム
デジタル微分分析器(digital differential anlyzer,DDA)法は線分走査変換アルゴリズムである.
線分の始点座標が(xstart,ystart)、終点座標が(xend,yend)であると仮定し、線分の傾きがmであり、水平方向の増分がdxであり、垂直方向の増分がdyである.
(1)、アルゴリズムの要約
1*、線分の2つのエンドポイントのピクセル位置を入力して、エンドポイントの位置間の水平と垂直の差はパラメータdx,dyに与えられます.
2*、x方向、y方向の増分であると判断し、どちらが大きいか(この方向の変化が速い)、dx、dyの絶対値が大きいかを決定するパラメータsteps(サイクル実行回数)の値.
3＊線分に沿って次の画素位置を生成するステップ毎に必要なオフセット量を決定し、画素位置(x 0,y 0)からステップステップステップを繰り返す.
ステップ毎のインクリメントの決定ルール:
dx絶対値がdyの絶対値より大きく、xstartがxendより小さい場合: x、y方向の増分値はそれぞれ1とmである.
dx絶対値がdyの絶対値より大きく、xstartがxendより大きい場合: x、y方向の増分値はそれぞれ−1と−mである.
dx絶対値がdyの絶対値より小さく、xstartがxendより小さい場合: x、y方向の増分値はそれぞれ1/mと1である.
dx絶対値がdyの絶対値より小さい場合、xstartはxendより大きい: x、y方向の増分値はそれぞれ−1／mと−1である.
(2)、アルゴリズムの説明
#include < stdlib.h>
#include < math.h >
inline int round(const float a){ return (int)(a+0.5f);};
void lineDDA( int x0, int y0, int xEnd, int yEnd)
{
int dx = xEnd - x0;
int dy = yEnd - y0;
int steps, k;
float xIncrement, yIncrement, x = x0, y = y0;
(int)fabs((float)dx) > (int)fabs((float)dy) ? steps = fabs((float)dx) : steps = fabs((float)dy);
xIncrement = float(dx) / float(steps);
yIncrement = float(dy) / float(steps);
setPixel( round(x), round(y));// ， 。
for( k=0; k<steps; k++)
{
x += xIncrement;
y += yIncrement;
setPixel(round(x), round(y));
}
return ;
}DDA法による画素位置の計算は,直線方程式を用いて直接計算したものよりも速い.しかし、浮動小数点増分の連続的な重ね合わせにおいて、整誤差の蓄積により、長い線分に対して計算された画素位置は実際の線分から逸脱し、この過程での整動作と浮動小数点演算はまだ十分に時間がかかります.デルタmと1/mを整数と小数に分離することにより、すべての計算を整数動作に簡略化してDDAアルゴリズムの性能を改善することができる.
二、Bresenham線画のアルゴリズム
Bresenham線画アルゴリズムはBresenhamによって提案された正確で効果的なラスター線生成アルゴリズムであり、このアルゴリズムはインクリメンタル整数のみを用いて計算される.このアルゴリズムはまた、円および他の曲線を示すためにも使用できる.
このアルゴリズムは、沿線経路方向のサンプリング位置Xk＋1において、DlowerとDupperを使用して、2つの画素と数学的な線経路の偏差を識別し、2つの画素のうちどちらがより線経路に近いかを決定し、その後、より線経路に近い画素を描画する.
(1)、アルゴリズムの要約
|m|<1時のBresenham線画のアルゴリズム:
1*、線分の2つの端点を入力し、左端点を(x 0,y 0)に保存します.
2*、(x 0,y 0)をフレームキャッシュに入れて、最初の点を描きます.
3*、定数dx、dy、2 dy、および2 dy-2 dxを計算し、決定パラメータの最初の値を得る:p 0=2 dy-dx;
4*、k=0から、沿線の各Xkにおいて、検査を行います.
Pk<0の場合、次の描画点が(Xk＋1、Yk)であり、Pk＋1=Pk+2 dyである.
そうでなければ、次の描画点は(Xk＋1、Yk＋1)であり、Pk＋1＝Pk＋2 dy−2 dxである.
5*、ステップ4を繰り返し、dx-1回を共有します.
(2)、アルゴリズム実装(傾き0＜k＜1.0)
#include <stdlib.h>
#include <math.h>
/* Bresenham line-drawing procedure for |m| < 1.0 */
void lineBres(int x0, int y0, int xEnd, int yEnd)
{
int dx = fabs(xEnd - x0), dy = fabs(yEnd - y0);
int p = 2 * dy - dx ;
int twoDy = 2 * dy, twoDyMinusDx = 2 * (dy - dx);
int x, y;
/* Determine which endpoint to use as start position .*/
if(x0 > xEnd)
{
x = xEnd;
y = yEnd;
xEnd = x0;
}
else
{
x = x0;
y = y0;
}
setPixel(x, y);
while( x <xEnd )
{
x++;
if( p<0 )
p += twoDy;
else
{
y++;
p += twoDyMinusDx;
}
setPixel(x, y);
}
}＜円生成アルゴリズム＞
三、中点円画のアルゴリズム
(1)、背景
デカルト座標系または極座標系の円方程式と円の対称性を利用して円を描くのは、やはり効率が悪く、時間がかかります.デカルト座標系の円方程式を使って円を描くためには、乗算と平和平方根演算が必要です.極座標の円方程式を使って円を描くには、乗算と三角演算が必要です.これらの演算は時間がかかります.
ラスターシステムのBresenham線画アルゴリズムを円画アルゴリズムに移植し、画素と円の距離の二乗を比較することによって平方根演算を回避することができる.
しかし、より優れたアルゴリズム:中点描画円アルゴリズムは、二乗演算をせずに直接距離を比較することができる.このアルゴリズムの基本的な考えは、中心が円境界内かそれとも外側かを決定するために、2つの画素間の中間位置を検査することである.この方法は他の円錐曲線により容易に適用され,整数円半径に対して,中間点法はBresenham円描画アルゴリズムと同じ画素位置を生成する.また、中点検査を行う場合は、任意の円錐断面曲線に沿って決定される画素位置は、その誤差が画素間隔の1/2以内に制限されます.
(2)、概要
中点描画円アルゴリズムのステップ:
1*、円半径rと円心(Xc,Yc)を入力し、円周(円心が原点)上の最初の点を得る.(x 0,y 0)=(0,r).
2*、決定パラメータの初期値を計算します.p 0=5/4-rです.
3*、各Xk位置で、k=0から次のテストを完了します.もしPk<0、円心が(0,0)の円の次の点が(Xk+1,Yk)で、Pk+1=Pk+2 Xk+1+1でなければ、円の次の点が(Xk+1,Yk-1)で、Pk+1=Pk+2 X+1 + 1-2 Yk+1は、2 Xk+1=2 Xk+2、2 Yk+1=2 Yk-2です.
4*、他の7つの八分円の中の対称点を決定します.
5*、算出されたピクセル位置(x,y)ごとに、円心(Xc,Yc)の円パスに移動し、座標値を描きます.x=x+Xc,y=y+Yc;
6*、x>=yまで、ステップ3からステップ5を繰り返します.
(3)、アルゴリズムの説明
#include <GL/glut.h>
class screenPt
{
private:
GLint x, y;
public:
screenPt()
{
x = y = 0;
}
void setCoords( GLint xCoordValue, GLint yCoordValue)
{
x = xCoordValue;
y = yCoordValue;
}
GLint getx() const
{
return x;
}
GLint gety() const
{
return y;
}
void incrementx()
{
x++;
}
void decrementy()
{
y--;
}
};
void setPixel( GLint xCoord, GLint yCoord)
{
glBegin(GL_POINTS);
glVertex2i(xCoord, yCoord);
glEnd();
}
void circleMidpoint(GLint xc, GLint yc, GLint radius)
{
screenPt circPt;
GLint p = 1 - radius;
circPt.setCoords(0, radius);
void circlePlotPoints( GLint , GLint , screenPt);
circlePlotPoints(xc, yc, circPt);
while(circPt.getx() < circPt.gety() )
{
circPt.incrementx();
if( p<0 )
p += 2 * circPt.getx() + 1;
else
{
circPt.decrementy();
p += 2 * ( circPt.getx() - circPt.gety() ) +1;
}
circlePlotPoints(xc, yc, circPt);
}
}四、中点楕円アルゴリズム
(1)、アルゴリズムの要約
中点楕円アルゴリズムのステップ:
1*、楕円のx軸半径rx、y軸半径ryと楕円中心(xc、yc)を入力して、楕円(中心が原点)の上の最初の点を得ます.(x 0,y 0)=(0,ry)
2*、計算エリア1における決定パラメータの初期値:p 10=ry^2 - rx^2*ry+(rx^2)/4
3*、エリア1の各xk位置で、k=0から次のテストを行います.p 1 k<0なら、中心に沿って(0,0)の楕円の次の点は(xk+1, yk)そして、P 1 k+1=p 1 k+2*ry^2*xk+1+ry^2でなければ、楕円形の次の点に沿って(xk+1,yk-1)で、p 1 k+1=p 1 k+2*ry^2*x+1-2*rx^2*2*kk+1+1 ry^2で、2*ry^2 2***rx^2*yk+1=2*rx^2*kk-2*rx^2まで、2*ry^2*x==2*ry^2*yまでです.
4*、領域1で計算された最後の点(x 0,y 0)を使って、領域2のパラメータの初期値:p 20=ry^2(x 0+1/2)^2+rx^2*(y 0-1)^2-rx^2*ry^2を計算します.
5*、領域2の各y k位置において、k=0から以下のテストを行います.p 2 k>0の場合、中心に沿って(0,0)の楕円の次の点は(xk,yk-1)で、p 2 k+1=p 2 k-2 rx^2*k+rx^2、そうでなければ、楕円に沿った次の点は(x+1 k+1、k+1、p+1、k+1、p+2 k+1、p+1、k+1、p+1、p+2 k+1、k+2 x+1、p+1、p+1、k+1、p+1、k+1、k+2、p+2、p+2、p+1、k+1、p+2、p+2、p+2計算します.y=0まで
6*、他の3つの象限の中の対称点を確定します.
7*、計算した各ピクセル位置(x,y)を中心の楕円軌道に移動し、座標値に従って点を描きます.x=x+xc、y=y+yc.
(2)、アルゴリズムの説明
inline int round( const float a){ return int (a + 0.5); }
void ellipseMidpoint( int xCenter, int yCenter, int Rx, int Ry)
{
int Rx2 = Rx * Rx;
int Ry2 = Ry * Ry;
int twoRx2 = 2 * Rx2;
int twoRy2 = 2 * Ry2;
int p;
int x = 0;
int y = Ry;
int px = 0;
int py = twoRx2 * y;
void ellipsePlotPoints( int, int, int, int);
ellipsePlotPoints( xCenter, yCenter, x, y);
/*Region 1*/
p = round(Ry2 - (Rx2 * Ry) + (0.25 * Rx2));
while(px <py)
{
x++;
px += twoRy2;
if( p<0 )
p += Ry2 +px;
else
{
y--;
py -= twoRx2;
p += Ry2 +px - py;
}
ellipsePlotPoints(xCenter, yCenter, x, y);
}
/*Region 2*/
p = round(Ry2 * (x+0.5) * (x+0.5) + Rx2 * (y-1)*(y-1) - Rx2 * Ry2);
while( y>0 )
{
y--;
py -= twoRx2;
if( p>0 )
p += Rx2 - py;
else
{
x++;
px += twoRy2;
p += Rx2 - py + px;
}
ellipsePlotPoints(xCenter, yCenter, x, y);
}
}
void ellipsePlotPoints(int xCenter, int yCenter, int x, int y)
{
setPixel(xCenter + x, yCenter + y);
setPixel(xCenter - x, yCenter + y);
setPixel(xCenter + x, yCenter - y);
setPixel(xCenter - x, yCenter - y);
}