Method for real-time and realistic rendering of complex scenes on internet

Abstract

A method for realistic and real-time rendering of complex scene in internet environment, comprising: generating sequences of scene-object-multi-resolution models, a scene configuration file, textures and material files, and a scene data list file; compressing the sequences of scene-object-multi-resolution models, the scene configuration file, the textures and material files, and the scene data list file and uploading the compressed files to a server; downloading, at a client terminal, the scene-object-multi-resolution models, the scene configuration file, the texture and material file, and the scene data list file in ascending order of resolution and rendering the scene simultaneously; dividing, in rendering the scene, a frustum in parallel into a plurality of partitions, generating a shadow map for each frustum, filtering the shadow maps to obtain an anti-aliasing shadowing effect; and the shadow map closest to a viewpoint is updated on a frame-by-frame basis and updating frequency decreases for the shadow maps distant from the viewpoint, wherein the shadow map closest to the viewpoint has the largest size, and the size of the shadow map decreases for the shadow maps distant from the viewpoint.

Claims

1. A method for realistic and real-time rendering of complex scene in internet environment, comprising: a) generating sequences of scene-object-multi-resolution models, a scene configuration file, a texture and material file, and a scene data list file; b) compressing the sequences of scene-object-multi-resolution models, the scene configuration file, the textures and material files, and the scene data list file and uploading the compressed files to a server; c) downloading, at a client terminal, the scene-object-multi-resolution models, the scene configuration file, the texture and material file, and the scene data list file in ascending order of resolution and rendering the scene simultaneously; d) dividing, in rendering the scene, a frustum in parallel into a plurality of partitions, generating a shadow map for each frustum, filtering the shadow maps to obtain an anti-aliasing shadowing effect; and e) the shadow map closest to a viewpoint is updated on a frame-by-frame basis and updating frequency decreases for the shadow maps distant from the viewpoint, wherein the shadow map closest to the viewpoint has the largest size, and the size of the shadow map decreases for the shadow maps distant from the viewpoint.

2. The method according to claim 1, wherein the scene-object-multi-resolution model is generated by: replacing two polygons, all vertexes of which constitute a set ψ, with a tetrahedron, wherein four vertexes of the tetrahedron are determined as follows: selecting two endpoints of a diameter of ψ as a first vertex and a second vertex; selecting a point in ψ that has a largest sum of distances from the first vertex and the second vertex as the third vertex; and selecting a point in ψ that has a largest sum of distances from the first vertex, the second vertex, and the third vertex as the fourth vertex; and repeating the replacing procedure to generate the scene-object-multi-resolution model.

3. The method according to claim 1, wherein the multi-resolution models include high-resolution models and low-resolution models, wherein the model's resolution is determined by a number of polygons contained therein.

4. The method according to claim 3, wherein the number of the polygons contained in the model depends from a distance from the model to the viewpoint.

5. The method according to claim 1, wherein the scene configuration file include property information of the object.

6. The method according to claim 5, wherein the object includes tree, building, and terrain.

7. The method according to claim 5, wherein the property information includes the object's name, position, rotational angle, tilting angle, size, and scaling size, and file name of geometric model data.

8. The method according to claim 1, wherein the texture and material file includes ambient light information, diffused light information, specular light information, and the texture image of the models.

9. The method according to claim 1, wherein the scene data list file lists as the scene data list file respective file names of the sequences of scene-object-multi-resolution models, the scene configuration file, the textures and material files, and the scene data list file and uploading the compressed files to a server and corresponding catalog information.

10. The method according to claim 9, wherein the scene data list file lists the scene configuration file, the textures and material files, and the sequences of scene-object-multi-resolution models in sequence.

11. The method according to claim 10, wherein the sequences of scene-object-multi-resolution models are arranged in ascending order or resolution.

12. The method according to claim 1, wherein the scene is rendered simultaneously with the downloading of data, wherein the low-resolution models are replaced with the high-resolution models progressively so that the models of the objects close to a viewpoint contain sufficient details.

13. The method according to claim 1, wherein the dividing comprises dividing the frustum into the plurality of partitions in parallel to a distant cross section perpendicular to sight line to increase a resolution of shadow map close to a viewpoint.

14. The method according to claim 1, wherein only the models in a current frustum of light source are rendered while the models outside the frustum of light source are culled.

15. The method according to claim 14, wherein culling the models comprises: calculating a boundary box comprising eight vertexes for each model; calculating, for each vertexes, coordinates and a distance to a viewpoint in a coordinate system of a viewport of a current screen; and culling the model if it is not close to the viewpoint and projections of its eight vertexes in the coordinate system of the viewport of the screen are outside the viewport of the screen.

16. The method according to claim 1, wherein the shadow map is smoothed using a Gauss filter in the frame buffer of the client terminal.

17. The method according to claim 16, wherein Gauss filtering is performed according to: $\mathrm{sf}\left[p\right]=5^{-\left(k-3\right)}\Sigma 2^{-\left({.Math.\Delta .Math.}_1+2\left(4-k\right)\right)}\mathrm{stex}\left[p+\Delta \right]$ $\mathrm{where},\Delta \in \left\{{\left(x,y\right)}^t|x,y=-\frac{k-1}{2},-\frac{k-1}{2}+1\mathrm{.Math.},\frac{k-1}{2}.\right\},$ k is a positive odd number, ∥Δ∥.sub.1 is a Euclidean norm of a vector Δ(i=1, 2), p represents coordinates of a fragment in the coordinate system of the screen obtained by rasterizing a primitive, and stex[x] indicates whether a point x is in the shadow, wherein if the point x is in the shadow, stex[x] returns a value 0, otherwise stex[x] returns a value 1, the value range of sf is between 0.0 and 1.0 and sf is used for illumination calculation of fragment within and outside the shadow.

18. The method according to claim 1, wherein in rendering the scene in the client terminal, depth value of each rasterized fragment is compared in parallel with that of a corresponding pixel of the filtered shadow map to generate shadowing effect.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 illustrates an overall flow of a method according to the present invention, the method comprising off-line multi-resolution modeling and on-line realistic rendering.

(2) FIG. 2 illustrates the off-line multi-resolution modeling in the method according to the present invention as shown in FIG. 1, the off-line multi-resolution modeling comprising off-line multi-resolution scene construction and server-side storage, wherein: the off-line multi-resolution scene construction comprises: constructing precise scene model construction, model gradual simplification, MR model sequence (i.e., much model sequence) output, ground model construction, and scene configuration file construction; and the server-side storage comprises storing the file in Zip format and set a password or license, downloading a list, and uploading data to the server.

(3) FIG. 3 illustrates the on-line realistic rendering in the method according to the present invention as shown in FIG. 1, the on-line realistic rendering comprising: remote-client scene data downloading, remote-client scene data importing, and remote-client scene real-time shadow rendering and interactive operation, wherein: the remote-client scene data downloading comprises downloading scene data and files uploaded to the server; the remote-client scene data importing comprises scene data importing and scene data analyzing; the remote-client scene real-time shadow rendering and interactive operation comprises: GPU acceleration, shadow calculation, resolution control, and off-line real-time rendering of scene shadow and interactive operation.

(4) FIG. 4 illustrates an overall flow of the off-line real-time rendering of scene shadow and interactive operation according to the present invention as shown in FIG. 3, the off-line real-time rendering of scene shadow and interactive operation being implemented by a frustum imaging module, a scene model selection module, and a light source frustum imaging module. The off-line real-time rendering of scene shadow and interactive operation are performed off-line after the data is obtained on-line. In each rendered frame, the frustum image module first divides the frustum into a plurality of sub-frustum using Parallel-Split Shadow Mapping (PSSM) according to the position of the view point. The scene model selection module performs model cropping on each sub-frustum and determines a model to be rendered in each frustum. Then the model in each frustum is projected into a light source coordinate system. A shadow map is generated by the light source frustum imaging module for each sub-frustum. Then the frustum imaging module renders the scene. The frustum imaging module projects coordinates of each rasterized fragment into the light source coordinate system and compares the projected coordinates with corresponding coordinates in the shadow map of the sub-frustum corresponding to the fraction and performs anti-aliasing filter in the shadow map to generate a soft shadowing effect. In this way, the large-scale scene can be rendered in real time.

(5) FIG. 5 illustrates a list of tree multi-resolution models arranged from bottom to top in accordance to generation order of the models. The list shown in FIG. 5 includes 5 models. FIG. 5(a) to FIG. 5(e) show models with resolutions from high to low, respectively.

(6) FIG. 6 illustrates a downloading interface showing a URL and a transfer progress. In this figure, seventeen files have been downloaded, wherein each tree is represented by five models with different resolutions. The downloaded files constitute 37.5% of the total files that need to be downloaded. The user needs to designate a memory location to store the downloaded scene files and all the multi-resolution model files.

(7) FIG. 7 illustrates an interface where the scene file is opened. The user needs to indicate the memory location where the scene file has been stored.

(8) FIG. 8 illustrates a transition effect from low-resolution tree models to high-resolution tree models in rendering a forest scene. There are 605 trees being rendered. FIG. 8(a) illustrates a rendering effect achieved by employing the lowest-resolution models where all the trees are represented by the lowest-resolution models containing 424662 triangles in total. FIG. 8(b) illustrates a rendering effect achieved by employing the lowest-resolution models and the secondary-lowest-resolution models where a major part of the trees (464 trees) are represented by the lowest-resolution models and a minor part of the trees (141 trees) are represented by the secondary-lowest-resolution models. FIG. 8(b) contains 754042 triangles in total. FIG. 8(c) illustrates a rendering effect achieved by employing models with four different resolutions, where 462 trees are represented by the lowest-resolution models, 76 trees are represented by the secondary-lowest-resolution models, 42 trees are represented by tertiary-lowest-resolution models, and 25 trees are represented by secondary-highest models. FIG. 8(c) contains 1249235 triangles in total.

(9) FIG. 9 illustrates division of a frustum according to the present invention.

(10) FIG. 10 illustrates a comparison between a shadowing effect before anti-aliasing process and a shadowing effect after anti-aliasing process according to the present invention. FIG. 10(a) illustrates the shadowing effect before the anti-aliasing process. FIG. 10(b) illustrates a shadowing effect after the anti-aliasing processing using a 3*3 Gauss filter. FIG. 10(b) illustrates a shadowing effect after the anti-aliasing processing using a 5*5 Gauss filter.

(11) FIG. 11 illustrates real-time changing of a dynamic shadowing effect according to the present invention. FIG. 11(a) illustrates the effect in the early morning. FIG. 11(b) illustrates the effect when the sun has risen high.

(12) FIG. 12 illustrates a pedestrian view and a bird's eye view of the scene according to the present invention.

EMBODIMENTS

(13) The present invention will be explained in detail with reference to the drawings. It should be noted that the embodiments are only illustrated for easy understanding of the present invention rather than limit the scope thereof.

(14) 1. Overview of the Method

(15) The present invention provides, among other things, real-time and realistic rendering of complex scenes on the internet, which comprises real-time calculation of dynamic shadowing of the complex scene and roaming in the complex scene. The present invention may relate to techniques such as simplification of 3D geometric models, sequential extraction of multi-resolution models, transition between multi-resolution model sequences of simplified 3D geometric models, frustum clipping, real-time shadowing, and data downloading based on the web. The real-time and realistic rendering of the complex scene can be applied in movie and game manufacture, virtual simulation, digital agroforestry, and urban landscape planning, etc.

(16) A method according to the present invention may comprise five steps:

(17) Step 1: Constructing complex scene data. 3D geometric models with high reality are obtained by various modeling methods. A sequence of multi-resolution models is generated for each 3D geometric model according to a predetermined rule. The sequence of the multi-resolution models is output as a file with a standard 3D data format. Scene configuration file and textures and material files are constructed. A downloading file is configured for each scene.

(18) Step 2: Uploading data to a server. Each of the multi-resolution models, the scene configuration file, and the textures and material files is stored as in a binary format. These binary files are converted into the Zip format protected by a password. The zip file has a relatively small size suitable for subsequent transmission. These files and the downloading list are uploaded to the server.

(19) Step 3: Downloading a specified list file after a scene rendering program is activated at a client terminal and then downloading the zip files corresponding to the scene configuration file, the multi-resolution models, and the geomorphic texture files according to the list file. The downloading process is performed in a progressive way. For example, in downloading the sequence of the multi-resolution models, models with a relatively low resolution are downloaded prior to the models with a relatively high resolution. The rendering and the downloading are performed in two threads and thus can be performed simultaneously. If the high-resolution models of the scene have not been downloaded, the lowest-resolution models can be used temporarily instead. The downloaded zip files are read into a memory and unzipped into the binary model files using the password. The binary files are read into the memory and the unzipped files are deleted for security consideration.

(20) Step 4: Rendering the scene. The sequences of the multi-resolution models are organized into Vertex Buffer Objects (VBOs). The VBOs are input to a video memory for accelerating the rendering. Real-time shadowing is employed where a real-time dynamic shadowing effect is achieved by the GPU using OpenGL Shading Language (GLSL) based on Shadow mapping. A frustum is divided in parallel into a plurality of partitions. A shadow mapping is generated for each partition to achieve an anti-aliasing shadowing effect.

(21) Step 5: Generating shadow maps (also called depth cache maps) for the shadows. The shadow maps close to the viewpoint are large in size and updated on a frame-by-frame basis. The shadow maps distant from the viewpoint are small in size and updating frequency thereof decreases accordingly. The shadow map in each frustum is generated by Multiple Render Targets simultaneously. In rendering, the shadowing effect can be achieved by comparing each element in a fragment shader with the shadow maps. Due to the slim branches of a plant model, the shadow may have obvious aliasing effect and uncontinuous branches. In view of this, Gauss filtering may be employed in the fragment shader for anti-aliasing process.

(22) FIG. 1 illustrates an overall flow of the method. FIGS. 2 and 3 illustrate steps of two parts of FIG. 1. FIG. 4 illustrates real-time shadow rendering method of the scene and interactive operation thereof.

(23) 2. Construction of Complex Scene Data

(24) There are many ways for modeling the scene, including but not limited to modeling based on image, modeling based on laser scanning point clouds, model based on hand-drawing pictures, modeling based on growth mechanism of plant, modeling based on curved line or surfaces, modeling based on human interactions using software, or combinations thereof. One of these modeling methods is used to generate 3D geometric models having high reality and the sequence of multi-resolution models are generated for each 3D geometric model taking consideration of requirement of rendering the scene and transmission over the network.

(25) Traditional progressive simplification methods can be used to simplify the three-dimensional manifold models. However, these methods do not work for non-manifolds having complex topology and non-manifold geometric shapes. The method according to the present invention can be applied to non-manifold objects, especially the leave object of the tree. The complex object is replaced with a simple local geometric object defined by local spatial degree. This process is repeated until a simple representative model is generated. The spatial degree of a set of points ψ defined as the volume of a tetrahedron defined by the following four points: the first and second points being two endpoints of the tetrahedron's diameter; the third point being a point in ψ with a largest sum of distances to the first and second points; and the fourth point being a point in ψ with a largest sum of distances to the first, second, and third points. The tetrahedron is obtained by connecting the first to fourth points in sequence. The present invention simplifies a geometric object comprising two polygons. For example, two tetrahedrons have 8 vertexes. Two triangles have 6 vertexes. A triangle and a tetrahedron have 7 vertexes. The geometric object is represented by a tetrahedron having a largest spatial degree. The progressive simplification method maintains consistency of the simplification of texture coordinates and the geometric information. The consistency of the texture coordinates means the consistency between a length direction of a texture image and a direction of a diameter of the set. For a leaf texture of a tree model, a complex mesh model of the leaf is replaced with a tetrahedron in progressive simplification. The texture coordinates are replaced with (0, 0), (1, 0), (1, 1) and (0, 1). The tetrahedron is subject to texture mapping using a right-hand coordinate system. A normal vector of the tetrahedron is used as an axis of the right-hand coordinate system. For further simplification, two adjacent tetrahedrons can be combined into a larger tetrahedron. The normal vector of the tetrahedron is calculated and the numbers of the vertexes and the texture coordinates are determined according to the right-hand rule.

(26) After the multi-resolution models are generated, the lists of the multi-resolution models (MR model sequences) are constructed by selecting specific models. The model selection rule used by the present invention is the distance to the viewpoint based on the complexity of the model. The number of polygons is a linear function or nonlinear function (including the piecewise function) of distance from the viewpoint. For a piecewise function, the distance is divided into k+1 segment by dividing points {d.sub.i}.sub.i=1, 2, . . . , k (0≦d.sub.1≦d.sub.2≦ . . . ≦d.sub.k). The k dividing points divide a non-negative space into (k+1) segments. The numbers of polygons in respective segments are noted as {n.sub.i}.sub.i=1, 2, . . . , k+1 (n.sub.1≧n.sub.2≧ . . . ≧n.sub.k≧n.sub.k+1>0), where n.sub.1 is the number of the finest model's polygons. n.sub.i+1=s.Math.n.sub.i,1≦i≦k,0<s<1. s is a compression factor defined by a user to represent the simplification degree of the model.

(27) FIG. 5 illustrates a sequence of multi-resolution models of a tree. These models take into consideration texture information, and thus texture mapping can be applied to all the multi-resolution models. FIG. 5(a) illustrates a finest model of the tree suitable to be displayed when the tree is close to the view point. Braches of the tree have 15937 leaves each represented by a polygon. Then texture mapping is performed using four channels of text images. The branches have 214785 polygons. Bark mapping is also performed. FIG. 5(b) illuminates simplification of FIG. 5(a). In FIG. 5(b), the leaves have 15937 polygons and branches have 92682 polygons. The complexity of the model as shown in FIG. 5(b) is about 50.6% of the original model. FIG. 5(c) illustrates a simplification of the model as shown in FIG. 5(b). In FIG. 5(c), the leaves have 5688 polygons and the branches have 14968 polygons. The complexity of the model is about 9.7% of the original model. FIG. 5(d) illustrates a simplification of the model as shown in FIG. 5(c). In FIG. 5(d), the leaves have 1401 polygons and the branches have 644 polygons. The complexity of the model is about 0.74% of the original model. FIG. 5(c) illustrates a simplification of the model as shown in FIG. 5(b). In FIG. 5(e), the leaves have 86 polygons and the branches have 644 polygons. The complexity of the model is about 0.26% of the original model.

(28) The resolution of each mode in the sequence of multi-resolution models (corresponding to the simplification degree of the complexity of the model) is defined as a ratio of the number of polygons in the current model to that in the finest model. This is determined by a segmented function, which is shown in below equation (2) for example:

(29) $\begin{array}{cc}\{\begin{array}{c}100\%,0<d_{\mathrm{me}}\le 15\\ 50.0\%,15<d_{\mathrm{me}}\le 50\\ 10.0\%,50<d_{\mathrm{me}}\le 150\\ 1.00\%,150<d_{\mathrm{me}}\le 300\\ 0.25\%,300<d_{\mathrm{me}}<+\infty \end{array}& \left(1\right)\end{array}$

(30) Where d.sub.me represents the distance from the model to the view point. The unit of the distance is meter.

(31) Simplification of the polygons of the branches takes priority over simplification of the polygons of the leaves. The overall reality of the scene is more sensitive to the simplification of the leaves than to that of the branches in that the branches are sheltered by the leaves.

(32) The generated sequence of multi-resolution models is exported as a file of standard 3D data format. The file comprises 3D coordinates of each vertex of the models, connections between respective vertexes (i.e., surface information), texture coordinates, texture file name, and material information. The coordinates of the vertexes, the normal vector, the texture coordinates and the surface information constitute a group. The material information is designated for each group. The vertexes' numbers are designated for each surface. The normal vector's number and/or the numbers of the texture coordinates are also designated. Each file comprises one or more groups. A material file is designated for each file.

(33) The 3D data files are encoded as records of these files. The order for encoding the vertex information and surface information are related to the simplification procedure of the models. For example, the vertexes' coordinates are arranged in a reversed order with respect to the order in which the points are simplified in the progressive simplification procedure. Corresponding normal coordinates and texture coordinates are arranged according. The surfaces are arranged in accordance with the vertexes' order. A surface will be arranged before other surfaces if its vertexes are arranged before the vertexes of the other surfaces. In encoding, the surfaces and the vertexes are arranged together. The vertex information comprises coordinates, normal vector coordinates, and texture coordinates. The order of the vertexes depend on the order of the surfaces. The vertexes of each surface are arranged before the surface and as close to the surface as possible.

(34) In addition to the model files, scene configuration file and texture and material files are also constructed. The scene configuration file describes the layout of each scene, comprising scaling, position, and rotation angle of each model. The texture and material file include material properties, such as ambient light, diffused light, reflected light, transparency, and texture image, of each group.

(35) Furthermore, a geographic model is configured for each scene. The geographic model comprises an elevation map and a texture file. Alternatively, a geometric image can be used as the geographic model. When the geographic image is used as the geographic model, the elevation information is obtained by scaling luminance values of the image.

(36) Finally, all of the above documents are listed in a text file as a download list. The scene configuration file, the geographic files, the textures and material files, and the sequences of multi-resolution models are listed in sequence. The sequence of multi-resolution models are listed in such an order that models having small size and low complexity are listed prior to those having large size and high complexity. This helps a user to download part of the scene data rapidly. The file directing the content and order for downloading is called a downloading list file.

(37) 3. Uploading of Data

(38) Each multi-resolution model, scene configuration file, and texture and material file are converted into a binary format and then compressed into a zip package protected by a password. This reduces file size and ensures data security, facilitating subsequent transmission via network. These files and the downloading list file are uploaded to a server.

(39) 4. Downloading and Importing of Data

(40) Data can be downloaded remotely via the network by a user data downloading module at a client terminal. Only the user of a specific client terminal can download the scene data because the client terminal should know the address of the data priori. The list file is downloaded first. Then the scene configuration file, the geographic file, and the sequences of multi-resolution models are downloaded in sequence in accordance with the list file. In downloading the sequences of the multi-resolution models, the models having a small volume of data and low complexity are downloaded before the models having a large volume of data and high complexity. FIG. 6 illustrates a downloading interface, the upper right portion of which shows the progress of downloading. The progress of downloading can also be seen at a console window in a bottom portion of FIG. 6.

(41) The importing of data can be divided into two phases. In the first phase, the user at the client terminal specifies a scene file, which records all information of a scene to be rendered. The information may include, e.g., the name of the zip file correspond to the scene, the position of the scene, and the elevation and geographic texture of the scene, etc. In the second phase, the zip file is decompressed into a binary file. The binary file is read into a memory and then deleted for security consideration.

(42) The downloading and importing of data can be performed in parallel, wherein the downloading of data is performed by a secondary thread. The scene is rendered while the data is downloading. Models that have not been downloaded can be replaced by simple ones so that the user at the client terminal can see a simplified scene. As more complex models are downloaded, the scene becomes increasingly clear and realistic. FIG. 7 shows, in addition to FIG. 6, a dialog box for opening files. It can be seen that data can be read into a program during the downloading of the data.

(43) 5. Rendering of Scene

(44) 5.1 Smooth Transition of Multi-Resolution Model Sequences

(45) In order to achieve smooth transition between the sequences of multi-resolution models, models that are not in the frustum of the viewpoint are culled before the rendering to increase rendering speed.

(46) In particular, a boundary box is calculated for each model. Coordinates of eight vertexes of the boundary box is calculated in a viewport coordinate system. If none of the projections of the eight vertexes in the viewpoint coordinate system is in the viewport, the model is culled and will not be rendered. However, this process will erroneously cull certain models very close to the viewpoint. The erroneously culled models may appear in the frustum abruptly with movement of the viewpoint, causing jolt in visual perception. In view of this, a limitation is provided that models very close to the viewpoint are always rendered. Although a few trees outside the frustum are rendered, the rendering speed is not affected substantially. The same applies to generation of shadow mapping. Then respective distances from the tree to the viewpoint are calculated and a corresponding multi-resolution model is selected according to a threshold defined by the user.

(47) The rendering speed and effect may vary according to computer hardware and user's requirement. Sometimes the user may prefer fine rendering effect than real-time rendering speed, while sometimes the user may want real-time roaming in the scene and have fewer requirements on the rendering effect. As such, a control interface can be provided for the user to select a desirable model resolution. The user of the client terminal can control the distance ranges corresponding to the multi-resolution models via the interface to adjust the complexity of the scene. In this way, the user can achieve a satisfied effect. The principle of the control is shown in equation (2).

(48) FIG. 8 illustrates the effect of adjusting the scene complexity by controlling the distances corresponding to each multi-resolution model. FIG. 8(a) shows the scene rendering in default configuration. Trees within 11 meters from the viewpoint are rendered by models with the highest reality. The branches, leaves, and shadows all have a good rendering effect. Trees located in a range of 11 meters to 39 meters from the viewpoint are rendered by simplified models. Trees located in a range of 40 meters to 95 meters from the viewpoint are rendered by further simplified models. Trees located beyond 95 meters are rendered by even further simplified models. In this way, the scene is rendered in a fast speed. FIG. 8(b) shows a rendering effect when parameters are adjusted to adapt to a computer with a lower configuration or a slower downloading speed. In this case, some models close to the viewpoint are simplified models. FIG. 8(c) shows a rendering effect when parameters are adjusted to adapt to a computer with a even lower configuration or a even slower downloading speed. In this case, most models close to the viewpoint are simplified models. It can be seen from the figures that even though the simplified models are used for rendering, high reality can be achieved by the present invention. When fine models are downloaded to the computer, the reality can be further enhanced.

(49) 5. 2 Real-Time Shadow Rendering

(50) The shadows are generated by shadow mapping. Each frame are rendered twice. In the first rendering of the frame, the current scene is rendered in a light source frustum (light source space) to obtain a current shadow map. Each pixel in the shadow map represents a depth value of the current position with respect to the light source. The second rendering is performed a frustum of viewpoint (space of viewpoint). Coordinates of each 3D fragment are projected by a fragment shader to the light source space. If the projected depth value is larger than that of the current point in the shadow map, the point is in the shadow.

(51) The shadows obtained by a single shadow mapping may often have severe aliasing. Thus, anti-aliasing process is performed. The frustum of viewpoint is divided into a plurality of partitions and the shadow map in the frustum of light source is calculated for each partition, respectively.

(52) In the first rendering, for each frustum of the light source, models that are not in the current frustum of light source are culled. That is, only models in the current frustum of light source are rendered. In this way, even though the frustum of viewpoint is divided, the geometric complexity for the first rendering does not change substantially. That is, the total number of models to be rendered for generating the plurality of shadow maps after dividing the frustum is substantially the same as that when the frustum is not divided. In the second rendering, the fragment shader first determines to which frustum a pixel belongs and then converts the coordinates of the pixel into the coordinate system of the frustum. Shadowing effect can be obtained by comparison with a corresponding shadow map. The plant model has many interwoven leaves and branches so its shadow may have obvious aliasing and breakpoints. Thus, Gauss filtering is employed in the fragment shader. FIGS. 10(a) and 10(b) show results before and after 3*3 smooth filtering, respectively. FIG. 10(c) shows the result obtained after 5*5 smooth filtering. In the Gauss filtering, the shadow contribution value sf of each point is a Gauss convolution of the shadow depth value in the shadow map. Two different Gauss smooth filtering are designed to achieve different anti-aliasing effect of the shadow. A k*k filter can be expressed as below

(53) $\begin{array}{cc}\mathrm{sf}\left[p\right]=5^{-\left(k-3\right)}\Sigma 2^{-\left({.Math.\Delta .Math.}_1+2\left(4-k\right)\right)}\mathrm{stex}\left[p+\Delta \right]\mathrm{where},\Delta \in \left\{{\left(x,y\right)}^t|x,y=-\frac{k-1}{2},-\frac{k-1}{2}+1\mathrm{.Math.},\frac{k-1}{2}.\right\},& \left(2\right),\end{array}$

(54) k is a positive odd number, ∥Δ∥.sub.1 is the Euclidean norm of a vector Δ(i=1, 2). p represents the normalized device coordinates of a fragment in the coordinate system of the screen obtained by rasterizing a primitive, and stex[x] indicates whether a point x is in the shadow. If the point x is in the shadow, stex[x] returns a value 0, otherwise stex[x] returns a value 1. The value range of sf is between 0.0 and 1.0 and sf is used for illumination calculation of fragment in and not in the shadow.

(55) Illumination calculation in the scene is based on a simple illumination model (Phong illumination model). The illumination comprises diffused light, specular light, and ambient light.

(56) Shadows are added to Phong shading method, wherein for each fragment:

(57) 1) calculating ambient light: Ia;

(58) 2) calculating diffused light: Id;

(59) 3) calculating specular light: Is;

(60) 4) calculating shadowing factor: f;

(61) 5) calculating pixel's RGB value: I=Ia+(Kd*Id+Ks*Is)*f,

(62) where Kd and Ks are the material's reflection factors for diffused light and specular light respectively.

(63) For different frustum partitions, the shadow maps are updated with different frequencies. For the frustum partition closest to the viewpoint, the shadow maps are updated on a frame-by-frame basis. The updating frequency decreases for frustums distance from the viewpoint. The shadow maps have a relatively large size for the frustums close to the viewpoint and a relatively small size for the frustums distant from the viewpoint. For example, for the frustum close to the viewpoint, the shadow map may have a large size, e.g., 4096*4096 pixels to achieve accurate shadow information, while for the frustum distant from the viewpoint the shadow map may have a small size, e.g., 512*512 pixels. Multiple Render Targets technology is employed for each frustum partition to generate the shadow map for each frustum simultaneously.

(64) FIG. 4 illustrates real-time shadow rendering and interactive operation performed off-line after the data is acquired on line.

(65) 6. Results and Conclusions

(66) The method according to the present invention can be implemented by C++ language on a PC with an Intel Core i7 2.66 GHz CPU, 2 GB RAM and an NVIDIA GeForce GTX460 graphic card. The PC is equipped with Windows XP operating system and OpenGL 2.0 graphic function library.

(67) For each tree model, a sequence of multi-resolution models is generated. Each sequence comprises four models with different resolutions. FIG. 12(a) illustrates a complex scene comprising 43350 plant models. The user can roam in the scene in a bird's eye manner. The rendering window has a resolution of 1920*1150 pixels. FIG. 12(b) illustrates a complex scene comprising 43350 plant models. The user can roam in the scene in a bird's eye manner. The rendering window has a resolution of 1920*1150 pixels. The method according to the present invention can implement real-time and realistic rendering of large-scale scene.

(68) Table 1 shows some of the experimental data, comprising the number of frames rendered per second, the number of models in the frustum of viewpoint, the LOD control distance, the number of multi-resolution models for each level, and the total number of polygons in the frustum. The number of multi-resolution models for each level is the number of multi-resolution models displayed in the frustum for the current viewpoint. For example, the numbers of the multi-resolution models for respective levels are 24, 32, 175, and 202, respectively. There are 24 tree models with the highest complexity within 899 centimeters from the viewpoint. There are 175 tree models with the tertiary-highest complexity in a range of 2862-14201 centimeters from the viewpoint. There are 202 tree models with the fourthly-highest complexity beyond 14202 centimeters from the viewpoint.

(69) TABLE-US-00001 TABLE 1 Experimental Data FIG. 12 (a) FIG. 12 (b) FPS 23.91 11.85 Number of Models 433 8667 in the Frustum LOD distances 899; 2861; 14201 205; 529; 1991 Models in Each 24; 32; 175; 202 98; 121; 156; 8292 LOD Level Number of Polygons 1075622 21737965 in the Frustum

(70) The foregoing description is only directed to specific embodiments of the present invention. The scope of the present invention is not limited thereto. Any changes or replacements that are obvious to one of ordinary skill in the art in light of the present invention will fall within the scope thereof. The scope of the present invention is therefore defined by the attached claims.