f:id:vasilyjp:20200928130510p:plain

ポリゴンメッシュの紹介

皆様、はじめまして！　計測プラットフォーム部バックエンドチームの村木と申します。

本記事では私達のチームが、お客様の足の形状を分析していく中で得た、様々な知見を紹介していきたいと思います。

まず、足の形を3Dで表現するために私達が採用しましたモデリング手法「ポリゴンメッシュ」について紹介します。

「ポリゴンメッシュ」（以降では単に「メッシュ」と表記します）は、3Dのオブジェクトをその表面を覆う多角形、または三角形の集合として表現する手法です。

上の画像は、足の形状をメッシュで表現した例になります。多数の細かい三角形でオブジェクトの表面が覆われているのが見て取れるかと思います。

trimeshの紹介

3Dオブジェクトを多角形の集合で表現するということについて、私達が使用しているPythonライブラリ、trimeshを使って詳しく見ていきましょう。

trimeshは、三角形メッシュ（triangle mesh）を読み込み、簡単に操作・分析するためのピュアPythonライブラリです。

「三角形メッシュ」とは、その名の通り一般の多角形ではなく三角形のみでオブジェクトの表面を覆うメッシュの一種を指します。

では、trimeshを使って基本的なメッシュデータを定義してみます。

import trimesh

mesh = trimesh.Trimesh(
    vertices=[[0, 0, 0], [0, 0, 1], [0, 1, 0]],
    faces=[[0, 1, 2]]
    )

このコードでは、引数 vertices に3つの頂点の情報を与え、また引数 faces に1つの面すなわち三角形の情報を与えています。1つのfacesを構成する [0, 1, 2] という数値は、それぞれ0,1,2番目のverticesから構成される三角形であることを示しています。

このように頂点と面の集合をリストとして与えることで、メッシュを定義することが出来ます。

足の形状の特徴データ

次に、私達が考案しました、以下の1から3の処理で求まる足の形状に関するデータを紹介します。

XY平面に、等間隔で配置した格子点を設ける。
それぞれの格子点から、Z軸方向にのばした直線とメッシュデータとの交点を求める。
YZ平面、ZX平面についても同様の処理でメッシュデータとの交点を求める。

こちらが、1つの平面のみを図示したものです。格子点とメッシュの交点

この処理で得られた交点の座標の集合は、足の形状の特徴を表すデータとして扱えることが、私達の分析の中で分かってきました。

次の節ではこの処理、すなわち「格子状に配置したベクトルとメッシュとの交点を求める処理」を、trimeshを使って実装していきます。

ベクトルとメッシュの交点計算

以下のコードが、格子状に配置したベクトルとメッシュとの交点を求め、ビジュアライズする処理です。

import trimesh
import numpy as np


def load_and_create_mesh():
    npz_kw = np.load('np_vertices_faces.npz')
    vertices = npz_kw["vertices"]
    faces = npz_kw["faces"]
    return trimesh.Trimesh(vertices=vertices, faces=faces)


def create_ray_origins():
    x_coord = np.linspace(-160, 160, num=160, endpoint=False)
    y_coord = np.linspace(0, 80, num=40, endpoint=False)
    X, Y = np.meshgrid(x_coord, y_coord, sparse=False, indexing='xy')
    return np.dstack([np.zeros(X.shape), X, Y]).reshape([-1, 3])


def create_ray_directions(size):
    ray_directions = np.array([[1, 0, 0]] * size)
    return ray_directions


def ray_intersects_location(mesh, ray_origins, ray_directions):
    locations, index_ray, index_tri = mesh.ray.intersects_location(
        ray_origins=ray_origins,
        ray_directions=ray_directions)
    return locations


def create_scene(mesh, ray_origins, ray_directions, locations):
    # stack rays into line segments for visualization as Path3D
    ray_visualize = trimesh.load_path(np.hstack((
        ray_origins,
        ray_origins + ray_directions)).reshape(-1, 2, 3))

    # make mesh transparent- ish
    mesh.visual.face_colors = [100, 100, 100, 100]

    # create a visualization scene with rays, hits, and mesh
    scene = trimesh.Scene([
        mesh,
        ray_visualize,
        trimesh.points.PointCloud(locations)])
    return scene


if __name__ == '__main__':
    mesh = load_and_create_mesh()
    ray_origins = create_ray_origins()
    ray_directions = create_ray_directions(ray_origins.shape[0])
    locations = ray_intersects_location(mesh, ray_origins, ray_directions)
    scene = create_scene(mesh, ray_origins, ray_directions, locations)
    scene.show()

なお、ビジュアライズの処理は、trimeshのリポジトリに含まれているサンプルコードを参考にしています。 github.com

以下、各処理の説明です。

load_and_create_mesh関数
- vertices, facesのロードと、trimeshオブジェクトの生成
create_ray_origins関数
- intersects_locationに与える引数ray_originsの生成
  - 等間隔でならんだ格子状の座標を生成している
create_ray_directions関数
- intersects_locationに与える引数ray_directionsの生成
ray_intersects_location関数
- 格子状に配置した直線とメッシュとの交点を求める
create_scene関数
- pygletを使ったメッシュと交点の座標をビジュアライズする

最も注目して頂きたいのは、ray_intersects_location関数で行われている処理です。trimeshオブジェクトのフィールドのrayオブジェクトとそのメソッドである intersects_location を使って、複数のベクトルとメッシュ表面との交点を一括して計算しています。

メソッド intersects_location は、その引数ray_originsでは交点を求めたいベクトルの起点となる座標のリストを与え、引数ray_directionsでは各ベクトルの方向を表す座標を与える仕様であることにも注意して下さい。

さて、メソッド intersects_location の呼び出しによって無事に格子状に配置したベクトルとメッシュ表面との交点を求めることが出来ました。しかし、この処理では格子が細かい場合に処理速度が遅く、求める交点が数十万に及ぶ場合は数十秒に渡る時間がかかってしまうという問題がありました。

embreeを用いた高速化

幸いなことにtrimeshでは、rayオブジェクトを使った処理は、embreeというライブラリを使用することで高速化することが可能でした。

embreeは、Intelによって開発されたCPUベースの高性能レイトレーシングライブラリです。Intelの最新のプロセッサ向けにパフォーマンスが最適化されたライブラリであり、レンダリング処理のパフォーマンスを向上させることが出来ます。

trimeshはこのembreeの組み込みに対応しており、embreeとそのPythonラッパーであるpyembreeをインストールするだけで、ソースコードを修正することなく処理の高速化を行うことが出来ます。

embreeとpyembreeのインストール方法は、公式のスクリプトが参考になります。

#!/bin/bash
set -xe

# Fetch the archive from GitHub releases.
wget https://github.com/embree/embree/releases/download/v2.17.7/embree-2.17.7.x86_64.linux.tar.gz -O /tmp/embree.tar.gz -nv
echo "2c4bdacd8f3c3480991b99e85b8f584975ac181373a75f3e9675bf7efae501fe  /tmp/embree.tar.gz" | sha256sum --check
tar -xzf /tmp/embree.tar.gz --strip-components=1 -C /usr/local
# remove archive
rm -rf /tmp/embree.tar.gz

# Install python bindings for embree (and upstream requirements).
pip install --no-cache-dir numpy cython
pip install --no-cache-dir https://github.com/scopatz/pyembree/releases/download/0.1.6/pyembree-0.1.6.tar.gz