intern/container/CTR_TaggedSetOps.h

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