← Back to branch summary

~ubuntu-branches/ubuntu/edgy/k3d/edgy-proposed

« back to all changes in this revision

Viewing changes to modules/surface_polygonizer_library/jules_bloomenthal.h

  • Committer: Bazaar Package Importer
  • Author(s): David Martínez Moreno
  • Date: 2005-04-28 18:38:10 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050428183810-kvc6nz46z6gheo0k
Tags: 0.4.5.0-5
* AAAAAAAARGH, *patching* configure.ac broke again the build process! Fixed
  (I hope).
* Removed more cruft of shaderpreprocessor/ from configure.

Show diffs side-by-side

added added

removed removed

Lines of Context:
modules/surface_polygonizer_library/jules_bloomenthal.h
 
1
#ifndef JULES_BLOOMENTHAL_H
 
2
#define JULES_BLOOMENTHAL_H
 
3
 
 
4
// A C++ Implicit Surface Polygonizer
 
5
// Copyright 2002-2004, Romain Behar <romainbehar@yahoo.com>
 
6
//
 
7
// This program is free software; you can redistribute it and/or
 
8
// modify it under the terms of the GNU General Public
 
9
// License as published by the Free Software Foundation; either
 
10
// version 2 of the License, or (at your option) any later version.
 
11
//
 
12
// This program is distributed in the hope that it will be useful,
 
13
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
15
// General Public License for more details.
 
16
//
 
17
// You should have received a copy of the GNU General Public
 
18
// License along with this program; if not, write to the Free Software
 
19
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
20
 
 
21
/** \file
 
22
                \brief Declares bloomenthal_polygonizer, an implicit surface polygonizer
 
23
                \author Romain Behar (romainbehar@yahoo.com)
 
24
*/
 
25
 
 
26
#include "isurface_polygonizer.h"
 
27
 
 
28
#include <k3dsdk/vectors.h>
 
29
 
 
30
#include <map>
 
31
#include <stack>
 
32
 
 
33
// It is based on Jules Bloomenthal's work :
 
34
//
 
35
// C code from the article
 
36
// "An Implicit Surface Polygonizer"
 
37
// by Jules Bloomenthal, jbloom@beauty.gmu.edu
 
38
// in "Graphics Gems IV", Academic Press, 1994
 
39
//
 
40
// implicit.c
 
41
//     an implicit surface polygonizer, translated from Mesa
 
42
//     applications should call polygonize()
 
43
//
 
44
// Authored by Jules Bloomenthal, Xerox PARC.
 
45
// Copyright (c) Xerox Corporation, 1991.  All rights reserved.
 
46
// Permission is granted to reproduce, use and distribute this code for
 
47
// any and all purposes, provided that this notice appears in all copies.
 
48
 
 
49
typedef k3d::vector3 vertex_t;
 
50
typedef std::vector<vertex_t> vertices_t;
 
51
typedef std::vector<unsigned long> polygon_t;
 
52
typedef std::vector<polygon_t> polygons_t;
 
53
 
 
54
typedef unsigned long enum_t;
 
55
 
 
56
// Lattice position (centered on (0, 0, 0), signed values)
 
57
class Location
 
58
{
 
59
public:
 
60
        Location(const int I = 0, const int J = 0, const int K = 0) :
 
61
                i(I),
 
62
                j(J),
 
63
                k(K)
 
64
        {
 
65
        }
 
66
 
 
67
        inline friend bool operator == (const Location& a, const Location& b)
 
68
        {
 
69
                return (a.i == b.i) && (a.j == b.j) && (a.k == b.k);
 
70
        }
 
71
        inline friend Location operator + (const Location& a, const Location& b)
 
72
        {
 
73
                return Location(a.i + b.i, a.j + b.j, a.k + b.k);
 
74
        }
 
75
        inline friend bool operator <= (const Location& a, const Location& b)
 
76
        {
 
77
                return (a.i <= b.i && a.j <= b.j && a.k <= b.k);
 
78
        }
 
79
        inline friend bool operator < (const Location& a, const Location& b)
 
80
        {
 
81
                return (a.i < b.i && a.j < b.j && a.k < b.k);
 
82
        }
 
83
 
 
84
        friend std::ostream& operator << (std::ostream& Stream, const Location& RHS)
 
85
        {
 
86
                Stream << RHS.i << " " << RHS.j << " " << RHS.k;
 
87
                return Stream;
 
88
        }
 
89
 
 
90
        Location Left() { return Location(i-1, j, k); }
 
91
        Location Right() { return Location(i+1, j, k); }
 
92
        Location Bottom() { return Location(i, j-1, k); }
 
93
        Location Top() { return Location(i, j+1, k); }
 
94
        Location Near() { return Location(i, j, k-1); }
 
95
        Location Far() { return Location(i, j, k+1); }
 
96
 
 
97
        int i;
 
98
        int j;
 
99
        int k;
 
100
};
 
101
 
 
102
/*
 
103
class LocationHash
 
104
{
 
105
public:
 
106
        inline int HashFunc(const Location& Value)
 
107
        {
 
108
                static const int HashBit = 5;
 
109
                static const int Mask = (1 << HashBit) - 1;
 
110
                return ((Value.i & Mask) << (HashBit*2)) | ((Value.j & Mask) << HashBit) | (Value.k & Mask);
 
111
        }
 
112
};
 
113
*/
 
114
 
 
115
template<typename type_t>
 
116
class LocationMap
 
117
{
 
118
public:
 
119
        typedef std::vector< std::pair<Location, type_t> > table_t;
 
120
 
 
121
        LocationMap() {}
 
122
        ~LocationMap() {}
 
123
 
 
124
        void insert(const Location& loc, const type_t item)
 
125
        {
 
126
                int key = loc.i + loc.j + loc.k;
 
127
                m_table[key].push_back(std::pair<Location, type_t>(loc, item));
 
128
        }
 
129
 
 
130
        bool get(const Location& loc, type_t& out)
 
131
        {
 
132
                int key = loc.i + loc.j + loc.k;
 
133
                table_t& table(m_table[key]);
 
134
                for(typename table_t::const_iterator t = table.begin(); t != table.end(); t++)
 
135
                        if(t->first == loc)
 
136
                                {
 
137
                                        out = t->second;
 
138
                                        return true;
 
139
                                }
 
140
 
 
141
                return false;
 
142
        }
 
143
 
 
144
private:
 
145
        std::map<unsigned long, std::vector< std::pair<Location, type_t> > > m_table;
 
146
};
 
147
 
 
148
// bloomenthal_polygonizer implementation
 
149
class bloomenthal_polygonizer
 
150
{
 
151
public:
 
152
        typedef enum
 
153
        {
 
154
                MARCHINGCUBES,
 
155
                TETRAHEDRAL
 
156
        } polygonization_t;
 
157
 
 
158
        bloomenthal_polygonizer(
 
159
                const polygonization_t polygonization_type,
 
160
                const double voxel_size,
 
161
                const double threshold,
 
162
                const int xmin, const int xmax,
 
163
                const int ymin, const int ymax,
 
164
                const int zmin, const int zmax,
 
165
                const vertex_t& origin,
 
166
                implicit_functor& functor,
 
167
                vertices_t& surface_vertices,
 
168
                vertices_t& surface_normals,
 
169
                polygons_t& surface_polygons);
 
170
 
 
171
        ~bloomenthal_polygonizer();
 
172
 
 
173
        bool polygonize_from_inside_point(const vertex_t& startingpoint);
 
174
 
 
175
        void polygonize_whole_grid();
 
176
 
 
177
        void cross_limits() { m_keep_within_limits = false; }
 
178
 
 
179
        // Cube corner
 
180
        class Corner
 
181
        {
 
182
        public:
 
183
                Location l;
 
184
                vertex_t p;
 
185
                double value;
 
186
 
 
187
                Corner(const Location& L) :
 
188
                        l(L)
 
189
                {
 
190
                }
 
191
 
 
192
                inline friend bool operator == (const Corner& c1, const Corner& c2)
 
193
                {
 
194
                        return (c1.l == c2.l) && (c1.p == c2.p) && (c1.value == c2.value);
 
195
                }
 
196
        };
 
197
 
 
198
        // Partitioning cell
 
199
        class Cube
 
200
        {
 
201
        public:
 
202
                Location l;
 
203
                Corner* corners[8];
 
204
 
 
205
                Cube(const Location& L) :
 
206
                        l(L)
 
207
                {
 
208
                        for(int i = 0; i < 8; i++)
 
209
                                corners[i] = 0;
 
210
                }
 
211
        };
 
212
 
 
213
        class Edge
 
214
        {
 
215
        public:
 
216
                Edge(const Location& L1, const Location& L2, const int VID = -1) :
 
217
                        vid(VID)
 
218
                {
 
219
                        if(L1.i > L2.i || (L1.i == L2.i && (L1.j > L2.j || (L1.j == L2.j && L1.k > L2.k))))
 
220
                                {
 
221
                                        l1 = L2;
 
222
                                        l2 = L1;
 
223
                                }
 
224
                        else
 
225
                                {
 
226
                                        l1 = L1;
 
227
                                        l2 = L2;
 
228
                                }
 
229
                }
 
230
 
 
231
                inline friend bool operator == (const Edge& e1, const Edge& e2)
 
232
                {
 
233
                        return (e1.l1 == e2.l1) && (e1.l2 == e2.l2) && (e1.vid == e2.vid);
 
234
                }
 
235
 
 
236
                Location l1;
 
237
                Location l2;
 
238
                int vid;
 
239
        };
 
240
 
 
241
        class EdgeHash
 
242
        {
 
243
        private:
 
244
                static const int HashBit = 5;
 
245
                static const int Mask = (1 << HashBit) - 1;
 
246
                static const int HashSize = 1 << (3 * HashBit);
 
247
 
 
248
                inline int HashFunc(const Location& l)
 
249
                {
 
250
                        return ((((l.i & Mask) << HashBit) | (l.j & Mask)) << HashBit) | (l.k & Mask);
 
251
                }
 
252
 
 
253
        public:
 
254
                EdgeHash()
 
255
                        {
 
256
                        edges.resize(HashSize*2);
 
257
                        }
 
258
 
 
259
                void push_back(const Edge& Value)
 
260
                        {
 
261
                        int index = HashFunc(Value.l1) + HashFunc(Value.l2);
 
262
                        edges[index].push_back(Value);
 
263
                        }
 
264
 
 
265
                int GetValue(const Edge& Value)
 
266
                        {
 
267
                                int index = HashFunc(Value.l1) + HashFunc(Value.l2);
 
268
                                for(unsigned int n = 0; n < edges[index].size(); n++)
 
269
                                        {
 
270
                                                if(edges[index][n].l1 == Value.l1 && edges[index][n].l2 == Value.l2)
 
271
                                                        return edges[index][n].vid;
 
272
                                        }
 
273
 
 
274
                                return -1;
 
275
                        }
 
276
 
 
277
        protected:
 
278
                std::vector< std::vector<Edge> > edges;
 
279
        };
 
280
 
 
281
private:
 
282
        /// Polygonizer parameters
 
283
 
 
284
        // Polygonization type
 
285
        polygonization_t m_Decomposition;
 
286
        // Width of the partitioning cube
 
287
        double m_VoxelSize;
 
288
        // Threshold value (defining the equipotential surface)
 
289
        double m_Threshold;
 
290
        // Grid limit corners (left-bottom-near and right-top-far)
 
291
        Location m_MinCorner;
 
292
        Location m_MaxCorner;
 
293
        bool m_keep_within_limits;
 
294
        // Grid center ( Location(0, 0, 0) )
 
295
        vertex_t m_GridOrigin;
 
296
        // Implicit function
 
297
        implicit_functor& m_FieldFunctor;
 
298
        // Surface storage
 
299
        vertices_t& m_Vertices;
 
300
        vertices_t& m_normals;
 
301
        polygons_t& m_Polygons;
 
302
 
 
303
        /// Temp storage
 
304
 
 
305
        // Active cubes
 
306
        std::stack<Cube> m_active_cubes;
 
307
 
 
308
        // Centers hash
 
309
        LocationMap<bool> m_centers;
 
310
        // Return true if already set, otherwise set and return false
 
311
        bool mark_center(const Location& l)
 
312
        {
 
313
                bool out;
 
314
                if(m_centers.get(l, out))
 
315
                        return true;
 
316
 
 
317
                m_centers.insert(l, true);
 
318
                return false;
 
319
        }
 
320
 
 
321
        // Corners hash
 
322
        LocationMap<Corner*> m_Corners;
 
323
        // Return corner if found, else return 0
 
324
        Corner* get_corner(const Location& l)
 
325
        {
 
326
                Corner* out;
 
327
                if(m_Corners.get(l, out))
 
328
                        return out;
 
329
 
 
330
                return 0;
 
331
        }
 
332
 
 
333
        Corner* get_cached_corner(const Location& l);
 
334
 
 
335
        // Edge hash
 
336
        EdgeHash m_Edges;
 
337
 
 
338
        // Build fast Marching Cube tables
 
339
        typedef unsigned long table_item_t;
 
340
        std::vector< std::vector< std::vector<table_item_t> > > m_CubeTable;
 
341
 
 
342
 
 
343
        // Convert between vertex and Location
 
344
        vertex_t location_vertex(const Location& l);
 
345
        Location nearest_location(const vertex_t& p);
 
346
 
 
347
        void PolygonizeSurface(const Location& startinglocation);
 
348
 
 
349
        // Inline functions
 
350
        inline int bit_value(int number, int bit_number) { return (number >> bit_number) & 1; }
 
351
        inline int invert_bit(int i, int bit) { return i ^ (1 << bit); }
 
352
 
 
353
        vertex_t normal(const vertex_t& Point);
 
354
 
 
355
        bool SurfaceLocation(Location& startinglocation);
 
356
 
 
357
        // Tetrahedral Polygonization
 
358
        void TriangulateTet(const Cube& cube1, int c1, int c2, int c3, int c4);
 
359
 
 
360
        // Cubical Polygonization
 
361
        void MakeCubeTable();
 
362
        void MarchingCube(const Cube& cube1);
 
363
 
 
364
        void TestFace(const Location& facelocation, Cube& old, int face, int c1, int c2, int c3, int c4);
 
365
 
 
366
        int VerticeId(Corner *c1, Corner *c2);
 
367
        void Converge(const vertex_t& p1, const vertex_t& p2, double v, vertex_t& p);
 
368
 
 
369
        void SaveTriangle(unsigned long u, unsigned long v, unsigned long w);
 
370
};
 
371
 
 
372
#endif // JULES_BLOOMENTHAL_H
 
373
 
 
374