×

Progressive compression of clustered multi-resolution polygonal models

  • US 6,009,435 A
  • Filed: 11/21/1997
  • Issued: 12/28/1999
  • Est. Priority Date: 11/21/1997
  • Status: Expired due to Term
First Claim
Patent Images

1. A system for compressing a clustered multi-resolution polygonal model comprising:

  • a memory containing a polygonal model with two or more levels of detail with progressively more resolution, each level of detail having a plurality of vertices forming a plurality of triangles, each level of detail having a geometric information about the position of the vertices in space and each level of detail having a connectivity information about the association between each triangle and the vertices that form the triangle, the memory further having a clustering information for each level of detail about how a plurality of sets of vertices in each level of detail are clustered and how each of the respective clusters correspond to a vertex in a level of detail with a next lower resolution;

    a central processing unit (CPU);

    a connectivity process, executed by the CPU, that identifies the connectivity information of a highest resolution level of detail;

    a clustering process, executed by the CPU, that orders the clustering information for each level of detail, from the level of detail with the highest resolution to the level of detail with the lowest resolution, where the clustering information is compressed by a clustering compression process having the following steps;

    first, determining a connectivity preserving partition of the vertices of the level of detail into one or more connected clusters, with two vertices joined by an edge of the level of detail belonging to the same connected cluster if the clustering information determines that the two vertices are clustered into the same set, andsecond, determining an anti-connectivity partition of the connected clusters into one or more sets of connected clusters, with two connected clusters belonging to the same set of connected clusters if the clustering information determines that the vertices that belong to the two connected clusters are clustered into the same set; and

    a geometry process, executed by the CPU, that orders the geometric information of each level of detail from the level of detail with lowest resolution to the level of detail with highest resolution.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×