Cycles: svn merge -r40358:40411 ^/trunk/blender
[blender.git] / intern / container / CTR_TaggedSetOps.h
1 /*
2  * $Id$
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): none yet.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file container/CTR_TaggedSetOps.h
30  *  \ingroup ctr
31  */
32
33
34 #ifndef NAN_INCLUDED_LOD_TaggedSetOps_h
35 #define NAN_INCLUDED_LOD_TaggedSetOps_h
36
37 #include "MEM_NonCopyable.h"
38 #include <vector>
39
40 /**
41  * This class contains some utility functions for finding the intersection,
42  * union, and difference of a collection of stl vector of indices into
43  * a set of primitives.
44  *
45  * These are mainly used as helper functions in the decimation and bsp
46  * libraries.
47  *
48  * This template class assumes that each value of type IndexType encountered
49  * in the list is a valid index into an array of primitives. This is not
50  * checked at run-time and is left to the user to insure. Prmitives of
51  * type ObjectType must have the following public methods to be used by
52  * this template class:
53  *
54  *      int
55  * OpenTag(void) --- return a persistent tag value for the primitive
56  *
57  *      void
58  * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla.
59  *
60  *      bool
61  * SelectTag() --- return a persistent boolean tag for this primitive
62  *
63  *      void
64  * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla.
65  *
66  * Here persistent means that the tag should be associated with the object for the
67  * entire lifetime of the primitive. Again none of this stuff is enforced you have
68  * to make sure that your primitives do the right thing. Often these tags can be
69  * cunningly stowed away inside some of the spare bits in the primitive. See
70  * CTR_TaggedIndex for such a class.
71  *
72  */
73
74 template 
75 <class IndexType, class ObjectType>
76 class CTR_TaggedSetOps : public MEM_NonCopyable {
77
78 public :
79
80         static
81                 void
82         Intersect(
83                 const std::vector< std::vector<IndexType> > &index_list,
84                 std::vector<ObjectType> &primitives,
85                 std::vector<IndexType> &output,
86                 unsigned int mask,
87                 unsigned int shift
88         ) {
89
90                 // iterate through vectors in index_list
91                 // iterate through individual members of each vector
92                 // mark each obejct that the index points to 
93
94                 typename std::vector< std::vector<IndexType> >::const_iterator 
95                         last_vector = index_list.end();
96                 typename std::vector< std::vector<IndexType> >::const_iterator 
97                         start_vector = index_list.begin();
98
99                 // FIXME some temporary space
100
101                 std::vector<IndexType> temp_union;
102                 temp_union.reserve(64);
103
104                 int tag_num = 0;
105
106                 for (; start_vector != last_vector; ++start_vector) {
107
108                         typename std::vector<IndexType>::const_iterator 
109                                 last_index = start_vector->end();
110                         typename std::vector<IndexType>::const_iterator 
111                                 start_index = start_vector->begin();
112
113                         for (; start_index != last_index; ++start_index) {
114
115                                 ObjectType & prim = primitives[*start_index];
116
117                                 if (!prim.OpenTag()) {
118                                         // compute the union
119                                         temp_union.push_back(*start_index);
120                                 }
121                                 int tag = prim.OpenTag();
122                                 tag = (tag & mask) >> shift;
123                                 tag += 1;
124                                 prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask));
125                         }
126
127                         ++tag_num;
128                 }
129                                 
130                 // now iterate through the union and pull out all those with the right tag
131                 
132                 typename std::vector<IndexType>::const_iterator last_index = 
133                         temp_union.end();
134                 typename std::vector<IndexType>::const_iterator start_index = 
135                         temp_union.begin();
136
137                 for (; start_index != last_index; ++start_index) {
138
139                         ObjectType & prim = primitives[*start_index];
140
141                         if (prim.OpenTag() == tag_num) {
142                                 //it's part of the intersection!
143
144                                 output.push_back(*start_index);
145                                 // because we're iterating through the union 
146                                 // it's safe to remove the tag at this point
147
148                                 prim.SetOpenTag(prim.OpenTag() & ~mask);
149                         }
150                 }
151         };
152                 
153         // note not a strict set intersection!
154         // if x appears twice in b and is part of the intersection
155         // it will appear twice in the intersection
156
157         static
158                 void
159         IntersectPair(
160                 const std::vector<IndexType> &a,
161                 const std::vector<IndexType> &b,
162                 std::vector<ObjectType> &primitives,
163                 std::vector<IndexType> &output
164         ) {
165                 
166                 typename std::vector<IndexType>::const_iterator last_index = 
167                         a.end();
168                 typename std::vector<IndexType>::const_iterator start_index = 
169                         a.begin();
170
171                 for (; start_index != last_index; ++start_index) {
172                         ObjectType & prim = primitives[*start_index];
173                         prim.SetSelectTag(true);
174                 }
175                 last_index = b.end();
176                 start_index = b.begin();
177
178                 for (; start_index != last_index; ++start_index) {
179                         ObjectType & prim = primitives[*start_index];
180                         if (prim.SelectTag()) {
181                                 output.push_back(*start_index);
182                         }
183                 }
184                 // deselect
185                 last_index = a.end();
186                 start_index = a.begin();
187
188                 for (; start_index != last_index; ++start_index) {
189                         ObjectType & prim = primitives[*start_index];
190                         prim.SetSelectTag(false);
191                 }
192         };
193
194
195         static  
196                 void
197         Union(
198                 std::vector< std::vector<IndexType> > &index_list,
199                 std::vector<ObjectType> &primitives,
200                 std::vector<IndexType> &output
201         ) {
202         
203                 // iterate through vectors in index_list
204                 // iterate through individual members of each vector
205                 // mark each obejct that the index points to 
206
207                 typename std::vector< std::vector<IndexType> >::const_iterator 
208                         last_vector = index_list.end();
209                 typename std::vector< std::vector<IndexType> >::iterator 
210                         start_vector = index_list.begin();
211
212                 for (; start_vector != last_vector; ++start_vector) {
213
214                         typename std::vector<IndexType>::const_iterator 
215                                 last_index = start_vector->end();
216                         typename std::vector<IndexType>::iterator 
217                                 start_index = start_vector->begin();
218
219                         for (; start_index != last_index; ++start_index) {
220
221                                 ObjectType & prim = primitives[*start_index];
222
223                                 if (!prim.SelectTag()) {
224                                         // compute the union
225                                         output.push_back(*start_index);
226                                         prim.SetSelectTag(true);
227                                 }
228                         }
229                 }
230                                 
231                 // now iterate through the union and reset the tags
232                 
233                 typename std::vector<IndexType>::const_iterator last_index = 
234                         output.end();
235                 typename std::vector<IndexType>::iterator start_index = 
236                         output.begin();
237
238                 for (; start_index != last_index; ++start_index) {
239
240                         ObjectType & prim = primitives[*start_index];
241                         prim.SetSelectTag(false);
242                 }                       
243         }
244
245
246         static
247                 void
248         Difference(
249                 std::vector< IndexType> &a,
250                 std::vector< IndexType> &b,
251                 std::vector<ObjectType> &primitives,
252                 std::vector< IndexType> &output
253         ) {
254
255                 // iterate through b mark all
256                 // iterate through a and add to output all unmarked 
257
258                 typename std::vector<IndexType>::const_iterator last_index = 
259                         b.end();
260                 typename std::vector<IndexType>::iterator start_index = 
261                         b.begin();
262
263                 for (; start_index != last_index; ++start_index) {
264
265                         ObjectType & prim = primitives[*start_index];
266                         prim.SetSelectTag(true);
267                 }
268                         
269                 last_index = a.end();
270                 start_index = a.begin();
271
272                 for (; start_index != last_index; ++start_index) {
273
274                         ObjectType & prim = primitives[*start_index];
275                         if (!prim.SelectTag()) {
276                                 output.push_back(*start_index);
277                         }
278                 }
279
280                 // clean up the tags
281         
282                 last_index = b.end();
283                 start_index = b.begin();
284
285                 for (; start_index != last_index; ++start_index) {
286
287                         ObjectType & prim = primitives[*start_index];
288                         prim.SetSelectTag(false);
289                 }
290         };
291
292 private :
293
294         // private constructor - this class is not meant for
295         // instantiation
296
297         CTR_TaggedSetOps();
298
299 };
300
301 #endif
302