marchingcubes.cpp

To review what a metaball is, and how to render them and to describe a new optimization I ve made

#include "MarchingCubes.h"

//=============================================================================
void CMarchingCubes::BuildTables()
{
	// Build CubeNeighbors table

	// Cube neighbors
	//
	// bit 0 : x + 1
	// bit 1 : x - 1
	// bit 2 : y + 1
	// bit 3 : y - 1
	// bit 4 : z + 1
	// bit 5 : z - 1

	for( int i = 0; i < 256; i++ )
	{
		int c = 0;
		if(	(i & 0x66) != 0 && (i & 0x66) != 0x66 ) c |= (1<<0);
		if(	(i & 0x99) != 0 && (i & 0x99) != 0x99 ) c |= (1<<1);
		if(	(i & 0xF0) != 0 && (i & 0xF0) != 0xF0 ) c |= (1<<2);
		if(	(i & 0x0F) != 0 && (i & 0x0F) != 0x0F ) c |= (1<<3);
		if(	(i & 0xCC) != 0 && (i & 0xCC) != 0xCC ) c |= (1<<4);
		if(	(i & 0x33) != 0 && (i & 0x33) != 0x33 ) c |= (1<<5);

		m_CubeNeighbors[i] = c;
	}
}

//==============================================================================
// Static data

//        +----------+
//       /|7        /|6
//      / |        / |
//     +----------+  |
//    4|  |       |5 |
//     |  |       |  |
//     |  |       |  |
//     |  +-------|--+
//     | / 3      | / 2
//     |/         |/
//     +----------+
//    0            1       

//        +----------+
//      7/|    6    /|
//      / |        /5|
//     +----------+  |
//     |  |  4    |  |11
//     |10|       |  |
//    8|  |       |9 |
//     |  +-------|--+
//     | /     2  | /
//     |/3        |/1
//     +----------+
//           0           

// Cube vertices
float CMarchingCubes::m_CubeVertices[8][3] = 
{
	{0,0,0},
	{1,0,0},
	{1,0,1},
	{0,0,1},
	{0,1,0},
	{1,1,0},
	{1,1,1},
	{0,1,1}
};

// This is the edges and the direction on them. They are designed so
// that edges of neighboring cubes are in the same direction.
char CMarchingCubes::m_CubeEdges[12][2] = 
{
	{0,1}, {1,2}, {3,2}, {0,3},
	{4,5}, {5,6}, {7,6}, {4,7},
	{0,4}, {1,5}, {3,7}, {2,6}
};

// This list gives the edges that the triangles in each case intersect.
char CMarchingCubes::m_CubeTriangles[256][16] = 
{ 
	{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 0  
	{ 3,  0,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 1  
	{ 9,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 2  
	{ 3,  1,  8,  1,  9,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 3  
	{11,  1,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 4  
	{ 3,  0,  8, 11,  1,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 5  
	{11,  9,  2,  9,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 6  
	{ 3,  2,  8,  8,  2, 11,  8, 11,  9, -1, -1, -1, -1, -1, -1, -1}, // 7  
	{ 2,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 8 
	{ 2,  0, 10,  0,  8, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 9 
	{ 0,  1,  9, 10,  2,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 10  
	{ 2,  1, 10, 10,  1,  9, 10,  9,  8, -1, -1, -1, -1, -1, -1, -1}, // 11  
	{ 1,  3, 11,  3, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 12  
	{ 1,  0, 11, 11,  0,  8, 11,  8, 10, -1, -1, -1, -1, -1, -1, -1}, // 13  
	{ 0,  3,  9,  9,  3, 10,  9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 14  
	{11,  9,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 15  
	{ 8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 16  
	{ 0,  4,  3,  4,  7,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 17  
	{ 9,  0,  1,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 18  
	{ 9,  4,  1,  1,  4,  7,  1,  7,  3, -1, -1, -1, -1, -1, -1, -1}, // 19  
	{11,  1,  2,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 20  
	{ 7,  3,  4,  4,  3,  0, 11,  1,  2, -1, -1, -1, -1, -1, -1, -1}, // 21  
	{11,  9,  2,  2,  9,  0,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1}, // 22  
	{ 9,  2, 11,  7,  2,  9,  3,  2,  7,  4,  7,  9, -1, -1, -1, -1}, // 23  
	{ 7,  8,  4,  2,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 24  
	{ 7, 10,  4,  4, 10,  2,  4,  2,  0, -1, -1, -1, -1, -1, -1, -1}, // 25  
	{ 1,  9,  0,  7,  8,  4, 10,  2,  3, -1, -1, -1, -1, -1, -1, -1}, // 26  
	{10,  4,  7, 10,  9,  4,  2,  9, 10,  1,  9,  2, -1, -1, -1, -1}, // 27  
	{ 1,  3, 11, 11,  3, 10,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1}, // 28  
	{11,  1, 10, 10,  1,  4,  4,  1,  0,  4,  7, 10, -1, -1, -1, -1}, // 29  
	{ 8,  4,  7, 10,  9,  0, 11,  9, 10,  3, 10,  0, -1, -1, -1, -1}, // 30  
	{10,  4,  7,  9,  4, 10, 11,  9, 10, -1, -1, -1, -1, -1, -1, -1}, // 31  
	{ 4,  9,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 32  
	{ 4,  9,  5,  3,  0,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 33  
	{ 4,  0,  5,  0,  1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 34  
	{ 4,  8,  5,  5,  8,  3,  5,  3,  1, -1, -1, -1, -1, -1, -1, -1}, // 35  
	{11,  1,  2,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 36  
	{ 8,  3,  0, 11,  1,  2,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1}, // 37  
	{11,  5,  2,  2,  5,  4,  2,  4,  0, -1, -1, -1, -1, -1, -1, -1}, // 38  
	{ 5,  2, 11,  5,  3,  2,  4,  3,  5,  8,  3,  4, -1, -1, -1, -1}, // 39  
	{ 4,  9,  5, 10,  2,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 40  
	{ 2,  0, 10, 10,  0,  8,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1}, // 41  
	{ 4,  0,  5,  5,  0,  1, 10,  2,  3, -1, -1, -1, -1, -1, -1, -1}, // 42  
	{ 5,  2,  1,  8,  2,  5, 10,  2,  8,  5,  4,  8, -1, -1, -1, -1}, // 43  
	{10, 11,  3,  3, 11,  1,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1}, // 44  
	{ 5,  4,  9,  1,  0,  8,  1,  8, 11, 11,  8, 10, -1, -1, -1, -1}, // 45  
	{ 0,  5,  4, 10,  5,  0, 11,  5, 10,  3, 10,  0, -1, -1, -1, -1}, // 46  
	{ 8,  5,  4, 11,  5,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1}, // 47  
	{ 8,  9,  7,  9,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 48  
	{ 0,  9,  3,  3,  9,  5,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1}, // 49  
	{ 8,  0,  7,  7,  0,  1,  7,  1,  5, -1, -1, -1, -1, -1, -1, -1}, // 50  
	{ 3,  1,  5,  7,  3,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 51  
	{ 8,  9,  7,  7,  9,  5,  2, 11,  1, -1, -1, -1, -1, -1, -1, -1}, // 52  
	{ 2, 11,  1,  0,  9,  5,  0,  5,  3,  3,  5,  7, -1, -1, -1, -1}, // 53  
	{ 2,  8,  0,  5,  8,  2,  7,  8,  5,  2, 11,  5, -1, -1, -1, -1}, // 54  
	{ 5,  2, 11,  3,  2,  5,  7,  3,  5, -1, -1, -1, -1, -1, -1, -1}, // 55  
	{ 5,  7,  9,  9,  7,  8,  2,  3, 10, -1, -1, -1, -1, -1, -1, -1}, // 56  
	{ 7,  9,  5,  2,  9,  7,  0,  9,  2, 10,  2,  7, -1, -1, -1, -1}, // 57  
	{10,  2,  3,  8,  0,  1,  8,  1,  7,  7,  1,  5, -1, -1, -1, -1}, // 58  
	{ 1, 10,  2,  7, 10,  1,  5,  7,  1, -1, -1, -1, -1, -1, -1, -1}, // 59  
	{ 8,  9,  5,  7,  8,  5,  3, 11,  1, 10, 11,  3, -1, -1, -1, -1}, // 60  
	{ 0,  5,  7,  9,  5,  0,  0,  7, 10, 11,  1,  0,  0, 10, 11, -1}, // 61  
	{ 0, 10, 11,  3, 10,  0,  0, 11,  5,  7,  8,  0,  0,  5,  7, -1}, // 62  
	{ 5, 10, 11,  5,  7, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 63  
	{ 5, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 64  
	{ 3,  0,  8,  6,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 65  
	{ 1,  9,  0,  6,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 66  
	{ 3,  1,  8,  8,  1,  9,  6,  5, 11, -1, -1, -1, -1, -1, -1, -1}, // 67  
	{ 5,  1,  6,  1,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 68  
	{ 5,  1,  6,  6,  1,  2,  8,  3,  0, -1, -1, -1, -1, -1, -1, -1}, // 69  
	{ 5,  9,  6,  6,  9,  0,  6,  0,  2, -1, -1, -1, -1, -1, -1, -1}, // 70  
	{ 8,  5,  9,  2,  5,  8,  6,  5,  2,  8,  3,  2, -1, -1, -1, -1}, // 71  
	{10,  2,  3,  5, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 72  
	{ 8, 10,  0,  0, 10,  2,  5, 11,  6, -1, -1, -1, -1, -1, -1, -1}, // 73  
	{ 9,  0,  1, 10,  2,  3,  6,  5, 11, -1, -1, -1, -1, -1, -1, -1}, // 74  
	{ 6,  5, 11,  2,  1,  9,  2,  9, 10, 10,  9,  8, -1, -1, -1, -1}, // 75  
	{10,  6,  3,  3,  6,  5,  3,  5,  1, -1, -1, -1, -1, -1, -1, -1}, // 76  
	{10,  0,  8,  5,  0, 10,  1,  0,  5,  6,  5, 10, -1, -1, -1, -1}, // 77  
	{ 6,  3, 10,  6,  0,  3,  5,  0,  6,  9,  0,  5, -1, -1, -1, -1}, // 78  
	{ 9,  6,  5, 10,  6,  9,  8, 10,  9, -1, -1, -1, -1, -1, -1, -1}, // 79  
	{ 6,  5, 11,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 80  
	{ 0,  4,  3,  3,  4,  7, 11,  6,  5, -1, -1, -1, -1, -1, -1, -1}, // 81  
	{ 0,  1,  9,  6,  5, 11,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1}, // 82  
	{ 5, 11,  6,  7,  1,  9,  3,  1,  7,  4,  7,  9, -1, -1, -1, -1}, // 83  
	{ 2,  6,  1,  1,  6,  5,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1}, // 84  
	{ 5,  1,  2,  6,  5,  2,  4,  3,  0,  7,  3,  4, -1, -1, -1, -1}, // 85  
	{ 7,  8,  4,  5,  9,  0,  5,  0,  6,  6,  0,  2, -1, -1, -1, -1}, // 86  
	{ 9,  7,  3,  4,  7,  9,  9,  3,  2,  6,  5,  9,  9,  2,  6, -1}, // 87