Panda3D
transformState.cxx
Go to the documentation of this file.
1 /**
2  * PANDA 3D SOFTWARE
3  * Copyright (c) Carnegie Mellon University. All rights reserved.
4  *
5  * All use of this software is subject to the terms of the revised BSD
6  * license. You should have received a copy of this license along
7  * with this source code in a file named "LICENSE."
8  *
9  * @file transformState.cxx
10  * @author drose
11  * @date 2002-02-25
12  */
13 
14 #include "transformState.h"
15 #include "compose_matrix.h"
16 #include "bamReader.h"
17 #include "bamWriter.h"
18 #include "datagramIterator.h"
19 #include "indent.h"
20 #include "compareTo.h"
21 #include "pStatTimer.h"
22 #include "config_pgraph.h"
23 #include "lightReMutexHolder.h"
24 #include "lightMutexHolder.h"
25 #include "thread.h"
26 
27 using std::ostream;
28 
29 LightReMutex *TransformState::_states_lock = nullptr;
30 TransformState::States *TransformState::_states = nullptr;
31 CPT(TransformState) TransformState::_identity_state;
32 CPT(TransformState) TransformState::_invalid_state;
33 UpdateSeq TransformState::_last_cycle_detect;
34 size_t TransformState::_garbage_index = 0;
35 bool TransformState::_uniquify_matrix = true;
36 
37 PStatCollector TransformState::_cache_update_pcollector("*:State Cache:Update");
38 PStatCollector TransformState::_garbage_collect_pcollector("*:State Cache:Garbage Collect");
39 PStatCollector TransformState::_transform_compose_pcollector("*:State Cache:Compose Transform");
40 PStatCollector TransformState::_transform_invert_pcollector("*:State Cache:Invert Transform");
41 PStatCollector TransformState::_transform_calc_pcollector("*:State Cache:Calc Components");
42 PStatCollector TransformState::_transform_break_cycles_pcollector("*:State Cache:Break Cycles");
43 PStatCollector TransformState::_transform_new_pcollector("*:State Cache:New");
44 PStatCollector TransformState::_transform_validate_pcollector("*:State Cache:Validate");
45 PStatCollector TransformState::_transform_hash_pcollector("*:State Cache:Calc Hash");
46 PStatCollector TransformState::_node_counter("TransformStates:On nodes");
47 PStatCollector TransformState::_cache_counter("TransformStates:Cached");
48 
49 CacheStats TransformState::_cache_stats;
50 
51 TypeHandle TransformState::_type_handle;
52 
53 /**
54  * Actually, this could be a private constructor, since no one inherits from
55  * TransformState, but gcc gives us a spurious warning if all constructors are
56  * private.
57  */
58 TransformState::
59 TransformState() : _lock("TransformState") {
60  if (_states == nullptr) {
61  init_states();
62  }
63  _saved_entry = -1;
64  _flags = F_is_identity | F_singular_known | F_is_2d;
65  _inv_mat = nullptr;
66  _cache_stats.add_num_states(1);
67 
68 #ifdef DO_MEMORY_USAGE
69  MemoryUsage::update_type(this, this);
70 #endif
71 }
72 
73 /**
74  * The destructor is responsible for removing the TransformState from the
75  * global set if it is there.
76  */
79  // We'd better not call the destructor twice on a particular object.
80  nassertv(!is_destructing());
81  set_destructing();
82 
83  // Free the inverse matrix computation, if it has been stored.
84  if (_inv_mat != nullptr) {
85  delete _inv_mat;
86  _inv_mat = nullptr;
87  }
88 
89  LightReMutexHolder holder(*_states_lock);
90 
91  // unref() should have cleared these.
92  nassertv(_saved_entry == -1);
93  nassertv(_composition_cache.is_empty() && _invert_composition_cache.is_empty());
94 
95  // If this was true at the beginning of the destructor, but is no longer
96  // true now, probably we've been double-deleted.
97  nassertv(get_ref_count() == 0);
98  _cache_stats.add_num_states(-1);
99 
100 #ifndef NDEBUG
101  _flags = F_is_invalid | F_is_destructing;
102 #endif
103 }
104 
105 /**
106  * Provides an arbitrary ordering among all unique TransformStates, so we can
107  * store the essentially different ones in a big set and throw away the rest.
108  *
109  * Note that if this returns 0, it doesn't necessarily imply that operator ==
110  * returns true; it uses a very slightly different comparison threshold.
111  *
112  * If uniquify_matrix is true, then matrix-defined TransformStates are also
113  * uniqified. If uniquify_matrix is false, then only component-defined
114  * TransformStates are uniquified, which is less expensive.
115  */
117 compare_to(const TransformState &other, bool uniquify_matrix) const {
118  static const int significant_flags =
119  (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_quat_given | F_is_2d);
120 
121  int flags = (_flags & significant_flags);
122  int other_flags = (other._flags & significant_flags);
123  if (flags != other_flags) {
124  return flags < other_flags ? -1 : 1;
125  }
126 
127  if ((_flags & (F_is_invalid | F_is_identity)) != 0) {
128  // All invalid transforms are equivalent to each other, and all identity
129  // transforms are equivalent to each other.
130  return 0;
131  }
132 
133  if ((_flags & F_components_given) != 0) {
134  // If the transform was specified componentwise, compare them
135  // componentwise.
136  int c = _pos.compare_to(other._pos);
137  if (c != 0) {
138  return c;
139  }
140 
141  if ((_flags & F_hpr_given) != 0) {
142  c = _hpr.compare_to(other._hpr);
143  if (c != 0) {
144  return c;
145  }
146  } else if ((_flags & F_quat_given) != 0) {
147  c = _quat.compare_to(other._quat);
148  if (c != 0) {
149  return c;
150  }
151  }
152 
153  c = _scale.compare_to(other._scale);
154  if (c != 0) {
155  return c;
156  }
157 
158  c = _shear.compare_to(other._shear);
159  return c;
160  }
161 
162  // Otherwise, compare the matrices . . .
163  if (uniquify_matrix) {
164  // . . . but only if the user thinks that's a worthwhile comparison.
165  return get_mat().compare_to(other.get_mat());
166 
167  } else {
168  // If not, we just compare the pointers.
169  if (this != &other) {
170  return (this < &other) ? -1 : 1;
171  }
172  return 0;
173  }
174 }
175 
176 /**
177  * Tests equivalence between two transform states. We use this instead of
178  * compare_to since this is faster, and we don't need an ordering between
179  * TransformStates because we use a hash map.
180  *
181  * If uniquify_matrix is true, then matrix-defined TransformStates are also
182  * uniqified. If uniquify_matrix is false, then only component-defined
183  * TransformStates are uniquified, which is less expensive.
184  */
186 operator == (const TransformState &other) const {
187  static const int significant_flags =
188  (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_quat_given | F_is_2d);
189 
190  int flags = (_flags & significant_flags);
191  int other_flags = (other._flags & significant_flags);
192  if (flags != other_flags) {
193  return false;
194  }
195 
196  if ((_flags & (F_is_invalid | F_is_identity)) != 0) {
197  // All invalid transforms are equivalent to each other, and all identity
198  // transforms are equivalent to each other.
199  return true;
200  }
201 
202  if ((_flags & F_components_given) != 0) {
203  // If the transform was specified componentwise, compare them
204  // componentwise.
205  if (_pos != other._pos) {
206  return false;
207  }
208 
209  if ((_flags & F_hpr_given) != 0) {
210  if (_hpr != other._hpr) {
211  return false;
212  }
213  } else if ((_flags & F_quat_given) != 0) {
214  if (_quat != other._quat) {
215  return false;
216  }
217  }
218 
219  if (_scale != other._scale) {
220  return false;
221  }
222 
223  return (_shear == other._shear);
224  }
225 
226  // Otherwise, compare the matrices . . .
227  if (_uniquify_matrix) {
228  // . . . but only if the user thinks that's a worthwhile comparison.
229  return get_mat().almost_equal(other.get_mat());
230 
231  } else {
232  // If not, we just compare the pointers.
233  return (this == &other);
234  }
235 }
236 
237 /**
238  * Constructs an identity transform.
239  */
240 CPT(TransformState) TransformState::
241 make_identity() {
242  // The identity state is asked for so often, we make it a special case and
243  // store a pointer forever once we find it the first time.
244  if (_identity_state == nullptr) {
245  TransformState *state = new TransformState;
246  _identity_state = return_unique(state);
247  }
248 
249  return _identity_state;
250 }
251 
252 /**
253  * Constructs an invalid transform; for instance, the result of inverting a
254  * singular matrix.
255  */
256 CPT(TransformState) TransformState::
257 make_invalid() {
258  if (_invalid_state == nullptr) {
259  TransformState *state = new TransformState;
260  state->_flags = F_is_invalid | F_singular_known | F_is_singular | F_components_known | F_mat_known;
261  _invalid_state = return_unique(state);
262  }
263 
264  return _invalid_state;
265 }
266 
267 /**
268  * Makes a new TransformState with the specified components.
269  */
270 CPT(TransformState) TransformState::
271 make_pos_hpr_scale_shear(const LVecBase3 &pos, const LVecBase3 &hpr,
272  const LVecBase3 &scale, const LVecBase3 &shear) {
273  nassertr(!(pos.is_nan() || hpr.is_nan() || scale.is_nan() || shear.is_nan()) , make_invalid());
274  // Make a special-case check for the identity transform.
275  if (pos == LVecBase3(0.0f, 0.0f, 0.0f) &&
276  hpr == LVecBase3(0.0f, 0.0f, 0.0f) &&
277  scale == LVecBase3(1.0f, 1.0f, 1.0f) &&
278  shear == LVecBase3(0.0f, 0.0f, 0.0f)) {
279  return make_identity();
280  }
281 
282  TransformState *state = new TransformState;
283  state->_pos = pos;
284  state->_hpr = hpr;
285  state->_scale = scale;
286  state->_shear = shear;
287  state->_flags = F_components_given | F_hpr_given | F_components_known | F_hpr_known | F_has_components;
288  state->check_uniform_scale();
289  return return_new(state);
290 }
291 
292 /**
293  * Makes a new TransformState with the specified components.
294  */
295 CPT(TransformState) TransformState::
296 make_pos_quat_scale_shear(const LVecBase3 &pos, const LQuaternion &quat,
297  const LVecBase3 &scale, const LVecBase3 &shear) {
298  nassertr(!(pos.is_nan() || quat.is_nan() || scale.is_nan() || shear.is_nan()) , make_invalid());
299  // Make a special-case check for the identity transform.
300  if (pos == LVecBase3(0.0f, 0.0f, 0.0f) &&
301  quat == LQuaternion::ident_quat() &&
302  scale == LVecBase3(1.0f, 1.0f, 1.0f) &&
303  shear == LVecBase3(0.0f, 0.0f, 0.0f)) {
304  return make_identity();
305  }
306 
307  TransformState *state = new TransformState;
308  state->_pos = pos;
309  state->_quat = quat;
310  state->_scale = scale;
311  state->_shear = shear;
312  state->_flags = F_components_given | F_quat_given | F_components_known | F_quat_known | F_has_components;
313  state->check_uniform_scale();
314  return return_new(state);
315 }
316 
317 /**
318  * Makes a new TransformState with the specified transformation matrix.
319  */
320 CPT(TransformState) TransformState::
321 make_mat(const LMatrix4 &mat) {
322  nassertr(!mat.is_nan(), make_invalid());
323  // Make a special-case check for the identity matrix.
324  if (mat.is_identity()) {
325  return make_identity();
326  }
327 
328  TransformState *state = new TransformState;
329  state->_mat = mat;
330  state->_flags = F_mat_known;
331  return return_new(state);
332 }
333 
334 /**
335  * Makes a new two-dimensional TransformState with the specified components.
336  */
337 CPT(TransformState) TransformState::
338 make_pos_rotate_scale_shear2d(const LVecBase2 &pos, PN_stdfloat rotate,
339  const LVecBase2 &scale,
340  PN_stdfloat shear) {
341  nassertr(!(pos.is_nan() || cnan(rotate) || scale.is_nan() || cnan(shear)) , make_invalid());
342  // Make a special-case check for the identity transform.
343  if (pos == LVecBase2(0.0f, 0.0f) &&
344  rotate == 0.0f &&
345  scale == LVecBase2(1.0f, 1.0f) &&
346  shear == 0.0f) {
347  return make_identity();
348  }
349 
350  TransformState *state = new TransformState;
351  state->_pos.set(pos[0], pos[1], 0.0f);
352  switch (get_default_coordinate_system()) {
353  default:
354  case CS_zup_right:
355  state->_hpr.set(rotate, 0.0f, 0.0f);
356  break;
357  case CS_zup_left:
358  state->_hpr.set(-rotate, 0.0f, 0.0f);
359  break;
360  case CS_yup_right:
361  state->_hpr.set(0.0f, 0.0f, -rotate);
362  break;
363  case CS_yup_left:
364  state->_hpr.set(0.0, 0.0f, rotate);
365  break;
366  }
367  state->_scale.set(scale[0], scale[1], 1.0f);
368  state->_shear.set(shear, 0.0f, 0.0f);
369  state->_flags = F_components_given | F_hpr_given | F_components_known | F_hpr_known | F_has_components | F_is_2d;
370  state->check_uniform_scale2d();
371  return return_new(state);
372 }
373 
374 
375 /**
376  * Makes a new two-dimensional TransformState with the specified 3x3
377  * transformation matrix.
378  */
379 CPT(TransformState) TransformState::
380 make_mat3(const LMatrix3 &mat) {
381  nassertr(!mat.is_nan(), make_invalid());
382  // Make a special-case check for the identity matrix.
383  if (mat.is_identity()) {
384  return make_identity();
385  }
386 
387  TransformState *state = new TransformState;
388  state->_mat.set(mat(0, 0), mat(0, 1), 0.0f, mat(0, 2),
389  mat(1, 0), mat(1, 1), 0.0f, mat(1, 2),
390  0.0f, 0.0f, 1.0f, 0.0f,
391  mat(2, 0), mat(2, 1), 0.0f, mat(2, 2));
392  state->_flags = F_mat_known | F_is_2d;
393  return return_new(state);
394 }
395 
396 /**
397  * Returns a new TransformState object that represents the original
398  * TransformState with its pos component replaced with the indicated value.
399  */
400 CPT(TransformState) TransformState::
401 set_pos(const LVecBase3 &pos) const {
402  nassertr(!pos.is_nan(), this);
403  nassertr(!is_invalid(), this);
404  if (is_identity() || components_given()) {
405  // If we started with a componentwise transform, we keep it that way.
406  if (quat_given()) {
407  return make_pos_quat_scale_shear(pos, get_quat(), get_scale(), get_shear());
408  } else {
409  return make_pos_hpr_scale_shear(pos, get_hpr(), get_scale(), get_shear());
410  }
411 
412  } else {
413  // Otherwise, we have a matrix transform, and we keep it that way.
414  LMatrix4 mat = get_mat();
415  mat.set_row(3, pos);
416  return make_mat(mat);
417  }
418 }
419 
420 /**
421  * Returns a new TransformState object that represents the original
422  * TransformState with its rotation component replaced with the indicated
423  * value, if possible.
424  */
425 CPT(TransformState) TransformState::
426 set_hpr(const LVecBase3 &hpr) const {
427  nassertr(!hpr.is_nan(), this);
428  nassertr(!is_invalid(), this);
429  // nassertr(has_components(), this);
430  return make_pos_hpr_scale_shear(get_pos(), hpr, get_scale(), get_shear());
431 }
432 
433 /**
434  * Returns a new TransformState object that represents the original
435  * TransformState with its rotation component replaced with the indicated
436  * value, if possible.
437  */
438 CPT(TransformState) TransformState::
439 set_quat(const LQuaternion &quat) const {
440  nassertr(!quat.is_nan(), this);
441  nassertr(!is_invalid(), this);
442  // nassertr(has_components(), this);
443  return make_pos_quat_scale_shear(get_pos(), quat, get_scale(), get_shear());
444 }
445 
446 /**
447  * Returns a new TransformState object that represents the original
448  * TransformState with its scale component replaced with the indicated value,
449  * if possible.
450  */
451 CPT(TransformState) TransformState::
452 set_scale(const LVecBase3 &scale) const {
453  nassertr(!scale.is_nan(), this);
454  nassertr(!is_invalid(), this);
455 
456  if (is_2d() && scale[0] == scale[1] && scale[1] == scale[2]) {
457  // Don't inflate from 2-d to 3-d just because we got a uniform scale.
458  return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
459  LVecBase2(scale[0], scale[0]),
460  get_shear2d());
461  }
462 
463  // nassertr(has_components(), this);
464  if (quat_given()) {
465  return make_pos_quat_scale_shear(get_pos(), get_quat(), scale, get_shear());
466  } else {
467  return make_pos_hpr_scale_shear(get_pos(), get_hpr(), scale, get_shear());
468  }
469 }
470 
471 /**
472  * Returns a new TransformState object that represents the original
473  * TransformState with its shear component replaced with the indicated value,
474  * if possible.
475  */
476 CPT(TransformState) TransformState::
477 set_shear(const LVecBase3 &shear) const {
478  nassertr(!shear.is_nan(), this);
479  nassertr(!is_invalid(), this);
480  // nassertr(has_components(), this);
481  if (quat_given()) {
482  return make_pos_quat_scale_shear(get_pos(), get_quat(), get_scale(), shear);
483  } else {
484  return make_pos_hpr_scale_shear(get_pos(), get_hpr(), get_scale(), shear);
485  }
486 }
487 
488 /**
489  * Returns a new TransformState object that represents the original 2-d
490  * TransformState with its pos component replaced with the indicated value.
491  */
492 CPT(TransformState) TransformState::
493 set_pos2d(const LVecBase2 &pos) const {
494  nassertr(!pos.is_nan(), this);
495  nassertr(!is_invalid(), this);
496  if (!is_2d()) {
497  return set_pos(LVecBase3(pos[0], pos[1], 0.0f));
498  }
499 
500  if (is_identity() || components_given()) {
501  // If we started with a componentwise transform, we keep it that way.
502  return make_pos_rotate_scale_shear2d(pos, get_rotate2d(), get_scale2d(),
503  get_shear2d());
504 
505  } else {
506  // Otherwise, we have a matrix transform, and we keep it that way.
507  LMatrix3 mat = get_mat3();
508  mat.set_row(2, pos);
509  return make_mat3(mat);
510  }
511 }
512 
513 /**
514  * Returns a new TransformState object that represents the original 2-d
515  * TransformState with its rotation component replaced with the indicated
516  * value, if possible.
517  */
518 CPT(TransformState) TransformState::
519 set_rotate2d(PN_stdfloat rotate) const {
520  nassertr(!cnan(rotate), this);
521  nassertr(!is_invalid(), this);
522 
523  if (!is_2d()) {
524  switch (get_default_coordinate_system()) {
525  default:
526  case CS_zup_right:
527  return set_hpr(LVecBase3(rotate, 0.0f, 0.0f));
528  case CS_zup_left:
529  return set_hpr(LVecBase3(-rotate, 0.0f, 0.0f));
530  case CS_yup_right:
531  return set_hpr(LVecBase3(0.0f, 0.0f, -rotate));
532  case CS_yup_left:
533  return set_hpr(LVecBase3(0.0f, 0.0f, rotate));
534  }
535  }
536 
537  return make_pos_rotate_scale_shear2d(get_pos2d(), rotate, get_scale2d(),
538  get_shear2d());
539 }
540 
541 /**
542  * Returns a new TransformState object that represents the original 2-d
543  * TransformState with its scale component replaced with the indicated value,
544  * if possible.
545  */
546 CPT(TransformState) TransformState::
547 set_scale2d(const LVecBase2 &scale) const {
548  nassertr(!scale.is_nan(), this);
549  nassertr(!is_invalid(), this);
550 
551  if (!is_2d()) {
552  return set_scale(LVecBase3(scale[0], scale[1], 1.0f));
553  }
554  return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
555  scale, get_shear2d());
556 }
557 
558 /**
559  * Returns a new TransformState object that represents the original 2-d
560  * TransformState with its shear component replaced with the indicated value,
561  * if possible.
562  */
563 CPT(TransformState) TransformState::
564 set_shear2d(PN_stdfloat shear) const {
565  nassertr(!cnan(shear), this);
566  nassertr(!is_invalid(), this);
567  if (!is_2d()) {
568  return set_shear(LVecBase3(shear, 0.0f, 0.0f));
569  }
570  return make_pos_rotate_scale_shear2d(get_pos2d(), get_rotate2d(),
571  get_scale2d(), shear);
572 }
573 
574 /**
575  * Returns a new TransformState object that represents the composition of this
576  * state with the other state.
577  *
578  * The result of this operation is cached, and will be retained as long as
579  * both this TransformState object and the other TransformState object
580  * continue to exist. Should one of them destruct, the cached entry will be
581  * removed, and its pointer will be allowed to destruct as well.
582  */
583 CPT(TransformState) TransformState::
584 compose(const TransformState *other) const {
585  // We handle identity as a trivial special case.
586  if (is_identity()) {
587  return other;
588  }
589  if (other->is_identity()) {
590  return this;
591  }
592 
593  // If either transform is invalid, the result is invalid.
594  if (is_invalid()) {
595  return this;
596  }
597  if (other->is_invalid()) {
598  return other;
599  }
600 
601  if (!transform_cache) {
602  return do_compose(other);
603  }
604 
605  LightReMutexHolder holder(*_states_lock);
606 
607  // Is this composition already cached?
608  int index = _composition_cache.find(other);
609  if (index != -1) {
610  const Composition &comp = _composition_cache.get_data(index);
611  if (comp._result != nullptr) {
612  // Success!
613  _cache_stats.inc_hits();
614  return comp._result;
615  }
616  }
617 
618  // Not in the cache. Compute a new result. It's important that we don't
619  // hold the lock while we do this, or we lose the benefit of
620  // parallelization.
621  CPT(TransformState) result = do_compose(other);
622 
623  if (index != -1) {
624  Composition &comp = _composition_cache.modify_data(index);
625  // Well, it wasn't cached already, but we already had an entry (probably
626  // created for the reverse direction), so use the same entry to store
627  // the new result.
628  comp._result = result;
629 
630  if (result != (const TransformState *)this) {
631  // See the comments below about the need to up the reference count
632  // only when the result is not the same as this.
633  result->cache_ref();
634  }
635  // Here's the cache!
636  _cache_stats.inc_hits();
637  return result;
638  }
639  _cache_stats.inc_misses();
640 
641  // We need to make a new cache entry, both in this object and in the other
642  // object. We make both records so the other TransformState object will
643  // know to delete the entry from this object when it destructs, and vice-
644  // versa.
645 
646  // The cache entry in this object is the only one that indicates the result;
647  // the other will be NULL for now.
648  _cache_stats.add_total_size(1);
649  _cache_stats.inc_adds(_composition_cache.is_empty());
650 
651  _composition_cache[other]._result = result;
652 
653  if (other != this) {
654  _cache_stats.add_total_size(1);
655  _cache_stats.inc_adds(other->_composition_cache.is_empty());
656  other->_composition_cache[this]._result = nullptr;
657  }
658 
659  if (result != (TransformState *)this) {
660  // If the result of do_compose() is something other than this, explicitly
661  // increment the reference count. We have to be sure to decrement it
662  // again later, when the composition entry is removed from the cache.
663  result->cache_ref();
664 
665  // (If the result was just this again, we still store the result, but we
666  // don't increment the reference count, since that would be a self-
667  // referential leak.)
668  }
669 
670  _cache_stats.maybe_report("TransformState");
671 
672  return result;
673 }
674 
675 /**
676  * Returns a new TransformState object that represents the composition of this
677  * state's inverse with the other state.
678  *
679  * This is similar to compose(), but is particularly useful for computing the
680  * relative state of a node as viewed from some other node.
681  */
682 CPT(TransformState) TransformState::
683 invert_compose(const TransformState *other) const {
684  // This method isn't strictly const, because it updates the cache, but we
685  // pretend that it is because it's only a cache which is transparent to the
686  // rest of the interface.
687 
688  // We handle identity as a trivial special case.
689  if (is_identity()) {
690  return other;
691  }
692  // Unlike compose(), the case of other->is_identity() is not quite as
693  // trivial for invert_compose().
694 
695  // If either transform is invalid, the result is invalid.
696  if (is_invalid()) {
697  return this;
698  }
699  if (other->is_invalid()) {
700  return other;
701  }
702 
703  if (other == this) {
704  // a->invert_compose(a) always produces identity.
705  return make_identity();
706  }
707 
708  if (!transform_cache) {
709  return do_invert_compose(other);
710  }
711 
712  LightReMutexHolder holder(*_states_lock);
713 
714  int index = _invert_composition_cache.find(other);
715  if (index != -1) {
716  const Composition &comp = _invert_composition_cache.get_data(index);
717  if (comp._result != nullptr) {
718  // Success!
719  _cache_stats.inc_hits();
720  return comp._result;
721  }
722  }
723 
724  // Not in the cache. Compute a new result. It's important that we don't
725  // hold the lock while we do this, or we lose the benefit of
726  // parallelization.
727  CPT(TransformState) result = do_invert_compose(other);
728 
729  // Is this composition already cached?
730  if (index != -1) {
731  Composition &comp = _invert_composition_cache.modify_data(index);
732  // Well, it wasn't cached already, but we already had an entry (probably
733  // created for the reverse direction), so use the same entry to store
734  // the new result.
735  comp._result = result;
736 
737  if (result != (const TransformState *)this) {
738  // See the comments below about the need to up the reference count
739  // only when the result is not the same as this.
740  result->cache_ref();
741  }
742  // Here's the cache!
743  _cache_stats.inc_hits();
744  return result;
745  }
746  _cache_stats.inc_misses();
747 
748  // We need to make a new cache entry, both in this object and in the other
749  // object. We make both records so the other TransformState object will
750  // know to delete the entry from this object when it destructs, and vice-
751  // versa.
752 
753  // The cache entry in this object is the only one that indicates the result;
754  // the other will be NULL for now.
755  _cache_stats.add_total_size(1);
756  _cache_stats.inc_adds(_invert_composition_cache.is_empty());
757  _invert_composition_cache[other]._result = result;
758 
759  if (other != this) {
760  _cache_stats.add_total_size(1);
761  _cache_stats.inc_adds(other->_invert_composition_cache.is_empty());
762  other->_invert_composition_cache[this]._result = nullptr;
763  }
764 
765  if (result != (TransformState *)this) {
766  // If the result of compose() is something other than this, explicitly
767  // increment the reference count. We have to be sure to decrement it
768  // again later, when the composition entry is removed from the cache.
769  result->cache_ref();
770 
771  // (If the result was just this again, we still store the result, but we
772  // don't increment the reference count, since that would be a self-
773  // referential leak.)
774  }
775 
776  return result;
777 }
778 
779 /**
780  * This method overrides ReferenceCount::unref() to check whether the
781  * remaining reference count is entirely in the cache, and if so, it checks
782  * for and breaks a cycle in the cache involving this object. This is
783  * designed to prevent leaks from cyclical references within the cache.
784  */
785 bool TransformState::
786 unref() const {
787  if (garbage_collect_states || !transform_cache) {
788  // If we're not using the cache at all, or if we're relying on garbage
789  // collection, just allow the pointer to unref normally.
790  return ReferenceCount::unref();
791  }
792 
793  // Here is the normal refcounting case, with a normal cache, and without
794  // garbage collection in effect. In this case we will pull the object out
795  // of the cache when its reference count goes to 0.
796 
797  // We always have to grab the lock, since we will definitely need to be
798  // holding it if we happen to drop the reference count to 0. Having to grab
799  // the lock at every call to unref() is a big limiting factor on
800  // parallelization.
801  LightReMutexHolder holder(*_states_lock);
802 
803  if (auto_break_cycles && uniquify_transforms) {
804  if (get_cache_ref_count() > 0 &&
805  get_ref_count() == get_cache_ref_count() + 1) {
806  // If we are about to remove the one reference that is not in the cache,
807  // leaving only references in the cache, then we need to check for a
808  // cycle involving this TransformState and break it if it exists.
809  ((TransformState *)this)->detect_and_break_cycles();
810  }
811  }
812 
813  if (ReferenceCount::unref()) {
814  // The reference count is still nonzero.
815  return true;
816  }
817 
818  // The reference count has just reached zero. Make sure the object is
819  // removed from the global object pool, before anyone else finds it and
820  // tries to ref it.
821  ((TransformState *)this)->release_new();
822  ((TransformState *)this)->remove_cache_pointers();
823 
824  return false;
825 }
826 
827 /**
828  * Returns true if the composition cache and invert composition cache for this
829  * particular TransformState are self-consistent and valid, false otherwise.
830  */
831 bool TransformState::
832 validate_composition_cache() const {
833  LightReMutexHolder holder(*_states_lock);
834 
835  size_t size = _composition_cache.get_num_entries();
836  for (size_t i = 0; i < size; ++i) {
837  const TransformState *source = _composition_cache.get_key(i);
838  if (source != nullptr) {
839  // Check that the source also has a pointer back to this one. We always
840  // add entries to the composition cache in pairs.
841  int ri = source->_composition_cache.find(this);
842  if (ri == -1) {
843  // Failure! There is no back-pointer.
844  pgraph_cat.error()
845  << "TransformState::composition cache is inconsistent!\n";
846  pgraph_cat.error(false)
847  << *this << " compose " << *source << "\n";
848  pgraph_cat.error(false)
849  << "but no reverse\n";
850  return false;
851  }
852  }
853  }
854 
855  size = _invert_composition_cache.get_num_entries();
856  for (size_t i = 0; i < size; ++i) {
857  const TransformState *source = _invert_composition_cache.get_key(i);
858  if (source != nullptr) {
859  // Check that the source also has a pointer back to this one. We always
860  // add entries to the composition cache in pairs.
861  int ri = source->_invert_composition_cache.find(this);
862  if (ri == -1) {
863  // Failure! There is no back-pointer.
864  pgraph_cat.error()
865  << "TransformState::invert composition cache is inconsistent!\n";
866  pgraph_cat.error(false)
867  << *this << " invert compose " << *source << "\n";
868  pgraph_cat.error(false)
869  << "but no reverse\n";
870  return false;
871  }
872  }
873  }
874 
875  return true;
876 }
877 
878 /**
879  *
880  */
881 void TransformState::
882 output(ostream &out) const {
883  out << "T:";
884  if (is_invalid()) {
885  out << "(invalid)";
886 
887  } else if (is_identity()) {
888  out << "(identity)";
889 
890  } else if (has_components()) {
891  bool output_hpr = !get_hpr().almost_equal(LVecBase3(0.0f, 0.0f, 0.0f));
892 
893  if (!components_given()) {
894  // A leading "m" indicates the transform was described as a full matrix,
895  // and we are decomposing it for the benefit of the user.
896  out << "m";
897 
898  } else if (output_hpr && quat_given()) {
899  // A leading "q" indicates that the pos, scale, and shear are exactly as
900  // specified, but the rotation was described as a quaternion, and we are
901  // decomposing that to hpr for the benefit of the user.
902  out << "q";
903  }
904 
905  char lead = '(';
906  if (is_2d()) {
907  if (!get_pos2d().almost_equal(LVecBase2(0.0f, 0.0f))) {
908  out << lead << "pos " << get_pos2d();
909  lead = ' ';
910  }
911  if (output_hpr) {
912  out << lead << "rotate " << get_rotate2d();
913  lead = ' ';
914  }
915  if (!get_scale2d().almost_equal(LVecBase2(1.0f, 1.0f))) {
916  if (has_uniform_scale()) {
917  out << lead << "scale " << get_uniform_scale();
918  lead = ' ';
919  } else {
920  out << lead << "scale " << get_scale2d();
921  lead = ' ';
922  }
923  }
924  if (has_nonzero_shear()) {
925  out << lead << "shear " << get_shear2d();
926  lead = ' ';
927  }
928  } else {
929  if (!get_pos().almost_equal(LVecBase3(0.0f, 0.0f, 0.0f))) {
930  out << lead << "pos " << get_pos();
931  lead = ' ';
932  }
933  if (output_hpr) {
934  out << lead << "hpr " << get_hpr();
935  lead = ' ';
936  }
937  if (!get_scale().almost_equal(LVecBase3(1.0f, 1.0f, 1.0f))) {
938  if (has_uniform_scale()) {
939  out << lead << "scale " << get_uniform_scale();
940  lead = ' ';
941  } else {
942  out << lead << "scale " << get_scale();
943  lead = ' ';
944  }
945  }
946  if (has_nonzero_shear()) {
947  out << lead << "shear " << get_shear();
948  lead = ' ';
949  }
950  }
951  if (lead == '(') {
952  out << "(almost identity)";
953  } else {
954  out << ")";
955  }
956 
957  } else {
958  if (is_2d()) {
959  out << get_mat3();
960  } else {
961  out << get_mat();
962  }
963  }
964 }
965 
966 /**
967  *
968  */
969 void TransformState::
970 write(ostream &out, int indent_level) const {
971  indent(out, indent_level) << *this << "\n";
972 }
973 
974 /**
975  * Writes a brief description of the composition cache and invert composition
976  * cache to the indicated ostream. This is not useful except for performance
977  * analysis, to examine the cache structure.
978  */
979 void TransformState::
980 write_composition_cache(ostream &out, int indent_level) const {
981  indent(out, indent_level + 2) << _composition_cache << "\n";
982  indent(out, indent_level + 2) << _invert_composition_cache << "\n";
983 }
984 
985 /**
986  * Returns the total number of unique TransformState objects allocated in the
987  * world. This will go up and down during normal operations.
988  */
989 int TransformState::
990 get_num_states() {
991  if (_states == nullptr) {
992  return 0;
993  }
994  LightReMutexHolder holder(*_states_lock);
995  return _states->get_num_entries();
996 }
997 
998 /**
999  * Returns the total number of TransformState objects that have been allocated
1000  * but have no references outside of the internal TransformState cache.
1001  *
1002  * A nonzero return value is not necessarily indicative of leaked references;
1003  * it is normal for two TransformState objects, both of which have references
1004  * held outside the cache, to have the result of their composition stored
1005  * within the cache. This result will be retained within the cache until one
1006  * of the base TransformStates is released.
1007  *
1008  * Use list_cycles() to get an idea of the number of actual "leaked"
1009  * TransformState objects.
1010  */
1011 int TransformState::
1012 get_num_unused_states() {
1013  if (_states == nullptr) {
1014  return 0;
1015  }
1016  LightReMutexHolder holder(*_states_lock);
1017 
1018  // First, we need to count the number of times each TransformState object is
1019  // recorded in the cache. We could just trust get_cache_ref_count(), but
1020  // we'll be extra cautious for now.
1021  typedef pmap<const TransformState *, int> StateCount;
1022  StateCount state_count;
1023 
1024  size_t size = _states->get_num_entries();
1025  for (size_t si = 0; si < size; ++si) {
1026  const TransformState *state = _states->get_key(si);
1027 
1028  size_t i;
1029  size_t cache_size = state->_composition_cache.get_num_entries();
1030  for (i = 0; i < cache_size; ++i) {
1031  const TransformState *result = state->_composition_cache.get_data(i)._result;
1032  if (result != nullptr && result != state) {
1033  // Here's a TransformState that's recorded in the cache. Count it.
1034  std::pair<StateCount::iterator, bool> ir =
1035  state_count.insert(StateCount::value_type(result, 1));
1036  if (!ir.second) {
1037  // If the above insert operation fails, then it's already in the
1038  // cache; increment its value.
1039  (*(ir.first)).second++;
1040  }
1041  }
1042  }
1043  cache_size = state->_invert_composition_cache.get_num_entries();
1044  for (i = 0; i < cache_size; ++i) {
1045  const TransformState *result = state->_invert_composition_cache.get_data(i)._result;
1046  if (result != nullptr && result != state) {
1047  std::pair<StateCount::iterator, bool> ir =
1048  state_count.insert(StateCount::value_type(result, 1));
1049  if (!ir.second) {
1050  (*(ir.first)).second++;
1051  }
1052  }
1053  }
1054  }
1055 
1056  // Now that we have the appearance count of each TransformState object, we
1057  // can tell which ones are unreferenced outside of the TransformState cache,
1058  // by comparing these to the reference counts.
1059  int num_unused = 0;
1060 
1061  StateCount::iterator sci;
1062  for (sci = state_count.begin(); sci != state_count.end(); ++sci) {
1063  const TransformState *state = (*sci).first;
1064  int count = (*sci).second;
1065  nassertr(count == state->get_cache_ref_count(), num_unused);
1066  nassertr(count <= state->get_ref_count(), num_unused);
1067  if (count == state->get_ref_count()) {
1068  num_unused++;
1069 
1070  if (pgraph_cat.is_debug()) {
1071  pgraph_cat.debug()
1072  << "Unused state: " << (void *)state << ":"
1073  << state->get_ref_count() << " =\n";
1074  state->write(pgraph_cat.debug(false), 2);
1075  }
1076  }
1077  }
1078 
1079  return num_unused;
1080 }
1081 
1082 /**
1083  * Empties the cache of composed TransformStates. This makes every
1084  * TransformState forget what results when it is composed with other
1085  * TransformStates.
1086  *
1087  * This will eliminate any TransformState objects that have been allocated but
1088  * have no references outside of the internal TransformState map. It will not
1089  * eliminate TransformState objects that are still in use.
1090  *
1091  * Nowadays, this method should not be necessary, as reference-count cycles in
1092  * the composition cache should be automatically detected and broken.
1093  *
1094  * The return value is the number of TransformStates freed by this operation.
1095  */
1096 int TransformState::
1097 clear_cache() {
1098  if (_states == nullptr) {
1099  return 0;
1100  }
1101  LightReMutexHolder holder(*_states_lock);
1102 
1103  PStatTimer timer(_cache_update_pcollector);
1104  int orig_size = _states->get_num_entries();
1105 
1106  // First, we need to copy the entire set of states to a temporary vector,
1107  // reference-counting each object. That way we can walk through the copy,
1108  // without fear of dereferencing (and deleting) the objects in the map as we
1109  // go.
1110  {
1111  typedef pvector< CPT(TransformState) > TempStates;
1112  TempStates temp_states;
1113  temp_states.reserve(orig_size);
1114 
1115  size_t size = _states->get_num_entries();
1116  for (size_t si = 0; si < size; ++si) {
1117  const TransformState *state = _states->get_key(si);
1118  temp_states.push_back(state);
1119  }
1120 
1121  // Now it's safe to walk through the list, destroying the cache within
1122  // each object as we go. Nothing will be destructed till we're done.
1123  TempStates::iterator ti;
1124  for (ti = temp_states.begin(); ti != temp_states.end(); ++ti) {
1125  TransformState *state = (TransformState *)(*ti).p();
1126 
1127  size_t i;
1128  size_t cache_size = state->_composition_cache.get_num_entries();
1129  for (i = 0; i < cache_size; ++i) {
1130  const TransformState *result = state->_composition_cache.get_data(i)._result;
1131  if (result != nullptr && result != state) {
1132  result->cache_unref();
1133  nassertr(result->get_ref_count() > 0, 0);
1134  }
1135  }
1136  _cache_stats.add_total_size(-(int)state->_composition_cache.get_num_entries());
1137  state->_composition_cache.clear();
1138 
1139  cache_size = state->_invert_composition_cache.get_num_entries();
1140  for (i = 0; i < cache_size; ++i) {
1141  const TransformState *result = state->_invert_composition_cache.get_data(i)._result;
1142  if (result != nullptr && result != state) {
1143  result->cache_unref();
1144  nassertr(result->get_ref_count() > 0, 0);
1145  }
1146  }
1147  _cache_stats.add_total_size(-(int)state->_invert_composition_cache.get_num_entries());
1148  state->_invert_composition_cache.clear();
1149  }
1150 
1151  // Once this block closes and the temp_states object goes away, all the
1152  // destruction will begin. Anything whose reference was held only within
1153  // the various objects' caches will go away.
1154  }
1155 
1156  int new_size = _states->get_num_entries();
1157  return orig_size - new_size;
1158 }
1159 
1160 /**
1161  * Performs a garbage-collection cycle. This must be called periodically if
1162  * garbage-collect-states is true to ensure that TransformStates get cleaned
1163  * up appropriately. It does no harm to call it even if this variable is not
1164  * true, but there is probably no advantage in that case.
1165  */
1166 int TransformState::
1167 garbage_collect() {
1168  if (_states == nullptr || !garbage_collect_states) {
1169  return 0;
1170  }
1171 
1172  LightReMutexHolder holder(*_states_lock);
1173 
1174  PStatTimer timer(_garbage_collect_pcollector);
1175  size_t orig_size = _states->get_num_entries();
1176 
1177  // How many elements to process this pass?
1178  size_t size = orig_size;
1179  size_t num_this_pass = std::max(0, int(size * garbage_collect_states_rate));
1180  if (num_this_pass <= 0) {
1181  return 0;
1182  }
1183 
1184  bool break_and_uniquify = (auto_break_cycles && uniquify_transforms);
1185 
1186  size_t si = _garbage_index;
1187  if (si >= size) {
1188  si = 0;
1189  }
1190 
1191  num_this_pass = std::min(num_this_pass, size);
1192  size_t stop_at_element = (si + num_this_pass) % size;
1193 
1194  do {
1195  TransformState *state = (TransformState *)_states->get_key(si);
1196  if (break_and_uniquify) {
1197  if (state->get_cache_ref_count() > 0 &&
1198  state->get_ref_count() == state->get_cache_ref_count()) {
1199  // If we have removed all the references to this state not in the
1200  // cache, leaving only references in the cache, then we need to
1201  // check for a cycle involving this TransformState and break it if
1202  // it exists.
1203  state->detect_and_break_cycles();
1204  }
1205  }
1206 
1207  if (!state->unref_if_one()) {
1208  // This state has recently been unreffed to 1 (the one we added when
1209  // we stored it in the cache). Now it's time to delete it. This is
1210  // safe, because we're holding the _states_lock, so it's not possible
1211  // for some other thread to find the state in the cache and ref it
1212  // while we're doing this. Also, we've just made sure to unref it to 0,
1213  // to ensure that another thread can't get it via a weak pointer.
1214  state->release_new();
1215  state->remove_cache_pointers();
1216  state->cache_unref_only();
1217  delete state;
1218 
1219  // When we removed it from the hash map, it swapped the last element
1220  // with the one we just removed. So the current index contains one we
1221  // still need to visit.
1222  --size;
1223  --si;
1224  if (stop_at_element > 0) {
1225  --stop_at_element;
1226  }
1227  }
1228 
1229  si = (si + 1) % size;
1230  } while (si != stop_at_element);
1231  _garbage_index = si;
1232 
1233  nassertr(_states->get_num_entries() == size, 0);
1234 
1235 #ifdef _DEBUG
1236  nassertr(_states->validate(), 0);
1237 #endif
1238 
1239  // If we just cleaned up a lot of states, see if we can reduce the table in
1240  // size. This will help reduce iteration overhead in the future.
1241  _states->consider_shrink_table();
1242 
1243  return (int)orig_size - (int)size;
1244 }
1245 
1246 /**
1247  * Detects all of the reference-count cycles in the cache and reports them to
1248  * standard output.
1249  *
1250  * These cycles may be inadvertently created when state compositions cycle
1251  * back to a starting point. Nowadays, these cycles should be automatically
1252  * detected and broken, so this method should never list any cycles unless
1253  * there is a bug in that detection logic.
1254  *
1255  * The cycles listed here are not leaks in the strictest sense of the word,
1256  * since they can be reclaimed by a call to clear_cache(); but they will not
1257  * be reclaimed automatically.
1258  */
1259 void TransformState::
1260 list_cycles(ostream &out) {
1261  if (_states == nullptr) {
1262  return;
1263  }
1264  LightReMutexHolder holder(*_states_lock);
1265 
1266  typedef pset<const TransformState *> VisitedStates;
1267  VisitedStates visited;
1268  CompositionCycleDesc cycle_desc;
1269 
1270  size_t size = _states->get_num_entries();
1271  for (size_t si = 0; si < size; ++si) {
1272  const TransformState *state = _states->get_key(si);
1273 
1274  bool inserted = visited.insert(state).second;
1275  if (inserted) {
1276  ++_last_cycle_detect;
1277  if (r_detect_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
1278  // This state begins a cycle.
1279  CompositionCycleDesc::reverse_iterator csi;
1280 
1281  out << "\nCycle detected of length " << cycle_desc.size() + 1 << ":\n"
1282  << "state " << (void *)state << ":" << state->get_ref_count()
1283  << " =\n";
1284  state->write(out, 2);
1285  for (csi = cycle_desc.rbegin(); csi != cycle_desc.rend(); ++csi) {
1286  const CompositionCycleDescEntry &entry = (*csi);
1287  if (entry._inverted) {
1288  out << "invert composed with ";
1289  } else {
1290  out << "composed with ";
1291  }
1292  out << (const void *)entry._obj << ":" << entry._obj->get_ref_count()
1293  << " " << *entry._obj << "\n"
1294  << "produces " << (const void *)entry._result << ":"
1295  << entry._result->get_ref_count() << " =\n";
1296  entry._result->write(out, 2);
1297  visited.insert(entry._result);
1298  }
1299 
1300  cycle_desc.clear();
1301  } else {
1302  ++_last_cycle_detect;
1303  if (r_detect_reverse_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
1304  // This state begins a cycle.
1305  CompositionCycleDesc::iterator csi;
1306 
1307  out << "\nReverse cycle detected of length " << cycle_desc.size() + 1 << ":\n"
1308  << "state ";
1309  for (csi = cycle_desc.begin(); csi != cycle_desc.end(); ++csi) {
1310  const CompositionCycleDescEntry &entry = (*csi);
1311  out << (const void *)entry._result << ":"
1312  << entry._result->get_ref_count() << " =\n";
1313  entry._result->write(out, 2);
1314  out << (const void *)entry._obj << ":"
1315  << entry._obj->get_ref_count() << " =\n";
1316  entry._obj->write(out, 2);
1317  visited.insert(entry._result);
1318  }
1319  out << (void *)state << ":"
1320  << state->get_ref_count() << " =\n";
1321  state->write(out, 2);
1322 
1323  cycle_desc.clear();
1324  }
1325  }
1326  }
1327  }
1328 }
1329 
1330 
1331 /**
1332  * Lists all of the TransformStates in the cache to the output stream, one per
1333  * line. This can be quite a lot of output if the cache is large, so be
1334  * prepared.
1335  */
1336 void TransformState::
1337 list_states(ostream &out) {
1338  if (_states == nullptr) {
1339  out << "0 states:\n";
1340  return;
1341  }
1342  LightReMutexHolder holder(*_states_lock);
1343 
1344  size_t size = _states->get_num_entries();
1345  out << size << " states:\n";
1346  for (size_t si = 0; si < size; ++si) {
1347  const TransformState *state = _states->get_key(si);
1348  state->write(out, 2);
1349  }
1350 }
1351 
1352 /**
1353  * Ensures that the cache is still stored in sorted order, and that none of
1354  * the cache elements have been inadvertently deleted. Returns true if so,
1355  * false if there is a problem (which implies someone has modified one of the
1356  * supposedly-const TransformState objects).
1357  */
1358 bool TransformState::
1359 validate_states() {
1360  if (_states == nullptr) {
1361  return true;
1362  }
1363 
1364  PStatTimer timer(_transform_validate_pcollector);
1365 
1366  LightReMutexHolder holder(*_states_lock);
1367  if (_states->is_empty()) {
1368  return true;
1369  }
1370 
1371  if (!_states->validate()) {
1372  pgraph_cat.error()
1373  << "TransformState::_states cache is invalid!\n";
1374  return false;
1375  }
1376 
1377  size_t size = _states->get_num_entries();
1378  size_t si = 0;
1379  nassertr(si < size, false);
1380  nassertr(_states->get_key(si)->get_ref_count() >= 0, false);
1381  size_t snext = si;
1382  ++snext;
1383  while (snext < size) {
1384  nassertr(_states->get_key(snext)->get_ref_count() >= 0, false);
1385  const TransformState *ssi = _states->get_key(si);
1386  if (!ssi->validate_composition_cache()) {
1387  return false;
1388  }
1389  const TransformState *ssnext = _states->get_key(snext);
1390  bool c = (*ssi) == (*ssnext);
1391  bool ci = (*ssnext) == (*ssi);
1392  if (c != ci) {
1393  pgraph_cat.error()
1394  << "TransformState::operator == () not defined properly!\n";
1395  pgraph_cat.error(false)
1396  << "(a, b): " << c << "\n";
1397  pgraph_cat.error(false)
1398  << "(b, a): " << ci << "\n";
1399  ssi->write(pgraph_cat.error(false), 2);
1400  ssnext->write(pgraph_cat.error(false), 2);
1401  return false;
1402  }
1403  si = snext;
1404  ++snext;
1405  }
1406 
1407  return true;
1408 }
1409 
1410 /**
1411  * Make sure the global _states map is allocated. This only has to be done
1412  * once. We could make this map static, but then we run into problems if
1413  * anyone creates a TransformState object at static init time; it also seems
1414  * to cause problems when the Panda shared library is unloaded at application
1415  * exit time.
1416  */
1417 void TransformState::
1418 init_states() {
1419  _states = new States;
1420 
1421  ConfigVariableBool uniquify_matrix
1422  ("uniquify-matrix", true,
1423  PRC_DESC("Set this true to look up arbitrary 4x4 transform matrices in "
1424  "the cache, to ensure that two differently-computed transforms "
1425  "that happen to encode the same matrix will be collapsed into "
1426  "a single pointer. Nowadays, with the transforms stored in a "
1427  "hashtable, we're generally better off with this set true."));
1428 
1429  // Store this at the beginning, so that we don't have to query this every
1430  // time that the comparison operator is invoked.
1431  _uniquify_matrix = uniquify_matrix;
1432 
1433  // TODO: we should have a global Panda mutex to allow us to safely create
1434  // _states_lock without a startup race condition. For the meantime, this is
1435  // OK because we guarantee that this method is called at static init time,
1436  // presumably when there is still only one thread in the world.
1437  _states_lock = new LightReMutex("TransformState::_states_lock");
1438  _cache_stats.init();
1440 }
1441 
1442 /**
1443  * This function is used to share a common TransformState pointer for all
1444  * equivalent TransformState objects.
1445  *
1446  * This is different from return_unique() in that it does not actually
1447  * guarantee a unique pointer, unless uniquify-transforms is set.
1448  */
1449 CPT(TransformState) TransformState::
1450 return_new(TransformState *state) {
1451  nassertr(state != nullptr, state);
1452  if (!uniquify_transforms && !state->is_identity()) {
1453  return state;
1454  }
1455 
1456  return return_unique(state);
1457 }
1458 
1459 /**
1460  * This function is used to share a common TransformState pointer for all
1461  * equivalent TransformState objects.
1462  *
1463  * See the similar logic in RenderState. The idea is to create a new
1464  * TransformState object and pass it through this function, which will share
1465  * the pointer with a previously-created TransformState object if it is
1466  * equivalent.
1467  */
1468 CPT(TransformState) TransformState::
1469 return_unique(TransformState *state) {
1470  nassertr(state != nullptr, state);
1471 
1472  if (!transform_cache) {
1473  return state;
1474  }
1475 
1476 #ifndef NDEBUG
1477  if (paranoid_const) {
1478  nassertr(validate_states(), state);
1479  }
1480 #endif
1481 
1482  PStatTimer timer(_transform_new_pcollector);
1483 
1484  LightReMutexHolder holder(*_states_lock);
1485 
1486  if (state->_saved_entry != -1) {
1487  // This state is already in the cache. nassertr(_states->find(state) ==
1488  // state->_saved_entry, state);
1489  return state;
1490  }
1491 
1492  // Save the state in a local PointerTo so that it will be freed at the end
1493  // of this function if no one else uses it.
1494  CPT(TransformState) pt_state = state;
1495 
1496  int si = _states->find(state);
1497  if (si != -1) {
1498  // There's an equivalent state already in the set. Return it.
1499  return _states->get_key(si);
1500  }
1501 
1502  // Not already in the set; add it.
1503  if (garbage_collect_states) {
1504  // If we'll be garbage collecting states explicitly, we'll increment the
1505  // reference count when we store it in the cache, so that it won't be
1506  // deleted while it's in it.
1507  state->cache_ref();
1508  }
1509  si = _states->store(state, nullptr);
1510 
1511  // Save the index and return the input state.
1512  state->_saved_entry = si;
1513  return pt_state;
1514 }
1515 
1516 /**
1517  * The private implemention of compose(); this actually composes two
1518  * TransformStates, without bothering with the cache.
1519  */
1520 CPT(TransformState) TransformState::
1521 do_compose(const TransformState *other) const {
1522  PStatTimer timer(_transform_compose_pcollector);
1523 
1524  nassertr((_flags & F_is_invalid) == 0, this);
1525  nassertr((other->_flags & F_is_invalid) == 0, other);
1526 
1527  if (compose_componentwise &&
1528  has_uniform_scale() &&
1529  !has_nonzero_shear() && !other->has_nonzero_shear() &&
1530  ((components_given() && other->has_components()) ||
1531  (other->components_given() && has_components()))) {
1532  // We will do this operation componentwise if *either* transform was given
1533  // componentwise (and there is no non-uniform scale in the way).
1534 
1535  CPT(TransformState) result;
1536  if (is_2d() && other->is_2d()) {
1537  // Do a 2-d compose.
1538  LVecBase2 pos = get_pos2d();
1539  PN_stdfloat rotate = get_rotate2d();
1540  LQuaternion quat = get_norm_quat();
1541  PN_stdfloat scale = get_uniform_scale();
1542 
1543  LPoint3 op = quat.xform(other->get_pos());
1544  pos += LVecBase2(op[0], op[1]) * scale;
1545 
1546  rotate += other->get_rotate2d();
1547  LVecBase2 new_scale = other->get_scale2d() * scale;
1548 
1549  result = make_pos_rotate_scale2d(pos, rotate, new_scale);
1550 
1551  } else {
1552  // A normal 3-d compose.
1553  LVecBase3 pos = get_pos();
1554  LQuaternion quat = get_norm_quat();
1555  PN_stdfloat scale = get_uniform_scale();
1556 
1557  pos += quat.xform(other->get_pos()) * scale;
1558  quat = other->get_norm_quat() * quat;
1559  LVecBase3 new_scale = other->get_scale() * scale;
1560 
1561  result = make_pos_quat_scale(pos, quat, new_scale);
1562  }
1563 
1564 #ifndef NDEBUG
1565  if (paranoid_compose) {
1566  // Now verify against the matrix.
1567  LMatrix4 new_mat;
1568  new_mat.multiply(other->get_mat(), get_mat());
1569  if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
1570  CPT(TransformState) correct = make_mat(new_mat);
1571  pgraph_cat.warning()
1572  << "Componentwise composition of " << *this << " and " << *other
1573  << " produced:\n"
1574  << *result << "\n instead of:\n" << *correct << "\n";
1575  result = correct;
1576  }
1577  }
1578 #endif // NDEBUG
1579 
1580  return result;
1581  }
1582 
1583  // Do the operation with matrices.
1584  if (is_2d() && other->is_2d()) {
1585  LMatrix3 new_mat = other->get_mat3() * get_mat3();
1586  return make_mat3(new_mat);
1587  } else {
1588  LMatrix4 new_mat;
1589  new_mat.multiply(other->get_mat(), get_mat());
1590  return make_mat(new_mat);
1591  }
1592 }
1593 
1594 /**
1595  * The private implemention of invert_compose().
1596  */
1597 CPT(TransformState) TransformState::
1598 do_invert_compose(const TransformState *other) const {
1599  PStatTimer timer(_transform_invert_pcollector);
1600 
1601  nassertr((_flags & F_is_invalid) == 0, this);
1602  nassertr((other->_flags & F_is_invalid) == 0, other);
1603 
1604  if (compose_componentwise &&
1605  has_uniform_scale() &&
1606  !has_nonzero_shear() && !other->has_nonzero_shear() &&
1607  ((components_given() && other->has_components()) ||
1608  (other->components_given() && has_components()))) {
1609  // We will do this operation componentwise if *either* transform was given
1610  // componentwise (and there is no non-uniform scale in the way).
1611 
1612  CPT(TransformState) result;
1613  if (is_2d() && other->is_2d()) {
1614  // Do a 2-d invert compose.
1615  LVecBase2 pos = get_pos2d();
1616  PN_stdfloat rotate = get_rotate2d();
1617  LQuaternion quat = get_norm_quat();
1618  PN_stdfloat scale = get_uniform_scale();
1619 
1620  // First, invert our own transform.
1621  if (scale == 0.0f) {
1622  ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
1623  return make_invalid();
1624  }
1625  scale = 1.0f / scale;
1626  quat.invert_in_place();
1627  rotate = -rotate;
1628  LVecBase3 mp = quat.xform(-LVecBase3(pos[0], pos[1], 0.0f));
1629  pos = LVecBase2(mp[0], mp[1]) * scale;
1630  LVecBase2 new_scale(scale, scale);
1631 
1632  // Now compose the inverted transform with the other transform.
1633  if (!other->is_identity()) {
1634  LPoint3 op = quat.xform(other->get_pos());
1635  pos += LVecBase2(op[0], op[1]) * scale;
1636 
1637  rotate += other->get_rotate2d();
1638  new_scale = other->get_scale2d() * scale;
1639  }
1640 
1641  result = make_pos_rotate_scale2d(pos, rotate, new_scale);
1642 
1643  } else {
1644  // Do a normal, 3-d invert compose.
1645  LVecBase3 pos = get_pos();
1646  LQuaternion quat = get_norm_quat();
1647  PN_stdfloat scale = get_uniform_scale();
1648 
1649  // First, invert our own transform.
1650  if (scale == 0.0f) {
1651  ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
1652  return make_invalid();
1653  }
1654  scale = 1.0f / scale;
1655  quat.invert_in_place();
1656  pos = quat.xform(-pos) * scale;
1657  LVecBase3 new_scale(scale, scale, scale);
1658 
1659  // Now compose the inverted transform with the other transform.
1660  if (!other->is_identity()) {
1661  pos += quat.xform(other->get_pos()) * scale;
1662  quat = other->get_norm_quat() * quat;
1663  new_scale = other->get_scale() * scale;
1664  }
1665 
1666  result = make_pos_quat_scale(pos, quat, new_scale);
1667  }
1668 
1669 #ifndef NDEBUG
1670  if (paranoid_compose) {
1671  // Now verify against the matrix.
1672  if (is_singular()) {
1673  pgraph_cat.warning()
1674  << "Unexpected singular matrix found for " << *this << "\n";
1675  } else {
1676  nassertr(_inv_mat != nullptr, make_invalid());
1677  LMatrix4 new_mat;
1678  new_mat.multiply(other->get_mat(), *_inv_mat);
1679  if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
1680  CPT(TransformState) correct = make_mat(new_mat);
1681  pgraph_cat.warning()
1682  << "Componentwise invert-composition of " << *this << " and " << *other
1683  << " produced:\n"
1684  << *result << "\n instead of:\n" << *correct << "\n";
1685  result = correct;
1686  }
1687  }
1688  }
1689 #endif // NDEBUG
1690 
1691  return result;
1692  }
1693 
1694  if (is_singular()) {
1695  return make_invalid();
1696  }
1697 
1698  // Now that is_singular() has returned false, we can assume that _inv_mat
1699  // has been allocated and filled in.
1700  nassertr(_inv_mat != nullptr, make_invalid());
1701 
1702  if (is_2d() && other->is_2d()) {
1703  const LMatrix4 &i = *_inv_mat;
1704  LMatrix3 inv3(i(0, 0), i(0, 1), i(0, 3),
1705  i(1, 0), i(1, 1), i(1, 3),
1706  i(3, 0), i(3, 1), i(3, 3));
1707  if (other->is_identity()) {
1708  return make_mat3(inv3);
1709  } else {
1710  return make_mat3(other->get_mat3() * inv3);
1711  }
1712  } else {
1713  if (other->is_identity()) {
1714  return make_mat(*_inv_mat);
1715  } else {
1716  return make_mat(other->get_mat() * (*_inv_mat));
1717  }
1718  }
1719 }
1720 
1721 /**
1722  * Detects whether there is a cycle in the cache that begins with this state.
1723  * If any are detected, breaks them by removing this state from the cache.
1724  */
1725 void TransformState::
1726 detect_and_break_cycles() {
1727  PStatTimer timer(_transform_break_cycles_pcollector);
1728 
1729  ++_last_cycle_detect;
1730  if (r_detect_cycles(this, this, 1, _last_cycle_detect, nullptr)) {
1731  // Ok, we have a cycle. This will be a leak unless we break the cycle by
1732  // freeing the cache on this object.
1733  if (pgraph_cat.is_debug()) {
1734  pgraph_cat.debug()
1735  << "Breaking cycle involving " << (*this) << "\n";
1736  }
1737 
1738  remove_cache_pointers();
1739  } else {
1740  ++_last_cycle_detect;
1741  if (r_detect_reverse_cycles(this, this, 1, _last_cycle_detect, nullptr)) {
1742  if (pgraph_cat.is_debug()) {
1743  pgraph_cat.debug()
1744  << "Breaking cycle involving " << (*this) << "\n";
1745  }
1746 
1747  remove_cache_pointers();
1748  }
1749  }
1750 }
1751 
1752 /**
1753  * Detects whether there is a cycle in the cache that begins with the
1754  * indicated state. Returns true if at least one cycle is found, false if
1755  * this state is not part of any cycles. If a cycle is found and cycle_desc
1756  * is not NULL, then cycle_desc is filled in with the list of the steps of the
1757  * cycle, in reverse order.
1758  */
1759 bool TransformState::
1760 r_detect_cycles(const TransformState *start_state,
1761  const TransformState *current_state,
1762  int length, UpdateSeq this_seq,
1764  if (current_state->_cycle_detect == this_seq) {
1765  // We've already seen this state; therefore, we've found a cycle.
1766 
1767  // However, we only care about cycles that return to the starting state
1768  // and involve more than two steps. If only one or two nodes are
1769  // involved, it doesn't represent a memory leak, so no problem there.
1770  return (current_state == start_state && length > 2);
1771  }
1772  ((TransformState *)current_state)->_cycle_detect = this_seq;
1773 
1774  size_t i;
1775  size_t cache_size = current_state->_composition_cache.get_num_entries();
1776  for (i = 0; i < cache_size; ++i) {
1777  const TransformState *result = current_state->_composition_cache.get_data(i)._result;
1778  if (result != nullptr) {
1779  if (r_detect_cycles(start_state, result, length + 1,
1780  this_seq, cycle_desc)) {
1781  // Cycle detected.
1782  if (cycle_desc != nullptr) {
1783  const TransformState *other = current_state->_composition_cache.get_key(i);
1784  CompositionCycleDescEntry entry(other, result, false);
1785  cycle_desc->push_back(entry);
1786  }
1787  return true;
1788  }
1789  }
1790  }
1791 
1792  cache_size = current_state->_invert_composition_cache.get_num_entries();
1793  for (i = 0; i < cache_size; ++i) {
1794  const TransformState *result = current_state->_invert_composition_cache.get_data(i)._result;
1795  if (result != nullptr) {
1796  if (r_detect_cycles(start_state, result, length + 1,
1797  this_seq, cycle_desc)) {
1798  // Cycle detected.
1799  if (cycle_desc != nullptr) {
1800  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1801  CompositionCycleDescEntry entry(other, result, true);
1802  cycle_desc->push_back(entry);
1803  }
1804  return true;
1805  }
1806  }
1807  }
1808 
1809  // No cycle detected.
1810  return false;
1811 }
1812 
1813 /**
1814  * Works the same as r_detect_cycles, but checks for cycles in the reverse
1815  * direction along the cache chain. (A cycle may appear in either direction,
1816  * and we must check both.)
1817  */
1818 bool TransformState::
1819 r_detect_reverse_cycles(const TransformState *start_state,
1820  const TransformState *current_state,
1821  int length, UpdateSeq this_seq,
1823  if (current_state->_cycle_detect == this_seq) {
1824  // We've already seen this state; therefore, we've found a cycle.
1825 
1826  // However, we only care about cycles that return to the starting state
1827  // and involve more than two steps. If only one or two nodes are
1828  // involved, it doesn't represent a memory leak, so no problem there.
1829  return (current_state == start_state && length > 2);
1830  }
1831  ((TransformState *)current_state)->_cycle_detect = this_seq;
1832 
1833  size_t i;
1834  size_t cache_size = current_state->_composition_cache.get_num_entries();
1835  for (i = 0; i < cache_size; ++i) {
1836  const TransformState *other = current_state->_composition_cache.get_key(i);
1837  if (other != current_state) {
1838  int oi = other->_composition_cache.find(current_state);
1839  nassertr(oi != -1, false);
1840 
1841  const TransformState *result = other->_composition_cache.get_data(oi)._result;
1842  if (result != nullptr) {
1843  if (r_detect_reverse_cycles(start_state, result, length + 1,
1844  this_seq, cycle_desc)) {
1845  // Cycle detected.
1846  if (cycle_desc != nullptr) {
1847  const TransformState *other = current_state->_composition_cache.get_key(i);
1848  CompositionCycleDescEntry entry(other, result, false);
1849  cycle_desc->push_back(entry);
1850  }
1851  return true;
1852  }
1853  }
1854  }
1855  }
1856 
1857  cache_size = current_state->_invert_composition_cache.get_num_entries();
1858  for (i = 0; i < cache_size; ++i) {
1859  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1860  if (other != current_state) {
1861  int oi = other->_invert_composition_cache.find(current_state);
1862  nassertr(oi != -1, false);
1863 
1864  const TransformState *result = other->_invert_composition_cache.get_data(oi)._result;
1865  if (result != nullptr) {
1866  if (r_detect_reverse_cycles(start_state, result, length + 1,
1867  this_seq, cycle_desc)) {
1868  // Cycle detected.
1869  if (cycle_desc != nullptr) {
1870  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1871  CompositionCycleDescEntry entry(other, result, false);
1872  cycle_desc->push_back(entry);
1873  }
1874  return true;
1875  }
1876  }
1877  }
1878  }
1879 
1880  // No cycle detected.
1881  return false;
1882 }
1883 
1884 
1885 /**
1886  * This inverse of return_new, this releases this object from the global
1887  * TransformState table.
1888  *
1889  * You must already be holding _states_lock before you call this method.
1890  */
1891 void TransformState::
1892 release_new() {
1893  nassertv(_states_lock->debug_is_locked());
1894 
1895  if (_saved_entry != -1) {
1896  _saved_entry = -1;
1897  nassertv_always(_states->remove(this));
1898  }
1899 }
1900 
1901 /**
1902  * Remove all pointers within the cache from and to this particular
1903  * TransformState. The pointers to this object may be scattered around in the
1904  * various CompositionCaches from other TransformState objects.
1905  *
1906  * You must already be holding _states_lock before you call this method.
1907  */
1908 void TransformState::
1909 remove_cache_pointers() {
1910  nassertv(_states_lock->debug_is_locked());
1911 
1912  // Fortunately, since we added CompositionCache records in pairs, we know
1913  // exactly the set of TransformState objects that have us in their cache:
1914  // it's the same set of TransformState objects that we have in our own
1915  // cache.
1916 
1917 /*
1918  * We do need to put considerable thought into this loop, because as we clear
1919  * out cache entries we'll cause other TransformState objects to destruct,
1920  * which could cause things to get pulled out of our own _composition_cache
1921  * map. We want to allow this (so that we don't encounter any just-destructed
1922  * pointers in our cache), but we don't want to get bitten by this cascading
1923  * effect. Instead of walking through the map from beginning to end,
1924  * therefore, we just pull out the first one each time, and erase it.
1925  */
1926 
1927 #ifdef DO_PSTATS
1928  if (_composition_cache.is_empty() && _invert_composition_cache.is_empty()) {
1929  return;
1930  }
1931  PStatTimer timer(_cache_update_pcollector);
1932 #endif // DO_PSTATS
1933 
1934  // There are lots of ways to do this loop wrong. Be very careful if you
1935  // need to modify it for any reason.
1936  size_t i = 0;
1937  while (!_composition_cache.is_empty()) {
1938  // It is possible that the "other" TransformState object is currently
1939  // within its own destructor. We therefore can't use a PT() to hold its
1940  // pointer; that could end up calling its destructor twice. Fortunately,
1941  // we don't need to hold its reference count to ensure it doesn't destruct
1942  // while we process this loop; as long as we ensure that no *other*
1943  // TransformState objects destruct, there will be no reason for that one
1944  // to.
1945  TransformState *other = (TransformState *)_composition_cache.get_key(i);
1946 
1947  // We hold a copy of the composition result so we can dereference it
1948  // later.
1949  Composition comp = _composition_cache.get_data(i);
1950 
1951  // Now we can remove the element from our cache. We do this now, rather
1952  // than later, before any other TransformState objects have had a chance
1953  // to destruct, so we are confident that our iterator is still valid.
1954  _composition_cache.remove_element(i);
1955  _cache_stats.add_total_size(-1);
1956  _cache_stats.inc_dels();
1957 
1958  if (other != this) {
1959  int oi = other->_composition_cache.find(this);
1960 
1961  // We may or may not still be listed in the other's cache (it might be
1962  // halfway through pulling entries out, from within its own destructor).
1963  if (oi != -1) {
1964  // Hold a copy of the other composition result, too.
1965  Composition ocomp = other->_composition_cache.get_data(oi);
1966 
1967  other->_composition_cache.remove_element(oi);
1968  _cache_stats.add_total_size(-1);
1969  _cache_stats.inc_dels();
1970 
1971  // It's finally safe to let our held pointers go away. This may have
1972  // cascading effects as other TransformState objects are destructed,
1973  // but there will be no harm done if they destruct now.
1974  if (ocomp._result != nullptr && ocomp._result != other) {
1975  cache_unref_delete(ocomp._result);
1976  }
1977  }
1978  }
1979 
1980  // It's finally safe to let our held pointers go away. (See comment
1981  // above.)
1982  if (comp._result != nullptr && comp._result != this) {
1983  cache_unref_delete(comp._result);
1984  }
1985  }
1986 
1987  // A similar bit of code for the invert cache.
1988  i = 0;
1989  while (!_invert_composition_cache.is_empty()) {
1990  TransformState *other = (TransformState *)_invert_composition_cache.get_key(i);
1991  nassertv(other != this);
1992  Composition comp = _invert_composition_cache.get_data(i);
1993  _invert_composition_cache.remove_element(i);
1994  _cache_stats.add_total_size(-1);
1995  _cache_stats.inc_dels();
1996  if (other != this) {
1997  int oi = other->_invert_composition_cache.find(this);
1998  if (oi != -1) {
1999  Composition ocomp = other->_invert_composition_cache.get_data(oi);
2000  other->_invert_composition_cache.remove_element(oi);
2001  _cache_stats.add_total_size(-1);
2002  _cache_stats.inc_dels();
2003  if (ocomp._result != nullptr && ocomp._result != other) {
2004  cache_unref_delete(ocomp._result);
2005  }
2006  }
2007  }
2008  if (comp._result != nullptr && comp._result != this) {
2009  cache_unref_delete(comp._result);
2010  }
2011  }
2012 }
2013 
2014 /**
2015  * Computes a suitable hash value for phash_map.
2016  */
2017 void TransformState::
2018 do_calc_hash() {
2019  PStatTimer timer(_transform_hash_pcollector);
2020  _hash = 0;
2021 
2022  static const int significant_flags =
2023  (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_is_2d);
2024 
2025  int flags = (_flags & significant_flags);
2026  _hash = int_hash::add_hash(_hash, flags);
2027 
2028  if ((_flags & (F_is_invalid | F_is_identity)) == 0) {
2029  // Only bother to put the rest of the stuff in the hash if the transform
2030  // is not invalid or empty.
2031 
2032  if ((_flags & F_components_given) != 0) {
2033  // If the transform was specified componentwise, hash it componentwise.
2034  _hash = _pos.add_hash(_hash);
2035  if ((_flags & F_hpr_given) != 0) {
2036  _hash = _hpr.add_hash(_hash);
2037 
2038  } else if ((_flags & F_quat_given) != 0) {
2039  _hash = _quat.add_hash(_hash);
2040  }
2041 
2042  _hash = _scale.add_hash(_hash);
2043  _hash = _shear.add_hash(_hash);
2044 
2045  } else {
2046  // Otherwise, hash the matrix . . .
2047  if (_uniquify_matrix) {
2048  // . . . but only if the user thinks that's worthwhile.
2049  if ((_flags & F_mat_known) == 0) {
2050  // Calculate the matrix without doubly-locking.
2051  do_calc_mat();
2052  }
2053  _hash = _mat.add_hash(_hash);
2054 
2055  } else {
2056  // Otherwise, hash the pointer only--any two different matrix-based
2057  // TransformStates are considered to be different, even if their
2058  // matrices have the same values.
2059 
2060  _hash = pointer_hash::add_hash(_hash, this);
2061  }
2062  }
2063  }
2064 
2065  _flags |= F_hash_known;
2066 }
2067 
2068 /**
2069  * Determines whether the transform is singular (i.e. it scales to zero, and
2070  * has no inverse).
2071  */
2072 void TransformState::
2073 calc_singular() {
2074  LightMutexHolder holder(_lock);
2075  if ((_flags & F_singular_known) != 0) {
2076  // Someone else computed it first.
2077  return;
2078  }
2079 
2080  PStatTimer timer(_transform_calc_pcollector);
2081 
2082  nassertv((_flags & F_is_invalid) == 0);
2083 
2084  // We determine if a matrix is singular by attempting to invert it (and we
2085  // save the result of this invert operation for a subsequent
2086  // do_invert_compose() call, which is almost certain to be made if someone
2087  // is asking whether we're singular).
2088 
2089  // This should be NULL if no one has called calc_singular() yet.
2090  nassertv(_inv_mat == nullptr);
2091  _inv_mat = new LMatrix4;
2092 
2093  if ((_flags & F_mat_known) == 0) {
2094  do_calc_mat();
2095  }
2096  bool inverted = _inv_mat->invert_from(_mat);
2097 
2098  if (!inverted) {
2099  _flags |= F_is_singular;
2100  delete _inv_mat;
2101  _inv_mat = nullptr;
2102  }
2103  _flags |= F_singular_known;
2104 }
2105 
2106 /**
2107  * This is the implementation of calc_components(); it assumes the lock is
2108  * already held.
2109  */
2110 void TransformState::
2111 do_calc_components() {
2112  if ((_flags & F_components_known) != 0) {
2113  // Someone else computed it first.
2114  return;
2115  }
2116 
2117  PStatTimer timer(_transform_calc_pcollector);
2118 
2119  nassertv((_flags & F_is_invalid) == 0);
2120  if ((_flags & F_is_identity) != 0) {
2121  _scale.set(1.0f, 1.0f, 1.0f);
2122  _shear.set(0.0f, 0.0f, 0.0f);
2123  _hpr.set(0.0f, 0.0f, 0.0f);
2124  _quat = LQuaternion::ident_quat();
2125  _pos.set(0.0f, 0.0f, 0.0f);
2126  _flags |= F_has_components | F_components_known | F_hpr_known | F_quat_known | F_uniform_scale | F_identity_scale;
2127 
2128  } else {
2129  // If we don't have components and we're not identity, the only other
2130  // explanation is that we were constructed via a matrix.
2131  nassertv((_flags & F_mat_known) != 0);
2132 
2133  if ((_flags & F_mat_known) == 0) {
2134  do_calc_mat();
2135  }
2136  bool possible = decompose_matrix(_mat, _scale, _shear, _hpr, _pos);
2137  if (!possible) {
2138  // Some matrices can't be decomposed into scale, hpr, pos. In this
2139  // case, we now know that we cannot compute the components; but the
2140  // closest approximations are stored, at least.
2141  _flags |= F_components_known | F_hpr_known;
2142 
2143  } else {
2144  // Otherwise, we do have the components, or at least the hpr.
2145  _flags |= F_has_components | F_components_known | F_hpr_known;
2146  check_uniform_scale();
2147  }
2148 
2149  // However, we can always get at least the pos.
2150  _mat.get_row3(_pos, 3);
2151  }
2152 }
2153 
2154 /**
2155  * This is the implementation of calc_hpr(); it assumes the lock is already
2156  * held.
2157  */
2158 void TransformState::
2159 do_calc_hpr() {
2160  if ((_flags & F_hpr_known) != 0) {
2161  // Someone else computed it first.
2162  return;
2163  }
2164 
2165  PStatTimer timer(_transform_calc_pcollector);
2166 
2167  nassertv((_flags & F_is_invalid) == 0);
2168  if ((_flags & F_components_known) == 0) {
2169  do_calc_components();
2170  }
2171  if ((_flags & F_hpr_known) == 0) {
2172  // If we don't know the hpr yet, we must have been given a quat.
2173  // Decompose it.
2174  nassertv((_flags & F_quat_known) != 0);
2175  _hpr = _quat.get_hpr();
2176  _flags |= F_hpr_known;
2177  }
2178 }
2179 
2180 /**
2181  * Derives the quat from the hpr.
2182  */
2183 void TransformState::
2184 calc_quat() {
2185  LightMutexHolder holder(_lock);
2186  if ((_flags & F_quat_known) != 0) {
2187  // Someone else computed it first.
2188  return;
2189  }
2190 
2191  PStatTimer timer(_transform_calc_pcollector);
2192 
2193  nassertv((_flags & F_is_invalid) == 0);
2194  if ((_flags & F_components_known) == 0) {
2195  do_calc_components();
2196  }
2197  if ((_flags & F_quat_known) == 0) {
2198  // If we don't know the quat yet, we must have been given a hpr.
2199  // Decompose it.
2200  nassertv((_flags & F_hpr_known) != 0);
2201  _quat.set_hpr(_hpr);
2202  _flags |= F_quat_known;
2203  }
2204 }
2205 
2206 /**
2207  * Derives the normalized quat from the quat.
2208  */
2209 void TransformState::
2210 calc_norm_quat() {
2211  PStatTimer timer(_transform_calc_pcollector);
2212 
2213  LQuaternion quat = get_quat();
2214  LightMutexHolder holder(_lock);
2215  _norm_quat = quat;
2216  _norm_quat.normalize();
2217  _flags |= F_norm_quat_known;
2218 }
2219 
2220 /**
2221  * This is the implementation of calc_mat(); it assumes the lock is already
2222  * held.
2223  */
2224 void TransformState::
2225 do_calc_mat() {
2226  if ((_flags & F_mat_known) != 0) {
2227  // Someone else computed it first.
2228  return;
2229  }
2230 
2231  PStatTimer timer(_transform_calc_pcollector);
2232 
2233  nassertv((_flags & F_is_invalid) == 0);
2234  if ((_flags & F_is_identity) != 0) {
2235  _mat = LMatrix4::ident_mat();
2236 
2237  } else {
2238  // If we don't have a matrix and we're not identity, the only other
2239  // explanation is that we were constructed via components.
2240  nassertv((_flags & F_components_known) != 0);
2241  if ((_flags & F_hpr_known) == 0) {
2242  do_calc_hpr();
2243  }
2244 
2245  compose_matrix(_mat, _scale, _shear, get_hpr(), _pos);
2246  }
2247  _flags |= F_mat_known;
2248 }
2249 
2250 /**
2251  * Moves the TransformState object from one PStats category to another, so
2252  * that we can track in PStats how many pointers are held by nodes, and how
2253  * many are held in the cache only.
2254  */
2255 void TransformState::
2256 update_pstats(int old_referenced_bits, int new_referenced_bits) {
2257 #ifdef DO_PSTATS
2258  if ((old_referenced_bits & R_node) != 0) {
2259  _node_counter.sub_level(1);
2260  } else if ((old_referenced_bits & R_cache) != 0) {
2261  _cache_counter.sub_level(1);
2262  }
2263  if ((new_referenced_bits & R_node) != 0) {
2264  _node_counter.add_level(1);
2265  } else if ((new_referenced_bits & R_cache) != 0) {
2266  _cache_counter.add_level(1);
2267  }
2268 #endif // DO_PSTATS
2269 }
2270 
2271 /**
2272  * Tells the BamReader how to create objects of type TransformState.
2273  */
2274 void TransformState::
2275 register_with_read_factory() {
2276  BamReader::get_factory()->register_factory(get_class_type(), make_from_bam);
2277 }
2278 
2279 /**
2280  * Writes the contents of this object to the datagram for shipping out to a
2281  * Bam file.
2282  */
2283 void TransformState::
2284 write_datagram(BamWriter *manager, Datagram &dg) {
2285  TypedWritable::write_datagram(manager, dg);
2286 
2287  if ((_flags & F_is_identity) != 0) {
2288  // Identity, nothing much to that.
2289  int flags = F_is_identity | F_singular_known | F_is_2d;
2290  dg.add_uint32(flags);
2291 
2292  } else if ((_flags & F_is_invalid) != 0) {
2293  // Invalid, nothing much to that either.
2294  int flags = F_is_invalid | F_singular_known | F_is_singular | F_components_known | F_mat_known;
2295  dg.add_uint32(flags);
2296 
2297  } else if ((_flags & F_components_given) != 0) {
2298  // A component-based transform.
2299  int flags = F_components_given | F_components_known | F_has_components;
2300  flags |= (_flags & F_is_2d);
2301  if ((_flags & F_quat_given) != 0) {
2302  flags |= (F_quat_given | F_quat_known);
2303  } else if ((_flags & F_hpr_given) != 0) {
2304  flags |= (F_hpr_given | F_hpr_known);
2305  }
2306 
2307  dg.add_uint32(flags);
2308 
2309  _pos.write_datagram(dg);
2310  if ((_flags & F_quat_given) != 0) {
2311  _quat.write_datagram(dg);
2312  } else {
2313  get_hpr().write_datagram(dg);
2314  }
2315  _scale.write_datagram(dg);
2316  _shear.write_datagram(dg);
2317 
2318  } else {
2319  // A general matrix.
2320  nassertv((_flags & F_mat_known) != 0);
2321  int flags = F_mat_known;
2322  flags |= (_flags & F_is_2d);
2323  dg.add_uint32(flags);
2324  _mat.write_datagram(dg);
2325  }
2326 }
2327 
2328 /**
2329  * Called immediately after complete_pointers(), this gives the object a
2330  * chance to adjust its own pointer if desired. Most objects don't change
2331  * pointers after completion, but some need to.
2332  *
2333  * Once this function has been called, the old pointer will no longer be
2334  * accessed.
2335  */
2336 PT(TypedWritableReferenceCount) TransformState::
2337 change_this(TypedWritableReferenceCount *old_ptr, BamReader *manager) {
2338  // First, uniquify the pointer.
2339  TransformState *state = DCAST(TransformState, old_ptr);
2340  CPT(TransformState) pointer = return_unique(state);
2341 
2342  // We have to cast the pointer back to non-const, because the bam reader
2343  // expects that.
2344  return (TransformState *)pointer.p();
2345 }
2346 
2347 /**
2348  * This function is called by the BamReader's factory when a new object of
2349  * type TransformState is encountered in the Bam file. It should create the
2350  * TransformState and extract its information from the file.
2351  */
2352 TypedWritable *TransformState::
2353 make_from_bam(const FactoryParams &params) {
2354  TransformState *state = new TransformState;
2355  DatagramIterator scan;
2356  BamReader *manager;
2357 
2358  parse_params(params, scan, manager);
2359  state->fillin(scan, manager);
2360  manager->register_change_this(change_this, state);
2361 
2362  return state;
2363 }
2364 
2365 /**
2366  * This internal function is called by make_from_bam to read in all of the
2367  * relevant data from the BamFile for the new TransformState.
2368  */
2369 void TransformState::
2370 fillin(DatagramIterator &scan, BamReader *manager) {
2371  TypedWritable::fillin(scan, manager);
2372  _flags = scan.get_uint32();
2373 
2374  if ((_flags & F_components_given) != 0) {
2375  // Componentwise transform.
2376  _pos.read_datagram(scan);
2377  if ((_flags & F_quat_given) != 0) {
2378  _quat.read_datagram(scan);
2379  } else {
2380  _hpr.read_datagram(scan);
2381  }
2382  _scale.read_datagram(scan);
2383  _shear.read_datagram(scan);
2384 
2385  check_uniform_scale();
2386  }
2387 
2388  if ((_flags & F_mat_known) != 0) {
2389  // General matrix.
2390  _mat.read_datagram(scan);
2391  }
2392 }
TransformState::is_identity
bool is_identity() const
Returns true if the transform represents the identity matrix, false otherwise.
Definition: transformState.I:197
LightMutexHolder
Similar to MutexHolder, but for a light mutex.
Definition: lightMutexHolder.h:25
indent
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition: indent.cxx:20
ConfigVariableBool
This is a convenience class to specialize ConfigVariable as a boolean type.
Definition: configVariableBool.h:23
UpdateSeq
This is a sequence number that increments monotonically.
Definition: updateSeq.h:37
Thread::get_main_thread
get_main_thread
Returns a pointer to the "main" Thread object–this is the Thread that started the whole process.
Definition: thread.h:107
TransformState::get_quat
get_quat
Returns the rotation component of the transform as a quaternion.
Definition: transformState.h:152
pvector
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:42
ReferenceCount::unref_if_one
bool unref_if_one() const
Atomically decreases the reference count of this object if it is one.
Definition: referenceCount.I:327
TransformState::~TransformState
virtual ~TransformState()
The destructor is responsible for removing the TransformState from the global set if it is there.
Definition: transformState.cxx:78
SimpleHashMap::get_data
const Value & get_data(size_t n) const
Returns the data in the nth entry of the table.
Definition: simpleHashMap.I:387
DatagramIterator
A class to retrieve the individual data elements previously stored in a Datagram.
Definition: datagramIterator.h:27
LightReMutexHolder
Similar to MutexHolder, but for a light reentrant mutex.
Definition: lightReMutexHolder.h:25
pmap
This is our own Panda specialization on the default STL map.
Definition: pmap.h:49
TransformState::is_2d
bool is_2d() const
Returns true if the transform has been constructed entirely using the 2-d transform operations,...
Definition: transformState.I:227
CPT
CPT(TransformState) TransformState
Constructs an identity transform.
Definition: transformState.cxx:240
BamReader
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:110
pStatTimer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
compareTo.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SimpleHashMap::remove
bool remove(const Key &key)
Removes the indicated key and its associated data from the table.
Definition: simpleHashMap.I:254
BamWriter
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition: bamWriter.h:63
SimpleHashMap::get_key
const Key & get_key(size_t n) const
Returns the key in the nth entry of the table.
Definition: simpleHashMap.I:375
CacheStats::inc_hits
void inc_hits()
Increments by 1 the count of cache hits.
Definition: cacheStats.I:35
BamReader::register_change_this
void register_change_this(ChangeThisFunc func, TypedWritable *whom)
Called by an object reading itself from the bam file to indicate that the object pointer that will be...
Definition: bamReader.cxx:835
CacheStats::init
void init()
Initializes the CacheStats for the first time.
Definition: cacheStats.cxx:22
CacheStats::add_num_states
void add_num_states(int count)
Adds the indicated count (positive or negative) to the total count of individual RenderState or Trans...
Definition: cacheStats.I:91
TransformState::get_mat
get_mat
Returns the matrix that describes the transform.
Definition: transformState.h:156
BamReader::get_factory
static WritableFactory * get_factory()
Returns the global WritableFactory for generating TypedWritable objects.
Definition: bamReader.I:177
pointer_hash::add_hash
static size_t add_hash(size_t start, const void *key)
Adds the indicated key into a running hash.
Definition: stl_compares.I:110
TransformState::get_shear
get_shear
Returns the shear component of the transform.
Definition: transformState.h:155
TransformState::has_nonzero_shear
bool has_nonzero_shear() const
Returns true if the shear component is non-zero, false if it is zero or if the matrix cannot be decom...
Definition: transformState.I:358
bamReader.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SimpleHashMap::validate
bool validate() const
Returns true if the internal table appears to be consistent, false if there are some internal errors.
Definition: simpleHashMap.I:504
TypedWritable
Base class for objects that can be written to and read from Bam files.
Definition: typedWritable.h:35
Datagram
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
Definition: datagram.h:38
SimpleHashMap
This template class implements an unordered map of keys to data, implemented as a hashtable.
Definition: simpleHashMap.h:81
TransformState::get_mat3
LMatrix3 get_mat3() const
Returns the 3x3 matrix that describes the 2-d transform.
Definition: transformState.I:526
compose_matrix.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
Thread::get_current_thread
get_current_thread
Returns a pointer to the currently-executing Thread object.
Definition: thread.h:109
PStatTimer
A lightweight class that can be used to automatically start and stop a PStatCollector around a sectio...
Definition: pStatTimer.h:30
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
CacheStats::add_total_size
void add_total_size(int count)
Adds the indicated count (positive or negative) to the total number of entries for the cache (net occ...
Definition: cacheStats.I:80
MemoryUsage::update_type
static void update_type(ReferenceCount *ptr, TypeHandle type)
Associates the indicated type with the given pointer.
Definition: memoryUsage.I:55
CacheStats::inc_adds
void inc_adds(bool is_new)
Increments by 1 the count of elements added to the cache.
Definition: cacheStats.I:56
SimpleHashMap::find
int find(const Key &key) const
Searches for the indicated key in the table.
Definition: simpleHashMap.I:156
FactoryParams
An instance of this class is passed to the Factory when requesting it to do its business and construc...
Definition: factoryParams.h:36
TransformState::get_scale2d
LVecBase2 get_scale2d() const
Returns the scale component of the 2-d transform.
Definition: transformState.I:504
TransformState::get_scale
get_scale
Returns the scale component of the transform.
Definition: transformState.h:154
transformState.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
TransformState::get_pos2d
LVecBase2 get_pos2d() const
Returns the pos component of the 2-d transform.
Definition: transformState.I:471
TransformState::quat_given
bool quat_given() const
Returns true if the rotation was specified via a quaternion, false otherwise.
Definition: transformState.I:280
lightMutexHolder.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
cache_unref_delete
void cache_unref_delete(RefCountType *ptr)
This global helper function will unref the given ReferenceCount object, and if the reference count re...
Definition: cachedTypedWritableReferenceCount.I:204
LightReMutexDirect::debug_is_locked
bool debug_is_locked() const
Returns true if the current thread has locked the LightReMutex, false otherwise.
Definition: lightReMutexDirect.I:123
TypedWritable::write_datagram
virtual void write_datagram(BamWriter *manager, Datagram &dg)
Writes the contents of this object to the datagram for shipping out to a Bam file.
Definition: typedWritable.cxx:54
TransformState
Indicates a coordinate-system transform on vertices.
Definition: transformState.h:54
CacheStats
This is used to track the utilization of the TransformState and RenderState caches,...
Definition: cacheStats.h:25
PStatCollector
A lightweight class that represents a single element that may be timed and/or counted via stats.
Definition: pStatCollector.h:43
TransformState::operator==
bool operator==(const TransformState &other) const
Tests equivalence between two transform states.
Definition: transformState.cxx:186
TransformState::get_uniform_scale
PN_stdfloat get_uniform_scale() const
Returns the scale component of the transform, as a single number.
Definition: transformState.I:439
TransformState::components_given
bool components_given() const
Returns true if the transform was specified componentwise, or false if it was specified with a genera...
Definition: transformState.I:260
SimpleHashMap::store
int store(const Key &key, const Value &data)
Records the indicated key/data pair in the map.
Definition: simpleHashMap.I:177
TransformState::unref
virtual bool unref() const
Explicitly decrements the reference count.
TransformState::is_invalid
bool is_invalid() const
Returns true if the transform represents an invalid matrix, for instance the result of inverting a si...
Definition: transformState.I:207
SimpleHashMap::modify_data
Value & modify_data(size_t n)
Returns a modifiable reference to the data in the nth entry of the table.
Definition: simpleHashMap.I:399
TransformState::get_norm_quat
get_norm_quat
Returns the rotation component of the transform as a quaternion.
Definition: transformState.h:153
TransformState::has_uniform_scale
bool has_uniform_scale() const
Returns true if the scale is uniform across all three axes (and therefore can be expressed as a singl...
Definition: transformState.I:339
Factory::register_factory
void register_factory(TypeHandle handle, CreateFunc *func, void *user_data=nullptr)
Registers a new kind of thing the Factory will be able to create.
Definition: factory.I:73
TransformState::get_hpr
get_hpr
Returns the rotation component of the transform as a trio of Euler angles.
Definition: transformState.h:151
TransformState::compare_to
int compare_to(const TransformState &other) const
Provides an arbitrary ordering among all unique TransformStates, so we can store the essentially diff...
Definition: transformState.I:30
SimpleHashMap::is_empty
bool is_empty() const
Returns true if the table is empty; i.e.
Definition: simpleHashMap.I:454
integer_hash::add_hash
static size_t add_hash(size_t start, const Key &key)
Adds the indicated key into a running hash.
Definition: stl_compares.I:101
TransformState::has_components
bool has_components() const
Returns true if the transform can be described by separate pos, hpr, and scale components.
Definition: transformState.I:246
CacheStats::inc_misses
void inc_misses()
Increments by 1 the count of cache misses.
Definition: cacheStats.I:45
Datagram::add_uint32
void add_uint32(uint32_t value)
Adds an unsigned 32-bit integer to the datagram.
Definition: datagram.I:94
TransformState::write_datagram
virtual void write_datagram(BamWriter *manager, Datagram &dg)
Writes the contents of this object to the datagram for shipping out to a Bam file.
ReferenceCount::unref
virtual bool unref() const
Explicitly decrements the reference count.
Definition: referenceCount.I:179
TransformState::get_pos
get_pos
Returns the pos component of the transform.
Definition: transformState.h:150
TypedWritableReferenceCount
A base class for things which need to inherit from both TypedWritable and from ReferenceCount.
Definition: typedWritableReferenceCount.h:31
SimpleHashMap::clear
void clear()
Completely empties the table.
Definition: simpleHashMap.I:331
datagramIterator.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
indent.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
DatagramIterator::get_uint32
uint32_t get_uint32()
Extracts an unsigned 32-bit integer.
Definition: datagramIterator.I:164
TransformState::get_shear2d
PN_stdfloat get_shear2d() const
Returns the shear component of the 2-d transform.
Definition: transformState.I:515
TypedWritable::fillin
virtual void fillin(DatagramIterator &scan, BamReader *manager)
This internal function is intended to be called by each class's make_from_bam() method to read in all...
Definition: typedWritable.cxx:103
CachedTypedWritableReferenceCount::get_cache_ref_count
get_cache_ref_count
Returns the current reference count.
Definition: cachedTypedWritableReferenceCount.h:47
CacheStats::inc_dels
void inc_dels()
Increments by 1 the count of elements removed from the cache.
Definition: cacheStats.I:69
bamWriter.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
LightReMutex
A lightweight reentrant mutex.
Definition: lightReMutex.h:32
config_pgraph.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
thread.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
TransformState::get_rotate2d
PN_stdfloat get_rotate2d() const
Returns the rotation component of the 2-d transform as an angle in degrees clockwise about the origin...
Definition: transformState.I:483
ReferenceCount::get_ref_count
get_ref_count
Returns the current reference count.
Definition: referenceCount.h:53
parse_params
void parse_params(const FactoryParams &params, DatagramIterator &scan, BamReader *&manager)
Takes in a FactoryParams, passed from a WritableFactory into any TypedWritable's make function,...
Definition: bamReader.I:275
SimpleHashMap::get_num_entries
size_t get_num_entries() const
Returns the number of active entries in the table.
Definition: simpleHashMap.I:445
SimpleHashMap::consider_shrink_table
bool consider_shrink_table()
Shrinks the table if the allocated storage is significantly larger than the number of elements in it.
Definition: simpleHashMap.I:693
CacheStats::maybe_report
void maybe_report(const char *name)
Outputs a report if enough time has elapsed.
Definition: cacheStats.I:18
TransformState::is_singular
bool is_singular() const
Returns true if the transform represents a singular transform (that is, it has a zero scale,...
Definition: transformState.I:216
SimpleHashMap::remove_element
void remove_element(size_t n)
Removes the nth entry from the table.
Definition: simpleHashMap.I:435
lightReMutexHolder.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pset
This is our own Panda specialization on the default STL set.
Definition: pset.h:49