Panda3D

subdivSegment.cxx

00001 // Filename: subdivSegment.cxx
00002 // Created by:  drose (14Oct03)
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 "subdivSegment.h"
00016 
00017 
00018 
00019 
00020 ////////////////////////////////////////////////////////////////////
00021 //     Function: binary_search
00022 //  Description: Performs a standard binary search.  This utility
00023 //               function is used below.
00024 ////////////////////////////////////////////////////////////////////
00025 static int
00026 binary_search(double val, const double *array, int bot, int top) {
00027   if (top < bot) {
00028     return bot;
00029   }
00030   int mid = (bot + top)/2;
00031 
00032   if (array[mid] < val) {
00033     return binary_search(val, array, mid+1, top);
00034   } else {
00035     return binary_search(val, array, bot, mid-1);
00036   }
00037 }
00038 
00039 
00040 ////////////////////////////////////////////////////////////////////
00041 //     Function: SubdivSegment::cut
00042 //       Access: Public
00043 //  Description: Applies _num_cuts cuts to the segment.
00044 ////////////////////////////////////////////////////////////////////
00045 void SubdivSegment::
00046 cut() {
00047   int c;
00048   double ct = get_score();
00049 
00050   _cuts.erase(_cuts.begin(), _cuts.end());
00051   int last = _f;
00052   for (c = 1; c < _num_cuts+1; c++) {
00053     double val = (double)c * ct / (double)(_num_cuts+1) + _cint[_f];
00054     int i = binary_search(val, _cint, _f, _t);
00055     if (i != last && i < _t) {
00056       _cuts.push_back(i);
00057     }
00058     last = i;
00059   }
00060 
00061   while ((int)_cuts.size() < _num_cuts) {
00062     // Do we have any extra?  Assign them into likely places.
00063     int last = _f;
00064     int mc = -1;
00065     int mv = 0;
00066     for (c = 0; c < (int)_cuts.size(); c++) {
00067       if (mc == -1 || _cuts[c] - last > mv) {
00068         mc = c;
00069         mv = _cuts[c] - last;
00070       }
00071       last = _cuts[c];
00072     }
00073 
00074     if (mc==-1) {
00075       // Surrender.
00076       return;
00077     }
00078     if (mc==0) {
00079       _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _f) / 2);
00080     } else {
00081       _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _cuts[mc-1]) / 2);
00082     }
00083   }
00084 }
00085 
 All Classes Functions Variables Enumerations