Panda3D
|
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