Patent ID: 8497860

Claim:
A computer-implemented method for identifying a neighbor of a query polyhedron in a polyhedral 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 stored in a computer comprising a location code for each polyhedron of the mesh and an associated set of neighbor masks for each polyhedron, the method comprising: a) receiving identification information for a query polyhedron; b) searching the location code array and neighbor mask sets to identify a nearest common ancestor of the query polyhedron; (c) obtaining at least three additional masks, which together with the neighbor mask can be used to identify a bit position where a neighbor polygon can be determined; applying one of the three additional 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 (d) generating the location code for a neighbor polyhedron based on the nearest common ancestor identified in b), wherein the location code of the neighbor polyhedron can be any of the possible neighbors of the query polyhedron, and wherein searching the location code array and identifying the neighbor polyhedron comprises performing two or more logical bitwise operations on bit combinations or particular bit patterns within a location code.