[go: up one dir, main page]

WO2018179253A1 - ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム - Google Patents

ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム Download PDF

Info

Publication number
WO2018179253A1
WO2018179253A1 PCT/JP2017/013326 JP2017013326W WO2018179253A1 WO 2018179253 A1 WO2018179253 A1 WO 2018179253A1 JP 2017013326 W JP2017013326 W JP 2017013326W WO 2018179253 A1 WO2018179253 A1 WO 2018179253A1
Authority
WO
WIPO (PCT)
Prior art keywords
polygon
point
polygon model
intersecting
unit
Prior art date
Application number
PCT/JP2017/013326
Other languages
English (en)
French (fr)
Inventor
済 川又
Original Assignee
株式会社ソニー・インタラクティブエンタテインメント
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 株式会社ソニー・インタラクティブエンタテインメント filed Critical 株式会社ソニー・インタラクティブエンタテインメント
Priority to PCT/JP2017/013326 priority Critical patent/WO2018179253A1/ja
Priority to US16/494,023 priority patent/US11107278B2/en
Priority to JP2019508036A priority patent/JP6700480B2/ja
Publication of WO2018179253A1 publication Critical patent/WO2018179253A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation

Definitions

  • the present invention relates to a polygon model generation device, a polygon model generation method, and a program.
  • Patent Document 1 discloses a technique for generating a polygon model arranged in a virtual space from an image including depth information acquired by photographing an object arranged in a real space. Are listed.
  • an initial sculpture including a triangular polygon is generated in a virtual space. And the point (data point) in the virtual space matched with the combination with the pixel in the acquired image and the depth of the said pixel is specified. Then, ray casting is performed on the identified data point from the origin, and the intersection of the ray cast ray and the polygon is identified. The initial sculpture is deformed by moving the vertex of the polygon according to the length between the specified intersection and the data point.
  • the inventors are examining a new method for generating a polygon model along the outline of a point cloud.
  • point cloud data indicating a point cloud in the virtual space is generated from an image including depth information. For example, by performing Delaunay triangulation (tetrahedron division) using points belonging to the point group as Delaunay points, a polygon model including a plurality of polygons each having a point belonging to the point group as a vertex is generated.
  • the polygon model generated in this way does not have an outer surface that follows the outline of the point cloud.
  • the polygon model is made closer to the one along the outline of the point group by deleting a polygon including a side longer than a predetermined length from the polygon model.
  • a polygon model with sufficient accuracy along the outline of the point group may not be obtained due to the influence of the density of the point group.
  • the present invention has been made in view of the above problems, and one of its purposes is to provide a polygon model generation device, a polygon model generation method, and a program capable of accurately generating a polygon model along the outline of a point cloud. There is.
  • a polygon model generation device includes a polygon model generation unit that generates a polygon model including a plurality of polygons based on point cloud data indicating a point cloud in a virtual space, An intersecting polygon identifying unit for identifying an intersecting polygon that is a polygon that intersects a line segment having both ends of a first position where the polygon model is desired in a virtual space and a second position that is a position of a point belonging to the point group; And an intersecting polygon deleting unit that deletes the intersecting polygon from the polygon model.
  • an image acquisition unit that acquires an image obtained by photographing a subject in a real space, and points that belong to the image based on the image correspond to points on the subject in the real space, respectively.
  • a point cloud data generating unit for generating point cloud data
  • a corresponding camera position specifying unit for specifying a position in the virtual space corresponding to a position in the real space of the real camera when the subject is photographed
  • the intersecting polygon specifying unit specifies the intersecting polygon with the position specified by the corresponding camera position specifying procedure as the first position.
  • an invisible polygon specifying unit that specifies an invisible polygon that is an invisible polygon in any of one or a plurality of virtual cameras set in the virtual space; and And an invisible polygon deletion unit to be deleted from the model.
  • a point density value determining unit that determines a point density value associated with a point belonging to the point group, and a length of a side constituting the polygon
  • a long-side polygon deletion unit that deletes the polygon from the polygon model when the value exceeds a threshold value corresponding to the value of the point density associated with the end point of the side.
  • the intersecting polygon identifying unit identifies the intersecting polygon for only at least a part of the points having the point density value larger than a predetermined value as the second position. May be.
  • the polygon model generation method includes a polygon model generation step of generating a polygon model including a plurality of polygons based on point cloud data indicating a point cloud in the virtual space, and the polygon in the virtual space.
  • An intersecting polygon identifying step for identifying an intersecting polygon that is a polygon that intersects a line segment having both ends of a first position where a model is desired and a second position that is a position of a point belonging to the point group; and And an intersecting polygon deleting step for deleting from the polygon model.
  • the program according to the present invention provides a polygon model generation procedure for generating a polygon model including a plurality of polygons based on point cloud data indicating a point cloud in the virtual space, and a first request for the polygon model in the virtual space.
  • An intersecting polygon identifying procedure for identifying an intersecting polygon, which is the polygon that intersects a line segment having both ends of one position and a second position that is a position of a point belonging to the point group; and deleting the intersecting polygon from the polygon model The computer executes the intersecting polygon deletion procedure.
  • FIG. 1 is a configuration diagram of a polygon model generation apparatus 10 according to an embodiment of the present invention.
  • the polygon model generation apparatus 10 according to the present embodiment is a computer such as a game console or a personal computer, for example.
  • the polygon model generation apparatus 10 according to the present embodiment includes, for example, a processor 12, a storage unit 14, an operation unit 16, and a display unit 18.
  • the processor 12 is a program control device such as a CPU that operates according to a program installed in the polygon model generation apparatus 10, for example.
  • the processor 12 according to the present embodiment also includes a GPU (Graphics Processing Unit) that draws an image in a frame buffer based on graphics commands and data supplied from the CPU.
  • GPU Graphics Processing Unit
  • the storage unit 14 is a storage element such as a ROM or a RAM, a hard disk drive, or the like.
  • the storage unit 14 stores a program executed by the processor 12 and the like.
  • a frame buffer area in which an image is rendered by the GPU is secured.
  • the operation unit 16 is a user interface such as a keyboard, a mouse, and a game console controller, and receives a user operation input and outputs a signal indicating the content to the processor 12.
  • the display unit 18 is a display device such as a liquid crystal display, and displays various images in accordance with instructions from the processor 12.
  • the polygon model generation apparatus 10 may include a communication interface such as a network board, an optical disk drive that reads an optical disk such as a DVD-ROM or a Blu-ray (registered trademark) disk, a USB (Universal Serial Bus) port, and the like. .
  • a communication interface such as a network board
  • an optical disk drive that reads an optical disk such as a DVD-ROM or a Blu-ray (registered trademark) disk, a USB (Universal Serial Bus) port, and the like.
  • FIG. 2 is a diagram schematically illustrating an example of a state in which the subject 20 according to the present embodiment is arranged in the real space 22.
  • a real object having a shape like a Stanford bunny is shown as an example of the subject 20.
  • FIG. 3 is a diagram schematically illustrating an example of a state in which a polygon model imitating the subject 20 is arranged in the virtual space 32.
  • the polygon model generation apparatus 10 for example, based on one or a plurality of photographed images obtained by photographing the subject 20 illustrated in FIG. 3 is generated.
  • the finally generated polygon model is referred to as a final polygon model 30.
  • the 3 is composed of a plurality of polygons 34.
  • the virtual space 32 according to the present embodiment is a space that models the real space 22.
  • the position and orientation of the subject 20 in the real space 22 are reflected in the position and orientation of the final polygon model 30 in the virtual space 32.
  • the position in the real space 22 is expressed in the X1Y1Z1 coordinate system
  • the position in the virtual space 32 is expressed in the X2Y2Z2 coordinate system.
  • the polygon model generation apparatus 10 first acquires one or a plurality of photographed images obtained by photographing the subject 20 with the real camera 24.
  • a captured image may be simultaneously captured by each of the plurality of real cameras 24, and a captured image of the subject 20 may be captured from various directions by one real camera 24.
  • the real camera 24 may be a camera capable of capturing a captured image including depth information, such as a stereo camera or a camera with an infrared distance sensor.
  • a depth image indicating the distribution of the distance from the actual camera 24 to the subject 20 that is associated with each pixel included in the captured image may be generated by the actual camera 24 together with the captured image.
  • FIG. 4 is a diagram schematically illustrating an example of a plurality of points 36 belonging to a point group indicated by point group data generated based on one or a plurality of captured images.
  • point cloud data indicating a point cloud to which a plurality of points 36 in the virtual space 32 belong is generated by a known method based on one or a plurality of captured images acquired by the polygon model generation device 10.
  • point cloud data may be generated based on the captured image and the depth image.
  • the density of the points 36 belonging to the point group may become coarse and dense.
  • the density of the points 36 belonging to the point group may vary depending on the orientation of the subject 20 with respect to the actual camera 24.
  • FIG. 5 is a diagram illustrating an example of point data associated with one point 36 included in the point cloud data.
  • the point data shown in FIG. 5 includes a point ID, which is identification information of the point 36 associated with the point data, and coordinate data indicating a three-dimensional coordinate value representing the position of the point 36 expressed in the X2Y2Z2 coordinate system. Combinations are included.
  • the point group data generated in the present embodiment includes the point data illustrated in FIG. 5 as many as the number of points 36 belonging to the point group.
  • the coordinate values (x1, y1, z1) in the X1Y1Z1 coordinate system of the real space 22 are the coordinate values (t ⁇ x1, t ⁇ y1, t ⁇ z1) in the X2Y2Z2 coordinate system in the virtual space 32.
  • T is a constant. Therefore, in this embodiment, the shape of the solid along the outline of the point group shown in FIG. 4 is substantially the same as the shape of the subject 20 shown in FIG.
  • the polygon model generation apparatus 10 generates polygon model data indicating a polygon model, which is composed of a plurality of polygons 34, based on the points 36 belonging to the point group shown in FIG.
  • polygon model data indicating the polygon model illustrated in FIG. 6 is generated, which is composed of polygons 34 each having a point 36 belonging to the point group shown in FIG.
  • some of the points 36 belonging to the point group may be points on the surface of the polygon 34 instead of the vertices of the polygon 34.
  • the first polygon model 40 composed of a plurality of triangles may be generated by performing Delaunay triangulation (tetrahedral division) with the Delaunay points 36 belonging to the point group shown in FIG.
  • the first polygon model 40 need not be generated by Delaunay triangulation, and the first polygon model 40 may be generated by other methods.
  • FIG. 7 is a diagram showing an example of polygon data associated with one polygon 34.
  • polygon model data including polygon data corresponding to the number of polygons 34 included in the initial polygon model 40 is generated.
  • the polygon data includes, for example, a polygon ID that is identification information of the polygon 34 associated with the polygon data, and vertex data that is an ordered list of point IDs of the points 36 that are the vertices of the polygon 34. .
  • the normal direction (front and back) of the polygon 34 associated with the polygon data may be defined by the polygon data.
  • an ordered list of points 36 associated with each vertex which is the order of the vertices when the polygon 34 is viewed from the front side, may be included in the polygon data as vertex data.
  • the direction from the back side to the front side of the polygon 34 may be defined as the normal direction.
  • the initial polygon model 40 illustrated in FIG. 6 includes the convex hull of the point group shown in FIG. 4, and cannot be said to be along the outline of the point group shown in FIG. Therefore, in the present embodiment, the long side polygon deletion process, the intersecting polygon deletion process, and the invisible polygon deletion process described below are executed, so that the polygons 34 constituting the first polygon model 40 illustrated in FIG. Deleted.
  • the first polygon model 40 illustrated in FIG. 5 becomes a polygon model along the outline of the point group shown in FIG. 4, that is, a polygon model with high reproduction accuracy of the subject 20. Approaching.
  • the value of the point density associated with each point 36 belonging to the point group is determined.
  • the number of points 36 included in a hexahedron having a predetermined volume centered on a specific point 36 may be determined as the value of the point density corresponding to the specific point 36.
  • the partial space in which the point cloud data recursively divides the three-dimensional space occupied by the cube covering the point cloud indicated by the point cloud data into the positions of the respective points 36 arranged in the virtual space 32 into eight. May include data of an octree data structure associated with.
  • the density of the point 36 roughly specified based on the octree may be determined as the value of the point density associated with the point 36. In this way, the point density value is determined at high speed.
  • the method for determining the value of the point density is not limited to the above method.
  • a threshold value associated with the side 42 is determined based on a point density value associated with the point 36 that is an end point of the side 42.
  • the point density value associated with the point 36a that is one end point of the side 42a is specified as v1.
  • the value of the point density associated with the point 36b which is the other end point of the side 42a is specified as v2.
  • the threshold th associated with the side 42a is determined based on the value v1 and the value v2.
  • a threshold associated with a smaller value of the values v1 and v2 may be determined as the threshold th.
  • a threshold value associated with a larger value among the values v1 and v2 may be determined as the threshold value th.
  • a threshold value associated with the average value of the values v1 and v2 may be determined as the threshold value th.
  • the correspondence rule between the point density value and the threshold value is determined in advance, and the threshold value can be determined based on the point density value.
  • the threshold value can be determined based on the point density value.
  • a smaller value is determined as a threshold value associated with the value of the point density.
  • a side 42 having a length that is larger than the threshold value associated with the side 42 is specified.
  • the polygon 34 including the specified side 42 is first deleted from the polygon model 40. That is, the polygon data corresponding to the polygon 34 including the specified side 42 is deleted from the polygon model data.
  • the polygon 34a and the polygon 34b including the side 42a are first deleted from the polygon model 40.
  • the point group shown in FIG. A polygon model with high accuracy may not be obtained due to the influence of density.
  • the predetermined length is shortened, the polygon model becomes along the outline of the point group even in the concave portion, while the possibility that a hole is formed in the polygon model increases.
  • the predetermined length is increased, the possibility that the polygon model is punctured is reduced, but the possibility that the polygon model does not follow the outline of the point group in the concave portion increases.
  • the polygon 34 including the long side is deleted based on a threshold value reflecting the density of the points 36 belonging to the point group. Specifically, for example, even in a portion where the points 36 are dense, even a polygon 34 including a relatively short side is deleted, while in a portion where the points 36 are coarse, a polygon 34 including a relatively long side is deleted. Even it is not deleted. Thus, in this embodiment, a highly accurate polygon model can be obtained.
  • the intersecting polygon deletion process described below is executed.
  • an example of the intersecting polygon deletion process will be described with reference to FIG.
  • a position in the virtual space 32 corresponding to the position of the real camera 24 in the real space 22 when the photographed image is taken is specified.
  • the X1Y1Z1 coordinate value of the position of the real camera 24 is (x1, y1, z1)
  • the X2Y2Z2 coordinate value of the position in the virtual space 32 corresponding to the position of the real camera 24 is expressed as (t ⁇ x1, t ⁇ y1, t ⁇ z1) are specified.
  • the position in the virtual space 32 corresponding to the position of the real camera 24 in the real space 22 specified in this way is referred to as a corresponding camera position of the real camera 24.
  • a point 36 in the virtual space 32 corresponding to a point on the surface of the subject 20 associated with the pixel included in the captured image captured by the real camera 24 is specified.
  • the point 36 specified in this way is referred to as a visible point of the actual camera 24.
  • the polygon 34 that intersects with the ray in the ray cast is deleted from the polygon model.
  • the polygon 34c is specified as the polygon 34 that intersects the line segment having the corresponding camera position P1 and the position of the point 36c as both ends.
  • the polygon 34c is deleted from the polygon model. That is, the polygon data corresponding to the polygon 34c is deleted from the polygon model data.
  • intersecting polygon deletion processing it is possible to delete polygons 34 that cannot be deleted by the long side polygon deletion processing, and the polygon model after the intersection polygon deletion processing is executed is based on the outline of the point cloud. Get closer.
  • the invisible polygon deletion process described below deletes the polygon 34 inside the outer surface of the polygon model, and as a result, the waste of the data size of the polygon model data is reduced.
  • an example of the invisible polygon deletion process will be described with reference to FIGS. 10 to 12B.
  • the polygon model on which the long side polygon deletion process and the intersecting polygon deletion process are executed is arranged in the virtual space 32.
  • the polygon model on which the long side polygon deletion process and the intersecting polygon deletion process are executed is referred to as an intermediate polygon model 50.
  • the intermediate polygon model 50 is similar in appearance to the final polygon model 30, but the polygon 34 inside the outer surface remains as described above.
  • the polygons 34 included in the intermediate polygon model 50 may be arranged in the virtual space 32 in a state where they can be distinguished from each other. For example, a visible attribute such as texture or color associated with the polygon ID of the polygon 34 may be set for the polygon 34.
  • FIG. 11 shows a virtual space image 54 showing a state of viewing the direction of the virtual camera 52 intermediate polygon model 50 arranged at the position P3 in FIG.
  • the visibility attribute set for the polygon 34 may be reflected in the virtual space image.
  • the visible polygon 34 (visible polygon 34d) is specified from the position where the virtual space image 54 is captured.
  • the polygon 34 corresponding to the polygon ID associated with the visible attribute set for the polygon 34 whose image is included in the virtual space image 54 may be specified as the visible polygon 34d.
  • the above-described placement of the virtual camera 52, generation of the virtual space image 54, and identification of the visible polygon 34d are sequentially performed for each of a plurality of positions in the virtual space 32.
  • the placement of the virtual camera 52, the generation of the virtual space image 54, and the identification of the visible polygon 34d at each of a plurality of positions in the virtual space 32 may be executed in parallel processing.
  • the polygon 34 that is not specified as the visible polygon 34d in any virtual space image 54 is specified as an invisible polygon.
  • the polygon ID of the polygon 34 specified as the visible polygon 34d may be added to the visible polygon ID list that is empty in the initial state. Then, a polygon 34 whose polygon ID is not included in the visible polygon ID list may be specified as an invisible polygon.
  • the polygon 34 specified as the invisible polygon is deleted from the intermediate polygon model 50. That is, the polygon data corresponding to the invisible polygon is deleted from the polygon model data.
  • the normal direction correction process is executed for the polygons 34 specified as the visible polygons 34d in the respective virtual space images 54 during the invisible polygon deletion process.
  • the normal inversion count value associated with the visible polygon 34d is increased by one. That is, when the inner product of the vector V1 in the shooting direction by the virtual camera 52 and the vector V2 in the normal direction of the visible polygon 34d is positive, the normal inversion count value associated with the visible polygon 34d increases by one.
  • the normal inversion count value associated with the visible polygon 34d is decreased by one. That is, when the inner product of the vector V1 in the shooting direction by the virtual camera 52 and the vector V2 in the normal direction of the visible polygon 34d is negative, the normal inversion count value associated with the visible polygon 34d is decreased by 1. It is assumed that the initial value of the normal inversion count value associated with the visible polygon 34d is 0.
  • the visible polygon 34d having a positive normal inversion count value is identified.
  • the normal direction indicated by the polygon data associated with the identified visible polygon 34d is reversed.
  • the order of the second point ID and the third point ID is switched among the three point IDs included in the vertex data of the polygon data.
  • the final polygon model 30 illustrated in FIG. 3 is generated by performing the invisible polygon deletion process and the normal direction correction process as described above.
  • the virtual space image 54 can be easily generated.
  • the visible polygon 34d is specified based on the virtual space image 54 that can be easily generated in this way, the invisible polygon can be easily specified.
  • a high-accuracy final polygon model 30 that imitates the subject 20 with a low processing load by a simple process of deleting the polygon 34 from the initial polygon model 40 illustrated in FIG. Can be generated.
  • FIG. 13 is a functional block diagram showing an example of functions implemented in the polygon model generation apparatus 10 according to the present embodiment.
  • the polygon model generation device 10 functionally includes, for example, a captured image storage unit 60, a camera data storage unit 62, a polygon model data storage unit 64, a captured image acquisition unit 66, and a camera data acquisition unit 68.
  • Point cloud data generation unit 70 initial polygon model generation unit 72, point density value determination unit 74, threshold value determination unit 76, long side polygon deletion unit 78, corresponding camera position specification unit 80, intersecting polygon deletion unit 82, visibility attribute setting Section 84, virtual camera arrangement section 86, virtual space image generation section 88, visible polygon identification section 90, normal direction correction section 92, and invisible polygon deletion section 94.
  • the photographed image storage unit 60, the camera data storage unit 62, and the polygon model data storage unit 64 are mainly implemented by the storage unit 14.
  • the above functions may be implemented by causing the processor 12 to execute a program that is installed in the polygon model generation apparatus 10 that is a computer and that includes instructions corresponding to the above functions.
  • the program may be supplied to the polygon model generation apparatus 10 via a computer-readable information storage medium such as an optical disk, a magnetic disk, a magnetic tape, a magneto-optical disk, or a flash memory, or via the Internet. Good.
  • the photographed image storage unit 60 stores one or a plurality of photographed images obtained by photographing the subject 20 in the real space 22, for example.
  • the captured image storage unit 60 may store a captured image associated with depth information such as a depth image.
  • the camera data storage unit 62 stores camera data indicating the position, orientation, angle of view, and the like of the real camera 24 in the real space 22 when a photographed image is taken.
  • the camera data storage unit 62 stores a plurality of camera data associated with the photographed images.
  • the polygon model data storage unit 64 stores, for example, point group data including a plurality of point data illustrated in FIG. 5 and polygon model data including a plurality of polygon data illustrated in FIG.
  • the photographed image acquisition unit 66 acquires one or a plurality of photographed images stored in the photographed image storage unit 60, for example.
  • the camera data acquisition unit 68 acquires one or a plurality of camera data stored in the camera data storage unit 62, for example.
  • the point cloud data generation unit 70 generates and generates point cloud data based on the captured image acquired by the captured image acquisition unit 66 and the camera data acquired by the camera data acquisition unit 68.
  • the obtained point cloud data is stored in the polygon model data storage unit 64.
  • the first polygon model generation unit 72 generates the first polygon model 40 including a plurality of polygons 34 based on the point cloud data stored in the polygon model data storage unit 64, for example.
  • an initial polygon model 40 including a plurality of polygons 34 having apexes of the points 36 belonging to the point group indicated by the point group data stored in the polygon model data storage unit 64 may be generated.
  • the first polygon model generation unit 72 stores the generated first polygon model 40 in the polygon model data storage unit 64, for example.
  • the point density value determination unit 74 is based on the distribution of the point group indicated by the point group data stored in the polygon model data storage unit 64, and belongs to the point group as described above. A point density value associated with the point 36 is determined.
  • the threshold value determination unit 76 associates each polygon 34 indicated by the polygon data stored in the polygon model data storage unit 64 with the side 42 constituting the polygon 34 as described above. Determine the threshold value to be used.
  • the smaller the value of the point density the smaller the threshold value associated with the value of the point density may be determined.
  • the threshold determination unit 76 may hold data indicating a correspondence rule between the point density value and the threshold. The threshold determination unit 76 may determine a threshold using this data.
  • the long-side polygon deleting unit 78 for example, when the length of the side 42 constituting the polygon 34 exceeds a threshold corresponding to the value of the point density associated with the end point of the side 42, the polygon 34 is deleted from the polygon model.
  • the long side polygon deleting unit 78 may delete the polygon 34 including the side 42 whose length is larger than the associated threshold as described above from the polygon model.
  • polygon data including the polygon ID of the polygon 34 including the side 42 whose length is longer than the associated threshold value may be deleted from the polygon model data.
  • the corresponding camera position specifying unit 80 is based on the camera data acquired by the camera data acquisition unit 68, and is in the virtual space 32 corresponding to the position of the real camera 24 in the real space 22 indicated by the camera data.
  • the corresponding camera position which is the position is specified.
  • the intersecting polygon deleting unit 82 intersects a line 34 that intersects a line segment having both ends of a position where the polygon model is desired in the virtual space 32 and the position of the point 36 belonging to the point cloud indicated by the point cloud data. Is identified.
  • the corresponding camera position of the actual camera 24 and the point 36 corresponding to the surface of the subject 20 whose image is captured by the actual camera 24 intersect with a line segment at both ends.
  • the polygon 34 may be specified.
  • the line segment has both ends of the position of the point 36 and the position where the polygon model is desired in the virtual space 32.
  • the intersecting polygon 34 may be specified.
  • a polygon 34 that intersects a line segment that has an end point at infinity with respect to the center of the polygon model and a point 36 in the virtual space 32 may be specified.
  • the polygon 34 may be specified.
  • a polygon 34 that intersects a line segment having both ends of a point 36 and a position where a polygon model is desired in the virtual space 32 set by the user may be specified.
  • the intersecting polygon deletion unit 82 deletes the specified polygon 34 from the polygon model.
  • polygon data including the polygon ID of the identified polygon 34 may be deleted from the polygon model data.
  • the visible attribute setting unit 84 sets a visible attribute associated with the polygon 34 to each polygon 34 constituting the intermediate polygon model 50 arranged in the virtual space 32.
  • the virtual camera placement unit 86 determines the position and shooting direction of the virtual camera 52 in the virtual space 32, for example.
  • the virtual camera placement unit 86 may change the position and orientation of the virtual camera 52 in accordance with the operation of the operation unit 16 by the user. Then, the virtual camera placement unit 86 may determine the placement of the virtual camera 52 in accordance with the user's determination operation.
  • the virtual space image generation unit 88 generates a virtual space image 54 that represents a state in which the shooting direction of the virtual camera 52 is viewed from the position of the virtual camera 52 arranged by the virtual camera arrangement unit 86.
  • a plurality of virtual space images 54 representing the states viewed from different positions may be generated.
  • the visible polygon specifying unit 90 specifies the visible polygon 34d that is visible from the virtual camera 52 based on the virtual space image 54, for example.
  • the normal direction correcting unit 92 executes the normal direction correcting process described above for each visible polygon 34d specified by the visible polygon specifying unit 90.
  • the invisible polygon deletion unit 94 specifies an invisible polygon that is an invisible polygon 34 in any one or a plurality of virtual cameras 52 set in the virtual space 32.
  • the invisible polygon deleting unit 94 deletes the specified invisible polygon from the polygon model.
  • polygon data including a polygon ID of an invisible polygon may be deleted from the polygon model data.
  • polygon data associated with a polygon 34 that has not been identified as the visible polygon 34d in any virtual space image 54 may be deleted from the polygon model data.
  • the captured image acquisition unit 66 acquires one or a plurality of captured images stored in the captured image storage unit 60 (S101).
  • the camera data acquisition part 68 acquires the camera data matched with the picked-up image acquired by the process shown to S101 memorize
  • a plurality of captured images are acquired in the process shown in S101, and a plurality of camera data associated with the captured images are acquired in the process shown in S102.
  • the point cloud data generation unit 70 generates point cloud data including a plurality of point data, and stores the generated point cloud data in the polygon model data storage unit 64 (S103).
  • point cloud data may be generated based on the captured image acquired in the process shown in S101.
  • point cloud data may be generated based on the captured image acquired in the process shown in S101 and the camera data acquired in the process shown in S102.
  • the first polygon model generation unit 72 generates polygon model data of the first polygon model 40 based on the point cloud data stored in the process shown in S103, and the generated polygon model data is stored in the polygon model data storage unit 64. (S104).
  • the long side polygon deletion process (S105), the intersecting polygon deletion process (S106), and the invisible polygon deletion process (S107) are executed in this order, and the polygon model data associated with the final polygon model 30 is finally obtained. Generated.
  • the point density value determination unit 74 performs processing for points 36 corresponding to each of the plurality of point data included in the point cloud data. Then, a point density value corresponding to the point 36 is determined (S201).
  • the threshold value determination unit 76 determines a threshold value associated with the side 42 of the polygon 34 indicated by the polygon data for each of a plurality of polygon data included in the polygon model data generated in the process shown in S104 (S202).
  • the side 42 corresponds to a combination of points 36 associated with a combination of two point IDs included in the vertex data of the polygon data.
  • the threshold value associated with the side 42 can be determined based on the value of the point density determined in the process shown in S105 for the point 36 associated with each of these two point IDs.
  • the long side polygon deleting unit 78 specifies the polygon 34 including the side 42 in which the length of the side 42 exceeds the threshold value determined for the side 42 from the sides 42 for which the threshold value has been determined in the process of S202. (S203).
  • the long side polygon deleting unit 78 deletes the polygon data including the polygon ID of the polygon 34 specified by the processing shown in S203 from the polygon model data stored in the polygon model data storage unit 64 (S204). Then, the long side polygon deletion process (S105) is ended.
  • the corresponding camera position specifying unit 80 specifies the corresponding camera position of the actual camera 24 that is associated with the camera data based on the camera data acquired in the process shown in S102 (S301). In the present processing example, since a plurality of camera data are acquired, a plurality of corresponding camera positions are specified.
  • the intersecting polygon deletion unit 82 selects one of the corresponding camera positions specified in the process shown in S301, for which the process shown in S303 to S307 below is not executed (S302).
  • the intersecting polygon deletion unit 82 specifies a captured image captured by the real camera 24 corresponding to the corresponding camera position selected in the process shown in S302 (S303).
  • the intersecting polygon deletion unit 82 specifies a plurality of points 36 corresponding to the surface of the subject 20 whose image is included in the captured image specified in the process shown in S303 (S304).
  • the intersecting polygon deletion unit 82 extracts, from among the plurality of points 36 identified in the process shown in S304, those having a point density value that is determined in the process shown in S201 and is greater than a predetermined value. (S305).
  • the intersecting polygon deletion unit 82 intersects a line segment having both ends of the position of the point 36 and the corresponding camera position selected in the process shown in S301.
  • the polygon 34 to be specified is specified (S306).
  • the intersecting polygon deletion unit 82 deletes the polygon data including the polygon ID of the polygon 34 specified in the process shown in S306 from the polygon model data stored in the polygon model data storage unit 64 (S307).
  • the intersecting polygon deletion unit 82 confirms whether or not there is a corresponding camera position that has not been selected in the processing shown in S302 and has not been executed in the processing shown in S303 to S307 (S308). If it exists (S308: Y), the process returns to S302. If it does not exist (S308: N), the intersecting polygon deletion process (S106) is terminated.
  • the visual attribute setting unit 84 sets different visual attributes for each of the polygon data included in the polygon model data stored in the polygon model data storage unit 64 (S401).
  • the virtual camera placement unit 86 determines the position of the virtual camera 52 that desires the polygon model and the shooting direction of the virtual camera 52 in the virtual space 32 (S402).
  • the position and the shooting direction may be determined randomly, or the position and the shooting direction may be determined in accordance with a user's designation.
  • the virtual space image generation unit 88 generates a virtual space image 54 representing a state in which the shooting direction of the virtual camera 52 is viewed from the position of the virtual camera 52 (S403).
  • the visible polygon specifying unit 90 specifies the visible polygon 34d that is visible from the virtual camera 52 based on the virtual space image 54 generated by the process shown in S403 (S404).
  • the visible polygon specifying unit 90 adds the polygon ID of the visible polygon 34d specified in the process shown in S404 to the visible polygon ID list (S405).
  • a normal inversion count value having an initial value of 0 is associated with the polygon ID.
  • the normal direction correcting unit 92 then calculates the inner product value of the vector V1 in the shooting direction by the virtual camera 52 and the vector V2 in the normal direction of the visible polygon 34d for each of the visible polygons 34d specified in the process shown in S120. Is calculated (S406).
  • the normal direction correcting unit 92 updates the normal inversion count value associated with the polygon ID included in the visible polygon ID list according to the inner product value calculated in the process shown in S405 (S407).
  • the normal inversion count value associated with the polygon ID of the visible polygon 34d for which the calculated inner product value is positive is incremented by one.
  • the normal inversion count value associated with the polygon ID of the visible polygon 34d whose calculated inner product value is negative is decreased by one.
  • the invisible polygon deletion unit 94 confirms whether or not the processing shown in S403 to S407 has been repeatedly executed a predetermined number of times (S408).
  • S408 N
  • the virtual camera placement unit 86 changes the position of the virtual camera 52 that desires the polygon model and the shooting direction of the virtual camera 52 in the virtual space 32 (S409), and the process returns to S403.
  • the position and the shooting direction may be changed randomly, or may be changed to the position and shooting direction specified by the user.
  • the normal direction correcting unit 92 specifies a polygon ID whose associated normal reverse count value is positive from the polygon IDs included in the visible polygon ID list held by the visible polygon specifying unit 90. (S410).
  • the normal direction correcting unit 92 inverts the normal direction represented by the polygon data including the polygon ID specified in the process shown in S409, which is stored in the polygon model data storage unit 64 (S411).
  • the normal direction correcting unit 92 performs the second point ID and the third point ID among the three point IDs included in the vertex data of the polygon data including the polygon ID specified in the process shown in S410. The order of the point IDs is changed.
  • the invisible polygon deleting unit 94 specifies an invisible polygon based on the visible polygon ID list held by the visible polygon specifying unit 90 and the polygon data stored in the polygon model data storage unit 64 (S412).
  • the invisible polygon deletion unit 94 deletes the polygon data including the polygon ID of the invisible polygon specified by the processing shown in S411 from the polygon model data stored in the polygon model data storage unit 64 (S413). Then, the invisible polygon deletion process (S107) ends.
  • the intersection polygon deletion process shown in S106 may be executed without executing the long side polygon deletion process shown in S105. Further, instead of the long side polygon deleting process shown in S105, a process of uniformly deleting the polygons 34 including the side 42 longer than the predetermined length may be executed. Further, after the process of uniformly deleting the polygons 34 including the side 42 longer than the predetermined length is executed, the long side polygon deletion process shown in S105 may be executed.
  • processing shown in S305 may not be executed, and the processing shown in S306 and S307 may be executed for all the points 36 specified in the processing shown in S304.
  • the invisible polygon deletion process shown in S107 may be executed on the polygon model for which the long side polygon deletion process shown in S105 or the intersecting polygon deletion process shown in S106 has not been executed. Further, the invisible polygon deletion process shown in S107 may not be executed after the intersection polygon deletion process shown in S106 is executed.

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Image Generation (AREA)
  • Processing Or Creating Images (AREA)

Abstract

点群の輪郭に沿ったポリゴンモデルを精度よく生成できるポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラムを提供する。最初ポリゴンモデル生成部（７２）は、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成する。交差ポリゴン削除部（８２）は、仮想空間内におけるポリゴンモデルを望む第１位置と点群に属する点の位置である第２位置とを両端とする線分と交差するポリゴンである交差ポリゴンを特定する。交差ポリゴン削除部（８２）は、交差ポリゴンをポリゴンモデルから削除する。

Description

ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム
　本発明は、ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラムに関する。
　点群の輪郭に沿ったポリゴンモデルを生成する技術が存在する。このような技術の一例として、特許文献１には、実空間に配置されたオブジェクトを撮影することで取得される深さ情報を含む画像から仮想空間内に配置されるポリゴンモデルを生成する技術が記載されている。
　この技術では、まず、三角形のポリゴンを含むイニシャルスカルプチャが仮想空間内に生成される。そして取得された画像内の画素及び当該画素の深さとの組合せに対応付けられる仮想空間内の点（データポイント）が特定される。そして特定されたデータポイントに対して原点からレイキャストが実行され、レイキャストされた光線とポリゴンとの交点が特定される。そして特定された交点とデータポイントとの間の長さに応じて上記のポリゴンの頂点を移動させることで、イニシャルスカルプチャが変形される。
国際公開第２０１５／１９３７０８号
　発明者らは、点群の輪郭に沿ったポリゴンモデルを生成する新たな手法を検討している。この手法では、まず、深さ情報を含む画像などから仮想空間内の点群を示す点群データが生成される。そして例えば当該点群に属する点をドロネー点とするドロネー三角形分割（四面体分割）などを行うことによって、それぞれ当該点群に属する点を頂点とする複数のポリゴンを含むポリゴンモデルが生成される。
　しかしこのようにして生成されるポリゴンモデルは外表面が点群の輪郭に沿ったものとはならない。ここで例えば所定長よりも長い辺を含むポリゴンをポリゴンモデルから削除することでポリゴンモデルを点群の輪郭に沿ったものにより近づけることが考えられる。しかしこのようにしても点群の粗密等の影響で点群の輪郭に沿った充分な精度のポリゴンモデルが得られないことがあった。
　本発明は上記課題に鑑みてなされたものであって、その目的の１つは、点群の輪郭に沿ったポリゴンモデルを精度よく生成できるポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラムを提供することにある。
　上記課題を解決するために、本発明に係るポリゴンモデル生成装置は、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成部と、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定部と、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除部と、を含む。
　本発明の一態様では、実空間において実カメラが被写体を撮影した画像を取得する画像取得部と、前記画像に基づいて、属する点がそれぞれ前記実空間内における前記被写体上の点に相当する前記点群データを生成する点群データ生成部と、前記被写体を撮影した際の前記実カメラの前記実空間内における位置に相当する、前記仮想空間内の位置を特定する対応カメラ位置特定部と、をさらに含み、前記交差ポリゴン特定部は、前記対応カメラ位置特定手順で特定される位置を前記第１位置として前記交差ポリゴンを特定する。
　また、本発明の一態様では、前記仮想空間内に設定される１又は複数の仮想カメラのいずれにおいても不可視な前記ポリゴンである不可視ポリゴンを特定する不可視ポリゴン特定部と、前記不可視ポリゴンを前記ポリゴンモデルから削除する不可視ポリゴン削除部と、をさらに含む。
　また、本発明の一態様では、前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定部と、前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除部と、をさらに含む。
　この態様では、前記交差ポリゴン特定部は、対応付けられる前記点密度の値が所定値よりも大きな点の少なくとも一部のそれぞれのみについて、当該点の位置を前記第２位置として前記交差ポリゴンを特定してもよい。
　また、本発明に係るポリゴンモデル生成方法は、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成ステップと、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定ステップと、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除ステップと、を含む。
　また、本発明に係るプログラムは、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成手順、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定手順、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除手順、をコンピュータに実行させる。
本発明の一実施形態に係るポリゴンモデル生成装置の構成図である。 被写体が実空間に配置されている様子の一例を模式的に示す図である。 被写体を模したポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。 点群データが示す点群に属する複数の点の一例を模式的に示す図である。 点データの一例を示す図である。 最初ポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。 ポリゴンデータの一例を示す図である。 長辺ポリゴン削除処理の一例を説明する説明図である。 交差ポリゴン削除処理の一例を説明する説明図である。 中間ポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。 仮想空間画像の一例を示す図である。 法線方向修正処理の一例を説明する説明図である。 法線方向修正処理の一例を説明する説明図である。 本発明の一実施形態に係るポリゴンモデル生成装置で実装される機能の一例を示す機能ブロック図である。 本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。 本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。 本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。 本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。
　以下、本発明の一実施形態について図面に基づき詳細に説明する。
　図１は、本発明の一実施形態に係るポリゴンモデル生成装置１０の構成図である。本実施形態に係るポリゴンモデル生成装置１０は、例えば、ゲームコンソールやパーソナルコンピュータなどのコンピュータである。図１に示すように、本実施形態に係るポリゴンモデル生成装置１０は、例えば、プロセッサ１２、記憶部１４、操作部１６、表示部１８、を含んでいる。
　プロセッサ１２は、例えばポリゴンモデル生成装置１０にインストールされるプログラムに従って動作するＣＰＵ等のプログラム制御デバイスである。本実施形態に係るプロセッサ１２には、ＣＰＵから供給されるグラフィックスコマンドやデータに基づいてフレームバッファに画像を描画するＧＰＵ（Graphics Processing Unit）も含まれている。
　記憶部１４は、ＲＯＭやＲＡＭ等の記憶素子やハードディスクドライブなどである。記憶部１４には、プロセッサ１２によって実行されるプログラムなどが記憶される。また、本実施形態に係る記憶部１４には、ＧＰＵにより画像が描画されるフレームバッファの領域が確保されている。
　操作部１６は、キーボード、マウス、ゲームコンソールのコントローラ等のユーザインタフェースであって、ユーザの操作入力を受け付けて、その内容を示す信号をプロセッサ１２に出力する。
　表示部１８は、液晶ディスプレイ等の表示デバイスであって、プロセッサ１２の指示に従って各種の画像を表示する。
　なお、ポリゴンモデル生成装置１０は、ネットワークボードなどの通信インタフェース、ＤＶＤ－ＲＯＭやＢｌｕ－ｒａｙ（登録商標）ディスクなどの光ディスクを読み取る光ディスクドライブ、ＵＳＢ（Universal Serial Bus）ポートなどを含んでいてもよい。
　図２は、本実施形態に係る被写体２０が実空間２２内に配置されている様子の一例を模式的に示す図である。図２には、スタンフォードバニーのような形状の実オブジェクトが被写体２０の一例として示されている。
　図３は、被写体２０を模したポリゴンモデルが仮想空間３２内に配置されている様子の一例を模式的に示す図である。本実施形態に係るポリゴンモデル生成装置１０では、例えば、実空間２２に配置された実カメラ２４が図２に例示する被写体２０を撮影した１又は複数の撮影画像に基づいて、最終的には図３に示すポリゴンモデルが生成される。以下、最終的に生成されるポリゴンモデルを最終ポリゴンモデル３０と呼ぶこととする。
　図３に示す最終ポリゴンモデル３０は、複数のポリゴン３４から構成されている。本実施形態に係る仮想空間３２は、実空間２２をモデリングした空間となっている。本実施形態では実空間２２内における被写体２０の位置や向きは、仮想空間３２内の最終ポリゴンモデル３０の位置や向きに反映される。以下、実空間２２内における位置はＸ１Ｙ１Ｚ１座標系で表現され、仮想空間３２内における位置はＸ２Ｙ２Ｚ２座標系で表現されることとする。
　以下、ポリゴンモデル生成装置１０で行われる、被写体２０に基づく最終ポリゴンモデル３０の生成処理について説明する。
　本実施形態に係るポリゴンモデル生成装置１０は、まず、実カメラ２４が被写体２０を撮影した１又は複数の撮影画像を取得する。なお、複数の実カメラ２４のそれぞれによって同時に撮影画像が撮影されてもよいし、１の実カメラ２４によって様々な向きから被写体２０の撮影画像が撮影されてもよい。また実カメラ２４は、ステレオカメラや赤外線測距センサ付きのカメラなどといった、深さ情報を含む撮影画像の撮影が可能なカメラであってもよい。この場合例えば、撮影画像に含まれる画素のそれぞれに対応付けられる、実カメラ２４から被写体２０までの距離の分布を示すデプス画像が、実カメラ２４によって撮影画像とともに生成されてもよい。
　図４は、１又は複数の撮影画像に基づいて生成される点群データが示す点群に属する複数の点３６の一例を模式的に示す図である。本実施形態では、ポリゴンモデル生成装置１０が取得する１又は複数の撮影画像に基づいて、公知の手法により、仮想空間３２内の複数の点３６が属する点群を示す点群データが生成される。また撮影画像とデプス画像に基づいて点群データが生成されてもよい。
　本実施形態では、複数の撮影画像が撮影される場合には、各撮影画像が撮影される際の被写体２０と実カメラ２４との間の距離の違いや撮影画像を撮影する複数の実カメラ２４の解像度の違いなどによって、点群に属する点３６の密度に粗密が生じることがある。また実カメラ２４に対する被写体２０の向きによっても点群に属する点３６の密度に粗密が生じることがある。
　図５は、点群データに含まれる、１の点３６に対応付けられる点データの一例を示す図である。図５に示す点データには、当該点データに対応付けられる点３６の識別情報である点ＩＤと当該点３６のＸ２Ｙ２Ｚ２座標系で表現された位置を表す３次元座標値を示す座標データとの組合せが含まれる。本実施形態で生成される点群データには、図５に例示する点データが点群に属する点３６の数だけ含まれる。
　そして図４に示す点３６の位置は、１又は複数の撮影画像に基づいて特定される、被写体２０の表面上の点の位置に対応付けられる。そして本実施形態では例えば、実空間２２のＸ１Ｙ１Ｚ１座標系における座標値（ｘ１，ｙ１，ｚ１）が、仮想空間３２内のＸ２Ｙ２Ｚ２座標系における座標値（ｔ・ｘ１，ｔ・ｙ１，ｔ・ｚ１）（ｔは定数）にマッピングされる。そのため本実施形態では、図４に示す点群の輪郭に沿った立体の形状は、図２に示す被写体２０の形状と概ね同じになる。
　そして本実施形態に係るポリゴンモデル生成装置１０は、図４に示す点群に属する点３６に基づいて、複数のポリゴン３４から構成される、ポリゴンモデルを示すポリゴンモデルデータを生成する。ここでは例えば、それぞれ図４に示す点群に属する点３６を頂点とするポリゴン３４から構成される、図６に例示するポリゴンモデルを示すポリゴンモデルデータが生成されることとする。なお点群に属する点３６のなかには、ポリゴン３４の頂点とはならずにポリゴン３４の面上の点となるものがあってもよい。以下、図６に示すポリゴンモデルを最初ポリゴンモデル４０と呼ぶこととする。例えば、図４に示す点群に属する点３６をドロネー点とするドロネー三角形分割（四面体分割）を行うことで、複数の三角形から構成される最初ポリゴンモデル４０が生成されてもよい。なおドロネー三角形分割によって最初ポリゴンモデル４０が生成される必要はなく、その他の方法によって最初ポリゴンモデル４０が生成されても構わない。
　図７は、１のポリゴン３４に対応付けられるポリゴンデータの一例を示す図である。本実施形態では、最初ポリゴンモデル４０に含まれるポリゴン３４の数だけポリゴンデータを含むポリゴンモデルデータが生成される。ポリゴンデータには、例えば、当該ポリゴンデータに対応付けられるポリゴン３４の識別情報であるポリゴンＩＤと、当該ポリゴン３４の頂点である点３６の点ＩＤの順序付きリストである頂点データと、が含まれる。
　またポリゴンデータによって当該ポリゴンデータに対応付けられるポリゴン３４の法線方向（表裏）が定義されてもよい。例えばポリゴン３４を表側から見た際において反時計回りとなるような頂点の順序である、各頂点に対応付けられる点３６の順序付きリストが頂点データとしてポリゴンデータに含まれるようにしてもよい。そしてこの場合にポリゴン３４の裏側から表側に向かう方向が法線方向として定義されてもよい。
　なおポリゴンデータのデータ構造は図７に示すものに限定されない。
　ここで図６に例示する最初ポリゴンモデル４０には、図４に示す点群の凸包が含まれており、図４に示す点群の輪郭に沿ったものであるとは言えない。そこで本実施形態では、以下で説明する長辺ポリゴン削除処理、交差ポリゴン削除処理、及び、不可視ポリゴン削除処理が実行されることによって、図６に例示する最初ポリゴンモデル４０を構成するポリゴン３４が順次削除される。そしてこのようにすることで本実施形態によれば、図５に例示する最初ポリゴンモデル４０が、図４に示す点群の輪郭に沿ったポリゴンモデル、すなわち被写体２０の再現精度の高いポリゴンモデルに近づいていく。
　ここで図８を参照しながら長辺ポリゴン削除処理の一例について説明する。
　長辺ポリゴン削除処理では、まず、図４に示す点群の分布に基づいて、当該点群に属するそれぞれの点３６に対応付けられる点密度の値が決定される。
　ここで特定の点３６を中心とする所定の体積の六面体に含まれる点３６の数が、当該特定の点３６に対応する点密度の値として決定されてもよい。
　また、点群データが、仮想空間３２内に配置されるそれぞれの点３６の位置を、当該点群データが示す点群を覆う立方体が占める３次元空間を再帰的に８つに分割した部分空間に対応付けた八分木データ構造のデータを含んでいてもよい。この場合、八分木に基づいて大まかに特定される点３６の密度が当該点３６に対応付けられる点密度の値として決定されてもよい。このようにすれば点密度の値が高速に決定される。
　なお点密度の値の決定方法は以上の方法には限定されない。
　次に、最初ポリゴンモデル４０に含まれるそれぞれの辺４２につき、当該辺４２の端点である点３６に対応付けられる点密度の値に基づいて、当該辺４２に対応付けられる閾値が決定される。図８の例において、辺４２ａの一方の端点である点３６ａに対応付けられる点密度の値がｖ１と特定されたとする。また辺４２ａの他方の端点である点３６ｂに対応付けられる点密度の値がｖ２と特定されたとする。この場合は例えば、値ｖ１と値ｖ２とに基づいて、辺４２ａに対応付けられる閾値ｔｈが決定される。ここで例えば値ｖ１と値ｖ２のうちの小さな値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。また例えば値ｖ１と値ｖ２のうちの大きな値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。また例えば値ｖ１と値ｖ２の平均値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。
　なお本実施形態では点密度の値と閾値との対応規則は予め定められており、点密度の値に基づいて閾値が決定可能であることとする。また点密度の値が大きいほど当該点密度の値に対応付けられる閾値として小さな値が決定されることとする。
　そして最初ポリゴンモデル４０に含まれる辺４２のうちから、当該辺４２に対応づけられる閾値よりも当該辺４２の長さの方が大きな辺４２が特定される。そして特定された辺４２を含むポリゴン３４が最初ポリゴンモデル４０から削除される。すなわち、特定された辺４２を含むポリゴン３４に対応するポリゴンデータが、ポリゴンモデルデータから削除される。図８の例では、辺４２ａの長さＬが閾値ｔｈを超える場合には、辺４２ａを含むポリゴン３４ａ及びポリゴン３４ｂが最初ポリゴンモデル４０から削除される。
　上述の長辺ポリゴン削除処理を実行せずに、図６に例示する最初ポリゴンモデル４０から所定長よりも長い辺４２を含むポリゴン３４を一律で削除するようにすると、図４に示す点群の粗密の影響で精度の高いポリゴンモデルが得られないことがある。例えば、上述の所定長を短くすると凹部においてもポリゴンモデルが点群の輪郭に沿ったものとなる一方でポリゴンモデルに穴が空く可能性が高くなる。また上述の所定長を長くするとポリゴンモデルに穴が空く可能性は低減されるが凹部においてポリゴンモデルが点群の輪郭に沿ったものとならない可能性が高くなる。
　本実施形態に係る長辺ポリゴン削除処理では、点群に属する点３６の密度が反映された閾値に基づき長辺を含むポリゴン３４が削除される。具体的には例えば、点３６が密である部分においては比較的短い辺を含むポリゴン３４であっても削除される一方で、点３６が粗である部分においては比較的長い辺を含むポリゴン３４であっても削除されない。このようにして本実施形態では、精度の高いポリゴンモデルを得ることができる。
　そして本実施形態ではポリゴンモデルの精度をさらに高めるため、以下で説明する交差ポリゴン削除処理が実行される。ここで図９を参照しながら交差ポリゴン削除処理の一例について説明する。
　交差ポリゴン削除処理では、まず、撮影画像を撮影した際の実空間２２における実カメラ２４の位置に相当する、仮想空間３２内における位置が特定される。上述のように実カメラ２４の位置のＸ１Ｙ１Ｚ１座標値が（ｘ１，ｙ１，ｚ１）である場合には、この実カメラ２４の位置に相当する仮想空間３２内の位置のＸ２Ｙ２Ｚ２座標値として（ｔ・ｘ１，ｔ・ｙ１，ｔ・ｚ１）が特定される。以下、このようにして特定される、実空間２２における実カメラ２４の位置に相当する、仮想空間３２内における位置を、当該実カメラ２４の対応カメラ位置と呼ぶこととする。
　そして実カメラ２４によって撮影された撮影画像に含まれる画素に対応付けられる被写体２０の表面上の点に相当する、仮想空間３２内における点３６が特定される。以下、このようにして特定される点３６を、当該実カメラ２４の可視点と呼ぶこととする。
　そして実カメラ２４の対応カメラ位置から、当該実カメラ２４の可視点のうち対応付けられる点密度の値が所定値よりも大きな点３６のそれぞれに対してレイキャストが実行される。
　そしてレイキャストにおけるレイと交差するポリゴン３４がポリゴンモデルから削除される。例えば図９に示す、実カメラ２４の対応カメラ位置Ｐ１から当該実カメラ２４の可視点である点３６ｃに対してレイキャストを実行した際に、当該レイキャストにおけるレイとポリゴン３４ｃが位置Ｐ２において交差したとする。すなわち、対応カメラ位置Ｐ１と点３６ｃの位置とを両端とする線分と交差するポリゴン３４としてポリゴン３４ｃが特定されたとする。この場合、このポリゴン３４ｃがポリゴンモデルから削除される。すなわち、ポリゴン３４ｃに対応するポリゴンデータが、ポリゴンモデルデータから削除される。
　上述の交差ポリゴン削除処理によれば、長辺ポリゴン削除処理では削除しきれないポリゴン３４の削除が可能となり、交差ポリゴン削除処理が実行された後のポリゴンモデルは点群の輪郭に沿ったものにより近づく。
　しかし以上の長辺ポリゴン削除処理及び交差ポリゴン削除処理を実行しても、ポリゴンモデルの外表面よりも内側のポリゴン３４が残ることがある。このようなポリゴン３４は、ポリゴンモデルの外観の表現に寄与しない。そのため、このようなポリゴン３４に対応するポリゴンデータはポリゴンモデルデータにおける無駄といえる。
　そこで本実施形態では、以下で説明する不可視ポリゴン削除処理によって、ポリゴンモデルの外表面よりも内側のポリゴン３４が削除され、その結果、ポリゴンモデルデータのデータサイズの無駄が低減されるようにした。ここで図１０～図１２Ｂを参照しながら不可視ポリゴン削除処理の一例について説明する。
　まず図１０に示すように、長辺ポリゴン削除処理及び交差ポリゴン削除処理が実行されたポリゴンモデルが、仮想空間３２内に配置される。以下、長辺ポリゴン削除処理及び交差ポリゴン削除処理が実行されたポリゴンモデルを、中間ポリゴンモデル５０と呼ぶこととする。中間ポリゴンモデル５０は、外観は最終ポリゴンモデル３０と同様であるが、上述のように外表面よりも内側のポリゴン３４が残っている。ここで中間ポリゴンモデル５０に含まれるポリゴン３４が互いに識別可能な状態で仮想空間３２内に配置されてもよい。例えば、ポリゴン３４のポリゴンＩＤに対応付けられるテクスチャや色等の可視属性が当該ポリゴン３４に設定されてもよい。
　そして中間ポリゴンモデル５０を望む仮想空間３２内の位置に配置された仮想カメラ５２から中間ポリゴンモデル５０の方向を見た様子を表す、図１１に例示する仮想空間画像５４がレンダリングされる。図１１には、図１０における位置Ｐ３に配置された仮想カメラ５２中間ポリゴンモデル５０の方向を見た様子を表す仮想空間画像５４が示されている。ここでポリゴン３４に設定されている可視属性が仮想空間画像に反映されてもよい。そして当該仮想空間画像５４を撮影した位置から可視であるポリゴン３４（可視ポリゴン３４ｄ）が特定される。ここで例えば、仮想空間画像５４に像が含まれるポリゴン３４に設定されている可視属性に対応付けられるポリゴンＩＤに対応するポリゴン３４が、可視ポリゴン３４ｄとして特定されてもよい。
　ここで図１０に示すように、仮想空間３２内の複数の位置のそれぞれについて、順次、上述の仮想カメラ５２の配置、仮想空間画像５４の生成、及び、可視ポリゴン３４ｄの特定が行われてもよい。また仮想空間３２内の複数の位置のそれぞれにおける、仮想カメラ５２の配置、仮想空間画像５４の生成、及び、可視ポリゴン３４ｄの特定が並列処理で実行されてもよい。そしていずれの仮想空間画像５４においても可視ポリゴン３４ｄとして特定されなかったポリゴン３４が、不可視ポリゴンとして特定される。
　ここで例えば、初期状態では空である可視ポリゴンＩＤリストに、可視ポリゴン３４ｄとして特定されたポリゴン３４のポリゴンＩＤが追加されるようにしてもよい。そして可視ポリゴンＩＤリストにポリゴンＩＤが含まれていないポリゴン３４が不可視ポリゴンとして特定されてもよい。
　そして、不可視ポリゴンとして特定されたポリゴン３４が、中間ポリゴンモデル５０から削除される。すなわち不可視ポリゴンに対応するポリゴンデータが、ポリゴンモデルデータから削除される。
　また本実施形態では、不可視ポリゴン削除処理の際に、それぞれの仮想空間画像５４において可視ポリゴン３４ｄとして特定されたポリゴン３４については、法線方向修正処理が実行される。
　ここでは例えば図１２Ａに示すように、可視ポリゴン３４ｄの法線方向が仮想カメラ５２に向かっていない場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１増加する。すなわち仮想カメラ５２による撮影方向のベクトルＶ１と可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積が正である場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１増加する。
　逆に例えば図１２Ｂに示すように、可視ポリゴン３４ｄの法線方向が仮想カメラ５２に向かっている場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１減少する。すなわち仮想カメラ５２による撮影方向のベクトルＶ１と可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積が負である場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１減少する。なお、可視ポリゴン３４ｄに対応付けられる法線反転カウント値の初期値は０であることとする。
　そしてすべての仮想空間画像に対して法線反転カウント値の増加や減少が実行された結果において、対応付けられる法線反転カウント値が正である可視ポリゴン３４ｄが特定される。そして特定された可視ポリゴン３４ｄに対応付けられるポリゴンデータが示す法線方向が反転される。ここでは例えば、ポリゴンデータの頂点データに含まれる３つの点ＩＤのうち２番目の点ＩＤと３番目の点ＩＤの順序が入れ替わる。
　図６に示す最初ポリゴンモデル４０を構成するポリゴン３４が順次削除された結果、法線方向がポリゴンモデルの外表面の内側から外側に向かっていないポリゴン３４が存在することがある。このようなポリゴン３４についても上述の法線方向修正処理によって、その法線方向がポリゴン３４の外表面の内側から外側に向かうよう修正される。
　そして以上のようにして不可視ポリゴン削除処理及び法線方向修正処理が行われることで、図３に例示する最終ポリゴンモデル３０が生成される。
　ＧＰＵのレンダリング機能を用いれば、仮想空間画像５４は容易に生成できる。そして本実施形態ではこのように容易に生成可能な仮想空間画像５４に基づいて、可視ポリゴン３４ｄが特定されるため、不可視ポリゴンを容易に特定できる。
　以上で説明したように、本実施形態では、図５に例示する最初ポリゴンモデル４０からポリゴン３４を削除するというシンプルな処理によって、低処理負荷で、被写体２０を模した高精度の最終ポリゴンモデル３０を生成することができる。
　以下、本実施形態に係るポリゴンモデル生成装置１０の機能、及び、ポリゴンモデル生成装置１０で実行される処理についてさらに説明する。
　図１３は、本実施形態に係るポリゴンモデル生成装置１０で実装される機能の一例を示す機能ブロック図である。図１３に示すように、ポリゴンモデル生成装置１０は、機能的には例えば、撮影画像記憶部６０、カメラデータ記憶部６２、ポリゴンモデルデータ記憶部６４、撮影画像取得部６６、カメラデータ取得部６８、点群データ生成部７０、最初ポリゴンモデル生成部７２、点密度値決定部７４、閾値決定部７６、長辺ポリゴン削除部７８、対応カメラ位置特定部８０、交差ポリゴン削除部８２、可視属性設定部８４、仮想カメラ配置部８６、仮想空間画像生成部８８、可視ポリゴン特定部９０、法線方向修正部９２、不可視ポリゴン削除部９４、を含んでいる。
　撮影画像記憶部６０、カメラデータ記憶部６２、ポリゴンモデルデータ記憶部６４は、記憶部１４を主として実装される。撮影画像取得部６６、カメラデータ取得部６８、点群データ生成部７０、最初ポリゴンモデル生成部７２、点密度値決定部７４、閾値決定部７６、長辺ポリゴン削除部７８、対応カメラ位置特定部８０、交差ポリゴン削除部８２、可視属性設定部８４、仮想カメラ配置部８６、仮想空間画像生成部８８、可視ポリゴン特定部９０、法線方向修正部９２、不可視ポリゴン削除部９４は、プロセッサ１２を主として実装される。
　以上の機能は、コンピュータであるポリゴンモデル生成装置１０にインストールされた、以上の機能に対応する指令を含むプログラムをプロセッサ１２で実行することにより実装されてもよい。このプログラムは、例えば、光ディスク、磁気ディスク、磁気テープ、光磁気ディスク、フラッシュメモリ等のコンピュータ読み取り可能な情報記憶媒体を介して、あるいは、インターネットなどを介してポリゴンモデル生成装置１０に供給されてもよい。
　撮影画像記憶部６０は、本実施形態では例えば、実空間２２において実カメラ２４が被写体２０を撮影した１又は複数の撮影画像を記憶する。撮影画像記憶部６０は、デプス画像などといった深さ情報に関連付けられた撮影画像を記憶してもよい。
　カメラデータ記憶部６２は、本実施形態では例えば、撮影画像を撮影した際における、実空間２２内における実カメラ２４の位置、向き、画角、などを示すカメラデータを記憶する。撮影画像記憶部６０に複数の撮影画像が記憶される場合は、カメラデータ記憶部６２には、それぞれ撮影画像に対応付けられる複数のカメラデータが記憶される。
　ポリゴンモデルデータ記憶部６４は、本実施形態では例えば、図５に例示する点データを複数含む点群データ、及び、図７に例示するポリゴンデータを複数含むポリゴンモデルデータを記憶する。
　撮影画像取得部６６は、本実施形態では例えば、撮影画像記憶部６０に記憶されている１又は複数の撮影画像を取得する。
　カメラデータ取得部６８は、本実施形態では例えば、カメラデータ記憶部６２に記憶されている１又は複数のカメラデータを取得する。
　点群データ生成部７０は、本実施形態では例えば、撮影画像取得部６６が取得する撮影画像、及び、カメラデータ取得部６８が取得するカメラデータに基づいて、点群データを生成して、生成された点群データをポリゴンモデルデータ記憶部６４に記憶させる。
　最初ポリゴンモデル生成部７２は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されている点群データに基づいて、複数のポリゴン３４を含む最初ポリゴンモデル４０を生成する。ここで例えば、それぞれポリゴンモデルデータ記憶部６４に記憶されている点群データが示す点群に属する点３６を頂点とする複数のポリゴン３４を含む最初ポリゴンモデル４０が生成されてもよい。そして最初ポリゴンモデル生成部７２は、本実施形態では例えば、生成された最初ポリゴンモデル４０をポリゴンモデルデータ記憶部６４に記憶させる。
　点密度値決定部７４は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されている点群データが示す点群の分布に基づいて、上述のようにして、当該点群に属するそれぞれの点３６に対応付けられる点密度の値を決定する。
　閾値決定部７６は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンデータが示すそれぞれのポリゴン３４について、上述のようにして、当該ポリゴン３４を構成する辺４２に対応付けられる閾値を決定する。ここで点密度の値が大きいほど当該点密度の値に対応付けられる閾値として小さな値が決定されるようにしてもよい。また閾値決定部７６は、点密度の値と閾値との対応規則を示すデータを保持していてもよい。そして閾値決定部７６は、このデータを用いて閾値を決定してもよい。
　長辺ポリゴン削除部７８は、本実施形態では例えば、ポリゴン３４を構成する辺４２の長さが、当該辺４２の端点に対応付けられる点密度の値に応じた閾値を超える場合に、当該ポリゴン３４をポリゴンモデルから削除する。ここで長辺ポリゴン削除部７８は、上述のようにして、対応づけられる閾値よりもその長さの方が大きな辺４２を含むポリゴン３４をポリゴンモデルから削除してもよい。また、対応づけられる閾値よりもその長さの方が大きな辺４２を含むポリゴン３４のポリゴンＩＤを含むポリゴンデータが、ポリゴンモデルデータから削除されてもよい。
　対応カメラ位置特定部８０は、本実施形態では例えば、カメラデータ取得部６８が取得するカメラデータに基づいて、当該カメラデータが示す実空間２２における実カメラ２４の位置に相当する仮想空間３２内の位置である対応カメラ位置を特定する。
　交差ポリゴン削除部８２は、本実施形態では例えば、仮想空間３２内におけるポリゴンモデルを望む位置と、点群データが示す点群に属する点３６の位置とを両端とする線分と交差するポリゴン３４を特定する。
　ここで上述のように、実カメラ２４の対応カメラ位置と、当該実カメラ２４によって撮影された撮影画像に像が含まれる被写体２０の表面に相当する点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。また、対応付けられる点密度の値が所定値よりも大きな点３６の少なくとも一部のそれぞれのみについて、当該点３６の位置と仮想空間３２内におけるポリゴンモデルを望む位置とを両端とする線分に交差するポリゴン３４が特定されてもよい。
　また例えば、仮想空間３２における、ポリゴンモデルの中心に対する無限遠点と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。また例えば、ポリゴンモデルの中心から、当該ポリゴンモデルを内包する球の半径の所定倍（例えば１．５倍や３倍など）以上離れた位置と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。
　また例えば、ユーザによって設定された仮想空間３２内におけるポリゴンモデルを望む位置と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。
　そして交差ポリゴン削除部８２は、本実施形態では例えば、特定されたポリゴン３４をポリゴンモデルから削除する。ここで例えば、特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータがポリゴンモデルデータから削除されてもよい。
　可視属性設定部８４は、本実施形態では例えば、仮想空間３２内に配置されている中間ポリゴンモデル５０を構成するそれぞれのポリゴン３４に、当該ポリゴン３４に対応付けられる可視属性を設定する。
　仮想カメラ配置部８６は、本実施形態では例えば、仮想空間３２内における仮想カメラ５２の位置及び撮影方向を決定する。ここで例えば、仮想カメラ配置部８６は、ユーザによる操作部１６の操作に応じて、仮想カメラ５２の位置や向きを変更してもよい。そして、仮想カメラ配置部８６は、ユーザの決定操作に応じて、仮想カメラ５２の配置を決定してもよい。
　仮想空間画像生成部８８は、本実施形態では例えば、仮想カメラ配置部８６により配置された仮想カメラ５２の位置から仮想カメラ５２の撮影方向を見た様子を表す仮想空間画像５４を生成する。ここで例えば、それぞれ互いに異なる位置から見た様子を表す複数の仮想空間画像５４が生成されてもよい。
　可視ポリゴン特定部９０は、本実施形態では例えば、仮想空間画像５４に基づいて、仮想カメラ５２から可視である可視ポリゴン３４ｄを特定する。
　法線方向修正部９２は、本実施形態では例えば、可視ポリゴン特定部９０が特定するそれぞれの可視ポリゴン３４ｄに対して、上述の法線方向修正処理を実行する。
　不可視ポリゴン削除部９４は、本実施形態では例えば、仮想空間３２内に設定される１又は複数の仮想カメラ５２のいずれにおいても不可視なポリゴン３４である不可視ポリゴンを特定する。そして不可視ポリゴン削除部９４は、本実施形態では例えば、特定される不可視ポリゴンをポリゴンモデルから削除する。ここで例えば、不可視ポリゴンのポリゴンＩＤを含むポリゴンデータが、ポリゴンモデルデータから削除されてもよい。またいずれの仮想空間画像５４においても可視ポリゴン３４ｄとして特定されなかったポリゴン３４に対応付けられるポリゴンデータが、ポリゴンモデルデータから削除されてもよい。
　ここで、本実施形態に係るポリゴンモデル生成装置１０で行われる処理の流れの一例を、図１４に例示するフロー図を参照しながら説明する。なお以下の処理例では、以下の処理の開始の際には空である可視ポリゴンＩＤリストが可視ポリゴン特定部９０によって保持されていることとする。
　まず、撮影画像取得部６６が、撮影画像記憶部６０に記憶されている１又は複数の撮影画像を取得する（Ｓ１０１）。そしてカメラデータ取得部６８が、カメラデータ記憶部６２に記憶されている、Ｓ１０１に示す処理で取得された撮影画像に対応付けられるカメラデータを取得する（Ｓ１０２）。本処理例ではＳ１０１に示す処理で複数の撮影画像が取得され、Ｓ１０２に示す処理でそれぞれ撮影画像に対応付けられる複数のカメラデータが取得されることとする。
　そして点群データ生成部７０が、複数の点データを含む点群データを生成して、生成された点群データをポリゴンモデルデータ記憶部６４に記憶させる（Ｓ１０３）。ここでＳ１０１に示す処理で取得された撮影画像に基づいて点群データが生成されてもよい。あるいはＳ１０１に示す処理で取得された撮影画像及びＳ１０２に示す処理で取得されたカメラデータに基づいて点群データが生成されてもよい。
　そして最初ポリゴンモデル生成部７２が、Ｓ１０３に示す処理で記憶された点群データに基づいて、最初ポリゴンモデル４０のポリゴンモデルデータを生成して、生成されたポリゴンモデルデータをポリゴンモデルデータ記憶部６４に記憶させる(Ｓ１０４)。
　そして上述の長辺ポリゴン削除処理（Ｓ１０５）、交差ポリゴン削除処理（Ｓ１０６）、不可視ポリゴン削除処理（Ｓ１０７）の順に処理が実行され、最終ポリゴンモデル３０に対応付けられるポリゴンモデルデータが最終的には生成される。
　以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０５に示す長辺ポリゴン削除処理の流れの一例を、図１５に例示するフロー図を参照しながら説明する。
　まず、点密度値決定部７４が、Ｓ１０３に示す処理で記憶された点群データが示す点群の分布に基づいて、当該点群データに含まれる複数の点データのそれぞれに対応する点３６について、当該点３６に対応する点密度の値を決定する（Ｓ２０１）。
　そして閾値決定部７６が、Ｓ１０４に示す処理で生成されるポリゴンモデルデータに含まれる複数のポリゴンデータのそれぞれについて、当該ポリゴンデータが示すポリゴン３４の辺４２に対応付けられる閾値を決定する（Ｓ２０２）。ここで例えば、辺４２は、ポリゴンデータの頂点データに含まれる２つの点ＩＤの組合せに対応付けられる点３６の組合せに対応する。そしてこれら２つの点ＩＤのそれぞれに対応付けられる点３６についてＳ１０５に示す処理で決定された点密度の値に基づいて、辺４２に対応付けられる閾値は決定可能である。
　そして長辺ポリゴン削除部７８は、Ｓ２０２に示す処理で閾値が決定された辺４２のなかから、辺４２の長さが当該辺４２について決定された閾値を超える辺４２を含むポリゴン３４を特定する（Ｓ２０３）。
　そして長辺ポリゴン削除部７８は、Ｓ２０３に示す処理で特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ２０４）。そして長辺ポリゴン削除処理（Ｓ１０５）は終了される。
　以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０６に示す交差ポリゴン削除処理の流れの一例を、図１６に例示するフロー図を参照しながら説明する。
　まず対応カメラ位置特定部８０が、Ｓ１０２に示す処理で取得されたカメラデータに基づいて、それぞれカメラデータに対応付けられる、実カメラ２４の対応カメラ位置を特定する（Ｓ３０１）。本処理例ではカメラデータが複数取得されるので、対応カメラ位置は複数特定される。
　そして交差ポリゴン削除部８２が、Ｓ３０１に示す処理で特定された対応カメラ位置のうちから、以下のＳ３０３～Ｓ３０７に示す処理が実行されていない１つを選択する（Ｓ３０２）。
　そして、交差ポリゴン削除部８２は、Ｓ３０２に示す処理で選択された対応カメラ位置に対応する実カメラ２４が撮影した撮影画像を特定する（Ｓ３０３）。
　そして交差ポリゴン削除部８２は、Ｓ３０３に示す処理で特定された撮影画像に像が含まれる被写体２０の表面に相当する複数の点３６を特定する（Ｓ３０４）。
　そして交差ポリゴン削除部８２は、Ｓ３０４に示す処理で特定された複数の点３６のうちから、Ｓ２０１に示す処理で決定された、対応付けられる点密度の値が所定値よりも大きいものを抽出する（Ｓ３０５）。
　そして交差ポリゴン削除部８２は、Ｓ３０５に示す処理で抽出された複数の点３６のそれぞれについて、当該点３６の位置とＳ３０１に示す処理で選択された対応カメラ位置とを両端とする線分を交差するポリゴン３４を特定する（Ｓ３０６）。
　そして交差ポリゴン削除部８２は、Ｓ３０６に示す処理で特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ３０７）。
　そして交差ポリゴン削除部８２は、Ｓ３０２に示す処理で未選択である、Ｓ３０３～Ｓ３０７に示す処理が実行されていない対応カメラ位置が存在するかを確認する（Ｓ３０８）。存在する場合は（Ｓ３０８：Ｙ）、Ｓ３０２に示す処理に戻る。存在しない場合は（Ｓ３０８：Ｎ）、交差ポリゴン削除処理（Ｓ１０６）は終了される。
　以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０７に示す不可視ポリゴン削除処理の流れの一例を、図１７に例示するフロー図を参照しながら説明する。
　まず、可視属性設定部８４が、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータに含まれるポリゴンデータのそれぞれに対して互いに異なる可視属性を設定する（Ｓ４０１）。
　そして仮想カメラ配置部８６が、仮想空間３２内における、ポリゴンモデルを望む仮想カメラ５２の位置、及び、仮想カメラ５２の撮影方向を決定する（Ｓ４０２）。ここで例えば、位置及び撮影方向がランダムに決定されてもよいし、ユーザの指定に応じて位置及び撮影方向が決定されてもよい。
　そして仮想空間画像生成部８８が、仮想カメラ５２の位置から仮想カメラ５２の撮影方向を見た様子を表す仮想空間画像５４を生成する（Ｓ４０３）。
　そして可視ポリゴン特定部９０が、Ｓ４０３に示す処理で生成された仮想空間画像５４に基づいて、仮想カメラ５２から可視である可視ポリゴン３４ｄを特定する（Ｓ４０４）。
　そして可視ポリゴン特定部９０が、Ｓ４０４に示す処理で特定された可視ポリゴン３４ｄのポリゴンＩＤを可視ポリゴンＩＤリストに追加する（Ｓ４０５）。なお本処理例では、可視ポリゴンＩＤリストにポリゴンＩＤが追加される際に、初期値が０である法線反転カウント値が当該ポリゴンＩＤに関連付けられることとする。
　そして法線方向修正部９２は、Ｓ１２０に示す処理で特定された可視ポリゴン３４ｄのそれぞれについて、仮想カメラ５２による撮影方向のベクトルＶ１と当該可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積の値を計算する（Ｓ４０６）。
　そして法線方向修正部９２は、Ｓ４０５に示す処理で計算される内積の値に応じて、可視ポリゴンＩＤリストに含まれるポリゴンＩＤに関連付けられている法線反転カウント値を更新する（Ｓ４０７）。ここで例えば、計算された内積の値が正である可視ポリゴン３４ｄのポリゴンＩＤに関連付けられている法線反転カウント値は１増加される。また、計算された内積の値が負である可視ポリゴン３４ｄのポリゴンＩＤに関連付けられている法線反転カウント値は１減少される。
　そして不可視ポリゴン削除部９４が、Ｓ４０３～Ｓ４０７に示す処理が予め定められた回数だけ繰り返し実行されたか否かを確認する（Ｓ４０８）。ここで実行回数が予め定められた回数に達していないことが確認されたとする（Ｓ４０８：Ｎ）。この場合は、仮想カメラ配置部８６が、仮想空間３２内における、ポリゴンモデルを望む仮想カメラ５２の位置、及び、仮想カメラ５２の撮影方向を変更して（Ｓ４０９）、Ｓ４０３に示す処理に戻る。ここで位置及び撮影方向は、ランダムに変更されてもよいし、ユーザが指定した位置及び撮影方向に変更されてもよい。
　Ｓ４０８に示す処理において、実行回数が予め定められた回数に達したことが確認されたとする（Ｓ４０８：Ｙ）。この場合、法線方向修正部９２が、可視ポリゴン特定部９０が保持する可視ポリゴンＩＤリストに含まれるポリゴンＩＤのうちから、関連付けられている法線反転カウント値が正であるポリゴンＩＤを特定する（Ｓ４１０）。
　そして法線方向修正部９２は、ポリゴンモデルデータ記憶部６４に記憶されている、Ｓ４０９に示す処理で特定されたポリゴンＩＤを含むポリゴンデータが表す法線方向を反転させる（Ｓ４１１）。Ｓ４１１に示す処理では例えば、法線方向修正部９２が、Ｓ４１０に示す処理で特定されたポリゴンＩＤを含むポリゴンデータの頂点データに含まれる３つの点ＩＤのうち２番目の点ＩＤと３番目の点ＩＤの順序を入れ替える。
　そして不可視ポリゴン削除部９４が、可視ポリゴン特定部９０が保持する可視ポリゴンＩＤリスト及びポリゴンモデルデータ記憶部６４に記憶されているポリゴンデータに基づいて、不可視ポリゴンを特定する（Ｓ４１２）。
　そして不可視ポリゴン削除部９４が、Ｓ４１１に示す処理で特定された不可視ポリゴンのポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ４１３）。そして不可視ポリゴン削除処理（Ｓ１０７）は終了される。
　なお図１７に示す処理例において、Ｓ４０６、Ｓ４０７、Ｓ４１０、及び、Ｓ４１１に示す処理が、上述の法線方向修正処理に相当する。
　以上で説明した処理例において、例えば、Ｓ１０５に示す長辺ポリゴン削除処理が実行されずに、Ｓ１０６に示す交差ポリゴン削除処理が実行されてもよい。またＳ１０５に示す長辺ポリゴン削除処理の代わりに、所定長よりも長い辺４２を含むポリゴン３４を一律で削除する処理が実行されてもよい。また所定長よりも長い辺４２を含むポリゴン３４を一律で削除する処理が実行された後に、Ｓ１０５に示す長辺ポリゴン削除処理が実行されてもよい。
　またＳ３０５に示す処理が実行されず、Ｓ３０４に示す処理で特定されたすべての点３６について、Ｓ３０６、Ｓ３０７に示す処理が実行されてもよい。
　また上述のＳ４０３～Ｓ４０９に示す処理が繰り返し処理として実行されるのではなく、Ｓ４０２に示す処理で仮想カメラ５２の位置及び仮想カメラ５２の撮影方向が複数決定されるようにした上で、Ｓ４０３～Ｓ４０７に示す処理が並列処理で実行されてもよい。
　またＳ１０５に示す長辺ポリゴン削除処理やＳ１０６に示す交差ポリゴン削除処理が実行されていないポリゴンモデルに対して、Ｓ１０７に示す不可視ポリゴン削除処理が実行されてもよい。またＳ１０６に示す交差ポリゴン削除処理が実行された後にＳ１０７に示す不可視ポリゴン削除処理が実行されなくてもよい。
　なお、本発明は上述の実施形態に限定されるものではない。
　また、上記の具体的な文字列や数値及び図面中の具体的な文字列や数値は例示であり、これらの文字列や数値には限定されない。

Claims (7)

  1. 　仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成部と、
    　前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定部と、
    　前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除部と、
    　を含むことを特徴とするポリゴンモデル生成装置。
  2. 　実空間において実カメラが被写体を撮影した画像を取得する画像取得部と、
    　前記画像に基づいて、属する点がそれぞれ前記実空間内における前記被写体上の点に相当する前記点群データを生成する点群データ生成部と、
    　前記被写体を撮影した際の前記実カメラの前記実空間内における位置に相当する、前記仮想空間内の位置を特定する対応カメラ位置特定部と、をさらに含み、
    　前記交差ポリゴン特定部は、前記対応カメラ位置特定手順で特定される位置を前記第１位置として前記交差ポリゴンを特定する、
    　ことを特徴とする請求項１に記載のポリゴンモデル生成装置。
  3. 　前記仮想空間内に設定される１又は複数の仮想カメラのいずれにおいても不可視な前記ポリゴンである不可視ポリゴンを特定する不可視ポリゴン特定部と、
    　前記不可視ポリゴンを前記ポリゴンモデルから削除する不可視ポリゴン削除部と、をさらに含む、
    　ことを特徴とする請求項１又は２に記載のポリゴンモデル生成装置。
  4. 　前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定部と、
    　前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除部と、をさらに含む、
    　ことを特徴とする請求項１から３のいずれか一項に記載のポリゴンモデル生成装置。
  5. 　前記交差ポリゴン特定部は、対応付けられる前記点密度の値が所定値よりも大きな点の少なくとも一部のそれぞれのみについて、当該点の位置を前記第２位置として前記交差ポリゴンを特定する、
    　ことを特徴とする請求項４に記載のポリゴンモデル生成装置。
  6. 　仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成ステップと、
    　前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定ステップと、
    　前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除ステップと、
    　を含むことを特徴とするポリゴンモデル生成方法。
  7. 　仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成手順、
    　前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定手順、
    　前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除手順、
    　をコンピュータに実行させることを特徴とするプログラム。
PCT/JP2017/013326 2017-03-30 2017-03-30 ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム WO2018179253A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
PCT/JP2017/013326 WO2018179253A1 (ja) 2017-03-30 2017-03-30 ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム
US16/494,023 US11107278B2 (en) 2017-03-30 2017-03-30 Polygon model generating apparatus, polygon model generation method, and program
JP2019508036A JP6700480B2 (ja) 2017-03-30 2017-03-30 ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2017/013326 WO2018179253A1 (ja) 2017-03-30 2017-03-30 ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム

Publications (1)

Publication Number Publication Date
WO2018179253A1 true WO2018179253A1 (ja) 2018-10-04

Family

ID=63674433

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2017/013326 WO2018179253A1 (ja) 2017-03-30 2017-03-30 ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム

Country Status (3)

Country Link
US (1) US11107278B2 (ja)
JP (1) JP6700480B2 (ja)
WO (1) WO2018179253A1 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2021150553A1 (en) 2020-01-22 2021-07-29 Vntana, Inc. Mesh optimization for computer graphics
CN117576140A (zh) * 2024-01-17 2024-02-20 四川省公路规划勘察设计研究院有限公司 基于三维点云道路模型投影轮廓获取方法
JP7591352B2 (ja) 2019-04-10 2024-11-28 ダッソー システムズ 実際のシーンの構造の３ｄ再構成

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111814235A (zh) * 2020-07-01 2020-10-23 广东博智林机器人有限公司 车位排布优化和多边形简化方法、装置、设备和存储介质
CN112927369B (zh) * 2021-02-22 2023-04-18 中铁二院工程集团有限责任公司 一种三维模型的表面法线一致性修复方法及体积计算方法
US11263804B1 (en) * 2021-09-13 2022-03-01 Illuscio, Inc. Systems and methods for efficient point cloud visualization based on a hybrid rendering of data points and meshes
JP7442604B1 (ja) * 2022-11-29 2024-03-04 株式会社バンダイ 画像処理方法、情報処理装置、及び、コンピュータプログラム

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002222430A (ja) * 2001-01-26 2002-08-09 Nippon Telegr & Teleph Corp <Ntt> ３次元ポリゴンメッシュを生成する方法、装置、プログラム及びプログラムを記録したコンピュータ読み取り可能な記録媒体
JP2007322351A (ja) * 2006-06-05 2007-12-13 Mitsubishi Electric Corp ３次元物体照合装置
JP2012146262A (ja) * 2011-01-14 2012-08-02 Toshiba Corp 構造物計測システム
US20150363665A1 (en) * 2014-06-16 2015-12-17 Sony Corporation 3d scanning with depth cameras using mesh sculpting

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE112005003003T5 (de) * 2004-12-10 2007-11-15 Kyoto University System, Verfahren und Programm zum Komprimieren von dreidimensionalen Bilddaten sowie Aufzeichnungsmedium hierfür
WO2007083602A1 (ja) * 2006-01-23 2007-07-26 National University Corporation Yokohama National University 補間処理方法、補間処理装置、形状評価方法、および形状評価装置
US8243070B1 (en) * 2008-04-18 2012-08-14 Adobe Systems Incorporated Triangulation for accelerated rendering of polygons
EP2372653B1 (en) * 2008-12-24 2015-07-22 Sony Computer Entertainment Inc. Image processing device and image processing method
US9330490B2 (en) * 2011-04-29 2016-05-03 University Health Network Methods and systems for visualization of 3D parametric data during 2D imaging
JP5773944B2 (ja) * 2012-05-22 2015-09-02 株式会社ソニー・コンピュータエンタテインメント 情報処理装置および情報処理方法
US9710462B2 (en) * 2013-01-29 2017-07-18 Learning Sites, Inc. System and method for automatically translating an imaged surface of an object
US9547838B2 (en) * 2013-11-06 2017-01-17 Oracle International Corporation Automated generation of a three-dimensional space representation and planogram verification
US10818066B2 (en) * 2016-11-24 2020-10-27 Ajou University Industry-Academic Cooperation Foundation Visualization method and device for multi-dimensional data analysis

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002222430A (ja) * 2001-01-26 2002-08-09 Nippon Telegr & Teleph Corp <Ntt> ３次元ポリゴンメッシュを生成する方法、装置、プログラム及びプログラムを記録したコンピュータ読み取り可能な記録媒体
JP2007322351A (ja) * 2006-06-05 2007-12-13 Mitsubishi Electric Corp ３次元物体照合装置
JP2012146262A (ja) * 2011-01-14 2012-08-02 Toshiba Corp 構造物計測システム
US20150363665A1 (en) * 2014-06-16 2015-12-17 Sony Corporation 3d scanning with depth cameras using mesh sculpting

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
NISHITANI SUBARU ET AL.: "Representing a 3D scene from selected optimum textures by using a multi-view stereo", IPSJ SIG NOTES COMPUTER VISION AND IMAGE MEDIA, 23 May 2013 (2013-05-23), pages 1 - 8 *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7591352B2 (ja) 2019-04-10 2024-11-28 ダッソー システムズ 実際のシーンの構造の３ｄ再構成
WO2021150553A1 (en) 2020-01-22 2021-07-29 Vntana, Inc. Mesh optimization for computer graphics
EP4094231A4 (en) * 2020-01-22 2024-06-05 Vntana, Inc. MESH OPTIMIZATION FOR COMPUTER GRAPHICS
CN117576140A (zh) * 2024-01-17 2024-02-20 四川省公路规划勘察设计研究院有限公司 基于三维点云道路模型投影轮廓获取方法

Also Published As

Publication number Publication date
JPWO2018179253A1 (ja) 2019-07-04
US11107278B2 (en) 2021-08-31
JP6700480B2 (ja) 2020-05-27
US20200027268A1 (en) 2020-01-23

Similar Documents

Publication Publication Date Title
WO2018179253A1 (ja) ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラム
US11529762B2 (en) System and method of 3D print modelling
CN110574076B (zh) 图像生成设备、图像生成方法和计算可读存储介质
US10974459B2 (en) Parallel method of flood filling, and apparatus
US10137646B2 (en) Preparing a polygon mesh for printing
EP2051533B1 (en) 3D image rendering apparatus and method
EP3649621B1 (en) 3d modelling for 3d printing of objects having zero-thickness parts
US8797360B2 (en) Image display device, method for controlling image display device, and information storage medium
US20130057574A1 (en) Storage medium recorded with program, information processing apparatus, information processing system, and information processing method
US10217259B2 (en) Method of and apparatus for graphics processing
CN110956695A (zh) 信息处理装置、信息处理方法和存储介质
GB2562101A (en) System and method of 3D print modelling
WO2018179254A1 (ja) 画像生成装置、画像生成方法及びプログラム
JP7479793B2 (ja) 画像処理装置、仮想視点映像を生成するシステム、画像処理装置の制御方法及びプログラム
JP7313811B2 (ja) 画像処理装置、画像処理方法、及びプログラム
JP2000339465A (ja) ３次元形状の対応付け方法
JP7614801B2 (ja) 画像処理装置、画像処理方法及びプログラム
JP2020013390A (ja) 情報処理装置、情報処理プログラム及び情報処理方法
KR930003811B1 (ko) 3차원도형 처리방법 및 그 장치
JP7698754B1 (ja) 画像処理プログラム、画像処理システム、画像処理方法、および画像処理装置
JP6660159B2 (ja) 情報処理装置、情報処理装置の制御方法およびプログラム
JPH11175758A (ja) 立体表示方法および装置
JP2025116987A (ja) 画像処理プログラム、画像処理システム、画像処理方法、および画像処理装置
JP2025116986A (ja) 画像処理プログラム、画像処理システム、画像処理方法、および画像処理装置
CN120393404A (zh) 计算机程序产品、信息处理系统、信息处理装置以及信息处理方法

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 17904086

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2019508036

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 17904086

Country of ref document: EP

Kind code of ref document: A1