Patent ID: 7777740

Claim:
A computer-implemented method for identifying a neighbor of a query tetrahedron in a tetrahedral mesh, where the tetrahedral 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 tetrahedron of the mesh and an associated set of neighbor masks for each tetrahedron, the method comprising: a) receiving identification information for a query tetrahedron; b) searching the location code array and neighbor mask sets to identify a nearest common ancestor of the query tetrahedron; and c) using a microprocessor to generate the location code for a neighbor tetrahedron based on the nearest common ancestor identified in b), wherein the location code of the neighbor tetrahedron can be any of the possible neighbors of the query tetrahedron, and wherein searching the location code array and identifying the neighbor tetrahedron comprises obtaining at least three additional masks, which together with a neighbor mask from the neighbor mask sets can be used to identify a bit position where a neighbor tetrahedron can be determined; applying one of the three additional masks to the location code of the query tetrahedron 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 tetrahedron 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 the neighbor mask of the query tetrahedron 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 tetrahedron by applying the bitwise “exclusive or” function to the logical code of the query tetrahedron and the shifted bits of the ninth logical result.