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