California Institute of Technology

Lucent Technologies Inc.

Peter Schroeder

Wim Sweldens

Nathan Jacob Litke

Adi Levin

Andrei Khodakovsky

Alan H Barr

Igor V Guskov

Michael Ortiz

Mathieu Desbrun

Mark Meyer

Fehmi Cirak

Steven Schkolne

Emil C Praun

Surface drawing is described as a medium which provides direct control over the creation of a wide range of intricate shapes. Surfaces are created by moving a hand, instrumented with a special glove, through space in a semi-immersive 3D display and interaction environment. Intricate forms can be created using intuitive motions. The design space can be freely explored during the modeling process without the need to plan the construction of the final shape. In particular it supports unconstrained erasing and buildup of new geometry. An incremental Cookie Cutter algorithm, a construction method for triangulated meshes is described which allows the user to freely grow, join, and erase surfaces based on hand motions.

Three dimensional surface drawing controlled by hand motion

A special set of normal meshes is defined where errors and residuals will also be along a direction that minimizes the error in coding. These normal meshes can be used to model a three dimensional surface.

Use of normal meshes in three-dimensional imaging

Methods of connectivity encoding polygonal mesh representations of objects are described, along with methods of decoding encoded connectivity information for polygonal mesh representations of objects. In the encoding process, an active vertex queue is initialized with one or more vertices incident to a seed face. A vertex is selected from the queue, and the ring of the vertex traversed. If an unprocessed face is encountered during the traversal, the degree of the face, and the valences of any unprocessed vertices incident to the face are output. Any such unprocessed vertices are also entered into the queue. The method iterates until no more vertices remain on the active queue. In one implementation, an encoded data stream is output, which comprises two logical streams, one for face-degree information and the other for vertex-valence information. In the decoding process, the encoded data stream is received, and the connectivity of the mesh regenerated.

Connectivity encoding and decoding of polygon meshes

A method of subdividing a representation of an object surface comprising a tessellated mesh of polygons is provided. The surface may be bounded by one or more boundary curves. One or more polygons in the mesh may be each subdivided into child polygons, each having one or more vertices. The result is a second mesh representation which may have a finer level of resolution than the original mesh. The locations or parameters of the vertices of the child polygons in the second mesh may be determined using suitable weightings of the locations or parameters of adjacent vertices in the original mesh. The locations of the vertices in the second mesh may be further refined through application of detail vectors. The locations of boundary vertices are always constrained to lie on one of the boundary curves bounding the surface in question. The method may continue iterating until the surface as represented by the subdivided surface representation is fine enough for the intended application.

Object surface representation and related methods and systems

A new progressive compression scheme for arbitrary topology, highly detailed and densely sampled meshes arising from geometry scanning. Meshes may have three distinct components: geometry, parameter, and connectivity information. The latter two do not contribute to the reduction of error in a compression setting. Using semi-regular meshes, parameter and connectivity information can be virtually eliminated. The semiregular meshes may be used with semi-regular wavelet transforms, zerotree coding, and subdivision based reconstruction.

Compression of 3D surfaces using progressive geometry

A method of trimming a mesh representation of an object surface comprising a tessellated mesh of polygons. A trim curve is projected onto the mesh representation to determine the trim area. Polygons within or intersecting the trim area are removed, and new polygons are introduced to attach the trimmed mesh to the trim curve projection. Detail data is formed for vertices of polygons near the trim curve, representing information about the object surface not present in the trimmed mesh representation. The detail data is applied to the vertices, thereby refining their locations. Any polygons near the trim curve which are outside a prescribed tolerance of the object surface are subdivided. The steps of forming and applying the detail data followed by the step of subdividing are iteratively performed until the trimmed mesh representation is within a prescribed tolerance of the object surface.

Method of trimming a representation of an object surface comprising a mesh of tessellated polygons and related system

Thin-shell finite-element analysis based on the use of subdivision surfaces: (1) describing the geometry of a shell in its undeformed configuration, and (2) generating smooth interpolated displacement fields possessing bounded energy. No nodal rotations are used in the interpolation. The interpolation scheme induced by subdivision is nonlocal, i.e., the displacement field over one element depends on the nodal displacements of the element nodes and all nodes of immediately neighboring elements. However, the use of subdivision surfaces ensures that all local displacement fields thus constructed combine conformingly to define one single limit surface.

Method and system for thin-shell finite-element analysis

Techniques are disclosed for generating consistent parameterizations for a set of meshes each of which includes data points representative of a corresponding surface. The consistent parameterizations preferably share the same base domain, and are generated using a net tracing algorithm. The net tracing algorithm involves determining for each of the meshes a net of paths having a connectivity substantially the same as that of the base domain. In an illustrative embodiment, the net tracing algorithm as applied to a given one of the meshes includes determining, for each edge in the base domain, a tentative path for use in the net of paths corresponding to the mesh. The tentative paths are then prioritized based on length, and selected ones of the tentative paths are used to construct a spanning tree of the base domain. One or more swirl detection operations are preferably performed as part of the spanning tree construction, with the results of the swirl detection operations being utilized in selecting particular ones of the tentative paths for use in the spanning tree. The net of paths is completed by adding one or more additional paths to the spanning tree, followed by applying a straightening operation to one or more of the paths in the net. The consistent parameterizations can be utilized to generate same-connectivity remeshes of the original meshes, which considerably facilitates subsequent digital geometry processing (DGP) operations.

Method and apparatus for generation of consistent parameterizations for a set of meshes

A method of forming detail data corresponding to a vertex of a polygonal mesh representation of an object surface. The mesh representation has a limit surface, and the vertex has a limit point on the limit surface. The detail data for the vertex relates to the shape of the limit surface near the limit point corresponding to the vertex, and may capture detail about the object surface which is not captured by the mesh representation. The method may involve forming difference or detail data for one or more vertices from the group comprising the vertex in question and one or more neighboring vertices, weighting the resulting difference or detail data with prescribed weights, and deriving the detail data for the vertex in question from the weighted difference or detail data. The difference data for a vertex is the difference between the vertex as mapped onto the object surface and the limit point for the vertex on the limit surface.

Detail data pertaining to the shape of an object surface and related methods and systems

A method of updating in real-time the locations and velocities of mass points of a two- or three-dimensional object represented by a mass-spring system. A modified implicit Euler integration scheme is employed to determine the updated locations and velocities. In an optional post-integration step, the updated locations are corrected to preserve angular momentum. A processor readable medium and a network server each tangibly embodying the method are also provided. A system comprising a processor in combination with the medium, and a system comprising the server in combination with a client for accessing the server over a computer network, are also provided.

Growing community of inventors

Pasadena, CA, United States of America

Peter Schroeder