ラスタライズスレ

yahoo翻訳→てきとう修正完了

元スレ

ちなみに、↑より前に、このスレで、この手法を発見する前のスレ主がが苦悩している

It's quite surprising that the most elementary rendering operations, like rasterization, are so little documented.
ラスタライゼーションのような、最も基本のレンダリング操作が、ほとんど文書化されないことは、全く驚くべきです。

Graphics cards take care of most of this, so people have forgotten how it actually works.
グラフィックスカードがほとんどの面倒を見るので、実際にどのようにレンダリングされるかは、忘れ去られました。

But there are many reasons left why understanding the inner workings of the graphics pipeline is still useful.
しかし、グラフィックスパイプラインの内部の働きを理解することが、まだ役に立つ、多くの理由が残っています。

Not only for software rendering, but for any situation where this type of operations is required.
ソフトウェアレンダリングのためにだけでなく、この種類の操作が必要である、どんな状況でも。

Knowledge of these algorithm simply make you a better graphics programmer.
これらのアルゴリズムの知識は、容易にあなたをより良いグラフィックスプログラマーにする。

Today I present you the theory and implementation of an advanced rasterizer.
今回、あなたに先進のラスタライザーの理論と実践を贈ります。

It is advanced in the sense that it has many nice properties the classical scanline conversion algorithm does not have.
先進のラスタライザーは古典的な走査線変換アルゴリズムにはない、多くの素晴らしい特性があるという点で、進んでいます。

The main problem with the old algorithm is that it's hard to process pixels in parallel.
古いアルゴリズムの主な問題は、平行にピクセルを処理するのは難しいということです。

It identifies filled scanlines, but this is only suited for processing one pixel at a time.
古いアルゴリズムでは塗りつぶされた走査線を確認します、しかし、これは一度に1ピクセルを処理することに適しているだけです。

A much more efficient approach is to process 2x2 pixels together.
ずっと効果的なアプローチは、一緒に2x2ピクセルを処理することです。

These are called quads.
これらは、クアッドと呼ばれています。

By sharing some setup cost per quad, and using advanced parallel instructions, this results in a significant speedup.
クアッドごとの若干のセットアップコストを共有し、進化した並列命令を使うことによって、大幅なスピードアップが可能です。

Some of the current graphics hardware also uses quad pixel pipelines.
現在のグラフィックスハードウェアのいくつかも、クアッドピクセルパイプラインを使っています。

Our starting point is the half-space function approach.
我々の出発点は、半空間関数を使用したアプローチです。

Before I go into details, all you have to know is that a half-space function is positive on one side of a line, and negative on the other.
私が詳述する前に、あなたが知っていなければならないことは、半空間関数が線の一方で正で、他方で負であるということです。

So it splits the screen in half, hence the name.
スクリーンを半分に割ることが、半空間関数の名前の由来です。

Here's a small illustration of it, where the edges of a triangle each split the screen in a positive and negative part:
小さな具体例があります。三角形のエッジは、それぞれ、スクリーンを正と負の部分に裂きました:

half-space.png.
半分-space.png.

Locations where all three half-space functions are positive define the inside of the triangle.
すべての三つ半空間関数が正である場所は、三角形の内部ということになります。

When a half-edge function is zero, we're on an edge.
半空間関数がゼロであるときは、エッジの上です。

When any of them is negative, we are outside the triangle.
全て負のときは、三角形の外側です。

So this can be used for rasterization.
それで、これをラスタライゼーションのために使うことができます。

If we can find formulas for the half-space functions, and evaluate them for each pixel location, we know which pixels need to be filled.
我々が半空間関数の公式を見つけることができて、ピクセル位置ごとにそれらを評価できるなら、我々はどのピクセルが塗りつぶされるべきか分かります。

So what formula is positive on one side of a line and negative on the other?
では、どんな公式で、線の一方で正で、他の上で負になるでしょうか?

Surprisingly, the equation of a line is exactly what we're looking for.
驚くべきことに、線の方程式は、まさに我々が探しているものです。

For a segment with starting coordinates (x1, y1) and end coordinates (x2, y2), the equation is:
始点(x1、y1)、終点(x2、y2)としたとき、方程式は次のようになります。

(x2 - x1) * (y - y1) - (y2 - y1) * (x - x1) = 0

You can easily verify that this equation is true for any point (x, y) on this line (for example the start and end points themselves).
あなたは、この方程式が、線上のどんな点(x、y)についても成り立つことを、簡単に確かめることができます。(たとえば始点と終点が同じとき、など)

But the left hand side also behaves perfectly as a half-space fuction.
しかし、左側も半空間関数として完全にふるまいます。

It is positive for (x, y) coordinates on one side, and negative on the other.
ある側で、(x、y)座標が正、他方で負です。

It's zero on the line itself, which effectively defines the line in the above equation.
線自体の上ではゼロです。そして、それは上記の方程式で効果的に線を定めます。

Verifying this behaviour is left as an excercise for the reader.
このふるまいを確かめることは、読者のためのexcerciseとして残されます。

Let's write some code!
いくらかのコードを書きましょう!


コード略


This is the simplest working implementation of the half-space functions algorithm.
これは、半空間関数のアルゴリズムで最も単純な実装です。

Before I continue to explain how it can be improved, there are a few things to note.
これがどのように改善されるか、の説明をし続ける前に、いくつか注意する点があります。

It would be possible to scan the whole screen, to see which pixels are inside the triangle, but this is of course a waste of time.
どのピクセルが三角形内部にあるかを知るために、スクリーン上全てを調べることは可能です、しかし、これはもちろん時間の無駄です。

Therefore only the smallest rectangle surrounding the triangle is scanned.
したがって、三角形を囲んでいる最も小さな長方形だけ、調べます。

You might also have noticed that I swapped some components in the formula.
あなたは、私が公式の若干の構成要素を交換したと、気がついたかもしれません。

This is because in screen coordinates, the y-axis points downward.
これは、スクリーン座標で、y軸が下を指すからです。

It is also very important that the triangle's vertices are in counter-clockwise order.
三角形の頂点が反時計回りの順序であることは、非常に重要です。

This makes sure that all the positive sides of the half-spaces point inside the triangle.
これにより、半空間のすべての正の側は、三角形の中を示す、とういことが確認できます。

Unfortunately, this implementation isn't fast at all.
残念なことに、この実装は、まったく速くありません。

For every pixel, six multiplications and no less than fifteen subtractions are required.
あらゆるピクセルのために、6つの乗算と15の引き算が必要です。

But don't worry, this can be optimized greatly.
しかし、心配しないでください、これは大いに最適化することができます。

Per horizontal line that we scan, only the x component in the formula changes.
スキャンする水平線ごとでは、公式の中の変化は、xの値だけです。

For the first edge, this means only (y1 - y2) gets added to the half-edge function value of the previous pixel.
最初のエッジから、ただ(y1 - y2)の増分が、前のピクセルの半空間関数の値に加えられます。


※自分用要約

(x1 - x2) * (y - y1) - (y1 - y2) * (x - x1)
= dx12 *  (y - y1) - dy12 * (x - x1)        ∵dx12=(x1-x2),  dy12=(y1-y2)
= (dy12 * x1 - dx12 * y1) + (dx12 * y - dy12 * x)

ここで、x = minx,  y = miny とし、スキャンごとに増分(dy12)を加え、xを1ピクセル進むごとに増分(dx12)を加える。

三角形は
(dy12 * x1 - dx12 * y1) + (dx12 * miny - dy12 * minx) > 0
からスキャン開始され、この式を満たすとき塗りつぶされる

(dy12 * x1 - dx12 * y1) + (dx12 * maxy - dy12 * maxx) > 0
まで調べるとスキャン終了

詳しくは下のコード参照(略してるけど..)



That's just an addition and subtraction per pixel!
それは、ちょうどピクセル当たりの加算と減算です!

Furthermore, the vertex coordinates are 'constant' per triangle, so (y1 - y2) and all other pairs like this only have to be computed once per pixel.
さらにまた、そう、頂点座標は、三角形にごとに『一定です』、そして、(y1 - y2)や、このような他の全ての組は、ピクセルにつき一度計算されなければならないだけです。

Also for stepping in the y direction it's just an addition of a constant.
また、y方向に進むのは、ただの定数の追加ですみます。

Let's implement this:
これを実行しましょう:




コード略


The C1-C3 variables are the constant part of the half-edge equation and are not recomputed per pixel.
C1-C3変数は、半直線エッジ方程式の恒常的な部分で、ピクセルごとに再計算されません。

The Cy1-Cy3 variables determine the 'starting value' of the half-space functions at the top of the bounding rectangle.
Cy1-Cy3変数は、制限用長方形の最上位で半空間関数の『値を開始』を決めます。

And finally the Dx1-Dx3 variables are the start values per horizontal scan.
そして、最後に、Dx1-Dx3変数は、水平方向スキャンごとの開始値です。

Only these are incremented (actually decremented) with the delta values every pixel.
ピクセルごとに、微小値が増加(これらだけは増加します(実質的には減少)します

So testing whether a pixel is inside the triangle has become really cheap:
このようにして、ピクセルが三角形内部にあるかどうか調べることについて、本当にコストが安くなりました:

aside from some setup per horizontal line and per triangle that is negligible, just three subtractions and three compares for zero.
いくつかを除いて、水平線につき、そして、取るに足りない三角形、ちょうど3つの引き算と3につきセットアップは、ゼロのために匹敵します。

Ok, so this algorithm is starting to show its usefulness.
Ok、そう、このアルゴリズムは、その有用性を示し始めています。

But there still are some serious issues to solve.
しかし、まだ、解決するには、若干の深刻な問題が、あります。

Here's an actual image created using this code:
このコードを使用してつくられる実際のイメージは、ここにあります:

first_try.png.
first_try.png.

If it isn't clear that this is actually a car, here's the shaded reference image:
これが本当に車であることが明らかでないなら、陰影のついた参照イメージが以下に:

reference.png.
reference.png.

As you can see, there are many gaps between the polygons.
ご覧の通り、多角形間の多くのギャップが、あります。


The cause is twofold:
目的は二つの面を有します:

precision, and the fill convention.
精度と塗りつぶし方。

There are precision issues because floating-point numbers are quite limited.
浮動小数点数はすごく制限があるため、精度問題があります。

They have 24-bit of precision.
浮動小数は、24ビットの精度を持ちます。

If you look at the half-space function, you see that we do several subtractions and multiplications.
半空間関数では、我々はいくつかの引き算と乗算を行います。

That's the perfect recipe for precision problems.
それは、精度問題の完全なレシピです。

What most people would do in such situation is use double-precision floating-point numbers.
大部分の人々がそのような状況ですることは、倍精度浮動小数点数を使うことです。

While this will make the issue unnoticable, it isn't exactly perfect and also slower.
これは問題を注目させますが、一方、それは必ずしも完璧でないうえに、より遅いです。

The real solution might sound crazy:
本当の解決は、おかしく聞こえるかもしれません:

use integers!
整数を使ってください!

Integers have 32-bit of precision, and do not suffer from precision loss when subtracting.
整数は精度の32ビットを持って、引き算するとき、精度損失で苦しみません。

Instead of using a 'floating-point', we'll use fixed-point arithmetic to assure we get sub-pixel accuracy.
『浮動小数点』を使う代わりに、我々は我々がサブピクセル精度を得ることを保証する固定小数点演算を使います。

The second cause of the gaps is the fill convention.
隙間の第2の原因は、塗りつぶし方です。

The half-space functions can be positive or negative, but also zero.
半空間関数は正か、負か、または、ゼロであることができます。

In this case, the pixel is exactly on the edge.
この場合、ピクセルは確かにエッジ上にあります。

Until now, we've ignored this case and treated it as a pixel outside.
これまで、我々はこのケースを無視して、それを外のピクセルとみなしました。

We could treat it as inside, using = comparators, but this isn't correct either.
我々はそれを=比較演算子を使用して内側にあるとみなすことができました、しかし、これも正しくありません。

What will happen is that pixels on the edge between two triangles will be drawn twice.
起きることは、2つの三角形の間の端のピクセルが二回引かれるということです。

While this may sound more acceptable than gaps, it causes some serious artifacts for things like transparency and stenciling.
これが隙間より許容できるように感じるかもしれないが、それは透明度やステンシルのようなものに、いくつか重大な人工的な結果を引き起こします。

What we'll use here is a top-left fill convention, just like DirectX and OpenGL.
我々がここで使うものは、左上塗りつぶしで、ちょうどDirectXとOpenGLのような感じです。

This means that all edges which are on the left side of the triangle, or on a horizontal top, are treated as inside the triangle.
これは、三角形の左側または、水平上上部の全てのエッジか、三角形の内側として扱われます。

This convention assures that no gaps will occur, nor drawing the same pixel twice.
この慣例は隙間が起こらないことを保証します、また、二回同じピクセルを描きません。

Let's first see how we can detect whether an edge is 'top-left'.
最初に、我々がどのように、エッジが『左上』であるかどうか検出することができるかについて見ましょう。

For humans, it's really easy to recognise them.
人間にとっては、それらを認識することは、本当に簡単です。

Here are a few examples:
2、3の例は、ここにあります:

top-left.png.

I'm sure nobody really had a problem to identify the top-left edges himself, it's really simple.
私は誰もが左上端を特定するのに問題がなかったと確信します、それは本当に単純です。

But give yourself a minute to think about how you would detect this using code...
しかし、これをどうやってコードを使って決定するか、ちょっと考えてみてください。

Don't look before you tried it, but here's the answer:
答えはこれですが、あなたがそれをためす前に、答えを見ないでください、:

detect.png.

The arrows indicate the counter-clockwise order of the vertices.
矢は、頂点の反時計回りを示します。

Note how for left edges they all point downward!
それら全部がどのように左の端のために下を指すかについて気づいてください!

To detect this in code we merely have to check the Dy1-Dy3 values!
これをコードに落とし込むためには、我々は単にDy1-Dy3の値をチェックしなければならないだけです!

The only exception is the top edge.
唯一の例外は、一番上の(水平になっている)エッジです。

There, Dy# is zero, but Dx# is positive.
そこでは、Dy#はゼロです、しかし、Dx#は正です。

Now that we know how to detect top-left edges, we still have to deal with them correctly so pixels on these edges are treated as inside.
今、我々が左上端を見つける方法を知っているが、これらの端のピクセルが正しく中とみなされるように、我々はまだそれらを扱わねばなりません。

What we actually want to do is change the Cx# > 0 statements into Cx# >= 0 statements.
我々が本当にしたいことは、Cx# > 0ステートメントをCx# >= 0ステートメントに変えることです。

Testing for top-left edges per pixel is way to slow, and handling all these cases in separate loops is way too complex.
ピクセルごとの左上エッジのためのテストは遅いです、そして、別々のループにおいてすべてのこれらのケースを取り扱うことはあまりに複雑です。

But look at what Cx# > 0 fundamentally is.
しかし、Cx# > 0が基本的にそうであることを見てください。

It is 'true' when Cx# is 1, 2, 3, etc, and 'false' when Cx# is 0, -1, -2, etc. All we want to do is make it true also when Cx# is zero.
Cx#が1、2、3・・・ のとき、true、そしてCx#が0、-1、-2 ・・・のとき falseです。
我々がやりたいこと全ては、Cx#が0のとき、trueにすることです。

The solution is too simple for words:
解決は、あまりに単純です:

all we have to do is add 1 to Cx# beforehand.
我々がしなければならないすべては、前もって1をCx#に加えることです。

This can even be done sooner, with the C1-C3 variables!
これは、C1-C3変数により、さらに即座にすることさえできます!

Ok, let's sum this all up:
Ok、これのすべてを要約しましょう:


コード略



コードについての説明を、スレ#76あたりより抜粋

28.4の固定小数点フォーマットにするために、16で乗算。
微小増減(デルタ)を計算したあと、
この微小増減は、後で乗算され、48.16のビット精度が必要となる。

そこで、48.16を、32ビットで表せるように16.16フォーマットで表すことにすると、乗算前は僅かに整数部8ビット。
これでは256ピクセルしか表せない。

24.8フォーマットは12ビットの解像度、つまり4096ピクセル表せる。
4ビットサブピクセルにつかったとしても、十分な解像度がある。
これなら妥協できる。
もし、もっと高い解像度や、高精度AAやサブピクセルが必要なら、
64ビット使っちゃうか、他の方法にするしか。

途中で
int minx = (min(X1, X2, X3) + 0xF) >> 4;
とかやってるとこの、0xF足してるのは、ceil()関数と同じです。
なんでceilしてるかというと、最初のエッジの右端を正確に塗りつぶすため。




Here's the end result:
結果は、ここにあります:

correct.png.

Not only is it now entirely flawless, it's also faster than the floating-point version!
完璧な上に、浮動小数点版より速いです!

The range of the fixed-point integers is big enough for a 2048x2048 color buffer, with 4 bits of sub-pixel precision.
固定小数点整数の範囲は、4ビットのサブピクセルの、2048x2048カラーバッファ、のために十分に大きいです。

Now we got this fixed, let's focus on performance again...
我々がこの修正が出来た今、もう一度パフォーマンスに集中しましょう...

This implementation is perfect for small triangles.
この実装は、小さな三角形に完璧です。

The setup cost per triangle is really low compared to the scanline conversion algorithm.
三角形ごとのセットアップコストは、走査線転換アルゴリズムと比較して本当に低いです。

Unfortunately, it's not optimal for big triangles.
残念なことに、それは大きい三角形には最適でありません。

About half of all pixels will be outside the triangle, but we still pay the price of evaluating the half-space functions.
もしすべてのピクセルの約半分で、ピクセルが三角形の外側にあるとしても、我々はまだ、半空間関数を評価するコストを払います。

Furthermore, until now I've only talked about drawing one pixel at a time, while the real benefits of this approach is the possibility for parallelism.
さらに、私はまだ、ただ一度に1ピクセルを描くことについて話していますが、この方法の本当の利益は、並列可能であるということです。

I'll show you how to take advantage of this, and what other benefits we get from it.
私は、どのようにこれを利用するべきか、そして、我々がそれからどんな他の利点を得るかあなたに教えます。

What we really want to do is quickly skip pixels outside the triangle.
我々が本当にしたいことは、速く、外の三角形のピクセルをスキップすることです。

We don't want to waste any time evaluating half-space functions there.
我々は、半空間関数の評価のために、少しの時間も無駄にしたくありません。

We also don't want to spend too much time inside the triangle.
また、あまりにたくさんの時間を三角形の内側判定に費やしたくありません。

The really interesting part is around the edges.
本当に興味深い部分は、エッジの周囲にあります。

So what we'll do is quickly detect whether 8x8 blocks are not covered, partially covered, or fully covered.
そこで、我々がすることは、速く、8x8ブロックがおおわれないか、部分的にカバーしなかったか、完全にはカバーしなかったかどうか検出することです。

Not covered or fully covered blocks can quicly be respectively rejected or accepted.
おおわれていないか、完全にはおおわれたブロックは、即座にそれぞれ受け入れられないか、受け入れられるか判別できます。

Partially covered blocks will be completely scanned.
部分的におおわれたブロックは、完全にスキャンされます。

There's another reason to do this block-based approach:
このブロックに基づくアプローチをするもう一つの理由が、あります:

it is very useful for visibility determination algorithms.
それは、可視性の決定アルゴリズムに非常に役立ちます。

And an extra benefit is that memory accesses are more localized.
さらに、追加利点として、メモリアクセスがより局所化されます。

So how do we detect coverage as fast as possible?
では、どのように、我々はできるだけ速く、範囲を見つけますか?

With the half-space functions, it's really easy.
半空間関数では、それは本当に簡単です。

All we have to do is evaluate the half-space functions in the corners of the blocks.
我々がしなければならないことすべては、ブロックの角で半空間関数を評価することです。

A non-covered block has negative half-space values for the corners for at least one edge.
全くおおわれていないブロックは、少なくとも1つのエッジにより、角で負の半空間関数を持ちます。

A completely covered block has positive half-space values for all edges.
完全におおわれたブロックは、すべてのエッジにより正の半空間値を持ちます。

Everything else is a partially covered block.
他の全ては、部分的におおわれたブロックです。

So the final implementation is:
よって、最終的な実装はこれです:


コード略


Note that I scan partially covered blocks completely, all 8x8 pixels.
部分的に覆われているブロックの、全てのピクセル(8x8)を完全にスキャンしたことに注意してください。

This is for consistency with the other blocks so they can be processed by the same visibility algorithm.
これは他のブロックについても一貫しているので、それらが同じ可視性アルゴリズムによって調べられることができます。

Also, this is extremely fast when done in an unrolled loop, using assembly instructions.
また、アセンブラ命令を使用して展開したループで使われたとき、これは驚くほど速いです。

All further optimizations to this algorithm are best done in assembly anyway.
このアルゴリズムへのすべての更なる最適化としては、どっちみちアセンブラ化が最も行われます。

So now the rasterizer can output coverage masks for 8x8 pixels.
そんなこんなで、ラスタライザーは8x8ピクセルの範囲マスクを出力することができます。

This can then easily be processed by the pixel pipeline(s).
これは、また、ピクセルパイプライン(s)で、簡単に処理されることができます。

It's easy to process them as 4x4 quads, and many calculations can even be done per block.
4x4クアッドとして彼らを調べることは簡単です、そして、多くの計算をブロックにごとにすることさえできます。

Everything taken together, there is no reason left to use the old scanline conversion algorithm.
すべてが一緒にされて、古い走査線転換アルゴリズムを使用する理由が残っていません。

Enjoy!

Nicolas "Nick" Capens




#55より

If it's not too much to ask, would it be possible to see an example of the right way to find the gradients?
もしよろしければ、勾配を見つける正しい方法を聞いても良いですか?

The easiest and most robust way is to use the plane equation.
もっとも簡単で強力な方法は、面の方程式を使うことです。

Let's say we want to interpolate some component z linearly across the polygon (note that z stands for any interpolant). 
我々がポリゴンに線形に交わる構成要素zを補間したいとしましょう。(zはどんな補間にも使えることに注目)

We can visualize this as a plane going through the x, y and z positions of the triangle, in 3D space. Now, the equation of a 3D plane is generally:
3D空間では、我々は三角形のx、y、z位置を通じた面として、これを思い浮かべることができます。3D面の方程式は、一般的には、こうです

A * x + B * y + C * z + D = 0

これを次のように変形できます

z = -A / C * x - B / C * y - D

Note that for every step in the x-direction, z increments by -A / C, and likewise it increments by -B / C for every step in the y-direction.
x方向の毎ステップで、zは -A/C ずつ増加し、同様に、y方向の毎ステップでは、 -B/C ずつ増加します。

So these are the gradients we're looking for to perform linear interpolation.
一次補間を行うために探しているグラデーションはそこです。

 In the plane equation (A, B, C) is the normal vector of the plane. It can easily be computed with a cross product.
面方程式では、A, B, Cは面の法線ベクトルn = (A, B, C)です。それは外積を計算することで、簡単に求まります。

Now that we have the gradients, let's call them dz/dx (which is -A / C) and dz/dy (which is -B / C), we can easily compute z everywhere on the triangle. 
勾配を得た今、-A/Cを dz/dx、 -B/Cを dz/dy と呼ぶことにし、三角形の任意の点でのzを簡単に計算することができます。

Then a generic z value of a point (x, y) can be computed as:
x、yでのz値は一般的に、このように計算されます。

z = z0 + dz/dx * (x - x0) + dz/dy * (y - y0)

Once you've computed the z value for the center of the starting pixel this way, you can easily add dz/dx to get the z value for the next pixel, or dz/dy for the pixel below (with the y-axis going down).
あなたがこの方法で、ピクセル中央でz値を計算したなら、次のピクセルを得るのためにdz/dxを簡単に加算できます。また、次の行(y軸の下)へ進む場合も、dz/dyを加えるだけです。





Comments