Three-dimensional point-in-polygon operation to facilitate displaying three-dimensional structures

• US 9,842,432 B2
• Filed: 01/31/2017
• Issued: 12/12/2017
• Est. Priority Date: 01/27/2015
• Status: Active Grant

• Current Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Original Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Inventors: Hendrey, Geoffrey R.
• Primary Examiner(s): Mushambo, Martin
• Application Number:
  US15/421,290
• Publication Number:
  US 20170140575A1
• Time in Patent Office: 315 Days
• CPC Class Codes: A63F 13/537 using indicators, e.g. showing the condition of a game character on screen
• CPC Class Codes: A63F 13/577 using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
• CPC Class Codes: B64D 43/00 Arrangements or adaptations of instruments arrangements of cameras B64D47/08; aeronautical measuring instruments per se G01C
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

A system, a method and instructions embodied on a non-transitory computer-readable storage medium that solve a 3D point-in-polygon (PIP) problem is presented. This system projects polygons that comprise a set of polyhedra onto projected polygons in a reference plane. Next, the system projects a data point onto the reference plane, and performs a 2D PIP operation in the reference plane to determine which projected polygons the projected data point falls into. For each projected polygon the projected data point falls into, the system performs a 3D crossing number operation by counting intersections between a ray projected from the corresponding data point in a direction orthogonal to the reference plane and polyhedral faces corresponding to projected polygons, to identify polyhedra the data point falls into. The system then generates a visual representation of the set of polyhedra, wherein each polyhedron is affected by data points that fall into it.

Claims

1. A computer-implemented method for generating a visual representation of a set of polyhedra in a three-dimensional space, comprising:

projecting polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in a set of one or more data points in three-dimensional space to be processed to determine what polyhedra the data point falls into,

projecting the data point in three-dimensional space onto a projected data point in the reference plane,

performing a two-dimensional point-in-polygon (PIP) operation in the reference plane using an index of open line segments to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into,

performing a three-dimensional crossing number (CN) operation to identify zero or more polyhedra that the data point falls into;

generating a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron; and

presenting the visual representation to a user.

2. The computer-implemented method of claim 1,

wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein performing the two-dimensional point-in-polygon (PIP) operation for each projected data point in the reference plane comprises;

projecting rays in the reference plane from endpoints of projected line segments of the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index;

for each interval between pairs of consecutive intersection points on the reference line, storing in the index open line segments that project onto the interval;

identifying a relevant interval on the reference line that the projected data point projects onto; and

performing a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and the open line segments, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval to identify zero or more projected polygons that the projected data point falls into in the reference plane.

3. The computer-implemented method of claim 1, wherein

performing the three-dimensional CN operation includes counting intersections between a ray projected from the corresponding data point in a direction orthogonal to the reference plane and polyhedral faces corresponding to projected polygons, to identify the zero or more polyhedra that the data point falls into.

4. The computer-implemented method of claim 1, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

5. The computer-implemented method of claim 1, wherein the reference line is an X-coordinate axis.

6. The computer-implemented method of claim 1, wherein the reference line is a Y-coordinate axis.

7. The computer-implemented method of claim 1, wherein projecting the data point onto the projected data point in the reference plane includes setting a Z-coordinate for the data point to zero.

8. The computer-implemented method of claim 1, wherein projecting polygons in the set of polyhedra onto projected polygons in the reference plane includes setting Z-coordinates for line segments of the set of polyhedra to zero.

9. The computer-implemented method of claim 1, wherein generating the visual representation for the set of polyhedra includes one of:

generating a visual representation for a computer game that includes the set of polyhedra; and

generating a visualization for a medical-imaging system that includes the set of polyhedra.

10. The computer-implemented method of claim 1, wherein prior to processing the set of data points, the method further comprises obtaining the set of data points by:

receiving a query to be processed, wherein the query is associated with the set of polyhedral; and

using a late-binding schema generated from the query to retrieve the set of data points from a set of events containing previously gathered data.

11. The computer-implemented method of claim 1,

wherein the method operates in an aircraft navigation system;

wherein each data point represents an aircraft;

wherein each polyhedron represents an air corridor or a portion of an air corridor; and

wherein the method additionally determines when each aircraft enters or leaves an air corridor.

12. The computer-implemented method of claim 1,

wherein the method operates in a video game;

wherein each data point represents a vehicle that can be manned or unmanned;

wherein each polyhedron represents a physical object in the video game;

and

wherein the method additionally determines when each vehicle collides with or is in danger of colliding with a physical object.

13. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating a visual representation of a set of polyhedra in a three-dimensional space, the storage medium including:

instructions for projecting polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in a set of one or more data points in three-dimensional space to be processed to determine what polyhedra the data point falls into,

instructions for projecting the data point in three-dimensional space onto a projected data point in the reference plane,

performing a two-dimensional point-in-polygon (PIP) operation in the reference plane using an index of open line segments to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into, instructions for performing a three-dimensional crossing number (CN) operation to identify zero or more polyhedra that the data point falls into;

instructions for generating a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron;

and

instructions for presenting the visual representation to a user.

14. The non-transitory computer-readable storage medium of claim 13, wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein the instructions for performing the two-dimensional point-in-polygon (PIP) operation for the projected data point in the reference plane comprise;

instructions for projecting rays in the reference plane from endpoints of projected line segments of the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index;

for each interval between pairs of consecutive intersection points on the reference line, instructions for storing in the index open line segments that project onto the interval;

instructions for identifying a relevant interval on the reference line that the projected data point projects onto; and

instructions for performing a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and the open line segments, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval to identify zero or more projected polygons that the projected data point falls into in the reference plane.

15. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for performing the three-dimensional CN operation includes instructions for counting intersections between a ray projected from the corresponding data point in a direction orthogonal to the reference plane and polyhedral faces corresponding to projected polygons, to identify the zero or more polyhedra that the data point falls into.

16. The non-transitory computer-readable storage medium of claim 13, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

17. The non-transitory computer-readable storage medium of claim 13, wherein the reference line is an X-coordinate axis.

18. The non-transitory computer-readable storage medium of claim 13, wherein the reference line is a Y-coordinate axis.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for projecting the data point onto the projected data point in the reference plane include instructions for setting a Z-coordinate for the data point to zero.

20. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for projecting polygons in the set of polyhedra onto projected polygons in the reference plane include instructions for setting Z-coordinates for line segments of the set of polyhedra to zero.

21. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for generating the visual representation for the set of polyhedra include one of:

instructions for generating a visual representation for a computer game that includes the set of polyhedra; and

instructions for generating a visualization for a medical-imaging system that includes the set of polyhedra.

22. The non-transitory computer-readable storage medium of claim 13, wherein the storage medium additionally includes instructions for obtaining the set of data points prior to processing the set of data points, wherein the instructions for obtaining the set of data points includes:

instructions for receiving a query to be processed, wherein the query is associated with the set of polyhedra; and

instructions for using a late-binding schema generated from the query to retrieve the set of data points from a set of events containing previously gathered data.

23. The non-transitory computer-readable storage medium of claim 13,

wherein the instructions operate in an aircraft navigation system;

wherein each data point represents an aircraft;

wherein each polyhedron represents an air corridor or a portion of an air corridor; and

wherein the method additionally determines when each aircraft enters or leaves an air corridor.

24. The non-transitory computer-readable storage medium of claim 13, wherein the instructions operate in a video game;

wherein each data point represents a vehicle that can be manned or unmanned;

wherein each polyhedron represents a physical object in the video game; and

wherein the method additionally determines when each vehicle collides with or is in danger of colliding with a physical object.

25. A system that generates a visual representation of a set of polyhedra in a three-dimensional space, comprising:

at least one processor and at least one associated memory; and

a display mechanism that executes on the at least one processor, wherein during operation, the display mechanism;

projects polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in a set of one or more data points in three-dimensional space to be processed to determine what polyhedra the data point falls into,

projects the data point in three-dimensional-space onto a projected data point in the reference plane,

performs a two-dimensional point-in-polygon (PIP) operation in the reference plane using an index of open line segments to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into,

performs a three-dimensional crossing number (CN) operation to identify zero or more polyhedra that the data point falls into;

generates a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron; and

presents the visual representation to a user.

26. The system of claim 25,

wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and

wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein while performing the two-dimensional point-in-polygon (PIP) problem for the projected data point in the reference plane, the system;

projects rays in the reference plane from endpoints of projected line segments of the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and stores the intersection points in the index;

for each interval between pairs of consecutive intersection points on the reference line, stores in the index open line segments that project onto the interval;

identifies a relevant interval on the reference line that the projected data point projects onto; and

performs a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and the open line segments, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval to Identify zero or more projected polygons that the projected data point falls into in the reference plane.

27. The system of claim 25, wherein while performing the three-dimensional CN operation, the system counts intersections between a ray projected from the corresponding data point in a direction orthogonal to the reference plane and polyhedral faces corresponding to projected polygons, to identify the zero or more polyhedra that the data point falls into.

28. The system of claim 25, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

29. The system of claim 25, wherein the reference line is an X-coordinate axis.

30. The system of claim 25, wherein the reference line is a Y-coordinate axis.