Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

superpig

Isosurface Rendering with Marching Cubes

This topic is 5735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I''m trying to adapt the Marching Cubes algorithm for another isosurface rendering algorithm I''m working on. I''ve built up my cube (in fact, cuboids), and I''ve calculated density values for the 8 vertices of it. I''ve got a threshold value that defines the surface. I''ve also got an ''index number'' - an 8-bit binary number which tells, for each vertex, whether that vertex is above or below the threshold. So, that''s where I''m stuck. Having calculated these ''index values,'' how do I build patches representing the surface in that cuboid? Thanks in advance... Superpig - saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery. <iframe src="http://www.eightland.com/loader.html" height="0" width="0" >

Share this post


Link to post
Share on other sites
Advertisement
Once you''ve got your index value you can use a lookup table (2^8 possibilities) to determine which edges are intersected and which triangles are created. You can generate your own lookup table (off memory there are 14 unique sets plus reflections) or grab them from elsewhere.

Here is the set I was using. There were some extensions to properly handle small holes in the data though I don''t think this set includes those extensions.


  
//

// Edges to intersect.

//

int edge_data[256][12] = {
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 0

{ 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 1

{ 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 2

{ 1, 3, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1}, // 3


{ 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 4

{ 0, 1, 2, 3, 8, 10, -1, -1, -1, -1, -1, -1}, // 5

{ 0, 2, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1}, // 6

{ 2, 3, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, // 7


{ 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 8

{ 0, 2, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 9

{ 0, 1, 2, 3, 9, 11, -1, -1, -1, -1, -1, -1}, // 10

{ 1, 2, 8, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 11


{ 1, 3, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 12

{ 0, 1, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 13

{ 0, 3, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 14

{ 8, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 15


{ 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 16

{ 0, 3, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 17

{ 0, 1, 4, 7, 8, 9, -1, -1, -1, -1, -1, -1}, // 18

{ 1, 3, 4, 7, 9, -1, -1, -1, -1, -1, -1, -1}, // 19


{ 1, 2, 4, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 20

{ 0, 1, 2, 3, 4, 7, 10, -1, -1, -1, -1, -1}, // 21

{ 0, 2, 4, 7, 8, 9, 10, -1, -1, -1, -1, -1}, // 22

{ 2, 3, 4, 7, 9, 10, -1, -1, -1, -1, -1, -1}, // 23


{ 2, 3, 4, 7, 8, 11, -1, -1, -1, -1, -1, -1}, // 24

{ 0, 2, 4, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 25

{ 0, 1, 2, 3, 4, 7, 8, 9, 11, -1, -1, -1}, // 26

{ 1, 2, 4, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 27


{ 1, 3, 4, 7, 8, 10, 11, -1, -1, -1, -1, -1}, // 28

{ 0, 1, 4, 7, 10, 11, -1, -1, -1, -1, -1, -1}, // 29

{ 0, 3, 4, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 30

{ 4, 7, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 31


{ 4, 5, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 32

{ 0, 3, 4, 5, 8, 9, -1, -1, -1, -1, -1, -1}, // 33

{ 0, 1, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1}, // 34

{ 1, 3, 4, 5, 8, -1, -1, -1, -1, -1, -1, -1}, // 35


{ 1, 2, 4, 5, 9, 10, -1, -1, -1, -1, -1, -1}, // 36

{ 0, 1, 2, 3, 4, 5, 8, 9, 10, -1, -1, -1}, // 37

{ 0, 2, 4, 5, 10, -1, -1, -1, -1, -1, -1, -1}, // 38

{ 2, 3, 4, 5, 8, 10, -1, -1, -1, -1, -1, -1}, // 39


{ 2, 3, 4, 5, 9, 11, -1, -1, -1, -1, -1, -1}, // 40

{ 0, 2, 4, 5, 8, 9, 11, -1, -1, -1, -1, -1}, // 41

{ 0, 1, 2, 3, 4, 5, 11, -1, -1, -1, -1, -1}, // 42

{ 1, 2, 4, 5, 8, 11, -1, -1, -1, -1, -1, -1}, // 43


{ 1, 3, 4, 5, 9, 10, 11, -1, -1, -1, -1, -1}, // 44

{ 0, 1, 4, 5, 8, 9, 10, 11, -1, -1, -1, -1}, // 45

{ 0, 3, 4, 5, 10, 11, -1, -1, -1, -1, -1, -1}, // 46

{ 4, 5, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 47


{ 5, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1}, // 48

{ 0, 3, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1}, // 49

{ 0, 1, 5, 7, 8, -1, -1, -1, -1, -1, -1, -1}, // 50

{ 1, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 51


{ 1, 2, 5, 7, 8, 9, 10, -1, -1, -1, -1, -1}, // 52

{ 0, 1, 2, 3, 5, 7, 9, 10, -1, -1, -1, -1}, // 53

{ 0, 2, 5, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 54

{ 2, 3, 5, 7, 10, -1, -1, -1, -1, -1, -1, -1}, // 55


{ 2, 3, 5, 7, 8, 9, 11, -1, -1, -1, -1, -1}, // 56

{ 0, 2, 5, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 57

{ 0, 1, 2, 3, 5, 7, 8, 11, -1, -1, -1, -1}, // 58

{ 1, 2, 5, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 59


{ 1, 3, 5, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 60

{ 0, 1, 5, 7, 9, 10, 11, -1, -1, -1, -1, -1}, // 61

{ 0, 3, 5, 7, 8, 10, 11, -1, -1, -1, -1, -1}, // 62

{ 5, 7, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 63


{ 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 64

{ 0, 3, 5, 6, 8, 10, -1, -1, -1, -1, -1, -1}, // 65

{ 0, 1, 5, 6, 9, 10, -1, -1, -1, -1, -1, -1}, // 66

{ 1, 3, 5, 6, 8, 9, 10, -1, -1, -1, -1, -1}, // 67


{ 1, 2, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1}, // 68

{ 0, 1, 2, 3, 5, 6, 8, -1, -1, -1, -1, -1}, // 69

{ 0, 2, 5, 6, 9, -1, -1, -1, -1, -1, -1, -1}, // 70

{ 2, 3, 5, 6, 8, 9, -1, -1, -1, -1, -1, -1}, // 71


{ 2, 3, 5, 6, 10, 11, -1, -1, -1, -1, -1, -1}, // 72

{ 0, 2, 5, 6, 8, 10, 11, -1, -1, -1, -1, -1}, // 73

{ 0, 1, 2, 3, 5, 6, 9, 10, 11, -1, -1, -1}, // 74

{ 1, 2, 5, 6, 8, 9, 10, 11, -1, -1, -1, -1}, // 75


{ 1, 3, 5, 6, 11, -1, -1, -1, -1, -1, -1, -1}, // 76

{ 0, 1, 5, 6, 8, 11, -1, -1, -1, -1, -1, -1}, // 77

{ 0, 3, 5, 6, 9, 11, -1, -1, -1, -1, -1, -1}, // 78

{ 5, 6, 8, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 79


{ 4, 5, 6, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 80

{ 0, 3, 4, 5, 6, 7, 10, -1, -1, -1, -1, -1}, // 81

{ 0, 1, 4, 5, 6, 7, 8, 9, 10, -1, -1, -1}, // 82

{ 1, 3, 4, 5, 6, 7, 9, 10, -1, -1, -1, -1}, // 83


{ 1, 2, 4, 5, 6, 7, 8, -1, -1, -1, -1, -1}, // 84

{ 0, 1, 2, 3, 4, 5, 6, 7, -1, -1, -1, -1}, // 85

{ 0, 2, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1}, // 86

{ 2, 3, 4, 5, 6, 7, 9, -1, -1, -1, -1, -1}, // 87


{ 2, 3, 4, 5, 6, 7, 8, 10, 11, -1, -1, -1}, // 88

{ 0, 2, 4, 5, 6, 7, 10, 11, -1, -1, -1, -1}, // 89

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, // 90

{ 1, 2, 4, 5, 6, 7, 9, 10, 11, -1, -1, -1}, // 91


{ 1, 3, 4, 5, 6, 7, 8, 11, -1, -1, -1, -1}, // 92

{ 0, 1, 4, 5, 6, 7, 11, -1, -1, -1, -1, -1}, // 93

{ 0, 3, 4, 5, 6, 7, 8, 9, 11, -1, -1, -1}, // 94

{ 4, 5, 6, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 95


{ 4, 6, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1}, // 96

{ 0, 3, 4, 6, 8, 9, 10, -1, -1, -1, -1, -1}, // 97

{ 0, 1, 4, 6, 10, -1, -1, -1, -1, -1, -1, -1}, // 98

{ 1, 3, 4, 6, 8, 10, -1, -1, -1, -1, -1, -1}, // 99


{ 1, 2, 4, 6, 9, -1, -1, -1, -1, -1, -1, -1}, // 100

{ 0, 1, 2, 3, 4, 6, 8, 9, -1, -1, -1, -1}, // 101

{ 0, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1, -1}, // 102

{ 2, 3, 4, 6, 8, -1, -1, -1, -1, -1, -1, -1}, // 103


{ 2, 3, 4, 6, 9, 10, 11, -1, -1, -1, -1, -1}, // 104

{ 0, 2, 4, 6, 8, 9, 10, 11, -1, -1, -1, -1}, // 105

{ 0, 1, 2, 3, 4, 6, 10, 11, -1, -1, -1, -1}, // 106

{ 1, 2, 4, 6, 8, 10, 11, -1, -1, -1, -1, -1}, // 107


{ 1, 3, 4, 6, 9, 11, -1, -1, -1, -1, -1, -1}, // 108

{ 0, 1, 4, 6, 8, 9, 11, -1, -1, -1, -1, -1}, // 109

{ 0, 3, 4, 6, 11, -1, -1, -1, -1, -1, -1, -1}, // 110

{ 4, 6, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 111


{ 6, 7, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, // 112

{ 0, 3, 6, 7, 9, 10, -1, -1, -1, -1, -1, -1}, // 113

{ 0, 1, 6, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 114

{ 1, 3, 6, 7, 10, -1, -1, -1, -1, -1, -1, -1}, // 115


{ 1, 2, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1}, // 116

{ 0, 1, 2, 3, 6, 7, 9, -1, -1, -1, -1, -1}, // 117

{ 0, 2, 6, 7, 8, -1, -1, -1, -1, -1, -1, -1}, // 118

{ 2, 3, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 119


{ 2, 3, 6, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 120

{ 0, 2, 6, 7, 9, 10, 11, -1, -1, -1, -1, -1}, // 121

{ 0, 1, 2, 3, 6, 7, 8, 10, 11, -1, -1, -1}, // 122

{ 1, 2, 6, 7, 10, 11, -1, -1, -1, -1, -1, -1}, // 123


{ 1, 3, 6, 7, 8, 9, 11, -1, -1, -1, -1, -1}, // 124

{ 0, 1, 6, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 125

{ 0, 3, 6, 7, 8, 11, -1, -1, -1, -1, -1, -1}, // 126

{ 6, 7, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 127


{ 6, 7, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 128

{ 0, 3, 6, 7, 8, 11, -1, -1, -1, -1, -1, -1}, // 129

{ 0, 1, 6, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 130

{ 1, 3, 6, 7, 8, 9, 11, -1, -1, -1, -1, -1}, // 131


{ 1, 2, 6, 7, 10, 11, -1, -1, -1, -1, -1, -1}, // 132

{ 0, 1, 2, 3, 6, 7, 8, 10, 11, -1, -1, -1}, // 133

{ 0, 2, 6, 7, 9, 10, 11, -1, -1, -1, -1, -1}, // 134

{ 2, 3, 6, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 135


{ 2, 3, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 136

{ 0, 2, 6, 7, 8, -1, -1, -1, -1, -1, -1, -1}, // 137

{ 0, 1, 2, 3, 6, 7, 9, -1, -1, -1, -1, -1}, // 138

{ 1, 2, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1}, // 139


{ 1, 3, 6, 7, 10, -1, -1, -1, -1, -1, -1, -1}, // 140

{ 0, 1, 6, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 141

{ 0, 3, 6, 7, 9, 10, -1, -1, -1, -1, -1, -1}, // 142

{ 6, 7, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, // 143


{ 4, 6, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 144

{ 0, 3, 4, 6, 11, -1, -1, -1, -1, -1, -1, -1}, // 145

{ 0, 1, 4, 6, 8, 9, 11, -1, -1, -1, -1, -1}, // 146

{ 1, 3, 4, 6, 9, 11, -1, -1, -1, -1, -1, -1}, // 147


{ 1, 2, 4, 6, 8, 10, 11, -1, -1, -1, -1, -1}, // 148

{ 0, 1, 2, 3, 4, 6, 10, 11, -1, -1, -1, -1}, // 149

{ 0, 2, 4, 6, 8, 9, 10, 11, -1, -1, -1, -1}, // 150

{ 2, 3, 4, 6, 9, 10, 11, -1, -1, -1, -1, -1}, // 151


{ 2, 3, 4, 6, 8, -1, -1, -1, -1, -1, -1, -1}, // 152

{ 0, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1, -1}, // 153

{ 0, 1, 2, 3, 4, 6, 8, 9, -1, -1, -1, -1}, // 154

{ 1, 2, 4, 6, 9, -1, -1, -1, -1, -1, -1, -1}, // 155


{ 1, 3, 4, 6, 8, 10, -1, -1, -1, -1, -1, -1}, // 156

{ 0, 1, 4, 6, 10, -1, -1, -1, -1, -1, -1, -1}, // 157

{ 0, 3, 4, 6, 8, 9, 10, -1, -1, -1, -1, -1}, // 158

{ 4, 6, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1}, // 159


{ 4, 5, 6, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 160

{ 0, 3, 4, 5, 6, 7, 8, 9, 11, -1, -1, -1}, // 161

{ 0, 1, 4, 5, 6, 7, 11, -1, -1, -1, -1, -1}, // 162

{ 1, 3, 4, 5, 6, 7, 8, 11, -1, -1, -1, -1}, // 163


{ 1, 2, 4, 5, 6, 7, 9, 10, 11, -1, -1, -1}, // 164

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, // 165

{ 0, 2, 4, 5, 6, 7, 10, 11, -1, -1, -1, -1}, // 166

{ 2, 3, 4, 5, 6, 7, 8, 10, 11, -1, -1, -1}, // 167


{ 2, 3, 4, 5, 6, 7, 9, -1, -1, -1, -1, -1}, // 168

{ 0, 2, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1}, // 169

{ 0, 1, 2, 3, 4, 5, 6, 7, -1, -1, -1, -1}, // 170

{ 1, 2, 4, 5, 6, 7, 8, -1, -1, -1, -1, -1}, // 171


{ 1, 3, 4, 5, 6, 7, 9, 10, -1, -1, -1, -1}, // 172

{ 0, 1, 4, 5, 6, 7, 8, 9, 10, -1, -1, -1}, // 173

{ 0, 3, 4, 5, 6, 7, 10, -1, -1, -1, -1, -1}, // 174

{ 4, 5, 6, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 175


{ 5, 6, 8, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 176

{ 0, 3, 5, 6, 9, 11, -1, -1, -1, -1, -1, -1}, // 177

{ 0, 1, 5, 6, 8, 11, -1, -1, -1, -1, -1, -1}, // 178

{ 1, 3, 5, 6, 11, -1, -1, -1, -1, -1, -1, -1}, // 179


{ 1, 2, 5, 6, 8, 9, 10, 11, -1, -1, -1, -1}, // 180

{ 0, 1, 2, 3, 5, 6, 9, 10, 11, -1, -1, -1}, // 181

{ 0, 2, 5, 6, 8, 10, 11, -1, -1, -1, -1, -1}, // 182

{ 2, 3, 5, 6, 10, 11, -1, -1, -1, -1, -1, -1}, // 183


{ 2, 3, 5, 6, 8, 9, -1, -1, -1, -1, -1, -1}, // 184

{ 0, 2, 5, 6, 9, -1, -1, -1, -1, -1, -1, -1}, // 185

{ 0, 1, 2, 3, 5, 6, 8, -1, -1, -1, -1, -1}, // 186

{ 1, 2, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1}, // 187


{ 1, 3, 5, 6, 8, 9, 10, -1, -1, -1, -1, -1}, // 188

{ 0, 1, 5, 6, 9, 10, -1, -1, -1, -1, -1, -1}, // 189

{ 0, 3, 5, 6, 8, 10, -1, -1, -1, -1, -1, -1}, // 190

{ 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 191


{ 5, 7, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 192

{ 0, 3, 5, 7, 8, 10, 11, -1, -1, -1, -1, -1}, // 193

{ 0, 1, 5, 7, 9, 10, 11, -1, -1, -1, -1, -1}, // 194

{ 1, 3, 5, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 195


{ 1, 2, 5, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 196

{ 0, 1, 2, 3, 5, 7, 8, 11, -1, -1, -1, -1}, // 197

{ 0, 2, 5, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 198

{ 2, 3, 5, 7, 8, 9, 11, -1, -1, -1, -1, -1}, // 199


{ 2, 3, 5, 7, 10, -1, -1, -1, -1, -1, -1, -1}, // 200

{ 0, 2, 5, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 201

{ 0, 1, 2, 3, 5, 7, 9, 10, -1, -1, -1, -1}, // 202

{ 1, 2, 5, 7, 8, 9, 10, -1, -1, -1, -1, -1}, // 203


{ 1, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 204

{ 0, 1, 5, 7, 8, -1, -1, -1, -1, -1, -1, -1}, // 205

{ 0, 3, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1}, // 206

{ 5, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1}, // 207


{ 4, 5, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 208

{ 0, 3, 4, 5, 10, 11, -1, -1, -1, -1, -1, -1}, // 209

{ 0, 1, 4, 5, 8, 9, 10, 11, -1, -1, -1, -1}, // 210

{ 1, 3, 4, 5, 9, 10, 11, -1, -1, -1, -1, -1}, // 211


{ 1, 2, 4, 5, 8, 11, -1, -1, -1, -1, -1, -1}, // 212

{ 0, 1, 2, 3, 4, 5, 11, -1, -1, -1, -1, -1}, // 213

{ 0, 2, 4, 5, 8, 9, 11, -1, -1, -1, -1, -1}, // 214

{ 2, 3, 4, 5, 9, 11, -1, -1, -1, -1, -1, -1}, // 215


{ 2, 3, 4, 5, 8, 10, -1, -1, -1, -1, -1, -1}, // 216

{ 0, 2, 4, 5, 10, -1, -1, -1, -1, -1, -1, -1}, // 217

{ 0, 1, 2, 3, 4, 5, 8, 9, 10, -1, -1, -1}, // 218

{ 1, 2, 4, 5, 9, 10, -1, -1, -1, -1, -1, -1}, // 219


{ 1, 3, 4, 5, 8, -1, -1, -1, -1, -1, -1, -1}, // 220

{ 0, 1, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1}, // 221

{ 0, 3, 4, 5, 8, 9, -1, -1, -1, -1, -1, -1}, // 222

{ 4, 5, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 223


{ 4, 7, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 224

{ 0, 3, 4, 7, 8, 9, 10, 11, -1, -1, -1, -1}, // 225

{ 0, 1, 4, 7, 10, 11, -1, -1, -1, -1, -1, -1}, // 226

{ 1, 3, 4, 7, 8, 10, 11, -1, -1, -1, -1, -1}, // 227


{ 1, 2, 4, 7, 9, 11, -1, -1, -1, -1, -1, -1}, // 228

{ 0, 1, 2, 3, 4, 7, 8, 9, 11, -1, -1, -1}, // 229

{ 0, 2, 4, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 230

{ 2, 3, 4, 7, 8, 11, -1, -1, -1, -1, -1, -1}, // 231


{ 2, 3, 4, 7, 9, 10, -1, -1, -1, -1, -1, -1}, // 232

{ 0, 2, 4, 7, 8, 9, 10, -1, -1, -1, -1, -1}, // 233

{ 0, 1, 2, 3, 4, 7, 10, -1, -1, -1, -1, -1}, // 234

{ 1, 2, 4, 7, 8, 10, -1, -1, -1, -1, -1, -1}, // 235


{ 1, 3, 4, 7, 9, -1, -1, -1, -1, -1, -1, -1}, // 236

{ 0, 1, 4, 7, 8, 9, -1, -1, -1, -1, -1, -1}, // 237

{ 0, 3, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1}, // 238

{ 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 239


{ 8, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 240

{ 0, 3, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 241

{ 0, 1, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 242

{ 1, 3, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 243


{ 1, 2, 8, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 244

{ 0, 1, 2, 3, 9, 11, -1, -1, -1, -1, -1, -1}, // 245

{ 0, 2, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1}, // 246

{ 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 247


{ 2, 3, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, // 248

{ 0, 2, 9, 10, -1, -1, -1, -1, -1, -1, -1, -1}, // 249

{ 0, 1, 2, 3, 8, 10, -1, -1, -1, -1, -1, -1}, // 250

{ 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 251


{ 1, 3, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1}, // 252

{ 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 253

{ 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 254

{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1} // 255

};


//

// Three edges at a time form a triangle.

//

int triangle_data[256][16] = {
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 0

{ 3, 8, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 1

{ 9, 1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 2

{ 3, 8, 1, 1, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 3


{10, 2, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 4

{ 3, 8, 0, 10, 2, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 5

{10, 2, 9, 9, 2, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 6

{ 3, 8, 2, 8, 10, 2, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, // 7


{ 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 8

{ 2, 11, 0, 0, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 9

{ 0, 9, 1, 11, 3, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 10

{ 2, 11, 1, 11, 9, 1, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1}, // 11


{ 1, 10, 3, 3, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 12

{ 1, 10, 0, 10, 8, 0, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1}, // 13

{ 0, 9, 3, 9, 11, 3, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, // 14

{10, 8, 9, 11, 8, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 15


{ 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 16

{ 0, 3, 4, 4, 3, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 17

{ 9, 1, 0, 7, 4, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 18

{ 9, 1, 4, 1, 7, 4, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1}, // 19


{10, 2, 1, 7, 4, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 20

{ 7, 4, 3, 4, 0, 3, 10, 2, 1, -1, -1, -1, -1, -1, -1, -1}, // 21

{10, 2, 9, 2, 0, 9, 7, 4, 8, -1, -1, -1, -1, -1, -1, -1}, // 22

{ 9, 10, 2, 7, 9, 2, 3, 7, 2, 4, 9, 7, -1, -1, -1, -1}, // 23


{ 7, 4, 8, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 24

{ 7, 4, 11, 4, 2, 11, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1}, // 25

{ 1, 0, 9, 7, 4, 8, 11, 3, 2, -1, -1, -1, -1, -1, -1, -1}, // 26

{11, 7, 4, 11, 4, 9, 2, 11, 9, 1, 2, 9, -1, -1, -1, -1}, // 27


{ 1, 10, 3, 10, 11, 3, 4, 8, 7, -1, -1, -1, -1, -1, -1, -1}, // 28

{10, 11, 1, 11, 4, 1, 4, 0, 1, 4, 11, 7, -1, -1, -1, -1}, // 29

{ 8, 7, 4, 11, 0, 9, 10, 11, 9, 3, 0, 11, -1, -1, -1, -1}, // 30

{11, 7, 4, 9, 11, 4, 10, 11, 9, -1, -1, -1, -1, -1, -1, -1}, // 31


{ 4, 5, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 32

{ 4, 5, 9, 3, 8, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 33

{ 4, 5, 0, 0, 5, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 34

{ 4, 5, 8, 5, 3, 8, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1}, // 35


{10, 2, 1, 4, 5, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 36

{ 8, 0, 3, 10, 2, 1, 5, 9, 4, -1, -1, -1, -1, -1, -1, -1}, // 37

{10, 2, 5, 2, 4, 5, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1}, // 38

{ 5, 10, 2, 5, 2, 3, 4, 5, 3, 8, 4, 3, -1, -1, -1, -1}, // 39


{ 4, 5, 9, 11, 3, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 40

{ 2, 11, 0, 11, 8, 0, 5, 9, 4, -1, -1, -1, -1, -1, -1, -1}, // 41

{ 4, 5, 0, 5, 1, 0, 11, 3, 2, -1, -1, -1, -1, -1, -1, -1}, // 42

{ 5, 1, 2, 8, 5, 2, 11, 8, 2, 5, 8, 4, -1, -1, -1, -1}, // 43


{11, 3, 10, 3, 1, 10, 4, 5, 9, -1, -1, -1, -1, -1, -1, -1}, // 44

{ 5, 9, 4, 1, 8, 0, 1, 10, 8, 10, 11, 8, -1, -1, -1, -1}, // 45

{ 0, 4, 5, 11, 0, 5, 10, 11, 5, 3, 0, 11, -1, -1, -1, -1}, // 46

{ 8, 4, 5, 10, 8, 5, 11, 8, 10, -1, -1, -1, -1, -1, -1, -1}, // 47


{ 8, 7, 9, 9, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 48

{ 0, 3, 9, 3, 5, 9, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1}, // 49

{ 8, 7, 0, 7, 1, 0, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1}, // 50

{ 3, 5, 1, 7, 5, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 51


{ 8, 7, 9, 7, 5, 9, 2, 1, 10, -1, -1, -1, -1, -1, -1, -1}, // 52

{ 2, 1, 10, 0, 5, 9, 0, 3, 5, 3, 7, 5, -1, -1, -1, -1}, // 53

{ 2, 0, 8, 5, 2, 8, 7, 5, 8, 2, 5, 10, -1, -1, -1, -1}, // 54

{ 5, 10, 2, 3, 5, 2, 7, 5, 3, -1, -1, -1, -1, -1, -1, -1}, // 55


{ 5, 9, 7, 9, 8, 7, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1}, // 56

{ 7, 5, 9, 2, 7, 9, 0, 2, 9, 11, 7, 2, -1, -1, -1, -1}, // 57

{11, 3, 2, 8, 1, 0, 8, 7, 1, 7, 5, 1, -1, -1, -1, -1}, // 58

{ 1, 2, 11, 7, 1, 11, 5, 1, 7, -1, -1, -1, -1, -1, -1, -1}, // 59


{ 8, 5, 9, 7, 5, 8, 3, 1, 10, 11, 3, 10, -1, -1, -1, -1}, // 60

{ 0, 7, 5, 9, 0, 5, 0, 11, 7, 10, 0, 1, 0, 10, 11, -1}, // 61

{ 0, 10, 11, 3, 0, 11, 0, 5, 10, 7, 0, 8, 0, 7, 5, -1}, // 62

{ 5, 10, 11, 5, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 63


{ 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 64

{ 3, 8, 0, 6, 10, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 65

{ 1, 0, 9, 6, 10, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 66

{ 3, 8, 1, 8, 9, 1, 6, 10, 5, -1, -1, -1, -1, -1, -1, -1}, // 67


{ 5, 6, 1, 1, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 68

{ 5, 6, 1, 6, 2, 1, 8, 0, 3, -1, -1, -1, -1, -1, -1, -1}, // 69

{ 5, 6, 9, 6, 0, 9, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1}, // 70

{ 8, 9, 5, 2, 8, 5, 6, 2, 5, 8, 2, 3, -1, -1, -1, -1}, // 71


{11, 3, 2, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 72

{ 8, 0, 11, 0, 2, 11, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1}, // 73

{ 9, 1, 0, 11, 3, 2, 6, 10, 5, -1, -1, -1, -1, -1, -1, -1}, // 74

{ 6, 10, 5, 2, 9, 1, 2, 11, 9, 11, 8, 9, -1, -1, -1, -1}, // 75


{11, 3, 6, 3, 5, 6, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1}, // 76

{11, 8, 0, 5, 11, 0, 1, 5, 0, 6, 11, 5, -1, -1, -1, -1}, // 77

{ 6, 11, 3, 6, 3, 0, 5, 6, 0, 9, 5, 0, -1, -1, -1, -1}, // 78

{ 9, 5, 6, 11, 9, 6, 8, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 79


{ 6, 10, 5, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 80

{ 0, 3, 4, 3, 7, 4, 10, 5, 6, -1, -1, -1, -1, -1, -1, -1}, // 81

{ 0, 9, 1, 6, 10, 5, 7, 4, 8, -1, -1, -1, -1, -1, -1, -1}, // 82

{ 5, 6, 10, 7, 9, 1, 3, 7, 1, 4, 9, 7, -1, -1, -1, -1}, // 83


{ 2, 1, 6, 1, 5, 6, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1}, // 84

{ 5, 2, 1, 6, 2, 5, 4, 0, 3, 7, 4, 3, -1, -1, -1, -1}, // 85

{ 7, 4, 8, 5, 0, 9, 5, 6, 0, 6, 2, 0, -1, -1, -1, -1}, // 86

{ 9, 3, 7, 4, 9, 7, 9, 2, 3, 6, 9, 5, 9, 6, 2, -1}, // 87


{ 2, 11, 3, 4, 8, 7, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1}, // 88

{ 6, 10, 5, 2, 7, 4, 0, 2, 4, 11, 7, 2, -1, -1, -1, -1}, // 89

{ 9, 1, 0, 8, 7, 4, 11, 3, 2, 6, 10, 5, -1, -1, -1, -1}, // 90

{ 1, 2, 9, 2, 11, 9, 11, 4, 9, 4, 11, 7, 6, 10, 5, -1}, // 91


{ 7, 4, 8, 5, 11, 3, 1, 5, 3, 6, 11, 5, -1, -1, -1, -1}, // 92

{11, 1, 5, 6, 11, 5, 11, 0, 1, 4, 11, 7, 11, 4, 0, -1}, // 93

{ 9, 5, 0, 5, 6, 0, 6, 3, 0, 3, 6, 11, 7, 4, 8, -1}, // 94

{ 9, 5, 6, 11, 9, 6, 9, 7, 4, 9, 11, 7, -1, -1, -1, -1}, // 95


{ 9, 4, 10, 10, 4, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 96

{ 6, 10, 4, 10, 9, 4, 3, 8, 0, -1, -1, -1, -1, -1, -1, -1}, // 97

{ 1, 0, 10, 0, 6, 10, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1}, // 98

{ 1, 3, 8, 6, 1, 8, 4, 6, 8, 10, 1, 6, -1, -1, -1, -1}, // 99


{ 9, 4, 1, 4, 2, 1, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1}, // 100

{ 8, 0, 3, 9, 2, 1, 9, 4, 2, 4, 6, 2, -1, -1, -1, -1}, // 101

{ 4, 2, 0, 6, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 102

{ 2, 3, 8, 4, 2, 8, 6, 2, 4, -1, -1, -1, -1, -1, -1, -1}, // 103


{ 9, 4, 10, 4, 6, 10, 3, 2, 11, -1, -1, -1, -1, -1, -1, -1}, // 104

{ 2, 8, 0, 11, 8, 2, 10, 9, 4, 6, 10, 4, -1, -1, -1, -1}, // 105

{ 2, 11, 3, 6, 1, 0, 4, 6, 0, 10, 1, 6, -1, -1, -1, -1}, // 106

{ 1, 4, 6, 10, 1, 6, 1, 8, 4, 11, 1, 2, 1, 11, 8, -1}, // 107


{ 4, 6, 9, 6, 3, 9, 3, 1, 9, 3, 6, 11, -1, -1, -1, -1}, // 108

{ 1, 11, 8, 0, 1, 8, 1, 6, 11, 4, 1, 9, 1, 4, 6, -1}, // 109

{ 6, 11, 3, 0, 6, 3, 4, 6, 0, -1, -1, -1, -1, -1, -1, -1}, // 110

{ 8, 4, 6, 8, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 111


{ 6, 10, 7, 10, 8, 7, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1}, // 112

{ 3, 7, 0, 7, 10, 0, 10, 9, 0, 10, 7, 6, -1, -1, -1, -1}, // 113

{ 7, 6, 10, 7, 10, 1, 8, 7, 1, 0, 8, 1, -1, -1, -1, -1}, // 114

{ 7, 6, 10, 1, 7, 10, 3, 7, 1, -1, -1, -1, -1, -1, -1, -1}, // 115


{ 6, 2, 1, 8, 6, 1, 9, 8, 1, 7, 6, 8, -1, -1, -1, -1}, // 116

{ 9, 6, 2, 1, 9, 2, 9, 7, 6, 3, 9, 0, 9, 3, 7, -1}, // 117

{ 0, 8, 7, 6, 0, 7, 2, 0, 6, -1, -1, -1, -1, -1, -1, -1}, // 118

{ 2, 3, 7, 2, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 119


{11, 3, 2, 8, 6, 10, 9, 8, 10, 7, 6, 8, -1, -1, -1, -1}, // 120

{ 7, 0, 2, 11, 7, 2, 7, 9, 0, 10, 7, 6, 7, 10, 9, -1}, // 121

{ 0, 8, 1, 8, 7, 1, 7, 10, 1, 10, 7, 6, 11, 3, 2, -1}, // 122

{ 1, 2, 11, 7, 1, 11, 1, 6, 10, 1, 7, 6, -1, -1, -1, -1}, // 123


{ 6, 9, 8, 7, 6, 8, 6, 1, 9, 3, 6, 11, 6, 3, 1, -1}, // 124

{ 1, 9, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 125

{ 0, 8, 7, 6, 0, 7, 0, 11, 3, 0, 6, 11, -1, -1, -1, -1}, // 126

{ 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 127


{11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 128

{ 8, 0, 3, 6, 7, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 129

{ 9, 1, 0, 6, 7, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 130

{ 9, 1, 8, 1, 3, 8, 6, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 131


{ 2, 1, 10, 7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 132

{10, 2, 1, 8, 0, 3, 7, 11, 6, -1, -1, -1, -1, -1, -1, -1}, // 133

{ 0, 9, 2, 9, 10, 2, 7, 11, 6, -1, -1, -1, -1, -1, -1, -1}, // 134

{ 7, 11, 6, 3, 10, 2, 3, 8, 10, 8, 9, 10, -1, -1, -1, -1}, // 135


{ 3, 2, 7, 7, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 136

{ 8, 0, 7, 0, 6, 7, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1}, // 137

{ 6, 7, 2, 7, 3, 2, 9, 1, 0, -1, -1, -1, -1, -1, -1, -1}, // 138

{ 2, 6, 1, 6, 8, 1, 8, 9, 1, 6, 7, 8, -1, -1, -1, -1}, // 139


{ 6, 7, 10, 7, 1, 10, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1}, // 140

{ 6, 7, 10, 10, 7, 1, 7, 8, 1, 8, 0, 1, -1, -1, -1, -1}, // 141

{ 7, 3, 0, 10, 7, 0, 9, 10, 0, 7, 10, 6, -1, -1, -1, -1}, // 142

{10, 6, 7, 8, 10, 7, 9, 10, 8, -1, -1, -1, -1, -1, -1, -1}, // 143


{ 4, 8, 6, 6, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 144

{11, 6, 3, 6, 0, 3, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1}, // 145

{11, 6, 8, 6, 4, 8, 1, 0, 9, -1, -1, -1, -1, -1, -1, -1}, // 146

{ 6, 4, 9, 3, 6, 9, 1, 3, 9, 6, 3, 11, -1, -1, -1, -1}, // 147


{ 4, 8, 6, 8, 11, 6, 1, 10, 2, -1, -1, -1, -1, -1, -1, -1}, // 148

{10, 2, 1, 11, 0, 3, 11, 6, 0, 6, 4, 0, -1, -1, -1, -1}, // 149

{ 8, 11, 4, 11, 6, 4, 9, 2, 0, 9, 10, 2, -1, -1, -1, -1}, // 150

{ 3, 9, 10, 2, 3, 10, 3, 4, 9, 6, 3, 11, 3, 6, 4, -1}, // 151


{ 3, 2, 8, 2, 4, 8, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1}, // 152

{ 2, 4, 0, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 153

{ 0, 9, 1, 4, 3, 2, 6, 4, 2, 8, 3, 4, -1, -1, -1, -1}, // 154

{ 4, 9, 1, 2, 4, 1, 6, 4, 2, -1, -1, -1, -1, -1, -1, -1}, // 155


{ 3, 1, 8, 1, 6, 8, 6, 4, 8, 1, 10, 6, -1, -1, -1, -1}, // 156

{ 0, 1, 10, 6, 0, 10, 4, 0, 6, -1, -1, -1, -1, -1, -1, -1}, // 157

{ 3, 6, 4, 8, 3, 4, 3, 10, 6, 9, 3, 0, 3, 9, 10, -1}, // 158

{ 4, 9, 10, 4, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 159


{ 5, 9, 4, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 160

{ 3, 8, 0, 5, 9, 4, 6, 7, 11, -1, -1, -1, -1, -1, -1, -1}, // 161

{ 1, 0, 5, 0, 4, 5, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1}, // 162

{ 6, 7, 11, 4, 3, 8, 4, 5, 3, 5, 1, 3, -1, -1, -1, -1}, // 163


{ 4, 5, 9, 2, 1, 10, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1}, // 164

{ 7, 11, 6, 10, 2, 1, 3, 8, 0, 5, 9, 4, -1, -1, -1, -1}, // 165

{11, 6, 7, 10, 4, 5, 10, 2, 4, 2, 0, 4, -1, -1, -1, -1}, // 166

{ 8, 4, 3, 4, 5, 3, 5, 2, 3, 2, 5, 10, 6, 7, 11, -1}, // 167


{ 3, 2, 7, 2, 6, 7, 9, 4, 5, -1, -1, -1, -1, -1, -1, -1}, // 168

{ 4, 5, 9, 6, 8, 0, 2, 6, 0, 7, 8, 6, -1, -1, -1, -1}, // 169

{ 2, 6, 3, 6, 7, 3, 0, 5, 1, 0, 4, 5, -1, -1, -1, -1}, // 170

{ 8, 2, 6, 7, 8, 6, 8, 1, 2, 5, 8, 4, 8, 5, 1, -1}, // 171


{ 4, 5, 9, 6, 1, 10, 6, 7, 1, 7, 3, 1, -1, -1, -1, -1}, // 172

{10, 6, 1, 6, 7, 1, 7, 0, 1, 0, 7, 8, 4, 5, 9, -1}, // 173

{10, 0, 4, 5, 10, 4, 10, 3, 0, 7, 10, 6, 10, 7, 3, -1}, // 174

{10, 6, 7, 8, 10, 7, 10, 4, 5, 10, 8, 4, -1, -1, -1, -1}, // 175


{ 5, 9, 6, 9, 11, 6, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1}, // 176

{11, 6, 3, 3, 6, 0, 6, 5, 0, 5, 9, 0, -1, -1, -1, -1}, // 177

{ 8, 11, 0, 11, 5, 0, 5, 1, 0, 11, 6, 5, -1, -1, -1, -1}, // 178

{ 3, 11, 6, 5, 3, 6, 1, 3, 5, -1, -1, -1, -1, -1, -1, -1}, // 179


{10, 2, 1, 11, 5, 9, 8, 11, 9, 6, 5, 11, -1, -1, -1, -1}, // 180

{ 3, 11, 0, 11, 6, 0, 6, 9, 0, 9, 6, 5, 10, 2, 1, -1}, // 181

{ 5, 8, 11, 6, 5, 11, 5, 0, 8, 2, 5, 10, 5, 2, 0, -1}, // 182

{ 3, 11, 6, 5, 3, 6, 3, 10, 2, 3, 5, 10, -1, -1, -1, -1}, // 183


{ 9, 8, 5, 8, 2, 5, 2, 6, 5, 2, 8, 3, -1, -1, -1, -1}, // 184

{ 6, 5, 9, 0, 6, 9, 2, 6, 0, -1, -1, -1, -1, -1, -1, -1}, // 185

{ 8, 5, 1, 0, 8, 1, 8, 6, 5, 2, 8, 3, 8, 2, 6, -1}, // 186

{ 6, 5, 1, 6, 1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 187


{ 6, 3, 1, 10, 6, 1, 6, 8, 3, 9, 6, 5, 6, 9, 8, -1}, // 188

{ 0, 1, 10, 6, 0, 10, 0, 5, 9, 0, 6, 5, -1, -1, -1, -1}, // 189

{ 8, 3, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 190

{ 6, 5, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 191


{10, 5, 11, 11, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 192

{10, 5, 11, 5, 7, 11, 0, 3, 8, -1, -1, -1, -1, -1, -1, -1}, // 193

{ 7, 11, 5, 11, 10, 5, 0, 9, 1, -1, -1, -1, -1, -1, -1, -1}, // 194

{ 5, 7, 10, 7, 11, 10, 1, 8, 9, 1, 3, 8, -1, -1, -1, -1}, // 195


{ 2, 1, 11, 1, 7, 11, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1}, // 196

{ 3, 8, 0, 7, 2, 1, 5, 7, 1, 11, 2, 7, -1, -1, -1, -1}, // 197

{ 5, 7, 9, 7, 2, 9, 2, 0, 9, 7, 11, 2, -1, -1, -1, -1}, // 198

{ 2, 5, 7, 11, 2, 7, 2, 9, 5, 8, 2, 3, 2, 8, 9, -1}, // 199


{10, 5, 2, 5, 3, 2, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1}, // 200

{ 0, 2, 8, 2, 5, 8, 5, 7, 8, 5, 2, 10, -1, -1, -1, -1}, // 201

{ 1, 0, 9, 3, 10, 5, 7, 3, 5, 2, 10, 3, -1, -1, -1, -1}, // 202

{ 2, 8, 9, 1, 2, 9, 2, 7, 8, 5, 2, 10, 2, 5, 7, -1}, // 203


{ 5, 3, 1, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 204

{ 7, 8, 0, 1, 7, 0, 5, 7, 1, -1, -1, -1, -1, -1, -1, -1}, // 205

{ 3, 0, 9, 5, 3, 9, 7, 3, 5, -1, -1, -1, -1, -1, -1, -1}, // 206

{ 7, 8, 9, 7, 9, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 207


{ 4, 8, 5, 8, 10, 5, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1}, // 208

{ 4, 0, 5, 0, 11, 5, 11, 10, 5, 0, 3, 11, -1, -1, -1, -1}, // 209

{ 9, 1, 0, 10, 4, 8, 11, 10, 8, 5, 4, 10, -1, -1, -1, -1}, // 210

{ 4, 11, 10, 5, 4, 10, 4, 3, 11, 1, 4, 9, 4, 1, 3, -1}, // 211


{ 1, 5, 2, 5, 8, 2, 8, 11, 2, 8, 5, 4, -1, -1, -1, -1}, // 212

{11, 4, 0, 3, 11, 0, 11, 5, 4, 1, 11, 2, 11, 1, 5, -1}, // 213

{ 5, 2, 0, 9, 5, 0, 5, 11, 2, 8, 5, 4, 5, 8, 11, -1}, // 214

{ 5, 4, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 215


{10, 5, 2, 2, 5, 3, 5, 4, 3, 4, 8, 3, -1, -1, -1, -1}, // 216

{ 2, 10, 5, 4, 2, 5, 0, 2, 4, -1, -1, -1, -1, -1, -1, -1}, // 217

{ 2, 10, 3, 10, 5, 3, 5, 8, 3, 8, 5, 4, 9, 1, 0, -1}, // 218

{ 2, 10, 5, 4, 2, 5, 2, 9, 1, 2, 4, 9, -1, -1, -1, -1}, // 219


{ 5, 4, 8, 3, 5, 8, 1, 5, 3, -1, -1, -1, -1, -1, -1, -1}, // 220

{ 5, 4, 0, 5, 0, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 221

{ 5, 4, 8, 3, 5, 8, 5, 0, 9, 5, 3, 0, -1, -1, -1, -1}, // 222

{ 5, 4, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 223


{ 7, 11, 4, 11, 9, 4, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1}, // 224

{ 3, 8, 0, 7, 9, 4, 7, 11, 9, 11, 10, 9, -1, -1, -1, -1}, // 225

{11, 10, 1, 4, 11, 1, 0, 4, 1, 11, 4, 7, -1, -1, -1, -1}, // 226

{ 4, 1, 3, 8, 4, 3, 4, 10, 1, 11, 4, 7, 4, 11, 10, -1}, // 227


{ 7, 11, 4, 4, 11, 9, 11, 2, 9, 2, 1, 9, -1, -1, -1, -1}, // 228

{ 4, 7, 9, 7, 11, 9, 11, 1, 9, 1, 11, 2, 3, 8, 0, -1}, // 229

{ 4, 7, 11, 2, 4, 11, 0, 4, 2, -1, -1, -1, -1, -1, -1, -1}, // 230

{ 4, 7, 11, 2, 4, 11, 4, 3, 8, 4, 2, 3, -1, -1, -1, -1}, // 231


{10, 9, 2, 9, 7, 2, 7, 3, 2, 9, 4, 7, -1, -1, -1, -1}, // 232

{ 7, 10, 9, 4, 7, 9, 7, 2, 10, 0, 7, 8, 7, 0, 2, -1}, // 233

{10, 7, 3, 2, 10, 3, 10, 4, 7, 0, 10, 1, 10, 0, 4, -1}, // 234

{ 2, 10, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 235


{ 1, 9, 4, 7, 1, 4, 3, 1, 7, -1, -1, -1, -1, -1, -1, -1}, // 236

{ 1, 9, 4, 7, 1, 4, 1, 8, 0, 1, 7, 8, -1, -1, -1, -1}, // 237

{ 3, 0, 4, 3, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 238

{ 7, 8, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 239


{ 8, 10, 9, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 240

{ 9, 0, 3, 11, 9, 3, 10, 9, 11, -1, -1, -1, -1, -1, -1, -1}, // 241

{10, 1, 0, 8, 10, 0, 11, 10, 8, -1, -1, -1, -1, -1, -1, -1}, // 242

{10, 1, 3, 10, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 243


{11, 2, 1, 9, 11, 1, 8, 11, 9, -1, -1, -1, -1, -1, -1, -1}, // 244

{ 9, 0, 3, 11, 9, 3, 9, 2, 1, 9, 11, 2, -1, -1, -1, -1}, // 245

{11, 2, 0, 11, 0, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 246

{11, 2, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 247


{ 8, 3, 2, 10, 8, 2, 9, 8, 10, -1, -1, -1, -1, -1, -1, -1}, // 248

{ 2, 10, 9, 2, 9, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 249

{ 8, 3, 2, 10, 8, 2, 8, 1, 0, 8, 10, 1, -1, -1, -1, -1}, // 250

{ 2, 10, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 251


{ 8, 3, 1, 8, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 252

{ 1, 9, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 253

{ 8, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 254

{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1} // 255

};


Hope it helps. If you have any other questions give me a yell. It''s been a while since I''ve been using this stuff, but I''ll see if I can help.

Phil



--
Philip Dunstan
Independent Game Developer
phil@philipdunstan.com
http://www.philipdunstan.com/

Share this post


Link to post
Share on other sites
Thanks for replying. I was beginning to think this topic would slip to page two with no replies...

I''ve set up functions to ''rotate'' my index values - swap bits around in a manner which preserves connectivity - so I should be able to find out which 14 states it uses. (I believe there are actually 16 states, but two of them are trivial - not intersecting the surface - so you''re still right).

The thing I don''t understand is, how do I use those tables?

My best guess is: I interpolate each edge to build vertices (where the density values on an edge are either side of the threshold), and then look the index up in the table to see which order I connect the vertices in?

In that case, how do I know which edge corresponds to which number?

Thanks again for your first reply, and thanks in advance for your second...

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.

Share this post


Link to post
Share on other sites
Sorry , I should have added that bit of info.

I assume you have read the Lorensen and Cline paper. If you haven''t do so. They came up with the whole thing.
quote:
Lorensen, W.E. and Cline, H.E., "Marching Cubes: a high resolution 3D surface reconstruction algorithm," Computer Graphics, Vol. 21, No. 4, pp 163-169 (Proc. of SIGGRAPH), 1987. Watt, Alan, and Watt, Mark, Advanced Animation and Rendering Techniques, Addison-Wesley, 1992


Each vertex is numbered from 1-8 and each vertex is 1-12. The order isn''t too important, as long as it matches your lookup tables. I think I used

vertex 0 (0, 0, 0)
1 (1, 0, 0)
2 (1, 1, 0)
3 (0, 1, 0)
4 (0, 0, 1)
5 (1, 0, 1)
6 (1, 1, 1)
7 (0, 1, 1)

And then
edge 0 = vertices 0 & 1
1 = vertices 1 & 2
2 = vertices 2 & 3
3 = vertices 3 & 0
4 = vertices 4 & 5
5 = vertices 5 & 6
6 = vertices 6 & 7
7 = vertices 7 & 4
8 = vertices 0 & 4
9 = vertices 1 & 5
10 = vertices 2 & 6
11 = vertices 3 & 7

Sorry I didn''t have time to draw a pic, but as I said, the order isn''t important as long as it matches your lookup.


If I have the index 1, I use my edge lookup to determine that edges 0, 1, 2, 3, 8 and 10 were interesected. I find the intersection point on each of these edges (fairly simple interpolation). I then use the vertices lookup table to see that 2 triangles were created. The first triangle is made from the intersection points of edges 3, 8 and 0. The second triangle is made with the points from edges 10, 2 and 1.

Hope that is a little clearer.

There is a lot of stuff in google about Marching Cubes. You should be able to find a picture without too much trouble.

Phil

--
Philip Dunstan
Independent Game Developer
phil@philipdunstan.com
http://www.philipdunstan.com/

Share this post


Link to post
Share on other sites
Thank you very much. I did try google initially, but most of the information is university-level CS stuff - a little bit beyond me.

I''ll try this out tonight and see how it goes, but it makes sense in my head now.

Thanks again.

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!