JP6802129B2 - Information processing equipment, methods and programs - Google Patents

Description

The present invention relates to an information processing apparatus, method and program suitable for parallel processing and capable of performing occlusion determination capable of processing at high speed.

Determining the visible region between objects in a 3D model is a hot topic in the field of CG (computer graphics) in general, and especially in volume rendering and free-viewpoint video generation. As a typical method, the ray casting method shows a schematic example (a schematic example in two dimensions constituting a cross section of a three-dimensional space) in FIG. 1 by performing an intersection test between a light ray and a surface of a target scene. Determine if the point is in the visible region. The ray casting method is generally to perform the following procedure for each ray.

(Procedure 1) The direction of light rays is determined by connecting the target point and the optical center of the camera. FIG. 1 shows an example of the determined ray direction.
(Procedure 2) As an intersection of the light ray and the bounding box of the target scene (a predetermined area of a rectangular parallelepiped set in space and voxel division for judgment), an incident point (light ray). Determine the entry point) and the exit point (the intersection where the light beam exits). In FIG. 1, the bounding box is schematically drawn in a grid pattern, and the incident point and the exit point of an example light ray are shown.
(Procedure 3) For each point on the voxel boundary on the light beam, by scanning the adjacent points on the exit point side sequentially from the incident point, the point that first intersects the 3D model (that is, the object) is visible. It is determined that occlusion has occurred at each point ahead of the point. In FIG. 1, for an example light ray and an object shown in gray, a point determined as a visible region and a point determined as an occlusion beyond the point are shown.

As a basic problem in the ray casting method, there is a problem of how to set an appropriate value for the scan width (stride shown in FIG. 1 as an example) in (Procedure 3). That is, if the stride is reduced, the accuracy is increased but the amount of calculation is increased, and conversely, if the stride is increased, the amount of calculation is reduced but the accuracy is reduced.

Regarding the problems of accuracy and computational complexity that are in a trade-off relationship, Non-Patent Document 1 proposes a method called cone step mapping, and adjusts the stride width by using a pre-processed cone. Further, Non-Patent Document 2 proposes a maximum mipmap method, and uses a mipmap-like data structure to skip an empty space and increase the scanning speed.

Further, as another method for determining the visible region, there is a Z-buffer method (depth buffer method) disclosed in Non-Patent Documents 3 and 4, and the like. In general, for each pixel of the rendered image of the target scene, if it corresponds to the surface of one object, the depth is saved, and such pixels also correspond to the surface of another object at the same time. When doing so, the method is to overwrite the depth value with the smaller one (that is, the depth of the object closer to the camera).

Dummer, J. "Cone Step Mapping: An Iterative Ray-Heightfield Intersection Algorithm (2006)." URL: http://www.lonesock.net/files/ConeStepMapping.pdf 2.3: 4. Tevs, Art, Ivo Ihrke, and Hans-Peter Seidel. "Maximum mipmaps for fast, accurate, and scalable dynamic height field rendering." Proceedings of the 2008 symposium on Interactive 3D graphics and games. ACM, 2008. Z-buffering from Wikipedia, https://en.wikipedia.org/wiki/Z-buffering. Computer Graphics Basics (University of Tsukuba) P-19 http://www.npal.cs.tsukuba.ac.jp/~endo/lecture/2016/cgbasics/08/08_slides.pdf.

However, the above two methods (the ray casting method considering speeding up as in Non-Patent Documents 1 and 2 and the Z-buffer method as in Non-Patent Documents 3 and 4) still have problems. ..

First, the ray casting method in consideration of high speed has a problem that a large amount of capacity and bandwidth of the storage device are consumed because it is necessary to store some result calculated in advance. In addition, it is difficult to handle a high-resolution 3D model because the calculation load for repeatedly performing the intersection determination becomes large. In addition, as a potential risk, the number of times the intersection determination is repeated may fluctuate depending on the target light beam, so that there is also a problem that it is not suitable for parallel processing using a GPU or the like.

Also, in the Z-buffer method, the judgment of whether or not one vertex (vertex of an object) is in the visible area depends on the state of another vertex, and it is possible to speed up with a CPU etc. suitable for sequential processing. There is a problem that it cannot always be easily used with GPUs and the like suitable for parallel processing. Furthermore, in the Z-buffer method, when calculating the distance from each vertex to the camera, it was assumed that occlusion occurred in only a part of the vertices.

In view of the above problems of the prior art, an object of the present invention is to provide an information processing device (as well as a method and a program) suitable for parallel processing and capable of performing occlusion determination capable of high-speed processing. To do.

In order to achieve the above object, the present invention is an information processing apparatus, in which model data of a 3D object is back-projected onto an image area in a predetermined camera arrangement, and the number of 3D objects projected at each point in the image area is used. A projection unit that obtains an overlap map with a certain degree of overlap, an extraction unit that extracts an area in which the overlap degree of the overlap map is 2 or more as an overlap area, and a 3D object of 2 or more corresponding to the overlap area. It is characterized by including a determination unit for specifying an area and determining what causes occlusion in the predetermined camera arrangement based on the positional relationship with the camera center from the area.

According to the present invention, occlusion determination capable of high-speed processing can be performed by a method suitable for parallel processing.

It is a figure which shows the outline of the ray casting method as a conventional method, and a schematic example for explaining a problem. It is a functional block diagram of the information processing apparatus which concerns on one Embodiment. It is a figure which shows the schematic example mainly for explaining the process of the projection part and the extraction part. It is a figure which shows the schematic example mainly for explaining the process of a determination part.

FIG. 2 is a functional block diagram of the information processing device according to the embodiment. As shown in the figure, the information processing device 10 includes a projection unit 1, an extraction unit 2, and a determination unit 3, and the determination unit 3 further includes a specific unit 31, a calculation unit 32, and a shielding determination unit 33. As shown in the figure, the functional outline of each part is as follows.

The projection unit 1 receives model data of a plurality of 3D objects prepared in advance as input, and back-projects the plurality of 3D objects onto an image area when rendering with a predetermined camera arrangement, thereby performing each of the image areas. The overlap degree of the 3D object is counted at the pixel position to obtain the given overlap map, and the overlap map is output to the extraction unit 2.

The extractor 2 extracts a region overlapping degree is in the 2 or more in the overlapping maps obtained from the projection unit 1 as each overlap region, and the information of the overlap region to the determination unit 3 (specific part 31) Output To do.

In the determination unit 3, the occlusion is generated among a plurality of 3D objects in the predetermined camera arrangement when the overlap map is created in the projection unit 1 based on the overlap area obtained from the extraction unit 2. Determine the area within a 3D object. As the element processing for the determination, each part 31 to 33 performs the following processing.

The specific unit 31 corresponds to the overlapping area (that is, back-projected to the overlapping area) for each of the overlapping areas obtained from the extraction unit 2, and the area (in the 3D object). (Partial area) is specified, and the specified result is output to the calculation unit 32. It should be noted that there are two or more corresponding 3D objects and their areas for each overlapping area.

The calculation unit 32 calculates the positional relationship from the camera center at the time of back projection with respect to the corresponding 3D object and the area obtained for each overlapping area in the specific unit 31, and transfers the positional relationship to the shielding determination unit 33. Output.

The occlusion determination unit 33 generates an occlusion based on the positional relationship calculated by the calculation unit 32 from the two or more corresponding 3D objects obtained by the specific unit 31 for each overlapping area and the area thereof. It is determined which one is present, and it is used as the output of the determination unit 3. In the shading determination unit 33, the projection unit 1 renders a plurality of 3D objects with a predetermined camera arrangement as information equivalent to the output (information for identifying which one does not generate occlusion). When back-rendering to the image area of the case, the 3D object that constitutes the visible area and the area thereof may be output.

Hereinafter, the details of the processing contents of each part described in detail will be described. 3 and 4 are diagrams showing a schematic example for the detailed explanation, and will be referred to as appropriate in the following description. Note that FIG. 3 is mainly for explaining the projection unit 1 and the extraction unit 2, and FIG. 4 is mainly for explaining the determination unit 3, and an example used between FIGS. 3 and 4 (object). A schematic example of a 3D object) is common.

<About projection 1>
The projection unit 1 obtains an overlapping map by performing back projection with a predetermined camera arrangement for a plurality of 3D objects to which the model data is input. As is well known, back projection is a process of clarifying how a given 3D model is distributed in an image in a predetermined camera arrangement. In the example of [1] in FIG. 3, four 3D objects M1 to M4 (Idi = 1 to 4 are assigned as IDs respectively) are back-projected to the camera C in a predetermined arrangement, so that the image area is overlapped. It is shown to get the multiplicity map OM. Further, as shown in [2] of FIG. 3, the obtained multiplicity map OM gives a distribution of the multiplicity (the number of overlapping) of 3D objects in the image area. In [2] of FIG. 3, a specific example of the multiplicity is shown by a balloon for explanation, and "multiplicity = 0" for the background area where the 3D object is not back-projected at all, and the 3D objects M3 and M4. "Multiplicity = 1" for the area where only one object is back-projected, and "Multiplicity = 2" for the area where parts of M3 and M4 of the two 3D objects overlap each other. It is shown as an example.

Regarding the specific back projection, the model data of each 3D object (the vertex positions of M objects in the 3D coordinate system of the model (total of N vertices in all M objects) is given by the following equation (1). Data) {P _i ^x , P _i ^y , P _i ^z } (i = 1, 2, ..., N) is back-projected to the (normalized) coordinates (u, v) of the image area. be able to. T ₃₄ is a back-projection matrix.

The back projection is performed on each vertex data {P _i ^x , P _i ^y , P _i ^z } (i = 1, 2, ..., N), and M 3D each at each coordinate (u, v). When at least one vertex of an object is back-projected, the multiplicity map overlapMap (u, v) is created in the projection unit 1 by adding "+1" to the contribution of the multiplicity from the object. Obtainable. Even if two or more vertices of one 3D object are back-projected to the coordinates (u, v), the contribution of the multiplicity from the 3D object is only "+1". .. Therefore, the range of values at each coordinate (u, v) of the multiplicity map overlapMap (u, v) is 0 or more and M or less.

Regarding the representation of the multiplicity map, the code "OM" is used when referring to it as a schematic example in the drawing, and "overlapMap (u, v)" is used to refer to it in mathematical formulas and the like.

Here, the prerequisites in one embodiment of the present invention for realizing the back projection or the like according to the equation (1) are listed below (1) to (5).
(1) Prepare the model data of the 3D object as each vertex data {P _i ^x , P _i ^y , P _i ^z }.
(2) The distinction between individual 3D objects (segment results) in the model data is also given in advance. That is, for each vertex data {P _i ^x , P _i ^y , P _i ^z }, the distinction of which of the M objects belongs is given in advance.
(3) An ID (expressed by the expression Id _i ) is also given to each individual object for giving a distinction to the vertex data.
(4) The projection matrix T ₃₄ and the camera position {C ^x , C ^y , C ^z } to be projected are defined as known ones.
(5) The density of each vertex data {P _i ^x , P _i ^y , P _i ^z } of the 3D object as model data is sufficiently high, and the two vertices v1 and v2 adjacent to each other are inverted by Eq. (1). When projected, it is projected at the same image coordinates (u, v) or at coordinates that are sufficiently close. For example, it is projected onto the coordinates (u, v) and their adjacent coordinates (u ± 1, v) or (u, v ± 1).

<About extraction unit 2>
The extraction unit 2 identifies and extracts each overlapping area from the multiplicity map. Specifically, the duplication map is binary by regarding the points where the multiplicity is 2 or more in the multiplicity map as the foreground and the other points where the multiplicity is 1 or less as the background. By applying an arbitrary region division method to what is regarded as an image, regions having a multiplicity of 2 or more as the foreground are identified and extracted as overlapping regions. For example, by applying the connection area labeling CCL as schematically shown by the following equation, IdaA (u, v), which is the ID of the connection area to which each coordinate (u, v) constituting the foreground belongs, can be obtained. You can do it. Here, CCL {} expresses the process of applying CCL as a function or the like in expressions such as programming.
IdA (u, v) = CCL {overlapMap (u, v)} (2)

In the example of FIG. 3, an example is shown in which two overlapping regions A1 and A2 are identified and then extracted as the region extraction result AM shown in [3] from the multiplicity map shown in [2]. The overlapping area A1 corresponds to the overlapping part of the 3D objects M1 and M2 of [1], and the overlapping area A2 corresponds to the overlapping part of the 3D objects M3 and M4 of [1].

<About specific part 31>
The identification unit 31 identifies which subregion of which 3D object corresponds to each overlapping portion, that is, which is back-projected, as a candidate for the cause of occlusion. Here, in one embodiment, the result when the specific object is already back-projected by the projection unit 1 (the result of which 3D object is back-projected to (u, v)) is set at each pixel position (u, v). It may be realized by referring to what is memorized in v).

However, in one embodiment, the specific unit 31 may specify the candidate by re-executing the same back projection as that performed by the back projection unit 1. According to the embodiment, the memory area to be stored can be omitted. When the number of cameras is large, the memory area becomes enormous, but in the one embodiment, such memory consumption can be avoided.

In the example of FIG. 4, the overlapping area A2 of the same area extraction result AM as that of [3] of FIG. 3 is processed by the specific unit 31, so that the partial areas M4-O2 and the 3D object of the 3D object M4 are processed. This is an example in which two subregions with M3-O2 are identified as candidates for occlusion.

<About calculation unit 32>
In the calculation unit 32, the subregions of a plurality of 3D objects that are candidates for occlusion specified for each overlapping region in the specific unit 31 are aligned with the camera center during back projection by the specific unit 31 (and projection unit 1). Calculate the positional relationship. In one embodiment, the positional relationship may be calculated as the average distance (oiler distance, etc.) between the center of the camera and each point in the subregion of each 3D object. (Note that the average distance is the center of the camera (1 point) and each point i = 1,2, ..., M in the partial area of each 3D object (M is the total number of points in the partial area of the 3D object). The distance may be D (i) (i = 1,2, ..., M), and the sum of each distance D (i) with respect to M points may be obtained by dividing by the number M. )

<About the shielding judgment unit 32>
In the occlusion determination unit 32, among the subregions of a plurality of 3D objects that are candidates for occlusion occurrence specified for each overlapping region based on the positional relationship calculated by the calculation unit 31, the subregions in which occlusion is actually generated are selected. Identify. Specifically, the one other than the one determined to be closest to the center of the camera in the positional relationship is specified as generating the occlusion. If the calculation unit 31 calculates the positional relationship using the average Euler distances in Eqs. (3) and (4), the ones other than the one with the minimum distance are specified as causing occlusion.

For example, in the example of FIG. 4, of the two subregions of the 3D object M4 subregion M4-O2 and the 3D object M3 subregion M3-O2 as candidates corresponding to the overlapping region A2, the camera C The subregion M4-O2 closest to the center of the camera is determined not to generate occlusion, and the subregion M3-O2 farther than this is determined to generate occlusion. In one embodiment of the present invention, the occlusion determination is determined in units of subregions of the object. (That is, it is omitted to make an occlusion judgment by further distinguishing within the partial area, for example, distinguishing what is on the front side (without occlusion) or on the back side (with occlusion) when viewed from the center of the camera.)

As described above, according to the present invention, it is possible to perform occlusion determination that can be used when determining the visible region in real time using a GPU or the like, and each process is suitable for parallel processing of the GPU or the like. It is configured and can be realized as an automatic process that does not require manual designation work. Here, in particular, the present invention is configured to be suitable for parallel processing because iterative processing as in the conventional method is not required.

The present invention can also be provided as a program that causes a computer to function as an information processing device 10. A well-known hardware configuration such as a CPU (central processing unit), memory, and various I / Fs can be adopted for the computer, and the CPU executes instructions corresponding to the functions of each part of the information processing unit 10. It will be. In addition, the computer is further equipped with a GPU (graphic processing unit) capable of performing parallel processing at a higher speed than the CPU, and the GPU reads a program for all or any part of the functions of the information processing device 10 instead of the CPU. You may want to do it.

10 ... Information processing device, 1 ... Projection unit, 2 ... Extraction unit, 3 ... Judgment unit

Claims (6)

A projection unit that back-projects the model data of a 3D object onto an image area in a predetermined camera arrangement to obtain an overlap map with a degree of overlap, which is the number of projected 3D objects at each point in the image area .
An extraction unit that extracts regions having a multiplicity of 2 or more in the overlap map as overlapping regions, and an extraction unit.
A determination unit that identifies an area for each of two or more 3D objects corresponding to the overlapping area, and determines which area causes occlusion in the predetermined camera arrangement based on the positional relationship with the camera center.
An information processing device characterized by being equipped with. The information processing apparatus according to claim 1 , wherein the extraction unit extracts by a connection region labeling method or other domain decomposition method. The information processing apparatus according to claim 1 or 2 , wherein the determination unit specifies the model data of the plurality of 3D objects by back-projecting the model data of the plurality of 3D objects onto each of the overlapping regions. The determination unit according to any one of claims 1 to 3 , wherein the determination unit determines that a region other than the one having the minimum distance from the camera center is determined to generate occlusion in the predetermined camera arrangement. Information processing device. A projection step in which model data of a 3D object is back-projected onto an image area in a predetermined camera arrangement to obtain an overlap map with a degree of overlap, which is the number of projected 3D objects at each point in the image area .
An extraction step in which regions having a multiplicity of 2 or more in the overlap map are extracted as overlapping regions, and
A determination step in which an area for each of two or more 3D objects corresponding to the overlapping area is specified, and an occlusion is generated in the predetermined camera arrangement based on the positional relationship with the camera center from the area. A method characterized by being prepared. Computer,
A projection unit that back-projects the model data of a 3D object onto an image area in a predetermined camera arrangement to obtain an overlap map with a degree of overlap, which is the number of projected 3D objects at each point in the image area .
An extraction unit that extracts regions having a multiplicity of 2 or more in the overlap map as overlapping regions, and an extraction unit.
A determination unit that specifies an area for each of two or more 3D objects corresponding to the overlapping area and determines an area that causes occlusion in the predetermined camera arrangement based on the positional relationship with the camera center. A program that functions as an information processing device, which is characterized by being provided.

Images