Generating Compressible Triangular Mesh

-- Laxmi P Gewali, C Sun

back to My Homepage
back to Research page

Abstract

To propose an algorithm based on the strip/core decomposition of polygons that yield compressible triangular mesh containing high proportion of quality triangles.

1. Introduction

• Triangular meshes are widely used to represent the surface of geometric objects.
• When meshes are fed to graphics display engines, the rendering time depends on the rate at which the triangles are transmitted to the engine.
• It is highly desirable to have a compact representation of the triangular mesh.
• Geometric compression is a way of presenting a mesh in a compact form so that multiple occurrence of vertices of a mesh is reduced.
• Triangular strip - a sequence of triangles where adjacent triangles in the sequence share an edge.
• Most geometric compression algorithms are based on the use of the properties of adjacent triangles in a mesh
• A good quality mesh should have high proportion of fat triangles
  • triangles of which the length of its sides do not differ much

2. Preliminary Work

• Complete listing
  • requires 3*k*s space. k = # of triangles, s = # of bits to encode a coordinate
  • 
  • t8 = abj, t7 = bcj...
• Triangular strip representation
  • requires (k-2)s + (k-1) bits. s = # of bits to encode a coordinate.
  • v₁v₂v₃b₁v₄b₂v₅b₃....b_k-2v_k+1b_k-1v_k+2
    • b ∈ {0, 1} used to indicate which of the previous 3 coordinates are used in conjunction with the new coordinate to construct a triangle
    • 
• Hamiltonian Mesh
  • A triangular mesh in which a hamiltonian path
    • HP: a path that visits each vertex exactly once
• Spanning tree approach
  • makes a triangular mesh hamiltonian
    1. constructs a spanning tree of the original mesh
    2. do a Euler tour of the spanning tree
       • Euler Tour == Euler Cycle
  • Drawbacks
    • the triangles at the boundary of the polygon are thin and long - not desirable
• Hierarchical approach
  • Algorithm starts on a coarse Hamiltonian triangular mesh
    • any polygon can be partitioned into four parts whose dual graph admits a hamiltonian cycle
    • dual graph
  • Elements of the coarse mesh are successively refined while maintaining its hamiltonian property
  • Only good for elements of the mesh that are close to isosceles right triangles

3. Strip/Core Decomposition

• 
• Two spiral strips. One sprialing inside-out and the other spiraling outside-in
  • The existense of a hamiltonian triangular mesh is obvious
• δ is the approximate size of the mesh element
• Formulation of the strip
  • construct (w1, w2) such that it is parallel to (v2, v3) and δ distance towards the center of the polygon
  • Follow the guiding path of v2, v3, v4, ... vn until w1 is reached. then start a new cycle by following w1, w2, w3, ... wn. Spiraling stops if the minor diameter of the core is < 3 δ.
  • the resulting structure is the strip/core decomposition of the convex polygon
• Decomposition of a convex polygon into spiral-strip and core can be implemented by performing the process of shrinking a convex chain.
• Open convex-chain is a connected proper subset of the boundary of a convex polygon
  • 
  • (figure above) completely open convex chain
  • 
  • (figure above) shrinking of a convex chain by 2 δ towards the interior

Please report all broken links and comments to jam0cam@yahoo.com

Created 3/14/06

Last Updated: 3/14/06