BRL-CAD
BBNode.cpp
Go to the documentation of this file.
1 /* B B N O D E . C P P
2  * BRL-CAD
3  *
4  * Copyright (c) 2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 #include "common.h"
21 #include <algorithm> // for std::max
22 #define NOMINMAX
23 extern "C" {
24 #include "bu/log.h"
25 }
26 #include "brep.h"
27 
28 namespace brlcad {
29 BBNode::~BBNode()
30 {
31  /* delete the children */
32  for (size_t i = 0; i < m_children.size(); i++) {
33  delete m_children[i];
34  }
35 }
36 
37 bool
38 BBNode::intersectsHierarchy(ON_Ray &ray, std::list<BBNode *> &results_opt)
39 {
40  double tnear, tfar;
41  bool intersects = intersectedBy(ray, &tnear, &tfar);
42  if (intersects && isLeaf()) {
43  results_opt.push_back(this);
44  } else if (intersects) {
45  for (size_t i = 0; i < m_children.size(); i++) {
46  m_children[i]->intersectsHierarchy(ray, results_opt);
47  }
48  }
49  return intersects;
50 }
51 
52 bool
53 BBNode::containsUV(const ON_2dPoint &uv)
54 {
55  if ((uv[0] > m_u[0]) && (uv[0] < m_u[1]) && (uv[1] > m_v[0]) && (uv[1] < m_v[1])) {
56  return true;
57  } else {
58  return false;
59  }
60 }
61 
62 int
63 BBNode::depth()
64 {
65  int d = 0;
66  for (size_t i = 0; i < m_children.size(); i++) {
67  d = 1 + std::max(d, m_children[i]->depth());
68  }
69  return d;
70 }
71 
72 void
73 BBNode::getLeaves(std::list<BBNode *> &out_leaves)
74 {
75  if (m_children.size() > 0) {
76  for (size_t i = 0; i < m_children.size(); i++) {
77  m_children[i]->getLeaves(out_leaves);
78  }
79  } else {
80  out_leaves.push_back(this);
81  }
82 }
83 
84 BBNode *
85 BBNode::closer(const ON_3dPoint &pt, BBNode *left, BBNode *right)
86 {
87  double ldist = pt.DistanceTo(left->m_estimate);
88  double rdist = pt.DistanceTo(right->m_estimate);
89  TRACE("\t" << ldist << " < " << rdist);
90  if (ldist < rdist) {
91  return left;
92  } else {
93  return right;
94  }
95 }
96 
97 ON_2dPoint
98 BBNode::getClosestPointEstimate(const ON_3dPoint &pt)
99 {
100  ON_Interval u, v;
101  return getClosestPointEstimate(pt, u, v);
102 }
103 
104 ON_2dPoint
105 BBNode::getClosestPointEstimate(const ON_3dPoint &pt, ON_Interval &u, ON_Interval &v)
106 {
107  if (isLeaf()) {
108  double uvs[5][2] = {{m_u.Min(), m_v.Min()}, {m_u.Max(), m_v.Min()},
109  {m_u.Max(), m_v.Max()}, {m_u.Min(), m_v.Max()},
110  {m_u.Mid(), m_v.Mid()}
111  }; /* include the estimate */
112  ON_3dPoint corners[5];
113  const ON_Surface *surf = m_face->SurfaceOf();
114 
115  u = m_u;
116  v = m_v;
117 
118  /* ??? pass these in from SurfaceTree::surfaceBBox() to avoid
119  * this recalculation?
120  */
121  if (!surf->EvPoint(uvs[0][0], uvs[0][1], corners[0]) ||
122  !surf->EvPoint(uvs[1][0], uvs[1][1], corners[1]) ||
123  !surf->EvPoint(uvs[2][0], uvs[2][1], corners[2]) ||
124  !surf->EvPoint(uvs[3][0], uvs[3][1], corners[3]))
125  {
126  throw new std::exception(); /* FIXME */
127  }
128  corners[4] = BBNode::m_estimate;
129 
130  /* find the point on the surface closest to pt */
131  size_t mini = 0;
132  double mindist = pt.DistanceTo(corners[mini]);
133  double tmpdist;
134  for (size_t i = 1; i < 5; i++) {
135  tmpdist = pt.DistanceTo(corners[i]);
136  TRACE("\t" << mindist << " < " << tmpdist);
137  if (tmpdist < mindist) {
138  mini = i;
139  mindist = tmpdist;
140  }
141  }
142  TRACE("Closest: " << mindist << "; " << PT2(uvs[mini]));
143  return ON_2dPoint(uvs[mini][0], uvs[mini][1]);
144  } else {
145  if (m_children.size() > 0) {
146  BBNode *closestNode = m_children[0];
147  for (size_t i = 1; i < m_children.size(); i++) {
148  closestNode = closer(pt, closestNode, m_children[i]);
149  TRACE("\t" << PT(closestNode->m_estimate));
150  }
151  return closestNode->getClosestPointEstimate(pt, u, v);
152  }
153  throw new std::exception();
154  }
155 }
156 
157 int
158 BBNode::getLeavesBoundingPoint(const ON_3dPoint &pt, std::list<BBNode *> &out)
159 {
160  if (isLeaf()) {
161  double min[3], max[3];
162  GetBBox(min, max);
163  if ((pt.x >= (min[0])) && (pt.x <= (max[0])) &&
164  (pt.y >= (min[1])) && (pt.y <= (max[1])) &&
165  (pt.z >= (min[2])) && (pt.z <= (max[2])))
166  {
167  /* falls within BBox so put in list */
168  out.push_back(this);
169  return 1;
170  }
171  return 0;
172  } else {
173  int sum = 0;
174  for (size_t i = 0; i < m_children.size(); i++) {
175  sum += m_children[i]->getLeavesBoundingPoint(pt, out);
176  }
177  return sum;
178  }
179 }
180 
181 int
182 BBNode::isTrimmed(const ON_2dPoint &uv, BRNode **closest, double &closesttrim, double within_distance_tol) const
183 {
184  BRNode *br;
185  std::list<BRNode *> trims;
186 
187  closesttrim = -1.0;
188  if (m_checkTrim) {
189  getTrimsAbove(uv, trims);
190 
191  if (trims.empty()) {
192  return 1;
193  } else { /* find closest BB */
194  std::list<BRNode *>::iterator i;
195  BRNode *vclosest = NULL;
196  BRNode *uclosest = NULL;
197  fastf_t currHeight = (fastf_t)0.0;
198  bool currTrimStatus = false;
199  bool verticalTrim = false;
200  bool underTrim = false;
201  double vdist = 0.0;
202  double udist = 0.0;
203 
204  for (i = trims.begin(); i != trims.end(); i++) {
205  br = dynamic_cast<BRNode *>(*i);
206 
207  /* skip if trim below */
208  if (br->m_node.m_max[1] + within_distance_tol < uv[Y]) {
209  continue;
210  }
211 
212  if (br->m_Vertical) {
213  if ((br->m_v[0] <= uv[Y]) && (br->m_v[1] >= uv[Y])) {
214  double dist = fabs(uv[X] - br->m_v[0]);
215  if (!verticalTrim) { /* haven't seen vertical trim yet */
216  verticalTrim = true;
217  vdist = dist;
218  vclosest = br;
219  } else {
220  if (dist < vdist) {
221  vdist = dist;
222  vclosest = br;
223  }
224  }
225 
226  }
227  continue;
228  }
229  double v;
230  bool trimstatus = br->isTrimmed(uv, v);
231  if (v >= 0.0) {
232  if (closest && *closest == NULL) {
233  currHeight = v;
234  currTrimStatus = trimstatus;
235  if (closest) {
236  *closest = br;
237  }
238  } else if (v < currHeight) {
239  currHeight = v;
240  currTrimStatus = trimstatus;
241  if (closest) {
242  *closest = br;
243  }
244  }
245  } else {
246  double dist = fabs(v);
247  if (!underTrim) {
248  underTrim = true;
249  udist = dist;
250  uclosest = br;
251  } else {
252  V_MIN(udist, dist);
253  uclosest = br;
254  }
255  }
256  }
257  if (closest && *closest == NULL) {
258  if (verticalTrim) {
259  closesttrim = vdist;
260  if (closest) {
261  *closest = vclosest;
262  }
263  }
264  if ((underTrim) && (!verticalTrim || (udist < closesttrim))) {
265  closesttrim = udist;
266  if (closest) {
267  *closest = uclosest;
268  }
269  }
270  return 1;
271  } else {
272  closesttrim = currHeight;
273  if ((verticalTrim) && (vdist < closesttrim)) {
274  closesttrim = vdist;
275  if (closest) {
276  *closest = vclosest;
277  }
278  }
279  if ((underTrim) && (udist < closesttrim)) {
280  closesttrim = udist;
281  if (closest) {
282  *closest = uclosest;
283  }
284  }
285  return currTrimStatus;
286  }
287  }
288  } else {
289  if (m_trimmed) {
290  return 1;
291  } else {
292  return 0;
293  }
294  }
295 }
296 
297 void
298 BBNode::getTrimsAbove(const ON_2dPoint &uv, std::list<BRNode *> &out_leaves) const
299 {
300  point_t bmin, bmax;
301  double dist;
302  for (std::list<BRNode *>::const_iterator i = m_trims_above.begin(); i != m_trims_above.end(); i++) {
303  BRNode *br = dynamic_cast<BRNode *>(*i);
304  br->GetBBox(bmin, bmax);
305  dist = 0.000001; /* 0.03*DIST_PT_PT(bmin, bmax); */
306  if ((uv[X] > bmin[X] - dist) && (uv[X] < bmax[X] + dist)) {
307  out_leaves.push_back(br);
308  }
309  }
310 }
311 
312 void BBNode::BuildBBox()
313 {
314  if (m_children.size() > 0) {
315  for (std::vector<BBNode *>::iterator childnode = m_children.begin(); childnode != m_children.end(); childnode++) {
316  if (!(*childnode)->isLeaf()) {
317  (*childnode)->BuildBBox();
318  }
319  if (childnode == m_children.begin()) {
320  m_node = ON_BoundingBox((*childnode)->m_node.m_min, (*childnode)->m_node.m_max);
321  } else {
322  for (int j = 0; j < 3; j++) {
323  V_MIN(m_node.m_min[j], (*childnode)->m_node.m_min[j]);
324  V_MAX(m_node.m_max[j], (*childnode)->m_node.m_max[j]);
325  }
326  }
327  }
328  }
329 }
330 
331 bool
332 BBNode::prepTrims()
333 {
334  CurveTree *ct = m_ctree;
335  std::list<BRNode *>::iterator i;
336  BRNode *br;
337  point_t curvemin, curvemax;
338  double dist = 0.000001;
339  bool trim_already_assigned = false;
340 
341  m_trims_above.clear();
342 
343  if (LIKELY(ct != NULL)) {
344  ct->getLeavesAbove(m_trims_above, m_u, m_v);
345  }
346 
347  m_trims_above.sort(sortY);
348 
349  if (!m_trims_above.empty()) {
350  i = m_trims_above.begin();
351  while (i != m_trims_above.end()) {
352  br = dynamic_cast<BRNode *>(*i);
353  if (br->m_Vertical) { /* check V to see if trim possibly overlaps */
354  br->GetBBox(curvemin, curvemax);
355  if (curvemin[Y] - dist <= m_v[1]) {
356  /* possibly contains trim can't rule out check
357  * closer */
358  m_checkTrim = true;
359  trim_already_assigned = true;
360  i++;
361  } else {
362  i = m_trims_above.erase(i);
363  }
364  } else {
365  i++;
366  }
367  }
368  }
369 
370  if (!trim_already_assigned) { /* already contains possible vertical trim */
371  if (m_trims_above.empty() /*|| m_trims_right.empty()*/) {
372  m_trimmed = true;
373  m_checkTrim = false;
374  } else if (!m_trims_above.empty()) { /*trimmed above check contains */
375  i = m_trims_above.begin();
376  br = dynamic_cast<BRNode *>(*i);
377  br->GetBBox(curvemin, curvemax);
378  dist = 0.000001; /* 0.03*DIST_PT_PT(curvemin, curvemax); */
379  if (curvemin[Y] - dist > m_v[1]) {
380  i++;
381 
382  if (i == m_trims_above.end()) { /* easy only trim in above list */
383  if (br->m_XIncreasing) {
384  m_trimmed = true;
385  m_checkTrim = false;
386  } else {
387  m_trimmed = false;
388  m_checkTrim = false;
389  }
390  } else {
391  /* check for trim bbox overlap TODO: look for
392  * multiple overlaps.
393  */
394  BRNode *bs;
395  bs = dynamic_cast<BRNode *>(*i);
396  point_t smin, smax;
397  bs->GetBBox(smin, smax);
398  if ((smin[Y] >= curvemax[Y]) || (smin[X] >= curvemax[X]) || (smax[X] <= curvemin[X])) { /* can determine inside/outside without closer inspection */
399  if (br->m_XIncreasing) {
400  m_trimmed = true;
401  m_checkTrim = false;
402  } else {
403  m_trimmed = false;
404  m_checkTrim = false;
405  }
406  } else {
407  m_checkTrim = true;
408  }
409  }
410  } else {
411  m_checkTrim = true;
412  }
413  } else { /* something wrong here */
414  bu_log("Error prepping trims");
415  return false;
416  }
417  }
418  return true;
419 }
420 }
421 
422 // Local Variables:
423 // tab-width: 8
424 // mode: C++
425 // c-basic-offset: 4
426 // indent-tabs-mode: t
427 // c-file-style: "stroustrup"
428 // End:
429 // ex: shiftwidth=4 tabstop=8
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define LIKELY(expression)
Definition: common.h:261
Header file for the BRL-CAD common definitions.
ustring closest
Definition: color.c:49
goto out
Definition: nmg_mod.c:3846
boost::shared_ptr< MathFunction > ct
Definition: vm_test.cpp:34
bool sortY(BRNode *first, BRNode *second)
double fastf_t
Definition: defines.h:300
Definition: color.c:50