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