From 0ee62e4ea6051857e37213b0371c6b426dabaf6e Mon Sep 17 00:00:00 2001 From: Bastien Montagne Date: Mon, 22 Oct 2012 06:47:54 +0000 Subject: Revert part of r51487 (those files are needed by the boolean ops code, /intern/bsp/...)! --- intern/container/CTR_TaggedIndex.h | 219 ++++++++++++++++++++++++++ intern/container/CTR_TaggedSetOps.h | 301 ++++++++++++++++++++++++++++++++++++ 2 files changed, 520 insertions(+) create mode 100644 intern/container/CTR_TaggedIndex.h create mode 100644 intern/container/CTR_TaggedSetOps.h diff --git a/intern/container/CTR_TaggedIndex.h b/intern/container/CTR_TaggedIndex.h new file mode 100644 index 00000000000..8420414d6c7 --- /dev/null +++ b/intern/container/CTR_TaggedIndex.h @@ -0,0 +1,219 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file container/CTR_TaggedIndex.h + * \ingroup ctr + */ + + +/** + + * Copyright (C) 2001 NaN Technologies B.V. + * Simple tagged index class. + */ + +#ifndef __CTR_TAGGEDINDEX_H__ +#define __CTR_TAGGEDINDEX_H__ + +/** + * This class is supposed to be a simple tagged index class. If these + * were indices into a mesh then we would never need 32 bits for such indices. + * It is often handy to have a few extra bits around to mark objects etc. We + * steal a few bits of CTR_TaggedIndex objects for this purpose. From the outside + * it will behave like a standard unsigned int but just carry the extra tag + * information around with it. + */ + +#include + +#include "MEM_sys_types.h" + +enum { + + empty_tag = 0x0, + empty_index = 0xffffffff +}; + +template < + int tag_shift, + int index_mask +> class CTR_TaggedIndex { +public: + CTR_TaggedIndex( + ) : + m_val ((empty_tag << tag_shift) | (empty_index & index_mask)) + { + } + + CTR_TaggedIndex( + const int val + ) : + m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) { + } + + CTR_TaggedIndex( + const unsigned int val + ) : + m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) { + } + + CTR_TaggedIndex( + const long int val + ) : + m_val ( ((long int) val & index_mask) + | ( (empty_tag << tag_shift) + & (~index_mask)) ) { + } + + CTR_TaggedIndex( + const long unsigned int val + ) : + m_val ( ((long unsigned int)val & index_mask) + | ( (empty_tag << tag_shift) + & (~index_mask) ) ) { + } + + +#if defined(_WIN64) + CTR_TaggedIndex( + const uint64_t val + ) : + m_val ( ((uint64_t)val & index_mask) + | ( (empty_tag << tag_shift) + & (~index_mask) ) ) { + } +#endif + + CTR_TaggedIndex( + const CTR_TaggedIndex &my_index + ): + m_val(my_index.m_val) + { + } + + bool + operator == ( + const CTR_TaggedIndex& rhs + ) const { + + return ((this->m_val & index_mask) == (rhs.m_val & index_mask)); + } + + operator unsigned int () const { + return m_val & index_mask; + } + + operator unsigned long int () const { + return (unsigned long int)(m_val & index_mask); + } + + operator int () const { + return int(m_val & index_mask); + } + + operator long int () const { + return (long int)(m_val & index_mask); + } + +#if defined(_WIN64) + operator uint64_t () const { + return (uint64_t)(m_val & index_mask); + } +#endif + + bool + IsEmpty( + ) const { + return ((m_val & index_mask) == (empty_index & index_mask)); + } + + + static + CTR_TaggedIndex + Empty( + ) { + return CTR_TaggedIndex(); + } + + void + Invalidate( + ) { + m_val = (empty_tag << tag_shift) | (empty_index & index_mask); + } + + + unsigned int + Tag ( + ) const { + return m_val >> tag_shift; + } + + void + SetTag( + unsigned int tag + ) { + m_val = (m_val & index_mask) | ((tag << tag_shift) & (~index_mask)); + } + + void + EmptyTag( + ) { + m_val = (m_val & index_mask) | ((empty_tag << tag_shift) & (~index_mask)); + } + + bool + IsEmptyTag( + ) const { + return (Tag() == Empty().Tag()); + } + + // functionals + + struct greater : std::binary_function + { + bool + operator()( + const CTR_TaggedIndex& a, + const CTR_TaggedIndex& b + ) const { + return (int(a) > int(b)); + } + }; + + +private : + CTR_TaggedIndex( + const CTR_TaggedIndex *index + ) {}; + + unsigned int m_val; + + +}; + +#endif + diff --git a/intern/container/CTR_TaggedSetOps.h b/intern/container/CTR_TaggedSetOps.h new file mode 100644 index 00000000000..d30081d2d60 --- /dev/null +++ b/intern/container/CTR_TaggedSetOps.h @@ -0,0 +1,301 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file container/CTR_TaggedSetOps.h + * \ingroup ctr + */ + + +#ifndef __CTR_TAGGEDSETOPS_H__ +#define __CTR_TAGGEDSETOPS_H__ + +#include "MEM_NonCopyable.h" +#include + +/** + * This class contains some utility functions for finding the intersection, + * union, and difference of a collection of stl vector of indices into + * a set of primitives. + * + * These are mainly used as helper functions in the decimation and bsp + * libraries. + * + * This template class assumes that each value of type IndexType encountered + * in the list is a valid index into an array of primitives. This is not + * checked at run-time and is left to the user to insure. Prmitives of + * type ObjectType must have the following public methods to be used by + * this template class: + * + * int + * OpenTag(void) --- return a persistent tag value for the primitive + * + * void + * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla. + * + * bool + * SelectTag() --- return a persistent boolean tag for this primitive + * + * void + * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla. + * + * Here persistent means that the tag should be associated with the object for the + * entire lifetime of the primitive. Again none of this stuff is enforced you have + * to make sure that your primitives do the right thing. Often these tags can be + * cunningly stowed away inside some of the spare bits in the primitive. See + * CTR_TaggedIndex for such a class. + * + */ + +template + +class CTR_TaggedSetOps : public MEM_NonCopyable { + +public : + + static + void + Intersect( + const std::vector< std::vector > &index_list, + std::vector &primitives, + std::vector &output, + unsigned int mask, + unsigned int shift + ) { + + // iterate through vectors in index_list + // iterate through individual members of each vector + // mark each obejct that the index points to + + typename std::vector< std::vector >::const_iterator + last_vector = index_list.end(); + typename std::vector< std::vector >::const_iterator + start_vector = index_list.begin(); + + // FIXME some temporary space + + std::vector temp_union; + temp_union.reserve(64); + + int tag_num = 0; + + for (; start_vector != last_vector; ++start_vector) { + + typename std::vector::const_iterator + last_index = start_vector->end(); + typename std::vector::const_iterator + start_index = start_vector->begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + + if (!prim.OpenTag()) { + // compute the union + temp_union.push_back(*start_index); + } + int tag = prim.OpenTag(); + tag = (tag & mask) >> shift; + tag += 1; + prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask)); + } + + ++tag_num; + } + + // now iterate through the union and pull out all those with the right tag + + typename std::vector::const_iterator last_index = + temp_union.end(); + typename std::vector::const_iterator start_index = + temp_union.begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + + if (prim.OpenTag() == tag_num) { + //it's part of the intersection! + + output.push_back(*start_index); + // because we're iterating through the union + // it's safe to remove the tag at this point + + prim.SetOpenTag(prim.OpenTag() & ~mask); + } + } + }; + + // note not a strict set intersection! + // if x appears twice in b and is part of the intersection + // it will appear twice in the intersection + + static + void + IntersectPair( + const std::vector &a, + const std::vector &b, + std::vector &primitives, + std::vector &output + ) { + + typename std::vector::const_iterator last_index = + a.end(); + typename std::vector::const_iterator start_index = + a.begin(); + + for (; start_index != last_index; ++start_index) { + ObjectType & prim = primitives[*start_index]; + prim.SetSelectTag(true); + } + last_index = b.end(); + start_index = b.begin(); + + for (; start_index != last_index; ++start_index) { + ObjectType & prim = primitives[*start_index]; + if (prim.SelectTag()) { + output.push_back(*start_index); + } + } + // deselect + last_index = a.end(); + start_index = a.begin(); + + for (; start_index != last_index; ++start_index) { + ObjectType & prim = primitives[*start_index]; + prim.SetSelectTag(false); + } + }; + + + static + void + Union( + std::vector< std::vector > &index_list, + std::vector &primitives, + std::vector &output + ) { + + // iterate through vectors in index_list + // iterate through individual members of each vector + // mark each obejct that the index points to + + typename std::vector< std::vector >::const_iterator + last_vector = index_list.end(); + typename std::vector< std::vector >::iterator + start_vector = index_list.begin(); + + for (; start_vector != last_vector; ++start_vector) { + + typename std::vector::const_iterator + last_index = start_vector->end(); + typename std::vector::iterator + start_index = start_vector->begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + + if (!prim.SelectTag()) { + // compute the union + output.push_back(*start_index); + prim.SetSelectTag(true); + } + } + } + + // now iterate through the union and reset the tags + + typename std::vector::const_iterator last_index = + output.end(); + typename std::vector::iterator start_index = + output.begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + prim.SetSelectTag(false); + } + } + + + static + void + Difference( + std::vector< IndexType> &a, + std::vector< IndexType> &b, + std::vector &primitives, + std::vector< IndexType> &output + ) { + + // iterate through b mark all + // iterate through a and add to output all unmarked + + typename std::vector::const_iterator last_index = + b.end(); + typename std::vector::iterator start_index = + b.begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + prim.SetSelectTag(true); + } + + last_index = a.end(); + start_index = a.begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + if (!prim.SelectTag()) { + output.push_back(*start_index); + } + } + + // clean up the tags + + last_index = b.end(); + start_index = b.begin(); + + for (; start_index != last_index; ++start_index) { + + ObjectType & prim = primitives[*start_index]; + prim.SetSelectTag(false); + } + }; + +private : + + // private constructor - this class is not meant for + // instantiation + + CTR_TaggedSetOps(); + +}; + +#endif + -- cgit v1.2.3