Panda3D

transformState.cxx

00001 // Filename: transformState.cxx
00002 // Created by:  drose (25Feb02)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "transformState.h"
00016 #include "compose_matrix.h"
00017 #include "bamReader.h"
00018 #include "bamWriter.h"
00019 #include "datagramIterator.h"
00020 #include "indent.h"
00021 #include "compareTo.h"
00022 #include "pStatTimer.h"
00023 #include "config_pgraph.h"
00024 #include "lightReMutexHolder.h"
00025 #include "lightMutexHolder.h"
00026 #include "thread.h"
00027 #include "py_panda.h"
00028 
00029 LightReMutex *TransformState::_states_lock = NULL;
00030 TransformState::States *TransformState::_states = NULL;
00031 CPT(TransformState) TransformState::_identity_state;
00032 CPT(TransformState) TransformState::_invalid_state;
00033 UpdateSeq TransformState::_last_cycle_detect;
00034 PStatCollector TransformState::_cache_update_pcollector("*:State Cache:Update");
00035 PStatCollector TransformState::_transform_compose_pcollector("*:State Cache:Compose Transform");
00036 PStatCollector TransformState::_transform_invert_pcollector("*:State Cache:Invert Transform");
00037 PStatCollector TransformState::_transform_calc_pcollector("*:State Cache:Calc Components");
00038 PStatCollector TransformState::_transform_break_cycles_pcollector("*:State Cache:Break Cycles");
00039 PStatCollector TransformState::_transform_new_pcollector("*:State Cache:New");
00040 PStatCollector TransformState::_transform_validate_pcollector("*:State Cache:Validate");
00041 PStatCollector TransformState::_transform_hash_pcollector("*:State Cache:Calc Hash");
00042 PStatCollector TransformState::_node_counter("TransformStates:On nodes");
00043 PStatCollector TransformState::_cache_counter("TransformStates:Cached");
00044 
00045 CacheStats TransformState::_cache_stats;
00046 
00047 TypeHandle TransformState::_type_handle;
00048 
00049 ////////////////////////////////////////////////////////////////////
00050 //     Function: TransformState::Constructor
00051 //       Access: Protected
00052 //  Description: Actually, this could be a private constructor, since
00053 //               no one inherits from TransformState, but gcc gives us a
00054 //               spurious warning if all constructors are private.
00055 ////////////////////////////////////////////////////////////////////
00056 TransformState::
00057 TransformState() : _lock("TransformState") {
00058   if (_states == (States *)NULL) {
00059     init_states();
00060   }
00061   _saved_entry = _states->end();
00062   _flags = F_is_identity | F_singular_known | F_is_2d;
00063   _inv_mat = (LMatrix4f *)NULL;
00064   _cache_stats.add_num_states(1);
00065 }
00066 
00067 ////////////////////////////////////////////////////////////////////
00068 //     Function: TransformState::Copy Constructor
00069 //       Access: Private
00070 //  Description: TransformStates are not meant to be copied.
00071 ////////////////////////////////////////////////////////////////////
00072 TransformState::
00073 TransformState(const TransformState &) {
00074   nassertv(false);
00075 }
00076 
00077 ////////////////////////////////////////////////////////////////////
00078 //     Function: TransformState::Copy Assignment Operator
00079 //       Access: Private
00080 //  Description: TransformStates are not meant to be copied.
00081 ////////////////////////////////////////////////////////////////////
00082 void TransformState::
00083 operator = (const TransformState &) {
00084   nassertv(false);
00085 }
00086 
00087 ////////////////////////////////////////////////////////////////////
00088 //     Function: TransformState::Destructor
00089 //       Access: Public, Virtual
00090 //  Description: The destructor is responsible for removing the
00091 //               TransformState from the global set if it is there.
00092 ////////////////////////////////////////////////////////////////////
00093 TransformState::
00094 ~TransformState() {
00095   // We'd better not call the destructor twice on a particular object.
00096   nassertv(!is_destructing());
00097   set_destructing();
00098  
00099   // Free the inverse matrix computation, if it has been stored.
00100   if (_inv_mat != (LMatrix4f *)NULL) {
00101     delete _inv_mat;
00102     _inv_mat = (LMatrix4f *)NULL;
00103   }
00104 
00105   LightReMutexHolder holder(*_states_lock);
00106 
00107   // unref() should have cleared these.
00108   nassertv(_saved_entry == _states->end());
00109   nassertv(_composition_cache.is_empty() && _invert_composition_cache.is_empty());
00110 
00111   // If this was true at the beginning of the destructor, but is no
00112   // longer true now, probably we've been double-deleted.
00113   nassertv(get_ref_count() == 0);
00114   _cache_stats.add_num_states(-1);
00115 }
00116 
00117 ////////////////////////////////////////////////////////////////////
00118 //     Function: TransformState::sorts_less
00119 //       Access: Published
00120 //  Description: Provides an arbitrary ordering among all unique
00121 //               TransformStates, so we can store the essentially
00122 //               different ones in a big set and throw away the rest.
00123 //
00124 //               If uniquify_matrix is true, then matrix-defined
00125 //               TransformStates are also uniqified.  If
00126 //               uniquify_matrix is false, then only component-defined
00127 //               TransformStates are uniquified, which is less
00128 //               expensive.
00129 ////////////////////////////////////////////////////////////////////
00130 bool TransformState::
00131 sorts_less(const TransformState &other, bool uniquify_matrix) const {
00132   static const int significant_flags = 
00133     (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_quat_given | F_is_2d);
00134 
00135   int flags = (_flags & significant_flags);
00136   int other_flags = (other._flags & significant_flags);
00137   if (flags != other_flags) {
00138     return flags < other_flags;
00139   }
00140 
00141   if ((_flags & (F_is_invalid | F_is_identity)) != 0) {
00142     // All invalid transforms are equivalent to each other, and all
00143     // identity transforms are equivalent to each other.
00144     return 0;
00145   }
00146 
00147   if ((_flags & F_components_given) != 0) {
00148     // If the transform was specified componentwise, compare them
00149     // componentwise.
00150     int c = _pos.compare_to(other._pos);
00151     if (c != 0) {
00152       return c < 0;
00153     }
00154 
00155     if ((_flags & F_hpr_given) != 0) {
00156       c = _hpr.compare_to(other._hpr);
00157       if (c != 0) {
00158         return c < 0;
00159       }
00160     } else if ((_flags & F_quat_given) != 0) {
00161       c = _quat.compare_to(other._quat);
00162       if (c != 0) {
00163         return c < 0;
00164       }
00165     }
00166 
00167     c = _scale.compare_to(other._scale);
00168     if (c != 0) {
00169       return c < 0;
00170     }
00171 
00172     c = _shear.compare_to(other._shear);
00173     return c < 0;
00174   }
00175 
00176   // Otherwise, compare the matrices . . .
00177   if (uniquify_matrix) {
00178     // . . . but only if the user thinks that's a worthwhile
00179     // comparison.
00180     return get_mat() < other.get_mat();
00181 
00182   } else {
00183     // If not, we just compare the pointers.
00184     return (this < &other);
00185   }
00186 }
00187 
00188 ////////////////////////////////////////////////////////////////////
00189 //     Function: TransformState::make_identity
00190 //       Access: Published, Static
00191 //  Description: Constructs an identity transform.
00192 ////////////////////////////////////////////////////////////////////
00193 CPT(TransformState) TransformState::
00194 make_identity() {
00195   // The identity state is asked for so often, we make it a special case
00196   // and store a pointer forever once we find it the first time.
00197   if (_identity_state == (TransformState *)NULL) {
00198     TransformState *state = new TransformState;
00199     _identity_state = return_unique(state);
00200   }
00201 
00202   return _identity_state;
00203 }
00204 
00205 ////////////////////////////////////////////////////////////////////
00206 //     Function: TransformState::make_invalid
00207 //       Access: Published, Static
00208 //  Description: Constructs an invalid transform; for instance, the
00209 //               result of inverting a singular matrix.
00210 ////////////////////////////////////////////////////////////////////
00211 CPT(TransformState) TransformState::
00212 make_invalid() {
00213   if (_invalid_state == (TransformState *)NULL) {
00214     TransformState *state = new TransformState;
00215     state->_flags = F_is_invalid | F_singular_known | F_is_singular | F_components_known | F_mat_known;
00216     _invalid_state = return_unique(state);
00217   }
00218 
00219   return _invalid_state;
00220 }
00221 
00222 ////////////////////////////////////////////////////////////////////
00223 //     Function: TransformState::make_pos_hpr_scale_shear
00224 //       Access: Published, Static
00225 //  Description: Makes a new TransformState with the specified
00226 //               components.
00227 ////////////////////////////////////////////////////////////////////
00228 CPT(TransformState) TransformState::
00229 make_pos_hpr_scale_shear(const LVecBase3f &pos, const LVecBase3f &hpr, 
00230                          const LVecBase3f &scale, const LVecBase3f &shear) {
00231   nassertr(!(pos.is_nan() || hpr.is_nan() || scale.is_nan() || shear.is_nan()) , make_invalid());
00232   // Make a special-case check for the identity transform.
00233   if (pos == LVecBase3f(0.0f, 0.0f, 0.0f) &&
00234       hpr == LVecBase3f(0.0f, 0.0f, 0.0f) &&
00235       scale == LVecBase3f(1.0f, 1.0f, 1.0f) &&
00236       shear == LVecBase3f(0.0f, 0.0f, 0.0f)) {
00237     return make_identity();
00238   }
00239 
00240   TransformState *state = new TransformState;
00241   state->_pos = pos;
00242   state->_hpr = hpr;
00243   state->_scale = scale;
00244   state->_shear = shear;
00245   state->_flags = F_components_given | F_hpr_given | F_components_known | F_hpr_known | F_has_components;
00246   state->check_uniform_scale();
00247   return return_new(state);
00248 }
00249 
00250 ////////////////////////////////////////////////////////////////////
00251 //     Function: TransformState::make_pos_quat_scale_shear
00252 //       Access: Published, Static
00253 //  Description: Makes a new TransformState with the specified
00254 //               components.
00255 ////////////////////////////////////////////////////////////////////
00256 CPT(TransformState) TransformState::
00257 make_pos_quat_scale_shear(const LVecBase3f &pos, const LQuaternionf &quat, 
00258                           const LVecBase3f &scale, const LVecBase3f &shear) {
00259   nassertr(!(pos.is_nan() || quat.is_nan() || scale.is_nan() || shear.is_nan()) , make_invalid());
00260   // Make a special-case check for the identity transform.
00261   if (pos == LVecBase3f(0.0f, 0.0f, 0.0f) &&
00262       quat == LQuaternionf::ident_quat() &&
00263       scale == LVecBase3f(1.0f, 1.0f, 1.0f) &&
00264       shear == LVecBase3f(0.0f, 0.0f, 0.0f)) {
00265     return make_identity();
00266   }
00267 
00268   TransformState *state = new TransformState;
00269   state->_pos = pos;
00270   state->_quat = quat;
00271   state->_scale = scale;
00272   state->_shear = shear;
00273   state->_flags = F_components_given | F_quat_given | F_components_known | F_quat_known | F_has_components;
00274   state->check_uniform_scale();
00275   return return_new(state);
00276 }
00277 
00278 ////////////////////////////////////////////////////////////////////
00279 //     Function: TransformState::make_mat
00280 //       Access: Published, Static
00281 //  Description: Makes a new TransformState with the specified
00282 //               transformation matrix.
00283 ////////////////////////////////////////////////////////////////////
00284 CPT(TransformState) TransformState::
00285 make_mat(const LMatrix4f &mat) {
00286   nassertr(!mat.is_nan(), make_invalid());
00287   // Make a special-case check for the identity matrix.
00288   if (mat == LMatrix4f::ident_mat()) {
00289     return make_identity();
00290   }
00291 
00292   TransformState *state = new TransformState;
00293   state->_mat = mat;
00294   state->_flags = F_mat_known;
00295   return return_new(state);
00296 }
00297 
00298 
00299 ////////////////////////////////////////////////////////////////////
00300 //     Function: TransformState::make_pos_rotate_scale_shear2d
00301 //       Access: Published, Static
00302 //  Description: Makes a new two-dimensional TransformState with the
00303 //               specified components.
00304 ////////////////////////////////////////////////////////////////////
00305 CPT(TransformState) TransformState::
00306 make_pos_rotate_scale_shear2d(const LVecBase2f &pos, float rotate,
00307                               const LVecBase2f &scale,
00308                               float shear) {
00309   nassertr(!(pos.is_nan() || cnan(rotate) || scale.is_nan() || cnan(shear)) , make_invalid());
00310   // Make a special-case check for the identity transform.
00311   if (pos == LVecBase2f(0.0f, 0.0f) &&
00312       rotate == 0.0f &&
00313       scale == LVecBase2f(1.0f, 1.0f) &&
00314       shear == 0.0f) {
00315     return make_identity();
00316   }
00317 
00318   TransformState *state = new TransformState;
00319   state->_pos.set(pos[0], pos[1], 0.0f);
00320   switch (get_default_coordinate_system()) {
00321   default:
00322   case CS_zup_right:
00323     state->_hpr.set(rotate, 0.0f, 0.0f);
00324     break;
00325   case CS_zup_left:
00326     state->_hpr.set(-rotate, 0.0f, 0.0f);
00327     break;
00328   case CS_yup_right:
00329     state->_hpr.set(0.0f, 0.0f, -rotate);
00330     break;
00331   case CS_yup_left:
00332     state->_hpr.set(0.0, 0.0f, rotate);
00333     break;
00334   }
00335   state->_scale.set(scale[0], scale[1], 1.0f);
00336   state->_shear.set(shear, 0.0f, 0.0f);
00337   state->_flags = F_components_given | F_hpr_given | F_components_known | F_hpr_known | F_has_components | F_is_2d;
00338   state->check_uniform_scale2d();
00339   return return_new(state);
00340 }
00341 
00342 
00343 ////////////////////////////////////////////////////////////////////
00344 //     Function: TransformState::make_mat3
00345 //       Access: Published, Static
00346 //  Description: Makes a new two-dimensional TransformState with the
00347 //               specified 3x3 transformation matrix.
00348 ////////////////////////////////////////////////////////////////////
00349 CPT(TransformState) TransformState::
00350 make_mat3(const LMatrix3f &mat) {
00351   nassertr(!mat.is_nan(), make_invalid());
00352   // Make a special-case check for the identity matrix.
00353   if (mat == LMatrix3f::ident_mat()) {
00354     return make_identity();
00355   }
00356 
00357   TransformState *state = new TransformState;
00358   state->_mat.set(mat(0, 0), mat(0, 1), 0.0f, mat(0, 2),
00359                   mat(1, 0), mat(1, 1), 0.0f, mat(1, 2),
00360                   0.0f, 0.0f, 1.0f, 0.0f,
00361                   mat(2, 0), mat(2, 1), 0.0f, mat(2, 2));
00362   state->_flags = F_mat_known | F_is_2d;
00363   return return_new(state);
00364 }
00365 
00366 ////////////////////////////////////////////////////////////////////
00367 //     Function: TransformState::set_pos
00368 //       Access: Published
00369 //  Description: Returns a new TransformState object that represents the
00370 //               original TransformState with its pos component
00371 //               replaced with the indicated value.
00372 ////////////////////////////////////////////////////////////////////
00373 CPT(TransformState) TransformState::
00374 set_pos(const LVecBase3f &pos) const {
00375   nassertr(!pos.is_nan(), this);
00376   nassertr(!is_invalid(), this);
00377   if (is_identity() || components_given()) {
00378     // If we started with a componentwise transform, we keep it that
00379     // way.
00380     if (quat_given()) {
00381       return make_pos_quat_scale_shear(pos, get_quat(), get_scale(), get_shear());
00382     } else {
00383       return make_pos_hpr_scale_shear(pos, get_hpr(), get_scale(), get_shear());
00384     }
00385 
00386   } else {
00387     // Otherwise, we have a matrix transform, and we keep it that way.
00388     LMatrix4f mat = get_mat();
00389     mat.set_row(3, pos);
00390     return make_mat(mat);
00391   }
00392 }
00393 
00394 ////////////////////////////////////////////////////////////////////
00395 //     Function: TransformState::set_hpr
00396 //       Access: Published
00397 //  Description: Returns a new TransformState object that represents the
00398 //               original TransformState with its rotation component
00399 //               replaced with the indicated value, if possible.
00400 ////////////////////////////////////////////////////////////////////
00401 CPT(TransformState) TransformState::
00402 set_hpr(const LVecBase3f &hpr) const {
00403   nassertr(!hpr.is_nan(), this);
00404   nassertr(!is_invalid(), this);
00405   //  nassertr(has_components(), this);
00406   return make_pos_hpr_scale_shear(get_pos(), hpr, get_scale(), get_shear());
00407 }
00408 
00409 ////////////////////////////////////////////////////////////////////
00410 //     Function: TransformState::set_quat
00411 //       Access: Published
00412 //  Description: Returns a new TransformState object that represents the
00413 //               original TransformState with its rotation component
00414 //               replaced with the indicated value, if possible.
00415 ////////////////////////////////////////////////////////////////////
00416 CPT(TransformState) TransformState::
00417 set_quat(const LQuaternionf &quat) const {
00418   nassertr(!quat.is_nan(), this);
00419   nassertr(!is_invalid(), this);
00420   //  nassertr(has_components(), this);
00421   return make_pos_quat_scale_shear(get_pos(), quat, get_scale(), get_shear());
00422 }
00423 
00424 ////////////////////////////////////////////////////////////////////
00425 //     Function: TransformState::set_scale
00426 //       Access: Published
00427 //  Description: Returns a new TransformState object that represents the
00428 //               original TransformState with its scale component
00429 //               replaced with the indicated value, if possible.
00430 ////////////////////////////////////////////////////////////////////
00431 CPT(TransformState) TransformState::
00432 set_scale(const LVecBase3f &scale) const {
00433   nassertr(!scale.is_nan(), this);
00434   nassertr(!is_invalid(), this);
00435 
00436   if (is_2d() && scale[0] == scale[1] && scale[1] == scale[2]) {
00437     // Don't inflate from 2-d to 3-d just because we got a uniform
00438     // scale.
00439     return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
00440                                          LVecBase2f(scale[0], scale[0]),
00441                                          get_shear2d());
00442   }
00443 
00444   //  nassertr(has_components(), this);
00445   if (quat_given()) {
00446     return make_pos_quat_scale_shear(get_pos(), get_quat(), scale, get_shear());
00447   } else {
00448     return make_pos_hpr_scale_shear(get_pos(), get_hpr(), scale, get_shear());
00449   }
00450 }
00451 
00452 ////////////////////////////////////////////////////////////////////
00453 //     Function: TransformState::set_shear
00454 //       Access: Published
00455 //  Description: Returns a new TransformState object that represents the
00456 //               original TransformState with its shear component
00457 //               replaced with the indicated value, if possible.
00458 ////////////////////////////////////////////////////////////////////
00459 CPT(TransformState) TransformState::
00460 set_shear(const LVecBase3f &shear) const {
00461   nassertr(!shear.is_nan(), this);
00462   nassertr(!is_invalid(), this);
00463   //  nassertr(has_components(), this);
00464   if (quat_given()) {
00465     return make_pos_quat_scale_shear(get_pos(), get_quat(), get_scale(), shear);
00466   } else {
00467     return make_pos_hpr_scale_shear(get_pos(), get_hpr(), get_scale(), shear);
00468   }
00469 }
00470 
00471 ////////////////////////////////////////////////////////////////////
00472 //     Function: TransformState::set_pos2d
00473 //       Access: Published
00474 //  Description: Returns a new TransformState object that represents the
00475 //               original 2-d TransformState with its pos component
00476 //               replaced with the indicated value.
00477 ////////////////////////////////////////////////////////////////////
00478 CPT(TransformState) TransformState::
00479 set_pos2d(const LVecBase2f &pos) const {
00480   nassertr(!pos.is_nan(), this);
00481   nassertr(!is_invalid(), this);
00482   if (!is_2d()) {
00483     return set_pos(LVecBase3f(pos[0], pos[1], 0.0f));
00484   }
00485 
00486   if (is_identity() || components_given()) {
00487     // If we started with a componentwise transform, we keep it that
00488     // way.
00489     return make_pos_rotate_scale_shear2d(pos, get_rotate2d(), get_scale2d(),
00490                                          get_shear2d());
00491 
00492   } else {
00493     // Otherwise, we have a matrix transform, and we keep it that way.
00494     LMatrix3f mat = get_mat3();
00495     mat.set_row(2, pos);
00496     return make_mat3(mat);
00497   }
00498 }
00499 
00500 ////////////////////////////////////////////////////////////////////
00501 //     Function: TransformState::set_rotate2d
00502 //       Access: Published
00503 //  Description: Returns a new TransformState object that represents the
00504 //               original 2-d TransformState with its rotation component
00505 //               replaced with the indicated value, if possible.
00506 ////////////////////////////////////////////////////////////////////
00507 CPT(TransformState) TransformState::
00508 set_rotate2d(float rotate) const {
00509   nassertr(!cnan(rotate), this);
00510   nassertr(!is_invalid(), this);
00511 
00512   if (!is_2d()) {
00513     switch (get_default_coordinate_system()) {
00514     default:
00515     case CS_zup_right:
00516       return set_hpr(LVecBase3f(rotate, 0.0f, 0.0f));
00517     case CS_zup_left:
00518       return set_hpr(LVecBase3f(-rotate, 0.0f, 0.0f));
00519     case CS_yup_right:
00520       return set_hpr(LVecBase3f(0.0f, 0.0f, -rotate));
00521     case CS_yup_left:
00522       return set_hpr(LVecBase3f(0.0f, 0.0f, rotate));
00523     }
00524   }
00525 
00526   return make_pos_rotate_scale_shear2d(get_pos2d(), rotate, get_scale2d(), 
00527                                        get_shear2d());
00528 }
00529 
00530 ////////////////////////////////////////////////////////////////////
00531 //     Function: TransformState::set_scale2d
00532 //       Access: Published
00533 //  Description: Returns a new TransformState object that represents the
00534 //               original 2-d TransformState with its scale component
00535 //               replaced with the indicated value, if possible.
00536 ////////////////////////////////////////////////////////////////////
00537 CPT(TransformState) TransformState::
00538 set_scale2d(const LVecBase2f &scale) const {
00539   nassertr(!scale.is_nan(), this);
00540   nassertr(!is_invalid(), this);
00541 
00542   if (!is_2d()) {
00543     return set_scale(LVecBase3f(scale[0], scale[1], 1.0f));
00544   }
00545   return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
00546                                        scale, get_shear2d());
00547 }
00548 
00549 ////////////////////////////////////////////////////////////////////
00550 //     Function: TransformState::set_shear2d
00551 //       Access: Published
00552 //  Description: Returns a new TransformState object that represents the
00553 //               original 2-d TransformState with its shear component
00554 //               replaced with the indicated value, if possible.
00555 ////////////////////////////////////////////////////////////////////
00556 CPT(TransformState) TransformState::
00557 set_shear2d(float shear) const {
00558   nassertr(!cnan(shear), this);
00559   nassertr(!is_invalid(), this);
00560   if (!is_2d()) {
00561     return set_shear(LVecBase3f(shear, 0.0f, 0.0f));
00562   }
00563   return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
00564                                        get_scale2d(), shear);
00565 }
00566 
00567 ////////////////////////////////////////////////////////////////////
00568 //     Function: TransformState::compose
00569 //       Access: Published
00570 //  Description: Returns a new TransformState object that represents the
00571 //               composition of this state with the other state.
00572 //
00573 //               The result of this operation is cached, and will be
00574 //               retained as long as both this TransformState object and
00575 //               the other TransformState object continue to exist.
00576 //               Should one of them destruct, the cached entry will be
00577 //               removed, and its pointer will be allowed to destruct
00578 //               as well.
00579 ////////////////////////////////////////////////////////////////////
00580 CPT(TransformState) TransformState::
00581 compose(const TransformState *other) const {
00582   // This method isn't strictly const, because it updates the cache,
00583   // but we pretend that it is because it's only a cache which is
00584   // transparent to the rest of the interface.
00585 
00586   // We handle identity as a trivial special case.
00587   if (is_identity()) {
00588     return other;
00589   }
00590   if (other->is_identity()) {
00591     return this;
00592   }
00593  
00594   // If either transform is invalid, the result is invalid.
00595   if (is_invalid()) {
00596     return this;
00597   }
00598   if (other->is_invalid()) {
00599     return other;
00600   }
00601 
00602 #ifndef NDEBUG
00603   if (!transform_cache) {
00604     return do_compose(other);
00605   }
00606 #endif  // NDEBUG
00607 
00608   LightReMutexHolder holder(*_states_lock);
00609 
00610   // Is this composition already cached?
00611   int index = _composition_cache.find(other);
00612   if (index != -1) {
00613     Composition &comp = ((TransformState *)this)->_composition_cache.modify_data(index);
00614     if (comp._result == (const TransformState *)NULL) {
00615       // Well, it wasn't cached already, but we already had an entry
00616       // (probably created for the reverse direction), so use the same
00617       // entry to store the new result.
00618       CPT(TransformState) result = do_compose(other);
00619       comp._result = result;
00620 
00621       if (result != (const TransformState *)this) {
00622         // See the comments below about the need to up the reference
00623         // count only when the result is not the same as this.
00624         result->cache_ref();
00625       }
00626     }
00627     // Here's the cache!
00628     _cache_stats.inc_hits();
00629     return comp._result;
00630   }
00631   _cache_stats.inc_misses();
00632 
00633   // We need to make a new cache entry, both in this object and in the
00634   // other object.  We make both records so the other TransformState
00635   // object will know to delete the entry from this object when it
00636   // destructs, and vice-versa.
00637 
00638   // The cache entry in this object is the only one that indicates the
00639   // result; the other will be NULL for now.
00640   CPT(TransformState) result = do_compose(other);
00641 
00642   _cache_stats.add_total_size(1);
00643   _cache_stats.inc_adds(_composition_cache.get_size() == 0);
00644 
00645   ((TransformState *)this)->_composition_cache[other]._result = result;
00646 
00647   if (other != this) {
00648     _cache_stats.add_total_size(1);
00649     _cache_stats.inc_adds(other->_composition_cache.get_size() == 0);
00650     ((TransformState *)other)->_composition_cache[this]._result = NULL;
00651   }
00652 
00653   if (result != (const TransformState *)this) {
00654     // If the result of compose() is something other than this,
00655     // explicitly increment the reference count.  We have to be sure
00656     // to decrement it again later, when the composition entry is
00657     // removed from the cache.
00658     result->cache_ref();
00659     
00660     // (If the result was just this again, we still store the
00661     // result, but we don't increment the reference count, since
00662     // that would be a self-referential leak.)
00663   }
00664 
00665   _cache_stats.maybe_report("TransformState");
00666 
00667   return result;
00668 }
00669 
00670 ////////////////////////////////////////////////////////////////////
00671 //     Function: TransformState::invert_compose
00672 //       Access: Published
00673 //  Description: Returns a new TransformState object that represents the
00674 //               composition of this state's inverse with the other
00675 //               state.
00676 //
00677 //               This is similar to compose(), but is particularly
00678 //               useful for computing the relative state of a node as
00679 //               viewed from some other node.
00680 ////////////////////////////////////////////////////////////////////
00681 CPT(TransformState) TransformState::
00682 invert_compose(const TransformState *other) const {
00683   // This method isn't strictly const, because it updates the cache,
00684   // but we pretend that it is because it's only a cache which is
00685   // transparent to the rest of the interface.
00686 
00687   // We handle identity as a trivial special case.
00688   if (is_identity()) {
00689     return other;
00690   }
00691   // Unlike compose(), the case of other->is_identity() is not quite as
00692   // trivial for invert_compose().
00693 
00694   // If either transform is invalid, the result is invalid.
00695   if (is_invalid()) {
00696     return this;
00697   }
00698   if (other->is_invalid()) {
00699     return other;
00700   }
00701 
00702   if (other == this) {
00703     // a->invert_compose(a) always produces identity.
00704     return make_identity();
00705   }
00706 
00707 #ifndef NDEBUG
00708   if (!transform_cache) {
00709     return do_invert_compose(other);
00710   }
00711 #endif  // NDEBUG
00712 
00713   LightReMutexHolder holder(*_states_lock);
00714 
00715   // Is this composition already cached?
00716   int index = _invert_composition_cache.find(other);
00717   if (index != -1) {
00718     Composition &comp = ((TransformState *)this)->_invert_composition_cache.modify_data(index);
00719     if (comp._result == (const TransformState *)NULL) {
00720       // Well, it wasn't cached already, but we already had an entry
00721       // (probably created for the reverse direction), so use the same
00722       // entry to store the new result.
00723       CPT(TransformState) result = do_invert_compose(other);
00724       comp._result = result;
00725 
00726       if (result != (const TransformState *)this) {
00727         // See the comments below about the need to up the reference
00728         // count only when the result is not the same as this.
00729         result->cache_ref();
00730       }
00731     }
00732     // Here's the cache!
00733     _cache_stats.inc_hits();
00734     return comp._result;
00735   }
00736   _cache_stats.inc_misses();
00737 
00738   // We need to make a new cache entry, both in this object and in the
00739   // other object.  We make both records so the other TransformState
00740   // object will know to delete the entry from this object when it
00741   // destructs, and vice-versa.
00742 
00743   // The cache entry in this object is the only one that indicates the
00744   // result; the other will be NULL for now.
00745   CPT(TransformState) result = do_invert_compose(other);
00746 
00747   _cache_stats.add_total_size(1);
00748   _cache_stats.inc_adds(_invert_composition_cache.get_size() == 0);
00749   ((TransformState *)this)->_invert_composition_cache[other]._result = result;
00750 
00751   if (other != this) {
00752     _cache_stats.add_total_size(1);
00753     _cache_stats.inc_adds(other->_invert_composition_cache.get_size() == 0);
00754     ((TransformState *)other)->_invert_composition_cache[this]._result = NULL;
00755   }
00756 
00757   if (result != (const TransformState *)this) {
00758     // If the result of compose() is something other than this,
00759     // explicitly increment the reference count.  We have to be sure
00760     // to decrement it again later, when the composition entry is
00761     // removed from the cache.
00762     result->cache_ref();
00763     
00764     // (If the result was just this again, we still store the
00765     // result, but we don't increment the reference count, since
00766     // that would be a self-referential leak.)
00767   }
00768 
00769   return result;
00770 }
00771 
00772 ////////////////////////////////////////////////////////////////////
00773 //     Function: TransformState::unref
00774 //       Access: Published, Virtual
00775 //  Description: This method overrides ReferenceCount::unref() to
00776 //               check whether the remaining reference count is
00777 //               entirely in the cache, and if so, it checks for and
00778 //               breaks a cycle in the cache involving this object.
00779 //               This is designed to prevent leaks from cyclical
00780 //               references within the cache.
00781 ////////////////////////////////////////////////////////////////////
00782 bool TransformState::
00783 unref() const {
00784   // We always have to grab the lock, since we will definitely need to
00785   // be holding it if we happen to drop the reference count to 0.
00786   LightReMutexHolder holder(*_states_lock);
00787 
00788   if (auto_break_cycles && uniquify_transforms) {
00789     if (get_cache_ref_count() > 0 &&
00790         get_ref_count() == get_cache_ref_count() + 1) {
00791       // If we are about to remove the one reference that is not in the
00792       // cache, leaving only references in the cache, then we need to
00793       // check for a cycle involving this TransformState and break it if
00794       // it exists.
00795       
00796       PStatTimer timer(_transform_break_cycles_pcollector);
00797         
00798       ++_last_cycle_detect;
00799       if (r_detect_cycles(this, this, 1, _last_cycle_detect, NULL)) {
00800         // Ok, we have a cycle.  This will be a leak unless we break the
00801         // cycle by freeing the cache on this object.
00802         if (pgraph_cat.is_debug()) {
00803           pgraph_cat.debug()
00804             << "Breaking cycle involving " << (*this) << "\n";
00805         }
00806         
00807         ((TransformState *)this)->remove_cache_pointers();
00808       } else {
00809         ++_last_cycle_detect;
00810         if (r_detect_reverse_cycles(this, this, 1, _last_cycle_detect, NULL)) {
00811           if (pgraph_cat.is_debug()) {
00812             pgraph_cat.debug()
00813               << "Breaking cycle involving " << (*this) << "\n";
00814           }
00815           
00816           ((TransformState *)this)->remove_cache_pointers();
00817         }
00818       }
00819     }
00820   }
00821 
00822   if (ReferenceCount::unref()) {
00823     // The reference count is still nonzero.
00824     return true;
00825   }
00826 
00827   // The reference count has just reached zero.  Make sure the object
00828   // is removed from the global object pool, before anyone else finds
00829   // it and tries to ref it.
00830   ((TransformState *)this)->release_new();
00831   ((TransformState *)this)->remove_cache_pointers();
00832   
00833   return false;
00834 }
00835 
00836 #ifdef HAVE_PYTHON
00837 ////////////////////////////////////////////////////////////////////
00838 //     Function: TransformState::get_composition_cache
00839 //       Access: Published
00840 //  Description: Returns a list of 2-tuples that represents the
00841 //               composition cache.  For each tuple in the list, the
00842 //               first element is the source transform, and the second
00843 //               is the result transform.  If both are None, there is
00844 //               no entry in the cache at that slot.
00845 //
00846 //               In general, a->compose(source) == result.
00847 //
00848 //               This has no practical value other than for examining
00849 //               the cache for performance analysis.
00850 ////////////////////////////////////////////////////////////////////
00851 PyObject *TransformState::
00852 get_composition_cache() const {
00853   IMPORT_THIS struct Dtool_PyTypedObject Dtool_TransformState;
00854   LightReMutexHolder holder(*_states_lock);
00855   size_t cache_size = _composition_cache.get_size();
00856   PyObject *list = PyList_New(cache_size);
00857 
00858   for (size_t i = 0; i < cache_size; ++i) {
00859     PyObject *tuple = PyTuple_New(2);
00860     PyObject *a, *b;
00861     if (!_composition_cache.has_element(i)) {
00862       a = Py_None;
00863       Py_INCREF(a);
00864       b = Py_None;
00865       Py_INCREF(b);
00866     } else {
00867       const TransformState *source = _composition_cache.get_key(i);
00868       if (source == (TransformState *)NULL) {
00869         a = Py_None;
00870         Py_INCREF(a);
00871       } else {
00872         source->ref();
00873         a = DTool_CreatePyInstanceTyped((void *)source, Dtool_TransformState, 
00874                                         true, true, source->get_type_index());
00875       }
00876       const TransformState *result = _composition_cache.get_data(i)._result;
00877       if (result == (TransformState *)NULL) {
00878         b = Py_None;
00879         Py_INCREF(b);
00880       } else {
00881         result->ref();
00882         b = DTool_CreatePyInstanceTyped((void *)result, Dtool_TransformState, 
00883                                         true, true, result->get_type_index());
00884       }
00885     }
00886     PyTuple_SET_ITEM(tuple, 0, a);
00887     PyTuple_SET_ITEM(tuple, 1, b);
00888 
00889     PyList_SET_ITEM(list, i, tuple);
00890   }
00891 
00892   return list;
00893 }
00894 #endif  // HAVE_PYTHON
00895 
00896 #ifdef HAVE_PYTHON
00897 ////////////////////////////////////////////////////////////////////
00898 //     Function: TransformState::get_invert_composition_cache
00899 //       Access: Published
00900 //  Description: Returns a list of 2-tuples that represents the
00901 //               invert_composition cache.  For each tuple in the list, the
00902 //               first element is the source transform, and the second
00903 //               is the result transform.  If both are None, there is
00904 //               no entry in the cache at that slot.
00905 //
00906 //               In general, a->invert_compose(source) == result.
00907 //
00908 //               This has no practical value other than for examining
00909 //               the cache for performance analysis.
00910 ////////////////////////////////////////////////////////////////////
00911 PyObject *TransformState::
00912 get_invert_composition_cache() const {
00913   IMPORT_THIS struct Dtool_PyTypedObject Dtool_TransformState;
00914   LightReMutexHolder holder(*_states_lock);
00915   size_t cache_size = _invert_composition_cache.get_size();
00916   PyObject *list = PyList_New(cache_size);
00917 
00918   for (size_t i = 0; i < cache_size; ++i) {
00919     PyObject *tuple = PyTuple_New(2);
00920     PyObject *a, *b;
00921     if (!_invert_composition_cache.has_element(i)) {
00922       a = Py_None;
00923       Py_INCREF(a);
00924       b = Py_None;
00925       Py_INCREF(b);
00926     } else {
00927       const TransformState *source = _invert_composition_cache.get_key(i);
00928       if (source == (TransformState *)NULL) {
00929         a = Py_None;
00930         Py_INCREF(a);
00931       } else {
00932         source->ref();
00933         a = DTool_CreatePyInstanceTyped((void *)source, Dtool_TransformState, 
00934                                         true, true, source->get_type_index());
00935       }
00936       const TransformState *result = _invert_composition_cache.get_data(i)._result;
00937       if (result == (TransformState *)NULL) {
00938         b = Py_None;
00939         Py_INCREF(b);
00940       } else {
00941         result->ref();
00942         b = DTool_CreatePyInstanceTyped((void *)result, Dtool_TransformState, 
00943                                         true, true, result->get_type_index());
00944       }
00945     }
00946     PyTuple_SET_ITEM(tuple, 0, a);
00947     PyTuple_SET_ITEM(tuple, 1, b);
00948 
00949     PyList_SET_ITEM(list, i, tuple);
00950   }
00951 
00952   return list;
00953 }
00954 #endif  // HAVE_PYTHON
00955 
00956 ////////////////////////////////////////////////////////////////////
00957 //     Function: TransformState::output
00958 //       Access: Published
00959 //  Description: 
00960 ////////////////////////////////////////////////////////////////////
00961 void TransformState::
00962 output(ostream &out) const {
00963   out << "T:";
00964   if (is_invalid()) {
00965     out << "(invalid)";
00966 
00967   } else if (is_identity()) {
00968     out << "(identity)";
00969 
00970   } else if (has_components()) {
00971     bool output_hpr = !get_hpr().almost_equal(LVecBase3f(0.0f, 0.0f, 0.0f));
00972 
00973     if (!components_given()) {
00974       // A leading "m" indicates the transform was described as a full
00975       // matrix, and we are decomposing it for the benefit of the
00976       // user.
00977       out << "m";
00978 
00979     } else if (output_hpr && quat_given()) {
00980       // A leading "q" indicates that the pos, scale, and shear are
00981       // exactly as specified, but the rotation was described as a
00982       // quaternion, and we are decomposing that to hpr for the
00983       // benefit of the user.
00984       out << "q";
00985     }
00986 
00987     char lead = '(';
00988     if (is_2d()) {
00989       if (!get_pos2d().almost_equal(LVecBase2f(0.0f, 0.0f))) {
00990         out << lead << "pos " << get_pos2d();
00991         lead = ' ';
00992       }
00993       if (output_hpr) {
00994         out << lead << "rotate " << get_rotate2d();
00995         lead = ' ';
00996       }
00997       if (!get_scale2d().almost_equal(LVecBase2f(1.0f, 1.0f))) {
00998         if (has_uniform_scale()) {
00999           out << lead << "scale " << get_uniform_scale();
01000           lead = ' ';
01001         } else {
01002           out << lead << "scale " << get_scale2d();
01003           lead = ' ';
01004         }
01005       }
01006       if (has_nonzero_shear()) {
01007         out << lead << "shear " << get_shear2d();
01008         lead = ' ';
01009       }
01010     } else {
01011       if (!get_pos().almost_equal(LVecBase3f(0.0f, 0.0f, 0.0f))) {
01012         out << lead << "pos " << get_pos();
01013         lead = ' ';
01014       }
01015       if (output_hpr) {
01016         out << lead << "hpr " << get_hpr();
01017         lead = ' ';
01018       }
01019       if (!get_scale().almost_equal(LVecBase3f(1.0f, 1.0f, 1.0f))) {
01020         if (has_uniform_scale()) {
01021           out << lead << "scale " << get_uniform_scale();
01022           lead = ' ';
01023         } else {
01024           out << lead << "scale " << get_scale();
01025           lead = ' ';
01026         }
01027       }
01028       if (has_nonzero_shear()) {
01029         out << lead << "shear " << get_shear();
01030         lead = ' ';
01031       }
01032     }
01033     if (lead == '(') {
01034       out << "(almost identity)";
01035     } else {
01036       out << ")";
01037     }
01038 
01039   } else {
01040     if (is_2d()) {
01041       out << get_mat3();
01042     } else {
01043       out << get_mat();
01044     }
01045   }
01046 }
01047 
01048 ////////////////////////////////////////////////////////////////////
01049 //     Function: TransformState::write
01050 //       Access: Published
01051 //  Description: 
01052 ////////////////////////////////////////////////////////////////////
01053 void TransformState::
01054 write(ostream &out, int indent_level) const {
01055   indent(out, indent_level) << *this << "\n";
01056 }
01057 
01058 ////////////////////////////////////////////////////////////////////
01059 //     Function: TransformState::write_composition_cache
01060 //       Access: Published
01061 //  Description: Writes a brief description of the composition cache
01062 //               and invert composition cache to the indicated
01063 //               ostream.  This is not useful except for performance
01064 //               analysis, to examine the cache structure.
01065 ////////////////////////////////////////////////////////////////////
01066 void TransformState::
01067 write_composition_cache(ostream &out, int indent_level) const {
01068   indent(out, indent_level + 2) << _composition_cache << "\n";
01069   indent(out, indent_level + 2) << _invert_composition_cache << "\n";
01070 }
01071 
01072 ////////////////////////////////////////////////////////////////////
01073 //     Function: TransformState::get_num_states
01074 //       Access: Published, Static
01075 //  Description: Returns the total number of unique TransformState
01076 //               objects allocated in the world.  This will go up and
01077 //               down during normal operations.
01078 ////////////////////////////////////////////////////////////////////
01079 int TransformState::
01080 get_num_states() {
01081   if (_states == (States *)NULL) {
01082     return 0;
01083   }
01084   LightReMutexHolder holder(*_states_lock);
01085   return _states->size();
01086 }
01087 
01088 ////////////////////////////////////////////////////////////////////
01089 //     Function: TransformState::get_num_unused_states
01090 //       Access: Published, Static
01091 //  Description: Returns the total number of TransformState objects that
01092 //               have been allocated but have no references outside of
01093 //               the internal TransformState cache.
01094 //
01095 //               A nonzero return value is not necessarily indicative
01096 //               of leaked references; it is normal for two
01097 //               TransformState objects, both of which have references
01098 //               held outside the cache, to have the result of their
01099 //               composition stored within the cache.  This result
01100 //               will be retained within the cache until one of the
01101 //               base TransformStates is released.
01102 //
01103 //               Use list_cycles() to get an idea of the number of
01104 //               actual "leaked" TransformState objects.
01105 ////////////////////////////////////////////////////////////////////
01106 int TransformState::
01107 get_num_unused_states() {
01108   if (_states == (States *)NULL) {
01109     return 0;
01110   }
01111   LightReMutexHolder holder(*_states_lock);
01112 
01113   // First, we need to count the number of times each TransformState
01114   // object is recorded in the cache.  We could just trust
01115   // get_cache_ref_count(), but we'll be extra cautious for now.
01116   typedef pmap<const TransformState *, int> StateCount;
01117   StateCount state_count;
01118 
01119   States::iterator si;
01120   for (si = _states->begin(); si != _states->end(); ++si) {
01121     const TransformState *state = (*si);
01122 
01123     int i;
01124     int cache_size = state->_composition_cache.get_size();
01125     for (i = 0; i < cache_size; ++i) {
01126       if (state->_composition_cache.has_element(i)) {
01127         const TransformState *result = state->_composition_cache.get_data(i)._result;
01128         if (result != (const TransformState *)NULL && result != state) {
01129           // Here's a TransformState that's recorded in the cache.
01130           // Count it.
01131           pair<StateCount::iterator, bool> ir =
01132             state_count.insert(StateCount::value_type(result, 1));
01133           if (!ir.second) {
01134             // If the above insert operation fails, then it's already in
01135             // the cache; increment its value.
01136             (*(ir.first)).second++;
01137           }
01138         }
01139       }
01140     }
01141     cache_size = state->_invert_composition_cache.get_size();
01142     for (i = 0; i < cache_size; ++i) {
01143       if (state->_invert_composition_cache.has_element(i)) {
01144         const TransformState *result = state->_invert_composition_cache.get_data(i)._result;
01145         if (result != (const TransformState *)NULL && result != state) {
01146           pair<StateCount::iterator, bool> ir =
01147             state_count.insert(StateCount::value_type(result, 1));
01148           if (!ir.second) {
01149             (*(ir.first)).second++;
01150           }
01151         }
01152       }
01153     }
01154   }
01155 
01156   // Now that we have the appearance count of each TransformState
01157   // object, we can tell which ones are unreferenced outside of the
01158   // TransformState cache, by comparing these to the reference counts.
01159   int num_unused = 0;
01160 
01161   StateCount::iterator sci;
01162   for (sci = state_count.begin(); sci != state_count.end(); ++sci) {
01163     const TransformState *state = (*sci).first;
01164     int count = (*sci).second;
01165     nassertr(count == state->get_cache_ref_count(), num_unused);
01166     nassertr(count <= state->get_ref_count(), num_unused);
01167     if (count == state->get_ref_count()) {
01168       num_unused++;
01169 
01170       if (pgraph_cat.is_debug()) {
01171         pgraph_cat.debug()
01172           << "Unused state: " << (void *)state << ":" 
01173           << state->get_ref_count() << " =\n";
01174         state->write(pgraph_cat.debug(false), 2);
01175       }
01176     }
01177   }
01178 
01179   return num_unused;
01180 }
01181 
01182 ////////////////////////////////////////////////////////////////////
01183 //     Function: TransformState::clear_cache
01184 //       Access: Published, Static
01185 //  Description: Empties the cache of composed TransformStates.  This
01186 //               makes every TransformState forget what results when
01187 //               it is composed with other TransformStates.
01188 //
01189 //               This will eliminate any TransformState objects that
01190 //               have been allocated but have no references outside of
01191 //               the internal TransformState map.  It will not
01192 //               eliminate TransformState objects that are still in
01193 //               use.
01194 //
01195 //               Nowadays, this method should not be necessary, as
01196 //               reference-count cycles in the composition cache
01197 //               should be automatically detected and broken.
01198 //
01199 //               The return value is the number of TransformStates
01200 //               freed by this operation.
01201 ////////////////////////////////////////////////////////////////////
01202 int TransformState::
01203 clear_cache() {
01204   if (_states == (States *)NULL) {
01205     return 0;
01206   }
01207   LightReMutexHolder holder(*_states_lock);
01208 
01209   PStatTimer timer(_cache_update_pcollector);
01210   int orig_size = _states->size();
01211 
01212   // First, we need to copy the entire set of states to a temporary
01213   // vector, reference-counting each object.  That way we can walk
01214   // through the copy, without fear of dereferencing (and deleting)
01215   // the objects in the map as we go.
01216   {
01217     typedef pvector< CPT(TransformState) > TempStates;
01218     TempStates temp_states;
01219     temp_states.reserve(orig_size);
01220 
01221     copy(_states->begin(), _states->end(),
01222          back_inserter(temp_states));
01223 
01224     // Now it's safe to walk through the list, destroying the cache
01225     // within each object as we go.  Nothing will be destructed till
01226     // we're done.
01227     TempStates::iterator ti;
01228     for (ti = temp_states.begin(); ti != temp_states.end(); ++ti) {
01229       TransformState *state = (TransformState *)(*ti).p();
01230 
01231       int i;
01232       int cache_size = state->_composition_cache.get_size();
01233       for (i = 0; i < cache_size; ++i) {
01234         if (state->_composition_cache.has_element(i)) {
01235           const TransformState *result = state->_composition_cache.get_data(i)._result;
01236           if (result != (const TransformState *)NULL && result != state) {
01237             result->cache_unref();
01238             nassertr(result->get_ref_count() > 0, 0);
01239           }
01240         }
01241       }
01242       _cache_stats.add_total_size(-state->_composition_cache.get_num_entries());
01243       state->_composition_cache.clear();
01244 
01245       cache_size = state->_invert_composition_cache.get_size();
01246       for (i = 0; i < cache_size; ++i) {
01247         if (state->_invert_composition_cache.has_element(i)) {
01248           const TransformState *result = state->_invert_composition_cache.get_data(i)._result;
01249           if (result != (const TransformState *)NULL && result != state) {
01250             result->cache_unref();
01251             nassertr(result->get_ref_count() > 0, 0);
01252           }
01253         }
01254       }
01255       _cache_stats.add_total_size(-state->_invert_composition_cache.get_num_entries());
01256       state->_invert_composition_cache.clear();
01257     }
01258 
01259     // Once this block closes and the temp_states object goes away,
01260     // all the destruction will begin.  Anything whose reference was
01261     // held only within the various objects' caches will go away.
01262   }
01263 
01264   int new_size = _states->size();
01265   return orig_size - new_size;
01266 }
01267 
01268 ////////////////////////////////////////////////////////////////////
01269 //     Function: TransformState::list_cycles
01270 //       Access: Published, Static
01271 //  Description: Detects all of the reference-count cycles in the
01272 //               cache and reports them to standard output.
01273 //
01274 //               These cycles may be inadvertently created when state
01275 //               compositions cycle back to a starting point.
01276 //               Nowadays, these cycles should be automatically
01277 //               detected and broken, so this method should never list
01278 //               any cycles unless there is a bug in that detection
01279 //               logic.
01280 //
01281 //               The cycles listed here are not leaks in the strictest
01282 //               sense of the word, since they can be reclaimed by a
01283 //               call to clear_cache(); but they will not be reclaimed
01284 //               automatically.
01285 ////////////////////////////////////////////////////////////////////
01286 void TransformState::
01287 list_cycles(ostream &out) {
01288   if (_states == (States *)NULL) {
01289     return;
01290   }
01291   LightReMutexHolder holder(*_states_lock);
01292 
01293   typedef pset<const TransformState *> VisitedStates;
01294   VisitedStates visited;
01295   CompositionCycleDesc cycle_desc;
01296 
01297   States::iterator si;
01298   for (si = _states->begin(); si != _states->end(); ++si) {
01299     const TransformState *state = (*si);
01300 
01301     bool inserted = visited.insert(state).second;
01302     if (inserted) {
01303       ++_last_cycle_detect;
01304       if (r_detect_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
01305         // This state begins a cycle.
01306         CompositionCycleDesc::reverse_iterator csi;
01307 
01308         out << "\nCycle detected of length " << cycle_desc.size() + 1 << ":\n"
01309             << "state " << (void *)state << ":" << state->get_ref_count()
01310             << " =\n";
01311         state->write(out, 2);
01312         for (csi = cycle_desc.rbegin(); csi != cycle_desc.rend(); ++csi) {
01313           const CompositionCycleDescEntry &entry = (*csi);
01314           if (entry._inverted) {
01315             out << "invert composed with ";
01316           } else {
01317             out << "composed with ";
01318           }
01319           out << (const void *)entry._obj << ":" << entry._obj->get_ref_count()
01320               << " " << *entry._obj << "\n"
01321               << "produces " << (const void *)entry._result << ":"
01322               << entry._result->get_ref_count() << " =\n";
01323           entry._result->write(out, 2);
01324           visited.insert(entry._result);
01325         }
01326 
01327         cycle_desc.clear();
01328       } else {
01329         ++_last_cycle_detect;
01330         if (r_detect_reverse_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
01331           // This state begins a cycle.
01332           CompositionCycleDesc::iterator csi;
01333           
01334           out << "\nReverse cycle detected of length " << cycle_desc.size() + 1 << ":\n"
01335               << "state ";
01336           for (csi = cycle_desc.begin(); csi != cycle_desc.end(); ++csi) {
01337             const CompositionCycleDescEntry &entry = (*csi);
01338             out << (const void *)entry._result << ":"
01339                 << entry._result->get_ref_count() << " =\n";
01340             entry._result->write(out, 2);
01341             out << (const void *)entry._obj << ":"
01342                 << entry._obj->get_ref_count() << " =\n";
01343             entry._obj->write(out, 2);
01344             visited.insert(entry._result);
01345           }
01346           out << (void *)state << ":"
01347               << state->get_ref_count() << " =\n";
01348           state->write(out, 2);
01349           
01350           cycle_desc.clear();
01351         }
01352       }
01353     }
01354   }
01355 }
01356 
01357 
01358 ////////////////////////////////////////////////////////////////////
01359 //     Function: TransformState::list_states
01360 //       Access: Published, Static
01361 //  Description: Lists all of the TransformStates in the cache to the
01362 //               output stream, one per line.  This can be quite a lot
01363 //               of output if the cache is large, so be prepared.
01364 ////////////////////////////////////////////////////////////////////
01365 void TransformState::
01366 list_states(ostream &out) {
01367   if (_states == (States *)NULL) {
01368     out << "0 states:\n";
01369     return;
01370   }
01371   LightReMutexHolder holder(*_states_lock);
01372 
01373   out << _states->size() << " states:\n";
01374   States::const_iterator si;
01375   for (si = _states->begin(); si != _states->end(); ++si) {
01376     const TransformState *state = (*si);
01377     state->write(out, 2);
01378   }
01379 }
01380 
01381 ////////////////////////////////////////////////////////////////////
01382 //     Function: TransformState::validate_states
01383 //       Access: Published, Static
01384 //  Description: Ensures that the cache is still stored in sorted
01385 //               order, and that none of the cache elements have been
01386 //               inadvertently deleted.  Returns true if so, false if
01387 //               there is a problem (which implies someone has
01388 //               modified one of the supposedly-const TransformState
01389 //               objects).
01390 ////////////////////////////////////////////////////////////////////
01391 bool TransformState::
01392 validate_states() {
01393   if (_states == (States *)NULL) {
01394     return true;
01395   }
01396 
01397   PStatTimer timer(_transform_validate_pcollector);
01398 
01399   LightReMutexHolder holder(*_states_lock);
01400   if (_states->empty()) {
01401     return true;
01402   }
01403 
01404   States::const_iterator si = _states->begin();
01405   States::const_iterator snext = si;
01406   ++snext;
01407   nassertr((*si)->get_ref_count() > 0, false);
01408   while (snext != _states->end()) {
01409     if (!(*(*si) < *(*snext))) {
01410       pgraph_cat.error()
01411         << "TransformStates out of order!\n";
01412       (*si)->write(pgraph_cat.error(false), 2);
01413       (*snext)->write(pgraph_cat.error(false), 2);
01414       return false;
01415     }
01416     if ((*(*snext) < *(*si))) {
01417       pgraph_cat.error()
01418         << "TransformState::operator < not defined properly!\n";
01419       pgraph_cat.error(false)
01420         << "a < b: " << (*(*si) < *(*snext)) << "\n";
01421       pgraph_cat.error(false)
01422         << "b < a: " << (*(*snext) < *(*si)) << "\n";
01423       (*si)->write(pgraph_cat.error(false), 2);
01424       (*snext)->write(pgraph_cat.error(false), 2);
01425       return false;
01426     }
01427     si = snext;
01428     ++snext;
01429     nassertr((*si)->get_ref_count() > 0, false);
01430   }
01431 
01432   return true;
01433 }
01434 
01435 #ifdef HAVE_PYTHON
01436 ////////////////////////////////////////////////////////////////////
01437 //     Function: TransformState::get_states
01438 //       Access: Published, Static
01439 //  Description: Returns a list of all of the TransformState objects
01440 //               in the state cache.  The order of elements in this
01441 //               cache is arbitrary.
01442 ////////////////////////////////////////////////////////////////////
01443 PyObject *TransformState::
01444 get_states() {
01445   IMPORT_THIS struct Dtool_PyTypedObject Dtool_TransformState;
01446   if (_states == (States *)NULL) {
01447     return PyList_New(0);
01448   }
01449   LightReMutexHolder holder(*_states_lock);
01450 
01451   size_t num_states = _states->size();
01452   PyObject *list = PyList_New(num_states);
01453   States::const_iterator si;
01454   size_t i;
01455   for (si = _states->begin(), i = 0; si != _states->end(); ++si, ++i) {
01456     nassertr(i < num_states, list);
01457     const TransformState *state = (*si);
01458     state->ref();
01459     PyObject *a = 
01460       DTool_CreatePyInstanceTyped((void *)state, Dtool_TransformState, 
01461                                   true, true, state->get_type_index());
01462     PyList_SET_ITEM(list, i, a);
01463   }
01464   nassertr(i == num_states, list);
01465   return list;
01466 }
01467 #endif  // HAVE_PYTHON
01468 
01469 ////////////////////////////////////////////////////////////////////
01470 //     Function: TransformState::init_states
01471 //       Access: Public, Static
01472 //  Description: Make sure the global _states map is allocated.  This
01473 //               only has to be done once.  We could make this map
01474 //               static, but then we run into problems if anyone
01475 //               creates a TransformState object at static init time;
01476 //               it also seems to cause problems when the Panda shared
01477 //               library is unloaded at application exit time.
01478 ////////////////////////////////////////////////////////////////////
01479 void TransformState::
01480 init_states() {
01481   _states = new States;
01482 
01483   // TODO: we should have a global Panda mutex to allow us to safely
01484   // create _states_lock without a startup race condition.  For the
01485   // meantime, this is OK because we guarantee that this method is
01486   // called at static init time, presumably when there is still only
01487   // one thread in the world.
01488   _states_lock = new LightReMutex("TransformState::_states_lock");
01489   _cache_stats.init();
01490   nassertv(Thread::get_current_thread() == Thread::get_main_thread());
01491 }
01492   
01493 ////////////////////////////////////////////////////////////////////
01494 //     Function: TransformState::return_new
01495 //       Access: Private, Static
01496 //  Description: This function is used to share a common TransformState
01497 //               pointer for all equivalent TransformState objects.
01498 //
01499 //               This is different from return_unique() in that it
01500 //               does not actually guarantee a unique pointer, unless
01501 //               uniquify-transforms is set.
01502 ////////////////////////////////////////////////////////////////////
01503 CPT(TransformState) TransformState::
01504 return_new(TransformState *state) {
01505   nassertr(state != (TransformState *)NULL, state);
01506   if (!uniquify_transforms && !state->is_identity()) {
01507     return state;
01508   }
01509 
01510   return return_unique(state);
01511 }
01512 
01513 ////////////////////////////////////////////////////////////////////
01514 //     Function: TransformState::return_unique
01515 //       Access: Private, Static
01516 //  Description: This function is used to share a common TransformState
01517 //               pointer for all equivalent TransformState objects.
01518 //
01519 //               See the similar logic in RenderState.  The idea is to
01520 //               create a new TransformState object and pass it
01521 //               through this function, which will share the pointer
01522 //               with a previously-created TransformState object if it
01523 //               is equivalent.
01524 ////////////////////////////////////////////////////////////////////
01525 CPT(TransformState) TransformState::
01526 return_unique(TransformState *state) {
01527   nassertr(state != (TransformState *)NULL, state);
01528 
01529 #ifndef NDEBUG
01530   if (!transform_cache) {
01531     return state;
01532   }
01533 #endif
01534 
01535 #ifndef NDEBUG
01536   if (paranoid_const) {
01537     nassertr(validate_states(), state);
01538   }
01539 #endif
01540 
01541   PStatTimer timer(_transform_new_pcollector);
01542 
01543   LightReMutexHolder holder(*_states_lock);
01544 
01545   if (state->_saved_entry != _states->end()) {
01546     // This state is already in the cache.
01547     nassertr(_states->find(state) == state->_saved_entry, state);
01548     return state;
01549   }
01550 
01551   // Save the state in a local PointerTo so that it will be freed at
01552   // the end of this function if no one else uses it.
01553   CPT(TransformState) pt_state = state;
01554 
01555   pair<States::iterator, bool> result = _states->insert(state);
01556   if (result.second) {
01557     // The state was inserted; save the iterator and return the
01558     // input state.
01559     state->_saved_entry = result.first;
01560     return pt_state;
01561   }
01562 
01563   // The state was not inserted; there must be an equivalent one
01564   // already in the set.  Return that one.
01565   return *(result.first);
01566 }
01567 
01568 ////////////////////////////////////////////////////////////////////
01569 //     Function: TransformState::do_compose
01570 //       Access: Private
01571 //  Description: The private implemention of compose(); this actually
01572 //               composes two TransformStates, without bothering with the
01573 //               cache.
01574 ////////////////////////////////////////////////////////////////////
01575 CPT(TransformState) TransformState::
01576 do_compose(const TransformState *other) const {
01577   PStatTimer timer(_transform_compose_pcollector);
01578 
01579   nassertr((_flags & F_is_invalid) == 0, this);
01580   nassertr((other->_flags & F_is_invalid) == 0, other);
01581 
01582   if (compose_componentwise && 
01583       has_uniform_scale() && 
01584       !has_nonzero_shear() && !other->has_nonzero_shear() &&
01585       ((components_given() && other->has_components()) ||
01586        (other->components_given() && has_components()))) {
01587     // We will do this operation componentwise if *either* transform
01588     // was given componentwise (and there is no non-uniform scale in
01589     // the way).
01590 
01591     CPT(TransformState) result;
01592     if (is_2d() && other->is_2d()) {
01593       // Do a 2-d compose.
01594       LVecBase2f pos = get_pos2d();
01595       float rotate = get_rotate2d();
01596       LQuaternionf quat = get_norm_quat();
01597       float scale = get_uniform_scale();
01598 
01599       LPoint3f op = quat.xform(other->get_pos());
01600       pos += LVecBase2f(op[0], op[1]) * scale;
01601 
01602       rotate += other->get_rotate2d();
01603       LVecBase2f new_scale = other->get_scale2d() * scale;
01604       
01605       result = make_pos_rotate_scale2d(pos, rotate, new_scale);
01606 
01607     } else {
01608       // A normal 3-d compose.
01609       LVecBase3f pos = get_pos();
01610       LQuaternionf quat = get_norm_quat();
01611       float scale = get_uniform_scale();
01612       
01613       pos += quat.xform(other->get_pos()) * scale;
01614       quat = other->get_norm_quat() * quat;
01615       LVecBase3f new_scale = other->get_scale() * scale;
01616       
01617       result = make_pos_quat_scale(pos, quat, new_scale);
01618     }
01619       
01620 #ifndef NDEBUG
01621     if (paranoid_compose) {
01622       // Now verify against the matrix.
01623       LMatrix4f new_mat;
01624       new_mat.multiply(other->get_mat(), get_mat());
01625       if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
01626         CPT(TransformState) correct = make_mat(new_mat);
01627         pgraph_cat.warning()
01628           << "Componentwise composition of " << *this << " and " << *other
01629           << " produced:\n"
01630           << *result << "\n  instead of:\n" << *correct << "\n";
01631         result = correct;
01632       }
01633     }
01634 #endif  // NDEBUG
01635 
01636     return result;
01637   }
01638 
01639   // Do the operation with matrices.
01640   if (is_2d() && other->is_2d()) {
01641     LMatrix3f new_mat = other->get_mat3() * get_mat3();
01642     return make_mat3(new_mat);
01643   } else {
01644     LMatrix4f new_mat;
01645     new_mat.multiply(other->get_mat(), get_mat());
01646     return make_mat(new_mat);
01647   }
01648 }
01649 
01650 ////////////////////////////////////////////////////////////////////
01651 //     Function: TransformState::do_invert_compose
01652 //       Access: Private
01653 //  Description: The private implemention of invert_compose().
01654 ////////////////////////////////////////////////////////////////////
01655 CPT(TransformState) TransformState::
01656 do_invert_compose(const TransformState *other) const {
01657   PStatTimer timer(_transform_invert_pcollector);
01658 
01659   nassertr((_flags & F_is_invalid) == 0, this);
01660   nassertr((other->_flags & F_is_invalid) == 0, other);
01661 
01662   if (compose_componentwise && 
01663       has_uniform_scale() && 
01664       !has_nonzero_shear() && !other->has_nonzero_shear() &&
01665       ((components_given() && other->has_components()) ||
01666        (other->components_given() && has_components()))) {
01667     // We will do this operation componentwise if *either* transform
01668     // was given componentwise (and there is no non-uniform scale in
01669     // the way).
01670 
01671     CPT(TransformState) result;
01672     if (is_2d() && other->is_2d()) {
01673       // Do a 2-d invert compose.
01674       LVecBase2f pos = get_pos2d();
01675       float rotate = get_rotate2d();
01676       LQuaternionf quat = get_norm_quat();
01677       float scale = get_uniform_scale();
01678       
01679       // First, invert our own transform.
01680       if (scale == 0.0f) {
01681         ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
01682         return make_invalid();
01683       }
01684       scale = 1.0f / scale;
01685       quat.invert_in_place();
01686       rotate = -rotate;
01687       LVecBase3f mp = quat.xform(-LVecBase3f(pos[0], pos[1], 0.0f));
01688       pos = LVecBase2f(mp[0], mp[1]) * scale;
01689       LVecBase2f new_scale(scale, scale);
01690       
01691       // Now compose the inverted transform with the other transform.
01692       if (!other->is_identity()) {
01693         LPoint3f op = quat.xform(other->get_pos());
01694         pos += LVecBase2f(op[0], op[1]) * scale;
01695 
01696         rotate += other->get_rotate2d();
01697         new_scale = other->get_scale2d() * scale;
01698       }
01699 
01700       result = make_pos_rotate_scale2d(pos, rotate, new_scale);
01701 
01702     } else {
01703       // Do a normal, 3-d invert compose.
01704       LVecBase3f pos = get_pos();
01705       LQuaternionf quat = get_norm_quat();
01706       float scale = get_uniform_scale();
01707       
01708       // First, invert our own transform.
01709       if (scale == 0.0f) {
01710         ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
01711         return make_invalid();
01712       }
01713       scale = 1.0f / scale;
01714       quat.invert_in_place();
01715       pos = quat.xform(-pos) * scale;
01716       LVecBase3f new_scale(scale, scale, scale);
01717       
01718       // Now compose the inverted transform with the other transform.
01719       if (!other->is_identity()) {
01720         pos += quat.xform(other->get_pos()) * scale;
01721         quat = other->get_norm_quat() * quat;
01722         new_scale = other->get_scale() * scale;
01723       }
01724 
01725       result = make_pos_quat_scale(pos, quat, new_scale);
01726     }
01727 
01728 #ifndef NDEBUG
01729     if (paranoid_compose) {
01730       // Now verify against the matrix.
01731       if (is_singular()) {
01732         pgraph_cat.warning()
01733           << "Unexpected singular matrix found for " << *this << "\n";
01734       } else {
01735         nassertr(_inv_mat != (LMatrix4f *)NULL, make_invalid());
01736         LMatrix4f new_mat;
01737         new_mat.multiply(other->get_mat(), *_inv_mat);
01738         if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
01739           CPT(TransformState) correct = make_mat(new_mat);
01740           pgraph_cat.warning()
01741             << "Componentwise invert-composition of " << *this << " and " << *other
01742             << " produced:\n"
01743             << *result << "\n  instead of:\n" << *correct << "\n";
01744           result = correct;
01745         }
01746       }
01747     }
01748 #endif  // NDEBUG
01749 
01750     return result;
01751   }
01752 
01753   if (is_singular()) {
01754     return make_invalid();
01755   }
01756 
01757   // Now that is_singular() has returned false, we can assume that
01758   // _inv_mat has been allocated and filled in.
01759   nassertr(_inv_mat != (LMatrix4f *)NULL, make_invalid());
01760 
01761   if (is_2d() && other->is_2d()) {
01762     const LMatrix4f &i = *_inv_mat;
01763     LMatrix3f inv3(i(0, 0), i(0, 1), i(0, 3),
01764                    i(1, 0), i(1, 1), i(1, 3),
01765                    i(3, 0), i(3, 1), i(3, 3));
01766     if (other->is_identity()) {
01767       return make_mat3(inv3);
01768     } else {
01769       return make_mat3(other->get_mat3() * inv3);
01770     }
01771   } else {
01772     if (other->is_identity()) {
01773       return make_mat(*_inv_mat);
01774     } else {
01775       return make_mat(other->get_mat() * (*_inv_mat));
01776     }
01777   }
01778 }
01779 
01780 ////////////////////////////////////////////////////////////////////
01781 //     Function: TransformState::r_detect_cycles
01782 //       Access: Private, Static
01783 //  Description: Detects whether there is a cycle in the cache that
01784 //               begins with the indicated state.  Returns true if at
01785 //               least one cycle is found, false if this state is not
01786 //               part of any cycles.  If a cycle is found and
01787 //               cycle_desc is not NULL, then cycle_desc is filled in
01788 //               with the list of the steps of the cycle, in reverse
01789 //               order.
01790 ////////////////////////////////////////////////////////////////////
01791 bool TransformState::
01792 r_detect_cycles(const TransformState *start_state,
01793                 const TransformState *current_state,
01794                 int length, UpdateSeq this_seq,
01795                 TransformState::CompositionCycleDesc *cycle_desc) {
01796   if (current_state->_cycle_detect == this_seq) {
01797     // We've already seen this state; therefore, we've found a cycle.
01798 
01799     // However, we only care about cycles that return to the starting
01800     // state and involve more than two steps.  If only one or two
01801     // nodes are involved, it doesn't represent a memory leak, so no
01802     // problem there.
01803     return (current_state == start_state && length > 2);
01804   }
01805   ((TransformState *)current_state)->_cycle_detect = this_seq;
01806 
01807   int i;
01808   int cache_size = current_state->_composition_cache.get_size();
01809   for (i = 0; i < cache_size; ++i) {
01810     if (current_state->_composition_cache.has_element(i)) {
01811       const TransformState *result = current_state->_composition_cache.get_data(i)._result;
01812       if (result != (const TransformState *)NULL) {
01813         if (r_detect_cycles(start_state, result, length + 1, 
01814                             this_seq, cycle_desc)) {
01815           // Cycle detected.
01816           if (cycle_desc != (CompositionCycleDesc *)NULL) {
01817             const TransformState *other = current_state->_composition_cache.get_key(i);
01818             CompositionCycleDescEntry entry(other, result, false);
01819             cycle_desc->push_back(entry);
01820           }
01821           return true;
01822         }
01823       }
01824     }
01825   }
01826 
01827   cache_size = current_state->_invert_composition_cache.get_size();
01828   for (i = 0; i < cache_size; ++i) {
01829     if (current_state->_invert_composition_cache.has_element(i)) {
01830       const TransformState *result = current_state->_invert_composition_cache.get_data(i)._result;
01831       if (result != (const TransformState *)NULL) {
01832         if (r_detect_cycles(start_state, result, length + 1,
01833                             this_seq, cycle_desc)) {
01834           // Cycle detected.
01835           if (cycle_desc != (CompositionCycleDesc *)NULL) {
01836             const TransformState *other = current_state->_invert_composition_cache.get_key(i);
01837             CompositionCycleDescEntry entry(other, result, true);
01838             cycle_desc->push_back(entry);
01839           }
01840           return true;
01841         }
01842       }
01843     }
01844   }
01845 
01846   // No cycle detected.
01847   return false;
01848 }
01849 
01850 ////////////////////////////////////////////////////////////////////
01851 //     Function: TransformState::r_detect_reverse_cycles
01852 //       Access: Private, Static
01853 //  Description: Works the same as r_detect_cycles, but checks for
01854 //               cycles in the reverse direction along the cache
01855 //               chain.  (A cycle may appear in either direction, and
01856 //               we must check both.)
01857 ////////////////////////////////////////////////////////////////////
01858 bool TransformState::
01859 r_detect_reverse_cycles(const TransformState *start_state,
01860                         const TransformState *current_state,
01861                         int length, UpdateSeq this_seq,
01862                         TransformState::CompositionCycleDesc *cycle_desc) {
01863   if (current_state->_cycle_detect == this_seq) {
01864     // We've already seen this state; therefore, we've found a cycle.
01865 
01866     // However, we only care about cycles that return to the starting
01867     // state and involve more than two steps.  If only one or two
01868     // nodes are involved, it doesn't represent a memory leak, so no
01869     // problem there.
01870     return (current_state == start_state && length > 2);
01871   }
01872   ((TransformState *)current_state)->_cycle_detect = this_seq;
01873 
01874   int i;
01875   int cache_size = current_state->_composition_cache.get_size();
01876   for (i = 0; i < cache_size; ++i) {
01877     if (current_state->_composition_cache.has_element(i)) {
01878       const TransformState *other = current_state->_composition_cache.get_key(i);
01879       if (other != current_state) {
01880         int oi = other->_composition_cache.find(current_state);
01881         nassertr(oi != -1, false);
01882 
01883         const TransformState *result = other->_composition_cache.get_data(oi)._result;
01884         if (result != (const TransformState *)NULL) {
01885           if (r_detect_reverse_cycles(start_state, result, length + 1, 
01886                                       this_seq, cycle_desc)) {
01887             // Cycle detected.
01888             if (cycle_desc != (CompositionCycleDesc *)NULL) {
01889               const TransformState *other = current_state->_composition_cache.get_key(i);
01890               CompositionCycleDescEntry entry(other, result, false);
01891               cycle_desc->push_back(entry);
01892             }
01893             return true;
01894           }
01895         }
01896       }
01897     }
01898   }
01899 
01900   cache_size = current_state->_invert_composition_cache.get_size();
01901   for (i = 0; i < cache_size; ++i) {
01902     if (current_state->_invert_composition_cache.has_element(i)) {
01903       const TransformState *other = current_state->_invert_composition_cache.get_key(i);
01904       if (other != current_state) {
01905         int oi = other->_invert_composition_cache.find(current_state);
01906         nassertr(oi != -1, false);
01907 
01908         const TransformState *result = other->_invert_composition_cache.get_data(oi)._result;
01909         if (result != (const TransformState *)NULL) {
01910           if (r_detect_reverse_cycles(start_state, result, length + 1, 
01911                                       this_seq, cycle_desc)) {
01912             // Cycle detected.
01913             if (cycle_desc != (CompositionCycleDesc *)NULL) {
01914               const TransformState *other = current_state->_invert_composition_cache.get_key(i);
01915               CompositionCycleDescEntry entry(other, result, false);
01916               cycle_desc->push_back(entry);
01917             }
01918             return true;
01919           }
01920         }
01921       }
01922     }
01923   }
01924 
01925   // No cycle detected.
01926   return false;
01927 }
01928 
01929 
01930 ////////////////////////////////////////////////////////////////////
01931 //     Function: TransformState::release_new
01932 //       Access: Private
01933 //  Description: This inverse of return_new, this releases this object
01934 //               from the global TransformState table.
01935 //
01936 //               You must already be holding _states_lock before you
01937 //               call this method.
01938 ////////////////////////////////////////////////////////////////////
01939 void TransformState::
01940 release_new() {
01941   nassertv(_states_lock->debug_is_locked());
01942    
01943   if (_saved_entry != _states->end()) {
01944     nassertv(_states->find(this) == _saved_entry);
01945     _states->erase(_saved_entry);
01946     _saved_entry = _states->end();
01947   }
01948 }
01949 
01950 ////////////////////////////////////////////////////////////////////
01951 //     Function: TransformState::remove_cache_pointers
01952 //       Access: Private
01953 //  Description: Remove all pointers within the cache from and to this
01954 //               particular TransformState.  The pointers to this
01955 //               object may be scattered around in the various
01956 //               CompositionCaches from other TransformState objects.
01957 //
01958 //               You must already be holding _states_lock before you
01959 //               call this method.
01960 ////////////////////////////////////////////////////////////////////
01961 void TransformState::
01962 remove_cache_pointers() {
01963   nassertv(_states_lock->debug_is_locked());
01964    
01965   // Fortunately, since we added CompositionCache records in pairs, we
01966   // know exactly the set of TransformState objects that have us in their
01967   // cache: it's the same set of TransformState objects that we have in
01968   // our own cache.
01969 
01970   // We do need to put considerable thought into this loop, because as
01971   // we clear out cache entries we'll cause other TransformState
01972   // objects to destruct, which could cause things to get pulled out
01973   // of our own _composition_cache map.  We want to allow this (so
01974   // that we don't encounter any just-destructed pointers in our
01975   // cache), but we don't want to get bitten by this cascading effect.
01976   // Instead of walking through the map from beginning to end,
01977   // therefore, we just pull out the first one each time, and erase
01978   // it.
01979 
01980 #ifdef DO_PSTATS
01981   if (_composition_cache.is_empty() && _invert_composition_cache.is_empty()) {
01982     return;
01983   }
01984   PStatTimer timer(_cache_update_pcollector);
01985 #endif  // DO_PSTATS
01986 
01987   // There are lots of ways to do this loop wrong.  Be very careful if
01988   // you need to modify it for any reason.
01989   int i = 0;
01990   while (!_composition_cache.is_empty()) {
01991     // Scan for the next used slot in the table.
01992     while (!_composition_cache.has_element(i)) {
01993       ++i;
01994     }
01995 
01996     // It is possible that the "other" TransformState object is
01997     // currently within its own destructor.  We therefore can't use a
01998     // PT() to hold its pointer; that could end up calling its
01999     // destructor twice.  Fortunately, we don't need to hold its
02000     // reference count to ensure it doesn't destruct while we process
02001     // this loop; as long as we ensure that no *other* TransformState
02002     // objects destruct, there will be no reason for that one to.
02003     TransformState *other = (TransformState *)_composition_cache.get_key(i);
02004 
02005     // We hold a copy of the composition result so we can dereference
02006     // it later.
02007     Composition comp = _composition_cache.get_data(i);
02008 
02009     // Now we can remove the element from our cache.  We do this now,
02010     // rather than later, before any other TransformState objects have
02011     // had a chance to destruct, so we are confident that our iterator
02012     // is still valid.
02013     _composition_cache.remove_element(i);
02014     _cache_stats.add_total_size(-1);
02015     _cache_stats.inc_dels();
02016 
02017     if (other != this) {
02018       int oi = other->_composition_cache.find(this);
02019 
02020       // We may or may not still be listed in the other's cache (it
02021       // might be halfway through pulling entries out, from within its
02022       // own destructor).
02023       if (oi != -1) {
02024         // Hold a copy of the other composition result, too.
02025         Composition ocomp = other->_composition_cache.get_data(oi);
02026         
02027         other->_composition_cache.remove_element(oi);
02028         _cache_stats.add_total_size(-1);
02029         _cache_stats.inc_dels();
02030         
02031         // It's finally safe to let our held pointers go away.  This may
02032         // have cascading effects as other TransformState objects are
02033         // destructed, but there will be no harm done if they destruct
02034         // now.
02035         if (ocomp._result != (const TransformState *)NULL && ocomp._result != other) {
02036           cache_unref_delete(ocomp._result);
02037         }
02038       }
02039     }
02040 
02041     // It's finally safe to let our held pointers go away.  (See
02042     // comment above.)
02043     if (comp._result != (const TransformState *)NULL && comp._result != this) {
02044       cache_unref_delete(comp._result);
02045     }
02046   }
02047 
02048   // A similar bit of code for the invert cache.
02049   i = 0;
02050   while (!_invert_composition_cache.is_empty()) {
02051     while (!_invert_composition_cache.has_element(i)) {
02052       ++i;
02053     }
02054 
02055     TransformState *other = (TransformState *)_invert_composition_cache.get_key(i);
02056     nassertv(other != this);
02057     Composition comp = _invert_composition_cache.get_data(i);
02058     _invert_composition_cache.remove_element(i);
02059     _cache_stats.add_total_size(-1);
02060     _cache_stats.inc_dels();
02061     if (other != this) {
02062       int oi = other->_invert_composition_cache.find(this);
02063       if (oi != -1) {
02064         Composition ocomp = other->_invert_composition_cache.get_data(oi);
02065         other->_invert_composition_cache.remove_element(oi);
02066         _cache_stats.add_total_size(-1);
02067         _cache_stats.inc_dels();
02068         if (ocomp._result != (const TransformState *)NULL && ocomp._result != other) {
02069           cache_unref_delete(ocomp._result);
02070         }
02071       }
02072     }
02073     if (comp._result != (const TransformState *)NULL && comp._result != this) {
02074       cache_unref_delete(comp._result);
02075     }
02076   }
02077 }
02078 
02079 ////////////////////////////////////////////////////////////////////
02080 //     Function: TransformState::do_calc_hash
02081 //       Access: Private
02082 //  Description: Computes a suitable hash value for phash_map.
02083 ////////////////////////////////////////////////////////////////////
02084 void TransformState::
02085 do_calc_hash() {
02086   PStatTimer timer(_transform_hash_pcollector);
02087   _hash = 0;
02088 
02089   static const int significant_flags = 
02090     (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_is_2d);
02091 
02092   int flags = (_flags & significant_flags);
02093   _hash = int_hash::add_hash(_hash, flags);
02094 
02095   if ((_flags & (F_is_invalid | F_is_identity)) == 0) {
02096     // Only bother to put the rest of the stuff in the hash if the
02097     // transform is not invalid or empty.
02098     
02099     if ((_flags & (F_components_given | F_hpr_given | F_quat_given)) == 
02100         (F_components_given | F_hpr_given | F_quat_given)) {
02101       // If the transform was specified componentwise, hash it
02102       // componentwise.
02103       _hash = _pos.add_hash(_hash);
02104       if ((_flags & F_hpr_given) != 0) {
02105         _hash = _hpr.add_hash(_hash);
02106 
02107       } else if ((_flags & F_quat_given) != 0) {
02108         _hash = _quat.add_hash(_hash);
02109       }
02110 
02111       _hash = _scale.add_hash(_hash);
02112       _hash = _shear.add_hash(_hash);
02113 
02114     } else {
02115       // Otherwise, hash the pointer only--any two different
02116       // matrix-based TransformStates are considered to be different,
02117       // even if their matrices have the same values.
02118 
02119       _hash = pointer_hash::add_hash(_hash, this);
02120     }
02121   }
02122 
02123   _flags |= F_hash_known;
02124 }
02125 
02126 ////////////////////////////////////////////////////////////////////
02127 //     Function: TransformState::calc_singular
02128 //       Access: Private
02129 //  Description: Determines whether the transform is singular (i.e. it
02130 //               scales to zero, and has no inverse).
02131 ////////////////////////////////////////////////////////////////////
02132 void TransformState::
02133 calc_singular() {
02134   LightMutexHolder holder(_lock);
02135   if ((_flags & F_singular_known) != 0) {
02136     // Someone else computed it first.
02137     return;
02138   }
02139 
02140   PStatTimer timer(_transform_calc_pcollector);
02141 
02142   nassertv((_flags & F_is_invalid) == 0);
02143 
02144   // We determine if a matrix is singular by attempting to invert it
02145   // (and we save the result of this invert operation for a subsequent
02146   // do_invert_compose() call, which is almost certain to be made if
02147   // someone is asking whether we're singular).
02148 
02149   // This should be NULL if no one has called calc_singular() yet.
02150   nassertv(_inv_mat == (LMatrix4f *)NULL);
02151   _inv_mat = new LMatrix4f;
02152 
02153   if ((_flags & F_mat_known) == 0) {
02154     do_calc_mat();
02155   }
02156   bool inverted = _inv_mat->invert_from(_mat);
02157 
02158   if (!inverted) {
02159     _flags |= F_is_singular;
02160     delete _inv_mat;
02161     _inv_mat = (LMatrix4f *)NULL;
02162   }
02163   _flags |= F_singular_known;
02164 }
02165 
02166 ////////////////////////////////////////////////////////////////////
02167 //     Function: TransformState::do_calc_components
02168 //       Access: Private
02169 //  Description: This is the implementation of calc_components(); it
02170 //               assumes the lock is already held.
02171 ////////////////////////////////////////////////////////////////////
02172 void TransformState::
02173 do_calc_components() {
02174   if ((_flags & F_components_known) != 0) {
02175     // Someone else computed it first.
02176     return;
02177   }
02178 
02179   PStatTimer timer(_transform_calc_pcollector);
02180 
02181   nassertv((_flags & F_is_invalid) == 0);
02182   if ((_flags & F_is_identity) != 0) {
02183     _scale.set(1.0f, 1.0f, 1.0f);
02184     _shear.set(0.0f, 0.0f, 0.0f);
02185     _hpr.set(0.0f, 0.0f, 0.0f);
02186     _quat = LQuaternionf::ident_quat();
02187     _pos.set(0.0f, 0.0f, 0.0f);
02188     _flags |= F_has_components | F_components_known | F_hpr_known | F_quat_known | F_uniform_scale;
02189 
02190   } else {
02191     // If we don't have components and we're not identity, the only
02192     // other explanation is that we were constructed via a matrix.
02193     nassertv((_flags & F_mat_known) != 0);
02194 
02195     if ((_flags & F_mat_known) == 0) {
02196       do_calc_mat();
02197     }
02198     bool possible = decompose_matrix(_mat, _scale, _shear, _hpr, _pos);
02199     if (!possible) {
02200       // Some matrices can't be decomposed into scale, hpr, pos.  In
02201       // this case, we now know that we cannot compute the components;
02202       // but the closest approximations are stored, at least.
02203       _flags |= F_components_known | F_hpr_known;
02204 
02205     } else {
02206       // Otherwise, we do have the components, or at least the hpr.
02207       _flags |= F_has_components | F_components_known | F_hpr_known;
02208       check_uniform_scale();
02209     }
02210 
02211     // However, we can always get at least the pos.
02212     _mat.get_row3(_pos, 3);
02213   }
02214 }
02215 
02216 ////////////////////////////////////////////////////////////////////
02217 //     Function: TransformState::do_calc_hpr
02218 //       Access: Private
02219 //  Description: This is the implementation of calc_hpr(); it
02220 //               assumes the lock is already held.
02221 ////////////////////////////////////////////////////////////////////
02222 void TransformState::
02223 do_calc_hpr() {
02224   if ((_flags & F_hpr_known) != 0) {
02225     // Someone else computed it first.
02226     return;
02227   }
02228 
02229   PStatTimer timer(_transform_calc_pcollector);
02230 
02231   nassertv((_flags & F_is_invalid) == 0);
02232   if ((_flags & F_components_known) == 0) {
02233     do_calc_components();
02234   }
02235   if ((_flags & F_hpr_known) == 0) {
02236     // If we don't know the hpr yet, we must have been given a quat.
02237     // Decompose it.
02238     nassertv((_flags & F_quat_known) != 0);
02239     _hpr = _quat.get_hpr();
02240     _flags |= F_hpr_known;
02241   }
02242 }
02243 
02244 ////////////////////////////////////////////////////////////////////
02245 //     Function: TransformState::calc_quat
02246 //       Access: Private
02247 //  Description: Derives the quat from the hpr.
02248 ////////////////////////////////////////////////////////////////////
02249 void TransformState::
02250 calc_quat() {
02251   LightMutexHolder holder(_lock);
02252   if ((_flags & F_quat_known) != 0) {
02253     // Someone else computed it first.
02254     return;
02255   }
02256 
02257   PStatTimer timer(_transform_calc_pcollector);
02258 
02259   nassertv((_flags & F_is_invalid) == 0);
02260   if ((_flags & F_components_known) == 0) {
02261     do_calc_components();
02262   }
02263   if ((_flags & F_quat_known) == 0) {
02264     // If we don't know the quat yet, we must have been given a hpr.
02265     // Decompose it.
02266     nassertv((_flags & F_hpr_known) != 0);
02267     _quat.set_hpr(_hpr);
02268     _flags |= F_quat_known;
02269   }
02270 }
02271 
02272 ////////////////////////////////////////////////////////////////////
02273 //     Function: TransformState::calc_norm_quat
02274 //       Access: Private
02275 //  Description: Derives the normalized quat from the quat.
02276 ////////////////////////////////////////////////////////////////////
02277 void TransformState::
02278 calc_norm_quat() {
02279   PStatTimer timer(_transform_calc_pcollector);
02280 
02281   LQuaternionf quat = get_quat();
02282   LightMutexHolder holder(_lock);
02283   _norm_quat = quat;
02284   _norm_quat.normalize();
02285   _flags |= F_norm_quat_known;
02286 }
02287 
02288 ////////////////////////////////////////////////////////////////////
02289 //     Function: TransformState::do_calc_mat
02290 //       Access: Private
02291 //  Description: This is the implementation of calc_mat(); it
02292 //               assumes the lock is already held.
02293 ////////////////////////////////////////////////////////////////////
02294 void TransformState::
02295 do_calc_mat() {
02296   if ((_flags & F_mat_known) != 0) {
02297     // Someone else computed it first.
02298     return;
02299   }
02300 
02301   PStatTimer timer(_transform_calc_pcollector);
02302 
02303   nassertv((_flags & F_is_invalid) == 0);
02304   if ((_flags & F_is_identity) != 0) {
02305     _mat = LMatrix4f::ident_mat();
02306 
02307   } else {
02308     // If we don't have a matrix and we're not identity, the only
02309     // other explanation is that we were constructed via components.
02310     nassertv((_flags & F_components_known) != 0);
02311     if ((_flags & F_hpr_known) == 0) {
02312       do_calc_hpr();
02313     }
02314 
02315     compose_matrix(_mat, _scale, _shear, get_hpr(), _pos);
02316   }
02317   _flags |= F_mat_known;
02318 }
02319 
02320 ////////////////////////////////////////////////////////////////////
02321 //     Function: TransformState::update_pstats
02322 //       Access: Private
02323 //  Description: Moves the TransformState object from one PStats category
02324 //               to another, so that we can track in PStats how many
02325 //               pointers are held by nodes, and how many are held in
02326 //               the cache only.
02327 ////////////////////////////////////////////////////////////////////
02328 void TransformState::
02329 update_pstats(int old_referenced_bits, int new_referenced_bits) {
02330 #ifdef DO_PSTATS
02331   if ((old_referenced_bits & R_node) != 0) {
02332     _node_counter.sub_level(1);
02333   } else if ((old_referenced_bits & R_cache) != 0) {
02334     _cache_counter.sub_level(1);
02335   }
02336   if ((new_referenced_bits & R_node) != 0) {
02337     _node_counter.add_level(1);
02338   } else if ((new_referenced_bits & R_cache) != 0) {
02339     _cache_counter.add_level(1);
02340   }
02341 #endif  // DO_PSTATS
02342 }
02343 
02344 ////////////////////////////////////////////////////////////////////
02345 //     Function: TransformState::register_with_read_factory
02346 //       Access: Public, Static
02347 //  Description: Tells the BamReader how to create objects of type
02348 //               TransformState.
02349 ////////////////////////////////////////////////////////////////////
02350 void TransformState::
02351 register_with_read_factory() {
02352   BamReader::get_factory()->register_factory(get_class_type(), make_from_bam);
02353 }
02354 
02355 ////////////////////////////////////////////////////////////////////
02356 //     Function: TransformState::write_datagram
02357 //       Access: Public, Virtual
02358 //  Description: Writes the contents of this object to the datagram
02359 //               for shipping out to a Bam file.
02360 ////////////////////////////////////////////////////////////////////
02361 void TransformState::
02362 write_datagram(BamWriter *manager, Datagram &dg) {
02363   TypedWritable::write_datagram(manager, dg);
02364 
02365   if ((_flags & F_is_identity) != 0) {
02366     // Identity, nothing much to that.
02367     int flags = F_is_identity | F_singular_known | F_is_2d;
02368     dg.add_uint32(flags);
02369 
02370   } else if ((_flags & F_is_invalid) != 0) {
02371     // Invalid, nothing much to that either.
02372     int flags = F_is_invalid | F_singular_known | F_is_singular | F_components_known | F_mat_known;
02373     dg.add_uint32(flags);
02374 
02375   } else if ((_flags & F_components_given) != 0) {
02376     // A component-based transform.
02377     int flags = F_components_given | F_components_known | F_has_components;
02378     flags |= (_flags & F_is_2d);
02379     if ((_flags & F_quat_given) != 0) {
02380       flags |= (F_quat_given | F_quat_known);
02381     } else if ((_flags & F_hpr_given) != 0) {
02382       flags |= (F_hpr_given | F_hpr_known);
02383     }
02384 
02385     dg.add_uint32(flags);
02386 
02387     _pos.write_datagram(dg);
02388     if ((_flags & F_quat_given) != 0) {
02389       _quat.write_datagram(dg);
02390     } else {
02391       get_hpr().write_datagram(dg);
02392     }
02393     _scale.write_datagram(dg);
02394     _shear.write_datagram(dg);
02395 
02396   } else {
02397     // A general matrix.
02398     nassertv((_flags & F_mat_known) != 0);
02399     int flags = F_mat_known;
02400     flags |= (_flags & F_is_2d);
02401     dg.add_uint32(flags);
02402     _mat.write_datagram(dg);
02403   }
02404 }
02405 
02406 ////////////////////////////////////////////////////////////////////
02407 //     Function: TransformState::change_this
02408 //       Access: Public, Static
02409 //  Description: Called immediately after complete_pointers(), this
02410 //               gives the object a chance to adjust its own pointer
02411 //               if desired.  Most objects don't change pointers after
02412 //               completion, but some need to.
02413 //
02414 //               Once this function has been called, the old pointer
02415 //               will no longer be accessed.
02416 ////////////////////////////////////////////////////////////////////
02417 PT(TypedWritableReferenceCount) TransformState::
02418 change_this(TypedWritableReferenceCount *old_ptr, BamReader *manager) {
02419   // First, uniquify the pointer.
02420   TransformState *state = DCAST(TransformState, old_ptr);
02421   CPT(TransformState) pointer = return_unique(state);
02422   
02423   // We have to cast the pointer back to non-const, because the bam
02424   // reader expects that.
02425   return (TransformState *)pointer.p();
02426 }
02427 
02428 ////////////////////////////////////////////////////////////////////
02429 //     Function: TransformState::make_from_bam
02430 //       Access: Protected, Static
02431 //  Description: This function is called by the BamReader's factory
02432 //               when a new object of type TransformState is encountered
02433 //               in the Bam file.  It should create the TransformState
02434 //               and extract its information from the file.
02435 ////////////////////////////////////////////////////////////////////
02436 TypedWritable *TransformState::
02437 make_from_bam(const FactoryParams &params) {
02438   TransformState *state = new TransformState;
02439   DatagramIterator scan;
02440   BamReader *manager;
02441 
02442   parse_params(params, scan, manager);
02443   state->fillin(scan, manager);
02444   manager->register_change_this(change_this, state);
02445 
02446   return state;
02447 }
02448 
02449 ////////////////////////////////////////////////////////////////////
02450 //     Function: TransformState::fillin
02451 //       Access: Protected
02452 //  Description: This internal function is called by make_from_bam to
02453 //               read in all of the relevant data from the BamFile for
02454 //               the new TransformState.
02455 ////////////////////////////////////////////////////////////////////
02456 void TransformState::
02457 fillin(DatagramIterator &scan, BamReader *manager) {
02458   TypedWritable::fillin(scan, manager);
02459   _flags = scan.get_uint32();
02460 
02461   if ((_flags & F_components_given) != 0) {
02462     // Componentwise transform.
02463     _pos.read_datagram(scan);
02464     if ((_flags & F_quat_given) != 0) {
02465       _quat.read_datagram(scan);
02466     } else {
02467       _hpr.read_datagram(scan);
02468     }
02469     _scale.read_datagram(scan);
02470     _shear.read_datagram(scan);
02471 
02472     check_uniform_scale();
02473   }
02474 
02475   if ((_flags & F_mat_known) != 0) {
02476     // General matrix.
02477     _mat.read_datagram(scan);
02478   }
02479 }
 All Classes Functions Variables Enumerations