Panda3D
 All Classes Functions Variables Enumerations
nurbsSurfaceResult.cxx
1 // Filename: nurbsSurfaceResult.cxx
2 // Created by: drose (10Oct03)
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 "nurbsSurfaceResult.h"
16 #include "nurbsVertex.h"
17 
18 
19 ////////////////////////////////////////////////////////////////////
20 // Function: NurbsSurfaceResult::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 NurbsBasisVector &v_basis,
29  const LVecBase4 vecs[], const NurbsVertex *verts,
30  int num_u_vertices, int num_v_vertices) :
31  _u_basis(u_basis),
32  _v_basis(v_basis),
33  _verts(verts),
34  _num_u_vertices(num_u_vertices),
35  _num_v_vertices(num_v_vertices)
36 {
37  // The V basis matrices will always be transposed.
38  _v_basis.transpose();
39 
40  _last_u_segment = -1;
41  _last_v_segment = -1;
42  int u_order = _u_basis.get_order();
43  int v_order = _v_basis.get_order();
44  int num_u_segments = _u_basis.get_num_segments();
45  int num_v_segments = _v_basis.get_num_segments();
46  int num_segments = num_u_segments * num_v_segments;
47 
48  _composed.reserve(num_segments);
49  for (int i = 0; i < num_segments; i++) {
50  _composed.push_back(ComposedMats());
51  }
52 
53  for (int vi = 0; vi < num_v_segments; vi++) {
54  const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi);
55 
56  int vn = _v_basis.get_vertex_index(vi);
57  nassertv(vn >= 0 && vn + v_order - 1 < _num_v_vertices);
58 
59  for (int ui = 0; ui < num_u_segments; ui++) {
60  const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui);
61 
62  int un = _u_basis.get_vertex_index(ui);
63  nassertv(un >= 0 && un + u_order - 1 < _num_u_vertices);
64 
65  // Create four geometry matrices from our (up to) sixteen
66  // involved vertices.
67  LMatrix4 geom_x, geom_y, geom_z, geom_w;
68  memset(&geom_x, 0, sizeof(geom_x));
69  memset(&geom_y, 0, sizeof(geom_y));
70  memset(&geom_z, 0, sizeof(geom_z));
71  memset(&geom_w, 0, sizeof(geom_w));
72 
73  for (int uni = 0; uni < 4; uni++) {
74  for (int vni = 0; vni < 4; vni++) {
75  if (uni < u_order && vni < v_order) {
76  const LVecBase4 &vec = vecs[verti(un + uni, vn + vni)];
77  geom_x(uni, vni) = vec[0];
78  geom_y(uni, vni) = vec[1];
79  geom_z(uni, vni) = vec[2];
80  geom_w(uni, vni) = vec[3];
81  }
82  }
83  }
84 
85  // And compose these geometry matrices with the basis matrices
86  // to produce a new set of matrices, which will be used to
87  // evaluate the surface.
88  int i = segi(ui, vi);
89  nassertv(i >= 0 && i < (int)_composed.size());
90  ComposedMats &result = _composed[i];
91  result._x = u_basis_mat * geom_x * v_basis_transpose;
92  result._y = u_basis_mat * geom_y * v_basis_transpose;
93  result._z = u_basis_mat * geom_z * v_basis_transpose;
94  result._w = u_basis_mat * geom_w * v_basis_transpose;
95  }
96  }
97 }
98 
99 ////////////////////////////////////////////////////////////////////
100 // Function: NurbsSurfaceResult::eval_segment_point
101 // Access: Published
102 // Description: Evaluates the point on the surface corresponding to the
103 // indicated value in parametric time within the
104 // indicated surface segment. u and v should be in the
105 // range [0, 1].
106 //
107 // The surface is internally represented as a number of
108 // connected (or possibly unconnected) piecewise
109 // continuous segments. The exact number of segments
110 // for a particular surface depends on the knot vector,
111 // and is returned by get_num_segments(). Normally,
112 // eval_point() is used to evaluate a point along the
113 // continuous surface, but when you care more about local
114 // continuity, you can use eval_segment_point() to
115 // evaluate the points along each segment.
116 ////////////////////////////////////////////////////////////////////
118 eval_segment_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &point) const {
119  int i = segi(ui, vi);
120  nassertv(i >= 0 && i < (int)_composed.size());
121 
122  PN_stdfloat u2 = u*u;
123  LVecBase4 uvec(u*u2, u2, u, 1.0f);
124  PN_stdfloat v2 = v*v;
125  LVecBase4 vvec(v*v2, v2, v, 1.0f);
126 
127  PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w);
128 
129  point.set(vvec.dot(uvec * _composed[i]._x) / weight,
130  vvec.dot(uvec * _composed[i]._y) / weight,
131  vvec.dot(uvec * _composed[i]._z) / weight);
132 }
133 
134 ////////////////////////////////////////////////////////////////////
135 // Function: NurbsSurfaceResult::eval_segment_normal
136 // Access: Published
137 // Description: As eval_segment_point, but computes the normal to
138 // the surface at the indicated point. The normal vector
139 // will not necessarily be normalized, and could be
140 // zero.
141 ////////////////////////////////////////////////////////////////////
143 eval_segment_normal(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &normal) const {
144  int i = segi(ui, vi);
145  nassertv(i >= 0 && i < (int)_composed.size());
146 
147  PN_stdfloat u2 = u*u;
148  LVecBase4 uvec(u*u2, u2, u, 1.0f);
149  LVecBase4 duvec(3.0f * u2, 2.0f * u, 1.0f, 0.0f);
150  PN_stdfloat v2 = v*v;
151  LVecBase4 vvec(v*v2, v2, v, 1.0f);
152  LVecBase4 dvvec(3.0f * v2, 2.0f * v, 1.0f, 0.0f);
153 
154  LVector3 utan(vvec.dot(duvec * _composed[i]._x),
155  vvec.dot(duvec * _composed[i]._y),
156  vvec.dot(duvec * _composed[i]._z));
157 
158  LVector3 vtan(dvvec.dot(uvec * _composed[i]._x),
159  dvvec.dot(uvec * _composed[i]._y),
160  dvvec.dot(uvec * _composed[i]._z));
161 
162  normal = utan.cross(vtan);
163 }
164 
165 ////////////////////////////////////////////////////////////////////
166 // Function: NurbsSurfaceResult::eval_segment_extended_point
167 // Access: Published
168 // Description: Evaluates the surface in n-dimensional space according
169 // to the extended vertices associated with the surface in
170 // the indicated dimension.
171 ////////////////////////////////////////////////////////////////////
172 PN_stdfloat NurbsSurfaceResult::
173 eval_segment_extended_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d) const {
174  int i = segi(ui, vi);
175  nassertr(i >= 0 && i < (int)_composed.size(), 0.0f);
176 
177  PN_stdfloat u2 = u*u;
178  LVecBase4 uvec(u*u2, u2, u, 1.0f);
179  PN_stdfloat v2 = v*v;
180  LVecBase4 vvec(v*v2, v2, v, 1.0f);
181 
182  PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w);
183 
184  // Calculate the composition of the basis matrices and the geometry
185  // matrix on-the-fly.
186  const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi);
187  const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui);
188  int u_order = _u_basis.get_order();
189  int v_order = _v_basis.get_order();
190 
191  int un = _u_basis.get_vertex_index(ui);
192  int vn = _v_basis.get_vertex_index(vi);
193 
194  LMatrix4 geom;
195  memset(&geom, 0, sizeof(geom));
196 
197  for (int uni = 0; uni < 4; uni++) {
198  for (int vni = 0; vni < 4; vni++) {
199  if (uni < u_order && vni < v_order) {
200  geom(uni, vni) = _verts[verti(un + uni, vn + vni)].get_extended_vertex(d);
201  }
202  }
203  }
204 
205  LMatrix4 composed = u_basis_mat * geom * v_basis_transpose;
206  return vvec.dot(uvec * composed) / weight;
207 }
208 
209 ////////////////////////////////////////////////////////////////////
210 // Function: NurbsSurfaceResult::eval_segment_extended_points
211 // Access: Published
212 // Description: Simultaneously performs eval_extended_point on a
213 // contiguous sequence of dimensions. The dimensions
214 // evaluated are d through (d + num_values - 1); the
215 // results are filled into the num_values elements in
216 // the indicated result array.
217 ////////////////////////////////////////////////////////////////////
219 eval_segment_extended_points(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d,
220  PN_stdfloat result[], int num_values) const {
221  int i = segi(ui, vi);
222  nassertv(i >= 0 && i < (int)_composed.size());
223 
224  PN_stdfloat u2 = u*u;
225  LVecBase4 uvec(u*u2, u2, u, 1.0f);
226  PN_stdfloat v2 = v*v;
227  LVecBase4 vvec(v*v2, v2, v, 1.0f);
228 
229  PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w);
230 
231  // Calculate the composition of the basis matrices and the geometry
232  // matrix on-the-fly.
233  const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi);
234  const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui);
235  int u_order = _u_basis.get_order();
236  int v_order = _v_basis.get_order();
237 
238  int un = _u_basis.get_vertex_index(ui);
239  int vn = _v_basis.get_vertex_index(vi);
240 
241  for (int n = 0; n < num_values; n++) {
242  LMatrix4 geom;
243  memset(&geom, 0, sizeof(geom));
244 
245  for (int uni = 0; uni < 4; uni++) {
246  for (int vni = 0; vni < 4; vni++) {
247  if (uni < u_order && vni < v_order) {
248  geom(uni, vni) =
249  _verts[verti(un + uni, vn + vni)].get_extended_vertex(d + n);
250  }
251  }
252  }
253 
254  LMatrix4 composed = u_basis_mat * geom * v_basis_transpose;
255  result[n] = vvec.dot(uvec * composed) / weight;
256  }
257 }
258 
259 ////////////////////////////////////////////////////////////////////
260 // Function: NurbsSurfaceResult::find_u_segment
261 // Access: Private
262 // Description: Returns the index of the segment that contains the
263 // indicated value of t, or -1 if no segment contains
264 // this value.
265 ////////////////////////////////////////////////////////////////////
266 int NurbsSurfaceResult::
267 find_u_segment(PN_stdfloat u) {
268  // Trivially check the endpoints of the surface.
269  if (u >= get_end_u()) {
270  return _u_basis.get_num_segments() - 1;
271  } else if (u <= get_start_u()) {
272  return 0;
273  }
274 
275  // Check the last segment we searched for. Often, two consecutive
276  // requests are for the same segment.
277  if (_last_u_segment != -1 && (u >= _last_u_from && u < _last_u_to)) {
278  return _last_u_segment;
279  }
280 
281  // Look for the segment the hard way.
282  int segment = r_find_u_segment(u, 0, _u_basis.get_num_segments() - 1);
283  if (segment != -1) {
284  _last_u_segment = segment;
285  _last_u_from = _u_basis.get_from(segment);
286  _last_u_to = _u_basis.get_to(segment);
287  }
288  return segment;
289 }
290 
291 ////////////////////////////////////////////////////////////////////
292 // Function: NurbsSurfaceResult::r_find_u_segment
293 // Access: Private
294 // Description: Recursively searches for the segment that contains
295 // the indicated value of t by performing a binary
296 // search. This assumes the segments are stored in
297 // increasing order of t, and they don't overlap.
298 ////////////////////////////////////////////////////////////////////
299 int NurbsSurfaceResult::
300 r_find_u_segment(PN_stdfloat u, int top, int bot) const {
301  if (bot < top) {
302  // Not found.
303  return -1;
304  }
305  int mid = (top + bot) / 2;
306  nassertr(mid >= 0 && mid < _u_basis.get_num_segments(), -1);
307 
308  PN_stdfloat from = _u_basis.get_from(mid);
309  PN_stdfloat to = _u_basis.get_to(mid);
310  if (from > u) {
311  // Too high, try lower.
312  return r_find_u_segment(u, top, mid - 1);
313 
314  } else if (to <= u) {
315  // Too low, try higher.
316  return r_find_u_segment(u, mid + 1, bot);
317 
318  } else {
319  // Here we are!
320  return mid;
321  }
322 }
323 
324 
325 ////////////////////////////////////////////////////////////////////
326 // Function: NurbsSurfaceResult::find_v_segment
327 // Access: Private
328 // Description: Returns the index of the segment that contains the
329 // indicated value of t, or -1 if no segment contains
330 // this value.
331 ////////////////////////////////////////////////////////////////////
332 int NurbsSurfaceResult::
333 find_v_segment(PN_stdfloat v) {
334  // Trivially check the endpoints of the surface.
335  if (v >= get_end_v()) {
336  return _v_basis.get_num_segments() - 1;
337  } else if (v <= get_start_v()) {
338  return 0;
339  }
340 
341  // Check the last segment we searched for. Often, two consecutive
342  // requests are for the same segment.
343  if (_last_v_segment != -1 && (v >= _last_v_from && v < _last_v_to)) {
344  return _last_v_segment;
345  }
346 
347  // Look for the segment the hard way.
348  int segment = r_find_v_segment(v, 0, _v_basis.get_num_segments() - 1);
349  if (segment != -1) {
350  _last_v_segment = segment;
351  _last_v_from = _v_basis.get_from(segment);
352  _last_v_to = _v_basis.get_to(segment);
353  }
354  return segment;
355 }
356 
357 ////////////////////////////////////////////////////////////////////
358 // Function: NurbsSurfaceResult::r_find_v_segment
359 // Access: Private
360 // Description: Recursively searches for the segment that contains
361 // the indicated value of t by performing a binary
362 // search. This assumes the segments are stored in
363 // increasing order of t, and they don't overlap.
364 ////////////////////////////////////////////////////////////////////
365 int NurbsSurfaceResult::
366 r_find_v_segment(PN_stdfloat v, int top, int bot) const {
367  if (bot < top) {
368  // Not found.
369  return -1;
370  }
371  int mid = (top + bot) / 2;
372  nassertr(mid >= 0 && mid < _v_basis.get_num_segments(), -1);
373 
374  PN_stdfloat from = _v_basis.get_from(mid);
375  PN_stdfloat to = _v_basis.get_to(mid);
376  if (from > v) {
377  // Too high, try lower.
378  return r_find_v_segment(v, top, mid - 1);
379 
380  } else if (to <= v) {
381  // Too low, try higher.
382  return r_find_v_segment(v, mid + 1, bot);
383 
384  } else {
385  // Here we are!
386  return mid;
387  }
388 }
389 
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.
NurbsSurfaceResult(const NurbsBasisVector &u_basis, const NurbsBasisVector &v_basis, const LVecBase4 vecs[], const NurbsVertex *verts, int num_u_vertices, int num_v_vertices)
The constructor automatically builds up the result as the product of the indicated set of basis matri...
PN_stdfloat get_extended_vertex(int d) const
Returns an n-dimensional vertex value.
Definition: nurbsVertex.cxx:54
PN_stdfloat get_from(int segment) const
Returns the t value of the beginning of this segment.
void transpose()
Transposes the basis matrices stored in the vector.
void eval_segment_normal(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &normal) const
As eval_segment_point, but computes the normal to the surface at the indicated point.
PN_stdfloat get_end_u() const
Returns the last legal value of u on the surface.
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 represents a single control vertex in a NurbsEvaluator.
Definition: nurbsVertex.h:36
PN_stdfloat eval_segment_extended_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d) const
Evaluates the surface in n-dimensional space according to the extended vertices associated with the s...
void eval_segment_extended_points(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d, PN_stdfloat result[], int num_values) const
Simultaneously performs eval_extended_point on a contiguous sequence of dimensions.
PN_stdfloat get_end_v() const
Returns the last legal value of v on the surface.
PN_stdfloat get_start_u() const
Returns the first legal value of u on the surface.
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.
void eval_segment_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &point) const
Evaluates the point on the surface corresponding to the indicated value in parametric time within the...
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.
PN_stdfloat get_start_v() const
Returns the first legal value of v on the surface.