| Terrain synthesis technology has a wide range of applications in computer games,movie special effects,battlefield simulation and other scenarios.Terrain synthesis technology aims at pursuing more realistic results,more efficient processes,and more convenient and flexible control.Fractal models,physical erosion models,and samplebased terrain synthesis methods have emerged.Among the three methods,the result of the sample-based terrain synthesis method is the most realistic.The DEM(Digital Elevation Model)based terrain synthesis is using a digital elevation model of the real terrain as samples,controlled by the sketches drawn by the user,the feature matching patches are selected from the samples and synthesized a terrain model which has a same terrain style of the DEM and in line with the user desired.The purpose of this thesis is to improve the algorithm for feature region synthesis and non-feature region synthesis in the existing methods,and to study a more efficient DEM-based terrain synthesis method.The main research contents of this thesis are as follows:(1)For the synthesis of feature regions,a propagation-assisted KD tree is introduced for finding matching patches.Finding matching patches from the sample is an important task in DEM-based terrain synthesis,the propagation-assisted KD tree can help find matching patches more efficiently.The use of propagation-assisted KD trees can propagate good match relationships to their neighboring regions,eliminating the need for the backtracking behavior which is time-consuming.The feature region synthesis based on the propagation-assisted KD tree solves the propagation along the characteristic curve under the condition that the direction of characteristic curve changes in the terrain synthesis.In terms of the efficiency of synthesis,the time costs for the synthesis is reduced by half under the premise of ensuring the results of the synthesis.(2)For the synthesis of non-feature regions,parallel random sampling and propagation methods are used.The core idea is: when the number of patchs is large,random sampling can build some good good matches,and those good patch matches can be spread through propagation.Drawing on the idea of texture synthesis,the synthesis of non-feature regions is performed in parallel.A random sampling method is used to find good patch matches.Based on the matching cost,it is determined whether the randomly sampled candidate patch is rejected or accepted,and the good patch match is propagated around by propagation.The iterative iteration of the two steps,starting from a rough result,continuously iteratively updating the optimization process.With the above improvements,the synthesis efficiency of non-feature regions has increased by 5-10 times.(3)The feature region synthesis algorithm and non-feature region synthesis algorithm obtained in this thesis are applied to the DEM-based terrain synthesis system,and a new DEM-based terrain synthesis system is developed and implemented.At the same time,design experiments test and verify the system and evaluate the effect of the synthesis.Through system testing,the system function is available and realistic terrains can be generated with it. |
