Determining a node path through a node graph

• US 8,135,566 B2
• Filed: 06/10/2009
• Issued: 03/13/2012
• Est. Priority Date: 01/04/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Marshall, Carl S., Lake, Adam T.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Rodriguez, Carlos Ortiz
• Application Number:
  US12/482,209
• Publication Number:
  US 20090237398A1
• Time in Patent Office: 1,007 Days
• Field of Search: 345/428, 345/474, 700/1, 700/2, 700/98, 703/6
• US Class Current: 703/6
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: Y10S 345/959 Object path adherence

Abstract

Determining a node path through a node graph includes modifying the node graph in accordance with a predetermined platform performance, performing a path finding process through the node graph to obtain the node path, determining if the platform performance has changed, adjusting the node graph to compensate for a change in the platform performance, and re-performing the path finding process through the adjusted node graph to obtain the node path.

Claims

1. A method comprising:

detecting a change in performance of a platform on which an animation sequence runs, the platform comprising computer hardware;

adjusting, during the animation sequence, a three-dimensional (3D) mesh that defines a node graph for the animation sequence, the 3D mesh being adjusted to compensate for the change in performance by increasing a number of polygons in the 3D mesh if the performance of the platform increases and by decreasing the number of polygons in the 3D mesh if the performance of the platform decreases; and

performing a path finding process after the 3D mesh is adjusted to determine a path that a 3D model in the animation sequence should take through the adjusted 3D mesh, the path including a start node corresponding to a polygon of the 3D mesh and a destination node corresponding to a different polygon of the 3D mesh, the start node and the destination node comprising nodes of the node graph;

wherein when the node graph comprises data that is separate from the 3D mesh, nodes of the node graph are superimposed over the 3D mesh and contain data related to vertices of the 3D mesh;

wherein when the node graph comprises data associated with the 3D mesh, nodes of the node graph are located at centers of polygons of the 3D mesh or at vertices of the 3D mesh.

2. The method of claim 1, wherein the change in performance of the platform relates to how many frames of the animation sequence the platform can process in a time period.

3. The method of claim 1, wherein decreasing the number of polygons in the 3D mesh comprises removing vertices of polygons that are interior to the 3D mesh and connecting unconnected vertices to form polygons that are larger than polygons that existed before the vertices were removed.

4. The method of claim 1, wherein increasing the number of polygons in the 3D mesh comprises subdividing existing polygons in the 3D mesh to produce polygons that are smaller than polygons that existed prior to the subdividing.

5. The method of claim 1, wherein the path finding process comprises:

determining that a first node having a significance has been removed from the 3D mesh as a result of adjusting the 3D mesh;

assigning the significance to a second node in the 3D mesh; and

determining the path that the 3D model should take through the animation sequence using the second node in place of the first node.

6. The method of claim 5, further comprising:

selecting, as the second node, a node that is closest, in the 3D mesh, to the first node.

7. The method of claim 5, further comprising:

obtaining a position of the 3D model on the 3D mesh after adjusting the 3D mesh; and

selecting the second node based on traversal of the 3D model through the adjusted 3D mesh.

8. A method comprising:

generating an original three-dimensional (3D) mesh, the original 3D mesh representing terrain that is traversed by a 3D model in an animation sequence, the original 3D mesh comprising polygons, at least some of the polygons corresponding to nodes of a node graph, wherein when the node graph comprises data that is separate from the original 3D mesh, nodes of the node graph are superimposed over the original 3D mesh and contain data related to vertices of the original 3D mesh, wherein when the node graph comprises data associated with the original 3D mesh, nodes of the node graph are located at centers of polygons of the original 3D mesh or at vertices of the original 3D mesh;

adjusting the original 3D mesh by changing a size of the polygons;

determining that one or more nodes of significance have been removed from the original 3D mesh as a result of adjusting the original 3D mesh, the one or more nodes of significance for affecting a path of the 3D model through the original 3D mesh, the one or more nodes of significance including at least one of a start node or a destination node of the path, the start node corresponding to a polygon of the 3D mesh and the destination node corresponding to a different polygon of the 3D mesh, the start node and the destination node comprising nodes of the node graph;

assigning one or more nodes in the adjusted 3D mesh the significance of the one or more nodes in the original 3D mesh;

running the animation sequence to allow the 3D model to traverse the adjusted 3D mesh taking into account significance of the one or more nodes in the adjusted 3D mesh; and

displaying the animation sequence on a display screen.

9. The method of claim 8, wherein the one or more nodes of significance in the original 3D mesh comprise one of more of a start node from which the 3D model traverses the 3D mesh, a destination node indicating an ending point on a path of the 3D model through the 3D mesh, and a blocking node that defines a point through which the 3D model cannot pass.

10. The method of claim 8, wherein changing the size of the polygons comprises removing vertices of polygons that are interior to the original 3D mesh and connecting unconnected vertices to form polygons in the adjusted 3D mesh that are larger than polygons that existed before the vertices were removed.

11. The method of claim 8, wherein changing the size of the polygons comprises subdividing existing polygons in the original 3D mesh to produce polygons in the adjusted 3D mesh that are smaller than polygons that existed prior to the subdividing.

12. The method of claim 8, wherein the 3D mesh is adjusted while the animation sequence is being run.

13. The method of claim 8, wherein the original 3D mesh is adjusted in response to a change in performance of a hardware platform running the animation sequence in order to maintain a substantially steady frame rate in the animation sequence.

14. An article comprising a computer program product having stored therein instructions that are executable to:

detect a change in performance of a platform on which an animation sequence runs, the platform comprising computer hardware;

adjust, during the animation sequence, a three-dimensional (3D) mesh that defines a node graph for the animation sequence, the 3D mesh being adjusted to compensate for the change in performance by increasing a number of polygons in the 3D mesh if the performance of the platform increases and by decreasing the number of polygons in the 3D mesh if the performance of the platform decreases; and

perform a path finding process after the 3D mesh is adjusted to determine a path that a 3D model in the animation sequence should take through the adjusted 3D mesh, the path including a start node corresponding to a polygon of the 3D mesh and a destination node corresponding to a different polygon of the 3D mesh, the start node and the destination node comprising nodes of the node graph;

wherein when the node graph comprises data that is separate from the 3D mesh, nodes of the node graph are superimposed over the 3D mesh and contain data related to vertices of the 3D mesh;

wherein when the node graph comprises data associated with the 3D mesh, nodes of the node graph are located at centers of polygons of the 3D mesh or at vertices of the 3D mesh.

15. The article of claim 14, wherein the change in performance of the platform relates to how many frames of the animation sequence the platform can process in a time period.

16. The article of claim 14, wherein decreasing the number of polygons in the 3D mesh comprises removing vertices of polygons that are interior to the 3D mesh and connecting unconnected vertices to form polygons that are larger than polygons that existed before the vertices were removed.

17. The article of claim 14, wherein increasing the number of polygons in the 3D mesh comprises subdividing existing polygons in the 3D mesh to produce polygons that are smaller than polygons that existed prior to the subdividing.

18. The article of claim 14, wherein the path finding process comprises:

determining that a first node having a significance has been removed from the 3D mesh as a result of adjusting the 3D mesh;

assigning the significance to a second node in the 3D mesh; and

determining the path that the 3D model should take through the animation sequence using the second node in place of the first node.

19. The article of claim 18, further comprising instructions to:

select, as the second node, a node that is closest, in the 3D mesh, to the first node.

20. The article of claim 18, further comprising instructions to:

obtain a position of the 3D model on the 3D mesh after adjusting the 3D mesh; and

select the second node based on traversal of the 3D model through the adjusted 3D mesh.

21. An article comprising a computer program product having stored therein instructions that are executable to:

generate an original three-dimensional (3D) mesh, the original 3D mesh representing terrain that is traversed by a 3D model in an animation sequence, the original 3D mesh comprising polygons, at least some of the polygons corresponding to nodes of a node graph, wherein when the node graph comprises data that is separate from the original 3D mesh, nodes of the node graph are superimposed over the original 3D mesh and contain data related to vertices of the original 3D mesh, wherein when the node graph comprises data associated with the original 3D mesh, nodes of the node graph are located at centers of polygons of the original 3D mesh or at vertices of the original 3D mesh;

adjust the original 3D mesh changing a size of the polygons;

determine that one or more nodes of significance have been removed from the original 3D mesh as a result of adjusting the original 3D mesh, the one or more nodes of significance for affecting a path of the 3D model through the original 3D mesh, the one or more nodes of significance including at least one of a start node or a destination node of the path, the start node corresponding to a polygon of the 3D mesh and the destination node corresponding to a different polygon of the 3D mesh, the start node and the destination node comprising nodes of the node graph;

assign one or more nodes in the adjusted 3D mesh the significance of the one or more nodes in the original 3D mesh;

run the animation sequence to allow the 3D model to traverse the adjusted 3D mesh taking into account significance of the one or more nodes in the adjusted 3D mesh; and

display the animation sequence on a display screen.

22. The article of claim 21, wherein the one or more nodes of significance in the original 3D mesh comprise one of more of a start node from which the 3D model traverses the 3D mesh, a destination node indicating an ending point on a path of the 3D model through the 3D mesh, and a blocking node that defines a point through which the 3D model cannot pass.

23. The article of claim 21, wherein changing the size of the polygons comprises removing vertices of polygons that are interior to the original 3D mesh and connecting unconnected vertices to form polygons in the adjusted 3D mesh that are larger than polygons that existed before the vertices were removed.

24. The article of claim 21, wherein changing the size of the polygons comprises subdividing existing polygons in the original 3D mesh to produce polygons in the adjusted 3D mesh that are smaller than polygons that existed prior to the subdividing.

25. The article of claim 21, wherein the 3D mesh is adjusted while the animation sequence is being run.

26. The article of claim 21, wherein the original 3D mesh is adjusted in response to a change in performance of a hardware platform running the animation sequence in order to maintain a substantially steady frame rate in the animation sequence.