NCBI C++ ToolKit
phylo_tree_ps.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: phylo_tree_ps.cpp 47479 2023-05-02 13:24:02Z ucko $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  *
26  * Authors: Bob Falk
27  *
28  * File Description:
29  * Force tree layout
30  */
31 
32 #include <ncbi_pch.hpp>
33 
34 #include <corelib/ncbitime.hpp>
35 
39 
41 
42 #include <corelib/ncbitime.hpp>
43 #include <corelib/ncbistl.hpp>
44 
45 #include <cmath>
46 
47 //#define NUMERIC_ERROR_CHECK
48 template<typename T> bool isFinite(T arg)
49 {
50  return arg == arg &&
53 }
54 
56 
57 //#define VALIDATE_NODE_NODE_FORCES 1
58 
60 : m_ElectricalRepulsion(100.0f)
61 , m_Step(0.015f)
62 , m_Damping(0.89f)
63 , m_EdgeK(250.0f)
64 , m_RepulsionDist(350.0f)
65 , m_VelocityThresholdK(0.002f)
66 {
67 }
68 
70 : m_AdaptiveStep(1.0f)
71 , m_MaxVelocity(1.0f)
72 , m_PrevMaxVelocity(1.0)
73 , m_IsDone(false)
74 , m_Tree(NULL)
75 {
76  // Set up interactive menus for debugging.
77 #ifdef ATTRIB_MENU_SUPPORT
79 
80  CAttribMenu* sub_menu = m.AddSubMenuUnique("PhyloTreePS", this);
81 
82  sub_menu->AddFloat("Step Size",
83  &m_PhysicsParmsVolatile.m_Step, 0.02f, 0.000001f, 1.0f, 0.01f);
84  sub_menu->AddFloat("Damping",
85  &m_PhysicsParmsVolatile.m_Damping, 0.88f, 0.0f, 1.0f, 0.01f);
86  sub_menu->AddFloat("Edge K",
87  &m_PhysicsParmsVolatile.m_EdgeK, 300.0f, 0.0f, 1000.0f, 10.0f);
88  sub_menu->AddFloat("Repulsion",
89  &m_PhysicsParmsVolatile.m_ElectricalRepulsion, 100.0f, 0.0f, 500.0f, 5.0f);
90  sub_menu->AddFloat("Rep Dist",
91  &m_PhysicsParmsVolatile.m_RepulsionDist, 300.0f, 0.0f, 10000.0f, 20.0f);
92  sub_menu->AddFloat("Vel Threshold K",
93  &m_PhysicsParmsVolatile.m_VelocityThresholdK, 0.003f, 0.0f, 1.0f, 0.001f);
94 
95  sub_menu->AddFloatReadOnly("Time Edge F", &m_edge_forces_safe_t);
96  sub_menu->AddFloatReadOnly("Time Node F", &m_node_forces_safe_t);
97  sub_menu->AddFloatReadOnly("Time Int", &m_integrate_safe_t);
98  sub_menu->AddFloatReadOnly("Time Vox Update", &m_bound_update_safe_t);
99  sub_menu->AddIntReadOnly("Node-Node Int", &m_node_node_interactions_safe_t);
100  sub_menu->AddFloatReadOnly("Maximum Velocity", &m_MaxVelocity);
101  sub_menu->AddFloatReadOnly("Adaptive Step", &m_AdaptiveStep);
102 #endif
103 
104  Init(ds);
105 }
106 
107 
109 {
110 #ifdef ATTRIB_MENU_SUPPORT
112  m.RemoveMenuR("PhyloTreePS", this);
113 #endif
114 
115  Clear();
116 }
117 
119 {
120  m_Nodes.clear();
121  m_Edges.clear();
122  m_MaxVelocity = 1.0f;
123  m_PrevMaxVelocity = 1.0f;
124  m_AdaptiveStep = 1.0f;
125  m_IsDone = false;
126 
127  // This is taken care of in Init()
128  //m_NodeGrid.Clear();
129 
130 #ifdef VALIDATE_NODE_NODE_FORCES
131  m_ValidateGrid.clear();
132  m_ValidateNsq.clear();
133 #endif
134 }
135 
137 {
138  Clear();
139 
140  m_Tree = ds.GetTree();
141 
142  m_DefaultEdgeLen = 0.0f;
143 
148 
149  x_Init(ds.GetTree());
150 
151  x_UpdateVoxels();
152 
153  m_DefaultEdgeLen /= (float)m_Edges.size();
154 
155  // Compute edge forces between nodes
156  std::vector<Edge>::iterator eiter;
157 
158  for (eiter=m_Edges.begin(); eiter!=m_Edges.end(); ++eiter) {
159  (*eiter).rest_len_inv = 1.0f/m_DefaultEdgeLen;
160  }
161 }
162 
163 void CPhyloTreePS::x_ApplyNeighborCellForces(std::vector<int>& cell_nodes,
164  const CVect2<int>& adjacent_idx)
165 {
166  std::vector<int>& neighbor_nodes = m_NodeGrid.Get(adjacent_idx);
167 
168  // For all nodes in a pair of cells, compute the forces between them
169  for (size_t i=0; i<cell_nodes.size(); ++i) {
170  for (size_t j=0; j<neighbor_nodes.size(); ++j) {
171  int idx1 = cell_nodes[i];
172  int idx2 = neighbor_nodes[j];
173 
174  TVec offset(m_Nodes[idx1].pos - m_Nodes[idx2].pos);
175 
176  float dist2 = offset.Length2();
177 
178  if (dist2 < m_RepulsionDist2 && dist2 > FLT_EPSILON) {
179 
180  if (dist2 > FLT_EPSILON) {
181  float dist = sqrtf(dist2);
182 
185  m_Nodes[idx1].accel += offset;
186  m_Nodes[idx2].accel -= offset;
187 
188 #ifdef NUMERIC_ERROR_CHECK
189  if (!isFinite( m_Nodes[idx1].accel.X()) || !isFinite( m_Nodes[idx1].accel.Y())) {
190  _TRACE("Bad float! " << m_Nodes[idx1].accel.X() << " " << m_Nodes[idx1].accel.Y());
191  }
192  if (!isFinite( m_Nodes[idx2].accel.X()) || !isFinite( m_Nodes[idx2].accel.Y())) {
193  _TRACE("Bad float! " << m_Nodes[idx2].accel.X() << " " << m_Nodes[idx2].accel.Y());
194  }
195 #endif
196 
197 
199 
200 #ifdef VALIDATE_NODE_NODE_FORCES
201  m_ValidateGrid.push_back( CVect2<int>(std::min(idx1, idx2), std::max(idx1, idx2) );
202 #endif
203  }
204  // for debugging
205  //m_Nodes[idx1].force_nodes.push_back(idx2);
206  //m_Nodes[idx2].force_nodes.push_back(idx1);
207  }
208  }
209  }
210 }
211 
213  {
214  CVect2<int> min_pos = 0; //m_NodeGrid.GetMin();
216 
217  // Iterate over the whole grid which subdivides the space occupied
218  // by the tree into individual cells. For each cell, compute the
219  // forces between all the nodes in that cell, and then compute
220  // the forces between nodes in that cell and nodes in adjacent
221  // cells. Node forces will not travel more than one cell since
222  // we base cell size on the maximum distance for the the repulsion
223  // force between cells.
224  for (int x = min_pos.X(); x <= max_pos.X(); ++x) {
225  for (int y = min_pos.Y(); y <= max_pos.Y(); ++y) {
226  CVect2<int> idx(x,y);
227  std::vector<int>& cell_nodes = m_NodeGrid.Get(idx);
228  if (cell_nodes.size() > 0) {
229  // Find collisions between nodes hashed in this entry
230  for (size_t i=0; i<cell_nodes.size(); ++i) {
231  for (size_t j=i+1; j<cell_nodes.size(); ++j) {
232 
233  int idx1 = cell_nodes[i];
234  int idx2 = cell_nodes[j];
235 
236  TVec offset(m_Nodes[idx1].pos - m_Nodes[idx2].pos);
237 
238  float dist2 = offset.Length2();
239 
240  // Compute forces between one pair of nodes
241  if (dist2 < m_RepulsionDist2 && dist2 > FLT_EPSILON) {
242  float dist = sqrtf(dist2);
243 
246  m_Nodes[idx1].accel += offset;
247  m_Nodes[idx2].accel -= offset;
248 
249 #ifdef NUMERIC_ERROR_CHECK
250  if (!isFinite( m_Nodes[idx1].accel.X()) || !isFinite( m_Nodes[idx1].accel.Y())) {
251  _TRACE("Bad float! " << m_Nodes[idx1].accel.X() << " " << m_Nodes[idx1].accel.Y());
252  }
253 
254  if (!isFinite( m_Nodes[idx2].accel.X()) || !isFinite( m_Nodes[idx2].accel.Y())) {
255  _TRACE("Bad float! " << m_Nodes[idx2].accel.X() << " " << m_Nodes[idx2].accel.Y());
256  }
257 #endif
258 
259 
261 
262 #ifdef VALIDATE_NODE_NODE_FORCES
263  m_ValidateGrid.push_back( CVect2<int>(std::min(idx1, idx2), std::max(idx1, idx2) );
264 #endif
265 
266  //m_Nodes[idx1].force_nodes.push_back(idx2); // for debugging
267  //m_Nodes[idx2].force_nodes.push_back(idx1);
268  }
269  }
270  }
271 
272 
273  // Find all collisions between nodes in this entry and nodes
274  // in the adjacent cells idx(x+1,y), idx(x+1,y+1), idx(x,y+1),
275  // idx(x-1,y+1). Only look at nodes in positive direction so that
276  // you don't compute forces between adjacent cells twice (once
277  // when you visit each cell)
278  if (x+1 < m_NodeGrid.GetWidth()) {
279  x_ApplyNeighborCellForces(cell_nodes, CVect2<int>(x+1,y));
280 
281  if (y+1 < m_NodeGrid.GetHeight())
282  x_ApplyNeighborCellForces(cell_nodes, CVect2<int>(x+1,y+1));
283  }
284 
285  if (y+1 < m_NodeGrid.GetHeight()) {
286  x_ApplyNeighborCellForces(cell_nodes, CVect2<int>(x,y+1));
287 
288  if (x > 0)
289  x_ApplyNeighborCellForces(cell_nodes, CVect2<int>(x-1,y+1));
290  }
291 
292  }
293  }
294  }
295  }
296 
297 // Simple global form of repulsive forces. Has better visual result still,
298 // but is quite a bit slower.
300 {
301  // Iterate over all nodes and compute forces between them
302  for (size_t i=0; i<m_Nodes.size(); ++i) {
303  for (size_t j=i+1; j<m_Nodes.size(); ++j) {
304  TVec offset(m_Nodes[i].pos - m_Nodes[j].pos);
305 
306  float dist2 = offset.Length2();
307  if (dist2 > FLT_EPSILON) {
308  //offset *= (m_ElectricalRepulsion-m_RepulsionInv_x_ElectricalRepulsion*dist)/(dist2+ + FLT_EPSILON);
310  m_Nodes[i].accel += offset;
311  m_Nodes[j].accel -= offset;
312 
313 #ifdef NUMERIC_ERROR_CHECK
314  if (!isFinite( m_Nodes[i].accel.X()) || !isFinite( m_Nodes[i].accel.Y())) {
315  _TRACE("Bad float! " << m_Nodes[i].accel.X() << " " << m_Nodes[i].accel.Y());
316  }
317  if (!isFinite( m_Nodes[j].accel.X()) || !isFinite( m_Nodes[j].accel.Y())) {
318  _TRACE("Bad float! " << m_Nodes[j].accel.X() << " " << m_Nodes[j].accel.Y());
319  }
320 #endif
321 
323 
324 #ifdef VALIDATE_NODE_NODE_FORCES
325  m_ValidateGrid.push_back( CVect2<int>(std::min(idx1, idx2), std::max(idx1, idx2) );
326 #endif
327  }
328  }
329  }
330 }
331 
332 
334 {
335 #ifdef VALIDATE_NODE_NODE_FORCES
336  m_ValidateGrid.clear();
337  m_ValidateNsq.clear();
338 #endif
339 
340 
345 
346  // Compute edge forces between nodes
347  std::vector<Edge>::iterator eiter;
348 
349  m_LogDistMax = -500.0f;
350  m_LogDistMin = 500.0f;
351 
352  CStopWatch sw;
354 
355  sw.Start();
356 
357  // Compute forces from all edges
358  for (eiter=m_Edges.begin(); eiter!=m_Edges.end(); ++eiter) {
359  Node& n1 = m_Nodes[(*eiter).from_idx];
360  Node& n2 = m_Nodes[(*eiter).to_idx];
361 
362  TVec offset(n1.pos - n2.pos);
363  float dist = offset.Length();
364  (*eiter).len = dist;
365 
366  if (dist > FLT_EPSILON) {
367  float ldist = logf(dist*(*eiter).rest_len_inv);
368  //m_LogDistMax = std::max(ldist, m_LogDistMax);
369  //m_LogDistMin = std::min(ldist, m_LogDistMin);
370  offset *= (1.0f/dist)*ldist*m_PhysicsParmsSafe.m_EdgeK;
371 
372  n1.accel -= offset;
373  n2.accel += offset;
374 
375 #ifdef NUMERIC_ERROR_CHECK
376  if (!isFinite( n1.accel.X()) || !isFinite( n1.accel.Y())) {
377  _TRACE("Bad float! " << n1.accel.X() << " " << n1.accel.Y());
378  }
379  if (!isFinite( n2.accel.X()) || !isFinite( n2.accel.Y())) {
380  _TRACE("Bad float! " << n2.accel.X() << " " << n2.accel.Y());
381  }
382 #endif
383  }
384 
385  }
386 
387  sw.Stop();
388  m_edge_forces_t = sw.Elapsed()*1000.0f;
389 
390 
391  // Compute repulsion forces between all nodes (n^2 version)
392 #ifdef VALIDATE_NODE_NODE_FORCES
393  std::vector<Node>::iterator niter1, niter2;
394  for (niter1=m_Nodes.begin(); niter1!=m_Nodes.end(); ++niter1) {
395  TVec p1 = (*niter1).pos;
396 
397  for (niter2=niter1+1; niter2!=m_Nodes.end(); ++niter2) {
398  TVec p2 = (*niter2).pos;
399  TVec offset(p1-p2);
400 
401  //float dist = offset.Length() + 0.00001f;
402 
403  float dist2 = offset.Length2();
404  if (dist2 < m_RepulsionDist2) {
405  int idx1 = niter1-m_Nodes.begin();
406  int idx2 = niter2-m_Nodes.begin();
407  m_ValidateNsq.push_back( CVect2<int>(std::min(idx1, idx2), std::max(idx1, idx2) );
408  /*
409  float dist = sqrtf(dist2);
410  float mult_factor = (1.0f/dist)* (m_ElectricalRepulsion/dist);
411 
412  offset *= mult_factor;
413 
414  (*niter1).accel += offset;
415  (*niter2).accel -= offset;
416  */
417  }
418  }
419  }
420 #endif
421 
422 
423  sw.Restart();
424 
425  // Compute repulsive forces between nodes
426  //x_ApplyRepulsiveForces();
428 
429  m_node_forces_t = sw.Elapsed()*1000.0f;
430 }
431 
432 
433 
435 {
436  {
437  // Throttle step size if velocity is too high.
438  // Not really proper adaptive time stepping, but it should
439  // keep things from exploding
440  if (m_MaxVelocity > 20.0f &&
442  m_AdaptiveStep > 0.01f) {
444  }
445  else if (m_AdaptiveStep < 1.0f &&
446  m_MaxVelocity < 20.0f &&
448  m_AdaptiveStep += (1.0f - m_AdaptiveStep)*0.01f;
449  }
450  }
451 
452  // Compute all forces
453  CalcForces();
454 
455  // Reset tree extent, so that we can recompute it as
456  // we update the system. Extent is neede for our spatial
457  // collision grid each update.
462 
463  CStopWatch sw;
464  sw.Start();
465 
466  // This will reduce step size if we seem unstable.
468 
469  // Integrate forces into position updates
470  std::vector<Node>::iterator niter;
471  for (niter=m_Nodes.begin(); niter!=m_Nodes.end(); ++niter) {
472  // pos = pos + (pos-prev_pos)*damping + accel*dt;
473  TVec prev_offset((*niter).pos - (*niter).prev_pos);
474  (*niter).prev_pos = (*niter).pos;
475 
476  (*niter).pos.X() += (prev_offset.X()*m_PhysicsParmsSafe.m_Damping +
477  (*niter).accel.X()*step)*(*niter).constrained;
478  (*niter).pos.Y() += (prev_offset.Y()*m_PhysicsParmsSafe.m_Damping +
479  (*niter).accel.Y()*step)*(*niter).constrained;
480 
481 #ifdef NUMERIC_ERROR_CHECK
482  if (!isFinite((*niter).pos.X()) || !isFinite((*niter).pos.Y())) {
483  _TRACE("Bad float! " << (*niter).pos.X() << " " << (*niter).pos.Y());
484  }
485 #endif
486 
487  m_MinPos.X() = std::min(m_MinPos.X(), (*niter).pos.X());
488  m_MinPos.Y() = std::min(m_MinPos.Y(), (*niter).pos.Y());
489  m_MaxPos.X() = std::max(m_MaxPos.X(), (*niter).pos.X());
490  m_MaxPos.Y() = std::max(m_MaxPos.Y(), (*niter).pos.Y());
491 
492  (*niter).accel = TVec( TVec::TVecType(0) );
493 
494  //(*niter).prev_force_nodes = (*niter).force_nodes;
495  //(*niter).force_nodes.clear();
496  };
497 
498  sw.Stop();
499  m_integrate_t = sw.Elapsed()*1000.0f;
500 
501  sw.Restart();
502  // Update spatial data structure
503  x_UpdateVoxels();
504  m_bound_update_t = sw.Elapsed()*1000.0f;
505 }
506 
507 // Do the same thing as update, but also update the underlying
508 // data structure.
510 {
511  // This function is thread-safe, so update parms here:
513 
514  CalcForces();
515 
516  float max_velocity_squared = 0.0f;
517 
522 
524 
525  // Integrate and reset
526  std::vector<Node>::iterator niter;
527  for (niter=m_Nodes.begin(); niter!=m_Nodes.end(); ++niter) {
528  // pos = pos + (pos-prev_pos)*damping + accel*dt;
529  TVec prev_offset((*niter).pos - (*niter).prev_pos);
530  (*niter).prev_pos = (*niter).pos;
531 
532  float xoff = (prev_offset.X()*m_PhysicsParmsSafe.m_Damping +
533  (*niter).accel.X()*step)*(*niter).constrained;
534  float yoff = (prev_offset.Y()*m_PhysicsParmsSafe.m_Damping +
535  (*niter).accel.Y()*step)*(*niter).constrained;
536 
537  max_velocity_squared = std::max(max_velocity_squared, xoff*xoff + yoff*yoff);
538 
539  (*niter).pos.X() += xoff;
540  (*niter).pos.Y() += yoff;
541 
542  m_MinPos.X() = std::min(m_MinPos.X(), (*niter).pos.X());
543  m_MinPos.Y() = std::min(m_MinPos.Y(), (*niter).pos.Y());
544  m_MaxPos.X() = std::max(m_MaxPos.X(), (*niter).pos.X());
545  m_MaxPos.Y() = std::max(m_MaxPos.Y(), (*niter).pos.Y());
546 
547  // update node....
548 
549  (*m_Tree)[(*niter).tree_node_idx]->XY() = (*niter).pos;
550 
551  // Need angle to compute label positions
552  CPhyloTree::TTreeIdx pidx = (*m_Tree)[(*niter).tree_node_idx].GetParent();
553  if (pidx != CPhyloTree::Null()) {
554  CVect2<float> ppos = (*m_Tree)[pidx]->XY();
555 
556  // For how its currently used we just set hard coded angles
557  // based on whether x is positive or negative since we are only deciding
558  // if label is on left or right side
559  (*m_Tree)[(*niter).tree_node_idx]->SetAngle(
560  ((*niter).pos.X()-ppos.X() >= 0.0f) ? 0.0f : 3.1415927f);
561  }
562 
563  (*niter).accel = TVec( TVec::TVecType(0) );
564  };
565 
567  m_MaxVelocity = sqrtf(max_velocity_squared)/m_PhysicsParmsSafe.m_Step;
568 
569  /// It would be better to filter this result (probably filter x frames of
570  /// velocity to search for outliers and make sure average is good)
571  if (!m_IsDone) {
572  float node_count = (float)m_Nodes.size();
573  float threshold = m_PhysicsParmsSafe.m_VelocityThresholdK*((node_count+100.0f)/5.0f);
574  threshold = std::min(10.0f, threshold);
575  //_TRACE("Threshold: " << threshold << " max_velocity: " << m_MaxVelocity << " velocity threshold: " << m_PhysicsParmsSafe.m_VelocityThresholdK);
576  if (m_AdaptiveStep > 0.9f &&
577  m_MaxVelocity < threshold) {
578  m_IsDone = true;
579  }
580  }
581 
587 
588  x_UpdateVoxels();
589 }
590 
592 {
593  std::vector<Edge>::iterator eiter;
594 
595 
596  glLineWidth(2.0f);
597  glBegin(GL_LINES);
598 
599  for (eiter=m_Edges.begin(); eiter!=m_Edges.end(); ++eiter) {
600  Node& n1 = m_Nodes[(*eiter).from_idx];
601  Node& n2 = m_Nodes[(*eiter).to_idx];
602 
603  TVec offset(n1.pos - n2.pos);
604  float dist = offset.Length();
605  float ldist = logf(dist*(*eiter).rest_len_inv);
606 
607  if (ldist >= 0.0f)
608  glColor3f(std::max(0.0f, ldist/m_LogDistMax), 0.0f, 0.0f);
609  else
610  glColor3f(0.0f, 0.0f, std::max(0.0f, std::abs(ldist/m_LogDistMin)));
611 
612  glVertex2fv(n1.pos.GetData());
613  glVertex2fv(n2.pos.GetData());
614  }
615 
616  glEnd();
617 
618 
619  glPointSize(5.0f);
620  glColor3f(1.0f, 1.0f, 0.0f);
621  glBegin(GL_POINTS);
622  std::vector<Node>::iterator niter;
623  /*
624  for (niter=m_Nodes.begin(); niter!=m_Nodes.end(); ++niter) {
625  if ( (*m_Tree)[*niter]->GetSelectedState() == CPhyloNodeData::eSelected) {
626  glBegin(GL_LINES);
627  for (size_t j=0; j<(*niter).prev_force_nodes.size(); ++j) {
628  int idx = (*niter).prev_force_nodes[j];
629  TVec p1 = (*niter).pos;
630  TVec p2 = m_Nodes[idx].pos;
631  glVertex2fv(p1.GetData());
632  glVertex2fv(p2.GetData());
633  }
634  glEnd();
635 
636  glLineWidth(1.0f);
637  }
638  if ( !(*niter).constrained ) {
639  glVertex2fv((*niter).pos.GetData());
640  }
641  }
642  */
643  glEnd();
644 
645 #ifdef VALIDATE_NODE_NODE_FORCES
646  //m_ValidateGrid.clear();
647  //m_ValidateNsq.clear();
648 #endif
649 }
650 
651 
653 {
654  // Reset size of collision grid based on current node extent
659 
660  m_NodeGrid.SetMax(max_idx);
661  m_NodeGrid.SetMin(min_idx);
662 
663  // Resize and clear spatial grid
665  m_NodeGrid.Clear();
666 
667  // Put all nodes into the correct places in the grid
668  for (size_t j=0; j<m_Nodes.size(); ++j) {
669  TVec pos = m_Nodes[j].pos;
670  CVect2<int> posi(int(pos[0]/m_PhysicsParmsSafe.m_RepulsionDist) - min_idx.X(),
671  int(pos[1]/m_PhysicsParmsSafe.m_RepulsionDist) - min_idx.Y());
672 
673  m_NodeGrid.Get(posi).push_back(static_cast<int>(j));
674  }
675 }
676 
678 {
679 public:
681 
682 public:
684  : m_PS(ps)
685  {
686  }
687 
689  TTreeIdx node_idx, int delta)
690  {
691  if (delta==1 || delta==0) {
692  CPhyloTree::TNodeType& tnode = tree[node_idx];
694  n.pos = tnode->XY();
695  n.prev_pos = n.pos;
696  n.accel = 0.0f;
697  n.constrained = 1.0f;
698  n.tree_node_idx = node_idx;
699  n.is_leaf = tnode.IsLeaf();
700 
701  m_PS->GetMinPos().X() = std::min(m_PS->GetMinPos().X(), n.pos.X());
702  m_PS->GetMinPos().Y() = std::min(m_PS->GetMinPos().Y(), n.pos.Y());
703  m_PS->GetMaxPos().X() = std::max(m_PS->GetMaxPos().X(), n.pos.X());
704  m_PS->GetMaxPos().Y() = std::max(m_PS->GetMaxPos().Y(), n.pos.Y());
705 
706  // Parent index is index in new (force) array, not tree
707  // since tree may have collapsed nodes or unused nodes.
708  if (delta == 1) {
709  int pt_idx = (int) m_PS->GetNodes().size()-1;
710  m_ParentIdx.push(pt_idx);
711  }
712 
713  /// Add the edge from the current node to its parent
714  if (tnode.HasParent()) {
715  n.constrained = 1.0f;
716  CVect2<float> ppos(tree.GetParent(tnode)->XY());
717 
718  float len = (n.pos-ppos).Length();
719  m_PS->GetDefaultEdgeLen() += len;
720 
721  CPhyloTreePS::Edge e(m_ParentIdx.top(), static_cast<int>(m_PS->GetNodes().size()));
722  e.len = len;
723  e.rest_len_inv = 1.0f/100.0f;
724  m_PS->GetEdges().push_back(e);
725  }
726 
727  m_PS->GetNodes().push_back(n);
728  }
729  else if (delta == -1) {
730  m_ParentIdx.pop();
731  }
732  return eTreeTraverse;
733  }
734 
735 private:
737  stack<int> m_ParentIdx;
738 };
739 
741 {
742  CInitPSNodes draw_tree(this);
743  TreeDepthFirstEx(*tree, draw_tree);
744 }
745 
746 
static CAttribMenu & GetInstance()
Return a static instance of CAttribMenu.
Definition: attrib_menu.cpp:50
class CAttribMenuItem
CAttribFloatMenuItem * AddFloat(const std::string &name, float *user_value=NULL, float initial_value=0.5f, float min_value=0.0f, float max_value=1.0f, float stepsize=0.01f)
CAttribIntMenuItem * AddIntReadOnly(const std::string &name, int *user_value)
CAttribMenu * AddSubMenuUnique(const std::string &name, void *user_value=NULL)
Convienance function to add a submenu to this menu.
CAttribFloatMenuItem * AddFloatReadOnly(const std::string &name, float *user_value)
Add entries to the menu which display the users value but do not update it.
bool RemoveMenuR(const std::string &name, void *user_value=NULL)
Search the menu(s) recursively for menu 'name' with the specified user data 'user_value'.
CInitPSNodes(CPhyloTreePS *ps)
CPhyloTree::TTreeIdx TTreeIdx
stack< int > m_ParentIdx
ETreeTraverseCode operator()(CPhyloTree &tree, TTreeIdx node_idx, int delta)
CPhyloTreePS * m_PS
CPhyloTree * GetTree()
class CPhyloTreePS
float m_RepulsionDist2
Square of current effective repulsion distance.
float m_RepulsionInv_x_ElectricalRepulsion
Inverse of repulsion dist * electrical repulsion factor.
void Init(CPhyloTreeDataSource &ds)
void x_ApplyNeighborCellForces(std::vector< int > &cell_nodes, const CVect2< int > &adjacent_idx)
Called compute forces between nodes in 2 cells.
PhysicsParms m_PhysicsParmsSafe
Updated from m_PhysicsPamsVolatile when safe to do so.
float m_MaxVelocity
The maximum velocity is the maximum node velocity during the last call to UpdateAndSynch()
float m_edge_forces_t
For timer values.
float m_bound_update_safe_t
PhysicsParms m_PhysicsParmsVolatile
(potentially) updated from other thread(s)
int m_node_node_interactions_safe_t
std::vector< CVect2< int > > m_ValidateGrid
Only used for debugging.
float m_edge_forces_safe_t
bool m_IsDone
If true, system has slowed down to the point where continuing to update it is not necessary.
void x_Init(CPhyloTree *tree)
Create particle system from tree - ignore collapsed.
void x_ApplyRepulsiveForces()
Apply repulsive forces between all nodes.
CVect2< float > TVec
std::vector< Node > m_Nodes
Set of all nodes.
float m_DefaultEdgeLen
Default length for all edges in system.
TVec & GetMinPos()
Tracks bounding rectangle for all nodes.
float m_AdaptiveStep
Multiplier for m_PhysicsParmsSafe.m_Step to allow step size to be adaptively lowered if system appear...
float m_integrate_safe_t
float m_node_forces_safe_t
void Draw()
Visualize graph - debug rendering.
TVec m_MinPos
Tracks bounding rectangle for all nodes.
float m_LogDistMax
For debug-drawing.
TVec & GetMaxPos()
float m_bound_update_t
std::vector< Edge > m_Edges
Set of all edges.
void x_UpdateVoxels()
Update spatial subdivision of nodes.
int m_node_node_interactions_t
void x_ApplyRepulsiveForcesHashed()
Apply forces between nodes based on defined neighborhood size.
float & GetDefaultEdgeLen()
Default length for all edges in system.
std::vector< Node > & GetNodes()
Set of all nodes.
std::vector< Edge > & GetEdges()
Set of all edges.
void UpdateAndSynch()
Calculate forces, update positions, and update underlying tree.
void Update()
Calculate force then update positions.
float m_PrevMaxVelocity
Maximum velocity in previous update.
CSpatialHash2D< std::vector< int > > m_NodeGrid
Grid that keeps track of adjacent nodes.
CPhyloTree * m_Tree
Root node of tree.
void CalcForces()
Calculate forces for all nodes.
std::vector< CVect2< int > > m_ValidateNsq
Tree subclass also has functions and data needed for rendering and selection.
Definition: phylo_tree.hpp:52
void SetMin(TVeci &idx)
const TVeci & GetMin()
Get min/max indices for current (whole) grid.
const TVeci & GetMax()
TElemType & Get(const TVeci &item)
void SetMax(TVeci &idx)
int GetWidth() const
Get width/height of grid.
int GetHeight() const
CStopWatch –.
Definition: ncbitime.hpp:1937
bool HasParent() const
Check if the node has a parent.
Definition: tree_model.hpp:90
bool IsLeaf() const
Report whether this is a leaf node.
Definition: tree_model.hpp:121
static TTreeIdx Null()
Return the index value that represents a NULL node.
Definition: tree_model.hpp:678
#define T(s)
Definition: common.h:230
#define false
Definition: bool.h:36
int offset
Definition: replacements.h:160
#define NULL
Definition: ncbistd.hpp:225
#define _TRACE(message)
Definition: ncbidbg.hpp:122
float TVecType
Definition: vect2.hpp:50
const T * GetData() const
Definition: vect2.hpp:112
T & X()
Definition: vect2.hpp:107
T & Y()
Definition: vect2.hpp:109
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
double Restart(void)
Return time elapsed since first Start() or last Restart() call (in seconds).
Definition: ncbitime.hpp:2816
double Elapsed(void) const
Return time elapsed since first Start() or last Restart() call (in seconds).
Definition: ncbitime.hpp:2775
void Stop(void)
Suspend the timer.
Definition: ncbitime.hpp:2792
void Start(void)
Start the timer.
Definition: ncbitime.hpp:2764
ETreeTraverseCode
Tree traverse code returned by the traverse predicate function.
Definition: ncbi_tree.hpp:51
@ eTreeTraverse
Keep traversal.
Definition: ncbi_tree.hpp:52
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
static CStopWatch sw
const int infinity
Definition: nucprot.cpp:52
int i
if(yy_accept[yy_current_state])
yy_size_t n
int len
#define abs(a)
Definition: ncbi_heapmgr.c:130
The NCBI C++/STL use hints.
Defines: CTimeFormat - storage class for time format.
T max(T x_, T y_)
T min(T x_, T y_)
Int4 delta(size_t dimension_, const Int4 *score_)
void TreeDepthFirstEx(TTreeModel &tree_model, typename TTreeModel::TTreeIdx node_idx, Fun &func)
Depth-first tree traversal that skips collapsed nodes.
Definition: phylo_tree.hpp:429
bool isFinite(T arg)
#define FLT_EPSILON
Definition: stdtypes.cpp:214
Data structure for an edge between two nodes.
Data structure for a node in the particle system.
float m_VelocityThresholdK
factor to scale final velocity threshold
Modified on Mon Jul 22 05:00:27 2024 by modify_doxy.py rev. 669887