دانلود رایگان مقاله تعامل لمسی زمان واقعی خارج از هسته در مدل های بسیار بزرگ

Abstract

In this paper we address the problem of fast inclusion tests and distance calculation in very large models, an important issue in the context of environments involving haptic interaction or collision detection. Unfortunately, existing haptic rendering or collision detection toolkits cannot handle polygonal models obtained from 3D digitized point clouds unless the models are simplified up to a few thousand polygons, which leads to an important lack of detail for the scanned pieces.We propose a data structure that is able to manage very large polygonal models (over 25M polygons), and we explain how this can be used in order to compute the inclusion of a point into the solid surface very efficiently, performing several thousand pointin-solid tests per second. Our method uses a data structure called EBP-Octree (Extended Bounding-Planes Octree), which is a very tight hierarchy of convex bounding volumes. Based on a spatial decomposition of the model using an octree, at each node it defines a bounding volume using a subset of the planes of the portion of the polygonal model contained at that node. We use the EBP-Octree in a haptic interaction environment, where distance tests and the orientation of collided triangles must be accurate and fast. We also demonstrate that the proposed algorithm largely meets the interactive query rate demanded by a haptic interaction (1 kHz), despite being executed in a single CPU thread on a commonly available computer.

6. Conclusions and future work

We have proposed a data structure capable of handling large polygonal models in a haptic rendering system, never used before in such environments. Point classification query rates are below 0.5 ms in the worst scenarios, and around 0.03 ms in surface paths. Distance queries in common haptic interaction scenarios are also below 0.07 ms, which by far exceeds the expected haptic rendering query rate of 1 ms/test. In order to achieve these results, we have extended the BPOctree proposed by Melero et al. by including new features and algorithms, such as: • A 64 bit octcode that allows octrees up to 20 levels. This feature allows us to exceed the limit imposed by the 32-bit BP-Octree, which was only able to load models up to 2.5M polygons. • A procedure for labelling node corners that allows us to include new black and white nodes.