An Implementation of the Marching Cubes Algorithm  1.0
mc::SurfBuilder Class Reference

This class implements an improved version of the orginal Marching Cubes algorithm. The algorithm prevents the generation of polygonal surfaces with holes. However, it does not guarantee that the polygonal surface has the same topology as the implicit surface defined by the function that affinely interpolates the values of the unknown function in the grid cubes of the spatial decomposition. More...

#include <surfbuilder.hpp>

Collaboration diagram for mc::SurfBuilder:

List of all members.

Public Types

enum  FACES {
  L, R, B, T,
  N, F
}
 Defines an index for each face of a grid cube.
enum  EDGES {
  LB, LT, LN, LF,
  RB, RT, RN, RF,
  BN, BF, TN, TF
}
 Defines an index for each edge of a grid cube.
enum  VERTS {
  LBN, LBF, LTN, LTF,
  RBN, RBF, RTN, RTF
}
 Defines an index for each vertex of a grid cube.
typedef std::list< unsigned > TRAVERSAL
 Defines a type for a list containing the indices of the edges of a cube that are intersected by the (unknown) implicit function.
typedef std::list< TRAVERSALTABLEENTRY
 Defines a type for a list of traversals, such that each traversal is itself a list of the edges of a cube that are intersected by the (unknown) implicit function.
typedef std::vector< TABLEENTRYLOOKUPTABLE
 Defines a table for storing all traversals related to each one of 256 possible ways of assigning positive and negative values to an ordered sequence of vertices of a grid cube.

Public Member Functions

 SurfBuilder (Grid *g)
 Creates an instance of this class.
 ~SurfBuilder ()
 Destroys an instance of this class.
void run ()
 Creates the simplicial surface (i.e., a triangle mesh) that approximates the surface defined by the unknown implicit function.

Private Member Functions

void make_lookup_table ()
 Builds a table with 256 entries. Each entry is related to a possible (distinct) way of assigning one of two values to the vertices of a cube. Each entry also stores a set of traversals, each of which contains the set of cube edges intersected by the surface defined by the unknown implicit function.
bool compute_sign (unsigned n, unsigned i) const
 Returns true if and only if the i-th bit of a given number is 1.
VERTS get_1st_vertex (EDGES e) const
 Returns the index of the first vertex of a given edge.
VERTS get_2nd_vertex (EDGES e) const
 Returns the index of the second vertex of a given edge.
FACES left_face (EDGES e) const
 Returns the index of the left face of a given edge, considering the edge from the vertex with positive sign to the vertex with negative sign.
FACES right_face (EDGES e) const
 Returns the index of the right face of a given edge, considering the edge from the vertex with positive sign to the vertex with negative sign.
EDGES next_cw_edge (EDGES e, FACES f) const
 Returns the index of the edge that follows a given edge in a clockwise traversal of the edges of a given face of the grid cube.
FACES change_face (EDGES e, FACES f) const
 Returns the index of a face incident to an edge.
unsigned from_index_to_id (unsigned i, unsigned j, unsigned k) const
 Returns the unique identifier of a grid cube vertex corresponding to a given triple ( i , j , k) that uniquely identifies the vertex in the grid.
void compute_intersection (unsigned i, unsigned j, unsigned k, VERTS v1, VERTS v2, double f1, double f2, t3DVector &pt) const throw ( ExceptionObject )
 Computes the coordinates of the intersection point between a given edge and the surface defined by the (unknown) implicit function.

Private Attributes

Grid_grid
 A 3D grid with function values associated with the grid vertices.
LOOKUPTABLE _cubetable
 A table that stores the traversals of the grid cubes.

Detailed Description

This class implements an improved version of the orginal Marching Cubes algorithm. The algorithm prevents the generation of polygonal surfaces with holes. However, it does not guarantee that the polygonal surface has the same topology as the implicit surface defined by the function that affinely interpolates the values of the unknown function in the grid cubes of the spatial decomposition.

Definition at line 71 of file surfbuilder.hpp.


Constructor & Destructor Documentation

Creates an instance of this class.

Parameters:
gA pointer to a 3D grid with the vertices of all cubes of a spatial decomposition along with the values of the unknown implicit function at the vertices.

Definition at line 153 of file surfbuilder.hpp.

References _cubetable.

                           : _grid( g )
    {
      _cubetable.resize( 256 ) ;
    }

Member Function Documentation

FACES mc::SurfBuilder::change_face ( EDGES  e,
FACES  f 
) const [inline, private]

Returns the index of a face incident to an edge.

Parameters:
eThe index of an edge of a grid cube.
fThe index of a grid cube face incident to the given edge, which is not equal to the other face that this method should return.
Returns:
The index of a face incident to an edge.

Definition at line 302 of file surfbuilder.hpp.

References left_face(), and right_face().

Referenced by make_lookup_table().

    {
      FACES index = left_face( e ) ;

      return ( f == index ) ? right_face( e ) : index ;
    }
void mc::SurfBuilder::compute_intersection ( unsigned  i,
unsigned  j,
unsigned  k,
VERTS  v1,
VERTS  v2,
double  f1,
double  f2,
t3DVector pt 
) const throw ( ExceptionObject ) [private]

Computes the coordinates of the intersection point between a given edge and the surface defined by the (unknown) implicit function.

Parameters:
iFirst element of a triple that identifies the origin vertex of the grid cube containing the edge.
jSecond element of a triple that identifies the origin vertex of the grid cube containing the edge.
kThird element of a triple that identifies the origin vertex of the grid cube containing the edge.
v1The index of the first vertex of the edge with respect to the grid cube.
v2The index of the second vertex of the edge with respect to the grid cube.
f1The value of the unknown implicit function at the first vertex of the edge.
f2The value of the unknown implicit function at the second vertex of the edge.
ptA reference to the intersection point.

Definition at line 629 of file surfbuilder.cpp.

Referenced by run().

  {
    if ( SIGN( f1 ) == SIGN( f2 ) ) {
      std::stringstream ss ( std::stringstream::in | 
                             std::stringstream::out ) ;
      ss << "Trying to compute intersection point on non-interesecting edge" ;
      throw ExceptionObject( __FILE__ , __LINE__ , ss.str() ) ;
    }

    unsigned i1 , j1 , k1 , i2 , j2 , k2 ;

    /*
     * Initialize indices of "v1" and "v2".
     */
    i1 = i2 = i ;
    j1 = j2 = j ;
    k1 = k2 = k ;

    /*
     * Compute the indices of "v1" and "v2" with respect to the grid.
     */
    if ( ( v1 == RBN ) || ( v1 == RBF ) || ( v1 == RTN ) || ( v1 == RTF ) ) {
      i1 += 1 ;
    }

    if ( ( v1 == LTN ) || ( v1 == LTF ) || ( v1 == RTN ) || ( v1 == RTF ) ) {
      j1 += 1 ;
    }

    if ( ( v1 == LBF ) || ( v1 == LTF ) || ( v1 == RBF ) || ( v1 == RTF ) ) {
      k1 += 1 ;
    }

    if ( ( v2 == RBN ) || ( v2 == RBF ) || ( v2 == RTN ) || ( v2 == RTF ) ) {
      i2 += 1 ;
    }

    if ( ( v2 == LTN ) || ( v2 == LTF ) || ( v2 == RTN ) || ( v2 == RTF ) ) {
      j2 += 1 ;
    }

    if ( ( v2 == LBF ) || ( v2 == LTF ) || ( v2 == RBF ) || ( v2 == RTF ) ) {
      k2 += 1 ;
    }

    /*
     * DO SOMETHING TO AVOID COMPUTING THE SAME VERTEX TWICE!
     */

    /*
     * Obtain the coordinates of vertices "v1" and "v2".
     */
    t3DVector go = _grid->get_origin() ;

    double spacx = _grid->get_spacing_x() ;
    double spacy = _grid->get_spacing_y() ;
    double spacz = _grid->get_spacing_z() ;
 
    t3DVector p1 = go + t3DVector( spacx * i1 , spacy * j1 , spacz * k1 ) ;
    t3DVector p2 = go + t3DVector( spacx * i2 , spacy * j2 , spacz * k2 ) ;

    /*
     * Compute position  of intersection  point bewteen the  cube edge
     * and the surface defined  by the unknown implicit function using
     * affine interpolation.
     */
    const double coeff = f2 / ( f2 - f1 ) ;
    pt = ( coeff * p1 ) + ( ( 1 - coeff ) * p2 ) ;

    // DO SOMETHING WITH THE INTERSECTION POINT

    return ;
  }
bool mc::SurfBuilder::compute_sign ( unsigned  n,
unsigned  i 
) const [inline, private]

Returns true if and only if the i-th bit of a given number is 1.

Parameters:
nA given number.
iAnother given number representing the position of bit.
Returns:
The logic value true if the i-th bit of a given number is 1. Otherwise, returns the logic value false.

Definition at line 210 of file surfbuilder.hpp.

Referenced by make_lookup_table().

    {
      return  ( ( ( n ) >> ( i ) ) & 1 ) == 1 ;
    }
unsigned mc::SurfBuilder::from_index_to_id ( unsigned  i,
unsigned  j,
unsigned  k 
) const [inline, private]

Returns the unique identifier of a grid cube vertex corresponding to a given triple ( i , j , k) that uniquely identifies the vertex in the grid.

Parameters:
iFirst element of the vertex index.
jSecond element of the vertex index.
kThird element of the vertex index.
Returns:
The unique identifier of a grid cube vertex corresponding to a given triple ( i , j , k) that uniquely identifies the vertex in the grid.

Definition at line 325 of file surfbuilder.hpp.

References _grid, mc::Grid::get_size_x(), and mc::Grid::get_size_y().

    {
      unsigned sx = _grid->get_size_x() ;
      unsigned sy = _grid->get_size_y() ;

      return i + ( j * sx ) + ( k * sx * sy ) ;
    }

Returns the index of the first vertex of a given edge.

Parameters:
eThe index of an edge of a grid cube.
Returns:
The index of the first vertex of a given edge.

Definition at line 330 of file surfbuilder.cpp.

Referenced by make_lookup_table(), and run().

  {
    VERTS index ;

    if ( e == LB ) {
      index = LBN ;
    }
    else if ( e == LT ) {
      index = LTN ;
    }
    else if ( e == LN ) {
      index = LBN ;
    }
    else if ( e == LF ) {
      index = LBF ;
    }
    else if ( e == RB ) {
      index = RBN ;
    }
    else if ( e == RT ) {
      index = RTN ;
    }
    else if ( e == RN ) {
      index = RBN ;
    }
    else if ( e == RF ) {
      index = RBF ;
    }
    else if ( e == BN ) {
      index = LBN ;
    }
    else if ( e == BF ) {
      index = LBF ;
    }
    else if ( e == TN ) {
      index = LTN ;
    }
    else { // if ( e == TF ) {
      index = LTF ;
    }

    return index ;
  }

Returns the index of the second vertex of a given edge.

Parameters:
eThe index of an edge of a grid cube.
Returns:
The index of the second vertex of a given edge.

Definition at line 385 of file surfbuilder.cpp.

Referenced by make_lookup_table(), and run().

  {
    VERTS index ;

    if ( e == LB ) {
      index = LBF ;
    }
    else if ( e == LT ) {
      index = LTF ;
    }
    else if ( e == LN ) {
      index = LTN ;
    }
    else if ( e == LF ) {
      index = LTF ;
    }
    else if ( e == RB ) {
      index = RBF ;
    }
    else if ( e == RT ) {
      index = RTF ;
    }
    else if ( e == RN ) {
      index = RTN ;
    }
    else if ( e == RF ) {
      index = RTF ;
    }
    else if ( e == BN ) {
      index = RBN ;
    }
    else if ( e == BF ) {
      index = RBF ;
    }
    else if ( e == TN ) {
      index = RTN ;
    }
    else { // if ( e == TF ) {
      index = RTF ;
    }

    return index ;
  }

Returns the index of the left face of a given edge, considering the edge from the vertex with positive sign to the vertex with negative sign.

Parameters:
eThe index of an edge of a grid cube.
Returns:
The index of the left face of a given edge.

Definition at line 442 of file surfbuilder.cpp.

Referenced by change_face(), and make_lookup_table().

  {
    FACES index ;

    if ( e == LB ) {
      index = B ;
    }
    else if ( e == LT ) {
      index = L ;
    }
    else if ( e == LN ) {
      index = L ;
    }
    else if ( e == LF ) {
      index = F ;
    }
    else if ( e == RB ) {
      index = R ;
    }
    else if ( e == RT ) {
      index = T ;
    }
    else if ( e == RN ) {
      index = N ;
    }
    else if ( e == RF ) {
      index = R ;
    }
    else if ( e == BN ) {
      index = N ;
    }
    else if ( e == BF ) {
      index = B ;
    }
    else if ( e == TN ) {
      index = T ;
    }
    else { // if ( e == TF ) {
      index = F ;
    }

    return index ;
  }

Returns the index of the edge that follows a given edge in a clockwise traversal of the edges of a given face of the grid cube.

Parameters:
eThe index of an edge of a grid1 cube.
fThe index of a grid cube face containing the given edge.
Returns:
The index of the edge that follows a given edge in a clockwise traversal of the edges of a given face of the grid cube.

Definition at line 560 of file surfbuilder.cpp.

Referenced by make_lookup_table().

  {
    EDGES index ;

    if ( e == LB ) {
      index = ( f == L ) ? LF : BN ;
    }
    else if ( e == LT ) {
      index = ( f == L ) ? LN : TF ;
    }
    else if ( e == LN ) {
      index = ( f == L ) ? LB : TN ;
    }
    else if ( e == LF ) {
      index = ( f == L ) ? LT : BF ;
    }
    else if ( e == RB ) {
      index = ( f == R ) ? RN : BF ;
    }
    else if ( e == RT ) {
      index = ( f == R ) ? RF : TN ;
    }
    else if ( e == RN ) {
      index = ( f == R ) ? RT : BN ;
    }
    else if ( e == RF ) {
      index = ( f == R ) ? RB : TF ;
    }
    else if ( e == BN ) {
      index = ( f == B ) ? RB : LN ;
    }
    else if ( e == BF ) {
      index = ( f == B ) ? LB : RF ;
    }
    else if ( e == TN ) {
      index = ( f == T ) ? LT : RN ;
    }
    else { // if ( e == TF ) {
      index = ( f == T ) ? RT : LF ;
    }

    return index ;
  }

Returns the index of the right face of a given edge, considering the edge from the vertex with positive sign to the vertex with negative sign.

Parameters:
eThe index of an edge of a grid cube.
Returns:
The index of the right face of a given edge.

Definition at line 499 of file surfbuilder.cpp.

Referenced by change_face(), and make_lookup_table().

  {
    FACES index ;

    if ( e == LB ) {
      index = L ;
    }
    else if ( e == LT ) {
      index = T ;
    }
    else if ( e == LN ) {
      index = N ;
    }
    else if ( e == LF ) {
      index = L ;
    }
    else if ( e == RB ) {
      index = B ;
    }
    else if ( e == RT ) {
      index = R ;
    }
    else if ( e == RN ) {
      index = R ;
    }
    else if ( e == RF ) {
      index = F ;
    }
    else if ( e == BN ) {
      index = B ;
    }
    else if ( e == BF ) {
      index = F ;
    }
    else if ( e == TN ) {
      index = N ;
    }
    else { // if ( e == TF ) {
      index = T ;
    }

    return index ;
  }

The documentation for this class was generated from the following files: