Defining a neighborhood of vertices in a 3D surface mesh

A computer program, stored on a tangible storage medium, the program comprising executable instructions that cause a computer to:

• identify first and second base triangles in an initial model of a 3D surface;
• identifying each edge of the first and second base triangles as a right edge, a left edge, or a base edge;
• subdivide the first and second base triangles into a plurality of subdivision triangles;
• assign identifying labels to the plurality of subdivision triangles to indicate their positions in the first and second base triangles;
• assign one or more edge labels to each of the plurality of subdivision triangles having one or more edges along a corresponding edge of the corresponding base triangle, the edge label indicating that the corresponding edge of the corresponding base triangle is the right edge, the left edge, or the base edge;
• and thereafter further subdivide the digital model by:
• applying a test to a first identifying label of a first subdivision triangle of the first base triangle to derive a second identifying label of a second subdivision triangle of the second base triangle sharing a common edge with the first subdivision triangle, the test including selecting a bit replacement scheme based on an edge label of the first subdivision triangle and an edge label of the second subdivision triangle;
• using the first and second identifying labels to retrieve information about the first and second subdivision triangles;
• and
• using the information to subdivide the first subdivision triangle into smaller triangles.

A computer system comprising:

• a processor and a memory device coupled by a system bus;
• a display device operable to display rendered images;
• a graphics controller configured to receive data from the system bus and use the data in rendering images on the display device;
• and
• a 3D graphics program loaded into the memory device to assist the processor in delivering the data to the graphics controller, the 3D graphics program comprising executable instructions that cause the processor to:
• identify first and second base triangles in an initial model of a 3D surface;
• identifying each edge of the first and second base triangles as a right edge, a left edge, or a base edge;
• subdivide the first and second base triangles into a plurality of subdivision triangles;
• assign identifying labels to the plurality of subdivision triangles to indicate their positions in the first and second base triangles;
• assign one or more edge labels to each of the plurality of subdivision triangles having one or more edges along a corresponding edge of the corresponding base triangle, the edge label indicating that the corresponding edge of the corresponding base triangle is the right edge, the left edge, or the base edge;
• and thereafter further subdivide the digital model by:
• applying a test to a first identifying label of a first subdivision triangle of the first base triangle to derive a second identifying label of a second subdivision triangle of the second base triangle sharing a common edge with the first subdivision triangle, the test including selecting a bit replacement scheme based on an edge label of the first subdivision triangle and an edge label of the second subdivision triangle;
• using the first and second identifying labels to retrieve information about the first and second subdivision triangles;
• and
• using the information to subdivide the first subdivision triangle into smaller triangles.

A method, comprising:

• assigning a position label to a subdivision triangle of a base triangle, the position label indicating the position of the subdivision triangle in the base triangle, wherein the base triangle has a left edge, a right edge, and a base edge;
• assigning an edge label to the subdivision triangle, the edge label identifying an edge of the base triangle along which an edge of the subdivision triangles lies;
• determining a position label of another subdivision triangle, the another subdivision triangle included in another base triangle having a left edge, a right edge, and a base edge, the another subdivision triangle sharing a shared edge with the subdivision triangle, wherein determining the position label of the another subdivision triangle comprises:
• determining an edge label of the another subdivision triangle, wherein the edge label indicates whether the shared edge lies along the left edge, the right edge, or the base edge of the another base triangle;
• determining a bit replacement scheme based on the edge label of the subdivision triangle and the edge label of the another subdivision triangle;
• and
• modifying the position label of the subdivision triangle according to the bit replacement scheme in order to derive the position label of the another subdivision triangle.