Gallery of Level Set Method in 2D

in Japanese

I applied the previous implementation of the Level Set Method to various 2D images. See below.

gallery

Level Set Method -- Application to Arbitrary 3D Shapes --

in Japanese

Introduction

I have recently extended the previous implementation of the Level Set Method so that it can be applied to arbitrary 3D shapes. In this page, I would like to provide you with a brief explanation on the new implementation.
In order to accomplish the purpose, I used Open Asset Import Library (Assimp). The library allows us to load various 3D format files and to extract 3D information through the common interfaces the library comes with. I have made it possible for my engine to accept the STL format, which is one of 3D model formats, as an input.

Installation of Assimp Library

As MacPorts has it, we can easily install it as follows:

What's STL?

The following are a brief description:

1. It's an abbreviation for Stereo Lithography.
2. It describes a static 3D object.
3. It describes the object as a set of triangles.
4. The vertices of the triangle are listed in a counterclockwise order.
5. A normal vector for the triangle may also be listed. The vector is an unit one.
6. The STL file begins with solid, and ends with endsolid.
7. It has the format of either ASCII or BINARY.
8. It has no color information.
9. It has no compression.
10. It has 1 image.

For example, the STL file looks like this:

Extraction of 3D information

We can extract three vertices and one normal vector for each triangle through the interfaces Assimp Library provides.
In the 3D case, my implementation of the Level Set Method expects a std::uint8_t array with size of width x height x depth as input. The pixels on the surface of the object should be set to 128, and other pixels to 255. The procedures to convert the STL format into my requirement are as follows:

1. The scale conversion and the parallel shift are applied to an object to put it inside a box with the size of width x height x depth.
2. We find the 3D point (int-type) that has the distance less than 1 from each triangle and exists inside the triangle.
3. The pixel value is set to 128.

The adjacent pixels of the surface of the object has 128 and other pixels are set to 255.

Results

There are some demo movies below. All inputs have the size of 200x200x200 pixels.

gallery_of_level_set_method_in_3D

I downloaded some STL files from this site.

Development Environment

1. Mac OS X 10.8.2
2. Processor：3.06 GHz Intel Core 2 Duo
3. Memory：4GB
4. Xcode4.6 with Apple LLVM 4.2（C++ Language Dialect → C++11, C++ Standard Library → libc++）
5. boost-1.51.0 built by the Apple LLVM 4.1. See here
6. opencv-2.4.3 built by the Apple LLVM 4.2. See here.
7. assimp @3.0.1270 (MacPorts's package. Though MacPorts uses the different compiler from the one Xcode has, fortunately my implementation works well.)

My Source Code

Here is my source code. I tested it on the above environment.
The C++11 new features, such as lambda expression and thread library, are used to implement my engine.

Usage

See here.

Execution Command

The execution command looks like this: As soon as you type the return key, the application enters the pause mode. The calculation begins after typing 'p'.

Level Set 法 任意の3D形状への適用

in English

はじめに

先に実装したエンジンを、任意の３次元形状に適用できるよう拡張したので紹介します。
作業するにあたって、Open Asset Import Library（Assimpライブラリ）を利用しました。このライブラリは、さまざまな3Dモデルフォーマットを読み込み、ライブラリの提供するインターフェースを通して3D情報を取り出すことができます。今回は、STLフォーマットを入力値として受け取れるようLevel Set Methodのエンジンを拡張しました。

Assimpのインストール

macportsにあるのでこうします。

STLとは

簡単にまとめておきます。

1. Stereo Lithographyの略である。
2. 固定された３D物体を記述するものである。
3. 物体の表面を三角形に分割して表現する。
4. 三角形の頂点が反時計回りに列挙される。
5. 各三角形の法線ベクトルも記入されることがある。これは単位ベクトルでなければならない。
6. solid ではじまり、endsolidで終わる。
7. binaryとasciiがある。
8. 色情報はない。
9. 非圧縮である。
10. 1 imageである。

例えばこんな感じです。

3D情報の抽出

Assimpライブラリを使うと、頂点の座標と法線ベクトルを取り出すことができます。このとき頂点の数と法線ベクトルの数は同じです。上で見たように、本来であれば3つの頂点につき1つの法線ベクトルが対応するはずです。Assimpでは法線ベクトルが重複して取り出されます。
私のLevel Set Methodエンジンの入力値は、3Dの場合、サイズwidth x height x depthのstd::uint8_t型の配列です。オブジェクトに属していない画素の値は255、属している画素の値は128としています。入力値への変換手順は以下の通りです。

1. 適当なスケール変換と平行移動を行い、オブジェクトをwidth x height x depthの範囲に収める。
2. 各三角形（float型の頂点を持つ）から距離1以下の範囲に存在し、かつ、三角形内部に存在する座標値（int型）を求める。
3. その画素の値を128にする。

オブジェクトの表面近傍にある画素だけが128となり、その中身は255のままです。

結果

こちらで公開します。入力値のサイズは全て200x200x200 pixelsです。

gallery_of_level_set_method_in_3D

STLデータはこちらからダウンロードしました。

開発環境

1. Mac OS X 10.8.2
2. プロセッサ：3.06 GHz Intel Core 2 Duo
3. メモリ：4GB
4. Xcode4.6 with Apple LLVM 4.2（C++ Language Dialect → C++11, C++ Standard Library → libc++）
5. boost-1.51.0（Apple LLVM 4.1でコンパイルしたもの。こちら）
6. opencv-2.4.3（Apple LLVM 4.2でコンパイルしたもの。こちら）
7. assimp @3.0.1270（macportsでインストールしたもの。Xcodeで使われるコンパイラと違いますが動作しました。）

ソース

こちらです。上記の開発環境で動作確認しました。
注意：lambda式やthreadなど、C++11の新しい機能を使用しています。

実行方法

先のページと同じです。

コマンド例

起動後、すぐに一時停止するようにしています。「p」を打つと計算を始めます。