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  */
185 bool TransformState::
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->get_ref_count() == 1) {
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.
1213  state->release_new();
1214  state->remove_cache_pointers();
1215  state->cache_unref();
1216  delete state;
1217 
1218  // When we removed it from the hash map, it swapped the last element
1219  // with the one we just removed. So the current index contains one we
1220  // still need to visit.
1221  --size;
1222  --si;
1223  if (stop_at_element > 0) {
1224  --stop_at_element;
1225  }
1226  }
1227 
1228  si = (si + 1) % size;
1229  } while (si != stop_at_element);
1230  _garbage_index = si;
1231 
1232  nassertr(_states->get_num_entries() == size, 0);
1233 
1234 #ifdef _DEBUG
1235  nassertr(_states->validate(), 0);
1236 #endif
1237 
1238  // If we just cleaned up a lot of states, see if we can reduce the table in
1239  // size. This will help reduce iteration overhead in the future.
1240  _states->consider_shrink_table();
1241 
1242  return (int)orig_size - (int)size;
1243 }
1244 
1245 /**
1246  * Detects all of the reference-count cycles in the cache and reports them to
1247  * standard output.
1248  *
1249  * These cycles may be inadvertently created when state compositions cycle
1250  * back to a starting point. Nowadays, these cycles should be automatically
1251  * detected and broken, so this method should never list any cycles unless
1252  * there is a bug in that detection logic.
1253  *
1254  * The cycles listed here are not leaks in the strictest sense of the word,
1255  * since they can be reclaimed by a call to clear_cache(); but they will not
1256  * be reclaimed automatically.
1257  */
1258 void TransformState::
1259 list_cycles(ostream &out) {
1260  if (_states == nullptr) {
1261  return;
1262  }
1263  LightReMutexHolder holder(*_states_lock);
1264 
1265  typedef pset<const TransformState *> VisitedStates;
1266  VisitedStates visited;
1267  CompositionCycleDesc cycle_desc;
1268 
1269  size_t size = _states->get_num_entries();
1270  for (size_t si = 0; si < size; ++si) {
1271  const TransformState *state = _states->get_key(si);
1272 
1273  bool inserted = visited.insert(state).second;
1274  if (inserted) {
1275  ++_last_cycle_detect;
1276  if (r_detect_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
1277  // This state begins a cycle.
1278  CompositionCycleDesc::reverse_iterator csi;
1279 
1280  out << "\nCycle detected of length " << cycle_desc.size() + 1 << ":\n"
1281  << "state " << (void *)state << ":" << state->get_ref_count()
1282  << " =\n";
1283  state->write(out, 2);
1284  for (csi = cycle_desc.rbegin(); csi != cycle_desc.rend(); ++csi) {
1285  const CompositionCycleDescEntry &entry = (*csi);
1286  if (entry._inverted) {
1287  out << "invert composed with ";
1288  } else {
1289  out << "composed with ";
1290  }
1291  out << (const void *)entry._obj << ":" << entry._obj->get_ref_count()
1292  << " " << *entry._obj << "\n"
1293  << "produces " << (const void *)entry._result << ":"
1294  << entry._result->get_ref_count() << " =\n";
1295  entry._result->write(out, 2);
1296  visited.insert(entry._result);
1297  }
1298 
1299  cycle_desc.clear();
1300  } else {
1301  ++_last_cycle_detect;
1302  if (r_detect_reverse_cycles(state, state, 1, _last_cycle_detect, &cycle_desc)) {
1303  // This state begins a cycle.
1304  CompositionCycleDesc::iterator csi;
1305 
1306  out << "\nReverse cycle detected of length " << cycle_desc.size() + 1 << ":\n"
1307  << "state ";
1308  for (csi = cycle_desc.begin(); csi != cycle_desc.end(); ++csi) {
1309  const CompositionCycleDescEntry &entry = (*csi);
1310  out << (const void *)entry._result << ":"
1311  << entry._result->get_ref_count() << " =\n";
1312  entry._result->write(out, 2);
1313  out << (const void *)entry._obj << ":"
1314  << entry._obj->get_ref_count() << " =\n";
1315  entry._obj->write(out, 2);
1316  visited.insert(entry._result);
1317  }
1318  out << (void *)state << ":"
1319  << state->get_ref_count() << " =\n";
1320  state->write(out, 2);
1321 
1322  cycle_desc.clear();
1323  }
1324  }
1325  }
1326  }
1327 }
1328 
1329 
1330 /**
1331  * Lists all of the TransformStates in the cache to the output stream, one per
1332  * line. This can be quite a lot of output if the cache is large, so be
1333  * prepared.
1334  */
1335 void TransformState::
1336 list_states(ostream &out) {
1337  if (_states == nullptr) {
1338  out << "0 states:\n";
1339  return;
1340  }
1341  LightReMutexHolder holder(*_states_lock);
1342 
1343  size_t size = _states->get_num_entries();
1344  out << size << " states:\n";
1345  for (size_t si = 0; si < size; ++si) {
1346  const TransformState *state = _states->get_key(si);
1347  state->write(out, 2);
1348  }
1349 }
1350 
1351 /**
1352  * Ensures that the cache is still stored in sorted order, and that none of
1353  * the cache elements have been inadvertently deleted. Returns true if so,
1354  * false if there is a problem (which implies someone has modified one of the
1355  * supposedly-const TransformState objects).
1356  */
1357 bool TransformState::
1358 validate_states() {
1359  if (_states == nullptr) {
1360  return true;
1361  }
1362 
1363  PStatTimer timer(_transform_validate_pcollector);
1364 
1365  LightReMutexHolder holder(*_states_lock);
1366  if (_states->is_empty()) {
1367  return true;
1368  }
1369 
1370  if (!_states->validate()) {
1371  pgraph_cat.error()
1372  << "TransformState::_states cache is invalid!\n";
1373  return false;
1374  }
1375 
1376  size_t size = _states->get_num_entries();
1377  size_t si = 0;
1378  nassertr(si < size, false);
1379  nassertr(_states->get_key(si)->get_ref_count() >= 0, false);
1380  size_t snext = si;
1381  ++snext;
1382  while (snext < size) {
1383  nassertr(_states->get_key(snext)->get_ref_count() >= 0, false);
1384  const TransformState *ssi = _states->get_key(si);
1385  if (!ssi->validate_composition_cache()) {
1386  return false;
1387  }
1388  const TransformState *ssnext = _states->get_key(snext);
1389  bool c = (*ssi) == (*ssnext);
1390  bool ci = (*ssnext) == (*ssi);
1391  if (c != ci) {
1392  pgraph_cat.error()
1393  << "TransformState::operator == () not defined properly!\n";
1394  pgraph_cat.error(false)
1395  << "(a, b): " << c << "\n";
1396  pgraph_cat.error(false)
1397  << "(b, a): " << ci << "\n";
1398  ssi->write(pgraph_cat.error(false), 2);
1399  ssnext->write(pgraph_cat.error(false), 2);
1400  return false;
1401  }
1402  si = snext;
1403  ++snext;
1404  }
1405 
1406  return true;
1407 }
1408 
1409 /**
1410  * Make sure the global _states map is allocated. This only has to be done
1411  * once. We could make this map static, but then we run into problems if
1412  * anyone creates a TransformState object at static init time; it also seems
1413  * to cause problems when the Panda shared library is unloaded at application
1414  * exit time.
1415  */
1416 void TransformState::
1417 init_states() {
1418  _states = new States;
1419 
1420  ConfigVariableBool uniquify_matrix
1421  ("uniquify-matrix", true,
1422  PRC_DESC("Set this true to look up arbitrary 4x4 transform matrices in "
1423  "the cache, to ensure that two differently-computed transforms "
1424  "that happen to encode the same matrix will be collapsed into "
1425  "a single pointer. Nowadays, with the transforms stored in a "
1426  "hashtable, we're generally better off with this set true."));
1427 
1428  // Store this at the beginning, so that we don't have to query this every
1429  // time that the comparison operator is invoked.
1430  _uniquify_matrix = uniquify_matrix;
1431 
1432  // TODO: we should have a global Panda mutex to allow us to safely create
1433  // _states_lock without a startup race condition. For the meantime, this is
1434  // OK because we guarantee that this method is called at static init time,
1435  // presumably when there is still only one thread in the world.
1436  _states_lock = new LightReMutex("TransformState::_states_lock");
1437  _cache_stats.init();
1439 }
1440 
1441 /**
1442  * This function is used to share a common TransformState pointer for all
1443  * equivalent TransformState objects.
1444  *
1445  * This is different from return_unique() in that it does not actually
1446  * guarantee a unique pointer, unless uniquify-transforms is set.
1447  */
1448 CPT(TransformState) TransformState::
1449 return_new(TransformState *state) {
1450  nassertr(state != nullptr, state);
1451  if (!uniquify_transforms && !state->is_identity()) {
1452  return state;
1453  }
1454 
1455  return return_unique(state);
1456 }
1457 
1458 /**
1459  * This function is used to share a common TransformState pointer for all
1460  * equivalent TransformState objects.
1461  *
1462  * See the similar logic in RenderState. The idea is to create a new
1463  * TransformState object and pass it through this function, which will share
1464  * the pointer with a previously-created TransformState object if it is
1465  * equivalent.
1466  */
1467 CPT(TransformState) TransformState::
1468 return_unique(TransformState *state) {
1469  nassertr(state != nullptr, state);
1470 
1471  if (!transform_cache) {
1472  return state;
1473  }
1474 
1475 #ifndef NDEBUG
1476  if (paranoid_const) {
1477  nassertr(validate_states(), state);
1478  }
1479 #endif
1480 
1481  PStatTimer timer(_transform_new_pcollector);
1482 
1483  LightReMutexHolder holder(*_states_lock);
1484 
1485  if (state->_saved_entry != -1) {
1486  // This state is already in the cache. nassertr(_states->find(state) ==
1487  // state->_saved_entry, state);
1488  return state;
1489  }
1490 
1491  // Save the state in a local PointerTo so that it will be freed at the end
1492  // of this function if no one else uses it.
1493  CPT(TransformState) pt_state = state;
1494 
1495  int si = _states->find(state);
1496  if (si != -1) {
1497  // There's an equivalent state already in the set. Return it.
1498  return _states->get_key(si);
1499  }
1500 
1501  // Not already in the set; add it.
1502  if (garbage_collect_states) {
1503  // If we'll be garbage collecting states explicitly, we'll increment the
1504  // reference count when we store it in the cache, so that it won't be
1505  // deleted while it's in it.
1506  state->cache_ref();
1507  }
1508  si = _states->store(state, nullptr);
1509 
1510  // Save the index and return the input state.
1511  state->_saved_entry = si;
1512  return pt_state;
1513 }
1514 
1515 /**
1516  * The private implemention of compose(); this actually composes two
1517  * TransformStates, without bothering with the cache.
1518  */
1519 CPT(TransformState) TransformState::
1520 do_compose(const TransformState *other) const {
1521  PStatTimer timer(_transform_compose_pcollector);
1522 
1523  nassertr((_flags & F_is_invalid) == 0, this);
1524  nassertr((other->_flags & F_is_invalid) == 0, other);
1525 
1526  if (compose_componentwise &&
1527  has_uniform_scale() &&
1528  !has_nonzero_shear() && !other->has_nonzero_shear() &&
1529  ((components_given() && other->has_components()) ||
1530  (other->components_given() && has_components()))) {
1531  // We will do this operation componentwise if *either* transform was given
1532  // componentwise (and there is no non-uniform scale in the way).
1533 
1534  CPT(TransformState) result;
1535  if (is_2d() && other->is_2d()) {
1536  // Do a 2-d compose.
1537  LVecBase2 pos = get_pos2d();
1538  PN_stdfloat rotate = get_rotate2d();
1539  LQuaternion quat = get_norm_quat();
1540  PN_stdfloat scale = get_uniform_scale();
1541 
1542  LPoint3 op = quat.xform(other->get_pos());
1543  pos += LVecBase2(op[0], op[1]) * scale;
1544 
1545  rotate += other->get_rotate2d();
1546  LVecBase2 new_scale = other->get_scale2d() * scale;
1547 
1548  result = make_pos_rotate_scale2d(pos, rotate, new_scale);
1549 
1550  } else {
1551  // A normal 3-d compose.
1552  LVecBase3 pos = get_pos();
1553  LQuaternion quat = get_norm_quat();
1554  PN_stdfloat scale = get_uniform_scale();
1555 
1556  pos += quat.xform(other->get_pos()) * scale;
1557  quat = other->get_norm_quat() * quat;
1558  LVecBase3 new_scale = other->get_scale() * scale;
1559 
1560  result = make_pos_quat_scale(pos, quat, new_scale);
1561  }
1562 
1563 #ifndef NDEBUG
1564  if (paranoid_compose) {
1565  // Now verify against the matrix.
1566  LMatrix4 new_mat;
1567  new_mat.multiply(other->get_mat(), get_mat());
1568  if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
1569  CPT(TransformState) correct = make_mat(new_mat);
1570  pgraph_cat.warning()
1571  << "Componentwise composition of " << *this << " and " << *other
1572  << " produced:\n"
1573  << *result << "\n instead of:\n" << *correct << "\n";
1574  result = correct;
1575  }
1576  }
1577 #endif // NDEBUG
1578 
1579  return result;
1580  }
1581 
1582  // Do the operation with matrices.
1583  if (is_2d() && other->is_2d()) {
1584  LMatrix3 new_mat = other->get_mat3() * get_mat3();
1585  return make_mat3(new_mat);
1586  } else {
1587  LMatrix4 new_mat;
1588  new_mat.multiply(other->get_mat(), get_mat());
1589  return make_mat(new_mat);
1590  }
1591 }
1592 
1593 /**
1594  * The private implemention of invert_compose().
1595  */
1596 CPT(TransformState) TransformState::
1597 do_invert_compose(const TransformState *other) const {
1598  PStatTimer timer(_transform_invert_pcollector);
1599 
1600  nassertr((_flags & F_is_invalid) == 0, this);
1601  nassertr((other->_flags & F_is_invalid) == 0, other);
1602 
1603  if (compose_componentwise &&
1604  has_uniform_scale() &&
1605  !has_nonzero_shear() && !other->has_nonzero_shear() &&
1606  ((components_given() && other->has_components()) ||
1607  (other->components_given() && has_components()))) {
1608  // We will do this operation componentwise if *either* transform was given
1609  // componentwise (and there is no non-uniform scale in the way).
1610 
1611  CPT(TransformState) result;
1612  if (is_2d() && other->is_2d()) {
1613  // Do a 2-d invert compose.
1614  LVecBase2 pos = get_pos2d();
1615  PN_stdfloat rotate = get_rotate2d();
1616  LQuaternion quat = get_norm_quat();
1617  PN_stdfloat scale = get_uniform_scale();
1618 
1619  // First, invert our own transform.
1620  if (scale == 0.0f) {
1621  ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
1622  return make_invalid();
1623  }
1624  scale = 1.0f / scale;
1625  quat.invert_in_place();
1626  rotate = -rotate;
1627  LVecBase3 mp = quat.xform(-LVecBase3(pos[0], pos[1], 0.0f));
1628  pos = LVecBase2(mp[0], mp[1]) * scale;
1629  LVecBase2 new_scale(scale, scale);
1630 
1631  // Now compose the inverted transform with the other transform.
1632  if (!other->is_identity()) {
1633  LPoint3 op = quat.xform(other->get_pos());
1634  pos += LVecBase2(op[0], op[1]) * scale;
1635 
1636  rotate += other->get_rotate2d();
1637  new_scale = other->get_scale2d() * scale;
1638  }
1639 
1640  result = make_pos_rotate_scale2d(pos, rotate, new_scale);
1641 
1642  } else {
1643  // Do a normal, 3-d invert compose.
1644  LVecBase3 pos = get_pos();
1645  LQuaternion quat = get_norm_quat();
1646  PN_stdfloat scale = get_uniform_scale();
1647 
1648  // First, invert our own transform.
1649  if (scale == 0.0f) {
1650  ((TransformState *)this)->_flags |= F_is_singular | F_singular_known;
1651  return make_invalid();
1652  }
1653  scale = 1.0f / scale;
1654  quat.invert_in_place();
1655  pos = quat.xform(-pos) * scale;
1656  LVecBase3 new_scale(scale, scale, scale);
1657 
1658  // Now compose the inverted transform with the other transform.
1659  if (!other->is_identity()) {
1660  pos += quat.xform(other->get_pos()) * scale;
1661  quat = other->get_norm_quat() * quat;
1662  new_scale = other->get_scale() * scale;
1663  }
1664 
1665  result = make_pos_quat_scale(pos, quat, new_scale);
1666  }
1667 
1668 #ifndef NDEBUG
1669  if (paranoid_compose) {
1670  // Now verify against the matrix.
1671  if (is_singular()) {
1672  pgraph_cat.warning()
1673  << "Unexpected singular matrix found for " << *this << "\n";
1674  } else {
1675  nassertr(_inv_mat != nullptr, make_invalid());
1676  LMatrix4 new_mat;
1677  new_mat.multiply(other->get_mat(), *_inv_mat);
1678  if (!new_mat.almost_equal(result->get_mat(), 0.1)) {
1679  CPT(TransformState) correct = make_mat(new_mat);
1680  pgraph_cat.warning()
1681  << "Componentwise invert-composition of " << *this << " and " << *other
1682  << " produced:\n"
1683  << *result << "\n instead of:\n" << *correct << "\n";
1684  result = correct;
1685  }
1686  }
1687  }
1688 #endif // NDEBUG
1689 
1690  return result;
1691  }
1692 
1693  if (is_singular()) {
1694  return make_invalid();
1695  }
1696 
1697  // Now that is_singular() has returned false, we can assume that _inv_mat
1698  // has been allocated and filled in.
1699  nassertr(_inv_mat != nullptr, make_invalid());
1700 
1701  if (is_2d() && other->is_2d()) {
1702  const LMatrix4 &i = *_inv_mat;
1703  LMatrix3 inv3(i(0, 0), i(0, 1), i(0, 3),
1704  i(1, 0), i(1, 1), i(1, 3),
1705  i(3, 0), i(3, 1), i(3, 3));
1706  if (other->is_identity()) {
1707  return make_mat3(inv3);
1708  } else {
1709  return make_mat3(other->get_mat3() * inv3);
1710  }
1711  } else {
1712  if (other->is_identity()) {
1713  return make_mat(*_inv_mat);
1714  } else {
1715  return make_mat(other->get_mat() * (*_inv_mat));
1716  }
1717  }
1718 }
1719 
1720 /**
1721  * Detects whether there is a cycle in the cache that begins with this state.
1722  * If any are detected, breaks them by removing this state from the cache.
1723  */
1724 void TransformState::
1725 detect_and_break_cycles() {
1726  PStatTimer timer(_transform_break_cycles_pcollector);
1727 
1728  ++_last_cycle_detect;
1729  if (r_detect_cycles(this, this, 1, _last_cycle_detect, nullptr)) {
1730  // Ok, we have a cycle. This will be a leak unless we break the cycle by
1731  // freeing the cache on this object.
1732  if (pgraph_cat.is_debug()) {
1733  pgraph_cat.debug()
1734  << "Breaking cycle involving " << (*this) << "\n";
1735  }
1736 
1737  remove_cache_pointers();
1738  } else {
1739  ++_last_cycle_detect;
1740  if (r_detect_reverse_cycles(this, this, 1, _last_cycle_detect, nullptr)) {
1741  if (pgraph_cat.is_debug()) {
1742  pgraph_cat.debug()
1743  << "Breaking cycle involving " << (*this) << "\n";
1744  }
1745 
1746  remove_cache_pointers();
1747  }
1748  }
1749 }
1750 
1751 /**
1752  * Detects whether there is a cycle in the cache that begins with the
1753  * indicated state. Returns true if at least one cycle is found, false if
1754  * this state is not part of any cycles. If a cycle is found and cycle_desc
1755  * is not NULL, then cycle_desc is filled in with the list of the steps of the
1756  * cycle, in reverse order.
1757  */
1758 bool TransformState::
1759 r_detect_cycles(const TransformState *start_state,
1760  const TransformState *current_state,
1761  int length, UpdateSeq this_seq,
1763  if (current_state->_cycle_detect == this_seq) {
1764  // We've already seen this state; therefore, we've found a cycle.
1765 
1766  // However, we only care about cycles that return to the starting state
1767  // and involve more than two steps. If only one or two nodes are
1768  // involved, it doesn't represent a memory leak, so no problem there.
1769  return (current_state == start_state && length > 2);
1770  }
1771  ((TransformState *)current_state)->_cycle_detect = this_seq;
1772 
1773  size_t i;
1774  size_t cache_size = current_state->_composition_cache.get_num_entries();
1775  for (i = 0; i < cache_size; ++i) {
1776  const TransformState *result = current_state->_composition_cache.get_data(i)._result;
1777  if (result != nullptr) {
1778  if (r_detect_cycles(start_state, result, length + 1,
1779  this_seq, cycle_desc)) {
1780  // Cycle detected.
1781  if (cycle_desc != nullptr) {
1782  const TransformState *other = current_state->_composition_cache.get_key(i);
1783  CompositionCycleDescEntry entry(other, result, false);
1784  cycle_desc->push_back(entry);
1785  }
1786  return true;
1787  }
1788  }
1789  }
1790 
1791  cache_size = current_state->_invert_composition_cache.get_num_entries();
1792  for (i = 0; i < cache_size; ++i) {
1793  const TransformState *result = current_state->_invert_composition_cache.get_data(i)._result;
1794  if (result != nullptr) {
1795  if (r_detect_cycles(start_state, result, length + 1,
1796  this_seq, cycle_desc)) {
1797  // Cycle detected.
1798  if (cycle_desc != nullptr) {
1799  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1800  CompositionCycleDescEntry entry(other, result, true);
1801  cycle_desc->push_back(entry);
1802  }
1803  return true;
1804  }
1805  }
1806  }
1807 
1808  // No cycle detected.
1809  return false;
1810 }
1811 
1812 /**
1813  * Works the same as r_detect_cycles, but checks for cycles in the reverse
1814  * direction along the cache chain. (A cycle may appear in either direction,
1815  * and we must check both.)
1816  */
1817 bool TransformState::
1818 r_detect_reverse_cycles(const TransformState *start_state,
1819  const TransformState *current_state,
1820  int length, UpdateSeq this_seq,
1822  if (current_state->_cycle_detect == this_seq) {
1823  // We've already seen this state; therefore, we've found a cycle.
1824 
1825  // However, we only care about cycles that return to the starting state
1826  // and involve more than two steps. If only one or two nodes are
1827  // involved, it doesn't represent a memory leak, so no problem there.
1828  return (current_state == start_state && length > 2);
1829  }
1830  ((TransformState *)current_state)->_cycle_detect = this_seq;
1831 
1832  size_t i;
1833  size_t cache_size = current_state->_composition_cache.get_num_entries();
1834  for (i = 0; i < cache_size; ++i) {
1835  const TransformState *other = current_state->_composition_cache.get_key(i);
1836  if (other != current_state) {
1837  int oi = other->_composition_cache.find(current_state);
1838  nassertr(oi != -1, false);
1839 
1840  const TransformState *result = other->_composition_cache.get_data(oi)._result;
1841  if (result != nullptr) {
1842  if (r_detect_reverse_cycles(start_state, result, length + 1,
1843  this_seq, cycle_desc)) {
1844  // Cycle detected.
1845  if (cycle_desc != nullptr) {
1846  const TransformState *other = current_state->_composition_cache.get_key(i);
1847  CompositionCycleDescEntry entry(other, result, false);
1848  cycle_desc->push_back(entry);
1849  }
1850  return true;
1851  }
1852  }
1853  }
1854  }
1855 
1856  cache_size = current_state->_invert_composition_cache.get_num_entries();
1857  for (i = 0; i < cache_size; ++i) {
1858  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1859  if (other != current_state) {
1860  int oi = other->_invert_composition_cache.find(current_state);
1861  nassertr(oi != -1, false);
1862 
1863  const TransformState *result = other->_invert_composition_cache.get_data(oi)._result;
1864  if (result != nullptr) {
1865  if (r_detect_reverse_cycles(start_state, result, length + 1,
1866  this_seq, cycle_desc)) {
1867  // Cycle detected.
1868  if (cycle_desc != nullptr) {
1869  const TransformState *other = current_state->_invert_composition_cache.get_key(i);
1870  CompositionCycleDescEntry entry(other, result, false);
1871  cycle_desc->push_back(entry);
1872  }
1873  return true;
1874  }
1875  }
1876  }
1877  }
1878 
1879  // No cycle detected.
1880  return false;
1881 }
1882 
1883 
1884 /**
1885  * This inverse of return_new, this releases this object from the global
1886  * TransformState table.
1887  *
1888  * You must already be holding _states_lock before you call this method.
1889  */
1890 void TransformState::
1891 release_new() {
1892  nassertv(_states_lock->debug_is_locked());
1893 
1894  if (_saved_entry != -1) {
1895  _saved_entry = -1;
1896  nassertv_always(_states->remove(this));
1897  }
1898 }
1899 
1900 /**
1901  * Remove all pointers within the cache from and to this particular
1902  * TransformState. The pointers to this object may be scattered around in the
1903  * various CompositionCaches from other TransformState objects.
1904  *
1905  * You must already be holding _states_lock before you call this method.
1906  */
1907 void TransformState::
1908 remove_cache_pointers() {
1909  nassertv(_states_lock->debug_is_locked());
1910 
1911  // Fortunately, since we added CompositionCache records in pairs, we know
1912  // exactly the set of TransformState objects that have us in their cache:
1913  // it's the same set of TransformState objects that we have in our own
1914  // cache.
1915 
1916 /*
1917  * We do need to put considerable thought into this loop, because as we clear
1918  * out cache entries we'll cause other TransformState objects to destruct,
1919  * which could cause things to get pulled out of our own _composition_cache
1920  * map. We want to allow this (so that we don't encounter any just-destructed
1921  * pointers in our cache), but we don't want to get bitten by this cascading
1922  * effect. Instead of walking through the map from beginning to end,
1923  * therefore, we just pull out the first one each time, and erase it.
1924  */
1925 
1926 #ifdef DO_PSTATS
1927  if (_composition_cache.is_empty() && _invert_composition_cache.is_empty()) {
1928  return;
1929  }
1930  PStatTimer timer(_cache_update_pcollector);
1931 #endif // DO_PSTATS
1932 
1933  // There are lots of ways to do this loop wrong. Be very careful if you
1934  // need to modify it for any reason.
1935  size_t i = 0;
1936  while (!_composition_cache.is_empty()) {
1937  // It is possible that the "other" TransformState object is currently
1938  // within its own destructor. We therefore can't use a PT() to hold its
1939  // pointer; that could end up calling its destructor twice. Fortunately,
1940  // we don't need to hold its reference count to ensure it doesn't destruct
1941  // while we process this loop; as long as we ensure that no *other*
1942  // TransformState objects destruct, there will be no reason for that one
1943  // to.
1944  TransformState *other = (TransformState *)_composition_cache.get_key(i);
1945 
1946  // We hold a copy of the composition result so we can dereference it
1947  // later.
1948  Composition comp = _composition_cache.get_data(i);
1949 
1950  // Now we can remove the element from our cache. We do this now, rather
1951  // than later, before any other TransformState objects have had a chance
1952  // to destruct, so we are confident that our iterator is still valid.
1953  _composition_cache.remove_element(i);
1954  _cache_stats.add_total_size(-1);
1955  _cache_stats.inc_dels();
1956 
1957  if (other != this) {
1958  int oi = other->_composition_cache.find(this);
1959 
1960  // We may or may not still be listed in the other's cache (it might be
1961  // halfway through pulling entries out, from within its own destructor).
1962  if (oi != -1) {
1963  // Hold a copy of the other composition result, too.
1964  Composition ocomp = other->_composition_cache.get_data(oi);
1965 
1966  other->_composition_cache.remove_element(oi);
1967  _cache_stats.add_total_size(-1);
1968  _cache_stats.inc_dels();
1969 
1970  // It's finally safe to let our held pointers go away. This may have
1971  // cascading effects as other TransformState objects are destructed,
1972  // but there will be no harm done if they destruct now.
1973  if (ocomp._result != nullptr && ocomp._result != other) {
1974  cache_unref_delete(ocomp._result);
1975  }
1976  }
1977  }
1978 
1979  // It's finally safe to let our held pointers go away. (See comment
1980  // above.)
1981  if (comp._result != nullptr && comp._result != this) {
1982  cache_unref_delete(comp._result);
1983  }
1984  }
1985 
1986  // A similar bit of code for the invert cache.
1987  i = 0;
1988  while (!_invert_composition_cache.is_empty()) {
1989  TransformState *other = (TransformState *)_invert_composition_cache.get_key(i);
1990  nassertv(other != this);
1991  Composition comp = _invert_composition_cache.get_data(i);
1992  _invert_composition_cache.remove_element(i);
1993  _cache_stats.add_total_size(-1);
1994  _cache_stats.inc_dels();
1995  if (other != this) {
1996  int oi = other->_invert_composition_cache.find(this);
1997  if (oi != -1) {
1998  Composition ocomp = other->_invert_composition_cache.get_data(oi);
1999  other->_invert_composition_cache.remove_element(oi);
2000  _cache_stats.add_total_size(-1);
2001  _cache_stats.inc_dels();
2002  if (ocomp._result != nullptr && ocomp._result != other) {
2003  cache_unref_delete(ocomp._result);
2004  }
2005  }
2006  }
2007  if (comp._result != nullptr && comp._result != this) {
2008  cache_unref_delete(comp._result);
2009  }
2010  }
2011 }
2012 
2013 /**
2014  * Computes a suitable hash value for phash_map.
2015  */
2016 void TransformState::
2017 do_calc_hash() {
2018  PStatTimer timer(_transform_hash_pcollector);
2019  _hash = 0;
2020 
2021  static const int significant_flags =
2022  (F_is_invalid | F_is_identity | F_components_given | F_hpr_given | F_is_2d);
2023 
2024  int flags = (_flags & significant_flags);
2025  _hash = int_hash::add_hash(_hash, flags);
2026 
2027  if ((_flags & (F_is_invalid | F_is_identity)) == 0) {
2028  // Only bother to put the rest of the stuff in the hash if the transform
2029  // is not invalid or empty.
2030 
2031  if ((_flags & F_components_given) != 0) {
2032  // If the transform was specified componentwise, hash it componentwise.
2033  _hash = _pos.add_hash(_hash);
2034  if ((_flags & F_hpr_given) != 0) {
2035  _hash = _hpr.add_hash(_hash);
2036 
2037  } else if ((_flags & F_quat_given) != 0) {
2038  _hash = _quat.add_hash(_hash);
2039  }
2040 
2041  _hash = _scale.add_hash(_hash);
2042  _hash = _shear.add_hash(_hash);
2043 
2044  } else {
2045  // Otherwise, hash the matrix . . .
2046  if (_uniquify_matrix) {
2047  // . . . but only if the user thinks that's worthwhile.
2048  if ((_flags & F_mat_known) == 0) {
2049  // Calculate the matrix without doubly-locking.
2050  do_calc_mat();
2051  }
2052  _hash = _mat.add_hash(_hash);
2053 
2054  } else {
2055  // Otherwise, hash the pointer only--any two different matrix-based
2056  // TransformStates are considered to be different, even if their
2057  // matrices have the same values.
2058 
2059  _hash = pointer_hash::add_hash(_hash, this);
2060  }
2061  }
2062  }
2063 
2064  _flags |= F_hash_known;
2065 }
2066 
2067 /**
2068  * Determines whether the transform is singular (i.e. it scales to zero, and
2069  * has no inverse).
2070  */
2071 void TransformState::
2072 calc_singular() {
2073  LightMutexHolder holder(_lock);
2074  if ((_flags & F_singular_known) != 0) {
2075  // Someone else computed it first.
2076  return;
2077  }
2078 
2079  PStatTimer timer(_transform_calc_pcollector);
2080 
2081  nassertv((_flags & F_is_invalid) == 0);
2082 
2083  // We determine if a matrix is singular by attempting to invert it (and we
2084  // save the result of this invert operation for a subsequent
2085  // do_invert_compose() call, which is almost certain to be made if someone
2086  // is asking whether we're singular).
2087 
2088  // This should be NULL if no one has called calc_singular() yet.
2089  nassertv(_inv_mat == nullptr);
2090  _inv_mat = new LMatrix4;
2091 
2092  if ((_flags & F_mat_known) == 0) {
2093  do_calc_mat();
2094  }
2095  bool inverted = _inv_mat->invert_from(_mat);
2096 
2097  if (!inverted) {
2098  _flags |= F_is_singular;
2099  delete _inv_mat;
2100  _inv_mat = nullptr;
2101  }
2102  _flags |= F_singular_known;
2103 }
2104 
2105 /**
2106  * This is the implementation of calc_components(); it assumes the lock is
2107  * already held.
2108  */
2109 void TransformState::
2110 do_calc_components() {
2111  if ((_flags & F_components_known) != 0) {
2112  // Someone else computed it first.
2113  return;
2114  }
2115 
2116  PStatTimer timer(_transform_calc_pcollector);
2117 
2118  nassertv((_flags & F_is_invalid) == 0);
2119  if ((_flags & F_is_identity) != 0) {
2120  _scale.set(1.0f, 1.0f, 1.0f);
2121  _shear.set(0.0f, 0.0f, 0.0f);
2122  _hpr.set(0.0f, 0.0f, 0.0f);
2123  _quat = LQuaternion::ident_quat();
2124  _pos.set(0.0f, 0.0f, 0.0f);
2125  _flags |= F_has_components | F_components_known | F_hpr_known | F_quat_known | F_uniform_scale | F_identity_scale;
2126 
2127  } else {
2128  // If we don't have components and we're not identity, the only other
2129  // explanation is that we were constructed via a matrix.
2130  nassertv((_flags & F_mat_known) != 0);
2131 
2132  if ((_flags & F_mat_known) == 0) {
2133  do_calc_mat();
2134  }
2135  bool possible = decompose_matrix(_mat, _scale, _shear, _hpr, _pos);
2136  if (!possible) {
2137  // Some matrices can't be decomposed into scale, hpr, pos. In this
2138  // case, we now know that we cannot compute the components; but the
2139  // closest approximations are stored, at least.
2140  _flags |= F_components_known | F_hpr_known;
2141 
2142  } else {
2143  // Otherwise, we do have the components, or at least the hpr.
2144  _flags |= F_has_components | F_components_known | F_hpr_known;
2145  check_uniform_scale();
2146  }
2147 
2148  // However, we can always get at least the pos.
2149  _mat.get_row3(_pos, 3);
2150  }
2151 }
2152 
2153 /**
2154  * This is the implementation of calc_hpr(); it assumes the lock is already
2155  * held.
2156  */
2157 void TransformState::
2158 do_calc_hpr() {
2159  if ((_flags & F_hpr_known) != 0) {
2160  // Someone else computed it first.
2161  return;
2162  }
2163 
2164  PStatTimer timer(_transform_calc_pcollector);
2165 
2166  nassertv((_flags & F_is_invalid) == 0);
2167  if ((_flags & F_components_known) == 0) {
2168  do_calc_components();
2169  }
2170  if ((_flags & F_hpr_known) == 0) {
2171  // If we don't know the hpr yet, we must have been given a quat.
2172  // Decompose it.
2173  nassertv((_flags & F_quat_known) != 0);
2174  _hpr = _quat.get_hpr();
2175  _flags |= F_hpr_known;
2176  }
2177 }
2178 
2179 /**
2180  * Derives the quat from the hpr.
2181  */
2182 void TransformState::
2183 calc_quat() {
2184  LightMutexHolder holder(_lock);
2185  if ((_flags & F_quat_known) != 0) {
2186  // Someone else computed it first.
2187  return;
2188  }
2189 
2190  PStatTimer timer(_transform_calc_pcollector);
2191 
2192  nassertv((_flags & F_is_invalid) == 0);
2193  if ((_flags & F_components_known) == 0) {
2194  do_calc_components();
2195  }
2196  if ((_flags & F_quat_known) == 0) {
2197  // If we don't know the quat yet, we must have been given a hpr.
2198  // Decompose it.
2199  nassertv((_flags & F_hpr_known) != 0);
2200  _quat.set_hpr(_hpr);
2201  _flags |= F_quat_known;
2202  }
2203 }
2204 
2205 /**
2206  * Derives the normalized quat from the quat.
2207  */
2208 void TransformState::
2209 calc_norm_quat() {
2210  PStatTimer timer(_transform_calc_pcollector);
2211 
2212  LQuaternion quat = get_quat();
2213  LightMutexHolder holder(_lock);
2214  _norm_quat = quat;
2215  _norm_quat.normalize();
2216  _flags |= F_norm_quat_known;
2217 }
2218 
2219 /**
2220  * This is the implementation of calc_mat(); it assumes the lock is already
2221  * held.
2222  */
2223 void TransformState::
2224 do_calc_mat() {
2225  if ((_flags & F_mat_known) != 0) {
2226  // Someone else computed it first.
2227  return;
2228  }
2229 
2230  PStatTimer timer(_transform_calc_pcollector);
2231 
2232  nassertv((_flags & F_is_invalid) == 0);
2233  if ((_flags & F_is_identity) != 0) {
2234  _mat = LMatrix4::ident_mat();
2235 
2236  } else {
2237  // If we don't have a matrix and we're not identity, the only other
2238  // explanation is that we were constructed via components.
2239  nassertv((_flags & F_components_known) != 0);
2240  if ((_flags & F_hpr_known) == 0) {
2241  do_calc_hpr();
2242  }
2243 
2244  compose_matrix(_mat, _scale, _shear, get_hpr(), _pos);
2245  }
2246  _flags |= F_mat_known;
2247 }
2248 
2249 /**
2250  * Moves the TransformState object from one PStats category to another, so
2251  * that we can track in PStats how many pointers are held by nodes, and how
2252  * many are held in the cache only.
2253  */
2254 void TransformState::
2255 update_pstats(int old_referenced_bits, int new_referenced_bits) {
2256 #ifdef DO_PSTATS
2257  if ((old_referenced_bits & R_node) != 0) {
2258  _node_counter.sub_level(1);
2259  } else if ((old_referenced_bits & R_cache) != 0) {
2260  _cache_counter.sub_level(1);
2261  }
2262  if ((new_referenced_bits & R_node) != 0) {
2263  _node_counter.add_level(1);
2264  } else if ((new_referenced_bits & R_cache) != 0) {
2265  _cache_counter.add_level(1);
2266  }
2267 #endif // DO_PSTATS
2268 }
2269 
2270 /**
2271  * Tells the BamReader how to create objects of type TransformState.
2272  */
2273 void TransformState::
2274 register_with_read_factory() {
2275  BamReader::get_factory()->register_factory(get_class_type(), make_from_bam);
2276 }
2277 
2278 /**
2279  * Writes the contents of this object to the datagram for shipping out to a
2280  * Bam file.
2281  */
2282 void TransformState::
2283 write_datagram(BamWriter *manager, Datagram &dg) {
2284  TypedWritable::write_datagram(manager, dg);
2285 
2286  if ((_flags & F_is_identity) != 0) {
2287  // Identity, nothing much to that.
2288  int flags = F_is_identity | F_singular_known | F_is_2d;
2289  dg.add_uint32(flags);
2290 
2291  } else if ((_flags & F_is_invalid) != 0) {
2292  // Invalid, nothing much to that either.
2293  int flags = F_is_invalid | F_singular_known | F_is_singular | F_components_known | F_mat_known;
2294  dg.add_uint32(flags);
2295 
2296  } else if ((_flags & F_components_given) != 0) {
2297  // A component-based transform.
2298  int flags = F_components_given | F_components_known | F_has_components;
2299  flags |= (_flags & F_is_2d);
2300  if ((_flags & F_quat_given) != 0) {
2301  flags |= (F_quat_given | F_quat_known);
2302  } else if ((_flags & F_hpr_given) != 0) {
2303  flags |= (F_hpr_given | F_hpr_known);
2304  }
2305 
2306  dg.add_uint32(flags);
2307 
2308  _pos.write_datagram(dg);
2309  if ((_flags & F_quat_given) != 0) {
2310  _quat.write_datagram(dg);
2311  } else {
2312  get_hpr().write_datagram(dg);
2313  }
2314  _scale.write_datagram(dg);
2315  _shear.write_datagram(dg);
2316 
2317  } else {
2318  // A general matrix.
2319  nassertv((_flags & F_mat_known) != 0);
2320  int flags = F_mat_known;
2321  flags |= (_flags & F_is_2d);
2322  dg.add_uint32(flags);
2323  _mat.write_datagram(dg);
2324  }
2325 }
2326 
2327 /**
2328  * Called immediately after complete_pointers(), this gives the object a
2329  * chance to adjust its own pointer if desired. Most objects don't change
2330  * pointers after completion, but some need to.
2331  *
2332  * Once this function has been called, the old pointer will no longer be
2333  * accessed.
2334  */
2335 PT(TypedWritableReferenceCount) TransformState::
2336 change_this(TypedWritableReferenceCount *old_ptr, BamReader *manager) {
2337  // First, uniquify the pointer.
2338  TransformState *state = DCAST(TransformState, old_ptr);
2339  CPT(TransformState) pointer = return_unique(state);
2340 
2341  // We have to cast the pointer back to non-const, because the bam reader
2342  // expects that.
2343  return (TransformState *)pointer.p();
2344 }
2345 
2346 /**
2347  * This function is called by the BamReader's factory when a new object of
2348  * type TransformState is encountered in the Bam file. It should create the
2349  * TransformState and extract its information from the file.
2350  */
2351 TypedWritable *TransformState::
2352 make_from_bam(const FactoryParams &params) {
2353  TransformState *state = new TransformState;
2354  DatagramIterator scan;
2355  BamReader *manager;
2356 
2357  parse_params(params, scan, manager);
2358  state->fillin(scan, manager);
2359  manager->register_change_this(change_this, state);
2360 
2361  return state;
2362 }
2363 
2364 /**
2365  * This internal function is called by make_from_bam to read in all of the
2366  * relevant data from the BamFile for the new TransformState.
2367  */
2368 void TransformState::
2369 fillin(DatagramIterator &scan, BamReader *manager) {
2370  TypedWritable::fillin(scan, manager);
2371  _flags = scan.get_uint32();
2372 
2373  if ((_flags & F_components_given) != 0) {
2374  // Componentwise transform.
2375  _pos.read_datagram(scan);
2376  if ((_flags & F_quat_given) != 0) {
2377  _quat.read_datagram(scan);
2378  } else {
2379  _hpr.read_datagram(scan);
2380  }
2381  _scale.read_datagram(scan);
2382  _shear.read_datagram(scan);
2383 
2384  check_uniform_scale();
2385  }
2386 
2387  if ((_flags & F_mat_known) != 0) {
2388  // General matrix.
2389  _mat.read_datagram(scan);
2390  }
2391 }
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
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:30
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