Panda3D
|
00001 // Filename: nurbsSurfaceResult.cxx 00002 // Created by: drose (10Oct03) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "nurbsSurfaceResult.h" 00016 #include "nurbsVertex.h" 00017 00018 00019 //////////////////////////////////////////////////////////////////// 00020 // Function: NurbsSurfaceResult::Constructor 00021 // Access: Public 00022 // Description: The constructor automatically builds up the result as 00023 // the product of the indicated set of basis matrices 00024 // and the indicated table of control vertex positions. 00025 //////////////////////////////////////////////////////////////////// 00026 NurbsSurfaceResult:: 00027 NurbsSurfaceResult(const NurbsBasisVector &u_basis, 00028 const NurbsBasisVector &v_basis, 00029 const LVecBase4 vecs[], const NurbsVertex *verts, 00030 int num_u_vertices, int num_v_vertices) : 00031 _u_basis(u_basis), 00032 _v_basis(v_basis), 00033 _verts(verts), 00034 _num_u_vertices(num_u_vertices), 00035 _num_v_vertices(num_v_vertices) 00036 { 00037 // The V basis matrices will always be transposed. 00038 _v_basis.transpose(); 00039 00040 _last_u_segment = -1; 00041 _last_v_segment = -1; 00042 int u_order = _u_basis.get_order(); 00043 int v_order = _v_basis.get_order(); 00044 int num_u_segments = _u_basis.get_num_segments(); 00045 int num_v_segments = _v_basis.get_num_segments(); 00046 int num_segments = num_u_segments * num_v_segments; 00047 00048 _composed.reserve(num_segments); 00049 for (int i = 0; i < num_segments; i++) { 00050 _composed.push_back(ComposedMats()); 00051 } 00052 00053 for (int vi = 0; vi < num_v_segments; vi++) { 00054 const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi); 00055 00056 int vn = _v_basis.get_vertex_index(vi); 00057 nassertv(vn >= 0 && vn + v_order - 1 < _num_v_vertices); 00058 00059 for (int ui = 0; ui < num_u_segments; ui++) { 00060 const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui); 00061 00062 int un = _u_basis.get_vertex_index(ui); 00063 nassertv(un >= 0 && un + u_order - 1 < _num_u_vertices); 00064 00065 // Create four geometry matrices from our (up to) sixteen 00066 // involved vertices. 00067 LMatrix4 geom_x, geom_y, geom_z, geom_w; 00068 memset(&geom_x, 0, sizeof(geom_x)); 00069 memset(&geom_y, 0, sizeof(geom_y)); 00070 memset(&geom_z, 0, sizeof(geom_z)); 00071 memset(&geom_w, 0, sizeof(geom_w)); 00072 00073 for (int uni = 0; uni < 4; uni++) { 00074 for (int vni = 0; vni < 4; vni++) { 00075 if (uni < u_order && vni < v_order) { 00076 const LVecBase4 &vec = vecs[verti(un + uni, vn + vni)]; 00077 geom_x(uni, vni) = vec[0]; 00078 geom_y(uni, vni) = vec[1]; 00079 geom_z(uni, vni) = vec[2]; 00080 geom_w(uni, vni) = vec[3]; 00081 } 00082 } 00083 } 00084 00085 // And compose these geometry matrices with the basis matrices 00086 // to produce a new set of matrices, which will be used to 00087 // evaluate the surface. 00088 int i = segi(ui, vi); 00089 nassertv(i >= 0 && i < (int)_composed.size()); 00090 ComposedMats &result = _composed[i]; 00091 result._x = u_basis_mat * geom_x * v_basis_transpose; 00092 result._y = u_basis_mat * geom_y * v_basis_transpose; 00093 result._z = u_basis_mat * geom_z * v_basis_transpose; 00094 result._w = u_basis_mat * geom_w * v_basis_transpose; 00095 } 00096 } 00097 } 00098 00099 //////////////////////////////////////////////////////////////////// 00100 // Function: NurbsSurfaceResult::eval_segment_point 00101 // Access: Published 00102 // Description: Evaluates the point on the surface corresponding to the 00103 // indicated value in parametric time within the 00104 // indicated surface segment. u and v should be in the 00105 // range [0, 1]. 00106 // 00107 // The surface is internally represented as a number of 00108 // connected (or possibly unconnected) piecewise 00109 // continuous segments. The exact number of segments 00110 // for a particular surface depends on the knot vector, 00111 // and is returned by get_num_segments(). Normally, 00112 // eval_point() is used to evaluate a point along the 00113 // continuous surface, but when you care more about local 00114 // continuity, you can use eval_segment_point() to 00115 // evaluate the points along each segment. 00116 //////////////////////////////////////////////////////////////////// 00117 void NurbsSurfaceResult:: 00118 eval_segment_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &point) const { 00119 int i = segi(ui, vi); 00120 nassertv(i >= 0 && i < (int)_composed.size()); 00121 00122 PN_stdfloat u2 = u*u; 00123 LVecBase4 uvec(u*u2, u2, u, 1.0f); 00124 PN_stdfloat v2 = v*v; 00125 LVecBase4 vvec(v*v2, v2, v, 1.0f); 00126 00127 PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w); 00128 00129 point.set(vvec.dot(uvec * _composed[i]._x) / weight, 00130 vvec.dot(uvec * _composed[i]._y) / weight, 00131 vvec.dot(uvec * _composed[i]._z) / weight); 00132 } 00133 00134 //////////////////////////////////////////////////////////////////// 00135 // Function: NurbsSurfaceResult::eval_segment_normal 00136 // Access: Published 00137 // Description: As eval_segment_point, but computes the normal to 00138 // the surface at the indicated point. The normal vector 00139 // will not necessarily be normalized, and could be 00140 // zero. 00141 //////////////////////////////////////////////////////////////////// 00142 void NurbsSurfaceResult:: 00143 eval_segment_normal(int ui, int vi, PN_stdfloat u, PN_stdfloat v, LVecBase3 &normal) const { 00144 int i = segi(ui, vi); 00145 nassertv(i >= 0 && i < (int)_composed.size()); 00146 00147 PN_stdfloat u2 = u*u; 00148 LVecBase4 uvec(u*u2, u2, u, 1.0f); 00149 LVecBase4 duvec(3.0f * u2, 2.0f * u, 1.0f, 0.0f); 00150 PN_stdfloat v2 = v*v; 00151 LVecBase4 vvec(v*v2, v2, v, 1.0f); 00152 LVecBase4 dvvec(3.0f * v2, 2.0f * v, 1.0f, 0.0f); 00153 00154 LVector3 utan(vvec.dot(duvec * _composed[i]._x), 00155 vvec.dot(duvec * _composed[i]._y), 00156 vvec.dot(duvec * _composed[i]._z)); 00157 00158 LVector3 vtan(dvvec.dot(uvec * _composed[i]._x), 00159 dvvec.dot(uvec * _composed[i]._y), 00160 dvvec.dot(uvec * _composed[i]._z)); 00161 00162 normal = utan.cross(vtan); 00163 } 00164 00165 //////////////////////////////////////////////////////////////////// 00166 // Function: NurbsSurfaceResult::eval_segment_extended_point 00167 // Access: Published 00168 // Description: Evaluates the surface in n-dimensional space according 00169 // to the extended vertices associated with the surface in 00170 // the indicated dimension. 00171 //////////////////////////////////////////////////////////////////// 00172 PN_stdfloat NurbsSurfaceResult:: 00173 eval_segment_extended_point(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d) const { 00174 int i = segi(ui, vi); 00175 nassertr(i >= 0 && i < (int)_composed.size(), 0.0f); 00176 00177 PN_stdfloat u2 = u*u; 00178 LVecBase4 uvec(u*u2, u2, u, 1.0f); 00179 PN_stdfloat v2 = v*v; 00180 LVecBase4 vvec(v*v2, v2, v, 1.0f); 00181 00182 PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w); 00183 00184 // Calculate the composition of the basis matrices and the geometry 00185 // matrix on-the-fly. 00186 const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi); 00187 const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui); 00188 int u_order = _u_basis.get_order(); 00189 int v_order = _v_basis.get_order(); 00190 00191 int un = _u_basis.get_vertex_index(ui); 00192 int vn = _v_basis.get_vertex_index(vi); 00193 00194 LMatrix4 geom; 00195 memset(&geom, 0, sizeof(geom)); 00196 00197 for (int uni = 0; uni < 4; uni++) { 00198 for (int vni = 0; vni < 4; vni++) { 00199 if (uni < u_order && vni < v_order) { 00200 geom(uni, vni) = _verts[verti(un + uni, vn + vni)].get_extended_vertex(d); 00201 } 00202 } 00203 } 00204 00205 LMatrix4 composed = u_basis_mat * geom * v_basis_transpose; 00206 return vvec.dot(uvec * composed) / weight; 00207 } 00208 00209 //////////////////////////////////////////////////////////////////// 00210 // Function: NurbsSurfaceResult::eval_segment_extended_points 00211 // Access: Published 00212 // Description: Simultaneously performs eval_extended_point on a 00213 // contiguous sequence of dimensions. The dimensions 00214 // evaluated are d through (d + num_values - 1); the 00215 // results are filled into the num_values elements in 00216 // the indicated result array. 00217 //////////////////////////////////////////////////////////////////// 00218 void NurbsSurfaceResult:: 00219 eval_segment_extended_points(int ui, int vi, PN_stdfloat u, PN_stdfloat v, int d, 00220 PN_stdfloat result[], int num_values) const { 00221 int i = segi(ui, vi); 00222 nassertv(i >= 0 && i < (int)_composed.size()); 00223 00224 PN_stdfloat u2 = u*u; 00225 LVecBase4 uvec(u*u2, u2, u, 1.0f); 00226 PN_stdfloat v2 = v*v; 00227 LVecBase4 vvec(v*v2, v2, v, 1.0f); 00228 00229 PN_stdfloat weight = vvec.dot(uvec * _composed[i]._w); 00230 00231 // Calculate the composition of the basis matrices and the geometry 00232 // matrix on-the-fly. 00233 const LMatrix4 &v_basis_transpose = _v_basis.get_basis(vi); 00234 const LMatrix4 &u_basis_mat = _u_basis.get_basis(ui); 00235 int u_order = _u_basis.get_order(); 00236 int v_order = _v_basis.get_order(); 00237 00238 int un = _u_basis.get_vertex_index(ui); 00239 int vn = _v_basis.get_vertex_index(vi); 00240 00241 for (int n = 0; n < num_values; n++) { 00242 LMatrix4 geom; 00243 memset(&geom, 0, sizeof(geom)); 00244 00245 for (int uni = 0; uni < 4; uni++) { 00246 for (int vni = 0; vni < 4; vni++) { 00247 if (uni < u_order && vni < v_order) { 00248 geom(uni, vni) = 00249 _verts[verti(un + uni, vn + vni)].get_extended_vertex(d + n); 00250 } 00251 } 00252 } 00253 00254 LMatrix4 composed = u_basis_mat * geom * v_basis_transpose; 00255 result[n] = vvec.dot(uvec * composed) / weight; 00256 } 00257 } 00258 00259 //////////////////////////////////////////////////////////////////// 00260 // Function: NurbsSurfaceResult::find_u_segment 00261 // Access: Private 00262 // Description: Returns the index of the segment that contains the 00263 // indicated value of t, or -1 if no segment contains 00264 // this value. 00265 //////////////////////////////////////////////////////////////////// 00266 int NurbsSurfaceResult:: 00267 find_u_segment(PN_stdfloat u) { 00268 // Trivially check the endpoints of the surface. 00269 if (u >= get_end_u()) { 00270 return _u_basis.get_num_segments() - 1; 00271 } else if (u <= get_start_u()) { 00272 return 0; 00273 } 00274 00275 // Check the last segment we searched for. Often, two consecutive 00276 // requests are for the same segment. 00277 if (_last_u_segment != -1 && (u >= _last_u_from && u < _last_u_to)) { 00278 return _last_u_segment; 00279 } 00280 00281 // Look for the segment the hard way. 00282 int segment = r_find_u_segment(u, 0, _u_basis.get_num_segments() - 1); 00283 if (segment != -1) { 00284 _last_u_segment = segment; 00285 _last_u_from = _u_basis.get_from(segment); 00286 _last_u_to = _u_basis.get_to(segment); 00287 } 00288 return segment; 00289 } 00290 00291 //////////////////////////////////////////////////////////////////// 00292 // Function: NurbsSurfaceResult::r_find_u_segment 00293 // Access: Private 00294 // Description: Recursively searches for the segment that contains 00295 // the indicated value of t by performing a binary 00296 // search. This assumes the segments are stored in 00297 // increasing order of t, and they don't overlap. 00298 //////////////////////////////////////////////////////////////////// 00299 int NurbsSurfaceResult:: 00300 r_find_u_segment(PN_stdfloat u, int top, int bot) const { 00301 if (bot < top) { 00302 // Not found. 00303 return -1; 00304 } 00305 int mid = (top + bot) / 2; 00306 nassertr(mid >= 0 && mid < _u_basis.get_num_segments(), -1); 00307 00308 PN_stdfloat from = _u_basis.get_from(mid); 00309 PN_stdfloat to = _u_basis.get_to(mid); 00310 if (from > u) { 00311 // Too high, try lower. 00312 return r_find_u_segment(u, top, mid - 1); 00313 00314 } else if (to <= u) { 00315 // Too low, try higher. 00316 return r_find_u_segment(u, mid + 1, bot); 00317 00318 } else { 00319 // Here we are! 00320 return mid; 00321 } 00322 } 00323 00324 00325 //////////////////////////////////////////////////////////////////// 00326 // Function: NurbsSurfaceResult::find_v_segment 00327 // Access: Private 00328 // Description: Returns the index of the segment that contains the 00329 // indicated value of t, or -1 if no segment contains 00330 // this value. 00331 //////////////////////////////////////////////////////////////////// 00332 int NurbsSurfaceResult:: 00333 find_v_segment(PN_stdfloat v) { 00334 // Trivially check the endpoints of the surface. 00335 if (v >= get_end_v()) { 00336 return _v_basis.get_num_segments() - 1; 00337 } else if (v <= get_start_v()) { 00338 return 0; 00339 } 00340 00341 // Check the last segment we searched for. Often, two consecutive 00342 // requests are for the same segment. 00343 if (_last_v_segment != -1 && (v >= _last_v_from && v < _last_v_to)) { 00344 return _last_v_segment; 00345 } 00346 00347 // Look for the segment the hard way. 00348 int segment = r_find_v_segment(v, 0, _v_basis.get_num_segments() - 1); 00349 if (segment != -1) { 00350 _last_v_segment = segment; 00351 _last_v_from = _v_basis.get_from(segment); 00352 _last_v_to = _v_basis.get_to(segment); 00353 } 00354 return segment; 00355 } 00356 00357 //////////////////////////////////////////////////////////////////// 00358 // Function: NurbsSurfaceResult::r_find_v_segment 00359 // Access: Private 00360 // Description: Recursively searches for the segment that contains 00361 // the indicated value of t by performing a binary 00362 // search. This assumes the segments are stored in 00363 // increasing order of t, and they don't overlap. 00364 //////////////////////////////////////////////////////////////////// 00365 int NurbsSurfaceResult:: 00366 r_find_v_segment(PN_stdfloat v, int top, int bot) const { 00367 if (bot < top) { 00368 // Not found. 00369 return -1; 00370 } 00371 int mid = (top + bot) / 2; 00372 nassertr(mid >= 0 && mid < _v_basis.get_num_segments(), -1); 00373 00374 PN_stdfloat from = _v_basis.get_from(mid); 00375 PN_stdfloat to = _v_basis.get_to(mid); 00376 if (from > v) { 00377 // Too high, try lower. 00378 return r_find_v_segment(v, top, mid - 1); 00379 00380 } else if (to <= v) { 00381 // Too low, try higher. 00382 return r_find_v_segment(v, mid + 1, bot); 00383 00384 } else { 00385 // Here we are! 00386 return mid; 00387 } 00388 } 00389