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) {
219 pvector<int>::iterator ci;
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 }
NurbsSurfaceResult
The result of a NurbsSurfaceEvaluator.
Definition: nurbsSurfaceResult.h:29
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
SubdivSegment
Represents a single hypothetical subdivided segment, under consideration by the IsoPlacer.
Definition: subdivSegment.h:25
pvector< double >
isoPlacer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
nurbsSurfaceResult.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pvector.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
qtessSurface.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
subdivSegment.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.