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