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

Go to the SVN repository for this file.

1 /* $Id: phylo_tree_boundary_shapes.cpp 42852 2019-04-19 20:43:49Z katargir $
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  *
30  */
31 
32 #include <ncbi_pch.hpp>
34 #include <gui/opengl.h>
35 
36 #include <cmath>
37 
39 
40 
41 /*********************** IBoundaryShape **************************************/
42 
43 IBoundaryShape* IBoundaryShape::CreateBoundary(const string& boundary_type)
44 {
45  IBoundaryShape* shape = NULL;
46 
47  if (boundary_type == "Rectangle") {
48  shape = new CBoundaryShapeRect();
49  }
50  else if (boundary_type == "RoundedRectangle") {
51  shape = new CBoundaryShapeRoundedRect();
52  }
53  else if (boundary_type == "Triangle") {
54  shape = new CBoundaryShapeTri();
55  }
56  else if (boundary_type == "Ellipse") {
57  shape = new BoundaryShapeEllipse();
58  }
59 
60  return shape;
61 }
62 
64  float alpha_mod,
65  bool include_labels)
66 {
67  if (m_Hidden)
68  return;
69 
70  // Needed when view is scaled (not necessarily every time)
71  ComputeShapeWithLabels(scale, include_labels);
72 
73  glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
74  glEnable(GL_BLEND);
75  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
77  c.SetAlpha(c.GetAlpha()*alpha_mod);
78  glColor4fv(c.GetColorArray());
79 
80  vector<CVect2<float> > verts;
81  x_GetTris(verts, scale);
82 
83  glBegin(GL_TRIANGLES);
84  {
85  for (size_t i=0; i<verts.size(); i+=3) {
86  glVertex2fv(verts[i].GetData());
87  glVertex2fv(verts[i+1].GetData());
88  glVertex2fv(verts[i+2].GetData());
89  }
90  }
91  glEnd();
92 
93  //Draw the border around polygons as a line
95  glLineWidth(m_Parms.GetBorderWidth());
97  c.SetAlpha(c.GetAlpha()*alpha_mod);
98  glColor4fv(c.GetColorArray());
99 
100  verts.clear();
101  x_GetEdges(verts, scale);
102 
103  glBegin(GL_LINES);
104  {
105  for (size_t i=0; i<verts.size(); i+=2) {
106  glVertex2fv(verts[i].GetData());
107  glVertex2fv(verts[i+1].GetData());
108  }
109  }
110  glEnd();
111  }
112 
113  glDisable(GL_BLEND);
114 }
115 
117  CRef<CGlVboNode>& edge_node,
118  const CVect2<float>& scale,
119  float alpha_mod,
120  bool include_labels)
121 {
122  if (m_Hidden)
123  return;
124 
125  // Needed when view is scaled (not necessarily every time)
126  ComputeShapeWithLabels(scale, include_labels);
127 
128  //tri_node.Reset(new CGlVboNode(GL_TRIANGLES));
130  c.SetAlpha(c.GetAlpha()*alpha_mod);
131 
132  tri_node->GetState().ColorC(c);
133  tri_node->GetState().Enable(GL_BLEND);
134  tri_node->GetState().BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
135  tri_node->GetState().PolygonMode(GL_FRONT_AND_BACK, GL_FILL);
136 
137  vector<CVect2<float> > verts;
138  x_GetTris(verts, scale);
139 
140  // Get bounding rectangle for boundary area.
142  m_Extent.Init(tmax, tmax, -tmax, -tmax);
143 
144  for (size_t i = 0; i < verts.size(); ++i) {
145  TModelUnit x = (TModelUnit)verts[i].X();
146  TModelUnit y = (TModelUnit)verts[i].Y();
147 
152  }
153  tri_node->SetVertexBuffer2D(verts);
154 
155 
156  //Draw the border around the outside of the object (if border is given)
159  c.SetAlpha(c.GetAlpha()*alpha_mod);
160 
161  verts.clear();
162  x_GetEdges(verts, scale);
163 
164  //edge_node.Reset(new CGlVboNode(GL_LINES));
165  edge_node->GetState().ColorC(c);
166  edge_node->GetState().Enable(GL_BLEND);
167  edge_node->GetState().BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
168  edge_node->GetState().LineWidth(m_Parms.GetBorderWidth());
171 
172  edge_node->SetVertexBuffer2D(verts);
173  }
174 }
175 
176 /*********************** CBoundaryShapeRectBase **********************************/
177 
179 : m_PixelDeltaNegX(0.0f)
180 , m_PixelDeltaNegY(0.0f)
181 , m_PixelDeltaPosX(0.0f)
182 , m_PixelDeltaPosY(0.0f)
183 {
184  for (size_t i=0; i<4; ++i)
185  m_Points[i] = 0.0f;
186 }
187 
189  const CVect2<float>& /* base_node_pos */,
190  const std::vector<CVect2<float> >& pts,
191  const vector<std::pair<CVect2<float>, CGlRect<float> > >& pixel_pts)
192 {
193  float minx = 1e10f;
194  float miny = 1e10f;
195  float maxx = -1e10f;
196  float maxy = -1e10f;
197 
198  for (size_t i=0; i<pts.size(); ++i) {
199  minx = std::min(minx, pts[i].X());
200  maxx = std::max(maxx, pts[i].X());
201  miny = std::min(miny, pts[i].Y());
202  maxy = std::max(maxy, pts[i].Y());
203  }
204 
205  if (m_Parms.GetIncludeTextArea()) {
206  for (size_t i=0; i<pixel_pts.size(); ++i) {
207  minx = std::min(minx, pixel_pts[i].first.X());
208  maxx = std::max(maxx, pixel_pts[i].first.X());
209  miny = std::min(miny, pixel_pts[i].first.Y());
210  maxy = std::max(maxy, pixel_pts[i].first.Y());
211  }
212  }
213 
214  m_Points[0].X() = minx;
215  m_Points[0].Y() = miny;
216 
217  m_Points[1].X() = maxx;
218  m_Points[1].Y() = miny;
219 
220  m_Points[2].X() = maxx;
221  m_Points[2].Y() = maxy;
222 
223  m_Points[3].X() = minx;
224  m_Points[3].Y() = maxy;
225 
226  m_PixelPoints = pixel_pts;
227 }
228 
230  bool labels_visible)
231 {
232  // This function is needed because when the view scales, text fields
233  // move to a new position(translate) but do not scale. This means
234  // that the size of the bounding area cannot simply be scaled by the
235  // same amount as the underlying tree.
236 
237  // Recompute the size of the boudary taking into account the extent
238  // of text fields associated with specific nodes (positions) in the tree.
239  // The contribution of these fields is saved in the m_PixelDelta* vars.
240  m_PixelDeltaNegX = 0.0f;
241  m_PixelDeltaNegY = 0.0f;
242  m_PixelDeltaPosX = 0.0f;
243  m_PixelDeltaPosY = 0.0f;
244 
245  if (!labels_visible)
246  return;
247 
248  float sx = scale.X();
249  float sy = scale.Y();
250 
251  // Iterate over the node points and their associated text
252  // rectangles. Node positions are in normal (scaled) coordinates
253  // and text field dimensions are in absolute (pixel) coordinates.
254  for (size_t i=0; i<m_PixelPoints.size(); ++i) {
255  // a position in model coordinates:
256  CVect2<float> base_pos = m_PixelPoints[i].first;
257  // area of rectangle for the text field (in pixels)
258  CGlRect<float> pix_rect = m_PixelPoints[i].second;
259 
260  // For each of the 4 corners of the text field rectangle, determine
261  // if it outside the bounds of the current boundary and if so save
262  // that (scaled) amount in m_PixelDeltaNeg*
263  float negx = 1e10f;
264  float negy = 1e10f;
265  float posx = -1e10f;
266  float posy = -1e10f;
267 
268  for (int i=0; i<4; ++i) {
269  CGlPoint<float> pix_pos(pix_rect.GetCorner(i));
270 
271  negx = std::min(negx, pix_pos.X());
272  posx = std::max(posx, pix_pos.X());
273  negy = std::min(negy, pix_pos.Y());
274  posy = std::max(posy, pix_pos.Y());
275  }
276 
277  m_PixelDeltaNegX = std::max(m_PixelDeltaNegX, m_Points[0].X() - base_pos.X() - negx*sx );
278  m_PixelDeltaNegY = std::max(m_PixelDeltaNegY, m_Points[0].Y() - base_pos.Y() - negy*sy);
279  m_PixelDeltaPosX = std::max(m_PixelDeltaPosX, base_pos.X() + posx*sx - m_Points[2].X());
280  m_PixelDeltaPosY = std::max(m_PixelDeltaPosY, base_pos.Y() + posy*sy - m_Points[2].Y());
281  }
282 }
283 
284 /*********************** CBoundaryShapeRect **********************************/
285 
287  const CVect2<float>& scale)
288 {
289  float border_neg_x = m_PixelDeltaNegX + scale.X()*(m_Parms.GetBorderWidth());
290  float border_neg_y = m_PixelDeltaNegY + scale.Y()*(m_Parms.GetBorderWidth());
291  float border_pos_x = m_PixelDeltaPosX + scale.X()*(m_Parms.GetBorderWidth());
292  float border_pos_y = m_PixelDeltaPosY + scale.Y()*(m_Parms.GetBorderWidth());
293 
294  tris.push_back(CVect2<float>(m_Points[0].X() - border_neg_x,
295  m_Points[0].Y() - border_neg_y));
296  tris.push_back(CVect2<float>(m_Points[1].X() + border_pos_x,
297  m_Points[1].Y() - border_neg_y));
298  tris.push_back(CVect2<float>(m_Points[3].X() - border_neg_x,
299  m_Points[3].Y() + border_pos_y));
300 
301  tris.push_back(CVect2<float>(m_Points[1].X() + border_pos_x,
302  m_Points[1].Y() - border_neg_y));
303  tris.push_back(CVect2<float>(m_Points[2].X() + border_pos_x,
304  m_Points[2].Y() + border_pos_y));
305  tris.push_back(CVect2<float>(m_Points[3].X() - border_neg_x,
306  m_Points[3].Y() + border_pos_y));
307 }
308 
310  const CVect2<float>& scale)
311 {
312  //Draw the border around the outside of the object (if border is given)
314  float border_neg_x = m_PixelDeltaNegX + scale.X()*(m_Parms.GetBorderWidth() + 1);
315  float border_neg_y = m_PixelDeltaNegY + scale.Y()*(m_Parms.GetBorderWidth() + 1);
316  float border_pos_x = m_PixelDeltaPosX + scale.X()*(m_Parms.GetBorderWidth() + 1);
317  float border_pos_y = m_PixelDeltaPosY + scale.Y()*(m_Parms.GetBorderWidth() + 1);
318 
319  edges.push_back(CVect2<float>(m_Points[0].X() - border_neg_x,
320  m_Points[0].Y() - border_neg_y));
321  edges.push_back(CVect2<float>(m_Points[1].X() + border_pos_x,
322  m_Points[1].Y() - border_neg_y));
323 
324  edges.push_back(CVect2<float>(m_Points[1].X() + border_pos_x,
325  m_Points[1].Y() - border_neg_y));
326  edges.push_back(CVect2<float>(m_Points[2].X() + border_pos_x,
327  m_Points[2].Y() + border_pos_y));
328 
329  edges.push_back(CVect2<float>(m_Points[2].X() + border_pos_x,
330  m_Points[2].Y() + border_pos_y));
331  edges.push_back(CVect2<float>(m_Points[3].X() - border_neg_x,
332  m_Points[3].Y() + border_pos_y));
333 
334  edges.push_back(CVect2<float>(m_Points[3].X() - border_neg_x,
335  m_Points[3].Y() + border_pos_y));
336  edges.push_back(CVect2<float>(m_Points[0].X() - border_neg_x,
337  m_Points[0].Y() - border_neg_y));
338  }
339 }
340 
341 
342 /*********************** CBoundaryShapeRoundedRect ***************************/
343 
345  const CVect2<float>& pos,
346  float corner_width_x,
347  float corner_width_y,
348  float start_angle)
349 {
350  float tri_count = 10.0f;
351  float delta = (3.1415926535f/2.0f)/tri_count;
352  float angle = start_angle;
353  CVect2<float> prev_pt, pt;
354 
355  for(int i =0; i<=tri_count; i++){
356  prev_pt = pt;
357  pt.Set(pos.X() + corner_width_x*cosf(angle),
358  pos.Y() + corner_width_y*sinf(angle));
359 
360  if (i>0) {
361  tris.push_back(pos);
362  tris.push_back(prev_pt);
363  tris.push_back(pt);
364  }
365  angle += delta;
366  }
367 }
368 
370  const CVect2<float>& pos,
371  float corner_width_x,
372  float corner_width_y,
373  float start_angle)
374 {
375  float tri_count = 10.0f;
376  float delta = (3.1415926535f/2.0f)/tri_count;
377  float angle = start_angle;
378  CVect2<float> prev_pt, pt;
379 
380  for(int i =0; i<=tri_count; i++){
381  prev_pt = pt;
382  pt.Set(pos.X() + corner_width_x*cosf(angle),
383  pos.Y() + corner_width_y*sinf(angle));
384 
385  if (i>0) {
386  edges.push_back(prev_pt);
387  edges.push_back(pt);
388  }
389  angle += delta;
390  }
391 }
392 
393 
395  const CVect2<float>& scale)
396 {
397  // If border is not equal to at least the corner size, then elements may
398  // wind up outside the bounded area.
399  float border_width = std::max(m_Parms.GetBorderWidth(), m_Parms.GetCornerWidth());
400 
401  float border_neg_x = m_PixelDeltaNegX + scale.X()*(border_width);
402  float border_neg_y = m_PixelDeltaNegY + scale.Y()*(border_width);
403  float border_pos_x = m_PixelDeltaPosX + scale.X()*(border_width);
404  float border_pos_y = m_PixelDeltaPosY + scale.Y()*(border_width);
405 
406  float corner_width_x = scale.X()*m_Parms.GetCornerWidth();
407  float corner_width_y = scale.Y()*m_Parms.GetCornerWidth();
408 
409  // Maximum size for the rounded corners is 1/2 distance in x or y direction
410  // otherwise we get overlap (which looks bad)
411  // Get min dimension (x or y)
412  float xmin = std::min(m_Points[0].X(), m_Points[2].X()) - border_neg_x;
413  float xmax = std::max(m_Points[0].X(), m_Points[2].X()) + border_pos_x;
414  float ymin = std::min(m_Points[0].Y(), m_Points[2].Y()) - border_neg_y;
415  float ymax = std::max(m_Points[0].Y(), m_Points[2].Y()) + border_pos_y;
416 
417  float xw = xmax-xmin;
418  float yw = ymax-ymin;
419 
420  if (corner_width_x * 2.0f > xw)
421  corner_width_x = xw*0.5f;
422  if (corner_width_y * 2.0f > yw)
423  corner_width_y = yw*0.5f;
424 
425 
426  /* draw rounded rectangle in 7 parts: 3 rectangles and 4 corners
427  *
428  * /-----------------------\
429  * /4 | |7 \
430  * |---| 1. |---|
431  * |_2_| |3__|
432  * \5 | |6 /
433  * \-----------------------/
434  */
435 
436  // First quad (two tris, lower left and upper right)
437  tris.push_back(CVect2<float>(xmin + corner_width_x, ymin));
438  tris.push_back(CVect2<float>(xmax - corner_width_x, ymin));
439  tris.push_back(CVect2<float>(xmax - corner_width_x, ymax));
440 
441  tris.push_back(CVect2<float>(xmax - corner_width_x, ymax));
442  tris.push_back(CVect2<float>(xmin + corner_width_x, ymax));
443  tris.push_back(CVect2<float>(xmin + corner_width_x, ymin));
444 
445  // Second quad (as two tris)
446  tris.push_back(CVect2<float>(xmin, ymin + corner_width_y));
447  tris.push_back(CVect2<float>(xmin + corner_width_x, ymin + corner_width_y));
448  tris.push_back(CVect2<float>(xmin + corner_width_x, ymax - corner_width_y));
449 
450  tris.push_back(CVect2<float>(xmin + corner_width_x, ymax - corner_width_y));
451  tris.push_back(CVect2<float>(xmin, ymax - corner_width_y));
452  tris.push_back(CVect2<float>(xmin, ymin + corner_width_y));
453 
454  // third quad (as two tris)
455  tris.push_back(CVect2<float>(xmax - corner_width_x, ymin + corner_width_y));
456  tris.push_back(CVect2<float>(xmax, ymin + corner_width_y));
457  tris.push_back(CVect2<float>(xmax, ymax - corner_width_y));
458 
459  tris.push_back(CVect2<float>(xmax, ymax - corner_width_y));
460  tris.push_back(CVect2<float>(xmax - corner_width_x, ymax - corner_width_y));
461  tris.push_back(CVect2<float>(xmax - corner_width_x, ymin + corner_width_y));
462 
463 
464  float pi = 3.14159265358979f;
465 
466  CVect2<float> pos(xmin + corner_width_x, ymin + corner_width_y);
467  x_GetRoudedCornerTris(tris, pos, corner_width_x, corner_width_y, pi);
468 
469  pos.X() = xmax - corner_width_x;
470  x_GetRoudedCornerTris(tris, pos, corner_width_x, corner_width_y, (3.0f*pi)/2.0f);
471 
472  pos.Y() = ymax - corner_width_y;
473  x_GetRoudedCornerTris(tris, pos, corner_width_x, corner_width_y, 0.0f);
474 
475  pos.X() = xmin + corner_width_x;
476  x_GetRoudedCornerTris(tris, pos, corner_width_x, corner_width_y, pi/2.0f);
477 }
478 
480  const CVect2<float>& scale)
481 {
482  // If border is not equal to at least the corner size, then elements may
483  // wind up outside the bounded area.
484  float border_width = std::max(m_Parms.GetBorderWidth(), m_Parms.GetCornerWidth());
485 
486  float border_neg_x = m_PixelDeltaNegX + scale.X()*(border_width);
487  float border_neg_y = m_PixelDeltaNegY + scale.Y()*(border_width);
488  float border_pos_x = m_PixelDeltaPosX + scale.X()*(border_width);
489  float border_pos_y = m_PixelDeltaPosY + scale.Y()*(border_width);
490 
491  float corner_width_x = scale.X()*m_Parms.GetCornerWidth();
492  float corner_width_y = scale.Y()*m_Parms.GetCornerWidth();
493 
494  // Maximum size for the rounded corners is 1/2 distance in x or y direction
495  // otherwise we get overlap (which looks bad)
496  // Get min dimension (x or y)
497  float xmin = std::min(m_Points[0].X(), m_Points[2].X()) - border_neg_x;
498  float xmax = std::max(m_Points[0].X(), m_Points[2].X()) + border_pos_x;
499  float ymin = std::min(m_Points[0].Y(), m_Points[2].Y()) - border_neg_y;
500  float ymax = std::max(m_Points[0].Y(), m_Points[2].Y()) + border_pos_y;
501 
502  float xw = xmax-xmin;
503  float yw = ymax-ymin;
504 
505  if (corner_width_x * 2.0f > xw)
506  corner_width_x = xw*0.5f;
507  if (corner_width_y * 2.0f > yw)
508  corner_width_y = yw*0.5f;
509 
510 
511  /* draw rounded rectangle in 7 parts: 3 rectangles and 4 corners
512  *
513  * /-----------------------\
514  * /4 | |7 \
515  * |---| 1. |---|
516  * |_2_| |3__|
517  * \5 | |6 /
518  * \-----------------------/
519  */
520 
521  // First quad - top and bottom edges
522  edges.push_back(CVect2<float>(xmin + corner_width_x, ymin));
523  edges.push_back(CVect2<float>(xmax - corner_width_x, ymin));
524 
525  edges.push_back(CVect2<float>(xmax - corner_width_x, ymax));
526  edges.push_back(CVect2<float>(xmin + corner_width_x, ymax));
527 
528  // Second quad - left edge
529  edges.push_back(CVect2<float>(xmin , ymax - corner_width_y));
530  edges.push_back(CVect2<float>(xmin, ymin + corner_width_y));
531 
532  // third quad - right edge
533  edges.push_back(CVect2<float>(xmax, ymin + corner_width_y));
534  edges.push_back(CVect2<float>(xmax, ymax - corner_width_y));
535 
536  float pi = 3.14159265358979f;
537 
538  CVect2<float> pos(xmin + corner_width_x, ymin + corner_width_y);
539  x_GetRoudedCornerEdges(edges, pos, corner_width_x, corner_width_y, pi);
540 
541  pos.X() = xmax - corner_width_x;
542  x_GetRoudedCornerEdges(edges, pos, corner_width_x, corner_width_y, (3.0f*pi)/2.0f);
543 
544  pos.Y() = ymax - corner_width_y;
545  x_GetRoudedCornerEdges(edges, pos, corner_width_x, corner_width_y, 0.0f);
546 
547  pos.X() = xmin + corner_width_x;
548  x_GetRoudedCornerEdges(edges, pos, corner_width_x, corner_width_y, pi/2.0f);
549 }
550 
551 
552 /*********************** CBoundaryShapeTri ***********************************/
553 
555 {
556 }
557 
559  const CVect2<float>& base_node_pos,
560  const std::vector<CVect2<float> >& pts,
561  const vector<std::pair<CVect2<float>, CGlRect<float> > >& pixel_pts)
562 {
563  // Pixel points are the points that define text box areas
565  m_PixelPoints = pixel_pts;
566  }
567 
568  m_NodePoints = pts;
569  m_BaseNodePos = base_node_pos;
570 
571  // Remove the base (apex) node from the main set of nodes since it has a fixed position
572  // in the triangle and it can mess up the math (gets subtracted from itself and creates
573  // 0 length vector. Its probably the first node, but check all.
574  std::vector<CVect2<float> >::iterator iter;
575  for (iter=m_NodePoints.begin(); iter!=m_NodePoints.end(); ++iter) {
576  if ( ((*iter)-m_BaseNodePos).Length() < std::numeric_limits<float>::epsilon())
577  break;
578  }
579 
580  if (iter != m_NodePoints.end() )
581  m_NodePoints.erase(iter);
582 }
583 
585  const CVect2<float>& base_pos,
586  const CVect2<float>& dir,
587  const CVect2<float>& perp_dir,
588  float& max_len,
589  float& max_angle_top,
590  float& max_angle_bottom)
591 {
592  // Compute angle of all points from base line segment and save result in
593  // max_angle_top and max_angle_bottom. Top/bottom is relative to vector
594  // perpendicular to main direction of triangle (perp_dir)
595  for (size_t i=0; i<pts.size(); ++i) {
596  CVect2<float> pt_dir = pts[i] - base_pos;
597  float proj_len = pt_dir.Dot(dir);
598  max_len = std::max(max_len, proj_len);
599 
600  // If the offset from the base position is < 0, then some of the points
601  // are behind the apex of the triangle, and the shape won't work. Throw
602  // out nodes behind the triangle so we can show something (this could occur
603  // in physically-based graph layout)
604 
605  if (max_len > 0.0f) {
606  pt_dir.Normalize();
607  float cos_angle = pt_dir.Dot(dir);
608 
609  // clamp to -1.0 .. 1.0 to prevent numeric precision problems
610  cos_angle = cos_angle < -1.0f ? -1.0f : 1.0f < cos_angle ? 1.0f : cos_angle;
611 
612  float angle = acosf(cos_angle);
613  bool pos_angle = (perp_dir.Dot(pt_dir) > 0.0f);
614  if (pos_angle) {
615  max_angle_top = std::max(angle, max_angle_top);
616  max_angle_bottom = std::max(-angle, max_angle_bottom);
617  }
618  else {
619  max_angle_bottom = std::max(angle, max_angle_bottom);
620  max_angle_top = std::max(-angle, max_angle_top);
621  }
622  }
623  }
624 }
625 
628  const CVect2<float>& prev_pt_in,
629  const CVect2<float>& next_pt_in,
630  const CVect2<float>& scale,
631  CVect2<float>& pt_out1,
632  CVect2<float>& pt_out2)
633 {
634  CVect2<float> pdir;
635  CVect2<float> s1, s2;
636  float c, scale_modifier, theta;
637  float a = m_Parms.GetCornerWidth();
638 
639  // Get vectors going away from the vertex being 'rounded' (these are vectors to
640  // adjacent vertices).
641  s1 = prev_pt_in-pt_in;
642  float s1_len = s1.Length();
643  s1 /= s1_len;
644 
645  s2 = next_pt_in-pt_in;
646  float s2_len = s2.Length();
647  s2 /= s2_len;
648 
649  // Compute the angle as it appears in pixel coordinates (scaled) not using model
650  // coordinates which would be acos(s1.Dot(s2)).
651  CVect2<float> s1_scaled = CVect2<float>(s1.X()*1.0f/scale.X(), s1.Y()*1.0f/scale.Y());
652  CVect2<float> s2_scaled = CVect2<float>(s2.X()*1.0f/scale.X(), s2.Y()*1.0f/scale.Y());
653  s1_scaled.Normalize();
654  s2_scaled.Normalize();
655  theta = acos(s1_scaled.Dot(s2_scaled));
656 
657  RoundedCorner rc;
658 
659  // To round the corner, we find the two points where that same perpendicular
660  // segment of length 'a' will intersect the two vectors to neighboring
661  // vertices. The distance is based on the right triangle formed by
662  // the vector to the adjacent vertex, the line segemnt of length 'a'
663  // and the line bisecting the angle of length 'b'. So the distance
664  // to the intersection is 'c' from: sin(theta/2) = (a/2)/c
665  c = (a/2.0f)/sin(theta/2.0f);
666 
667  float scale_modifier1 = 1.0f/CVect2<float>(s1.X()/scale.X(), s1.Y()/scale.Y()).Length();
668  float scale_modifier2 = 1.0f/CVect2<float>(s2.X()/scale.X(), s2.Y()/scale.Y()).Length();
669 
670  if (c*scale_modifier1 > s1_len*0.5f)
671  c = (s1_len*0.5f)/scale_modifier1;
672  if (c*scale_modifier2 > s2_len*0.5f)
673  c = (s2_len*0.5f)/scale_modifier2;
674 
675  // Use c (scaled for pixel coordinates) to get intersection along the
676  // two vectors that make up the angle:
677  pt_out1 = pt_in + s1*c*scale_modifier1;
678  pt_out2 = pt_in + s2*c*scale_modifier2;
679 
680  // We need to find the center and radius of the circle which, when drawn,
681  // will create the rounded corner. This is the circle that is tangent to
682  // the interior of the angle at points pt_out1 and pt_out2, so the vector
683  // to the center of this circle goes through the midpoint of the line
684  // segment (pt_out1, pt_out2). The length of the vector OP where P is
685  // pt_in and O is the circle center is: cos(theta/2)=c/OP and radius
686  // is the other side of the triangle: sin(theta/2)=r/OP.
687  pdir = ((pt_out1+pt_out2)*0.5f)-pt_in;
688  float OP = c/cosf(theta/2.0f);
689  float r = sinf(theta/2)*OP;
690  pdir.Normalize();
691  scale_modifier = 1.0f/CVect2<float>(pdir.X()/scale.X(), pdir.Y()/scale.Y()).Length();
692 
693  rc.pos = pt_in + pdir*OP*scale_modifier;
694  rc.initial_vertex = pt_in;
695  rc.intersection1 = pt_out1;
696  rc.intersection2 = pt_out2;
697  rc.corner_width_x = scale.X()*r;
698  rc.corner_width_y = scale.Y()*r;
699 
700  return rc;
701 }
702 
703 
705  bool labels_visible)
706 {
707  // Get all text positions based on current scale factor
708  std::vector<CVect2<float> > text_pts;
709 
710  // Iterate over the node points and their associated text
711  // rectangles. Node positions are in normal (scaled) coordinates
712  // and text field dimensions are in absolute (pixel) coordinates.
713  size_t i;
714 
715  if (labels_visible) {
716  for (i = 0; i < m_PixelPoints.size(); ++i) {
717  // a position in model coordinates:
718  CVect2<float> base_pos = m_PixelPoints[i].first;
719  // area of rectangle for the text field (in pixels)
720  CGlRect<float> pix_rect = m_PixelPoints[i].second;
721 
722  for (int i = 0; i < 4; ++i) {
723  CGlPoint<float> pix_pos(pix_rect.GetCorner(i));
724  text_pts.push_back(CVect2<float>(base_pos.X() + pix_pos.X()*scale.X(),
725  base_pos.Y() + pix_pos.Y()*scale.Y()));
726  }
727  }
728  }
729 
730  // Shouldn't be called with an empty area
731  if (m_NodePoints.size() == 0 && text_pts.size() == 0)
732  return;
733 
734  //*************************************************************************
735  // Need to find main axis of triangle. If the the triangle is axis aligned
736  // use the centroid to pick the major axis direction. If not axis aligned,
737  // pick the axis to be the direction to the parent node (if direction to
738  // parent node is not defined, as is the case for the root node of the tree,
739  // also use the centroid).
740  //*************************************************************************
741  CVect2<float> axis_dir;
742  CVect2<float> centroid(0.0f);
745 
746  if (m_NodePoints.size() > 0) {
747  for (i=0; i<m_NodePoints.size(); ++i) {
748  centroid += m_NodePoints[i];
749  minpos.X() = std::min(minpos.X(), m_NodePoints[i].X());
750  minpos.Y() = std::min(minpos.Y(), m_NodePoints[i].Y());
751 
752  maxpos.X() = std::max(maxpos.X(), m_NodePoints[i].X());
753  maxpos.Y() = std::max(maxpos.Y(), m_NodePoints[i].Y());
754  }
755  }
756 
757  for (i=0; i<text_pts.size(); ++i) {
758  centroid += text_pts[i];
759  }
760 
761  centroid /= (float)(m_NodePoints.size() + text_pts.size());
762 
763  // Compute position of base line segment (non-horizontal case) as b1..b2
764  axis_dir = (centroid - m_BaseNodePos);
765  axis_dir.Normalize();
766 
767  // find bounding rectangle. main vertex is at (closest) to top/bottom/left or right
768  // and primary axis is in opposite direction
769 
770  // When there is only text the wrong axis may be picked.
771  if (m_Parms.GetAxisAligned() && m_NodePoints.size() > 0) {
772  // Make the primary axis of the triangle based on whether m_BaseNodePos
773  // is closer to the top, bottom, left or right side of the triangle.
774  float d1 = std::abs(m_BaseNodePos.X()-minpos.X());
775  float d2 = std::abs(m_BaseNodePos.X()-maxpos.X());
776  float d3 = std::abs(m_BaseNodePos.Y()-minpos.Y());
777  float d4 = std::abs(m_BaseNodePos.Y()-maxpos.Y());
778 
779  if (d1 < d2 && d1 < d3 && d1 < d4) {
780  axis_dir = CVect2<float>(1.0f, 0.0f);
781  }
782  else if (d2 < d3 && d2 < d4) {
783  axis_dir = CVect2<float>(-1.0f, 0.0f);
784  }
785  else if (d3 < d4) {
786  axis_dir = CVect2<float>(0.0f, 1.0f);
787  }
788  else {
789  axis_dir = CVect2<float>(0.0f, -1.0f);
790  }
791  }
792 
793  // Get a perpendicular vector that points in a counter-clockwise
794  // direction with respect to axis_dir. This is always true if
795  // we pick (-y,x).
796  CVect2<float> perp_dir(-axis_dir.Y(), axis_dir.X());
797 
798  CVect2<float> base_dir = axis_dir*m_Parms.GetTriOffset();
799  //float scale_modifier = 1.0f/CVect2<float>(base_dir.X()/scale.X(), base_dir.Y()/scale.Y()).Length();
800  CVect2<float> base_pos = m_BaseNodePos - base_dir;
801 
802 
803  // Compute angle of all points relative to the axis direction of the
804  // triangle and return the maximum values in max_angle_[top,bottom].
805  float max_len = -1e10f;
806  float max_angle_top = 0.0f;
807  float max_angle_bottom = 0.0f;
808 
809  if (!m_Parms.GetTextBox()) {
810  x_ComputeTriParms(text_pts,
811  base_pos,
812  axis_dir,
813  perp_dir,
814  max_len,
815  max_angle_top,
816  max_angle_bottom);
817  }
818 
820  base_pos,
821  axis_dir,
822  perp_dir,
823  max_len,
824  max_angle_top,
825  max_angle_bottom);
826 
827 
828  CVect2<float> p1, p2, p3;
829 
830  p1 = base_pos;
831  float a;
832 
833  if (m_Parms.GetAxisAligned() && m_NodePoints.size() > 0) {
834  float angle = std::max(max_angle_top, max_angle_bottom);
835 
836  a = max_len*tanf(angle);
837  p2 = base_pos + axis_dir*max_len - perp_dir*a;
838  p3 = base_pos + axis_dir*max_len + perp_dir*a;
839  }
840  else {
841  a = tanf(max_angle_bottom);
842  p2 = base_pos + axis_dir - perp_dir*a;
843 
844  a = tanf(max_angle_top);
845  p3 = base_pos + axis_dir + perp_dir*a;
846 
847  CVect2<float> v1 = p3-p1;
848  v1.Normalize();
849  CVect2<float> v2 = p2-p1;
850  v2.Normalize();
851 
852  CVect2<float> bisector = ((p1+v1) + (p1+v2))*0.5f - p1;
853  bisector.Normalize();
854 
855  max_len = 0.0f;
856  for (i=0; i<m_NodePoints.size(); ++i) {
857  CVect2<float> pt_dir = m_NodePoints[i] - p1;
858  float proj_len = pt_dir.Dot(bisector);
859  max_len = std::max(max_len, proj_len);
860  }
861 
862  if (m_Parms.GetIncludeTextArea() &&
863  !m_Parms.GetTextBox()) {
864 
865  for (i=0; i<text_pts.size(); ++i) {
866  CVect2<float> pt_dir = text_pts[i] - p1;
867  float proj_len = pt_dir.Dot(bisector);
868  max_len = std::max(max_len, proj_len);
869  }
870  }
871 
872  float c = max_len/v1.Dot(bisector);
873  p3 = p1 + v1*c;
874 
875  c = max_len/v2.Dot(bisector);
876  p2 = p1 + v2*c;
877  }
878 
879 
880  //*************************************************************************
881  // Expand triangle by border width
882  //*************************************************************************
883  // find tri center and translate
884  CVect2<float> tri_centroid = (p1 + p2 + p3)*0.3333f;
885  p1 -= tri_centroid;
886  p2 -= tri_centroid;
887  p3 -= tri_centroid;
888 
889  m_Center = tri_centroid;
890 
891  // Expand each vertex away from the center by 'border' PIXELS (scale
892  // each vector to convert distance to pixels)
893  CVect2<float> bdir;
894  float scaled_border;
895 
896  bdir = p1;
897  bdir.Normalize();
898  scaled_border = m_Parms.GetBorderWidth()/CVect2<float>(bdir.X()/scale.X(), bdir.Y()/scale.Y()).Length();
899  p1 += bdir*scaled_border;
900 
901  bdir = p2;
902  bdir.Normalize();
903  scaled_border = m_Parms.GetBorderWidth()/CVect2<float>(bdir.X()/scale.X(), bdir.Y()/scale.Y()).Length();
904  p2 += bdir*scaled_border;
905 
906  bdir = p3;
907  bdir.Normalize();
908  scaled_border = m_Parms.GetBorderWidth()/CVect2<float>(bdir.X()/scale.X(), bdir.Y()/scale.Y()).Length();
909  p3 += bdir*scaled_border;
910 
911  p1 += tri_centroid;
912  p2 += tri_centroid;
913  p3 += tri_centroid;
914 
915  //*************************************************************************
916  // Define rounded corners for triangle
917  // Corners will not appear rounded if m_Parms.GetCornerWidth() == 0,
918  // but we do the same processing either way since the duplicate
919  // points won't hurt.
920  //*************************************************************************
921  m_RoundedCorners.clear();
922  RoundedCorner rc;
923  CVect2<float> clipped_corner1, clipped_corner2;
924 
925  // If the text is not added, two quads will define bounding area, with each
926  // vertex split into 2 to that we can optionally have rounded corners.
927  if (!m_Parms.GetTextBox()) {
928  rc = x_ComputeRoundedCorner(p1, p3, p2, scale, clipped_corner1, clipped_corner2);
929  m_RoundedCorners.push_back(rc);
930  m_Rect1[0] = clipped_corner1;
931  m_Rect1[1] = clipped_corner2;
932 
933  rc = x_ComputeRoundedCorner(p2, p1, p3,
934  scale, clipped_corner1, clipped_corner2);
935  m_Rect1[2] = clipped_corner1;
936  m_Rect1[3] = clipped_corner2;
937  m_Rect2[0] = clipped_corner2;
938  m_RoundedCorners.push_back(rc);
939 
940  rc = x_ComputeRoundedCorner(p3, p2, p1,
941  scale, clipped_corner1, clipped_corner2);
942  m_RoundedCorners.push_back(rc);
943  m_Rect2[1] = clipped_corner1;
944  m_Rect2[2] = clipped_corner2;
945  m_Rect2[3] = m_Rect1[0];
946  }
947  else {
948  text_pts.push_back(p2);
949  text_pts.push_back(p3);
950 
951  float text_minx = 1e10f;
952  float text_miny = 1e10f;
953  float text_maxx = -1e10f;
954  float text_maxy = -1e10f;
955 
956  for (i=0; i<text_pts.size(); ++i) {
957  text_minx = std::min(text_minx, text_pts[i].X());
958  text_maxx = std::max(text_maxx, text_pts[i].X());
959  text_miny = std::min(text_miny, text_pts[i].Y());
960  text_maxy = std::max(text_maxy, text_pts[i].Y());
961  }
962 
963  float border_x = scale.X()*(m_Parms.GetBorderWidth());
964  float border_y = scale.Y()*(m_Parms.GetBorderWidth());
965 
966  text_minx -= border_x;
967  text_maxx += border_x;
968  text_miny -= border_y;
969  text_maxy += border_y;
970 
971  // Try to merge triangle corners (but not the parent nodes corner) with
972  // the text box corners that are closest. Will not work well for vertically
973  // oriented trees (should probably not include text in that case)
974  if (axis_dir.X() >= 0.0f) {
975  m_TextBox[0].X() = text_minx;
976  m_TextBox[0].Y() = text_miny;
977 
978  m_TextBox[1].X() = text_maxx;
979  m_TextBox[1].Y() = text_miny;
980 
981  m_TextBox[2].X() = text_maxx;
982  m_TextBox[2].Y() = text_maxy;
983 
984  m_TextBox[3].X() = text_minx;
985  m_TextBox[3].Y() = text_maxy;
986 
987  if (text_maxy > p3.Y())
988  p3.Y() = text_maxy;
989  else
990  text_maxy = p3.Y();
991 
992  if (text_miny < p2.Y())
993  p2.Y() = text_miny;
994  else
995  text_miny = p2.Y();
996 
997  m_TextBox[0].X() = p2.X();
998  m_TextBox[3].X() = p3.X();
999  }
1000  else {
1001  m_TextBox[0].X() = text_maxx;
1002  m_TextBox[0].Y() = text_maxy;
1003 
1004  m_TextBox[1].X() = text_minx;
1005  m_TextBox[1].Y() = text_maxy;
1006 
1007  m_TextBox[2].X() = text_minx;
1008  m_TextBox[2].Y() = text_miny;
1009 
1010  m_TextBox[3].X() = text_maxx;
1011  m_TextBox[3].Y() = text_miny;
1012 
1013  if (text_maxy > p2.Y())
1014  p2.Y() = text_maxy;
1015  else
1016  text_maxy = p2.Y();
1017 
1018  if (text_miny < p3.Y())
1019  p3.Y() = text_miny;
1020  else
1021  text_miny = p3.Y();
1022 
1023  m_TextBox[0].X() = p2.X();
1024  m_TextBox[3].X() = p3.X();
1025  }
1026 
1027  rc = x_ComputeRoundedCorner(p1, p3, p2, scale, clipped_corner1, clipped_corner2);
1028  m_Rect1[0] = clipped_corner1;
1029  m_Rect1[1] = clipped_corner2;
1030  m_Rect1[2] = p2;
1031  m_Rect1[3] = p3;
1032  m_RoundedCorners.push_back(rc);
1033 
1035  scale, clipped_corner1, clipped_corner2);
1036  m_Rect2[0] = p2;
1037  m_Rect2[1] = clipped_corner1;
1038  m_Rect2[2] = clipped_corner2;
1039  m_RoundedCorners.push_back(rc);
1040 
1042  scale, clipped_corner1, clipped_corner2);
1043  m_Rect2[3] = clipped_corner1;
1044  m_Rect3[0] = clipped_corner1;
1045  m_Rect3[1] = clipped_corner2;
1046  m_Rect3[2] = p3;
1047  m_Rect3[3] = p2;
1048  m_RoundedCorners.push_back(rc);
1049  }
1050 
1051  // Compute the center and area of the shape, including text box if
1052  // applicable. This information is used to scale the shape when
1053  // drawing the (optional) border
1054  float minx = 1e10f;
1055  float miny = 1e10f;
1056  float maxx = -1e10f;
1057  float maxy = -1e10f;
1058 
1059  for (int idx=0; idx<4; ++idx) {
1060  minx = std::min(minx, m_Rect1[idx].X());
1061  minx = std::min(minx, m_Rect2[idx].X());
1062  maxx = std::max(maxx, m_Rect1[idx].X());
1063  maxx = std::max(maxx, m_Rect2[idx].X());
1064 
1065  miny = std::min(miny, m_Rect1[idx].Y());
1066  miny = std::min(miny, m_Rect2[idx].Y());
1067  maxy = std::max(maxy, m_Rect1[idx].Y());
1068  maxy = std::max(maxy, m_Rect2[idx].Y());
1069 
1070  if (m_Parms.GetTextBox()) {
1071  minx = std::min(minx, m_Rect3[idx].X());
1072  maxx = std::max(maxx, m_Rect3[idx].X());
1073 
1074  miny = std::min(miny, m_Rect3[idx].Y());
1075  maxy = std::max(maxy, m_Rect3[idx].Y());
1076  }
1077  }
1078  m_Center.X() = (maxx + minx)/2.0f;
1079  m_Center.Y() = (maxy + miny)/2.0f;
1080  m_Width = maxx-minx;
1081  m_Height = maxy-miny;
1082 
1083 }
1084 
1085 
1086 
1088  const CVect2<float>& scale)
1089 {
1090  // Front quad with clipped front tri if we have a text box.
1091  // If not, this quad has the 4 vertices formed by the clipped
1092  // polygon tip and clipped lower corner with top of front
1093  // clip being first vertex.
1094  // /|
1095  // | |
1096  // \|
1097  tris.push_back(CVect2<float>(m_Rect1[0].X(), m_Rect1[0].Y()));
1098  tris.push_back(CVect2<float>(m_Rect1[1].X(), m_Rect1[1].Y()));
1099  tris.push_back(CVect2<float>(m_Rect1[2].X(), m_Rect1[2].Y()));
1100 
1101  tris.push_back(CVect2<float>(m_Rect1[2].X(), m_Rect1[2].Y()));
1102  tris.push_back(CVect2<float>(m_Rect1[3].X(), m_Rect1[3].Y()));
1103  tris.push_back(CVect2<float>(m_Rect1[0].X(), m_Rect1[0].Y()));
1104 
1105  // With a text box, this is the the lower right
1106  // triangle (with lower right corner clipped to
1107  // make it a quad) of the text box.
1108  // without a text box it is the upper (large) quad
1109  // of the main clipped triangle (3 clips make 6 vertices)
1110  tris.push_back(CVect2<float>(m_Rect2[0].X(), m_Rect2[0].Y()));
1111  tris.push_back(CVect2<float>(m_Rect2[1].X(), m_Rect2[1].Y()));
1112  tris.push_back(CVect2<float>(m_Rect2[2].X(), m_Rect2[2].Y()));
1113 
1114  tris.push_back(CVect2<float>(m_Rect2[2].X(), m_Rect2[2].Y()));
1115  tris.push_back(CVect2<float>(m_Rect2[3].X(), m_Rect2[3].Y()));
1116  tris.push_back(CVect2<float>(m_Rect2[0].X(), m_Rect2[0].Y()));
1117 
1118  // This is the upper left 'triangle' of the text box. Acutally
1119  // a quad because the included upper right corner is clipped
1120  if (m_Parms.GetTextBox()) {
1121  tris.push_back(CVect2<float>(m_Rect3[0].X(), m_Rect3[0].Y()));
1122  tris.push_back(CVect2<float>(m_Rect3[1].X(), m_Rect3[1].Y()));
1123  tris.push_back(CVect2<float>(m_Rect3[2].X(), m_Rect3[2].Y()));
1124 
1125  tris.push_back(CVect2<float>(m_Rect3[2].X(), m_Rect3[2].Y()));
1126  tris.push_back(CVect2<float>(m_Rect3[3].X(), m_Rect3[3].Y()));
1127  tris.push_back(CVect2<float>(m_Rect3[0].X(), m_Rect3[0].Y()));
1128  }
1129 
1130  // If corners not rounded, return.
1131  if (m_Parms.GetCornerWidth() == 0.0f)
1132  return;
1133 
1134  // Draw the rounded corners. If there is a text box,
1135  // two corners are the back of the text box.
1136  for (size_t i=0; i<m_RoundedCorners.size(); ++i) {
1138 
1139  vector<CVect2<float> > arc;
1140  x_GetArc(c, scale, arc);
1141 
1142  CVect2<float> base((c.intersection1+c.intersection2)*0.5f);
1143 
1144  // arc returns edge pairs usable as GL_LINES
1145  for (size_t i=0; i<arc.size(); i+=2) {
1146  tris.push_back(base);
1147  tris.push_back(arc[i]);
1148  tris.push_back(arc[i+1]);
1149  }
1150  }
1151 }
1152 
1154  const CVect2<float>& scale)
1155 {
1156  // Front quad with clipped front tri if we have a text box.
1157  // If not, this quad has the 4 vertices formed by the clipped
1158  // polygon tip and clipped lower corner with top of front
1159  // clip being first vertex.
1160  // /|
1161  // | |
1162  // \|
1163  if (m_Parms.GetTextBox()) {
1164  edges.push_back(m_Rect1[1]);
1165  edges.push_back(m_Rect1[2]);
1166  edges.push_back(m_Rect1[3]);
1167  edges.push_back(m_Rect1[0]);
1168  }
1169  else {
1170  edges.push_back(m_Rect1[1]);
1171  edges.push_back(m_Rect1[2]);
1172  }
1173 
1174 
1175  // With a text box, this is the the lower right
1176  // triangle (with lower right corner clipped to
1177  // make it a quad) of the text box.
1178  // without a text box it is the upper (large) quad
1179  // of the main clipped triangle (3 clips make 6 vertices)
1180  if (m_Parms.GetTextBox()) {
1181  edges.push_back(m_Rect2[0]);
1182  edges.push_back(m_Rect2[1]);
1183 
1184  edges.push_back(m_Rect2[2]);
1185  edges.push_back(m_Rect2[3]);
1186  }
1187  else {
1188  edges.push_back(m_Rect2[0]);
1189  edges.push_back(m_Rect2[1]);
1190 
1191  edges.push_back(m_Rect2[2]);
1192  edges.push_back(m_Rect2[3]);
1193  }
1194 
1195  // This is the upper left 'triangle' of the text box. Acutally
1196  // a quad because the included upper right corner is clipped
1197  if (m_Parms.GetTextBox()) {
1198  edges.push_back(m_Rect3[1]);
1199  edges.push_back(m_Rect3[2]);
1200  }
1201 
1202  // If corners not rounded, return.
1203  if (m_Parms.GetCornerWidth() == 0.0f)
1204  return;
1205 
1206  // Draw Lines around the rounded corners
1207  for (size_t i=0; i<m_RoundedCorners.size(); ++i) {
1208  x_GetArc(m_RoundedCorners[i], scale, edges);
1209  }
1210 }
1211 
1213  const CVect2<float>& scale,
1214  vector<CVect2<float> >& edges)
1215 {
1216  vector<CVect2<float> > arc;
1217 
1218  float corner_x = c.pos.X();
1219  float corner_y = c.pos.Y();
1220 
1223 
1224  // Get directions to start and stop of arc
1225  CVect2<float> dir0 = (c.intersection1-c.pos);
1226  CVect2<float> dir1 = (c.intersection2-c.pos);
1227  dir0.X() /= scale.X();
1228  dir0.Y() /= scale.Y();
1229  dir1.X() /= scale.X();
1230  dir1.Y() /= scale.Y();
1231 
1232  dir0.Normalize();
1233  dir1.Normalize();
1234 
1235  // Get angles for start and stop of arc, and put those angles
1236  // in order so that a1>a0
1237  float a0 = atan2f(dir0.Y(), dir0.X());
1238  if (a0 < 0.0f)
1239  a0 = 2.0f*3.14159f + a0;
1240  float a1 = atan2f(dir1.Y(), dir1.X());
1241  if (a1 < 0.0f)
1242  a1 = 2.0f*3.14159f + a1;
1243 
1244  if (a0 > a1) {
1245  std::swap(a0, a1);
1246  std::swap(p0, p1);
1247  }
1248 
1249  // special case if a0/a1 cross 0-boundary (all angles here
1250  // will be < 180). Add 2pi to a0 and swap a1, a0.
1251  if (a1-a0 > 3.14149f) {
1252  a0 += 2.0f*3.14159f;
1253  std::swap(a0, a1);
1254  std::swap(p0, p1);
1255  }
1256 
1257  int vert_count = 10;
1258  float delta = (a1-a0)/(float)vert_count;
1259  float angle = a0;
1260 
1261  // Add arc. Push back vertices in pairs so they
1262  // can be drawn as GL_LINEs
1263  CVect2<float> prev_vert;
1264 
1265  for(int i=0; i<=vert_count; i++){
1266  if (i==0) {
1267  prev_vert = p0;
1268  }
1269  else if (i==vert_count) {
1270  edges.push_back(prev_vert);
1271  edges.push_back(p1);
1272  }
1273  else {
1274  edges.push_back(prev_vert);
1275  edges.push_back(CVect2<float>(corner_x + c.corner_width_x*cosf(angle),
1276  corner_y + c.corner_width_y*sinf(angle)));
1277  prev_vert = edges[edges.size()-1];
1278  }
1279  angle += delta;
1280  }
1281 }
1282 
1283 /*********************** CBoundaryPoints ***********************************/
1285 {
1286  m_GraphPoints.push_back(pt);
1287 }
1288 
1290  const CGlRect<float>& offset)
1291 {
1292  m_PixelPoints.push_back(std::pair<CVect2<float>, CGlRect<float> >(pt, offset));
1293 }
1294 
1296 {
1297  m_GraphPoints.insert(m_GraphPoints.begin(),
1298  pts.m_GraphPoints.begin(),
1299  pts.m_GraphPoints.end());
1300  m_PixelPoints.insert(m_PixelPoints.begin(),
1301  pts.m_PixelPoints.begin(),
1302  pts.m_PixelPoints.end());
1303 
1304 
1305  pts.ClearBoundedPoints();
1306 }
1307 
1309 {
1310  m_GraphPoints.clear();
1311  m_PixelPoints.clear();
1312 }
1313 
1314 /*********************** CSubtreeBoundary ***********************************/
1316 {
1317 }
1318 
1319 
1321  float alpha_mod,
1322  bool include_labels)
1323 {
1324  if (!m_BoundaryShape.Empty())
1325  m_BoundaryShape->Render(scale, alpha_mod, include_labels);
1326 }
1327 
1329  float alpha_mod,
1330  bool include_labels)
1331 {
1332  if (!m_BoundaryShape.Empty() &&
1333  (m_LastScale - scale).Length2() > FLT_EPSILON) {
1334 
1335  m_LastScale = scale;
1336  if (m_BoundaryTris.IsNull()) {
1337  m_BoundaryTris.Reset(new CGlVboNode(GL_TRIANGLES));
1338  m_BoundaryTris->GetState().Enable(GL_BLEND);
1339  m_BoundaryTris->GetState().BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1340  }
1341  if (m_BoundaryEdges.IsNull()) {
1342  m_BoundaryEdges.Reset(new CGlVboNode(GL_LINES));
1343  m_BoundaryEdges->GetState().Enable(GL_BLEND);
1344  m_BoundaryEdges->GetState().BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1345  }
1346 
1347  m_BoundaryShape->RenderVbo(m_BoundaryTris, m_BoundaryEdges, scale, alpha_mod, include_labels);
1348  }
1349 }
1350 
1352 {
1355 }
1356 
1358  const CVect2<float>& scale,
1359  const CVect2<float>& base_node_pos,
1360  const string& layout_type)
1361 {
1362  // This will force a redraw of the shape
1363  m_LastScale.Set(0.0f, 0.0f);
1364 
1365  if (m_Shapes.find(layout_type) != m_Shapes.end())
1366  m_BoundaryShape = m_Shapes[layout_type];
1367  else
1368  m_BoundaryShape = m_Shapes["Default"];
1369 
1370  if (!m_BoundaryShape.Empty()) {
1371  m_BoundaryShape->ComputeShape(scale,
1372  base_node_pos,
1373  boundary_pts.GetGraphPoints(),
1374  boundary_pts.GetPixelPoints());
1375  m_BoundaryShape->Hide(false);
1376  }
1377 }
1378 
1380 {
1381  if (!m_BoundaryShape.Empty()) {
1383  }
1384 }
1385 
1387 {
1388  if (!m_BoundaryShape.Empty()) {
1389  return (r.Intersects(m_BoundaryShape->GetExtent()));
1390  }
1391 
1392  return false;
1393 }
1394 
1395 string CSubtreeBoundary::x_GetParameter(const string& features, const string& parm)
1396 {
1397  string parm_lower = parm;
1398  parm_lower = NStr::ToLower(parm_lower) + "=";
1399 
1400  string features_lower = features;
1401  features_lower = NStr::ToLower(features_lower);
1402 
1403  size_t idx = features_lower.find(parm_lower);
1404  if (idx != string::npos) {
1405  size_t end_idx = features.find_first_of(" ,\t", idx);
1406  if (end_idx == string::npos)
1407  end_idx = features.size();
1408 
1409  return features.substr(idx + parm_lower.length(), end_idx-(idx+parm_lower.length()));
1410  }
1411 
1412  return "";
1413 }
1414 
1415 bool CSubtreeBoundary::x_GetColorParameter(const string& features,
1416  const string& parm,
1417  bool parm_required,
1418  CRgbaColor& c)
1419 {
1420  string parm_lower = parm;
1421  parm_lower = NStr::ToLower(parm_lower) + "=[";
1422 
1423  string features_lower = features;
1424  features_lower = NStr::ToLower(features_lower);
1425 
1426  string::size_type idx1 = string::npos;
1427 
1428  if (!parm_required) {
1429  if (features[0] == '[')
1430  idx1 = 0;
1431  else {
1432  idx1 = features.find(" [");
1433  if (idx1 != string::npos)
1434  idx1 += 2;
1435  }
1436  }
1437 
1438  if (idx1 == string::npos) {
1439  idx1 = features_lower.find(parm_lower);
1440  if (idx1 != string::npos) {
1441  idx1 += parm_lower.length();
1442  }
1443  }
1444 
1445  if (idx1 != string::npos) {
1446  string::size_type idx2 = features.find(']', idx1 + 2);
1447  if (idx2 != string::npos) {
1448  // There is a color array.
1449  string color_str = features.substr(idx1, idx2-idx1);
1450  c.FromString(color_str);
1451 
1452  // Was the alpha value provided? if not use default.
1453  // list<string> toks;
1454  // NStr::Split(color_str.substr(1, idx2-idx1-1), ", ", toks);
1455  // if (toks.size() < 4)
1456  // c.SetAlpha(0.25f);
1457 
1458  return true;
1459  }
1460  }
1461 
1462  return false;
1463 }
1464 
1465 
1467  const string& boundary_type,
1468  const string& layout_type)
1469 {
1470  if (boundary_type != "") {
1471  IBoundaryShape* s = IBoundaryShape::CreateBoundary(boundary_type);
1472  if (s != NULL) {
1473  s->SetBoundaryParms(parms);
1474  CRef<IBoundaryShape> sr(s);
1475  m_Shapes[layout_type] = sr;
1476  }
1477  }
1478 }
1479 
1480 
1482 {
1483  // Avoid unnecessary updates:
1484  if (m_BoundaryStr == features)
1485  return;
1486 
1487  m_BoundaryStr = features;
1488 
1489  CBoundaryParms parms;
1490 
1491  // default to red if color not provided
1492  parms.GetColor().Set(1.0f, 0.0f, 0.0f, 0.25f);
1493 
1494  // find color string in feature in form [...]
1495  // may be given without a name or as color=[...]
1496  string color_str;
1497 
1498  //string::size_type idx1 = features.find_first_of('[');
1499 
1500  // If there is a qualifier name of the form name=[..] and
1501  // the qualifier is "color=" then this is the color we want.
1502  // Also if there is no qualifier (no name=), then that is
1503  // the color we want.
1504  x_GetColorParameter(features, "Color", false, parms.GetColor());
1505 
1506  //
1507  // shape=RoundedRect CladogramShape=Rect RadialShape=Ellipse ForceShape=Triangle
1508  // Color=[128, 128, 128, 32]
1509  // Border=22
1510 
1511  m_Shapes.clear();
1512 
1513  string parm;
1514 
1515  parm = x_GetParameter(features, "Border");
1516  if (parm != "")
1518 
1519  parm = x_GetParameter(features, "Corner");
1520  if (parm != "")
1522 
1523  // valid values: true t yes y | false f no n
1524  try {
1525  parm = x_GetParameter(features, "DrawEdge");
1526  if (parm != "")
1528  }
1529  catch (CStringException&) {
1530  // just use default
1531  };
1532 
1533  x_GetColorParameter(features, "EdgeColor", true, parms.GetBoundaryEdgeColor());
1534 
1535  try {
1536  parm = x_GetParameter(features, "IncludeText");
1537  if (parm != "")
1539  }
1540  catch (CStringException&) {
1541  // just use default
1542  };
1543 
1544  try {
1545  parm = x_GetParameter(features, "AxisAligned");
1546  if (parm != "")
1547  parms.SetAxisAligned(NStr::StringToBool(parm));
1548  }
1549  catch (CStringException&) {
1550  // just use default
1551  };
1552 
1553  try {
1554  parm = x_GetParameter(features, "TextBox");
1555  if (parm != "")
1556  parms.SetTextBox(NStr::StringToBool(parm));
1557  }
1558  catch (CStringException&) {
1559  // just use default
1560  };
1561 
1562  parm = x_GetParameter(features, "TriOffset");
1563  if (parm != "")
1565 
1566  parm = x_GetParameter(features, "Shape");
1567  if (parm == "")
1568  parm = "RoundedRectangle";
1569 
1571  if (s != NULL) {
1572  s->SetBoundaryParms(parms);
1573 
1574  CRef<IBoundaryShape> sr(s);
1575  m_Shapes["Default"] = sr;
1576  }
1577 
1578  x_AddBoundaryType(parms, x_GetParameter(features, "SlantedCladogram"),
1579  "SlantedCladogram");
1580  x_AddBoundaryType(parms, x_GetParameter(features, "RectCladogram"),
1581  "RectCladogram");
1582  x_AddBoundaryType(parms, x_GetParameter(features, "Radial"),
1583  "Radial");
1584  x_AddBoundaryType(parms, x_GetParameter(features, "ForceLayout"),
1585  "ForceLayout");
1586 
1587  m_BoundaryShape = m_Shapes["Default"];
1588 }
1589 
BoundaryShapeEllipse –.
void SetCornerWidth(float w)
Get/set size of rounded corners used for region (may not apply to all typs of regions) (in pixels)
void SetIncludeTextArea(bool b)
Enable/disable inclusion of text boxes into boundary area.
void SetTriOffset(float o)
Set/Get distance of a triangle's starting vertex behind its base node.
void SetDrawBoundaryEdge(bool b)
Enable/disable drawing of a single-pixel width colored edge around boundary.
void SetTextBox(bool b)
Enable/disable using a separate bounding box for text (meant for triangles)
void SetAxisAligned(bool b)
Enable/disable inclusion of text boxes into boundary area.
CRgbaColor & GetBoundaryEdgeColor()
void SetBorderWidth(float w)
Set/get size of border region around subtree (in pixels)
void AddPixelRect(const CVect2< float > &pt, const CGlRect< float > &rect)
Add point in bounded area along with a rectangle based at that point and defined in pixels,...
const vector< CVect2< float > > & GetGraphPoints() const
const vector< std::pair< CVect2< float >, CGlRect< float > > > & GetPixelPoints() const
void AddBoundedPoint(const CVect2< float > &pt)
Add point to be included in bounded area.
void AddBoundedPoints(CBoundaryPoints &pts)
Add the boundary areas of the subtree to this boundary area.
void ClearBoundedPoints()
Clear all accumulated bounding points.
vector< CVect2< float > > m_GraphPoints
Points and text rectangles used to compute boundary area (and discarded afterwards)
vector< std::pair< CVect2< float >, CGlRect< float > > > m_PixelPoints
virtual void ComputeShape(const CVect2< float > &scale, const CVect2< float > &base_node_pos, const std::vector< CVect2< float > > &pts, const vector< std::pair< CVect2< float >, CGlRect< float > > > &pixel_pts)
Given points which scale (pts) and rectangles for text (pixel_pts) which do not scale,...
float m_PixelDeltaNegX
Delta values applied to corners to accomodate labels which do not scale with the tree as a whole.
virtual void ComputeShapeWithLabels(const CVect2< float > &scale, bool labels_visible=true)
CVect2< float > m_Points[4]
Corners of the rectangle.
CBoundaryShapeRect –.
void x_GetEdges(vector< CVect2< float > > &edges, const CVect2< float > &scale)
void x_GetTris(vector< CVect2< float > > &tris, const CVect2< float > &scale)
CBoundaryShapeRoundedRect –.
void x_GetRoudedCornerTris(vector< CVect2< float > > &tris, const CVect2< float > &pos, float corner_width_x, float corner_width_y, float start_angle)
void x_GetRoudedCornerEdges(vector< CVect2< float > > &edges, const CVect2< float > &pos, float corner_width_x, float corner_width_y, float start_angle)
void x_GetTris(vector< CVect2< float > > &tris, const CVect2< float > &scale)
void x_GetEdges(vector< CVect2< float > > &edges, const CVect2< float > &scale)
CBoundaryShapeTri –.
void x_GetArc(const RoundedCorner &c, const CVect2< float > &scale, vector< CVect2< float > > &edges)
Get the points that make up the roundec.
void x_GetEdges(vector< CVect2< float > > &edges, const CVect2< float > &scale)
float m_Width
Width and height (maximum extents) used if scaling is applied.
void x_GetTris(vector< CVect2< float > > &tris, const CVect2< float > &scale)
virtual void ComputeShapeWithLabels(const CVect2< float > &scale, bool labels_visible=true)
virtual void ComputeShape(const CVect2< float > &scale, const CVect2< float > &base_node_pos, const std::vector< CVect2< float > > &pts, const vector< std::pair< CVect2< float >, CGlRect< float > > > &pixel_pts)
Given points which scale (pts) and rectangles for text (pixel_pts) which do not scale,...
std::vector< RoundedCorner > m_RoundedCorners
The rounded corners.
RoundedCorner x_ComputeRoundedCorner(const CVect2< float > &pt_in, const CVect2< float > &prev_pt_in, const CVect2< float > &next_pt_in, const CVect2< float > &scale, CVect2< float > &pt_out1, CVect2< float > &pt_out2)
CVect2< float > m_TextBox[4]
Used for debugging text box.
CVect2< float > m_Rect1[4]
Corners of the rectangles that make up the triangle with clipped corners (to allow rounding) and the ...
void x_ComputeTriParms(const std::vector< CVect2< float > > &pts, const CVect2< float > &base_pos, const CVect2< float > &dir, const CVect2< float > &perp_dir, float &max_len, float &max_angle_top, float &max_angle_bottom)
CVect2< float > m_Center
Center of the shape, used for scaling if a border is applied.
CGlVboNode A rendering node that holds a vertex buffer object.
Definition: glvbonode.hpp:64
class CRgbaColor provides a simple abstraction for managing colors.
Definition: rgba_color.hpp:58
CStringException –.
Definition: ncbistr.hpp:4506
string m_BoundaryStr
Feature string from which boundary parameters were created.
void RenderBoundary(const CVect2< float > &scale, float alpha_mod=1.0f, bool include_labels=true)
Render current shape.
bool Overlaps(TModelRect &r) const
Return true if boundary (in model coordinates) overlaps rectangle r.
void RenderBoundaryVbo(const CVect2< float > &scale, float alpha_mod=1.0f, bool include_labels=true)
Render to vbo (create vbo but do not draw)
void ComputeShapes(const CBoundaryPoints &boundary_pts, const CVect2< float > &scale, const CVect2< float > &base_node_pos, const string &layout_type)
Use the accumulated point data to compute shape dimensions.
CRef< CGlVboNode > m_BoundaryTris
void CreateShapes(const std::string &features)
Parse the features to create the shapes and set their options.
CRef< IBoundaryShape > m_BoundaryShape
Current (active) boundary shape (for current layout)
bool x_GetColorParameter(const string &features, const string &parm, bool parm_required, CRgbaColor &c)
For parsing a color parameter.
map< string, CRef< IBoundaryShape > > m_Shapes
All shapes created for boundary (may be different shapes for differnt layout algorighms).
void x_AddBoundaryType(const CBoundaryParms &parms, const string &boundary_type, const string &layout_type)
Add a boundary for the specified layout algorithm.
string x_GetParameter(const string &features, const string &parm)
For parsing boudary info - get a parameter.
void Hide(bool b=true)
Show/hide boundary area.
CRef< CGlVboNode > m_BoundaryEdges
void RenderVbo()
Render the vbo.
virtual void ComputeShapeWithLabels(const CVect2< float > &scale, bool labels_visible=true)
CBoundaryParms m_Parms
Paramters for boundary parsed from features string.
std::vector< CVect2< float > > m_NodePoints
Nodes inside the boundary.
CVect2< float > m_BaseNodePos
Parent/root node for nodes in the bounded area.
virtual void x_GetTris(vector< CVect2< float > > &tris, const CVect2< float > &scale)
const TModelRect & GetExtent() const
virtual void x_GetEdges(vector< CVect2< float > > &edges, const CVect2< float > &scale)
virtual void Render(const CVect2< float > &scale, float alpha_mod=1.0f, bool include_labels=true)
Render the boundary if !hidden.
void Hide(bool b)
Enable/disable rendering of the boundary.
vector< std::pair< CVect2< float >, CGlRect< float > > > m_PixelPoints
These pairs define the (scaled) location and associated text rectangle for the labels inside the boun...
virtual void RenderVbo(CRef< CGlVboNode > &tri_node, CRef< CGlVboNode > &edge_node, const CVect2< float > &scale, float alpha_mod=1.0f, bool include_labels=true)
TModelRect m_Extent
Extent of boundery (min/max xy)
virtual void ComputeShape(const CVect2< float > &scale, const CVect2< float > &base_node_pos, const std::vector< CVect2< float > > &pts, const vector< std::pair< CVect2< float >, CGlRect< float > > > &pixel_pts)=0
Given points which scale (pts) and rectangles for text (pixel_pts) which do not scale,...
void SetBoundaryParms(const CBoundaryParms &p)
static IBoundaryShape * CreateBoundary(const string &boundary_type)
Create a new boundary object given it's name.
bool m_Hidden
If true, do not render.
const_iterator end() const
Definition: map.hpp:152
void clear()
Definition: map.hpp:169
const_iterator find(const key_type &key) const
Definition: map.hpp:153
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
int offset
Definition: replacements.h:160
void swap(NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair1, NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair2)
Definition: ncbimisc.hpp:1508
string
Definition: cgiapp.hpp:687
#define NULL
Definition: ncbistd.hpp:225
float Length() const
Definition: vect2.hpp:271
T Dot(const CVect2< T > &) const
Definition: vect2.hpp:237
void Set(T x, T y)
Definition: vect2.hpp:260
const CVect2< U > & v2
Definition: globals.hpp:440
T & X()
Definition: vect2.hpp:107
const float pi
Definition: math.hpp:54
void Normalize()
Definition: vect2.hpp:296
const float epsilon
Definition: math.hpp:61
T & Y()
Definition: vect2.hpp:109
GLdouble TModelUnit
Definition: gltypes.hpp:48
void SetRight(T right)
Definition: glrect.hpp:114
void SetVertexBuffer2D(const vector< CVect2< float > > &data)
Definition: glvbonode.cpp:75
T X() const
Definition: glpoint.hpp:59
void Init()
Definition: glrect.hpp:62
void SetBottom(T bottom)
Definition: glrect.hpp:113
virtual void PolygonMode(GLenum face, GLenum mode)
Set the polygon rasterization mode.
Definition: glstate.cpp:522
T Top() const
Definition: glrect.hpp:84
T Bottom() const
Definition: glrect.hpp:82
virtual void Render()
Set state and call x_Render() to render geometry.
T Right() const
Definition: glrect.hpp:83
virtual void Enable(GLenum glstate)
glEnable() all options in m_Enabled
Definition: glstate.cpp:356
CGlState & GetState()
virtual void LineWidth(GLfloat w)
Set line width for drawing: glLineWidth()
Definition: glstate.cpp:410
virtual void LineCapStyle(ELineCapStyle c)
Set line cap ending style (pdf only)
Definition: glstate.cpp:610
T Left() const
Definition: glrect.hpp:81
T Y() const
Definition: glpoint.hpp:60
void SetLeft(T left)
Definition: glrect.hpp:112
CGlPoint< T > GetCorner(int idx)
Definition: glrect.hpp:100
virtual void LineJoinStyle(ELineJoinStyle s)
PDF-specific rendering state.
Definition: glstate.cpp:602
virtual void BlendFunc(GLenum sfactor, GLenum dfactor)
Options to be used when GL_BLEND is enabled.
Definition: glstate.cpp:562
void SetTop(T top)
Definition: glrect.hpp:115
virtual void ColorC(const CRgbaColor &c)
Definition: glstate.cpp:449
@ eRoundedJoin
Definition: glstate.hpp:77
@ eRoundCap
Definition: glstate.hpp:78
void Set(float r, float g, float b)
set the color from an Fl_Color
Definition: rgba_color.cpp:226
void SetAlpha(float r)
Definition: rgba_color.cpp:287
void FromString(const string &str)
Assign color values encoded in a string.
Definition: rgba_color.cpp:363
float GetAlpha(void) const
Definition: rgba_color.hpp:339
const float * GetColorArray(void) const
Access the color array directly.
Definition: rgba_color.hpp:394
void Reset(void)
Reset reference object.
Definition: ncbiobj.hpp:773
bool IsNull(void) const THROWS_NONE
Check if pointer is null – same effect as Empty().
Definition: ncbiobj.hpp:735
bool Empty(void) const THROWS_NONE
Check if CRef is empty – not pointing to any object, which means having a null value.
Definition: ncbiobj.hpp:719
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
static bool StringToBool(const CTempString str)
Convert string to bool.
Definition: ncbistr.cpp:2821
static double StringToDouble(const CTempStringEx str, TStringToNumFlags flags=0)
Convert string to double.
Definition: ncbistr.cpp:1387
static string & ToLower(string &str)
Convert string to lower case – string& version.
Definition: ncbistr.cpp:405
@ fConvErr_NoThrow
Do not throw an exception on error.
Definition: ncbistr.hpp:285
int i
#define abs(a)
Definition: ncbi_heapmgr.c:130
unsigned int a
Definition: ncbi_localip.c:102
T max(T x_, T y_)
T min(T x_, T y_)
Int4 delta(size_t dimension_, const Int4 *score_)
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
Standard mechanism to include OpenGL headers for all platforms.
#define FLT_EPSILON
Definition: stdtypes.cpp:214
Rounded corners are drawn as circles that replace the corner that would extend from intersection[1,...
Modified on Wed May 22 11:35:11 2024 by modify_doxy.py rev. 669887