FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer

Detecting interference between two or more 3D models plays a critical role in computer animation and virtual reality. Typical approaches are bounding volume hierarchies and spatial partitioning trees, which are mainly carried out on CPUs. The conventional approaches, due to their hierarchical struct...

Full description

Saved in:
Bibliographic Details
Main Authors: Chen, Shuangmin, Liu, Bangquan, Liu, Taijun, Yu, Xiaokang, Xin, Shiqing, He, Ying, Tu, Changhe
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/140604
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-140604
record_format dspace
spelling sg-ntu-dr.10356-1406042020-06-01T01:46:19Z FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer Chen, Shuangmin Liu, Bangquan Liu, Taijun Yu, Xiaokang Xin, Shiqing He, Ying Tu, Changhe School of Computer Science and Engineering Engineering::Computer science and engineering Algorithm 1D Buffer Detecting interference between two or more 3D models plays a critical role in computer animation and virtual reality. Typical approaches are bounding volume hierarchies and spatial partitioning trees, which are mainly carried out on CPUs. The conventional approaches, due to their hierarchical structure, cannot be fully parallelized. In this paper, we propose a highly parallel method, based on geometry images, for detecting interference in real time. Our method is inspired by two important observations - one is that interference between two 3D models can be converted into finding common colors contained in the couple of resulting geometry images, and the other is that the RGB space can be mapped onto a 1D buffer. Our algorithm, called FoldedGI, is parameter free, memory efficient and outperforms the state-of-the-art in terms of speed. We demonstrate its efficacy in dynamic interference detection, penetration depth computation and boolean operations between 3D objects. 2020-06-01T01:46:19Z 2020-06-01T01:46:19Z 2018 Journal Article Chen, S., Liu, B., Liu, T., Yu, X., Xin, S., He, Y., & Tu, C. (2018). FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer. Graphical Models, 100, 26-32. doi:10.1016/j.gmod.2018.05.002 1524-0703 https://hdl.handle.net/10356/140604 10.1016/j.gmod.2018.05.002 2-s2.0-85053853662 100 26 32 en Graphical Models © 2018 Elsevier Inc. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Algorithm
1D Buffer
spellingShingle Engineering::Computer science and engineering
Algorithm
1D Buffer
Chen, Shuangmin
Liu, Bangquan
Liu, Taijun
Yu, Xiaokang
Xin, Shiqing
He, Ying
Tu, Changhe
FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
description Detecting interference between two or more 3D models plays a critical role in computer animation and virtual reality. Typical approaches are bounding volume hierarchies and spatial partitioning trees, which are mainly carried out on CPUs. The conventional approaches, due to their hierarchical structure, cannot be fully parallelized. In this paper, we propose a highly parallel method, based on geometry images, for detecting interference in real time. Our method is inspired by two important observations - one is that interference between two 3D models can be converted into finding common colors contained in the couple of resulting geometry images, and the other is that the RGB space can be mapped onto a 1D buffer. Our algorithm, called FoldedGI, is parameter free, memory efficient and outperforms the state-of-the-art in terms of speed. We demonstrate its efficacy in dynamic interference detection, penetration depth computation and boolean operations between 3D objects.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Chen, Shuangmin
Liu, Bangquan
Liu, Taijun
Yu, Xiaokang
Xin, Shiqing
He, Ying
Tu, Changhe
format Article
author Chen, Shuangmin
Liu, Bangquan
Liu, Taijun
Yu, Xiaokang
Xin, Shiqing
He, Ying
Tu, Changhe
author_sort Chen, Shuangmin
title FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
title_short FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
title_full FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
title_fullStr FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
title_full_unstemmed FoldedGI : a highly parallel algorithm for interference detection by folding a geometry image into a 1D buffer
title_sort foldedgi : a highly parallel algorithm for interference detection by folding a geometry image into a 1d buffer
publishDate 2020
url https://hdl.handle.net/10356/140604
_version_ 1681058192424960000