Panda3D
 All Classes Functions Variables Enumerations
nurbsCurveResult.cxx
1 // Filename: nurbsCurveResult.cxx
2 // Created by: drose (04Dec02)
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 "nurbsCurveResult.h"
16 #include "nurbsVertex.h"
17 
18 
19 ////////////////////////////////////////////////////////////////////
20 // Function: NurbsCurveResult::Constructor
21 // Access: Public
22 // Description: The constructor automatically builds up the result as
23 // the product of the indicated set of basis matrices
24 // and the indicated table of control vertex positions.
25 ////////////////////////////////////////////////////////////////////
28  const LVecBase4 vecs[], const NurbsVertex *verts,
29  int num_vertices) :
30  _basis(basis),
31  _verts(verts)
32 {
33  _last_segment = -1;
34  int order = _basis.get_order();
35  int num_segments = _basis.get_num_segments();
36 
37  _composed.reserve(num_segments);
38  for (int i = 0; i < num_segments; i++) {
39  int vi = _basis.get_vertex_index(i);
40  nassertv(vi >= 0 && vi + order - 1 < num_vertices);
41 
42  // Create a geometry matrix from our (up to) four involved vertices.
43  LMatrix4 geom;
44  int ci = 0;
45  while (ci < order) {
46  geom.set_row(ci, vecs[vi + ci]);
47  ci++;
48  }
49  while (ci < 4) {
50  geom.set_row(ci, LVecBase4::zero());
51  ci++;
52  }
53 
54  // And compose this geometry matrix with the basis matrix to
55  // produce a new matrix, which will be used to evaluate the curve.
56  LMatrix4 result;
57  result.multiply(_basis.get_basis(i), geom);
58  _composed.push_back(result);
59  }
60 }
61 
62 ////////////////////////////////////////////////////////////////////
63 // Function: NurbsCurveResult::eval_segment_point
64 // Access: Published
65 // Description: Evaluates the point on the curve corresponding to the
66 // indicated value in parametric time within the
67 // indicated curve segment. t should be in the range
68 // [0, 1].
69 //
70 // The curve is internally represented as a number of
71 // connected (or possibly unconnected) piecewise
72 // continuous segments. The exact number of segments
73 // for a particular curve depends on the knot vector,
74 // and is returned by get_num_segments(). Normally,
75 // eval_point() is used to evaluate a point along the
76 // continuous curve, but when you care more about local
77 // continuity, you can use eval_segment_point() to
78 // evaluate the points along each segment.
79 ////////////////////////////////////////////////////////////////////
81 eval_segment_point(int segment, PN_stdfloat t, LVecBase3 &point) const {
82  PN_stdfloat t2 = t*t;
83  LVecBase4 tvec(t*t2, t2, t, 1.0f);
84 
85  PN_stdfloat weight = tvec.dot(_composed[segment].get_col(3));
86 
87  point.set(tvec.dot(_composed[segment].get_col(0)) / weight,
88  tvec.dot(_composed[segment].get_col(1)) / weight,
89  tvec.dot(_composed[segment].get_col(2)) / weight);
90 }
91 
92 ////////////////////////////////////////////////////////////////////
93 // Function: NurbsCurveResult::eval_segment_tangent
94 // Access: Published
95 // Description: As eval_segment_point, but computes the tangent to
96 // the curve at the indicated point. The tangent vector
97 // will not necessarily be normalized, and could be
98 // zero, particularly at the endpoints.
99 ////////////////////////////////////////////////////////////////////
101 eval_segment_tangent(int segment, PN_stdfloat t, LVecBase3 &tangent) const {
102  PN_stdfloat t2 = t*t;
103  LVecBase4 tvec(3.0 * t2, 2.0 * t, 1.0f, 0.0f);
104 
105  tangent.set(tvec.dot(_composed[segment].get_col(0)),
106  tvec.dot(_composed[segment].get_col(1)),
107  tvec.dot(_composed[segment].get_col(2)));
108 }
109 
110 ////////////////////////////////////////////////////////////////////
111 // Function: NurbsCurveResult::eval_segment_extended_point
112 // Access: Published
113 // Description: Evaluates the curve in n-dimensional space according
114 // to the extended vertices associated with the curve in
115 // the indicated dimension.
116 ////////////////////////////////////////////////////////////////////
117 PN_stdfloat NurbsCurveResult::
118 eval_segment_extended_point(int segment, PN_stdfloat t, int d) const {
119  nassertr(segment >= 0 && segment < _basis.get_num_segments(), 0.0f);
120 
121  PN_stdfloat t2 = t*t;
122  LVecBase4 tvec(t*t2, t2, t, 1.0f);
123 
124  PN_stdfloat weight = tvec.dot(_composed[segment].get_col(3));
125 
126  // Calculate the composition of the basis matrix and the geometry
127  // matrix on-the-fly.
128  int order = _basis.get_order();
129  int vi = _basis.get_vertex_index(segment);
130 
131  LVecBase4 geom;
132  int ci = 0;
133  while (ci < order) {
134  geom[ci] = _verts[vi + ci].get_extended_vertex(d);
135  ci++;
136  }
137  while (ci < 4) {
138  geom[ci] = 0.0f;
139  ci++;
140  }
141 
142  const LMatrix4 &basis = _basis.get_basis(segment);
143 
144  // Compute matrix * column vector.
145  LVecBase4 composed_geom(basis.get_row(0).dot(geom),
146  basis.get_row(1).dot(geom),
147  basis.get_row(2).dot(geom),
148  basis.get_row(3).dot(geom));
149  return tvec.dot(composed_geom) / weight;
150 }
151 
152 ////////////////////////////////////////////////////////////////////
153 // Function: NurbsCurveResult::eval_segment_extended_points
154 // Access: Published
155 // Description: Simultaneously performs eval_extended_point on a
156 // contiguous sequence of dimensions. The dimensions
157 // evaluated are d through (d + num_values - 1); the
158 // results are filled into the num_values elements in
159 // the indicated result array.
160 ////////////////////////////////////////////////////////////////////
162 eval_segment_extended_points(int segment, PN_stdfloat t, int d,
163  PN_stdfloat result[], int num_values) const {
164  nassertv(segment >= 0 && segment < _basis.get_num_segments());
165 
166  PN_stdfloat t2 = t*t;
167  LVecBase4 tvec(t*t2, t2, t, 1.0f);
168 
169  PN_stdfloat weight = tvec.dot(_composed[segment].get_col(3));
170 
171  // Calculate the composition of the basis matrix and the geometry
172  // matrix on-the-fly.
173  const LMatrix4 &basis = _basis.get_basis(segment);
174  int order = _basis.get_order();
175  int vi = _basis.get_vertex_index(segment);
176 
177  for (int n = 0; n < num_values; n++) {
178  LVecBase4 geom;
179  int ci = 0;
180  while (ci < order) {
181  geom[ci] = _verts[vi + ci].get_extended_vertex(d + n);
182  ci++;
183  }
184  while (ci < 4) {
185  geom[ci] = 0.0f;
186  ci++;
187  }
188 
189  // Compute matrix * column vector.
190  LVecBase4 composed_geom(basis.get_row(0).dot(geom),
191  basis.get_row(1).dot(geom),
192  basis.get_row(2).dot(geom),
193  basis.get_row(3).dot(geom));
194  result[n] = tvec.dot(composed_geom) / weight;
195  }
196 }
197 
198 ////////////////////////////////////////////////////////////////////
199 // Function: NurbsCurveResult::adaptive_sample
200 // Access: Published
201 // Description: Determines the set of subdivisions necessary to
202 // approximate the curve with a set of linear segments,
203 // no point of which is farther than tolerance units
204 // from the actual curve.
205 //
206 // After this call, you may walk through the resulting
207 // set of samples with get_num_samples(),
208 // get_sample_t(), and get_sample_point().
209 ////////////////////////////////////////////////////////////////////
211 adaptive_sample(PN_stdfloat tolerance) {
212  PN_stdfloat tolerance_2 = tolerance * tolerance;
213  _adaptive_result.clear();
214 
215  LPoint3 p0, p1;
216 
217  int num_segments = _basis.get_num_segments();
218  for (int segment = 0; segment < num_segments; ++segment) {
219  eval_segment_point(segment, 0.0f, p0);
220  if (segment == 0 || !p0.almost_equal(p1)) {
221  // We explicitly push the first point, and the boundary point
222  // anytime the segment boundary is discontinuous.
223  _adaptive_result.push_back(AdaptiveSample(_basis.get_from(segment), p0));
224  }
225 
226  eval_segment_point(segment, 1.0f, p1);
227 
228  // Then we recusrively get the remaining points in the segment.
229  r_adaptive_sample(segment, 0.0f, p0, 1.0f, p1, tolerance_2);
230  }
231 }
232 
233 ////////////////////////////////////////////////////////////////////
234 // Function: NurbsCurveResult::find_segment
235 // Access: Private
236 // Description: Returns the index of the segment that contains the
237 // indicated value of t, or -1 if no segment contains
238 // this value.
239 ////////////////////////////////////////////////////////////////////
240 int NurbsCurveResult::
241 find_segment(PN_stdfloat t) {
242  // Trivially check the endpoints of the curve.
243  if (t >= get_end_t()) {
244  return _basis.get_num_segments() - 1;
245  } else if (t <= get_start_t()) {
246  return 0;
247  }
248 
249  // Check the last segment we searched for. Often, two consecutive
250  // requests are for the same segment.
251  if (_last_segment != -1 && (t >= _last_from && t < _last_to)) {
252  return _last_segment;
253  }
254 
255  // Look for the segment the hard way.
256  int segment = r_find_segment(t, 0, _basis.get_num_segments() - 1);
257  if (segment != -1) {
258  _last_segment = segment;
259  _last_from = _basis.get_from(segment);
260  _last_to = _basis.get_to(segment);
261  }
262  return segment;
263 }
264 
265 ////////////////////////////////////////////////////////////////////
266 // Function: NurbsCurveResult::r_find_segment
267 // Access: Private
268 // Description: Recursively searches for the segment that contains
269 // the indicated value of t by performing a binary
270 // search. This assumes the segments are stored in
271 // increasing order of t, and they don't overlap.
272 ////////////////////////////////////////////////////////////////////
273 int NurbsCurveResult::
274 r_find_segment(PN_stdfloat t, int top, int bot) const {
275  if (bot < top) {
276  // Not found.
277  return -1;
278  }
279  int mid = (top + bot) / 2;
280  nassertr(mid >= 0 && mid < _basis.get_num_segments(), -1);
281 
282  PN_stdfloat from = _basis.get_from(mid);
283  PN_stdfloat to = _basis.get_to(mid);
284  if (from > t) {
285  // Too high, try lower.
286  return r_find_segment(t, top, mid - 1);
287 
288  } else if (to <= t) {
289  // Too low, try higher.
290  return r_find_segment(t, mid + 1, bot);
291 
292  } else {
293  // Here we are!
294  return mid;
295  }
296 }
297 
298 ////////////////////////////////////////////////////////////////////
299 // Function: NurbsCurveResult::r_adaptive_sample
300 // Access: Private
301 // Description: Recursively subdivides a potential evaluation of the
302 // segment until it is found to be within tolerance.
303 // This will add everything up to and including t1, but
304 // excluding t0.
305 ////////////////////////////////////////////////////////////////////
306 void NurbsCurveResult::
307 r_adaptive_sample(int segment, PN_stdfloat t0, const LPoint3 &p0,
308  PN_stdfloat t1, const LPoint3 &p1, PN_stdfloat tolerance_2) {
309  PN_stdfloat tmid = (t0 + t1) * 0.5f;
310  LPoint3 pmid;
311  eval_segment_point(segment, tmid, pmid);
312 
313  if (sqr_dist_to_line(pmid, p0, p1 - p0) > tolerance_2) {
314  // The line is still too curved--subdivide.
315  r_adaptive_sample(segment, t0, p0, tmid, pmid, tolerance_2);
316  r_adaptive_sample(segment, tmid, pmid, t1, p1, tolerance_2);
317 
318  } else {
319  // The line is sufficiently close. Stop here.
320  _adaptive_result.push_back(AdaptiveSample(_basis.scale_t(segment, t1), p1));
321  }
322 }
323 
324 ////////////////////////////////////////////////////////////////////
325 // Function: NurbsCurveResult::sqr_dist_to_line
326 // Access: Private, Static
327 // Description: A support function for r_adaptive_sample(), this
328 // computes the minimum distance from a point to a line,
329 // and returns the distance squared.
330 ////////////////////////////////////////////////////////////////////
331 PN_stdfloat NurbsCurveResult::
332 sqr_dist_to_line(const LPoint3 &point, const LPoint3 &origin,
333  const LVector3 &vec) {
334  LVector3 norm = vec;
335  norm.normalize();
336  LVector3 d = point - origin;
337  PN_stdfloat hyp_2 = d.length_squared();
338  PN_stdfloat leg = d.dot(norm);
339  return hyp_2 - leg * leg;
340 }
This is the base class for all three-component vectors and points.
Definition: lvecBase3.h:105
int get_num_segments() const
Returns the number of piecewise continuous segments in the curve.
PN_stdfloat get_extended_vertex(int d) const
Returns an n-dimensional vertex value.
Definition: nurbsVertex.cxx:54
LVecBase4f get_row(int row) const
Retrieves the indicated row of the matrix as a 4-component vector.
Definition: lmatrix.h:1258
PN_stdfloat get_from(int segment) const
Returns the t value of the beginning of this segment.
void eval_segment_point(int segment, PN_stdfloat t, LVecBase3 &point) const
Evaluates the point on the curve corresponding to the indicated value in parametric time within the i...
PN_stdfloat scale_t(int segment, PN_stdfloat t) const
Scales the value of t into the range [0, 1] corresponding to [from, to].
float length_squared() const
Returns the square of the vector&#39;s length, cheap and easy.
Definition: lvecBase3.h:748
int get_order() const
Returns the order of the segments in the curve.
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:100
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
Definition: lpoint3.h:99
PN_stdfloat get_end_t() const
Returns the last legal value of t on the curve.
void eval_segment_tangent(int segment, PN_stdfloat t, LVecBase3 &tangent) const
As eval_segment_point, but computes the tangent to the curve at the indicated point.
void eval_segment_extended_points(int segment, PN_stdfloat t, int d, PN_stdfloat result[], int num_values) const
Simultaneously performs eval_extended_point on a contiguous sequence of dimensions.
This represents a single control vertex in a NurbsEvaluator.
Definition: nurbsVertex.h:36
NurbsCurveResult(const NurbsBasisVector &basis, const LVecBase4 vecs[], const NurbsVertex *verts, int num_vertices)
The constructor automatically builds up the result as the product of the indicated set of basis matri...
PN_stdfloat eval_segment_extended_point(int segment, PN_stdfloat t, int d) const
Evaluates the curve in n-dimensional space according to the extended vertices associated with the cur...
This encapsulates a series of matrices that are used to represent the sequential segments of a NurbsC...
This is a 4-by-4 transform matrix.
Definition: lmatrix.h:451
const LMatrix4 & get_basis(int segment) const
Returns the basis matrix associated with the nth segment.
int get_vertex_index(int segment) const
Returns the vertex index of the nth segment.
This is the base class for all three-component vectors and points.
Definition: lvecBase4.h:111
PN_stdfloat get_to(int segment) const
Returns the t value of the end of this segment.
bool almost_equal(const LVecBase3f &other, float threshold) const
Returns true if two vectors are memberwise equal within a specified tolerance.
Definition: lvecBase3.h:1264
void adaptive_sample(PN_stdfloat tolerance)
Determines the set of subdivisions necessary to approximate the curve with a set of linear segments...
void set_row(int row, const LVecBase4f &v)
Replaces the indicated row of the matrix.
Definition: lmatrix.h:1187
bool normalize()
Normalizes the vector in place.
Definition: lvecBase3.h:782
PN_stdfloat get_start_t() const
Returns the first legal value of t on the curve.
static const LVecBase4f & zero()
Returns a zero-length vector.
Definition: lvecBase4.h:492