Real-time lines-of-sight and viewsheds determination system

• US 8,400,448 B1
• Filed: 08/10/2009
• Issued: 03/19/2013
• Est. Priority Date: 12/05/2007
• Status: Active Grant

• Current Assignee: Navy The USA As Represented By The Secretary of The
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Doyle, Robert J Jr.
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): Tseng, Charles
• Application Number:
  US12/461,350
• Time in Patent Office: 1,317 Days
• Field of Search: 345419-428
• US Class Current: 345/419
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A method for processing three-dimensional data that defines a three-dimensional scene, and determining and displaying lines-of-sight (LOS) and viewsheds on all visible surfaces of the scene, includes: i) assigning at a user-selected location at least one viewpoint in the scene; ii) applying ray tracing from locations in the scene to the viewpoint to determine locations in the scene that are in a line of sight (LOS) and outside the LOS of the viewpoint, thus determining the viewshed relative to the viewpoint while generating a set of color-coding information; iv) saving the set of color-coding information as a 2D texture image in graphics hardware memory; and v) compositing the 2D texture image over the 3D scene in a 3D window at a frame rate that enables real-time updating of the color coding as the scene is translated or rotated or the viewpoint is changed.

Claims

1. A computer software product for processing a three-dimensional scene, and determining and displaying lines-of-sight (LOS) and viewsheds in the scene, the product comprising a physical computer-readable medium including stored instructions that, when executed by a computer, cause the computer to:

i) assign at a user-selected location at least one viewpoint in the scene;

ii) apply ray tracing from locations in the scene to the viewpoint to determine locations in the scene that are in a line of sight (LOS) and outside the LOS of the viewpoint and thereby determining the viewshed relative to the viewpoint;

iii) color-code the scene whereby the color coding differentially indicates the locations in the line of sight (LOS) and outside the LOS of the viewpoint, thereby displaying a color-coded viewshed relative to the viewpoint;

iv) save the set of color-coding information as a 2D texture image in graphics hardware memory;

v) composite the 2D texture image over the 3D scene in a 3D window at a frame rate that enables real-time updating of the color coding as the scene is translated or rotated or the viewpoint is changed; and

vi) operate a graphical user interface (GUI) that includes a user-selected color-coding scheme for a display of safe headroom contours by coloring surfaces that have a near line of sight to an observer or multiple observers when rays are originated from points above said surfaces while differentially-coloring surfaces that are not in the direct line of sight whereby the safe headroom contours reveal whether people positioned on said surfaces can be seen by an observer.

2. The computer software product of claim 1, wherein the instructions for the GUI include the user-selecting range rings.

3. A system for acquiring three-dimensional data that defines a three-dimensional scene, and determining and displaying lines-of-sight (LOS) and viewsheds on all visible surfaces of the scene, comprising:

means for acquiring the three-dimensional data that includes data defining at least one elevation field of the scene with three-dimensional (3D) features within the scene;

a processor for receiving the elevation field data comprising a machine-readable storage media including stored instructions that, when executed by the processor, cause the processor to;

i) assign at a user-selected location at least one viewpoint in the scene;

ii) apply ray tracing from locations in the scene to the viewpoint to determine locations in the scene that are in a line of sight (LOS) and outside the LOS of the viewpoint and thereby determining the viewshed relative to the viewpoint;

iii) color-code the scene whereby the color coding differentially indicates the locations in the line of sight (LOS) and outside the LOS of the viewpoint, thereby displaying a color-coded viewshed relative to the viewpoint;

iv) save the set of color-coding information as a 2D texture image in graphics hardware memory;

v) composite the 2D texture image over the 3D scene in a 3D window at a frame rate that enables real-time updating of the color coding as the scene is translated or rotated or the viewpoint is changed; and

vi) operate a graphical user interface (GUI) that includes a user-selected color-coding scheme for a display of safe headroom contours by coloring surfaces that have a near line of sight to an observer or multiple observers when rays are originated from points above said surfaces while differentially-coloring surfaces that are not in the direct line of sight whereby the safe headroom contours reveal whether people positioned on said surfaces can be seen by an observer; and

a monitor for displaying the color-coded viewshed and scene, whereby a decision based on the color-coded viewshed may be made and implemented in a desired application.

4. The system of claim 3, wherein the instructions include displaying the viewpoint as that of a sniper positioned in the scene.

5. The system of claim 4, wherein the instructions include positioning multiple snipers in the scene and for the color-coding to indicate a viewshed relative to each of the multiple snipers.

6. The system of claim 5, wherein the instructions include indicating overlapping fields of fire or views from two or more snipers or observers.

7. The system of claim 3, wherein the instructions for the GUI include the user-selecting range rings.

8. The system of claim 3, wherein the application is personnel security protection.

9. The system of claim 3, wherein the application is convoy protection.

10. The system of claim 3, wherein the application is effectively positioning one or more snipers.

11. The system of claim 3, wherein the application is covert ingress and egress.

12. The system of claim 3, wherein the application is a construction project.

13. The system of claim 3, wherein the application is highway planning.

14. The system of claim 3, wherein the application is the positioning of video surveillance cameras.