An Implementation of the Marching Cubes Algorithm
1.0
|
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>
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< TRAVERSAL > | TABLEENTRY |
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< TABLEENTRY > | LOOKUPTABLE |
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. |
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.
mc::SurfBuilder::SurfBuilder | ( | Grid * | g | ) | [inline] |
Creates an instance of this class.
g | A 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 ) ; }
FACES mc::SurfBuilder::change_face | ( | EDGES | e, |
FACES | f | ||
) | const [inline, private] |
Returns the index of a face incident to an edge.
e | The index of an edge of a grid cube. |
f | The index of a grid cube face incident to the given edge, which is not equal to the other face that this method should return. |
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.
i | First element of a triple that identifies the origin vertex of the grid cube containing the edge. |
j | Second element of a triple that identifies the origin vertex of the grid cube containing the edge. |
k | Third element of a triple that identifies the origin vertex of the grid cube containing the edge. |
v1 | The index of the first vertex of the edge with respect to the grid cube. |
v2 | The index of the second vertex of the edge with respect to the grid cube. |
f1 | The value of the unknown implicit function at the first vertex of the edge. |
f2 | The value of the unknown implicit function at the second vertex of the edge. |
pt | A 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.
n | A given number. |
i | Another given number representing the position of bit. |
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.
i | First element of the vertex index. |
j | Second element of the vertex index. |
k | Third element of the vertex index. |
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 ) ; }
SurfBuilder::VERTS mc::SurfBuilder::get_1st_vertex | ( | EDGES | e | ) | const [private] |
Returns the index of the first vertex of a given edge.
e | The index of an edge of a grid cube. |
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 ; }
SurfBuilder::VERTS mc::SurfBuilder::get_2nd_vertex | ( | EDGES | e | ) | const [private] |
Returns the index of the second vertex of a given edge.
e | The index of an edge of a grid cube. |
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 ; }
SurfBuilder::FACES mc::SurfBuilder::left_face | ( | EDGES | e | ) | const [private] |
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.
e | The index of an edge of a grid cube. |
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 ; }
SurfBuilder::EDGES mc::SurfBuilder::next_cw_edge | ( | EDGES | e, |
FACES | f | ||
) | const [private] |
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.
e | The index of an edge of a grid1 cube. |
f | The index of a grid cube face containing the given edge. |
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 ; }
SurfBuilder::FACES mc::SurfBuilder::right_face | ( | EDGES | e | ) | const [private] |
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.
e | The index of an edge of a grid cube. |
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 ; }