Spatial decomposition methods using bit manipulation

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.

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.

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.

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.

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.

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.

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.