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

• US 7,098,909 B2
• Filed: 09/28/2002
• Issued: 08/29/2006
• Est. Priority Date: 07/31/2001
• Status: Expired due to Fees

• Current Assignee: CAD Center Corporation
• Original Assignee: CAD Center Corporation
• Inventors: Hayano, Tomoaki, Hayano, Naomi, Goh, Bujin, Sone, Atsushi
• Primary Examiner(s): Chauhan, Ulka J.
• Assistant Examiner(s): BROOME, SAID A
• Application Number:
  US10/433,315
• Publication Number:
  US 20040041805A1
• Time in Patent Office: 1,431 Days
• Field of Search: 345/419, 345/420, 345/619, 701/211
• US Class Current: 345/420
• 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 apparatus for automatically generating an outer or rooftop 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 end a rooftop shape of the three-dimensional structure based on said detected polygon having the minimum area,

wherein said means for 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.

2. The apparatus as claimed in claim 1, wherein said means for 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.

3. The apparatus as claimed in claim 1, further comprising at least 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.

4. An 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.

5. The apparatus as claimed in claim 4, wherein said means for 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 generate a roof shape of the three-dimensional structure based on a size relation of said at least one coefficient.

6. The apparatus as claimed in claim 4, wherein said means for 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.

7. A method for generating an outer or rooftop 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,

wherein said step of detecting a 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.

8. The method as claimed in claim 7, 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.

9. The method as claimed in claim 7 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.

10. A method for automatically generating an outer or rooftop 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.

11. The method as claimed in claim 10, 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.

12. The method as claimed in claim 10, 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.

13. A program for causing a computer to generate an outer or rooftop shape of a three-dimensional structure from a plurality of points having three-dimensional coordinates containing height information, said program performing operations that comprise 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,

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.

14. The program as claimed in claim 13 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.

15. The program as claimed in claim 13 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.

16. A program for causing a computer to automatically generate an outer or rooftop 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 (where 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.

17. The program as claimed in claim 16, 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.

18. The program as claimed in claim 16, 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.

19. A computer-readable media having stored thereon instructions, which when executed by one or more processors, cause one or more processors to perform acts comprising:

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 paints 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,

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.