オクトツリーを利用した3次元物体の最近点探索アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
複数の物体が存在する3次元空間において,任意の点から最も近い点を物体上から選択することは多くの分野で有用であるが,これを実現するための効率的なアルゴリズムはこれまで提案されていない.そこで本論文では,そのような最近点を高速に選択するための実用可能なアルゴリズムを提案する.このアルゴリズムはオクトツリーというソリッドモデルのもとで機能する.物体の表面を含む領域のみを再帰的に8等分割することで作成されるオクトツリーは,物体の表面を位置に関して階層的に管理している.この階屈構造を利用すると,1)任意の点から近い順に物体の表面を含む領域を選択し,さらに,2)最近点を獲得すれば直ちに終了するようなアルゴリズムが設計できる,このアルゴリズムは物体の表面を含む領域の大部分を探索しなくても最近点が決定できるので,その計算量は空間内の物体の個数やその形状の複雑さに依存しなくなる.したがって,このアルゴリズムは複雑な形状の物体が多数存在する空間においても高速に機能する.最後に,実験によって複雑な形状の空間におけるアルゴリズムの高速性,さらにはオクトツリーの最大レベルや最近点までの距離の変化に関するアルゴリズムの計算時間のふるまいを調べる.
- 一般社団法人情報処理学会の論文
- 1989-03-15
著者
-
登尾 啓史
大阪電気通信大学情報工学科
-
有本 卓
東京大学工学部計数工学科
-
登尾 哲史
大阪電気通信大学大学院総合情報学研究科コンピュータサイエンス専攻
-
登尾 啓史
大阪電気通信大学大学院総合情報学研究科コンピュータサイエンス専攻
-
畑 祐志
トヨタ自動車(株)パワートレーン本部 第3パワートレーン開発部
-
登尾 啓史
大阪電気通信大学工学部精密工学科
-
畑 祐志
トヨタ自動車(株)
-
登尾 啓史
大阪電気通信大学
-
有本 卓
東京大学工学部
関連論文
- 多面体の凸分割とその歯科シミュレータへの応用
- Newton's Cradleを用いた同時多点衝突運動モデルの実験と評価(セッション2 物理)
- 移動ロボットのセンサベーストナビゲーションについて
- 障害物が密集する未知環境で位置や姿勢の誤差を克服する センサベーストナビゲーション
- 学習方式による位置と力のハイブリッド制御
- 線形近似逆システムに基づいたロボットの学習制御法
- ロボットマニピュレ-タの運動学習制御
- 多変数最適IFIR型フィ-ドバック制御系の設計
- ディジタル式フィ-ドフォワ-ド型モデルマッチング制御系の最適設計
- 情報理論における記号と符号 (記号)
- 二足歩行の数理と制御 (自動制御--対象の完全表現)
- アナログからディジタルへ--音の世界 (アナログとディジタル)
- デ-タはどこまで圧縮できるか (情報理論--シャノン以後の展開)
- ハンガリ-における情報理論--人と動向 (情報理論--シャノン以後の展開)
- FF SUV用 新ハイブリッドトランスミッションの開発
- FF SUV用新ハイブリッドトランスミッションの開発 (特集 ハイブリッド)
- 障害物が疎らな未知環境で位置・姿勢・センサ誤差を克服する センサベーストナビゲーション
- オクトツリーを利用した3次元物体の最近点探索アルゴリズム
- 複数枚の画像を用いて3次元物体を近似したオクトツリーを生成する一手法
- BRepからオクトツリーへの変換アルゴリズムとその評価
- 直線に近い位相特性をもつARMAフィルタの設計--周波数特性に重点を置いた設計
- 二値算術符号の符号化効率について
- 手先拘束下にあるマニピュレータに対するModel-Based適応制御
- 局所センサ情報を用いた未知環境における複数の移動ロボットの運動計画法
- 観測モデルに誤りがある場合の最適フィルタについて
- 移動ロボットにおける空間有限性を考慮した位置推定 - 内界センサ情報と作業領域に関する知識のベイズ的融合法 -
- ディジタル直線の性質に基づく高速多角形近似を用いた移動物体の認識
- ディジタル濃淡画像の動的適応符号化法 (画像処理特集) -- (画像の符号化と表示)
- 直交多項式行列による多項式行列の連続時間安定論
- Construction of Multivariable Schwarz-form Realizations via Orthogonal Polynomial Matrices(Mathematical Theory of Control and Systems)
- メカトロニクスにおける制御技術(メカトロニクス)
- 選択画素符号化方式と選択画素を用いた図形処理
- Viterbiアルゴリズムの一般化について
- 木符号化アルゴリズムの一クラス
- ディジタルマップの海岸線発生についての一考察
- 制御における状態検知と診断(保全工学)
- ディジタル信号処理と制御理論 (コンピュ-タ時代の制御工学特集号)
- 制御理論の隣接分野へのひろがり
- ディジタル信号解析の高速算法
- 畳込み符号の不完全復号
- 多変数ARMA形系の同定
- 表記が多様な手書きドル金額の認識装置の開発
- 複数マニピュレータの協調のための学習制御とModel-Based適応制御 -操作物体の重心位置が未知の場合-
- ウェーブレット相関を用いた信号マッチング
- 共同研究成果報告 テレロボティックスの操作性やロバスト性に関する研究
- レオロジー物体を表現する3つのモデルの変形特性に関する研究
- 新しい撃力生成アルゴリズムとその評価に関する研究
- 新しい撃力生成アルゴリズムとその評価に関する研究
- レオロジー物体を表現する3つのモデルの変形特性に関する研究
- レオロジー物体を表現する3つのモデルの変形特性に関する研究
- 新しい撃力生成アルゴリズムとその評価に関する研究(人工現実感)(マルチメディア・仮想環境基礎)
- レオロジー物体を表現する3つのモデルの変形特性に関する研究(人工現実感)(マルチメディア・仮想環境基礎)
- この15年を振り返って
- センサベーストナビゲーションにおいて移動ロボットが目的地付近まで到達できる誤差の条件
- 障害物の幾何学的性質に基づくセンサベーストデッドロックフリーナビゲーションアルゴリズム
- センサベーストパスプランニングをデッドロックフリーにする十分条件の領域的一般化について
- センサベーストパスプランニングをデッドロックフリーにする十分条件の関数的一般化
- 私のロボット研究の過去・現在・未来
- 未知空間におけるパスプランニングアルゴリズムを設計するための十分条件とそれにもとづくアルゴリズムの評価 : ゴールからのユークリッド距離にもとづく経路計画
- 可視領域をもつ移動ロボットの未知空間における実際的なパスプランニングアルゴリズム
- K-M アルゴリズムのベクトル量子化への応用
- 複数マニピュレータの協調制御に対する学習制御とModel-Based適応制御
- 手先が幾何学的な拘束を受けるマニピュレータの学習制御 (手先力の収束性と計算機シミュレーションによる検証)
- 幾何学的拘束のあるロボットマニピュレータの学習制御
- メカニカルシステムの可学習性と受動性
- 忘却因子を導入した速度型学習制御則
- 高速演算アルゴリズムの最近の動向(技術展望)
- 多変数自己回帰系の同定
- ロボット軌道追従のための学習制御系の設計指針
- パラレルワイヤ駆動システムの作業座標系制御法とそのロバスト性
- 関節座標拘束を用いたループ機構を持つロボットの動力学解析
- 駆動・伝達系を含んだロボットアームのトルク演算制御と軌道生成
- アクティブなカメラ運動による両眼視差の検出
- 柔軟多リンク・マニピュレ-タのPDS制御
- 操作量に関して線形なある非線形制御系の最適制御
- 日米FAの最新動向--日米FAシンポジウムにおけるトピックス (システムと制御技術展′86特集号)
- 線形時変メカニカルシステムに対する学習制御系の収束性
- ロボット・ア-ムの自律制御 (ロボットア-ムの制御)
- ロボット・マニピュレ-タ (農業のロボット化)
- ロボットのリアルタイム制御 (マイクロコンピュ-タの応用特集号)
- ロボットの腕(手)の適応制御 (ロボットの腕・手--メカニズムと制御)
- マニピュレ-タの作業座標フィ-ドバック制御
- マニピュレ-タの適応的な軌道制御方式
- 一般化された情報量と有限パラメータ推定問題
- 記憶のない通信路の容量の計算法
- 逐次推定過程の情報理論的基礎づけ
- ハフおよびフーリエ変換を用いた拡大 ・ 回転 ・ 平行移動検出法の部品位置決めへの応用
- Gold-washing Algorithmに基づく有歪データ圧縮符号の漸近的特性
- ロボットと学習 (「知能ロボット」)
- ハフおよびフーリエ変換を用いた回転と平行移動の検出
- ガボール展開係数を用いた階層的テクスチャー解析
- ガボール展開係数を用いた階層的テクスチャ解析
- レオロジー物体を表現する3つのモデルの変形特性に関する研究(変形と力覚)
- 保安カメラ装置の自動カスタマイズを木の自己組織化法によリ実現する可能性の検討
- 無線LANにおけるCompound TCP+の輻輳制御方式の検討と評価(モバイルアプリケーション,ユビキタスサービス,モバイル分散クラウド,モバイルアドホックネットワーク,センサネットワーク及び一般)
- SF-085-2 医工学部連携による肝臓手術ナビゲーションシステムの開発と応用(SF-085 サージカルフォーラム(85)肝 手術手技-2,第112回日本外科学会定期学術集会)
- 階層レオロジーMSDモデルの形状精度と計算時間について
- クワッドツリーを利用した移動ロボットの高速経路生成アルゴリズム
- 複合現実感を用いた歯科シミュレータにおけるヒューマンインタフェースソフトウエアの開発
- クワッドツリーを利用した移動ロボットの高速動作生成アルゴリズム