Panda3D
subdivSegment.cxx
1 // Filename: subdivSegment.cxx
2 // Created by: drose (14Oct03)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "subdivSegment.h"
16 
17 
18 
19 
20 ////////////////////////////////////////////////////////////////////
21 // Function: binary_search
22 // Description: Performs a standard binary search. This utility
23 // function is used below.
24 ////////////////////////////////////////////////////////////////////
25 static int
26 binary_search(double val, const double *array, int bot, int top) {
27  if (top < bot) {
28  return bot;
29  }
30  int mid = (bot + top)/2;
31 
32  if (array[mid] < val) {
33  return binary_search(val, array, mid+1, top);
34  } else {
35  return binary_search(val, array, bot, mid-1);
36  }
37 }
38 
39 
40 ////////////////////////////////////////////////////////////////////
41 // Function: SubdivSegment::cut
42 // Access: Public
43 // Description: Applies _num_cuts cuts to the segment.
44 ////////////////////////////////////////////////////////////////////
45 void SubdivSegment::
46 cut() {
47  int c;
48  double ct = get_score();
49 
50  _cuts.erase(_cuts.begin(), _cuts.end());
51  int last = _f;
52  for (c = 1; c < _num_cuts+1; c++) {
53  double val = (double)c * ct / (double)(_num_cuts+1) + _cint[_f];
54  int i = binary_search(val, _cint, _f, _t);
55  if (i != last && i < _t) {
56  _cuts.push_back(i);
57  }
58  last = i;
59  }
60 
61  while ((int)_cuts.size() < _num_cuts) {
62  // Do we have any extra? Assign them into likely places.
63  int last = _f;
64  int mc = -1;
65  int mv = 0;
66  for (c = 0; c < (int)_cuts.size(); c++) {
67  if (mc == -1 || _cuts[c] - last > mv) {
68  mc = c;
69  mv = _cuts[c] - last;
70  }
71  last = _cuts[c];
72  }
73 
74  if (mc==-1) {
75  // Surrender.
76  return;
77  }
78  if (mc==0) {
79  _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _f) / 2);
80  } else {
81  _cuts.insert(_cuts.begin() + mc, (_cuts[mc] + _cuts[mc-1]) / 2);
82  }
83  }
84 }
85 
double get_score() const
Returns the net score of the segment.
Definition: subdivSegment.I:35
void cut()
Applies _num_cuts cuts to the segment.