Pileus Git - grits/blob - src/objects/marching.c

   1 /**
   2  * Copyright (C) 2002 Jamie Zawinski <jwz@jwz.org>
   3  * Copyright (C) 2009-2010 Andy Spencer <andy753421@gmail.com>
   4  *
   5  * Utility functions to create "marching cubes" meshes from 3d fields.
   6  *
   7  * Permission to use, copy, modify, distribute, and sell this software and its
   8  * documentation for any purpose is hereby granted without fee, provided that
   9  * the above copyright notice appear in all copies and that both that
  10  * copyright notice and this permission notice appear in supporting
  11  * documentation.  No representations are made about the suitability of this
  12  * software for any purpose.  It is provided "as is" without express or
  13  * implied warranty.
  14  *
  15  * Marching cubes implementation by Paul Bourke <pbourke@swin.edu.au>
  16  * http://astronomy.swin.edu.au/~pbourke/modelling/polygonise/
  17  */
  18
  19 #include <math.h>
  20 #include <glib.h>
  21 #include <string.h>
  22
  23 #include "grits-util.h"
  24 #include "marching.h"
  25
  26 /**
  27  * Indexing convention:
  28  *
  29  *           Vertices:                    Edges:
  30  *
  31  *        4  ______________ 5           ______________
  32  *         /|            /|           /|     4      /|
  33  *        / |         6 / |       7  / |8        5 / |
  34  *    7  /_____________/  |        /______________/  | 9
  35  *      |   |         |   |        |   |   6     |   |
  36  *      | 0 |_________|___| 1      |   |_________|10_|
  37  *      |  /          |  /      11 | 3/     0    |  /
  38  *      | /           | /          | /           | / 1
  39  *    3 |/____________|/ 2         |/____________|/
  40  *                                        2
  41  */
  42
  43 static const int edge_table[256] = {
  44         0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
  45         0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
  46         0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
  47         0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
  48         0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
  49         0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
  50         0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
  51         0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
  52         0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
  53         0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
  54         0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
  55         0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
  56         0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
  57         0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
  58         0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
  59         0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
  60         0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
  61         0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
  62         0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
  63         0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
  64         0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
  65         0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
  66         0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
  67         0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
  68         0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
  69         0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
  70         0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
  71         0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
  72         0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
  73         0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
  74         0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
  75         0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0
  76 };
  77
  78 static const int tri_table[256][16] = {
  79         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  80         { 0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  81         { 0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  82         { 1,  8,  3,  9,  8,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  83         { 1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  84         { 0,  8,  3,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  85         { 9,  2, 10,  0,  2,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  86         { 2,  8,  3,  2, 10,  8, 10,  9,  8, -1, -1, -1, -1, -1, -1, -1},
  87         { 3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  88         { 0, 11,  2,  8, 11,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  89         { 1,  9,  0,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  90         { 1, 11,  2,  1,  9, 11,  9,  8, 11, -1, -1, -1, -1, -1, -1, -1},
  91         { 3, 10,  1, 11, 10,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  92         { 0, 10,  1,  0,  8, 10,  8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
  93         { 3,  9,  0,  3, 11,  9, 11, 10,  9, -1, -1, -1, -1, -1, -1, -1},
  94         { 9,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  95         { 4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  96         { 4,  3,  0,  7,  3,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  97         { 0,  1,  9,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  98         { 4,  1,  9,  4,  7,  1,  7,  3,  1, -1, -1, -1, -1, -1, -1, -1},
  99         { 1,  2, 10,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 100         { 3,  4,  7,  3,  0,  4,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1},
 101         { 9,  2, 10,  9,  0,  2,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1},
 102         { 2, 10,  9,  2,  9,  7,  2,  7,  3,  7,  9,  4, -1, -1, -1, -1},
 103         { 8,  4,  7,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 104         {11,  4,  7, 11,  2,  4,  2,  0,  4, -1, -1, -1, -1, -1, -1, -1},
 105         { 9,  0,  1,  8,  4,  7,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1},
 106         { 4,  7, 11,  9,  4, 11,  9, 11,  2,  9,  2,  1, -1, -1, -1, -1},
 107         { 3, 10,  1,  3, 11, 10,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1},
 108         { 1, 11, 10,  1,  4, 11,  1,  0,  4,  7, 11,  4, -1, -1, -1, -1},
 109         { 4,  7,  8,  9,  0, 11,  9, 11, 10, 11,  0,  3, -1, -1, -1, -1},
 110         { 4,  7, 11,  4, 11,  9,  9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
 111         { 9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 112         { 9,  5,  4,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 113         { 0,  5,  4,  1,  5,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 114         { 8,  5,  4,  8,  3,  5,  3,  1,  5, -1, -1, -1, -1, -1, -1, -1},
 115         { 1,  2, 10,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 116         { 3,  0,  8,  1,  2, 10,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1},
 117         { 5,  2, 10,  5,  4,  2,  4,  0,  2, -1, -1, -1, -1, -1, -1, -1},
 118         { 2, 10,  5,  3,  2,  5,  3,  5,  4,  3,  4,  8, -1, -1, -1, -1},
 119         { 9,  5,  4,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 120         { 0, 11,  2,  0,  8, 11,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1},
 121         { 0,  5,  4,  0,  1,  5,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1},
 122         { 2,  1,  5,  2,  5,  8,  2,  8, 11,  4,  8,  5, -1, -1, -1, -1},
 123         {10,  3, 11, 10,  1,  3,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1},
 124         { 4,  9,  5,  0,  8,  1,  8, 10,  1,  8, 11, 10, -1, -1, -1, -1},
 125         { 5,  4,  0,  5,  0, 11,  5, 11, 10, 11,  0,  3, -1, -1, -1, -1},
 126         { 5,  4,  8,  5,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1},
 127         { 9,  7,  8,  5,  7,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 128         { 9,  3,  0,  9,  5,  3,  5,  7,  3, -1, -1, -1, -1, -1, -1, -1},
 129         { 0,  7,  8,  0,  1,  7,  1,  5,  7, -1, -1, -1, -1, -1, -1, -1},
 130         { 1,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 131         { 9,  7,  8,  9,  5,  7, 10,  1,  2, -1, -1, -1, -1, -1, -1, -1},
 132         {10,  1,  2,  9,  5,  0,  5,  3,  0,  5,  7,  3, -1, -1, -1, -1},
 133         { 8,  0,  2,  8,  2,  5,  8,  5,  7, 10,  5,  2, -1, -1, -1, -1},
 134         { 2, 10,  5,  2,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1},
 135         { 7,  9,  5,  7,  8,  9,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1},
 136         { 9,  5,  7,  9,  7,  2,  9,  2,  0,  2,  7, 11, -1, -1, -1, -1},
 137         { 2,  3, 11,  0,  1,  8,  1,  7,  8,  1,  5,  7, -1, -1, -1, -1},
 138         {11,  2,  1, 11,  1,  7,  7,  1,  5, -1, -1, -1, -1, -1, -1, -1},
 139         { 9,  5,  8,  8,  5,  7, 10,  1,  3, 10,  3, 11, -1, -1, -1, -1},
 140         { 5,  7,  0,  5,  0,  9,  7, 11,  0,  1,  0, 10, 11, 10,  0, -1},
 141         {11, 10,  0, 11,  0,  3, 10,  5,  0,  8,  0,  7,  5,  7,  0, -1},
 142         {11, 10,  5,  7, 11,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 143         {10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 144         { 0,  8,  3,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 145         { 9,  0,  1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 146         { 1,  8,  3,  1,  9,  8,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1},
 147         { 1,  6,  5,  2,  6,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 148         { 1,  6,  5,  1,  2,  6,  3,  0,  8, -1, -1, -1, -1, -1, -1, -1},
 149         { 9,  6,  5,  9,  0,  6,  0,  2,  6, -1, -1, -1, -1, -1, -1, -1},
 150         { 5,  9,  8,  5,  8,  2,  5,  2,  6,  3,  2,  8, -1, -1, -1, -1},
 151         { 2,  3, 11, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 152         {11,  0,  8, 11,  2,  0, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1},
 153         { 0,  1,  9,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1},
 154         { 5, 10,  6,  1,  9,  2,  9, 11,  2,  9,  8, 11, -1, -1, -1, -1},
 155         { 6,  3, 11,  6,  5,  3,  5,  1,  3, -1, -1, -1, -1, -1, -1, -1},
 156         { 0,  8, 11,  0, 11,  5,  0,  5,  1,  5, 11,  6, -1, -1, -1, -1},
 157         { 3, 11,  6,  0,  3,  6,  0,  6,  5,  0,  5,  9, -1, -1, -1, -1},
 158         { 6,  5,  9,  6,  9, 11, 11,  9,  8, -1, -1, -1, -1, -1, -1, -1},
 159         { 5, 10,  6,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 160         { 4,  3,  0,  4,  7,  3,  6,  5, 10, -1, -1, -1, -1, -1, -1, -1},
 161         { 1,  9,  0,  5, 10,  6,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1},
 162         {10,  6,  5,  1,  9,  7,  1,  7,  3,  7,  9,  4, -1, -1, -1, -1},
 163         { 6,  1,  2,  6,  5,  1,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1},
 164         { 1,  2,  5,  5,  2,  6,  3,  0,  4,  3,  4,  7, -1, -1, -1, -1},
 165         { 8,  4,  7,  9,  0,  5,  0,  6,  5,  0,  2,  6, -1, -1, -1, -1},
 166         { 7,  3,  9,  7,  9,  4,  3,  2,  9,  5,  9,  6,  2,  6,  9, -1},
 167         { 3, 11,  2,  7,  8,  4, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1},
 168         { 5, 10,  6,  4,  7,  2,  4,  2,  0,  2,  7, 11, -1, -1, -1, -1},
 169         { 0,  1,  9,  4,  7,  8,  2,  3, 11,  5, 10,  6, -1, -1, -1, -1},
 170         { 9,  2,  1,  9, 11,  2,  9,  4, 11,  7, 11,  4,  5, 10,  6, -1},
 171         { 8,  4,  7,  3, 11,  5,  3,  5,  1,  5, 11,  6, -1, -1, -1, -1},
 172         { 5,  1, 11,  5, 11,  6,  1,  0, 11,  7, 11,  4,  0,  4, 11, -1},
 173         { 0,  5,  9,  0,  6,  5,  0,  3,  6, 11,  6,  3,  8,  4,  7, -1},
 174         { 6,  5,  9,  6,  9, 11,  4,  7,  9,  7, 11,  9, -1, -1, -1, -1},
 175         {10,  4,  9,  6,  4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 176         { 4, 10,  6,  4,  9, 10,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1},
 177         {10,  0,  1, 10,  6,  0,  6,  4,  0, -1, -1, -1, -1, -1, -1, -1},
 178         { 8,  3,  1,  8,  1,  6,  8,  6,  4,  6,  1, 10, -1, -1, -1, -1},
 179         { 1,  4,  9,  1,  2,  4,  2,  6,  4, -1, -1, -1, -1, -1, -1, -1},
 180         { 3,  0,  8,  1,  2,  9,  2,  4,  9,  2,  6,  4, -1, -1, -1, -1},
 181         { 0,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 182         { 8,  3,  2,  8,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1},
 183         {10,  4,  9, 10,  6,  4, 11,  2,  3, -1, -1, -1, -1, -1, -1, -1},
 184         { 0,  8,  2,  2,  8, 11,  4,  9, 10,  4, 10,  6, -1, -1, -1, -1},
 185         { 3, 11,  2,  0,  1,  6,  0,  6,  4,  6,  1, 10, -1, -1, -1, -1},
 186         { 6,  4,  1,  6,  1, 10,  4,  8,  1,  2,  1, 11,  8, 11,  1, -1},
 187         { 9,  6,  4,  9,  3,  6,  9,  1,  3, 11,  6,  3, -1, -1, -1, -1},
 188         { 8, 11,  1,  8,  1,  0, 11,  6,  1,  9,  1,  4,  6,  4,  1, -1},
 189         { 3, 11,  6,  3,  6,  0,  0,  6,  4, -1, -1, -1, -1, -1, -1, -1},
 190         { 6,  4,  8, 11,  6,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 191         { 7, 10,  6,  7,  8, 10,  8,  9, 10, -1, -1, -1, -1, -1, -1, -1},
 192         { 0,  7,  3,  0, 10,  7,  0,  9, 10,  6,  7, 10, -1, -1, -1, -1},
 193         {10,  6,  7,  1, 10,  7,  1,  7,  8,  1,  8,  0, -1, -1, -1, -1},
 194         {10,  6,  7, 10,  7,  1,  1,  7,  3, -1, -1, -1, -1, -1, -1, -1},
 195         { 1,  2,  6,  1,  6,  8,  1,  8,  9,  8,  6,  7, -1, -1, -1, -1},
 196         { 2,  6,  9,  2,  9,  1,  6,  7,  9,  0,  9,  3,  7,  3,  9, -1},
 197         { 7,  8,  0,  7,  0,  6,  6,  0,  2, -1, -1, -1, -1, -1, -1, -1},
 198         { 7,  3,  2,  6,  7,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 199         { 2,  3, 11, 10,  6,  8, 10,  8,  9,  8,  6,  7, -1, -1, -1, -1},
 200         { 2,  0,  7,  2,  7, 11,  0,  9,  7,  6,  7, 10,  9, 10,  7, -1},
 201         { 1,  8,  0,  1,  7,  8,  1, 10,  7,  6,  7, 10,  2,  3, 11, -1},
 202         {11,  2,  1, 11,  1,  7, 10,  6,  1,  6,  7,  1, -1, -1, -1, -1},
 203         { 8,  9,  6,  8,  6,  7,  9,  1,  6, 11,  6,  3,  1,  3,  6, -1},
 204         { 0,  9,  1, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 205         { 7,  8,  0,  7,  0,  6,  3, 11,  0, 11,  6,  0, -1, -1, -1, -1},
 206         { 7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 207         { 7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 208         { 3,  0,  8, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 209         { 0,  1,  9, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 210         { 8,  1,  9,  8,  3,  1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1},
 211         {10,  1,  2,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 212         { 1,  2, 10,  3,  0,  8,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1},
 213         { 2,  9,  0,  2, 10,  9,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1},
 214         { 6, 11,  7,  2, 10,  3, 10,  8,  3, 10,  9,  8, -1, -1, -1, -1},
 215         { 7,  2,  3,  6,  2,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 216         { 7,  0,  8,  7,  6,  0,  6,  2,  0, -1, -1, -1, -1, -1, -1, -1},
 217         { 2,  7,  6,  2,  3,  7,  0,  1,  9, -1, -1, -1, -1, -1, -1, -1},
 218         { 1,  6,  2,  1,  8,  6,  1,  9,  8,  8,  7,  6, -1, -1, -1, -1},
 219         {10,  7,  6, 10,  1,  7,  1,  3,  7, -1, -1, -1, -1, -1, -1, -1},
 220         {10,  7,  6,  1,  7, 10,  1,  8,  7,  1,  0,  8, -1, -1, -1, -1},
 221         { 0,  3,  7,  0,  7, 10,  0, 10,  9,  6, 10,  7, -1, -1, -1, -1},
 222         { 7,  6, 10,  7, 10,  8,  8, 10,  9, -1, -1, -1, -1, -1, -1, -1},
 223         { 6,  8,  4, 11,  8,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 224         { 3,  6, 11,  3,  0,  6,  0,  4,  6, -1, -1, -1, -1, -1, -1, -1},
 225         { 8,  6, 11,  8,  4,  6,  9,  0,  1, -1, -1, -1, -1, -1, -1, -1},
 226         { 9,  4,  6,  9,  6,  3,  9,  3,  1, 11,  3,  6, -1, -1, -1, -1},
 227         { 6,  8,  4,  6, 11,  8,  2, 10,  1, -1, -1, -1, -1, -1, -1, -1},
 228         { 1,  2, 10,  3,  0, 11,  0,  6, 11,  0,  4,  6, -1, -1, -1, -1},
 229         { 4, 11,  8,  4,  6, 11,  0,  2,  9,  2, 10,  9, -1, -1, -1, -1},
 230         {10,  9,  3, 10,  3,  2,  9,  4,  3, 11,  3,  6,  4,  6,  3, -1},
 231         { 8,  2,  3,  8,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1},
 232         { 0,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 233         { 1,  9,  0,  2,  3,  4,  2,  4,  6,  4,  3,  8, -1, -1, -1, -1},
 234         { 1,  9,  4,  1,  4,  2,  2,  4,  6, -1, -1, -1, -1, -1, -1, -1},
 235         { 8,  1,  3,  8,  6,  1,  8,  4,  6,  6, 10,  1, -1, -1, -1, -1},
 236         {10,  1,  0, 10,  0,  6,  6,  0,  4, -1, -1, -1, -1, -1, -1, -1},
 237         { 4,  6,  3,  4,  3,  8,  6, 10,  3,  0,  3,  9, 10,  9,  3, -1},
 238         {10,  9,  4,  6, 10,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 239         { 4,  9,  5,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 240         { 0,  8,  3,  4,  9,  5, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1},
 241         { 5,  0,  1,  5,  4,  0,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1},
 242         {11,  7,  6,  8,  3,  4,  3,  5,  4,  3,  1,  5, -1, -1, -1, -1},
 243         { 9,  5,  4, 10,  1,  2,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1},
 244         { 6, 11,  7,  1,  2, 10,  0,  8,  3,  4,  9,  5, -1, -1, -1, -1},
 245         { 7,  6, 11,  5,  4, 10,  4,  2, 10,  4,  0,  2, -1, -1, -1, -1},
 246         { 3,  4,  8,  3,  5,  4,  3,  2,  5, 10,  5,  2, 11,  7,  6, -1},
 247         { 7,  2,  3,  7,  6,  2,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1},
 248         { 9,  5,  4,  0,  8,  6,  0,  6,  2,  6,  8,  7, -1, -1, -1, -1},
 249         { 3,  6,  2,  3,  7,  6,  1,  5,  0,  5,  4,  0, -1, -1, -1, -1},
 250         { 6,  2,  8,  6,  8,  7,  2,  1,  8,  4,  8,  5,  1,  5,  8, -1},
 251         { 9,  5,  4, 10,  1,  6,  1,  7,  6,  1,  3,  7, -1, -1, -1, -1},
 252         { 1,  6, 10,  1,  7,  6,  1,  0,  7,  8,  7,  0,  9,  5,  4, -1},
 253         { 4,  0, 10,  4, 10,  5,  0,  3, 10,  6, 10,  7,  3,  7, 10, -1},
 254         { 7,  6, 10,  7, 10,  8,  5,  4, 10,  4,  8, 10, -1, -1, -1, -1},
 255         { 6,  9,  5,  6, 11,  9, 11,  8,  9, -1, -1, -1, -1, -1, -1, -1},
 256         { 3,  6, 11,  0,  6,  3,  0,  5,  6,  0,  9,  5, -1, -1, -1, -1},
 257         { 0, 11,  8,  0,  5, 11,  0,  1,  5,  5,  6, 11, -1, -1, -1, -1},
 258         { 6, 11,  3,  6,  3,  5,  5,  3,  1, -1, -1, -1, -1, -1, -1, -1},
 259         { 1,  2, 10,  9,  5, 11,  9, 11,  8, 11,  5,  6, -1, -1, -1, -1},
 260         { 0, 11,  3,  0,  6, 11,  0,  9,  6,  5,  6,  9,  1,  2, 10, -1},
 261         {11,  8,  5, 11,  5,  6,  8,  0,  5, 10,  5,  2,  0,  2,  5, -1},
 262         { 6, 11,  3,  6,  3,  5,  2, 10,  3, 10,  5,  3, -1, -1, -1, -1},
 263         { 5,  8,  9,  5,  2,  8,  5,  6,  2,  3,  8,  2, -1, -1, -1, -1},
 264         { 9,  5,  6,  9,  6,  0,  0,  6,  2, -1, -1, -1, -1, -1, -1, -1},
 265         { 1,  5,  8,  1,  8,  0,  5,  6,  8,  3,  8,  2,  6,  2,  8, -1},
 266         { 1,  5,  6,  2,  1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 267         { 1,  3,  6,  1,  6, 10,  3,  8,  6,  5,  6,  9,  8,  9,  6, -1},
 268         {10,  1,  0, 10,  0,  6,  9,  5,  0,  5,  6,  0, -1, -1, -1, -1},
 269         { 0,  3,  8,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 270         {10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 271         {11,  5, 10,  7,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 272         {11,  5, 10, 11,  7,  5,  8,  3,  0, -1, -1, -1, -1, -1, -1, -1},
 273         { 5, 11,  7,  5, 10, 11,  1,  9,  0, -1, -1, -1, -1, -1, -1, -1},
 274         {10,  7,  5, 10, 11,  7,  9,  8,  1,  8,  3,  1, -1, -1, -1, -1},
 275         {11,  1,  2, 11,  7,  1,  7,  5,  1, -1, -1, -1, -1, -1, -1, -1},
 276         { 0,  8,  3,  1,  2,  7,  1,  7,  5,  7,  2, 11, -1, -1, -1, -1},
 277         { 9,  7,  5,  9,  2,  7,  9,  0,  2,  2, 11,  7, -1, -1, -1, -1},
 278         { 7,  5,  2,  7,  2, 11,  5,  9,  2,  3,  2,  8,  9,  8,  2, -1},
 279         { 2,  5, 10,  2,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1},
 280         { 8,  2,  0,  8,  5,  2,  8,  7,  5, 10,  2,  5, -1, -1, -1, -1},
 281         { 9,  0,  1,  5, 10,  3,  5,  3,  7,  3, 10,  2, -1, -1, -1, -1},
 282         { 9,  8,  2,  9,  2,  1,  8,  7,  2, 10,  2,  5,  7,  5,  2, -1},
 283         { 1,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 284         { 0,  8,  7,  0,  7,  1,  1,  7,  5, -1, -1, -1, -1, -1, -1, -1},
 285         { 9,  0,  3,  9,  3,  5,  5,  3,  7, -1, -1, -1, -1, -1, -1, -1},
 286         { 9,  8,  7,  5,  9,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 287         { 5,  8,  4,  5, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1},
 288         { 5,  0,  4,  5, 11,  0,  5, 10, 11, 11,  3,  0, -1, -1, -1, -1},
 289         { 0,  1,  9,  8,  4, 10,  8, 10, 11, 10,  4,  5, -1, -1, -1, -1},
 290         {10, 11,  4, 10,  4,  5, 11,  3,  4,  9,  4,  1,  3,  1,  4, -1},
 291         { 2,  5,  1,  2,  8,  5,  2, 11,  8,  4,  5,  8, -1, -1, -1, -1},
 292         { 0,  4, 11,  0, 11,  3,  4,  5, 11,  2, 11,  1,  5,  1, 11, -1},
 293         { 0,  2,  5,  0,  5,  9,  2, 11,  5,  4,  5,  8, 11,  8,  5, -1},
 294         { 9,  4,  5,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 295         { 2,  5, 10,  3,  5,  2,  3,  4,  5,  3,  8,  4, -1, -1, -1, -1},
 296         { 5, 10,  2,  5,  2,  4,  4,  2,  0, -1, -1, -1, -1, -1, -1, -1},
 297         { 3, 10,  2,  3,  5, 10,  3,  8,  5,  4,  5,  8,  0,  1,  9, -1},
 298         { 5, 10,  2,  5,  2,  4,  1,  9,  2,  9,  4,  2, -1, -1, -1, -1},
 299         { 8,  4,  5,  8,  5,  3,  3,  5,  1, -1, -1, -1, -1, -1, -1, -1},
 300         { 0,  4,  5,  1,  0,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 301         { 8,  4,  5,  8,  5,  3,  9,  0,  5,  0,  3,  5, -1, -1, -1, -1},
 302         { 9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 303         { 4, 11,  7,  4,  9, 11,  9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 304         { 0,  8,  3,  4,  9,  7,  9, 11,  7,  9, 10, 11, -1, -1, -1, -1},
 305         { 1, 10, 11,  1, 11,  4,  1,  4,  0,  7,  4, 11, -1, -1, -1, -1},
 306         { 3,  1,  4,  3,  4,  8,  1, 10,  4,  7,  4, 11, 10, 11,  4, -1},
 307         { 4, 11,  7,  9, 11,  4,  9,  2, 11,  9,  1,  2, -1, -1, -1, -1},
 308         { 9,  7,  4,  9, 11,  7,  9,  1, 11,  2, 11,  1,  0,  8,  3, -1},
 309         {11,  7,  4, 11,  4,  2,  2,  4,  0, -1, -1, -1, -1, -1, -1, -1},
 310         {11,  7,  4, 11,  4,  2,  8,  3,  4,  3,  2,  4, -1, -1, -1, -1},
 311         { 2,  9, 10,  2,  7,  9,  2,  3,  7,  7,  4,  9, -1, -1, -1, -1},
 312         { 9, 10,  7,  9,  7,  4, 10,  2,  7,  8,  7,  0,  2,  0,  7, -1},
 313         { 3,  7, 10,  3, 10,  2,  7,  4, 10,  1, 10,  0,  4,  0, 10, -1},
 314         { 1, 10,  2,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 315         { 4,  9,  1,  4,  1,  7,  7,  1,  3, -1, -1, -1, -1, -1, -1, -1},
 316         { 4,  9,  1,  4,  1,  7,  0,  8,  1,  8,  7,  1, -1, -1, -1, -1},
 317         { 4,  0,  3,  7,  4,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 318         { 4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 319         { 9, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 320         { 3,  0,  9,  3,  9, 11, 11,  9, 10, -1, -1, -1, -1, -1, -1, -1},
 321         { 0,  1, 10,  0, 10,  8,  8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 322         { 3,  1, 10, 11,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 323         { 1,  2, 11,  1, 11,  9,  9, 11,  8, -1, -1, -1, -1, -1, -1, -1},
 324         { 3,  0,  9,  3,  9, 11,  1,  2,  9,  2, 11,  9, -1, -1, -1, -1},
 325         { 0,  2, 11,  8,  0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 326         { 3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 327         { 2,  3,  8,  2,  8, 10, 10,  8,  9, -1, -1, -1, -1, -1, -1, -1},
 328         { 9, 10,  2,  0,  9,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 329         { 2,  3,  8,  2,  8, 10,  0,  1,  8,  1, 10,  8, -1, -1, -1, -1},
 330         { 1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 331         { 1,  3,  8,  9,  1,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 332         { 0,  9,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 333         { 0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 334         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
 335 };
 336
 337 static void do_normals(VolTriangle *tri)
 338 {
 339         /* Triangle normal */
 340         crossd3((gdouble*)tri->v[0],
 341                         (gdouble*)tri->v[1],
 342                         (gdouble*)tri->v[2],
 343                         (gdouble*)&tri->norm);
 344
 345         double mag = sqrt(tri->norm.x*tri->norm.x +
 346                           tri->norm.y*tri->norm.y +
 347                           tri->norm.z*tri->norm.z);
 348         if (mag == 0)
 349                 return; // wtf
 350
 351         /* Vertex normal */
 352         for (int vi = 0; vi < 3; vi++) {
 353                 double *tri_norm  = (double*)&tri->norm;
 354                 double *vert_norm = (double*)&tri->v[vi]->norm;
 355                 for (int i = 0; i < 3; i++)
 356                         vert_norm[i] += tri_norm[i]/mag/mag;
 357         }
 358 }
 359
 360 /* Linearly interpolate the position where an isosurface cuts
 361  * an edge between two vertices, each with their own scalar value
 362  */
 363 gdouble dist = 0;
 364 static VolVertex *interp_vertex(
 365                 VolPoint *p1, VolVertex *v, VolPoint *p2, double level)
 366 {
 367         dist = 0;
 368
 369         /* caching */
 370         if (v) return v;
 371
 372         /* Invalid values */
 373         if (isnan(p1->value)) level = p2->value;
 374         if (isnan(p2->value)) level = p1->value;
 375
 376         /* Debug */
 377         dist = distd((gdouble*)p1, (gdouble*)p2);
 378
 379         double mu = (level - p1->value) / (p2->value - p1->value);
 380         v = g_new0(VolVertex, 1);
 381         //v->c.x = (p2->c.x + p1->c.x)/2;
 382         //v->c.y = (p2->c.y + p1->c.y)/2;
 383         //v->c.z = (p2->c.z + p1->c.z)/2;
 384         v->c.x = p1->c.x + mu * (p2->c.x - p1->c.x);
 385         v->c.y = p1->c.y + mu * (p2->c.y - p1->c.y);
 386         v->c.z = p1->c.z + mu * (p2->c.z - p1->c.z);
 387         return v;
 388 }
 389
 390
 391 /**
 392  * By Paul Bourke <pbourke@swin.edu.au>
 393  * Modified by Andy Spencer <andy753421@gmail.com>
 394  */
 395 GList *march_one_cube(VolCell *cell, double level)
 396 {
 397         VolPoint  **c = cell->corner;
 398         VolVertex **e = cell->edge;
 399
 400         /* Determine the index into the edge table which
 401          * tells us which vertices are inside of the surface */
 402         int ci = 0;
 403         for (int i = 0; i < 8; i++)
 404                 if (c[i]->value < level || isnan(c[i]->value))
 405                         ci |= 1 << i;
 406
 407         /* Cube is entirely in/out of the surface */
 408         if (edge_table[ci] == 0)
 409                 return 0;
 410
 411         /* Find the vertices where the surface intersects the cube */
 412         if (edge_table[ci] & 1<<0 ) e[0 ] = interp_vertex(c[0], e[0 ], c[1], level);
 413         if (edge_table[ci] & 1<<1 ) e[1 ] = interp_vertex(c[1], e[1 ], c[2], level);
 414         if (edge_table[ci] & 1<<2 ) e[2 ] = interp_vertex(c[2], e[2 ], c[3], level);
 415         if (edge_table[ci] & 1<<3 ) e[3 ] = interp_vertex(c[3], e[3 ], c[0], level);
 416         if (edge_table[ci] & 1<<4 ) e[4 ] = interp_vertex(c[4], e[4 ], c[5], level);
 417         if (edge_table[ci] & 1<<5 ) e[5 ] = interp_vertex(c[5], e[5 ], c[6], level);
 418         if (edge_table[ci] & 1<<6 ) e[6 ] = interp_vertex(c[6], e[6 ], c[7], level);
 419         if (edge_table[ci] & 1<<7 ) e[7 ] = interp_vertex(c[7], e[7 ], c[4], level);
 420         if (edge_table[ci] & 1<<8 ) e[8 ] = interp_vertex(c[0], e[8 ], c[4], level);
 421         if (edge_table[ci] & 1<<9 ) e[9 ] = interp_vertex(c[1], e[9 ], c[5], level);
 422         if (edge_table[ci] & 1<<10) e[10] = interp_vertex(c[2], e[10], c[6], level);
 423         if (edge_table[ci] & 1<<11) e[11] = interp_vertex(c[3], e[11], c[7], level);
 424
 425         /* Create the triangle */
 426         GList *tris = NULL;
 427         for (int i = 0; tri_table[ci][i] != -1; i += 3) {
 428                 VolTriangle *tri = g_new0(VolTriangle, 1);
 429                 /* Use z,y,z */
 430                 tri->v[2] = e[tri_table[ci][i+0]];
 431                 tri->v[1] = e[tri_table[ci][i+1]];
 432                 tri->v[0] = e[tri_table[ci][i+2]];
 433                 tri->v[2]->tris++;
 434                 tri->v[1]->tris++;
 435                 tri->v[0]->tris++;
 436                 do_normals(tri);
 437                 tris = g_list_prepend(tris, tri);
 438         }
 439         return tris;
 440 }
 441
 442 /* Find triangles along an isosurface in a grid of points */
 443 //GList *marching_cubes_simple(VolGrid *grid, double level)
 444 //{
 445 //      GList *tris = NULL;
 446 //      for (int x = 0; x+1 < grid->xs; x++)
 447 //      for (int y = 0; y+1 < grid->ys; y++)
 448 //      for (int z = 0; z+1 < grid->zs; z++) {
 449 //              VolCell cell = {};
 450 //              cell.corner[0] = &grid->points[x  ][y  ][z  ];
 451 //              cell.corner[1] = &grid->points[x  ][y+1][z  ];
 452 //              cell.corner[2] = &grid->points[x+1][y+1][z  ];
 453 //              cell.corner[3] = &grid->points[x+1][y  ][z  ];
 454 //              cell.corner[4] = &grid->points[x  ][y  ][z+1];
 455 //              cell.corner[5] = &grid->points[x  ][y+1][z+1];
 456 //              cell.corner[6] = &grid->points[x+1][y+1][z+1];
 457 //              cell.corner[7] = &grid->points[x+1][y  ][z+1];
 458 //              GList *these = march_one_cube(&cell, level);
 459 //              tris = g_list_concat(these, tris);
 460 //      }
 461 //      return tris;
 462 //}
 463
 464 /**
 465  * Indexing convention:
 466  *
 467  *           Vertices:                    Edges:
 468  *
 469  *        4  ______________ 5           ______________
 470  *         /|            /|           /|     4      /|           | 2
 471  *        / |         6 / |       7  / |8        5 / |           |
 472  *    7  /_____________/  |        /______________/  | 9         |       1
 473  *      |   |         |   |        |   |   6     |   |           X----------
 474  *      | 0 |_________|___| 1      |   |_________|10_|          /
 475  *      |  /          |  /      11 | 3/     0    |  /          /
 476  *      | /           | /          | /           | / 1        / 0
 477  *    3 |/____________|/ 2         |/____________|/
 478  *                                        2
 479  */
 480
 481 GList *marching_cubes(VolGrid *grid, double level)
 482 {
 483         int xs = grid->xs;
 484         int ys = grid->ys;
 485         int zs = grid->zs;
 486
 487         GList *tris = NULL;
 488         VolVertex **verts = g_new0(VolVertex*, xs*ys*2*3);
 489 #define EDGE(x, y, z, num) (num + (x)*3 + (y)*xs*3 + ((z)%2)*ys*xs*3)
 490         for (int z = 0; z+1 < zs; z++) {
 491                 memset(&verts[EDGE(0,0,z+1,0)], 0, xs*ys*3*sizeof(VolVertex*));
 492         for (int y = 0; y+1 < ys; y++)
 493         for (int x = 0; x+1 < xs; x++) {
 494                 VolCell cell = {};
 495                 cell.corner[0] = vol_grid_get(grid, x  , y  , z  );
 496                 cell.corner[1] = vol_grid_get(grid, x  , y+1, z  );
 497                 cell.corner[2] = vol_grid_get(grid, x+1, y+1, z  );
 498                 cell.corner[3] = vol_grid_get(grid, x+1, y  , z  );
 499                 cell.corner[4] = vol_grid_get(grid, x  , y  , z+1);
 500                 cell.corner[5] = vol_grid_get(grid, x  , y+1, z+1);
 501                 cell.corner[6] = vol_grid_get(grid, x+1, y+1, z+1);
 502                 cell.corner[7] = vol_grid_get(grid, x+1, y  , z+1);
 503                 cell.edge[0 ] = verts[EDGE(x  ,y  ,z  ,1)];
 504                 cell.edge[1 ] = verts[EDGE(x  ,y+1,z  ,0)];
 505                 cell.edge[2 ] = verts[EDGE(x+1,y  ,z  ,1)];
 506                 cell.edge[3 ] = verts[EDGE(x  ,y  ,z  ,0)];
 507                 cell.edge[4 ] = verts[EDGE(x  ,y  ,z+1,1)];
 508                 cell.edge[7 ] = verts[EDGE(x  ,y  ,z+1,0)];
 509                 cell.edge[8 ] = verts[EDGE(x  ,y  ,z  ,2)];
 510                 cell.edge[9 ] = verts[EDGE(x  ,y+1,z  ,2)];
 511                 cell.edge[10] = verts[EDGE(x+1,y+1,z  ,2)];
 512                 cell.edge[11] = verts[EDGE(x+1,y  ,z  ,2)];
 513                 GList *these = march_one_cube(&cell, level);
 514                 if (these) {
 515                         verts[EDGE(x  ,y+1,z  ,0)] = cell.edge[1 ];
 516                         verts[EDGE(x+1,y  ,z  ,1)] = cell.edge[2 ];
 517                         verts[EDGE(x  ,y  ,z+1,1)] = cell.edge[4 ];
 518                         verts[EDGE(x  ,y+1,z+1,0)] = cell.edge[5 ];
 519                         verts[EDGE(x+1,y  ,z+1,1)] = cell.edge[6 ];
 520                         verts[EDGE(x  ,y  ,z+1,0)] = cell.edge[7 ];
 521                         verts[EDGE(x  ,y+1,z  ,2)] = cell.edge[9 ];
 522                         verts[EDGE(x+1,y+1,z  ,2)] = cell.edge[10];
 523                         verts[EDGE(x+1,y  ,z  ,2)] = cell.edge[11];
 524                         tris = g_list_concat(these, tris);
 525                 }
 526         } }
 527 #undef EDGE
 528         g_free(verts);
 529         g_debug("Marching: generated %d triangles", g_list_length(tris));
 530         return tris;
 531 }
 532
 533 void vol_triangle_free(VolTriangle *tri)
 534 {
 535         for (int i = 0; i < 3; i++)
 536                 if (--tri->v[i]->tris == 0)
 537                         g_free(tri->v[i]);
 538         g_free(tri);
 539 }
 540
 541 VolGrid *vol_grid_new(int xs, int ys, int zs)
 542 {
 543         g_debug("VolGrid: new - %d,%d,%d", xs, ys, zs);
 544         VolGrid *grid = g_new0(VolGrid, 1);
 545         grid->data    = g_new0(VolPoint, xs*ys*zs);
 546         grid->xs      = xs;
 547         grid->ys      = ys;
 548         grid->zs      = zs;
 549         return grid;
 550 }
 551
 552 void vol_grid_free(VolGrid *grid)
 553 {
 554         g_free(grid->data);
 555         g_free(grid);
 556 }