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