Spatial decomposition methods using bit manipulation
AssigneeBinary Simplex, Inc.
InventorMichael Lee
Life of this patent
Estimating the term…
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, binary location code array is used to represent an image and the method for identify the neighbor shape employs a bit manipulation step in code or psuedo-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.
Claims8
A computer-implemented method for identifying a 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 being displayed or capable of being displayed on a computer or screen, and the mesh is represented by a location code array comprising a location code for each polygon of the mesh and an associated set of neighbor masks for each polygon, the method comprising:
- a) receiving identification information for a query polygon;
- b) searching the location code array and neighbor mask sets to identify a nearest common ancestor of the query polygon;
- and
- c) generating the location code for a neighbor polygon based on the nearest common ancestor identified in b), wherein the location code of the neighbor polygon can be any of the possible neighbors of the query polygon, and wherein searching the location code array and identifying the neighbor polygon comprises performing two or more logical bitwise operations on bit combinations or particular bit patterns within a location code.
A computer-implemented method of navigating a three-dimensional image in constant time to manipulate and display an image, wherein the image is capable of being displayed on a computer or screen, the method 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 of the first plurality of polygons in an array in a memory of the computer;
- identifying an edge neighbor set corresponding to the first plurality of polygons;
- generating children polygons by bisecting each of the polygons in the edge neighbor set and 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 first plurality of polygons or the children polygons to select an image to display;
- and
- displaying the image.
Dependencies are inferred from the claim text.