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 #include "MEM_NonCopyable.h"
  36 #include <vector>
  37
  38 /**
  39  * This class contains some utility functions for finding the intersection,
  40  * union, and difference of a collection of stl vector of indices into
  41  * a set of primitives.
  42  *
  43  * These are mainly used as helper functions in the decimation and bsp
  44  * libraries.
  45  *
  46  * This template class assumes that each value of type IndexType encountered
  47  * in the list is a valid index into an array of primitives. This is not
  48  * checked at run-time and is left to the user to insure. Prmitives of
  49  * type ObjectType must have the following public methods to be used by
  50  * this template class:
  51  *
  52  *      int
  53  * OpenTag(void) --- return a persistent tag value for the primitive
  54  *
  55  *      void
  56  * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla.
  57  *
  58  *      bool
  59  * SelectTag() --- return a persistent boolean tag for this primitive
  60  *
  61  *      void
  62  * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla.
  63  *
  64  * Here persistent means that the tag should be associated with the object for the
  65  * entire lifetime of the primitive. Again none of this stuff is enforced you have
  66  * to make sure that your primitives do the right thing. Often these tags can be
  67  * cunningly stowed away inside some of the spare bits in the primitive. See
  68  * CTR_TaggedIndex for such a class.
  69  *
  70  */
  71
  72 template
  73 <class IndexType, class ObjectType>
  74 class CTR_TaggedSetOps : public MEM_NonCopyable {
  75
  76 public :
  77
  78         static
  79                 void
  80         Intersect(
  81                 const std::vector< std::vector<IndexType> > &index_list,
  82                 std::vector<ObjectType> &primitives,
  83                 std::vector<IndexType> &output,
  84                 unsigned int mask,
  85                 unsigned int shift
  86         ) {
  87
  88                 // iterate through vectors in index_list
  89                 // iterate through individual members of each vector
  90                 // mark each obejct that the index points to
  91
  92                 typename std::vector< std::vector<IndexType> >::const_iterator
  93                         last_vector = index_list.end();
  94                 typename std::vector< std::vector<IndexType> >::const_iterator
  95                         start_vector = index_list.begin();
  96
  97                 // FIXME some temporary space
  98
  99                 std::vector<IndexType> temp_union;
 100                 temp_union.reserve(64);
 101
 102                 int tag_num = 0;
 103
 104                 for (; start_vector != last_vector; ++start_vector) {
 105
 106                         typename std::vector<IndexType>::const_iterator
 107                                 last_index = start_vector->end();
 108                         typename std::vector<IndexType>::const_iterator
 109                                 start_index = start_vector->begin();
 110
 111                         for (; start_index != last_index; ++start_index) {
 112
 113                                 ObjectType & prim = primitives[*start_index];
 114
 115                                 if (!prim.OpenTag()) {
 116                                         // compute the union
 117                                         temp_union.push_back(*start_index);
 118                                 }
 119                                 int tag = prim.OpenTag();
 120                                 tag = (tag & mask) >> shift;
 121                                 tag += 1;
 122                                 prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask));
 123                         }
 124
 125                         ++tag_num;
 126                 }
 127
 128                 // now iterate through the union and pull out all those with the right tag
 129
 130                 typename std::vector<IndexType>::const_iterator last_index =
 131                         temp_union.end();
 132                 typename std::vector<IndexType>::const_iterator start_index =
 133                         temp_union.begin();
 134
 135                 for (; start_index != last_index; ++start_index) {
 136
 137                         ObjectType & prim = primitives[*start_index];
 138
 139                         if (prim.OpenTag() == tag_num) {
 140                                 //it's part of the intersection!
 141
 142                                 output.push_back(*start_index);
 143                                 // because we're iterating through the union
 144                                 // it's safe to remove the tag at this point
 145
 146                                 prim.SetOpenTag(prim.OpenTag() & ~mask);
 147                         }
 148                 }
 149         };
 150
 151         // note not a strict set intersection!
 152         // if x appears twice in b and is part of the intersection
 153         // it will appear twice in the intersection
 154
 155         static
 156                 void
 157         IntersectPair(
 158                 const std::vector<IndexType> &a,
 159                 const std::vector<IndexType> &b,
 160                 std::vector<ObjectType> &primitives,
 161                 std::vector<IndexType> &output
 162         ) {
 163
 164                 typename std::vector<IndexType>::const_iterator last_index =
 165                         a.end();
 166                 typename std::vector<IndexType>::const_iterator start_index =
 167                         a.begin();
 168
 169                 for (; start_index != last_index; ++start_index) {
 170                         ObjectType & prim = primitives[*start_index];
 171                         prim.SetSelectTag(true);
 172                 }
 173                 last_index = b.end();
 174                 start_index = b.begin();
 175
 176                 for (; start_index != last_index; ++start_index) {
 177                         ObjectType & prim = primitives[*start_index];
 178                         if (prim.SelectTag()) {
 179                                 output.push_back(*start_index);
 180                         }
 181                 }
 182                 // deselect
 183                 last_index = a.end();
 184                 start_index = a.begin();
 185
 186                 for (; start_index != last_index; ++start_index) {
 187                         ObjectType & prim = primitives[*start_index];
 188                         prim.SetSelectTag(false);
 189                 }
 190         };
 191
 192
 193         static
 194                 void
 195         Union(
 196                 std::vector< std::vector<IndexType> > &index_list,
 197                 std::vector<ObjectType> &primitives,
 198                 std::vector<IndexType> &output
 199         ) {
 200
 201                 // iterate through vectors in index_list
 202                 // iterate through individual members of each vector
 203                 // mark each obejct that the index points to
 204
 205                 typename std::vector< std::vector<IndexType> >::const_iterator
 206                         last_vector = index_list.end();
 207                 typename std::vector< std::vector<IndexType> >::iterator
 208                         start_vector = index_list.begin();
 209
 210                 for (; start_vector != last_vector; ++start_vector) {
 211
 212                         typename std::vector<IndexType>::const_iterator
 213                                 last_index = start_vector->end();
 214                         typename std::vector<IndexType>::iterator
 215                                 start_index = start_vector->begin();
 216
 217                         for (; start_index != last_index; ++start_index) {
 218
 219                                 ObjectType & prim = primitives[*start_index];
 220
 221                                 if (!prim.SelectTag()) {
 222                                         // compute the union
 223                                         output.push_back(*start_index);
 224                                         prim.SetSelectTag(true);
 225                                 }
 226                         }
 227                 }
 228
 229                 // now iterate through the union and reset the tags
 230
 231                 typename std::vector<IndexType>::const_iterator last_index =
 232                         output.end();
 233                 typename std::vector<IndexType>::iterator start_index =
 234                         output.begin();
 235
 236                 for (; start_index != last_index; ++start_index) {
 237
 238                         ObjectType & prim = primitives[*start_index];
 239                         prim.SetSelectTag(false);
 240                 }
 241         }
 242
 243
 244         static
 245                 void
 246         Difference(
 247                 std::vector< IndexType> &a,
 248                 std::vector< IndexType> &b,
 249                 std::vector<ObjectType> &primitives,
 250                 std::vector< IndexType> &output
 251         ) {
 252
 253                 // iterate through b mark all
 254                 // iterate through a and add to output all unmarked
 255
 256                 typename std::vector<IndexType>::const_iterator last_index =
 257                         b.end();
 258                 typename std::vector<IndexType>::iterator start_index =
 259                         b.begin();
 260
 261                 for (; start_index != last_index; ++start_index) {
 262
 263                         ObjectType & prim = primitives[*start_index];
 264                         prim.SetSelectTag(true);
 265                 }
 266
 267                 last_index = a.end();
 268                 start_index = a.begin();
 269
 270                 for (; start_index != last_index; ++start_index) {
 271
 272                         ObjectType & prim = primitives[*start_index];
 273                         if (!prim.SelectTag()) {
 274                                 output.push_back(*start_index);
 275                         }
 276                 }
 277
 278                 // clean up the tags
 279
 280                 last_index = b.end();
 281                 start_index = b.begin();
 282
 283                 for (; start_index != last_index; ++start_index) {
 284
 285                         ObjectType & prim = primitives[*start_index];
 286                         prim.SetSelectTag(false);
 287                 }
 288         };
 289
 290 private :
 291
 292         // private constructor - this class is not meant for
 293         // instantiation
 294
 295         CTR_TaggedSetOps();
 296
 297 };
 298
 299 #endif
 300