Panda3D
|
00001 // Filename: isoPlacer.cxx 00002 // Created by: drose (13Oct03) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "isoPlacer.h" 00016 #include "qtessSurface.h" 00017 #include "subdivSegment.h" 00018 #include "nurbsSurfaceResult.h" 00019 #include "pvector.h" 00020 00021 00022 //////////////////////////////////////////////////////////////////// 00023 // Function: IsoPlacer::get_scores 00024 // Access: Public 00025 // Description: 00026 //////////////////////////////////////////////////////////////////// 00027 void IsoPlacer:: 00028 get_scores(int subdiv, int across, double ratio, 00029 NurbsSurfaceResult *surf, bool s) { 00030 _maxi = subdiv - 1; 00031 00032 _cscore.clear(); 00033 _sscore.clear(); 00034 00035 _cscore.reserve(_maxi); 00036 _sscore.reserve(_maxi); 00037 00038 // First, tally up the curvature and stretch scores across the 00039 // surface. 00040 int i = 0; 00041 for (i = 0; i < _maxi; i++) { 00042 _cscore.push_back(0.0); 00043 _sscore.push_back(0.0); 00044 } 00045 00046 int a; 00047 for (a = 0; a <= across; a++) { 00048 double v = (double)a / (double)across; 00049 00050 LVecBase3 p1, p2, p3, pnext; 00051 LVecBase3 v1, v2; 00052 if (s) { 00053 surf->eval_point(0.0, v, p3); 00054 } else { 00055 surf->eval_point(v, 0.0, p3); 00056 } 00057 int num_points = 1; 00058 00059 for (i = -1; i < _maxi; i++) { 00060 double u = (double)(i+1) / (double)(_maxi+1); 00061 if (s) { 00062 surf->eval_point(u, v, pnext); 00063 } else { 00064 surf->eval_point(v, u, pnext); 00065 } 00066 00067 // We'll ignore consecutive equal points. They don't contribute 00068 // to curvature or size. 00069 if (!pnext.almost_equal(p3)) { 00070 num_points++; 00071 p1 = p2; 00072 p2 = p3; 00073 p3 = pnext; 00074 00075 v1 = v2; 00076 v2 = p3 - p2; 00077 double vlength = length(v2); 00078 v2 /= vlength; 00079 00080 if (i >= 0) { 00081 _sscore[i] += vlength; 00082 } 00083 00084 if (num_points >= 3) { 00085 // We only have a meaningful v1, v2 when we've read at least 00086 // three non-equal points. 00087 double d = v1.dot(v2); 00088 00089 _cscore[i] += acos(max(min(d, 1.0), -1.0)); 00090 } 00091 } 00092 } 00093 } 00094 00095 // Now integrate. 00096 _cint.clear(); 00097 _cint.reserve(_maxi + 1); 00098 00099 double net = 0.0; 00100 double ad = (double)(across+1); 00101 _cint.push_back(0.0); 00102 for (i = 0; i < _maxi; i++) { 00103 net += _cscore[i]/ad + ratio * _sscore[i]/ad; 00104 _cint.push_back(net); 00105 } 00106 } 00107 00108 //////////////////////////////////////////////////////////////////// 00109 // Function: IsoPlacer::place 00110 // Access: Public 00111 // Description: 00112 //////////////////////////////////////////////////////////////////// 00113 void IsoPlacer:: 00114 place(int count, pvector<double> &iso_points) { 00115 int i; 00116 00117 // Count up the average curvature. 00118 double avg_curve = 0.0; 00119 for (i = 0; i < _maxi; i++) { 00120 avg_curve += _cscore[i]; 00121 } 00122 avg_curve /= (double)_maxi; 00123 00124 // Find all the local maxima in the curvature table. These are bend 00125 // points. 00126 typedef pvector<int> BendPoints; 00127 BendPoints bpoints; 00128 BendPoints::iterator bi, bnext; 00129 00130 typedef pvector<SubdivSegment> Segments; 00131 Segments segments; 00132 Segments::iterator si; 00133 00134 /* 00135 // Having problems with bend points right now. Maybe this is just a 00136 // bad idea. It seems to work pretty well without them, anyway. 00137 for (i = 1; i < _maxi-1; i++) { 00138 // A point must be measurably higher than both its neighbors, as 00139 // well as at least 50% more curvy than the average curvature, to 00140 // qualify as a bend point. 00141 if (_cscore[i] > _cscore[i-1]+0.001 && 00142 _cscore[i] > _cscore[i+1]+0.001 && 00143 _cscore[i] > 1.5 * avg_curve) { 00144 bpoints.push_back(i); 00145 } 00146 } 00147 */ 00148 00149 // Now make sure there aren't any two bend points closer together 00150 // than maxi/count. If there are, remove the smaller of the two. 00151 bi = bpoints.begin(); 00152 int min_separation = _maxi/count; 00153 while (bi != bpoints.end()) { 00154 bnext = bi; 00155 ++bnext; 00156 00157 if (bnext != bpoints.end() && (*bnext) - (*bi) < min_separation) { 00158 // Too close. Remove one. 00159 if (_cscore[*bnext] > _cscore[*bi]) { 00160 *bi = *bnext; 00161 } 00162 bpoints.erase(bnext); 00163 } else { 00164 // Not too close; keep going; 00165 bi = bnext; 00166 } 00167 } 00168 00169 // Now, if we have fewer total subdivisions than bend points, then 00170 // remove the smallest bend points. 00171 while (count - 1 < (int)bpoints.size()) { 00172 bi = bpoints.begin(); 00173 BendPoints::iterator mi = bi; 00174 for (++bi; bi != bpoints.end(); ++bi) { 00175 if (_cscore[*bi] < _cscore[*mi]) { 00176 mi = bi; 00177 } 00178 } 00179 bpoints.erase(mi); 00180 } 00181 00182 // Now all the remaining bend points are valid. 00183 bi = bpoints.begin(); 00184 int last = 0; 00185 for (bi = bpoints.begin(); bi != bpoints.end(); ++bi) { 00186 segments.push_back(SubdivSegment(&_cint[0], last, *bi)); 00187 last = *bi; 00188 } 00189 segments.push_back(SubdivSegment(&_cint[0], last, _maxi)); 00190 00191 int nr = count - segments.size(); 00192 00193 // Now we have subdivided the curve into a number of smaller curves 00194 // at the bend points. We still have nr remaining cuts to make; 00195 // distribute these cuts among the curves evenly according to 00196 // score. 00197 00198 // Divvy out the extra cuts. First, each segment gets an amount 00199 // proportional to its score. 00200 double net_score = _cint[_maxi]; 00201 nassertv(net_score > 0.0); 00202 int ns = 0; 00203 for (si = segments.begin(); si != segments.end(); ++si) { 00204 (*si)._num_cuts = (int)floor(nr * (*si).get_score() / net_score); 00205 nassertv((*si)._num_cuts <= nr); // This fails if net_score is nan. 00206 ns += (*si)._num_cuts; 00207 } 00208 00209 // Then, assign the remaining cuts to the neediest segments. 00210 nr -= ns; 00211 while (nr > 0) { 00212 si = min_element(segments.begin(), segments.end()); 00213 (*si)._num_cuts++; 00214 nr--; 00215 } 00216 00217 // Now cut up the segments as indicated. 00218 for (si = segments.begin(); si != segments.end(); ++si) { 00219 (*si).cut(); 00220 } 00221 00222 // Finally, return the result. 00223 iso_points.erase(iso_points.begin(), iso_points.end()); 00224 00225 iso_points.push_back(0.0); 00226 for (si = segments.begin(); si != segments.end(); ++si) { 00227 pvector<int>::iterator ci; 00228 for (ci = (*si)._cuts.begin(); ci != (*si)._cuts.end(); ++ci) { 00229 iso_points.push_back((*ci+1) / (double)(_maxi+1)); 00230 } 00231 iso_points.push_back(((*si)._t+1) / (double)(_maxi+1)); 00232 } 00233 00234 // Oh, wait. The last segment is actually drawn all the way to 1. 00235 iso_points.back() = 1.0; 00236 } 00237 00238