|
Blender
V2.59
|
00001 /* 00002 * $Id: CTR_TaggedSetOps.h 35146 2011-02-25 10:45:31Z jesterking $ 00003 * ***** BEGIN GPL LICENSE BLOCK ***** 00004 * 00005 * This program is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU General Public License 00007 * as published by the Free Software Foundation; either version 2 00008 * of the License, or (at your option) any later version. 00009 * 00010 * This program is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 * GNU General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU General Public License 00016 * along with this program; if not, write to the Free Software Foundation, 00017 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 00018 * 00019 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. 00020 * All rights reserved. 00021 * 00022 * The Original Code is: all of this file. 00023 * 00024 * Contributor(s): none yet. 00025 * 00026 * ***** END GPL LICENSE BLOCK ***** 00027 */ 00028 00034 #ifndef NAN_INCLUDED_LOD_TaggedSetOps_h 00035 #define NAN_INCLUDED_LOD_TaggedSetOps_h 00036 00037 #include "MEM_NonCopyable.h" 00038 #include <vector> 00039 00074 template 00075 <class IndexType, class ObjectType> 00076 class CTR_TaggedSetOps : public MEM_NonCopyable { 00077 00078 public : 00079 00080 static 00081 void 00082 Intersect( 00083 const std::vector< std::vector<IndexType> > &index_list, 00084 std::vector<ObjectType> &primitives, 00085 std::vector<IndexType> &output, 00086 unsigned int mask, 00087 unsigned int shift 00088 ) { 00089 00090 // iterate through vectors in index_list 00091 // iterate through individual members of each vector 00092 // mark each obejct that the index points to 00093 00094 typename std::vector< std::vector<IndexType> >::const_iterator 00095 last_vector = index_list.end(); 00096 typename std::vector< std::vector<IndexType> >::const_iterator 00097 start_vector = index_list.begin(); 00098 00099 // FIXME some temporary space 00100 00101 std::vector<IndexType> temp_union; 00102 temp_union.reserve(64); 00103 00104 int tag_num = 0; 00105 00106 for (; start_vector != last_vector; ++start_vector) { 00107 00108 typename std::vector<IndexType>::const_iterator 00109 last_index = start_vector->end(); 00110 typename std::vector<IndexType>::const_iterator 00111 start_index = start_vector->begin(); 00112 00113 for (; start_index != last_index; ++start_index) { 00114 00115 ObjectType & prim = primitives[*start_index]; 00116 00117 if (!prim.OpenTag()) { 00118 // compute the union 00119 temp_union.push_back(*start_index); 00120 } 00121 int tag = prim.OpenTag(); 00122 tag = (tag & mask) >> shift; 00123 tag += 1; 00124 prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask)); 00125 } 00126 00127 ++tag_num; 00128 } 00129 00130 // now iterate through the union and pull out all those with the right tag 00131 00132 typename std::vector<IndexType>::const_iterator last_index = 00133 temp_union.end(); 00134 typename std::vector<IndexType>::const_iterator start_index = 00135 temp_union.begin(); 00136 00137 for (; start_index != last_index; ++start_index) { 00138 00139 ObjectType & prim = primitives[*start_index]; 00140 00141 if (prim.OpenTag() == tag_num) { 00142 //it's part of the intersection! 00143 00144 output.push_back(*start_index); 00145 // because we're iterating through the union 00146 // it's safe to remove the tag at this point 00147 00148 prim.SetOpenTag(prim.OpenTag() & ~mask); 00149 } 00150 } 00151 }; 00152 00153 // note not a strict set intersection! 00154 // if x appears twice in b and is part of the intersection 00155 // it will appear twice in the intersection 00156 00157 static 00158 void 00159 IntersectPair( 00160 const std::vector<IndexType> &a, 00161 const std::vector<IndexType> &b, 00162 std::vector<ObjectType> &primitives, 00163 std::vector<IndexType> &output 00164 ) { 00165 00166 typename std::vector<IndexType>::const_iterator last_index = 00167 a.end(); 00168 typename std::vector<IndexType>::const_iterator start_index = 00169 a.begin(); 00170 00171 for (; start_index != last_index; ++start_index) { 00172 ObjectType & prim = primitives[*start_index]; 00173 prim.SetSelectTag(true); 00174 } 00175 last_index = b.end(); 00176 start_index = b.begin(); 00177 00178 for (; start_index != last_index; ++start_index) { 00179 ObjectType & prim = primitives[*start_index]; 00180 if (prim.SelectTag()) { 00181 output.push_back(*start_index); 00182 } 00183 } 00184 // deselect 00185 last_index = a.end(); 00186 start_index = a.begin(); 00187 00188 for (; start_index != last_index; ++start_index) { 00189 ObjectType & prim = primitives[*start_index]; 00190 prim.SetSelectTag(false); 00191 } 00192 }; 00193 00194 00195 static 00196 void 00197 Union( 00198 std::vector< std::vector<IndexType> > &index_list, 00199 std::vector<ObjectType> &primitives, 00200 std::vector<IndexType> &output 00201 ) { 00202 00203 // iterate through vectors in index_list 00204 // iterate through individual members of each vector 00205 // mark each obejct that the index points to 00206 00207 typename std::vector< std::vector<IndexType> >::const_iterator 00208 last_vector = index_list.end(); 00209 typename std::vector< std::vector<IndexType> >::iterator 00210 start_vector = index_list.begin(); 00211 00212 for (; start_vector != last_vector; ++start_vector) { 00213 00214 typename std::vector<IndexType>::const_iterator 00215 last_index = start_vector->end(); 00216 typename std::vector<IndexType>::iterator 00217 start_index = start_vector->begin(); 00218 00219 for (; start_index != last_index; ++start_index) { 00220 00221 ObjectType & prim = primitives[*start_index]; 00222 00223 if (!prim.SelectTag()) { 00224 // compute the union 00225 output.push_back(*start_index); 00226 prim.SetSelectTag(true); 00227 } 00228 } 00229 } 00230 00231 // now iterate through the union and reset the tags 00232 00233 typename std::vector<IndexType>::const_iterator last_index = 00234 output.end(); 00235 typename std::vector<IndexType>::iterator start_index = 00236 output.begin(); 00237 00238 for (; start_index != last_index; ++start_index) { 00239 00240 ObjectType & prim = primitives[*start_index]; 00241 prim.SetSelectTag(false); 00242 } 00243 } 00244 00245 00246 static 00247 void 00248 Difference( 00249 std::vector< IndexType> &a, 00250 std::vector< IndexType> &b, 00251 std::vector<ObjectType> &primitives, 00252 std::vector< IndexType> &output 00253 ) { 00254 00255 // iterate through b mark all 00256 // iterate through a and add to output all unmarked 00257 00258 typename std::vector<IndexType>::const_iterator last_index = 00259 b.end(); 00260 typename std::vector<IndexType>::iterator start_index = 00261 b.begin(); 00262 00263 for (; start_index != last_index; ++start_index) { 00264 00265 ObjectType & prim = primitives[*start_index]; 00266 prim.SetSelectTag(true); 00267 } 00268 00269 last_index = a.end(); 00270 start_index = a.begin(); 00271 00272 for (; start_index != last_index; ++start_index) { 00273 00274 ObjectType & prim = primitives[*start_index]; 00275 if (!prim.SelectTag()) { 00276 output.push_back(*start_index); 00277 } 00278 } 00279 00280 // clean up the tags 00281 00282 last_index = b.end(); 00283 start_index = b.begin(); 00284 00285 for (; start_index != last_index; ++start_index) { 00286 00287 ObjectType & prim = primitives[*start_index]; 00288 prim.SetSelectTag(false); 00289 } 00290 }; 00291 00292 private : 00293 00294 // private constructor - this class is not meant for 00295 // instantiation 00296 00297 CTR_TaggedSetOps(); 00298 00299 }; 00300 00301 #endif 00302