International Business Machines Corporation

Claudio T Silva

Gabriel Taubin

James Thomas Klosowski

Andre Pierre Gueziec

Frank J Bossen

Fausto Bernardini

Holly Edith Rushmeier

Joshua D Mittleman

Joseph Shannon Baird Mitchell

Peter Lawrence Williams

Joao Luiz Dihl Comba

A method and apparatus are disclosed for finding a triangle mesh that interpolates a set of points obtained from a scanning system. A ball-pivoting algorithm computes a triangle mesh interpolating a given point cloud. The disclosed ball-pivoting algorithm triangulates a set of points by 'rolling' a ball of radius r on the point cloud. The points are surface samples acquired with multiple range scans of an object. The ball-pivoting algorithm starts with a seed triangle, and pivots the ball of a given radius, r, around an edge of the triangle. During the pivoting operation, the ball revolves around the edge while keeping in contact with the edge's endpoints. The ball pivots until it touches another scan point, forming another triangle. The ball-pivoting operation continues until all reachable edges have been tried, and then starts from another seed triangle, until all scan points have been considered.

Method and apparatus for reconstructing a surface using a ball-pivoting algorithm

A technique and system for selecting level-of-detail representations of geometric models to be rendered within an image processing system. For each geometric model, fractional visibility estimations are computed, thereby ranking how likely it is that a model is visible. Using these rankings, an appropriate level-of-detail for each geometric model is selected to optimize the rendering process by reducing the number of primitives that need to be rendered, while preserving the quality of the final image produced and displayed upon the screen. Visibility estimates for the geometric models are summed to produce a number which is then used to scale the number of primitives used in the level-of-detail representation of the geometric models.

System and process for level of detail selection based on approximate visibility estimation

A method for encoding a non-manifold polygonal mesh operates by converting an original (non-manifold) model to a manifold model, encoding the manifold model using a mesh compression technique, and clustering, or stitching together during a decompression process, vertices that were duplicated earlier to faithfully recover the original connectivity. By separating the connectivity from model geometry and properties, the method avoids encoding vertices (and properties bound to vertices) multiple times. This provides a reduction in the size of the bit-stream compared with encoding the model as a manifold.

Methods and apparatus for the efficient compression of non-manifold polygonal meshes

A data structure for representing a general n-dimensional polygonal mesh. The data structure includes a structure record and a data record for each three dimensional shape. The structural record contains polygonal model connectivity information and further includes a stitching record that defines corresponding polygonal (triangular) mesh edge pairs and a polygonal (triangular) tree record representing a polygon (triangle) tree. The stitching record includes a vertex tree and a set of jump edges. The data record includes at least three polygonal records, each corresponding to a polygon. Each polygonal record is associated with a face of said polygonal model and classifies its corresponding polygon as either a leaf polygon, a running polygon or a branching polygon. Polygonal shapes are encoded into the data structure by first building a spanning tree for the polygonal mesh. A set of cut edges are derived for the polygonal mesh. The stitching record is constructed for the set of cut edges. Then traversing the polygon tree, the data records are encoded. The encoded data is transmitted, the structure record being transmitted first, followed by the data record. The stitching tree and polygon tree are decoded as they are received and, after at least three polygons are received, received polygons may be displayed.

Compression of polygonal models with low latency decompression

A Prioritized-Layered Projection (PLP) method and system for optimizing the rendering high-depth complexity scenes. Objects in each frame are prioritized with an estimation of the visible set within the rendered frame. A priority order for only the primitives in visible sets within the frame are computed &ldquo;on demand&rdquo; to maximize the likelihood of rendering visible primitives before rendering occluded ones. For a fixed budget, such as, time or number of triangles, rendering is constrained to a geometry budgeted priority. The method includes two main steps: an occupancy-based tessellation of space; and a solidity-based traversal algorithm. By first computing an occupancy-based tessellation of space, more cells result where there are more geometric primitives. In this spatial tessellation, each cell is assigned a &ldquo;solidity&rdquo; value directly proportional to its likelihood of occluding other cells. In its simplest form, a cell's solidity value is directly proportional to the number of primitives contained within the cell. Cells are marked for projection, and the geometric primitives contained within the marked cells are rendered. Cell solidity, and other view-dependent information determines the order cells are rendered.

System, program product and method of rendering a three dimensional image on a display

The visibility ordering of polyhedral cells is efficiently determined by building an ordering graph, comprising oriented edges between two cells. Each edge (A,B) corresponds to the fact that cell A has to be projected, or rendered, before B. A set of ordering relations and rules that can be shown to generate, if one exists, a global ordering of the polyhedral cell complex. Three different types of edges are used to accomplish this: MPVO, BSP and PPC edges. MPVO edges exist between two cells that share a face. To define the BSP edges, a BSP-tree of the boundary faces of the cell complex is constructed. During this construction, some of the boundary faces of the cells will be 'cut' by the BSP-tree 'extended' faces, into multiple pieces. If C is the boundary cell, and c&prime;, c&Prime;, and so on, are the pieces of its boundary faces, the BSP_edge (c&prime;, C) is defined to mean that cell C can only be projected after c&prime; has been projected by the BSP. A cell C is in the PPC if one of the pieces that compose it, say c&prime;, has been projected by the BSP, but there exist other pieces of cell C that have not been projected. In this case, additional checks are done to ensure cells are not being projected out of order. This is accomplished by performing &lsquo;ray shooting&rsquo;.

Growing community of inventors

Mahwah, NJ, United States of America

Claudio T Silva