# Cube of Space Sampling for 3D Model Retrieval
## 3 3D Model Feature Representation
### Cube of Space Sampling (CSS)  
After pre-processing, feature extraction from 3D models can be performed. In this paper, a spatial scale of sampling for re-sampling 3D models was extracted. In other words, we focused on extracting the features of the spatial concept of a 3D model. This concept is similar to a set of building blocks, which is based on a number of small building blocks to construct and fit to each 3D model. The re-sampling process is described as follows:  
* Step one: normalization. All 3D models were normalized and shifted to the center of the cube space, in which they have the same views. * Step two: selection of cutting number. The cutting number of CSS, i.e., N (e.g., N = 10), was used to determine the density of sampling. In particular, the average cut into N blocks of the cube space in each dimension was considered. As a result, we obtained the total number N\({}^{3}\) of sub-spaces. Next, these sub-spaces were used to perform re-sampling for each 3D model. Figure 2 shows the pseudo code of the CSS process. Figure 2: The pseudo code of CSS. Note that there are two key techniques which were used in our method: \"AABB collision detection\" and \"Fast Collision detection\". \"AABB collision detection\" was used to reduce the detection area, and \"Fast Collision detection\" was for determining whether the subspace was a collision. \"AABB collision detection\" and \"Fast Collision detection\" are introduced as follows. 1. 3D collision detection: 3D collision detection in virtual reality and 3D games are the common technique used in the literature [25], which is based on collision detection to realize the physical phenomena. However, in our approach, a subspace was regarded as another 3D model or object, and a collision between two objects was measured. Then, each subspace with or without a collision was labeled to obtain a sampling matrix. Figure 3 shows an explanation for why we required collision detection between a 3D model and its sampling subspaces. 2. The candidate subspace for collision detection: as 3D models are usually presented by irregular shapes, high computational costs are usually required for precise collision detection between objects. In the literature, the most efficient method is AABB collision detection [26]. It uses the most closely placed cuboids to replace an irregular 3D model to perform complex and cumbersome collision detection. However, directly applying this method to our approach proved difficult. This is because if the resampling scope is too large, it will cause the loss of many features in detail. On the other hand, although the AABB method could not be used to fully detect a collision between objects, it could effectively reduce the number of spaces that we needed for the detection. Therefore, we used the AABB method to find out the most similar rectangular space with the smallest size for the surface of each 3D model, which was then used to map into the subspace to find candidate subspaces. In short, the rectangular space is a set of subspaces, which could show possible collision in the surface. Figure 4 shows an example of AABB collision detection. 3. Fast collision detection: most collision detection algorithms try to minimize the number of primitive-primitive intersections that need to be computed. A fast and reliable method for computing the primitive-primitive intersection is desired. Since rendering hardware is often targeted for triangles, the primitives in collision detection algorithms are often triangles as well [16]. Figure 4: The AABB Collision detection method. Each small black cube is the unit of sampling (cube space). Figure 3: The concept of the CSS method. Each greys cube is the subspace of a 3D model, and each has an associated label to show whether they contain a collision in the 3D model. \begin{tabular}{c} \(\bullet\) \\ \hline \hline \end{tabular}   
the experiments. The dataset is used for evaluating shape-based search methods relevant to the mechanical engineering domain. In 3D model retrieval, the ESB dataset is the commonly used benchmark.