Panda3D
isoPlacer.cxx
Go to the documentation of this file.
1 /**
2  * PANDA 3D SOFTWARE
3  * Copyright (c) Carnegie Mellon University. All rights reserved.
4  *
5  * All use of this software is subject to the terms of the revised BSD
6  * license. You should have received a copy of this license along
7  * with this source code in a file named "LICENSE."
8  *
9  * @file isoPlacer.cxx
10  * @author drose
11  * @date 2003-10-13
12  */
13 
14 #include "isoPlacer.h"
15 #include "qtessSurface.h"
16 #include "subdivSegment.h"
17 #include "nurbsSurfaceResult.h"
18 #include "pvector.h"
19 
20 
21 /**
22  *
23  */
24 void IsoPlacer::
25 get_scores(int subdiv, int across, double ratio,
26  NurbsSurfaceResult *surf, bool s) {
27  _maxi = subdiv - 1;
28 
29  _cscore.clear();
30  _sscore.clear();
31 
32  _cscore.reserve(_maxi);
33  _sscore.reserve(_maxi);
34 
35  // First, tally up the curvature and stretch scores across the surface.
36  int i = 0;
37  for (i = 0; i < _maxi; i++) {
38  _cscore.push_back(0.0);
39  _sscore.push_back(0.0);
40  }
41 
42  int a;
43  for (a = 0; a <= across; a++) {
44  double v = (double)a / (double)across;
45 
46  LVecBase3 p1, p2, p3, pnext;
47  LVecBase3 v1, v2;
48  if (s) {
49  surf->eval_point(0.0, v, p3);
50  } else {
51  surf->eval_point(v, 0.0, p3);
52  }
53  int num_points = 1;
54 
55  for (i = -1; i < _maxi; i++) {
56  double u = (double)(i+1) / (double)(_maxi+1);
57  if (s) {
58  surf->eval_point(u, v, pnext);
59  } else {
60  surf->eval_point(v, u, pnext);
61  }
62 
63  // We'll ignore consecutive equal points. They don't contribute to
64  // curvature or size.
65  if (!pnext.almost_equal(p3)) {
66  num_points++;
67  p1 = p2;
68  p2 = p3;
69  p3 = pnext;
70 
71  v1 = v2;
72  v2 = p3 - p2;
73  double vlength = length(v2);
74  v2 /= vlength;
75 
76  if (i >= 0) {
77  _sscore[i] += vlength;
78  }
79 
80  if (num_points >= 3) {
81  // We only have a meaningful v1, v2 when we've read at least three
82  // non-equal points.
83  double d = v1.dot(v2);
84 
85  _cscore[i] += acos(std::max(std::min(d, 1.0), -1.0));
86  }
87  }
88  }
89  }
90 
91  // Now integrate.
92  _cint.clear();
93  _cint.reserve(_maxi + 1);
94 
95  double net = 0.0;
96  double ad = (double)(across+1);
97  _cint.push_back(0.0);
98  for (i = 0; i < _maxi; i++) {
99  net += _cscore[i]/ad + ratio * _sscore[i]/ad;
100  _cint.push_back(net);
101  }
102 }
103 
104 /**
105  *
106  */
107 void IsoPlacer::
108 place(int count, pvector<double> &iso_points) {
109  int i;
110 
111  // Count up the average curvature.
112  double avg_curve = 0.0;
113  for (i = 0; i < _maxi; i++) {
114  avg_curve += _cscore[i];
115  }
116  avg_curve /= (double)_maxi;
117 
118  // Find all the local maxima in the curvature table. These are bend points.
119  typedef pvector<int> BendPoints;
120  BendPoints bpoints;
121  BendPoints::iterator bi, bnext;
122 
123  typedef pvector<SubdivSegment> Segments;
124  Segments segments;
125  Segments::iterator si;
126 
127  /*
128  // Having problems with bend points right now. Maybe this is just a bad
129  // idea. It seems to work pretty well without them, anyway.
130  for (i = 1; i < _maxi-1; i++) {
131  // A point must be measurably higher than both its neighbors, as well as
132  // at least 50% more curvy than the average curvature, to qualify as a
133  // bend point.
134  if (_cscore[i] > _cscore[i-1]+0.001 &&
135  _cscore[i] > _cscore[i+1]+0.001 &&
136  _cscore[i] > 1.5 * avg_curve) {
137  bpoints.push_back(i);
138  }
139  }
140  */
141 
142  // Now make sure there aren't any two bend points closer together than
143  // maxicount. If there are, remove the smaller of the two.
144  bi = bpoints.begin();
145  int min_separation = _maxi/count;
146  while (bi != bpoints.end()) {
147  bnext = bi;
148  ++bnext;
149 
150  if (bnext != bpoints.end() && (*bnext) - (*bi) < min_separation) {
151  // Too close. Remove one.
152  if (_cscore[*bnext] > _cscore[*bi]) {
153  *bi = *bnext;
154  }
155  bpoints.erase(bnext);
156  } else {
157  // Not too close; keep going;
158  bi = bnext;
159  }
160  }
161 
162  // Now, if we have fewer total subdivisions than bend points, then remove
163  // the smallest bend points.
164  while (count - 1 < (int)bpoints.size()) {
165  bi = bpoints.begin();
166  BendPoints::iterator mi = bi;
167  for (++bi; bi != bpoints.end(); ++bi) {
168  if (_cscore[*bi] < _cscore[*mi]) {
169  mi = bi;
170  }
171  }
172  bpoints.erase(mi);
173  }
174 
175  // Now all the remaining bend points are valid.
176  bi = bpoints.begin();
177  int last = 0;
178  for (bi = bpoints.begin(); bi != bpoints.end(); ++bi) {
179  segments.push_back(SubdivSegment(&_cint[0], last, *bi));
180  last = *bi;
181  }
182  segments.push_back(SubdivSegment(&_cint[0], last, _maxi));
183 
184  int nr = count - segments.size();
185 
186  // Now we have subdivided the curve into a number of smaller curves at the
187  // bend points. We still have nr remaining cuts to make; distribute these
188  // cuts among the curves evenly according to score.
189 
190  // Divvy out the extra cuts. First, each segment gets an amount
191  // proportional to its score.
192  double net_score = _cint[_maxi];
193  nassertv(net_score > 0.0);
194  int ns = 0;
195  for (si = segments.begin(); si != segments.end(); ++si) {
196  (*si)._num_cuts = (int)floor(nr * (*si).get_score() / net_score);
197  nassertv((*si)._num_cuts <= nr); // This fails if net_score is nan.
198  ns += (*si)._num_cuts;
199  }
200 
201  // Then, assign the remaining cuts to the neediest segments.
202  nr -= ns;
203  while (nr > 0) {
204  si = min_element(segments.begin(), segments.end());
205  (*si)._num_cuts++;
206  nr--;
207  }
208 
209  // Now cut up the segments as indicated.
210  for (si = segments.begin(); si != segments.end(); ++si) {
211  (*si).cut();
212  }
213 
214  // Finally, return the result.
215  iso_points.erase(iso_points.begin(), iso_points.end());
216 
217  iso_points.push_back(0.0);
218  for (si = segments.begin(); si != segments.end(); ++si) {
220  for (ci = (*si)._cuts.begin(); ci != (*si)._cuts.end(); ++ci) {
221  iso_points.push_back((*ci+1) / (double)(_maxi+1));
222  }
223  iso_points.push_back(((*si)._t+1) / (double)(_maxi+1));
224  }
225 
226  // Oh, wait. The last segment is actually drawn all the way to 1.
227  iso_points.back() = 1.0;
228 }
pvector< double >
pvector.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
qtessSurface.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SubdivSegment
Represents a single hypothetical subdivided segment, under consideration by the IsoPlacer.
Definition: subdivSegment.h:25
NurbsSurfaceResult::eval_point
bool eval_point(PN_stdfloat u, PN_stdfloat v, LVecBase3 &point)
Computes the point on the surface corresponding to the indicated value in parametric time.
Definition: nurbsSurfaceResult.I:59
isoPlacer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
nurbsSurfaceResult.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
subdivSegment.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
NurbsSurfaceResult
The result of a NurbsSurfaceEvaluator.
Definition: nurbsSurfaceResult.h:29