Method for generating and applying changes in the level of detail of a polygonal surface

A computer implemented method for automatically generating a computer representation of an increase in a level of detail of a polygonal surface, comprising the steps of:

• simplifying the polygonal surface;
• computing a low level of detail (LOD) polygonal surface;
• computing edge marks and vertex displacements relative to the low LOD polygonal surface;
• and
• determining a triangle forest to be added and stitched to the low LOD polygonal surface to form a higher LOD polygonal surface,
• wherein the step of simplifying said polygonal surface comprises steps of:
• creating a priority queue of surface edges, and
• for each edge in the priority queue, extracting an edge from the queue, testing the collapsibility of the extracted edge, and collapsing the extracted edge if the edge is determined to be collapsible, wherein
• the step of testing the collapsibility of the extracted edge is comprised of the steps of:
• applying at least one primary collapsibility test to an edge extracted from the queue;
• if the edge passes the at least one primary collapsibility test, applying further tests for determining whether an incremental surface comprised of a set of collapsed triangles is a triangle forest, and for determining whether the set of collapsed triangles and a set of remaining triangles are manifolds;
• and applying at least one secondary collapsibility test to the edge extracted from the queue.

A computer implemented method for cutting through a representation of a polygonal surface, the polygonal surface being representative of an actual structure, comprising steps of:

• providing data in a memory of a computer for representing the polygonal surface defined by triangles comprises edges, wherein each edge is defined by two vertices, wherein each vertex is specified by a tuple of vertex coordinates, each triangle is specified by a triple of vertex indices, each edge is specified as a pair of vertex indices of a triangle, each corner is a pair formed with a triangle and a vertex index of that triangle, each vertex having a vertex ID, each triangle having a triangle ID, and each corner having a corner ID;
• determining a set of vertices to be processed;
• forming corner groups from the corners associated with each vertex of the set of vertices;
• choosing a representative of a corner group as the corner of lowest ID;
• for each vertex of the set for which the associated number of corner groups is larger than one, replacing the corner group of lowest ID with the vertex;
• and
• for each vertex, and for each additional corner group, replacing the corner group with a new vertex, such that new vertex IDs are attributed consecutively to corner groups in order of increasing corner group representative ID.