System and method for procedurally generated building graphics within a street network of a three-dimensional virtual environment

• US 10,102,670 B2
• Filed: 08/18/2016
• Issued: 10/16/2018
• Est. Priority Date: 08/18/2016
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Ren, Liu, Zou, Lincan
• Primary Examiner(s): Liu, Zhengxi
• Application Number:
  US15/240,600
• Publication Number:
  US 20180053343A1
• Time in Patent Office: 789 Days
• Field of Search: 345418
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

A system and method of procedural generation of graphics corresponding to a plurality of buildings in a three-dimensional virtual environment includes identifying a region in the three-dimensional virtual environment that is enclosed by a plurality of streets within the three-dimensional virtual environment, generating a two-dimensional arrangement of a plurality of tiles within the region, identifying one building segment graphic in the subset of building segment graphics corresponding to each tile based on an array of pseudo-random index values stored in the memory for each tile in the plurality of tiles, and generating a graphical depiction of the three-dimensional virtual environment including a graphical depiction of the plurality of buildings in the region based on the two-dimensional arrangement of the plurality of tiles and the building segment graphic identified for each tile in the plurality of tiles.

Claims

1. A method for generating graphics corresponding to a plurality of buildings in a three-dimensional virtual environment comprising:

identifying, with a processor, a region in the three-dimensional virtual environment that is enclosed by a plurality of streets within the three-dimensional virtual environment;

identifying, with the processor, a rectangular portion of the region in the three-dimensional virtual environment;

generating, with the processor, a two-dimensional arrangement of a plurality of tiles only within the rectangular portion of the region, each tile corresponding to a subset of building segment graphics in a plurality of building segment graphics stored in a memory;

identifying, with the processor, one building segment graphic in the subset of building segment graphics for each tile in the plurality of tiles based on an array of pseudo-random index values stored in the memory, each index value corresponding to one building segment graphic in the subset of building segment graphics; and

generating, with the processor and a display device, a graphical depiction of the three-dimensional virtual environment including a graphical depiction of the plurality of buildings in the region based on the two-dimensional arrangement of the plurality of tiles and the one building segment graphic identified for each tile in the plurality of tiles.

2. The method of claim 1, the generating of the two-dimensional arrangement of the plurality of tiles further comprising:

generating, with the processor, the two-dimensional arrangement within the rectangular portion of the region including a first plurality of tiles having a first size, and a second plurality of tiles having a second size, the first size being greater than the second size, and the second plurality of tiles being formed in a margin of the rectangular portion of the region that cannot include an additional tile of the first size.

3. The method of claim 1 further comprising:

identifying, with the processor, coordinates of the region within the 3D virtual environment; and

retrieving, with the processor, the array of pseudo-random index values from a plurality of arrays of pseudo-random index values from the memory based on the coordinates.

4. The method of claim 1, the generating of the two-dimensional arrangement of the plurality of tiles within the region further comprising:

assigning, with the processor, a type code to each tile in the plurality of tiles based on an arrangement of sides of each tile in the plurality of tiles that are adjacent to another tile in the two-dimensional arrangement of the plurality of tiles; and

identifying, with the processor, the subset of building segment graphics corresponding to each tile based on the type code.

5. The method of claim 1, the identifying of the region in the three-dimensional virtual environment further comprising:

identifying, with the processor, a plurality of streets and a plurality of intersections between the plurality of streets in the three-dimensional virtual environment based on three-dimensional virtual environment data stored in the memory;

generating, with the processor, a directed graph including two half edges formed each pair of intersections in the plurality of intersections that are connected by streets in the plurality of streets; and

identifying the region in the three-dimensional virtual environment based on a loop in a portion of the half edges in the directed graph that enclose the region.

6. The method of claim 5 further comprising:

generating, with the processor, a bounding polygon around the region based on the plurality of streets in the three-dimensional virtual environment that correspond to the half edges in the directed graph that enclose the polygon; and

generating, with the processor, the two-dimensional arrangement of a plurality of tiles within the bounding polygon.

7. A graphics display system comprising:

a display device;

a memory configured to store data corresponding to;

a three-dimensional virtual environment including a plurality of streets; and

a plurality of building segment graphics for buildings in the three-dimensional virtual environment; and

a processor operatively connected to the memory and the display device, the processor being configured to;

identify a region in the three-dimensional virtual environment that is enclosed by the plurality of streets within the three-dimensional virtual environment;

identify a rectangular portion of the region in the three-dimensional virtual environment;

generate a two-dimensional arrangement of a plurality of tiles only within the rectangular portion of the region, each tile corresponding to a subset of building segment graphics in the plurality of building segment graphics;

identify one building segment graphic in the subset of building segment graphics for each tile in the plurality of tiles based on an array of pseudo-random index values stored in the memory, each index value corresponding to one building segment graphic in the subset of building segment graphics; and

generate a graphical depiction of the three-dimensional virtual environment with the display device, the graphical depiction including a plurality of buildings in the region based on the two-dimensional arrangement of the plurality of tiles and the one building segment graphic identified for each tile in the plurality of tiles.

8. The system of claim 7, the processor being further configured to:

generate the two-dimensional arrangement within the rectangular portion of the region including a first plurality of tiles having a first size, and a second plurality of tiles having a second size, the first size being greater than the second size, and the second plurality of tiles being formed in a margin of the rectangular portion of the region that cannot include an additional tile of the first size.

9. The system of claim 7, the processor being further configured to:

identify coordinates of the region within the 3D virtual environment; and

retrieve, the array of pseudo-random index values from a plurality of arrays of pseudo-random index values from the memory based on the coordinates.

10. The system of claim 7, the processor being further configured to:

assign a type code to each tile in the plurality of tiles based on an arrangement of sides of each tile in the plurality of tiles that are adjacent to another tile in the two-dimensional arrangement of the plurality of tiles; and

identify the subset of building segment graphics corresponding to each tile based on the type code.

11. The system of claim 7, the processor being further configured to:

identify a plurality of streets and a plurality of intersections between the plurality of streets in the three-dimensional virtual environment based on three-dimensional virtual environment data stored in the memory;

generate a directed graph including two half edges formed each pair of intersections in the plurality of intersections that are connected by streets in the plurality of streets; and

identify the region in the three-dimensional virtual environment based on a loop in a portion of the half edges in the directed graph that enclose the region.

12. The system of claim 11, the processor being further configured to:

generate a bounding polygon around the region based on the plurality of streets in the three-dimensional virtual environment that correspond to the half edges in the directed graph that enclose the polygon; and

generate the two-dimensional arrangement of a plurality of tiles within the bounding polygon.