Last update: Aug. 30, 1998

Publications on 3D Databases issues by Jarek (Jack) Rossignac's group at Georgia Tech. GVU Lab. and collaborators :

• Interactive Exploration of Distributed 3D Databases over the Internet, 1998.
• Geometric Compression through Topological Surgery, 1998.
• Geometry Coding and VRML, 1998.

BibTeX references.

Interactive 3D visualization & Internet based access to the information will, in combination be the primary vehicle for accessing remote DB. 3D Simplification and Compression of the models is required. A 3D server architecture is proposed to support multi-user access to a distributed DB of complex 3D models.

• Standard 3D representations based on triangular meshes (or polyhedra), photometric information (vertex normal, color & texture coordinates) and adjacency relations, prove inadequate.
• Progressive download is possible through a multi-resolution geometric representation together with some IBR-based technique for small, distant parts of the scenery (image "impostors").

Factors influencing the total response time:

1. Sampling rate of the input device.
2. Processing necessary to compute the new scene parameters.
3. Transfer of these scene parameters to the server.
4. Extraction & compression by the server of the incremental information needed by the client to produce the new image.
5. Transfer of the new information over the network or phone line.
6. Decoding by the client of the received information.
7. Updating of the client's representation of the scene.
8. Traversal by the client of the updated information.
9. Generation of the appropriate graphic instructions for the rendering subsystem.
10. Implementation of geometric transformations, lighting calculations, clipping and scan-conversions,

The Total Response Time is thus constrained by:

1. Bandwith of the connection.
2. Performance of the graphic subsystem.
3. Allocated server power.
4. Processing power and memory of the client.
5. Image accuracy imposed by the application or the current situation.

Graphic Tolerences :

Observations:

1. The user does NOT have the capability to recognize absolute colors with precision.
2. Human ability to derive shape from shading and highlights is limited to general curvature signs and magnitudes; changing these slightly will rarely confuse the user as to the nature of the objects being displayed.
3. The fidelity of rendering systems commonly used in 3D graphics applications varies with view changes and may itslef create visual artifacts

Proposition:

• Measure the tolerance as the Hausdorff distance between the original and simplified models bioth transformed by the 3D perspective map that correspond to the current view.

3D Simplification

Error Metric:

• H(O,S) = Max{ d(o, S) , d(s, O) },

for all points o in O and s in S, where O is the original triangulated surface and S is a 3D impostor (a simplification of O) with many less triangles than O. The distance function d is taken as the Hausdorff distance, i.e., the radius of the maximal ball centered on one surface (O or S) and disjoint from the other.

Essential features of current simplification techniques :

1. Identification of vertex clusters.
2. Coalescing of each cluster into one attractor vertex.
3. Computation of the position of these attractors.
4. Removal of triangles having more than one vertex in the same cluster, unless this alters the connectivity/topology.

Hierarchical Multi-Resolution Models

• View-independent discrete Level of Detail (LoD) of the features of a model:
  • Used in most commercial implementations.
  • Subdivide the model into isolated objects and precompute a series od static approximations for each object.
  • Works well for complex scenes composed of relatively small objects.
  • Not effective for relatively large and complex objects.
• Extracting simplifications from a global adaptive multi-resolution model
  • Assumption: tolerance varies slowly between frames.
  • Pre-compute a cluster-merging-tree, which will be used to accelerate the derivation of a new simplification from the previous one, when necessary.
  • To each node of the tree is associated an estimator of the error resulting form the simplification. If the error associated with a previously merged cluster exceeds the current tolerance, the cluster is broken back into sub-clusters, represented by the children of the node in question.

It is recommended to use:

1. LoD for components that are either relatively small or geometrically simple;
2. adaptive multi-resolution models only for the large, complex objects.

3D Compression

Triangles Strips

• A triangle is formed by combining a new vertex description with the descriptions of the 2 previously sent vertices.
• This process reduces the number of times the same vertex is processed by the graphic subsystem from an average of 6 to 2.4 . Supported by OpenGL.

Generalized Strips

• Based on Deering's generalized triangle mesh syntax.
• Requires a good traversal of general meshes.
• Vertex locations are compressed by generating predictors, quantizing the corrective vectors and using entropy coding. The predictor of each vertex is taken as the displacement from the origin of the local coordinate system.

Topological Surgery

• Builds a "cut" - a vertex spanning tree of the original mesh - using a spiraling strategy, which produces in general a tree with relatively few bifurcations (i.e., nodes with more than one child).
  • The cut is the boundary of a network of corridors connected by bifurcation triangles which have zero edges in the cut.
• The structure of the cut and of the corridors' network is efficiently encoded as a sparse tree by storing the numbers of consecutive single-child nodes.
• Achieves a result of fewer than 2 bits per triangle for the entire triangle/vertex incidence graph, for well-behaved meshes.
• Vertex locations are encoded like Deering's, but the predictor for each vertex is taken to be a linear combination of its 4 ancestors in the cut tree.

Progressive Transmission

• Based on Hoppe's Progressive Meshes which permits a transfer of a 3D mesh strating from a coarse mesh and inserting new vertices one by one.
• A vertex insertion identifies a vertex V and 2 of its incident edges. It splits the mesh at these edges and fills the hole with 2 triangles. V is thus split in 2 new vertices.
• Adaptive resolution can be supported by preforming edge collapses and their iinverse.

Note: An good survey is provided of the most recent techniques for 3D compression and simplification up until and including 1997.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu