Automatic generating device for 3-d structure shape, automatic generating method, program therefor, and recording medium recording the program

• US 20040041805A1
• Filed: 06/02/2003
• Published: 03/04/2004
• Est. Priority Date: 07/31/2001
• Status: Active Grant

• Current Assignee: CAD Center Corporation
• Original Assignee: CAD Center Corporation
• Inventors: Hayano, Tomoaki, Sone, Atsushi, Goh, Bujin
• Granted Patent: US 7,098,909 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation

Abstract

An automatic three-dimensional structure shape generation apparatus for automatically generating the shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information includes means for constituting a point group by collecting points such that three-dimensional distances between the points are within a predetermined threshold or two-dimensional distances and height differences between the points are within predetermined thresholds, means for detecting a polygon that includes the points of the point group at a minimum area from at least one of a plurality of predetermined polygons, and means for generating an outer shape or a rooftop shape of the three-dimensional structure from the polygon having the minimum area.

Claims

1. An automatic three-dimensional structure shape generation apparatus for automatically generating a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, comprising:

means for constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

means for detecting a polygon that includes the points of the point group at a minimum area from at least one of a plurality of predetermined polygons; and

means for generating one of an outer shape and a rooftop shape of the three-dimensional structure based on said detected polygon having the minimum area.

2. The automatic three-dimensional structure shape generation apparatus as claimed in claim 1, wherein said means for detecting the polygon having the minimum area gradually rotate one of all points of said point group and at least one of the predetermined polygons by a unit of a predetermined angle so as to find an angle at which said polygon has a minimum area.

3. The automatic three-dimensional structure shape generation apparatus as claimed in one of claim 1 and claim 2, wherein said means for detecting the polygon having the minimum area detect the polygon that includes the points of the point group at the minimum area based on an angle at which an edge of said polygon that includes the point group coincides with a predetermined direction vector.

4. The automatic three-dimensional structure shape generation apparatus as claimed in one of claim 1 through claim 3, further comprising one of means for removing an overflow portion of one of the generated outer shape and the generated rooftop shape of the three-dimensional structure from a corresponding building shape in a two-dimensional electronic map and means for arranging one of the generated outer shape and the generated rooftop shape of the three-dimensional structure such that said generated one is included in said corresponding building shape in the two-dimensional electronic map.

5. An automatic three-dimensional structure shape generation apparatus for automatically generating a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, comprising:

means for constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

means for using height information z (z>

0) of the points of the point group and a predetermined function to determine a coefficient of said function such that errors between said points and said function are minimized; and

means for generating the shape of the three-dimensional structure based on said coefficient.

6. The automatic three-dimensional structure shape generation apparatus as claimed in claim 5, wherein said means for generating the shape of the three-dimensional structure based on the coefficient compute at least one coefficient of one of a power series function whose order is higher than or equal to a first order and a linear combination function of an elementary function in accordance with a least square method, and generate a roof shape of the three-dimensional structure based on a size relation of said at least one coefficient.

7. The automatic three-dimensional structure shape generation apparatus as claimed in claim 5, wherein said means for generating the shape of the three-dimensional structure based on the coefficient extract a plurality of points, which are located at higher positions, from the point group, find one of a line and a curve such that errors between said plural points located at higher positions and said one are minimized, and generate a roof shape by determining said one as a roof edge.

8. An automatic three-dimensional structure shape generation method for automatically generating a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, the automatic three-dimensional structure shape generation method comprising the steps of:

constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

detecting a polygon that includes the points of the point group at a minimum area from at least one of a plurality of predetermined polygons; and

generating one of an outer shape and a rooftop shape of the three-dimensional structure based on said polygon having the minimum area.

9. The automatic three-dimensional structure shape generation method as claimed in claim 8, wherein said step of detecting the polygon having the minimum area gradually rotates one of all points of said point group and at least one of the predetermined polygons by a unit of a predetermined angle so as to find an angle at which said polygon has a minimum area.

10. The automatic three-dimensional structure shape generation method as claimed in one of claim 8 and claim 9, wherein said step of detecting the polygon having the minimum area detects the polygon that includes the points of the point group at the minimum area based on an angle at which an edge of said polygon that includes the point group coincides with a predetermined direction vector.

11. The automatic three-dimensional structure shape generation method as claimed in one of claim 8 through claim 10, further comprising one of a step of removing an overflow portion of one of the generated outer shape and the generated rooftop shape of the three-dimensional structure based on a corresponding building shape in a two-dimensional electronic map and a step of arranging one of the generated outer shape and the generated rooftop shape of the three-dimensional structure such that said generated one is included in said corresponding building shape in the two-dimensional electronic map.

12. An automatic three-dimensional structure shape generation method for automatically generating a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, the automatic three-dimensional structure shape generation method comprising the steps of:

constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

using height information z (z>

0) of the points of the point group and a predetermined function to determine a coefficient of said function such that errors between said points and said function are minimized; and

generating the shape of the three-dimensional structure based on said coefficient.

13. The automatic three-dimensional structure shape generation method as claimed in claim 12, wherein said step of generating the shape of the three-dimensional structure based on the coefficient computes at least one coefficient of one of a power series function whose order is higher than or equal to a first order and a linear combination function of an elementary function in accordance with a least square method, and generates a roof shape of the three-dimensional structure based on a size relation of said at least one coefficient.

14. The automatic three-dimensional-structure shape generation method as claimed in claim 12, wherein said step of generating the shape of the three-dimensional structure based on the coefficient extracts a plurality of points, which are located at higher positions, from the point group, finds one of a line and a curve such that errors between said plural points located at higher positions and said one are minimized, and generates a roof shape by determining said one as a roof edge.

15. A program for causing a computer to automatically generate a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, comprising the steps of:

constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

detecting a polygon that includes the points of the point group at a minimum area from at least one of a plurality of predetermined polygons; and

generating one of an outer shape and a rooftop shape of the three-dimensional structure based on said detected polygon having the minimum area.

16. The program as claimed in claim 15, wherein said step of detecting the polygon having the minimum area gradually rotates one of all points of said point group and at least one of the predetermined polygons by a unit of a predetermined angle so as to find an angle at which said polygon has a minimum area.

17. The program as claimed in one of claim 15 and claim 16, wherein said step of detecting the polygon having the minimum area detects the polygon that includes the points in the point group at the minimum area based on an angle at which an edge of said polygon that includes the point group coincides with a predetermined direction vector.

18. The program as claimed in one of claim 15 through claim 17, further comprising one of a step of removing an overflow portion of one of the generated outer shape and the generated rooftop shape of the three-dimensional structure from a corresponding building shape in a two-dimensional electronic map and a step of arranging one of the generated outer shape and the generated rooftop shape of the three-dimensional structure such that said generated one is included in said corresponding building shape in the two-dimensional electronic map.

22. A recording medium for recording the program as claimed in one of claim 15 through claim 21.

19. A program for causing a computer to automatically generate a shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, comprising the steps of:

constituting a point group by collecting such points that three-dimensional distances between said points are within a predetermined threshold or two-dimensional distances and height differences between said points are within predetermined thresholds;

using height information z (z>

0) of the points of the point group and a predetermined function to determine a coefficient of said function such that errors between said points and said function are minimized; and

generating the shape of the three-dimensional structure based on said coefficient.

20. The program as claimed in claim 19, wherein said step of generating the shape of the three-dimensional structure based on the coefficient computes at least one coefficient of one of a power series function whose order is higher than or equal to a first order and a linear combination function of an elementary function in accordance with a least square method, and generates a roof shape of the three-dimensional structure based on a size relation of said at least one coefficient.

21. The program as claimed in claim 19, wherein said step of generating the shape of the three-dimensional structure based on the coefficient extracts a plurality of points, which are located at higher positions, from the point group, finds one of a line and a curve such that errors between said plural points located at higher positions and said one are minimized, and generates a roof shape by determining said one as a roof edge.