Spatial decomposition methods using bit manipulation

• US 20040201584A1
• Filed: 03/27/2003
• Published: 10/14/2004
• Est. Priority Date: 02/20/2003
• Status: Active Grant

• Current Assignee: Binary Simplex, Inc.
• Original Assignee: Binary Simplex, Inc.
• Inventors: Lee, Michael
• Granted Patent: US 7,777,740 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• 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

Abstract

The invention relates to image decomposition strategies and computer-based methods for implementing them. In one method of the invention, the ordering of tetrahedral shapes that define or approximate an image is performed in such a way that neighboring tetrahedral shapes can be identified, located and efficiently used. In one aspect, a binary location code array is used to represent an image and the method for identifying the neighbor shape employs a bit manipulation step in code or pseudo-code for operating a computer. In this aspect, the invention allows one to move between adjacent tetrahedra, and any data corresponding to the tetrahedra, in constant time.

Claims

1. A computer-implemented method for identifying any neighbor of a query polygon in a polygonal mesh, where the polygonal mesh approximates a three-dimensional image or part of a three-dimensional image and the mesh is represented by a location code array comprising a location code for each polygon of the mesh, the method comprising

receiving identification information for a query polygon,

searching the location code array to identify a nearest common ancestor of the query polygon and a neighbor polygon;

generating the location code for a neighbor polygon based on the location code of the nearest common ancestor, wherein the location code of the neighbor polygon can be any of the possible neighbors of the query polygon; and

displaying the image or an image manipulated by the use of the location code for the neighbor polygon.

2. The method of claim 1, wherein the polygons are right angle tetrahedra and each location code is stored in at least partial binary number format.

3. The method of claim 2, wherein the step of generating the location code for a neighbor polygon comprises inverting at least one binary digit of the location code of the query polygon based on the nearest common ancestor.

4. The method of claim 1, wherein the location code comprises a first non-binary digit and a subsequent binary number.

5. The method of claim 2, wherein the location code comprises a first non-binary digit and a subsequent binary number.

6. The method of claim 3, wherein the location code comprises a first non-binary digit and a subsequent binary number.

7. The method of claim 1, further comprising manipulating the three-dimensional image whereby the view of the image is changed when displayed.

8. A computer-readable medium with computer-executable code stored thereon, wherein the computer-executable code performs the method of claim 1.

9. A computer-readable medium with computer-executable code stored thereon, wherein the computer-executable code performs the method of claim 2.

10. A computer-readable medium with computer-executable code stored thereon, wherein the computer-executable code performs the method of claim 3.

11. A computer-readable medium with computer-executable code stored thereon, wherein the computer-executable code performs the method of claim 4.

37. A display system, comprising:

a display generator;

an application program adapted to execute from a processor that operates from an operating system;

a memory device; and

a software component containing lines of code which, during execution of the application program, performs the steps of any one of claims 1, 12, 15, 17, 22, 27, or 32, to produce an image on the display generator.

12. A computer-implemented method of navigating an array in constant time to manipulate and display an image, wherein the array represents a model of a three-dimensional image, comprising the steps:

approximating the three-dimensional image with a polygonal mesh, wherein each polygon of the mesh can be bisected into smaller polygons;

associating a binary location code with each polygon;

storing the binary location codes in an array; and

generating children polygons with new binary location codes, wherein constant time analyzing of the three-dimensional image is capable through one or more computer-implemented operations on the binary location codes; and

displaying the image.

13. The method of claim 12, wherein the polygons are right angle tetrahedra.

14. The method of claim 13, wherein a computer-implemented operation on the binary location codes comprises inverting at least one digit of the binary location code.

15. A method of generating a display of a three-dimensional image, comprising the steps:

creating an array of location codes for a background scene for the display;

creating location codes for a plurality of composite images to overlie the background scene;

identifying the location codes in the background scene where at least a portion of the background scene is overlaid by a composite image to generate relevant location codes for a selected viewpoint of the three-dimensional image; and

instructing a rendering machine to render an image from the relevant location codes based upon a selected viewpoint, whereby a three-dimensional image is displayed.

16. The method of claim 15, wherein each location code is stored in at least partial binary format.

17. A method of using a computer processor to manipulate a three dimensional image, comprising receiving data representing a three-dimensional image rendered from scan images of a patient or anatomical or cellular structure, performing a series of transformations of location code data points represented in binary form to determine the nearest neighbor data points through a location code associated with each data point, generating the manipulated image using the nearest neighbor data points, and displaying the resulting image.

18. The method of claim 17, wherein the location code is stored in at least partial binary form.

19. The method of claim 18, wherein the data representing a three-dimensional image comprises a polygonal mesh.

20. The method of claim 19, wherein right angle tetrahedra are used as polygons.

21. The method of claim 20, wherein the transformation comprises inverting a binary digit in the location code of a data point.

22. A method of using a computer processor to manipulate a three dimensional image, comprising receiving data representing a three-dimensional image rendered from VR scene for computer gaming or digital film, performing a series of transformations of location code data points represented in binary form to determine the nearest neighbor data points through a location code associated with each data point, generating the manipulated image using the nearest neighbor data points, and displaying the resulting image.

23. The method of claim 22, wherein the location code is stored in at least partial binary form.

24. The method of claim 23 wherein the data representing a three-dimensional image comprises a polygonal mesh.

25. The method of claim 24, wherein right angle tetrahedra are used as polygons.

26. The method of claim 25, wherein the transformation comprises inverting a binary digit in the location code of a data point.

27. A method of using a computer processor to manipulate a three dimensional image, comprising receiving data representing a three-dimensional image rendered from a geological, subterranean, or satellite view, performing a series of transformations of location code data points represented in binary form to determine the nearest neighbor data points through a location code associated with each data point, generating the manipulated image using the nearest neighbor data points, and displaying the resulting image.

28. The method of claim 27, wherein the location code is stored in at least partial binary form.

29. The method of claim 28, wherein the data representing a three-dimensional image comprises a polygonal mesh.

30. The method of claim 29, wherein right angle tetrahedra are used as polygons.

31. The method of claim 30, wherein the transformation comprises inverting a binary digit in the location code of a data point.

32. A method of using a computer processor to simulate a three dimensional view of a scene or image, comprising receiving data representing the three-dimensional view or image stored on a data file or computer-readable medium, performing a series of transformations of location code data points represented in binary form to determine the nearest neighbor data points through a location code associated with each data point, generating a manipulated view or image using the nearest neighbor data points, and displaying the resulting view or image.

33. The method of claim 32, wherein the location code is stored in at least partial binary form.

34. The method of claim 33, wherein the data representing a three-dimensional image comprises a polygonal mesh.

35. The method of claim 34, wherein right angle tetrahedra are used as polygons.

36. The method of claim 35, wherein the transformation comprises inverting a binary digit in the location code of a data point.

38. A computer-implemented method for identifying any neighbor of a query polygon in a polygonal mesh, where the polygonal mesh approximates a three-dimensional image or part of a three-dimensional image and the mesh is represented by a location code array comprising a location code for each polygon of the mesh, the method comprising

receiving identification information for a query polygon,

searching the location code array to identify a nearest common ancestor of the query polygon and a neighbor polygon;

and

generating the location code for a neighbor polygon based on the location code of the nearest common ancestor, wherein the location code of the neighbor polygon can be any of the possible neighbors of the query polygon.

39. The method of claim 38, wherein the step of generating the location for a neighbor polygon based on the location code of the nearest common ancestor comprises inverting the least significant bit of the location code for the query polygon.

40. The method of claim 38, wherein the step of generating the location for a neighbor polygon based on the location code of the nearest common ancestor comprises

creating a mask set that identifies a bit position wherein a sibling can be determined;

applying the mask set to the location code of the query polygon by applying the bitwise “

and”

function, thereby generating a first logical result;

generating the bitwise compliment of the first logical result;

adding 1 to the bitwise compliment of the first logical result, thereby creating a second logical result;

creating a third logical result by applying the bitwise “

and”

function to the first logical result and the second logical result;

shifting the bits of the third logical result to the left by one position; and

generating the location code of a neighbor polygon by applying the bitwise “

exclusive or”

function to the logical code of the query polygon and the shifted bits of the third logical result.

41. The method of claim 38, wherein the step of generating the location for a neighbor polygon based on the location code of the nearest common ancestor comprises

obtaining at least three masks, each of which can identify a bit position wherein a neighbor can be determined;

applying one of said at least three masks to the location code of the query polygon by applying the bitwise “

and”

function, thereby generating a first logical result;

shifting the bits of the first logical result to the left at least one position;

generating a second logical result by applying the bitwise “

exclusive or”

function to the logical code of the query polygon and the shifted bits of the first logical result;

generating the bitwise compliment of the second logical result;

creating a third logical result by applying the bitwise “

xor”

function to a neighbor mask of the query polygon and another of said at least three masks;

creating a fourth logical result by applying the bitwise “

and”

function to the bitwise compliment of the second logical result and the third logical result;

creating a fifth logical result by shifting the bits of the fourth logical result to the left by one position;

creating a sixth logical result by applying the bitwise “

or”

function to the fourth logical result and the fifth logical result;

creating a seventh logical result by applying the bitwise “

and”

function to the sixth logical result and another of said at least three masks;

generating the bitwise compliment of the seventh logical result;

adding 1 to the bitwise compliment of the seventh logical result, thereby creating an eight logical result;

creating a ninth logical result by applying the bitwise “

and”

function to the eight logical result and the seventh logical result; and

generating the location code of a neighbor polygon by applying the bitwise “

exclusive or”

function to the logical code of the query polygon and the shifted bits of the ninth logical result.

42. The method of any of claims 38-41, wherein each the polygons is a right angle tetrahedron.

43. The method of any one of claims 38-42, wherein the location code is stored in non-binary and binary form.

44. A computer-implemented method of navigating a three-dimensional image in constant time to manipulate and display an image, comprising

using a microprocessor to approximate the three-dimensional image with a first plurality of polygons, each of the polygons is the same shape and size, and each of the polygons can be bisected into smaller polygons;

associating a binary location code with each polygon in the first plurality of polygons;

storing the binary location codes in an array in a memory of the computer;

generating children polygons by bisecting each of the polygons in the first plurality of polygons, associating a binary location code with each of the children polygons;

navigating the three-dimensional image in constant time using a microprocessor to perform operations on the binary location codes of the polygons; and

displaying the image.

45. The method of claim 44, wherein each of the polygons is a right angle tetrahedron.

46. The method of claim 44 or 45, wherein the step of navigating the image comprises using a microprocessor to invert at least one bit of a binary location code of a first tetrahedron in order to identify a sibling tetrahedron, and then displaying the sibling tetrahedron.

47. The method of any one of claims 44-46, wherein the step of navigating the image comprises

determining the location code of a first tetrahedron;

creating a mask set that identifies a bit position wherein a sibling tetrahedron can be determined;

applying the mask set to the location code of the first tetrahedron by applying the bitwise “

and”

function, thereby generating a first logical result;

generating the bitwise compliment of the first logical result;

adding 1 to the bitwise compliment of the first logical result, thereby creating a second logical result;

creating a third logical result by applying the bitwise “

and”

function to the first logical result and the second logical result;

shifting the bits of the third logical result to the left by one position;

generating the location code of a neighbor tetrahedron by applying the bitwise “

exclusive or”

function to the logical code of the first tetrahedron and the shifted bits of the third logical result;

using the location code of the neighbor tetrahedron to identify a path for navigating across the three-dimensional image.

48. A method of using a computer processor to manipulate a three dimensional image, comprising

receiving data representing a three-dimensional image rendered from a image scanning process;

processing the data to generate a model of the three-dimensional image by using a plurality of polygons;

assigning a location code to each of the polygons used in the model, each of said assigned location codes comprising a binary number;

using a microprocessor to perform a series of operations on at least one location codes of a polygons used in the model to identify a neighboring polygon, and using the location code of the neighboring polygon to manipulate the three-dimensional image; and

displaying the manipulated three-dimensional image.

49. The method of claim 48, wherein the location code is stored in non-binary and binary form.

50. The method of claim 49, wherein the data representing a three-dimensional image comprises a tetrahedral mesh.

51. The method of claim 48, wherein the series of operations comprise inverting a binary digit in the location code of a polygon.

52. A computer-implemented method of generating a display of a three-dimensional image, comprising

using a microprocessor to generate a model of a background scene for the display by generating a plurality of polygons to approximate the background scene;

creating a first array of location codes for the background scene by assigning a location code for each of the polygons used in the model for the background scene;

identifying a composite image to be superimposed on the background scene;

using a microprocessor to generate a model of the composite image by generating a plurality of polygons to approximate the composite image;

creating a second array of location codes for the composite image by assigning a location code for each of the polygons used in the model for the composite image;

identifying the location codes in first array where at least a portion of the background scene is to be overlaid by the composite image; and

rendering a display comprised of the background scene and the composite image using the location codes of the two arrays.

53. The method of claim 52, further comprising selecting a viewpoint from which the display may be viewed and modifying the display to render the background scene and the composite image from the selected viewpoint.

54. The method of claim 52, wherein each location code is stored in at least partial binary format.

55. The method of any one of claims 52-54, wherein each polygon is a right angle tetrahedron.

56. The method of any one of claims 52-54, whereby the rendering step is achieved by updating clusters at a rate that exceeds 10,000 cluster updates per second.

57. The method of any one of claims 52-54, whereby the rendering step is achieved by updating clusters at a rate that exceeds 20,000 cluster updates per second.

58. The method of any one of claims 52-54, whereby the rendering step is achieved by updating clusters at a rate that exceeds 60,000 cluster updates per second.

59. The method of any one of claims 52-54, whereby the rendering step is achieved by updating clusters at a rate that exceeds 80,000 cluster updates per second.

60. A computer-implemented method of generating a display of a three-dimensional image, comprising

using a microprocessor to generate a model of a three-dimentional image;

creating a first array of location codes for the model of the three-dimensional image by associating a location code for each element in the model;

storing the location codes in an array in a memory of the computer;

performing one of more transformations of the array to generate one or more resulting arrays;

analyzing the one or more resulting arrays to search for a selected element in the model, by searching in constant time using a microprocessor to perform operations on the location codes; and

identifying one or more location codes associated with the selected element in the model.

61. The method of claim 60, further comprising rendering a display using the identified location codes of the selected element in the model.