Abstract: Aiming to the similar Dynamic and Multi-objective Optimization Problem (DMOP), such as Collision Detection (CD), where as many of the collision pairs satisfying the collision conditions can be detected in certain time interval, notice that the detected collision pairs are not necessarily the globally optimal solution. A novel Quantum-Behaved Particle Swarm Algorithm (QPSO) was proposed. For this problem, the iteration searching process of quantum-behaved particle has been changed, in this algorithm, once a new position satisfying the condition is detected, then the next searching will be converge towards the latest detected position which maybe not the globally or local optimal solution. This strategy significantly improved the searching ability for the satisfied position in the limited time interval. The new QPSO apply to CD that the efficiency is much better than the traditional QPSO.
INTRODUCTION
The Particle Swarm Optimization (PSO) algorithm which was firstly put forward by American scientists Kennedy and Eberhart (1995), is has been widely applied in many fields depending on the characteristics as simple way, easy to realize, relatively strong global optimization ability. Presently, many types of improved PSO algorithm have been proposed (Coelho, 2010). One of them is the QPSO (Quantum-Behaved Particle Swarm Algorithm) (Sun et al., 2004) which proposed according to the basic theory and parallel calculating ability of quantum physics. The PSO or QPSO can be applied to solve the constraint optimizing problem, the dynamic and multi-objective optimizing problem (DMOP).
The problem noticed in this paper is similar to the classical DMOP, but not the classical DMOP. This similar DMOP, such as Collision and Self-collision Detection, where as many of the collision pairs satisfying the collision conditions can be detected in certain time interval, notice that the detected collision pairs are not necessarily the globally optimal solution.
Collision detection is a basic problem in virtual reality, in order to solve this problem vast of research has been done by lots of scholars abroad and domestic. In recent years, some scholars treat the collision detection problem as DMOP and adopting the intelligent optimization algorithm to find out the collision pairs satisfying conditions (Gartner and Schonherr, 2000). PSO has been successfully used to solve collision detection problem by some scholars (Wang et al., 2006; Li et al., 2010), the detection efficiency has achieved 2 to 3 times of Bounding Volume Hierarchies of AABB (Van den Bergen, 1997).
As the general way to solve the DMOP, the algorithm in reference (Wang et al., 2006), first adopting DBCSAN 8 to classify the small habitat and then collecting the collision pairs satisfying conditions by using Particle Swarm Optimization (PSO) to search multi-locally optimal value. But the efficiency of this algorithm is influenced by the requirements of the merge, division and some other operations in every time interval and in reference (Li et al., 2010) the algorithm is that removing the obvious not intersect area by using BVH, then adopting the PSO which is similar with algorithm in reference (Wang et al., 2006).
For the difference of the problem, the iteration searching process for quantum-behaved particle has been optimized and the efficiency of the global search ability improved greatly. When the first collision pair satisfying the condition is detected then the next searching will be converge towards the latest detected collision pair who satisfying the condition but not toward the globally optimal solution. This strategy is capable to collect as many as collision pairs within the limited time interval although it is not able to finally converge the global minimum. And this algorithm is capable to complete fast searching of collision pairs without the requirements of cluster and the merge, division and some other operations which usually used by other algorithm to solve DMOP.
MODEL OF COLLISION DETECTION PROBLEM
In the stochastic collision detection, between objects and the interiors of objects whether exist collisions could be considered as between two objects and interiors whether exist one or more feature pairs:
| (1) |
F is the fitness function, δ is the collision threshold. Convert this problem into a discrete two-dimension space optimization problem which is consisted by serial numbers of feature pairs in two objects and object interior and this problem could be good solved by using QPSO and found the set of feature pairs satisfying conditions. In the whole feature pair space possibly exist many collision pairs and objects are in continuously change, for these reasons constitute the solution space of this problem become a similar DMOP. The difference with normal DMOP is that the collision detection problem requires to find as many as feature pairs satisfying Eq. 1 in the limited time interval but not the multi local optimal values.
When the DMOP is solved by the traditional intelligent optimization, normally in order to obtain the global optimal value and local optimal value, the classification of searching space need to be done at first and then parallel search in each sub-space by adopting PSO, therefore, the clustering, merger and split and some other operations of sub-space have been added. In this article, aiming at the characteristics of this problem as collision detection, these sorts of operations have been avoided by the optimization of QPSO iterative process, the searching capability of this algorithm for multi collision pairs has been greatly improved.
DESCRIPTION OF ALGORITHM
Quantum-behaved particle swarm optimization: Quantum-behaved Particle Swarm Optimization (QPSO) is proposed based on PSO by Sun et al. (2004) and some others who are inspired by quantum physics theory, its iterative function is completely different with PSO, there is no velocity vector and searching process is stochastic, the global searching capability is much better.
In the No. t+1 iterative, the renew function of the position of the Jth dimension of the No. i particle is:
| (2) |
Among α is compression expansion factor:
which is called the average optimality value in No.j dimension, N is the particle swarm size, Pij (t) is the No.i particle of the optimal unit value in the Jth dimension:
is called potential well, Pij (t) and Pij (t) are the unit optimal value and global optimal value separately.
Because of the advanced global searching capability of QPSO, the precision of collision detection has improved by better search for collision characteristics pairs within the global scope.
Optimization of particle iterative process: QPSO is a kind of algorithm which consider the optimal value experienced by particle as local optimal value and consider the minimum (or maximum) of local optimal value as global optimal value and lead particle converge toward to global optimal value to ensure the global convergence. The DMOP could be solved by applying this algorithm in each sub-space which is produced by the pre-clustering division of searching space. The additional calculation has been added because of the additional pre-clustering division and sub-space division, merger and other operations of iterative process.
Aiming at the characteristics of this problem such as deformable objects collision detection problem, optimizing the whole iterative strategy of algorithm, the pre-clustering division and sub-space division, merger and other operations of iterative process are canceled. The optimized algorithm is not capable to collect the global and local optimal values for sure but it capable to find many more collision feature pairs which is greatly improve the global searching capability of algorithm.
During the process of collision detection, the collision pairs normally appear in clusters which means the probability of collision characteristics pairs appearing surround one collision characteristics pair is much higher than other place. For this reason once one collision feature pair Pn+1 has been detected in order to search for more collision feature pairs, the Quantum-behaved Particle Swarm need to move toward to. Pn While another collision feature pair Pn+1 has been detected, the whole Quantum-behaved Particle Swarm turn to the direction of, for here only F (Pn) δ and F (Pn+1) <δ needs to be satisfied.
Therefore, the whole collision detection process as described below:
| Step 1: | Model sampling, constitute two-dimension discrete search space |
| Step 2: | the particles are random generated in whole searching space, one set C is established and initialized which is used for store the returned collision pairs |
| Step 3: | Execute the procedure from a to C within a time interval |
| • | If the number Nc of feature pairs in set C is greater than N, then random select N pairs of feature pairs as initialization particle and if the number Nc of feature pairs in set C is smaller than N or the set C is empty, then consider the feature pairs in set C as the first Nc particle initialization and the initialized particles are random distributed in searching space and empty the set C |
| • | Find out the first collision feature pair by using the traditional QPSO iterative algorithm and store it in to set C and delete this feature pair from the searching space; if there is no collision feature pair has been found within the specified time interval, then this situation is considered as there is no collision occur, then turn to stage (4) |
| • | Conduct iterative according to Eq. 2 and find the fitness value of the next feature pair by calculation, if the collision detection condition could be satisfied by this fitness value, then set this feature pair as the global optimal value and the local optimal value of the present particle, keep repeating this procedure until the time interval finished and turn to procedure (4) |
| Step 4: | End and return to collision set C and the next time interval start, turn to procedure (3) |
RESULTS
The algorithm was implemented by the VC++6.0 and Open GL on the platform of Intel® Core™2 Duo CPU 2.8 GHz and 3.5 GB memory. The algorithm proposed in (Wang et al., 2006) which based on PSO, was also implemented here to compare. In the following two experiments, the Uniform sampling was chose as sampling method, vertices of the model were chose as feature pairs, the Euclidean distance function was chose as fitness function. The number of particles N = 30, the Collision threshold δ = 0.01, the compression expansion factor α = 1.
Experiment I: Two teapot models which contain 10000 triangular patches each were selected and the collision results shown in Fig. 1. The 5000 vertices were got from each model by uniform sampling to establish two-dimensional search space. The self-collision was neglected in this experiment for the rigid of teapot. The time slice was set to 100 ms, the number of collision pairs were recorded from 10 to 50 ms with 5 ms interval. The ratio of these records with the record of the end of time slice was computed. The result is shown as Fig. 2. It shows that the increase of the number of collision pairs is less than 5% after 35 ms for the algorithm in this paper, but the increase of the number of collision pairs is more than 45% after 35 ms for the algorithm in (Wang et al., 2006) which means the algorithm in this paper is more efficient.
| Fig. 1: | The result of collision |
| Fig. 2: | The result of experiment 1 |
| Fig. 3: | The collision results of experiment II |
| Fig. 4: | Results of experiment II |
Experiment II: An cloth which contains 16348 particles was chose and an sphere was also chose. The cloth was simulated by particle-spring model, the collision results were shown as Fig. 3. The particles of the cloth chose to establish two-dimensional search space. In this experiment, just the result of this algorithm was given for the other algorithms which based on intelligent optimization algorithms can not deal with self-collision. The result was computed by the same way as Experiment I and was shown as Fig. 4. It shows that the algorithm can deal with self-collision problem well. The algorithm can work in tandem with the algorithm based on shape regularity and make the algorithm more efficient, this is the reason why not compared with such algorithm based on shape regularity.
CONCLUSION
The iteration searching process for quantum-behaved particle has been optimized that is more suitable for the problem which similar to DMOP, such as objects collision and self-collision detection. The speed of deformable objects collision and self-collision detection was greatly improved. This strategy can also be applied to other area for such problem that as many of the solution satisfying the constraint conditions can be detected in certain time interval, notice that the detected solution are not necessarily the globally or local optimal solution. It can significantly improve the searching ability in the limited time interval for there is no need for clustering, merger, division and any other operations, experiment results show that the efficiency of this algorithm is much better than the similar algorithms.