SVOとはVoxelOctreeをメモリ効率を上げてマッピングする手法で、
基本的なボクセルデータvec_t rgbaの上位bitをアドレスとして設定します。
これによって空白ボクセル部にメモリを取られず、高効率でボクセルデータを格納することが出来ます。

(64bit type):
X: [ID:2][node x:10][node y:4] //ID : leafの所持フラグ
Y:[node y:6][node z:10]
Z:[color r:8][color g:8]
W:[color b:8][color a:8]
※数値はbit

SVOはRaytraceとの親和性が高く、また法線マップなどを使わずに詳細なディティールを表現できるため、
tech6等の次世代のゲームエンジンで積極的に取り入れられようとしています。

しかし、この実装通りに行うと、OpenCLでレイトレースするためには再帰関数がサポートされない関係で
bool hit_geom_level0(ray r,float *t,__global uint4 * geom)
bool hit_geom_level1(ray r,float *t,__global uint4 * geom)
と自前で再帰定義、呼び出しを行わなくてはいけません。
mipmap levelがそこまで高くなければ問題ありませんが、純粋にOctreeを作っていては納得できる分割数に至るまでにかなり階層が深くなってしまいます。
そこでmipmap level N(最大レベル)の分割数をある程度上げ、階層を固定化することでこの問題はある程度解決します。

また、SVOを使用することで、レイとジオメトリとの交差判定で得た距離をLevel of Detailに用いることで比較的簡単にCone Tracingの効果を得られる事も一応記しておきます(まだしっかりと実験していないので詳細は無しで)。

SVO自体の可視化

上データを使用した単純なパストレース

若干取り留めのない文章になってしまいましたが、この文ですこしでも「よし！SVOやる！」という方が増えてくれれば幸いです。
次回未定。

さて、前回ボクセルシーンを生成した訳ですが。
今回はそのデータを用いてRayCastを行ってみました。

RayCastとは:
RayMarchingとほぼ同じ意味で使われますが、簡単に言えばボリュームデータに対し、線分を少しづつ進めて交差判定を行う方法の事です。
用途としては、1[煙等、透過するオブジェクトのレンダリング]
2[X線画像等の体積を持ったデータの可視化]
ですが、最近リアルタイムレンダリングの界隈でライティング計算に用いるようになってきました。

流行に乗るために簡単な実装を行いました。
video

で、問題のRaycasting部分

//in raycast function
//*r is ray
	int const size = res * center.w;
	float4 const mini = center - size*0.5f;

	for(int i = 1;1;++i)
	{
		float4 const p = r.orig_ + r.dir_*i*center.w;
		float4 const r_vox_pos = ( p - mini )/center.w;
		int4 const r_vox_pos_i = convert_int(r_vox_pos);

		//exit without hit
		if(r_vox_pos_i.x < 0 || r_vox_pos_i.x >= res-1 ||
		   r_vox_pos_i.y < 0 || r_vox_pos_i.y >= res-1 ||
		   r_vox_pos_i.z < 0 || r_vox_pos_i.z >= res)
			return false;

		sphere sp;
		sp.pos_ = convert_float(r_vox_pos_i)*center.w - size/2.f + center.w*0.5f;
		sp.r_   = center.w*0.5f;
		float t;

		if( sphere_intersect(r,sp,&t) )
		{
			// hit actions
			return true;
		}

ここで交差した部分のボリュームデータが半透明な物であれば線分の開始点を書き換え(必要であればライティングも)て再びRaycastを行えばボリュームレンダリングになります。
また、今回は交差判定にbounding sphereを用いてますが、一般的にはAABBを使った方がクオリティの問題で良いと思います。

ではまた何かネタが出来たときに。

プログラミングの魔導書 Vol.3のプロジェクトが本格始動しました。Vol.3のテーマは「並行／並列／分散」です。
2012年6月以降に発売する予定で進めています。

今回も、前回に負けないくらいのメンバーと記事を取り揃える予定ですので、発売まで楽しみにお待ちください。

『プログラミングの魔導書 Vol.2』でのDave Abrahamsへのインタビュー記事の英語版がBoostPro Computingのサイトで公開されました。Dave Abrahamsは、Boost C++ Librariesの創立者の一人で、C++言語の規格にも大きく貢献した人物です。

Programmer’s Grimoire Interview: now in English – BoostPro Computing

今回、簡単なボクセライザーを作ったのでその実装方法を紹介しようかと思います。
ボクセル化自体、いろいろな方法がありますが今回はポリゴンデータからラスタライザの要領で直接ボクセル化を行う方法です。
FrameBufferを用いてボクセル化を行うにはGLUT入門で有名な@tokoik先生が記事を書いているのでそちらを参照してもらえればと思います。

さて、本題。
ラスタライザの要領と書きましたがラスタライザにも色々な実装方法がありますが、今回行った方法は一番簡単な(と思ってる)、三辺の一辺を終点とし、

開始点から徐々に辺を満たすように線を引く方法です。

実際のコード

//in the raster voxel func
v4f end_line = t.p[2] - t.p[1];
float const end_line_length = length(end_line);
end_line = norm(end_line);
unsigned const end_count = end_line_length / vox_len;

for(unsigned i = 0;i <= end_count;++i)
{
	v4f const end_pos = t.p[1] + end_line * (i*vox_len);
	v4f rast_line = end_pos - t.p[0];
	float const rast_line_length = length(rast_line);
	rast_line = norm(rast_line);
	unsigned const rast_count = rast_line_length / vox_len;

	//line painting
	for(unsigned j = 0;j <= rast_count;++j)
	{
		v4f const p = t.p[0] + rast_line * (j*vox_len);

		float const min_x = center[0] - (RES*vox_len)/2.f;
		unsigned const x = std::max(static_cast<int>((p[0] - min_x)/vox_len),0);
		float const min_y = center[1] - (RES*vox_len)/2;
		unsigned const y = std::max(static_cast<int>((p[1] - min_y)/vox_len),0);
		float const min_z = center[2] - (RES*vox_len)/2;
		unsigned const z = std::max(static_cast<int>((p[2] - min_z)/vox_len),0);

		voxel[x][y][z] = t.c;//painting voxel
	}
}

この方法での利点はどれだけ広大なシーンであっても問題なくvoxelizeを行えるという点です。
しかし、この方法の場合テクスチャ参照を行い、色を決定する場合かなり面倒なことになるので基本的にはFrameBufferを用いた実装をした方がいいと思います。

最後に今回の実行結果。それでは皆様、良い御年を。

さて、今回はHaskellで適当にOpenGL使って遊びましょうと言うことでGPipeの紹介をしたいと思います。

まずGPipeの紹介ですが、このパッケージはGLSLをHaskell上でDSLとして表現したものになっています。
よってGLSL等の手続き型シェーダコードを書くことなく、全てHaskellのコードで書く事ができるので、せっかく関数型つかってるのに・・・と肩を落としている人は使ってみるといいんじゃないでしょうか。

といった所で今回のコード

import Graphics.GPipe
import Graphics.GPipe.Texture.Load
import Graphics.UI.GLUT( Window,
                         mainLoop,
                         postRedisplay,
                         idleCallback,
                         getArgsAndInitialize,
                         ($=))
import qualified Data.Vec as Vec
import Data.Vec.Nat
import Data.Vec.LinAlg.Transform3D
import Data.Monoid

cube :: PrimitiveStream Triangle (Vec3 (Vertex Float), Vec3 (Vertex Float))
cube = mconcat [pos_x, neg_x, pos_y, neg_y, pos_z, neg_z]
pos_x = toGPUStream TriangleStrip $ zip [1:.0:.0:.(), 1:.1:.0:.(), 1:.0:.1:.(), 1:.1:.1:.()] (repeat (1:.0:.0:.()))
neg_x = toGPUStream TriangleStrip $ zip [0:.0:.1:.(), 0:.1:.1:.(), 0:.0:.0:.(), 0:.1:.0:.()] (repeat ((-1):.0:.0:.()))
pos_y = toGPUStream TriangleStrip $ zip [0:.1:.1:.(), 1:.1:.1:.(), 0:.1:.0:.(), 1:.1:.0:.()] (repeat (0:.1:.0:.()))
neg_y = toGPUStream TriangleStrip $ zip [0:.0:.0:.(), 1:.0:.0:.(), 0:.0:.1:.(), 1:.0:.1:.()] (repeat (0:.(-1):.0:.()))
pos_z = toGPUStream TriangleStrip $ zip [1:.0:.1:.(), 1:.1:.1:.(), 0:.0:.1:.(), 0:.1:.1:.()] (repeat (0:.0:.1:.()))
neg_z = toGPUStream TriangleStrip $ zip [0:.0:.0:.(), 0:.1:.0:.(), 1:.0:.0:.(), 1:.1:.0:.()] (repeat (0:.0:.(-1):.()))

tex_coords = [ 0:.0:.(),0:.1:.(),1:.0:.(),1:.1:.()]
plane :: PrimitiveStream Triangle (Vec3 (Vertex Float),Vec2 (Vertex Float))
plane = toGPUStream TriangleStrip $ zip [(-5):.0:.(-5):.(),(-5):.0:.5:.(),5:.0:.(-5):.(),5:.0:.5:.()] tex_coords

-- vertex shader
cube_proc_scene :: PrimitiveStream Triangle (Vec4 (Vertex Float), Vec3 (Vertex Float))
cube_proc_scene = fmap (cube_transform) $ cube

cube_transform :: (Vec3 (Vertex Float),Vec3 (Vertex Float)) -> (Vec4 (Vertex Float), Vec3 (Vertex Float))
cube_transform (pos,norm) = (transformedPos,norm)
    where
         viewMat = (translation (0:.0:.(-10):.())) `multmm` (rotationX (pi/6)) `multmm` (rotationY (pi/4))
         projMat = perspective 1 100 (pi/3) (800.0 / 600.0)
         viewProjMat = projMat `multmm` viewMat
         transformedPos = toGPU viewProjMat `multmv` (homPoint pos :: Vec4 (Vertex Float))

plane_proc_scene :: PrimitiveStream Triangle (Vec4 (Vertex Float), Vec2 (Vertex Float))
plane_proc_scene = fmap (plane_transform) $ plane

plane_transform :: (Vec3 (Vertex Float),Vec2 (Vertex Float)) -> (Vec4 (Vertex Float),Vec2 (Vertex Float))
plane_transform (pos,texcoord) = (transformedPos,texcoord)
    where
         viewMat = (translation (0:.0:.(-10):.())) `multmm` (rotationX (pi/6)) `multmm` (rotationY (pi/4))
         projMat = perspective 1 100 (pi/3) (800.0 / 600.0)
         viewProjMat = projMat `multmm` viewMat
         transformedPos = toGPU viewProjMat `multmv` (homPoint pos :: Vec4 (Vertex Float))

-- fragment shader
cube_scene :: FragmentStream (Color RGBFormat (Fragment Float))
cube_scene = fmap (lit) $ rasterizeFront $ cube_proc_scene

lit (norm) = color
             where
               li = norm `dot` toGPU (0.2:.0.5:.0.3:.())
               color = RGB (li:.li:.li:.())

plane_scene :: Texture2D RGBFormat -> FragmentStream (Color RGBFormat (Fragment Float))
plane_scene tex = fmap (texed tex) $ rasterizeFront $ plane_proc_scene

texed tex (texcoord) = sample (Sampler Linear Wrap) tex texcoord

render_all :: Texture2D RGBFormat -> FrameBuffer RGBFormat () ()
render_all tex = draw (cube_scene) $ draw (plane_scene tex) clear
    where
      draw  = paintColor NoBlending (RGB (True:.True:.True:.()))
      clear = newFrameBufferColor (RGB (0.1:.0.3:.0.6:.()))

idle win = do  postRedisplay (Just win)

main :: IO ()
main = do
  getArgsAndInitialize  tex <- loadTexture RGB8 "hoge.png"
  newWindow "GPipe"
       (100:.100:.())
        (800:.600:.())
        (render_scene tex)
       init_win
  mainLoop

render_scene :: Texture2D RGBFormat -> Vec2 Int -> IO (FrameBuffer RGBFormat () ())
render_scene tex size = do
          return $ render_all tex 

init_win :: Window -> IO ()
init_win win = do
   idleCallback $= Just (idle win)

実行結果

細かいところですが、import GLUTで部分importをしていますが、これは何も考えないで全てimportしてしまうとGPipeとGLUTの宣言が衝突してしまうのからです。
では更に細かい部分を次々と、

cube :: PrimitiveStream Triangle (Vec3 (Vertex Float), Vec3 (Vertex Float))

この見慣れないPrimitiveStreamと言うのは、VertexBufferに送る情報です。
これはTriangleの他に、”Line”、”Point”も定義されているので用法、用量を守って正しくお使い下さい。
次に

pos_x = toGPUStream TriangleStrip $ zip [1:.0:.0:.(), 1:.1:.0:.(), 1:.0:.1:.(), 1:.1:.1:.()] (repeat (1:.0:.0:.()))

この部分で実際のデータを渡してあげます。
TriangleStripはOpenGLユーザーでおなじみの次々と三角形を補完してやるアレです。
他にもGPipeではTrianglesも定義されているので用途に応じて使い分ければ良いでしょう。

ここで作られたcubeの情報を次に

cube_transform :: (Vec3 (Vertex Float),Vec3 (Vertex Float)) -> (Vec4 (Vertex Float), Vec3 (Vertex Float))

このtransformでVertexBufferにあるデータを実際にfragment shaderとラスタライザに渡すデータに変換しています。
ここがDSLで実現されたVertexShaderの部分です。

続いてfragment shader部、

cube_scene :: FragmentStream (Color RGBFormat (Fragment Float))
cube_scene = fmap (lit) $ rasterizeFront $ cube_proc_scene

ここでrasterizeFrontやrasterizeFrontAndBack等を使用してVertex Shader部分をラスタライズしますと伝えなくてはいけません。(めんどくさい)

lit (norm) = color
             where
               li = norm `dot` toGPU (0.2:.0.5:.0.3:.())
               color = RGB (li:.li:.li:.())

そしてこの部分で実際に表示する色を決定しています。

最後に、

render_all :: Texture2D RGBFormat -> FrameBuffer RGBFormat () ()
render_all tex = draw (cube_scene) $ draw (plane_scene tex) clear
    where
      draw  = paintColor NoBlending (RGB (True:.True:.True:.()))
      clear = newFrameBufferColor (RGB (0.1:.0.3:.0.6:.()))

newFrameBufferColorで新しくFrameBufferを作り、先ほどまでのコードをpaintColorで全てつなげば完了。画像が表示されます。まぁ簡単！

と、簡単にGPipeの紹介を行ったわけですが、これを見て判るとおり、あまり手間をかけずにHaskellを使ってshaderで遊べるのが魅力だと思います。

次は@kos59125さんのChart パッケージ編！

弊社ロングゲートも創立から2年が経過しようとしています。この度、弊社の活動を広くみなさまに知っていただこうと、ブログを開設する運びとなりました。

弊社からのお知らせのみならず、『プログラミングの魔導書』についてや、技術情報など、様々な情報を発信していきたいと思います。

これから末永くお付き合いいただければ幸いです。

どうぞよろしくお願いいたします。