RENDERING BASED GENERATION OF OCCLUSION CULLING MODELS

Abstract

A method and image processing apparatus for creating simplified representations of an existing virtual 3D model for use in occlusion culling. The existing virtual 3D model is received and a visual hull construction is performed on the existing virtual 3D model using an approximate voxel volume consisting of a plurality of voxels, the voxel volume fully encloses the existing virtual 3D model, and a set of projections from a plurality of viewing angles to provide a visual hull of the existing 3D model. The volumetric size of the visual hull of the existing 3D model is increased to envelop the existing virtual 3D model to provide the visual hull as an occludee model, and the volumetric size of the visual hull of the existing 3D model is decreased to be enveloped by the existing virtual 3D model to provide the visual hull as an occluder model. The occludee model and the occluder model are used during runtime in a 3D virtual environment for occlusion culling.

The present invention provides simplified representations for occlusion culling in a simple and computationally cost effective manner.

Claims

1. A method for creating simplified representations of an existing virtual 3D model for use in occlusion culling, said method comprising the steps of: receiving said existing virtual 3D model; performing visual hull construction on said existing virtual 3D model using an approximate voxel volume consisting of a plurality of voxels, said voxel volume fully enclosing said existing virtual 3D model and a set of projections from a plurality of viewing angles to provide a visual hull of said existing 3D model; increasing the volumetric size of said visual hull of said existing 3D model to envelop said existing virtual 3D model to provide said visual hull as an occludee model; decreasing the volumetric size of said visual hull of said existing 30 model to be enveloped by said existing virtual 3D model to provide said visual hull as an occluder model; and using said occludee model and said occluder model during runtime in a 3D virtual environment for occlusion culling.

2. The method according to claim 1, wherein increasing the volumetric size of said visual hull comprises adding at least one outer layer of voxels to said visual hull to provide said occludee model, and wherein decreasing the volumetric size comprises removing at least one outer layer of voxels from said visual hull to provide said occluder model.

3. The method according to claim 2, further comprising an additional step of adding or removing a limited layer of voxels to or from said visual hull, said limited layer being limited to predetermined portions of said visual hull.

4. The method according to claim 1, further comprising a step of converting said visual hull into a polygonal mesh representation prior to said steps of increasing and decreasing the volumetric size.

5. The method according to claim 4, wherein increasing and decreasing the size comprises resizing the polygon mesh representation of the visual hull.

6. A method for creating simplified representations of an existing virtual 3D model for use in occlusion culling, said method comprising the steps of: receiving said existing virtual 3D model; performing visual hull construction on said existing virtual 3D model, said visual hull construction comprising: providing an approximate voxel volume consisting of a plurality of voxels, said voxel volume fully enclosing said existing virtual 3D model; providing a first set of projections of said existing virtual 3D model from a plurality of viewing angles; providing a second set of projections of said existing virtual 3D model from said plurality of viewing angles; adding at least one layer of pixels to the outer border of each projection in said first set of projections; removing at least one layer of pixels from the outer border of each projection in said second set of projections; using said first set of projections and said approximate voxel volume to provide a first visual hull of said existing 3D model as an occludee model; using said second set of projections and said approximate voxel volume to provide a second visual hull of said existing 3D model as an occluder model; and using said occludee model and said occluder model during runtime in a virtual environment for occlusion culling.

7. The method according to claim 6, wherein said plurality of viewing angles are uniformly spaced apart by a predetermined repetition distance around the existing virtual 3D model.

8. The method according to claim 7, wherein at least one opening of said existing virtual 3D model defines an angular range in which a viewing angle results in a view through said at least one opening, and wherein the predetermined repetition distance of the plurality of viewing angles is selected to provide at least one viewing angle within said angular range.

9. The method according to claim 8, wherein the size of said voxels in said voxel volume during said visual hull construction is configured such that said view through said at least one opening corresponds to at least two voxels.

10. The method according to claim 6, wherein the resolution of the rendering of the existing 3D model during said visual hull construction is configured such that a pixel of said rendering corresponds to at least one voxel.

11. The method according to claim 6, wherein said occludee model and said occluder model is also used for shadow rendering during runtime in said 3D virtual environment.

12. The method according to claim 6, further comprising a step of converting said occludee model and said occluder model into a polygonal mesh representation.

13. An image processing system for creating simplified representations of an existing virtual 3D model for use in occlusion culling, said image processing system comprising: means to receive said existing virtual 3D model; means to perform a visual hull construction on said existing virtual 3D model using an approximate voxel volume consisting of a plurality of voxels, said voxel volume fully enclosing said existing virtual 3D model and a projection from a plurality of viewing angles to provide a visual hull of said existing 3D model; means to increase the volumetric size of said visual hull of said existing 3D model to envelop said existing virtual 3D model to provide said visual hull as an occludee model; means to decrease the volumetric size of said visual hull of said existing 3D model to be enveloped by said existing virtual 3D model to provide said visual hull as an occluder model; and means to perform occlusion culling using said occludee model and said occluder model during runtime in a 3D virtual environment.

14. (canceled)

15. The image processing system according to claim 13, wherein at least one of said means are located on a remote computing device or a plurality of remote computing devices.

15. (canceled)

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] The various aspects of the invention, including its particular features and advantages, will be readily understood from the following detailed description and the accompanying drawings, in which:

[0029] FIG. 1 shows an example of polygon based three-dimensional graphics image;

[0030] FIG. 2 illustrates a conceptual image processing system according to a currently preferred embodiment of the invention;

[0031] FIG. 3 shows a flowchart of method steps according to an embodiment of the invention;

[0032] FIG. 4a-e shows intermediate visualizations of the graphics objects generated at different steps of the method shown in FIG. 3;

[0033] FIG. 5 schematically illustrates a step to configure a repetition distance of the viewing angles; and

[0034] FIG. 6 shows a flowchart of method steps according to an alternative solution using the general inventive concept.

DETAILED DESCRIPTION

[0035] The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which currently preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided for thoroughness and completeness, and fully convey the scope of the invention to the skilled addressee. Like reference characters refer to like elements throughout.

[0036] The process of connecting three-dimensional vertices to form a representation of a graphical image may be referred to as creating a polygon mesh. FIG. 1 illustrates an exemplary three-dimensional graphics image, in the form of a “bunny”, which have been tiled into such a polygon mesh. The bunny 102 is here represented by a large plurality of polygons. In a system with a 3D graphics accelerator, an application program generates three-dimensional geometry data 102 including information corresponding to points on the surface of a three-dimensional graphical image. These points are usable as vertices of polygons which, when connected, may be rendered to form a representation of the graphical image such as the “bunny” shown in FIG. 1. Typically, the application program transfers the three-dimensional geometry data to a graphics accelerator and renders the encoded polygons on a display e.g. a computer screen.

[0037] The general concept of the present invention may typically be implemented in a image processing system 200, such as the conceptual image processing system shown in FIG. 2, including a general purpose processor 202 e.g. a user controlled personal computer, an application specific processor, a circuit containing processing components, a group of distributed processing components, a group of distributed computers configured for processing, etc. The processor 202 may be or include any number of hardware components for conducting data or signal processing or for executing computer code stored in memory. The memory may be one or more devices for storing data and/or computer code for completing or facilitating the various methods described in the present description. The memory may include volatile memory or non-volatile memory. The memory may include database components, object code components, script components, or any other type of information structure for supporting the various activities of the present description. According to an exemplary embodiment, any distributed or local memory device may be utilized with the systems and methods of this description. According to an exemplary embodiment the memory is communicably connected to the processor 202 (e.g., via a circuit or any other wired, wireless, or network connection) and includes computer code for executing one or more processes described herein.

[0038] However, as is shown in the conceptual illustration in FIG. 2, the general functionality of the inventive image processing system 200 may also and/or alternatively be provided in a distributed environment, for example by means of a distributed image processing system 200. In such an implementation, the image processing system 200 may be configured to comprise a user controlled computing device 202 (e.g. the user controlled personal computer) connected to a server/database arrangement 204 over the Internet 206. Accordingly, resources for performing the inventive concept may typically be divided between the computing device 202 and the server/database arrangement 204.

[0039] Further to reducing the hardware constrains on the user controlled computing device 202, it would according to the invention be possible to e.g. “on-demand” provide a user/customer with the functionality provided by means of the inventive concept. As an example, a user wanting to generate a simplified representation of an existing virtual 3D model for occlusion culling may, through a user interface shown on the computing device 202, access a computer implementation of the method running on the server 204. Alternatively, the computing device 202 may be provided with software for producing the original image (such as for example 3D Studio Max, Maya, etc.), where the software running on the computing device 202 is adapted to access/interact with (by means of e.g. an API and “on-demand”, as a subscription, as a fixed service, etc.) a computer implementation of the inventive concept running on the server 204.

[0040] Now referring to FIG. 3, the present invention is illustrated as a flowchart of steps in a method, and FIG. 4a-e in which intermediate visualizations of the virtual graphics objects obtained at each step of the method is schematically shown. The first step S1 comprises receiving an existing virtual 3D model 400, shown in FIG. 4a, by the computing device 202. As described above in connection with FIG. 2, the inventive concept can then further be performed on the ‘local’ computing device 202 or be performed remotely by one or several computing units 204 understood as e.g. a cloud implementation of the inventive concept. The z-axis of the 3D model 400 shown in FIG. 4a is also marked in order to relate to the subsequent illustrations.

[0041] In the next step S2 the 3D model 400 is subjected to a visual hull construction illustrated in FIG. 4b using a voxel volume (not shown) formed by a plurality of voxels fully enclosing the 3D model 400 and a plurality of viewing angles, herein shown as four viewing angles 401, 402, 403, 404. Note that to simplify understanding the 3D model 400 is illustrated in FIG. 4B in 2D with the z-axis shown. The process, e.g. the visual hull construction is however a 3D reconstruction and should not be construed as limited to two dimensions by the appended drawings. As shown in FIG. 4b each of the viewing angles 401, 402, 403, 404 provides a silhouette cone. Then, during the visual hull construction, voxels which do not form part of the silhouettes, i.e. the foreground images comprising the 2D projection of the original 3D object onto the voxel volume are removed from the plurality of voxels in the voxel volume. The resulting model 405, known as a visual hull 405 of the original 3D object 400 is the intersection of all the silhouette cones from the viewing angles 401, 402, 403, 404. The outline of the resulting visual hull 405 is shown in FIG. 4c. Note that due to the small number of viewing angles, in this case four, the visual hull 405 has an irregular shape compared to the original 3D model 400.

[0042] There are several factors which affect the accuracy of the visual hull 405. For example, the resolution of the 3D model 400 will determine how precisely the voxels can be removed during the visual hull construction. Likewise, the size of the voxels can also be set in order determine how precisely the voxels can be removed. Accordingly, the resolution of the rendering of the original 3D model 400 is usually set higher than the voxel size in order to provide a suitable basis for the visual hull 405. For example, the user can set the resolution, i.e. pixels provided by the rendering, such that a pixel will correspond to at least one voxel.

[0043] Further, the fidelity of the visual hull 405 to the 3D model 400 will depend on the number of viewing angles used to construct the visual hull 405. The visual hull 405 shown is constructed using only four viewing angles 401, 402, 403, 404 and is therefore not a precise match and differs in shape from the 3D model 400. By using more viewing angles a closer match and fidelity to the original model 400 may be achieved. Typically, on the order of hundreds of viewing angles can be used to provide a visual hull. Note that the viewing angles 401, 402, 403, 404 are spaced apart. During the visual hull construction the viewing angles 401, 402, 403, 404 can be spaced apart by e.g. a predetermined repetition distance around the 3D model 400. The repetition distance may be uniform in order to provide a non-biased view of the 3D model 400. It is also possible to provide more viewing angles from a specific side of the 3D model 400 to provide e.g. a view dependent visual hull.

[0044] In summary, the accuracy i.e. fidelity of the visual hull construction will depend on the number of viewing angles as well as the resolution of the rendering of the original 3D object 400, and the voxel size. The resolution and voxel size are interlinked and the skilled person realizes that each of them can be determined by the user, or automatically according to a criterions enabling a match between the two.

[0045] In the next step S3, the volumetric size of the visual hull 405 is increased to provide an occludee model 406, and decreased to provide an occluder model 407. The visual hull 405, the occludee model 406 illustrated by the dashed outline and the occluder model 407 illustrated by the dotted outline are shown in FIG. 4c. Note that the occludee model 406 is larger than the visual hull 405, and that the occluder model 407 is smaller than the visual hull 405. In order to increase or decrease the volumetric size, at least one outer layer of voxels is either added or removed from the visual hull 405. At least one layer means that there could be just one layer of voxels which is added or removed, but also that more than one layer can be added or removed such as three, five, ten or even more layers depending on the application. The voxels belonging to the outer layer can be identified e.g. through calculating which voxels are not surrounded on all sides by other voxels.

[0046] Further, some portions of the visual hull 405 can be of larger importance than others, such as e.g. portions of the visual hull 405 which would be removed through removing an outer layer of voxels. Likewise, a particular portion of the visual hull 405 can be more or less sensitive to addition of a layer of voxels and can thereby be subjected to such an additional step. The specifying of such portions, or limited layers, of the visual hull 405 can be provided automatically by a calculating which portions are sensitive to removal or addition of voxels, applying a weighting mask, or manually by a user marking important portions of the existing 3D model 400 which should not be removed.

[0047] In the next step S4 illustrated in FIG. 4d, the occludee model 407, which is smaller than the original object 400, is used in occlusion culling to determine if the original 3D model 400 would occlude another virtual object 408. Likewise as illustrated in FIG. 4e the occluder model 406, which is larger than the original object 400, is used to determine if the original object 400 would be occluded by another object 400. The occludee model 407 and occluder model 406 provided are guaranteed to be larger or smaller than the original 3D model 400 by the visual hull construction and the previous step S3 of addition or removal of layers. The occludee model 407 and occluder model 406 are used to determine if the original 3D model 400 is to be rendered or not during runtime in a 3D virtual environment. The 3D virtual environments where occlusion culling is used to reduce to rendering load are for example architectural walkthroughs, simulations, medical visualization and computer games. Note that in FIG. 4d the occluder model 407 which is smaller than the original 3D model 400 still occludes the other 3D object 408 and that object will therefore not be rendered. In FIG. 4e however, the occludee model 406 which is larger than the original 3D model 400 is not occluded by the other 3D object 408, and therefore the original 3D model 400 will be rendered.

[0048] The method can also further comprise a step of converting the occluder model 407 and occludee model 406 into polygonal mesh representation prior to the occlusion culling process. As an alternative (not shown) the visual hull 405 can also be converted into a polygonal mesh representation which is then resized, i.e. one instance resized larger and one instance resized smaller, and provided as an occludee model and a occluder model.

[0049] FIG. 5 illustrates a step of determining the repetition distance of the viewing angles used for the visual hull construction. The illustration is shown in 2D but is of course valid for the 3D case described. As described above, the plurality of viewing angles are typically spaced apart by a predetermined repetition distance around the 3D model 400. For example, the viewing angles may be spaced apart uniformly around the 3D model 400, or more viewing angles are placed on one or more specific sides of the 3D model 400 in order to provide a view dependent visual hull.

[0050] In FIG. 5 the circle 502 schematically illustrates where viewing angles may be placed around a 3D model 501. The size, i.e. radius, of the circle 502 is generally not important, and should only be construed as where the viewing angles may be placed around the 3D model 501. The skilled addressee realized that the viewing angles may be placed at different distances around and from the 3D model 501 and still realize the inventive concept.

[0051] The 3D model 501 shown in FIG. 5 has openings which need to be modeled on the visual hull in order to effectively process the occlusion culling and correctly identify if an object actually occludes another or not. As shown in FIG. 5 the 3D model 501 comprises two openings, i.e. through going holes. In order to accurately model these openings on the visual hull, the viewing angles will be required to be spaced apart with a repetition distance small enough to provide a view through the openings. Accordingly, angular ranges around the existing virtual 3D model in which a viewing angle results in a view through the openings are calculated. For the two openings shown this results in a first angular range θ.sub.1 and a second angular range θ.sub.2. The first angular range θ.sub.1 corresponds to a large repetition distance 503 and the second angular range θ.sub.2 corresponds a small repetition distance 504. Hence, in order to provide a view through the smallest opening the repetition distance is therefore set to at least the small repetition distance 504. Hence, by uniformly distributing a plurality of viewing angles around the original model 501 having a uniform predetermined repetition distance corresponding to the small repetition distance 504 at least one view through the large opening and the small opening is guaranteed. Alternatively, the viewing angles may be spaced more sparsely around the other portions of the 3D model 501 and close enough around the first angular range θ.sub.1 and the second angular range θ.sub.2to provide a view through those openings such that a more view dependent visual hull is provided.

[0052] Further, the size of the voxels in the voxel volume can be configured such that the view through the openings corresponds to at least two voxels. In other words, the size of the voxels is configured such that the width of the smallest opening corresponds to the width of at least two voxels.

[0053] FIG. 6 shows a flowchart of method steps according to an alternative solution of the general inventive concept. The first step S61 comprises receiving an existing virtual 3D model by e.g. the computing device 202. Then visual hull construction is performed under the steps S62-S68, where in the next step S62, an approximate voxel volume is provided. The approximate voxel volume consists of a plurality of voxels, and the approximate voxel volume fully encloses the existing virtual 3D model which has been received.

[0054] The next steps S63 and S64, comprises providing a first respectively a second set of projections of the existing virtual 3D model from a plurality of viewing angles. The projections should be interpreted as the silhouettes, i.e. the 2D projections of the existing virtual 3D model which together with the viewing angles can provide a silhouette cone. The first and second set thus comprises an identical set of projections from the same viewing angles during the steps S63 and S64.

[0055] Then, in the next step S65, at least one layer of pixels is added to the outer border of each projection in the first set of projections. The size of each projection in the first set of projections is thus increased by at least one outer layer of pixels.

[0056] Similarly, in the next step S66, at least one layer of pixels is removed from the outer border of each projection in the second set of projections. The size of each projection in the second set of projections is thus decreased by at least one outer layer of pixels.

[0057] In the next step S67, the first set of projections with an increased size due to the addition of at least one layer of pixels to the outer border and the approximate voxel volume are used to provide a first visual hull of the existing 3D model as an occludee model. The increased size of the projections in the first set of projections will provide larger silhouette cones, which results in less voxels being removed from the plurality of voxels in the approximate voxel volume. Thus, the resulting first visual hull is guaranteed to be larger than the existing virtual 3D model.

[0058] In the next step S68, the second set of projections with a decreased size due to the removal of at least one layer of pixels from the outer border and the approximate voxel volume are used to provide a second visual hull of said existing 3D model as an occluder model. The decreased size of the projections in the second set of projections will provide smaller silhouette cones, which results in more voxels being removed from the plurality of voxels in the approximate voxel volume. Thus, the resulting second visual hull is smaller than the existing virtual 3D model.

[0059] Finally, in step S69, the occludee model and the occluder model are used during runtime in a 3D virtual environment for occlusion culling.

[0060] Hence, the resizing in the alternative solution takes place prior to forming the visual hulls using the first and second set of projections and the viewing angles to form the occluder and occludee model.

[0061] The present disclosure contemplates methods, systems and program products on any machine-readable media for accomplishing various operations. The embodiments of the present disclosure may be implemented using existing computer processors, or by a special purpose computer processor for an appropriate system, incorporated for this or another purpose, or by a hardwired system. Embodiments within the scope of the present disclosure include program products comprising machine-readable media for carrying or having machine-executable instructions or data structures stored thereon. Such machine-readable media can be any available media that can be accessed by a general purpose or special purpose computer or other machine with a processor. By way of example, such machine-readable media can comprise RAM, ROM, EPROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code in the form of machine-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer or other machine with a processor. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a machine, the machine properly views the connection as a machine-readable medium. Thus, any such connection is properly termed a machine-readable medium. Combinations of the above are also included within the scope of machine-readable media. Machine-executable instructions include, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing machines to perform a certain function or group of functions.

[0062] Although the figures may show a specific order of method steps, the order of the steps may differ from what is depicted. Also two or more steps may be performed concurrently or with partial concurrence. Such variation will depend on the software and hardware systems chosen and on designer choice. All such variations are within the scope of the disclosure. Likewise, software implementations could be accomplished with standard programming techniques with rule based logic and other logic to accomplish the various connection steps, processing steps, comparison steps and decision steps. Additionally, even though the invention has been described with reference to specific exemplifying embodiments thereof, many different alterations, modifications and the like will become apparent for those skilled in the art. Variations to the disclosed embodiments can be understood and effected by the skilled addressee in practicing the claimed invention, from a study of the drawings, the disclosure, and the appended claims. Furthermore, in the claims, the word “comprising” does not exclude other elements or steps, and the indefinite article “a” or “an” does not exclude a plurality.