Method for creating progressive simplicial complexes

A computer-executed method for transforming a geometric model M to create an instance of a progressive simplicial complex approximation of geometric model M, wherein geometric model M comprises a tuple (K, V, D, A) where tuple member K is a simplicial complex, tuple member V is a set of vertex positions that determine the geometric realization of K, tuple member D is a set of simplex attributes, and tuple member A is a set of areas for the principal simplices of K, the method comprising the following steps:

• receiving a selection input to unify a vertex {b.sub.i } into a vertex {a.sub.i } tuple member K;
• replacing references to {b.sub.i } with references to {a.sub.i } in the simplices in tuple member K;
• deleting vertex {b.sub.i } from the set of vertex positions in tuple member V;
• propagating a set of simplex attributes in tuple member D associated with simplices for vertex {b.sub.i } into simplices associated with vertex {a.sub.i };
• and
• redistributing a set of areas in tuple member A for deleted principal simplices associated with deleted vertex {b.sub.i } to adjacent simplices in tuple member K.

A computer-executed method for transforming a geometric model M to create an instance of a progressive simplicial complex approximation of geometric model M, wherein geometric model M comprises a tuple (K, V) where tuple member K is a simplicial complex, tuple member V is a set of vertex positions that determine the geometric realization of K, the method comprising the following steps:

• receiving a selection input to unify a vertex {b.sub.i } into a vertex {a.sub.i } in tuple member K;
• replacing references to {b.sub.i } with references to {a.sub.i } in the simplices in tuple member K;
• deleting vertex {b.sub.i } from the set of vertex positions in tuple member V;
• propagating a set of simplex attributes associated with simplices for vertex {b.sub.i } into simplices associated with vertex {a.sub.i };
• and
• redistributing a set of areas for deleted principal simplices associated with deleted vertex {b.sub.i } to adjacent simplices in tuple member K.

A computer-executed method for transforming a geometric model M to create an instance of a progressive simplicial complex approximation of geometric model M, wherein geometric model M comprises a tuple (K, V, D, A) where tuple member K is a simplicial complex, tuple member V is a set of vertex positions that determine the geometric realization of K, tuple member D is a set of simplex attributes, and tuple member A is a set of areas for the principal simplices of K, the method comprising the following steps:

• receiving a selection input to split a first vertex {a.sub.i } in tuple member K;
• replacing an ancestor simplex for {a.sub.i } with a second vertex {b.sub.i } based on a split code associated with the vertex split for vertex {a.sub.i } in tuple member K;
• assigning a new vertex position in tuple member V for first vertex {a.sub.i } and second vertex {b.sub.i };
• assigning simplex attributes in tuple member D for new principal simplices with first vertex {a.sub.i } and second vertex {b.sub.i } using simplex attributes from first vertex {a.sub.i };
• and
• assigning a set of areas in tuple member A for zero-dimension principal simplices and one-dimension principal simplices for first vertex {a.sub.i } and second vertex {b.sub.i }.

A computer-executed method for transforming a geometric model M to create an instance of a progressive simplicial complex approximation of geometric model M, wherein geometric model M comprises a tuple (K, V) where tuple member K is a simplicial complex, and tuple member V is a set of vertex positions that determine the geometric realization of K, the method comprising the following steps:

• receiving a selection input to split a first vertex {a.sub.i } in tuple member K;
• replacing an ancestor simplex for {a.sub.i } with a second vertex {b.sub.i } based on a split code associated with the vertex split for vertex {a.sub.i } in tuple member K;
• and
• assigning a new vertex position in tuple member V for first vertex {a.sub.i } and second vertex {b.sub.i }.

A computer executed method to create a smooth visual transition geomorph M.sup.G (.alpha.)=(K.sup.f, V.sup.G (.alpha.), D.sup.f, A.sup.G (.alpha.)) between a coarser geometric model M.sup.c and a finer geometric model M.sup.f from a progressive simplicial complex P which approximates arbitrary geometric model M, where geometric models M.sup.c =(K.sup.c, V.sup.c, D.sup.c, A.sup.c,), M.sup.f =(K.sup.f, V.sup.f, D.sup.f, A.sup.f), and where member K is a simplicial complex, member V is a set of vertex positions that determine the geometric realization of K, member D is a set of simplex attributes, and 0.ltoreq..alpha..ltoreq.1, such that M.sup.G (0) looks like coarser geometric model M.sup.c, and M.sup.G (1) looks like finer geometric model M.sup.f, the method comprising the following steps:

• interpolating a set of vertex positions V.sup.G (.alpha.) between an original vertex position v.sup.f in a simplicial complex K.sup.f for finer model M.sup.f and an ancestor vertex position V.sup.c in a coarser simplicial complex K.sup.c for coarser model M.sup.c ;
• interpolating a first set of areas for a first set of principal simplices of dimension-zero for the finer progressive simplicial complex K.sup.f,
• interpolating a second set of areas for a second set of principal simplices of dimension-one for the finer simplicial complex K.sup.f ;
• and
• interpolating a third set of areas by finding a set difference of areas of a third set of principal simplices of dimension zero from the coarser simplicial complex K.sup.c and areas of a third set of principal simplices of dimension zero from the finer simplicial complex K.sup.f ;
• interpolating a fourth set of areas by finding a set difference of areas of a fourth set of principal simplices of dimension one from the coarser simplicial complex K.sup.c and areas of fourth a set of principal simplices of dimension one from the finer simplicial complex K.sup.f ;
• and
• using the set of transition positions, and the first, second, third and fourth sets of areas to create the smooth visual transition geomorph model M.sup.G (.alpha.) between the coarser model M.sup.c and the finer model M.sup.f for progressive simplicial complex P.

A computer executed method for iteratively choosing candidate pairs of vertices to unify in order to construct a progressive simplicial complex P from a progressive mesh representation of an arbitrary geometric model M, where geometric model M comprises a tuple (K, V, D, A), and where member K is a simplicial complex, member V is a set of vertex positions that determine the geometric realization of K, member D is a set of simplex attributes, and member A is a set of areas for the principal simplices of K, the method comprising the following steps:

• calculating transformation costs for candidate pairs of vertices from simplicial complex K;
• creating a priority queue to store the calculated transformation costs;
• performing a transformation using the first item from the priority queue;
• and
• updating the priority queue to reflect the performed transformation.

A computer-executed method for rendering a progressive simplicial complex P which approximates in a progressive mesh representation of an arbitrary geometric model M, where geometric model M comprises a tuple (K, V, D, A) where member K is a simplicial complex, member V is a set of vertex positions that determine the geometric realization of K, member D is a set of simplex attributes, and member A is a set of areas for the principal simplices of K, the method comprising the following steps:

• determining a first bounding volume for a principal simplex from simplicial complex K;
• projecting a length for the first bounding volume onto screen space for a display device to obtain a second bounding volume in screen space pixels for the display device;
• and
• determining whether the principal simplex should be rendered using the second bounding volume.

A computer-executed method for representing a progressive simplicial complex P which approximates in a progressive mesh representation of an arbitrary geometric model M, where geometric model M comprises a tuple (K, V) where member K is a simplicial complex, and member V is a set of vertex positions that determine the geometric realization of K, the method comprising the following steps:

• approximating the geometric model M as a first approximation M.sup.i from the progress mesh representation of M, where M.sup.i has i-vertices;
• determining a sequence of vertex unification transformations that simplify M.sup.i with the sequence of approximations M.sup.i-1 , M.sup.i-2, . . . down to a final approximation M.sup.f, where M.sup.f has a predetermined number of vertices;
• reversing the sequence of vertex unification transformations;
• renumbering the vertex unification transformations in the vertex split transformation sequence with a pre-determined numbering sequence;
• associating areas with principal two-simplices in the sequence of approximations M.sup.i, . . . , M.sup.f equal to a triangle area;
• and
• maintaining a sum of areas associated with principal simplices within a manifold component in the sequence of approximations M.sup.i, . . . , M.sup.f at a constant value.

A data structure in a memory of a computer system for storing a progressive simplicial complex P created for an arbitrary geometric model M, the data structure including a plurality of data structure members, the data structure comprising:

• a data structure member for storing a dimension for a simplex-s for a simplicial complex K;
• a data structure member for storing a simplex attribute identifier for the simplex-s;
• a data structure member for storing a list of children for the simplex-s;
• and
• a data structure member for storing a list of parents for the simplex-s.