呉暁林のラインアルゴリズム

Xiaolin Wu のラインアルゴリズムは、ラインアンチエイリアシングのアルゴリズムです。

アンチエイリアシング技術

Xiaolin Wu のラインアルゴリズムは、1991 年 7 月号のComputer Graphicsの記事「An Efficient Antialiasing Technique」と、1992 年 6 月号のDr. Dobb's Journalの記事「Fast Antialiasing」で紹介されました。

Bresenham のアルゴリズムは、非常に高速に線を描画しますが、アンチエイリアシングは実行しません。また、線の終点がピクセルグリッドの整数点に正確に一致しない場合は処理できません。線をアンチエイリアシングする単純な方法では、非常に長い時間がかかります。Wu のアルゴリズムは比較的高速ですが、Bresenham のアルゴリズムよりは遅いです。このアルゴリズムは、線をまたぐピクセルのペアを描画し、各ピクセルを線からの距離に応じて色付けします。線の端のピクセルは個別に処理されます。1 ピクセル未満の線は、特別なケースとして処理されます。

円描画アルゴリズムの拡張は、Xiaolin Wu によってGraphics Gems II という本で発表されました。線描画アルゴリズムが Bresenham の線描画アルゴリズムの代わりであるのと同様に、円描画アルゴリズムは Bresenham の円描画アルゴリズムの代わりです。

アルゴリズム

関数plot ( x , y , c )は    
    （x 、y ）のピクセルを明るさc （0≤c≤1 ）でプロットする              

// x の整数部分
関数ipart ( x )は  
    戻り階( x ) 

関数round ( x )は  
    ipart ( x + 0.5 )を返す   

// x の小数部
関数fpart ( x )は  
    x を返す- ipart ( x )   

関数rfpart ( x )は  
    1 - fpart ( x )を返す   

関数drawLine ( x0 , y0 , x1 , y1 )は  
    ブール値の急勾配:= abs ( y1 - y0 ) > abs ( x1 - x0 )         
    
    急勾配の場合は  
        スワップ( x0 , y0 ) 
        スワップ( x1 , y1 ) 
    終了の場合 
    x0 > x1ならば    
        スワップ( x0 、x1 ) 
        スワップ( y0 , y1 ) 
    終了の場合 
    
    dx := x1 - x0    
    dy := y1 - y0    

    dx == 0.0の場合    
        勾配:= 1.0  
    それ以外
        勾配:= dy / dx    
    終了の場合 

    // 最初のエンドポイントを処理する
    xend :=ラウンド( x0 )  
    yend := y0 +勾配* ( xend - x0 )        
    xギャップ:= rfpart ( x0 + 0.5 )    
    xpxl1 := xend // これはメインループで使用されます   
    ypxl1 := ipart (円)  
    急勾配の場合は  
        プロット( ypxl1 、xpxl1 、rfpart ( yend ) * xgap )      
        プロット( ypxl1 + 1 , xpxl1 , fpart ( yend ) * xgap )     
    それ以外
        プロット( xpxl1 、ypxl1 、rfpart ( yend ) * xgap )      
        プロット( xpxl1 , ypxl1 + 1 , fpart ( yend ) * xgap )     
    終了の場合 
    intery := yend + gradient // メインループの最初のy交差     
    
    // 2番目のエンドポイントを処理する
    xend :=ラウンド( x1 )  
    yend := y1 +勾配* ( xend - x1 )        
    xギャップ:= fpart ( x1 + 0.5 )    
    xpxl2 := xend //これはメインループで使用されます   
    ypxl2 := ipart (円)  
    急勾配の場合は  
        プロット( ypxl2 、xpxl2 、rfpart ( yend ) * xgap )      
        プロット( ypxl2 + 1 , xpxl2 , fpart ( yend ) * xgap )     
    それ以外
        プロット( xpxl2 、ypxl2 、rfpart ( yend ) * xgap )     
        プロット( xpxl2 , ypxl2 + 1 , fpart ( yend ) * xgap )    
    終了の場合 
    
    // メインループ
    急勾配の場合は  
        xpxl1 + 1からxpxl2 - 1までのxに対して          
           始める
                プロット( ipart ( intery ) 、x 、rfpart ( intery ))    
                プロット( ipart ( intery ) + 1 , x , fpart ( intery ))   
                中間値:=中間値+勾配    
           終わり
    それ以外
        xpxl1 + 1からxpxl2 - 1までのxに対して          
           始める
                プロット( x 、ipart ( intery ) 、rfpart ( intery ))   
                プロット( x 、ipart ( intery ) + 1 、fpart ( intery ))  
                中間値:=中間値+勾配    
           終わり
    終了の場合 
終了関数

参考文献

マイケル・アブラッシュ（1992年6月）。「高速アンチエイリアス (列)」。ドブ博士の日記。17 (6):139(7)。
Wu, Xiaolin ( 1991年 7 月)。「効率的なアンチエイリアシング手法」。ACM SIGGRAPH コンピュータグラフィックス。25 (4): 143–152。doi : 10.1145 /127719.122734。ISBN 0-89791-436-8。
ウー、シャオリン（1991）。「高速アンチエイリアスサークル生成」。ジェームズ・アーヴォ編著。グラフィックジェム II。サンフランシスコ：モーガン・カウフマン。 446–450ページ。ISBN 0-12-064480-0。

外部リンク

呉暁林のホームページ
マクマスター大学の Xiaolin Wu のホームページ