Panda3D

isoPlacer.cxx

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 
 All Classes Functions Variables Enumerations