Panda3D
 All Classes Functions Variables Enumerations
parametricCurve.cxx
1 // Filename: parametricCurve.cxx
2 // Created by: drose (04Mar01)
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 "parametricCurve.h"
16 #include "config_parametrics.h"
17 #include "hermiteCurve.h"
18 #include "nurbsCurve.h"
19 
20 #include "datagram.h"
21 #include "datagramIterator.h"
22 #include "bamWriter.h"
23 #include "bamReader.h"
24 #include "omniBoundingVolume.h"
25 
26 static const PN_stdfloat tolerance_divisor = 100000.0f;
27 
28 TypeHandle ParametricCurve::_type_handle;
29 
30 
31 ////////////////////////////////////////////////////////////////////
32 // Function: ParametricCurve::Constructor
33 // Access: Public
34 // Description: This is a virtual base class. Don't try to construct
35 // one from Scheme.
36 ////////////////////////////////////////////////////////////////////
38 ParametricCurve() : PandaNode("curve") {
39  _curve_type = PCT_NONE;
40  _num_dimensions = 3;
41 }
42 
43 ////////////////////////////////////////////////////////////////////
44 // Function: ParametricCurve::Destructor
45 // Access: Protected
46 // Description:
47 ////////////////////////////////////////////////////////////////////
48 ParametricCurve::
49 ~ParametricCurve() {
50  // Our drawer list must be empty by the time we destruct, since our
51  // drawers all maintain reference-counting pointers to us! If this
52  // is not so, we have lost a reference count somewhere, or we have
53  // gotten confused about which drawers we're registered to.
54  nassertv(_drawers.empty());
55 }
56 
57 ////////////////////////////////////////////////////////////////////
58 // Function: ParametricCurve::safe_to_flatten
59 // Access: Public, Virtual
60 // Description: Returns true if it is generally safe to flatten out
61 // this particular kind of PandaNode by duplicating
62 // instances, false otherwise (for instance, a Camera
63 // cannot be safely flattened, because the Camera
64 // pointer itself is meaningful).
65 ////////////////////////////////////////////////////////////////////
67 safe_to_flatten() const {
68  return false;
69 }
70 
71 ////////////////////////////////////////////////////////////////////
72 // Function: ParametricCurve::safe_to_transform
73 // Access: Public, Virtual
74 // Description: Returns true if it is generally safe to transform
75 // this particular kind of PandaNode by calling the
76 // xform() method, false otherwise. For instance, it's
77 // usually a bad idea to attempt to xform a Character.
78 ////////////////////////////////////////////////////////////////////
81  return false;
82 }
83 
84 ////////////////////////////////////////////////////////////////////
85 // Function: ParametricCurve::is_valid
86 // Access: Published, Virtual
87 // Description: Returns true if the curve is defined. This base
88 // class function always returns true; derived classes
89 // might override this to sometimes return false.
90 ////////////////////////////////////////////////////////////////////
92 is_valid() const {
93  return true;
94 }
95 
96 
97 ////////////////////////////////////////////////////////////////////
98 // Function: ParametricCurve::get_max_t
99 // Access: Published, Virtual
100 // Description: Returns the upper bound of t for the entire curve.
101 // The curve is defined in the range 0.0f <= t <=
102 // get_max_t(). This base class function always returns
103 // 1.0f; derived classes might override this to return
104 // something else.
105 ////////////////////////////////////////////////////////////////////
106 PN_stdfloat ParametricCurve::
107 get_max_t() const {
108  return 1.0f;
109 }
110 
111 
112 ////////////////////////////////////////////////////////////////////
113 // Function: ParametricCurve::set_curve_type
114 // Access: Published
115 // Description: Sets the flag indicating the use to which the curve
116 // is intended to be put. This flag is optional and
117 // only serves to provide a hint to the egg reader and
118 // writer code; it has no effect on the curve's
119 // behavior.
120 //
121 // Setting the curve type also sets the num_dimensions
122 // to 3 or 1 according to the type.
123 //
124 // THis flag may have one of the values PCT_XYZ,
125 // PCT_HPR, or PCT_T.
126 ////////////////////////////////////////////////////////////////////
128 set_curve_type(int type) {
129  _curve_type = type;
130  switch (_curve_type) {
131  case PCT_XYZ:
132  case PCT_HPR:
133  case PCT_NONE:
134  _num_dimensions = 3;
135  break;
136 
137  case PCT_T:
138  _num_dimensions = 1;
139  break;
140 
141  default:
142  assert(0);
143  }
144 }
145 
146 ////////////////////////////////////////////////////////////////////
147 // Function: ParametricCurve::get_curve_type
148 // Access: Published
149 // Description: Returns the flag indicating the use to which the curve
150 // is intended to be put.
151 ////////////////////////////////////////////////////////////////////
153 get_curve_type() const {
154  return _curve_type;
155 }
156 
157 ////////////////////////////////////////////////////////////////////
158 // Function: ParametricCurve::set_num_dimensions
159 // Access: Published
160 // Description: Specifies the number of significant dimensions in the
161 // curve's vertices. This should be one of 1, 2, or 3.
162 // Normally, XYZ and HPR curves have three dimensions;
163 // time curves should always have one dimension. This
164 // only serves as a hint to the mopath editor, and also
165 // controls how the curve is written out.
166 ////////////////////////////////////////////////////////////////////
169  _num_dimensions = num;
170 }
171 
172 ////////////////////////////////////////////////////////////////////
173 // Function: ParametricCurve::get_num_dimensions
174 // Access: Published
175 // Description: Returns the number of significant dimensions in the
176 // curve's vertices, as set by a previous call to
177 // set_num_dimensions(). This is only a hint as to how
178 // the curve is intended to be used; the actual number
179 // of dimensions of any curve is always three.
180 ////////////////////////////////////////////////////////////////////
183  return _num_dimensions;
184 }
185 
186 
187 ////////////////////////////////////////////////////////////////////
188 // Function: ParametricCurve::calc_length
189 // Access: Published
190 // Description: Approximates the length of the entire curve to within
191 // a few decimal places.
192 ////////////////////////////////////////////////////////////////////
193 PN_stdfloat ParametricCurve::
194 calc_length() const {
195  return calc_length(0.0f, get_max_t());
196 }
197 
198 ////////////////////////////////////////////////////////////////////
199 // Function: ParametricCurve::calc_length
200 // Access: Published
201 // Description: Approximates the length of the curve segment from
202 // parametric time 'from' to time 'to'.
203 ////////////////////////////////////////////////////////////////////
204 PN_stdfloat ParametricCurve::
205 calc_length(PN_stdfloat from, PN_stdfloat to) const {
206  PN_stdfloat t1, t2;
207  LPoint3 p1, p2;
208 
209  // Normally we expect from < to. If they came in backwards, reverse
210  // them.
211  PN_stdfloat to_minus_from = to - from;
212 
213  if (to_minus_from < 0.0f) {
214  PN_stdfloat temp = to;
215  to = from;
216  from = temp;
217  to_minus_from=-to_minus_from;
218  }
219 
220  // Start with a segment for each unit of t.
221  int num_segs = (int)(to_minus_from) + 1;
222  t2 = from;
223  get_point(t2, p2);
224  PN_stdfloat net = 0.0f;
225 
226  for (int i = 1; i <= num_segs; i++) {
227  t1 = t2;
228  p1 = p2;
229 
230  t2 = (to - from) * (PN_stdfloat)i / (PN_stdfloat)num_segs + from;
231  get_point(t2, p2);
232 
233  net += r_calc_length(t1, t2, p1, p2, (p1 - p2).length());
234  }
235  return net;
236 }
237 
238 ////////////////////////////////////////////////////////////////////
239 // Function: ParametricCurve::find_length
240 // Access: Published
241 // Description: Returns the parametric value corresponding to the
242 // indicated distance along the curve from the starting
243 // parametric value.
244 //
245 // This is the inverse of calc_length(): rather than
246 // determining the length along the curve between two
247 // parametric points, it determines the position in
248 // parametric time of a point n units along the curve.
249 //
250 // The search distance must not be negative.
251 ////////////////////////////////////////////////////////////////////
252 PN_stdfloat ParametricCurve::
253 find_length(PN_stdfloat start_t, PN_stdfloat length_offset) const {
254  nassertr(length_offset >= 0.0f, start_t);
255  nassertr(start_t >= 0.0f && start_t <= get_max_t(), start_t);
256 
257  PN_stdfloat t1, t2;
258  LPoint3 p1, p2;
259 
260  // Start with a segment for each unit of t.
261  PN_stdfloat max_t = get_max_t();
262  int num_segs = (int)cfloor(max_t - start_t + 1);
263  t2 = start_t;
264  get_point(t2, p2);
265  PN_stdfloat net = 0.0f;
266 
267  for (int i = 1; i <= num_segs; i++) {
268  assert(net <= length_offset);
269 
270  t1 = t2;
271  p1 = p2;
272 
273  t2 = start_t + (((max_t - start_t) * (PN_stdfloat)i) / (PN_stdfloat)num_segs);
274  get_point(t2, p2);
275 
276  PN_stdfloat seglength = (p1 - p2).length();
277  PN_stdfloat result;
278 
279  if (r_find_length(length_offset - net, result,
280  t1, t2, p1, p2, seglength)) {
281  // Found it!
282  return result;
283  }
284 
285  net += seglength;
286  }
287 
288  // Not on the curve? Huh.
289  return max_t;
290 }
291 
292 ////////////////////////////////////////////////////////////////////
293 // Function: ParametricCurve::adjust_point
294 // Access: Published, Virtual
295 // Description: Recomputes the curve such that it passes through the
296 // point (px, py, pz) at time t, but keeps the same
297 // tangent value at that point.
298 ////////////////////////////////////////////////////////////////////
300 adjust_point(PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat) {
301  return false;
302 }
303 
304 ////////////////////////////////////////////////////////////////////
305 // Function: ParametricCurve::adjust_tangent
306 // Access: Published, Virtual
307 // Description: Recomputes the curve such that it has the tangent
308 // (tx, ty, tz) at time t, but keeps the same position
309 // at the point.
310 ////////////////////////////////////////////////////////////////////
312 adjust_tangent(PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat) {
313  return false;
314 }
315 
316 ////////////////////////////////////////////////////////////////////
317 // Function: ParametricCurve::adjust_pt
318 // Access: Published, Virtual
319 // Description: Recomputes the curve such that it passes through the
320 // point (px, py, pz) with the tangent (tx, ty, tz).
321 ////////////////////////////////////////////////////////////////////
323 adjust_pt(PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat, PN_stdfloat) {
324  return false;
325 }
326 
327 ////////////////////////////////////////////////////////////////////
328 // Function: ParametricCurve::recompute
329 // Access: Published, Virtual
330 // Description: Recalculates the curve, if necessary. Returns
331 // true if the resulting curve is valid, false
332 // otherwise.
333 ////////////////////////////////////////////////////////////////////
336  return is_valid();
337 }
338 
339 ////////////////////////////////////////////////////////////////////
340 // Function: ParametricCurve::stitch
341 // Access: Published, Virtual
342 // Description: Regenerates this curve as one long curve: the first
343 // curve connected end-to-end with the second one.
344 // Either a or b may be the same as 'this'.
345 //
346 // Returns true if successful, false on failure or if
347 // the curve type does not support stitching.
348 ////////////////////////////////////////////////////////////////////
351  parametrics_cat.error()
352  << get_type() << " does not support stitching.\n";
353  return false;
354 }
355 
356 
357 ////////////////////////////////////////////////////////////////////
358 // Function: ParametricCurve::write_egg
359 // Access: Published
360 // Description: Writes an egg description of the nurbs curve to the
361 // specified output file. Returns true if the file is
362 // successfully written.
363 ////////////////////////////////////////////////////////////////////
365 write_egg(Filename filename, CoordinateSystem cs) {
366  pofstream out;
367  filename.set_text();
368 
369  if (!filename.open_write(out)) {
370  parametrics_cat.error()
371  << "Unable to write to " << filename << "\n";
372  return false;
373  }
374  return write_egg(out, filename, cs);
375 }
376 
377 ////////////////////////////////////////////////////////////////////
378 // Function: ParametricCurve::write_egg
379 // Access: Published
380 // Description: Writes an egg description of the nurbs curve to the
381 // specified output stream. Returns true if the file is
382 // successfully written.
383 ////////////////////////////////////////////////////////////////////
385 write_egg(ostream &out, const Filename &filename, CoordinateSystem cs) {
386  string curve_type;
387  switch (get_curve_type()) {
388  case PCT_XYZ:
389  curve_type = "xyz";
390  break;
391 
392  case PCT_HPR:
393  curve_type = "hpr";
394  break;
395 
396  case PCT_T:
397  curve_type = "t";
398  break;
399  }
400 
401  if (!has_name()) {
402  // If we don't have a name, come up with one.
403  string name = filename.get_basename_wo_extension();
404 
405  if (!curve_type.empty()) {
406  name += "_";
407  name += curve_type;
408  }
409 
410  set_name(name);
411  }
412 
413  if (cs == CS_default) {
414  cs = get_default_coordinate_system();
415  }
416 
417  if (cs != CS_invalid) {
418  out << "<CoordinateSystem> { ";
419  switch (cs) {
420  case CS_zup_right:
421  out << "Z-Up";
422  break;
423 
424  case CS_yup_right:
425  out << "Y-Up";
426  break;
427 
428  case CS_zup_left:
429  out << "Z-Up-Left";
430  break;
431 
432  case CS_yup_left:
433  out << "Y-Up-Left";
434  break;
435 
436  default:
437  break;
438  }
439  out << " }\n\n";
440  }
441 
442 
443  if (!format_egg(out, get_name(), curve_type, 0)) {
444  return false;
445  }
446 
447  if (out) {
448  return true;
449  } else {
450  return false;
451  }
452 }
453 
454 
455 
456 ////////////////////////////////////////////////////////////////////
457 // Function: ParametricCurve::get_bezier_segs
458 // Access: Public, Virtual
459 // Description: Fills up the indicated vector with a list of
460 // BezierSeg structs that describe the curve. This
461 // assumes the curve is a PiecewiseCurve of
462 // CubicCurvesegs. Returns true if successful, false
463 // otherwise.
464 ////////////////////////////////////////////////////////////////////
467  return false;
468 }
469 
470 ////////////////////////////////////////////////////////////////////
471 // Function: ParametricCurve::get_bezier_seg
472 // Access: Public, Virtual
473 // Description: Fills the BezierSeg structure with a description of
474 // the curve segment as a Bezier, if possible, but does
475 // not change the _t member of the structure. Returns
476 // true if successful, false otherwise.
477 ////////////////////////////////////////////////////////////////////
480  return false;
481 }
482 
483 ////////////////////////////////////////////////////////////////////
484 // Function: ParametricCurve::get_nurbs_interface
485 // Access: Public, Virtual
486 // Description: Returns a pointer to the object as a
487 // NurbsCurveInterface object if it happens to be a
488 // NURBS-style curve; otherwise, returns NULL.
489 ////////////////////////////////////////////////////////////////////
492  return (NurbsCurveInterface *)NULL;
493 }
494 
495 ////////////////////////////////////////////////////////////////////
496 // Function: ParametricCurve::convert_to_hermite
497 // Access: Public, Virtual
498 // Description: Stores an equivalent curve representation in the
499 // indicated Hermite curve, if possible. Returns true
500 // if successful, false otherwise.
501 ////////////////////////////////////////////////////////////////////
504  BezierSegs bz_segs;
505  if (!get_bezier_segs(bz_segs)) {
506  return false;
507  }
508 
509  hc->set_curve_type(_curve_type);
510 
511  // Now convert the Bezier segments to a Hermite. Normally, the
512  // Beziers will match up head-to-tail, but if they don't, that's a
513  // cut.
514  hc->remove_all_cvs();
515 
516  int i, n;
517  if (!bz_segs.empty()) {
518  PN_stdfloat scale_in = 0.0f;
519  PN_stdfloat scale_out = bz_segs[0]._t;
520  n = hc->append_cv(HC_SMOOTH, bz_segs[0]._v[0]);
521  hc->set_cv_out(n, 3.0f * (bz_segs[0]._v[1] - bz_segs[0]._v[0]) / scale_out);
522 
523  for (i = 0; i < (int)bz_segs.size()-1; i++) {
524  scale_in = scale_out;
525  scale_out = bz_segs[i+1]._t - bz_segs[i]._t;
526 
527  if (!bz_segs[i]._v[3].almost_equal(bz_segs[i+1]._v[0], 0.0001f)) {
528  // Oops, we have a cut.
529  hc->set_cv_type(n, HC_CUT);
530  }
531 
532  n = hc->append_cv(HC_FREE, bz_segs[i+1]._v[0]);
533  hc->set_cv_in(n, 3.0f * (bz_segs[i]._v[3] - bz_segs[i]._v[2]) / scale_in);
534  hc->set_cv_tstart(n, bz_segs[i]._t);
535 
536  hc->set_cv_out(n, 3.0f * (bz_segs[i+1]._v[1] - bz_segs[i+1]._v[0]) / scale_out);
537  }
538 
539  // Now the last CV.
540  scale_in = scale_out;
541  i = bz_segs.size()-1;
542  n = hc->append_cv(HC_SMOOTH, bz_segs[i]._v[3]);
543  hc->set_cv_in(n, 3.0f * (bz_segs[i]._v[3] - bz_segs[i]._v[2]) / scale_in);
544  hc->set_cv_tstart(n, bz_segs[i]._t);
545  }
546 
547  // Finally, go through and figure out which CV's are smooth or G1.
548  int num_cvs = hc->get_num_cvs();
549  for (n = 1; n < num_cvs-1; n++) {
550  if (hc->get_cv_type(n)!=HC_CUT) {
551  LVector3 in = hc->get_cv_in(n);
552  LVector3 out = hc->get_cv_out(n);
553 
554  if (in.almost_equal(out, 0.0001f)) {
555  hc->set_cv_type(n, HC_SMOOTH);
556  } else {
557  in.normalize();
558  out.normalize();
559  if (in.almost_equal(out, 0.0001f)) {
560  hc->set_cv_type(n, HC_G1);
561  }
562  }
563  }
564  }
565  return true;
566 }
567 
568 ////////////////////////////////////////////////////////////////////
569 // Function: ParametricCurve::convert_to_nurbs
570 // Access: Public, Virtual
571 // Description: Stores in the indicated NurbsCurve a NURBS
572 // representation of an equivalent curve. Returns true
573 // if successful, false otherwise.
574 ////////////////////////////////////////////////////////////////////
578  nassertr(nurbs != (NurbsCurveInterface *)NULL, false);
579 
580  BezierSegs bz_segs;
581  if (!get_bezier_segs(bz_segs)) {
582  return false;
583  }
584 
585  nc->set_curve_type(_curve_type);
586 
587  nurbs->remove_all_cvs();
588  nurbs->set_order(4);
589  if (!bz_segs.empty()) {
590  int i;
591  for (i = 0; i < (int)bz_segs.size(); i++) {
592  nurbs->append_cv(bz_segs[i]._v[0]);
593  nurbs->append_cv(bz_segs[i]._v[1]);
594  nurbs->append_cv(bz_segs[i]._v[2]);
595  if (i == (int)bz_segs.size()-1 ||
596  !bz_segs[i]._v[3].almost_equal(bz_segs[i+1]._v[0], 0.0001f)) {
597  nurbs->append_cv(bz_segs[i]._v[3]);
598  }
599  }
600 
601  PN_stdfloat t;
602  int ki = 4;
603  nurbs->set_knot(0, 0.0f);
604  nurbs->set_knot(1, 0.0f);
605  nurbs->set_knot(2, 0.0f);
606  nurbs->set_knot(3, 0.0f);
607 
608  for (i = 0; i < (int)bz_segs.size(); i++) {
609  t = bz_segs[i]._t;
610 
611  nurbs->set_knot(ki, t);
612  nurbs->set_knot(ki+1, t);
613  nurbs->set_knot(ki+2, t);
614  ki += 3;
615  if (i == ((int)bz_segs.size())-1 ||
616  !bz_segs[i]._v[3].almost_equal(bz_segs[i+1]._v[0], 0.0001f)) {
617  nurbs->set_knot(ki, t);
618  ki++;
619  }
620  }
621  }
622 
623  return nc->recompute();
624 }
625 
626 
627 ////////////////////////////////////////////////////////////////////
628 // Function: ParametricCurve::register_drawer
629 // Access: Public
630 // Description: Registers a Drawer with this curve that will
631 // automatically be updated whenever the curve is
632 // modified, so that the visible representation of the
633 // curve is kept up to date. This is called
634 // automatically by the ParametricCurveDrawer.
635 //
636 // Any number of Drawers may be registered with a
637 // particular curve.
638 ////////////////////////////////////////////////////////////////////
640 register_drawer(ParametricCurveDrawer *drawer) {
641  _drawers.push_back(drawer);
642 }
643 
644 ////////////////////////////////////////////////////////////////////
645 // Function: ParametricCurve::unregister_drawer
646 // Access: Public
647 // Description: Removes a previously registered drawer from the list
648 // of automatically-refreshed drawers. This is called
649 // automatically by the ParametricCurveDrawer.
650 ////////////////////////////////////////////////////////////////////
652 unregister_drawer(ParametricCurveDrawer *drawer) {
653  _drawers.remove(drawer);
654 }
655 
656 
657 
658 
659 ////////////////////////////////////////////////////////////////////
660 // Function: ParametricCurve::invalidate
661 // Access: Protected
662 // Description: Called from a base class to mark a section of the
663 // curve that has been modified and must be redrawn or
664 // recomputed in some way.
665 ////////////////////////////////////////////////////////////////////
666 void ParametricCurve::
667 invalidate(PN_stdfloat, PN_stdfloat) {
668  invalidate_all();
669 }
670 
671 ////////////////////////////////////////////////////////////////////
672 // Function: ParametricCurve::invalidate_all
673 // Access: Protected
674 // Description: Called from a base class to indicate that the curve
675 // has changed in some substantial way and must be
676 // entirely redrawn.
677 ////////////////////////////////////////////////////////////////////
678 void ParametricCurve::
679 invalidate_all() {
680  /*
681  DrawerList::iterator n;
682  for (n = _drawers.begin();
683  n != _drawers.end();
684  ++n) {
685  (*n)->redraw();
686  }
687  */
688 }
689 
690 ////////////////////////////////////////////////////////////////////
691 // Function: ParametricCurve::format_egg
692 // Access: Protected, Virtual
693 // Description: Formats the curve as an egg structure to write to the
694 // indicated stream. Returns true on success, false on
695 // failure.
696 ////////////////////////////////////////////////////////////////////
697 bool ParametricCurve::
698 format_egg(ostream &, const string &, const string &, int) const {
699  return false;
700 }
701 
702 
703 ////////////////////////////////////////////////////////////////////
704 // Function: ParametricCurve::r_calc_length
705 // Access: Private
706 // Description: The recursive implementation of calc_length. This
707 // function calculates the length of a segment of the
708 // curve between points t1 and t2, which presumably
709 // evaluate to the endpoints p1 and p2, and the segment
710 // has the length seglength.
711 ////////////////////////////////////////////////////////////////////
712 PN_stdfloat ParametricCurve::
713 r_calc_length(PN_stdfloat t1, PN_stdfloat t2, const LPoint3 &p1, const LPoint3 &p2,
714  PN_stdfloat seglength) const {
715  static const PN_stdfloat length_tolerance = 0.0000001f;
716  static const PN_stdfloat t_tolerance = 0.000001f;
717 
718  if (t2 - t1 < t_tolerance) {
719  // Stop recursing--we've just walked off the limit for
720  // representing smaller values of t.
721  return 0.0f;
722  }
723 
724  PN_stdfloat tmid;
725  LPoint3 pmid;
726  PN_stdfloat left, right;
727 
728  // Calculate the point on the curve midway between the two
729  // endpoints.
730  tmid = (t1+t2)*0.5f;
731  get_point(tmid, pmid);
732 
733  // Did we increase the length of the segment measurably?
734  left = (p1 - pmid).length();
735  right = (pmid - p2).length();
736 
737  if ((left + right) - seglength < length_tolerance) {
738  // No. We're done.
739  return seglength;
740  } else {
741  // Yes. Keep going.
742  return r_calc_length(t1, tmid, p1, pmid, left) +
743  r_calc_length(tmid, t2, pmid, p2, right);
744  }
745 }
746 
747 ////////////////////////////////////////////////////////////////////
748 // Function: ParametricCurve::r_find_length
749 // Access: Private
750 // Description: The recursive implementation of find_length. This is
751 // similar to r_calc_length, above. target_length is
752 // the length along the curve past t1 that we hope to
753 // find. If the indicated target_length falls within
754 // this segment, returns true and sets found_t to the
755 // point along the segment. Otherwise, updates
756 // seglength with the accurate calculated length of the
757 // segment and returns false.
758 ////////////////////////////////////////////////////////////////////
759 bool ParametricCurve::
760 r_find_length(PN_stdfloat target_length, PN_stdfloat &found_t,
761  PN_stdfloat t1, PN_stdfloat t2,
762  const LPoint3 &p1, const LPoint3 &p2,
763  PN_stdfloat &seglength) const {
764  static const PN_stdfloat length_tolerance = 0.0000001f;
765  static const PN_stdfloat t_tolerance = 0.000001f;
766 
767  if (target_length < t_tolerance) {
768  // Stop recursing--we've just walked off the limit for
769  // representing smaller values of t.
770  found_t = t1;
771  return true;
772 
773  }
774 
775  PN_stdfloat tmid;
776  LPoint3 pmid;
777  PN_stdfloat left, right;
778 
779  // Calculate the point on the curve midway between the two
780  // endpoints.
781  tmid = (t1+t2)*0.5f;
782  get_point(tmid, pmid);
783 
784  // Did we increase the length of the segment measurably?
785  left = (p1 - pmid).length();
786  right = (pmid - p2).length();
787 
788  if ((left + right) - seglength < length_tolerance) {
789  // No. Curve is relatively straight over this interval.
790  return find_t_linear(target_length, found_t, t1, t2, p1, p2);
791  /*
792  if (target_length <= seglength) {
793  // Compute t value that corresponds to target_length
794  // Maybe the point is in the left half of the segment?
795  if (r_find_t(target_length, found_t, t1, tmid, p1, pmid)) {
796  return true;
797  }
798  // Maybe it's on the right half?
799  if (r_find_t(target_length - left, found_t, tmid, t2, pmid, p2)) {
800  return true;
801  }
802  }
803  return false;
804  */
805  } else {
806  // Yes. Keep going.
807 
808  // Maybe the point is in the left half of the segment?
809  if (r_find_length(target_length, found_t, t1, tmid, p1, pmid, left)) {
810  return true;
811  }
812 
813  // Maybe it's on the right half?
814  if (r_find_length(target_length - left, found_t, tmid, t2, pmid, p2, right)) {
815  return true;
816  }
817 
818  // Neither. Keep going.
819  seglength = left + right;
820  return false;
821  }
822 }
823 
824 
825 
826 ////////////////////////////////////////////////////////////////////
827 // Function: ParametricCurve::r_find_t
828 // Access: Private
829 // Description: computes the t value in the parametric domain of a
830 // target point along a straight section of a curve.
831 // This is similar to r_calc_length, above.
832 // target_length is the length along the curve past t1
833 // that we hope to find. If the indicated target_length
834 // falls within this segment, returns true and sets
835 // found_t to the point along the segment.
836 ////////////////////////////////////////////////////////////////////
837 bool ParametricCurve::
838 r_find_t(PN_stdfloat target_length, PN_stdfloat &found_t,
839  PN_stdfloat t1, PN_stdfloat t2,
840  const LPoint3 &p1, const LPoint3 &p2) const {
841  static const PN_stdfloat length_tolerance = 0.0001f;
842  static const PN_stdfloat t_tolerance = 0.0001f;
843 
844  if (parametrics_cat.is_spam()) {
845  parametrics_cat.spam()
846  << "target_length " << target_length << " t1 " << t1 << " t2 " << t2 << "\n";
847  }
848 
849  // Is the target point close to the near endpoint
850  if (target_length < length_tolerance) {
851  found_t = t1;
852  return true;
853  }
854 
855  // No, compute distance between two endpoints
856  PN_stdfloat point_dist;
857  point_dist = (p2 - p1).length();
858 
859  // Is the target point past the far endpoint?
860  if (point_dist < target_length) {
861  return false;
862  }
863 
864  // Is the target point close to far endpoint?
865  if ( (point_dist - target_length ) < length_tolerance ) {
866  found_t = t2;
867  return true;
868  }
869 
870  // are we running out of parametric precision?
871  if ((t2 - t1) < t_tolerance) {
872  found_t = t1;
873  return true;
874  }
875 
876  // No, subdivide and continue
877  PN_stdfloat tmid;
878  LPoint3 pmid;
879  PN_stdfloat left;
880 
881  // Calculate the point on the curve midway between the two
882  // endpoints.
883  tmid = (t1+t2)*0.5f;
884  get_point(tmid, pmid);
885 
886  // Maybe the point is in the left half of the segment?
887  if (r_find_t(target_length, found_t, t1, tmid, p1, pmid)) {
888  return true;
889  }
890  // Nope, must be in the right half
891  left = (p1 - pmid).length();
892  if (r_find_t(target_length - left, found_t, tmid, t2, pmid, p2)) {
893  return true;
894  }
895 
896  // not found in either half, keep looking
897  return false;
898 }
899 
900 
901 ////////////////////////////////////////////////////////////////////
902 // Function: ParametricCurve::find_t_linear
903 // Access: Private
904 // Description: non-recursive version of r_find_t (see above)
905 ////////////////////////////////////////////////////////////////////
906 bool ParametricCurve::
907 find_t_linear(PN_stdfloat target_length, PN_stdfloat &found_t,
908  PN_stdfloat t1, PN_stdfloat t2,
909  const LPoint3 &p1, const LPoint3 &p2) const {
910  const PN_stdfloat length_tolerance = (p1-p2).length()/tolerance_divisor;
911  const PN_stdfloat t_tolerance = (t1+t2)/tolerance_divisor;
912 
913  if (parametrics_cat.is_spam()) {
914  parametrics_cat.spam()
915  << "target_length " << target_length << " t1 " << t1 << " t2 " << t2 << "\n";
916  }
917 
918  // first, check to make sure this segment contains the point
919  // we're looking for
920  if (target_length > (p1 - p2).length()) {
921  // segment is too short
922  return false;
923  }
924 
925  PN_stdfloat tleft = t1;
926  PN_stdfloat tright = t2;
927  PN_stdfloat tmid;
928  LPoint3 pmid;
929  PN_stdfloat len;
930 
931  while (1) {
932  tmid = (tleft + tright) * 0.5f;
933  get_point(tmid, pmid);
934  len = (pmid - p1).length();
935 
936  /*
937  if (parametrics_cat.is_spam()) {
938  parametrics_cat.spam()
939  << "tleft " << tleft << " tright " << tright <<
940  " tmid " << tmid << " len " << len << endl;
941  }
942  */
943 
944  // is our midpoint at the right distance?
945  if (fabs(len - target_length) < length_tolerance) {
946  found_t = tmid;
947  return true;
948  }
949 
950  /*
951  if (parametrics_cat.is_spam()) {
952  parametrics_cat.spam()
953  << "tright-tleft " << tright-tleft << " t_tolerance " << t_tolerance << endl;
954  }
955  */
956 
957  // are we out of parametric precision?
958  if ((tright - tleft) < t_tolerance) {
959  // unfortunately, we can't get any closer in parametric space
960  found_t = tmid;
961  return true;
962  }
963 
964  // should we look closer or farther?
965  if (len > target_length) {
966  // look closer
967  tright = tmid;
968  } else {
969  // look farther
970  tleft = tmid;
971  }
972  }
973 }
974 
975 
976 ////////////////////////////////////////////////////////////////////
977 // Function: ParametricCurve::write_datagram
978 // Access: Protected, Virtual
979 // Description: Function to write the important information in
980 // the particular object to a Datagram
981 ////////////////////////////////////////////////////////////////////
982 void ParametricCurve::
983 write_datagram(BamWriter *manager, Datagram &me) {
984  PandaNode::write_datagram(manager, me);
985 
986  me.add_int8(_curve_type);
987  me.add_int8(_num_dimensions);
988 }
989 
990 ////////////////////////////////////////////////////////////////////
991 // Function: ParametricCurve::fillin
992 // Access: Protected
993 // Description: Function that reads out of the datagram (or asks
994 // manager to read) all of the data that is needed to
995 // re-create this object and stores it in the appropiate
996 // place
997 ////////////////////////////////////////////////////////////////////
998 void ParametricCurve::
999 fillin(DatagramIterator &scan, BamReader *manager) {
1000  PandaNode::fillin(scan, manager);
1001 
1002  _curve_type = scan.get_int8();
1003  _num_dimensions = scan.get_int8();
1004 }
PN_int8 get_int8()
Extracts a signed 8-bit integer.
virtual bool convert_to_nurbs(ParametricCurve *nc) const
Stores in the indicated NurbsCurve a NURBS representation of an equivalent curve. ...
A basic node of the scene graph or data graph.
Definition: pandaNode.h:72
int get_num_dimensions() const
Returns the number of significant dimensions in the curve&#39;s vertices, as set by a previous call to se...
int get_num_cvs() const
Returns the number of CV&#39;s in the curve.
virtual bool adjust_point(PN_stdfloat t, PN_stdfloat px, PN_stdfloat py, PN_stdfloat pz)
Recomputes the curve such that it passes through the point (px, py, pz) at time t, but keeps the same tangent value at that point.
virtual void write_datagram(BamWriter *manager, Datagram &dg)
Writes the contents of this object to the datagram for shipping out to a Bam file.
Definition: pandaNode.cxx:4164
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:122
A virtual base class for parametric curves.
void add_int8(PN_int8 value)
Adds a signed 8-bit integer to the datagram.
Definition: datagram.I:128
bool set_cv_out(int n, PN_stdfloat x, PN_stdfloat y, PN_stdfloat z)
Changes the given CV&#39;s out tangent.
virtual bool recompute()
Recalculates the curve, if necessary.
int get_curve_type() const
Returns the flag indicating the use to which the curve is intended to be put.
ParametricCurve()
This is a virtual base class.
void register_drawer(ParametricCurveDrawer *drawer)
Registers a Drawer with this curve that will automatically be updated whenever the curve is modified...
int append_cv(int type, PN_stdfloat x, PN_stdfloat y, PN_stdfloat z)
Adds a new CV to the end of the curve.
void set_text()
Indicates that the filename represents a text file.
Definition: filename.I:507
bool write_egg(Filename filename, CoordinateSystem cs=CS_default)
Writes an egg description of the nurbs curve to the specified output file.
virtual bool safe_to_flatten() const
Returns true if it is generally safe to flatten out this particular kind of PandaNode by duplicating ...
virtual bool get_bezier_segs(BezierSegs &) const
Fills up the indicated vector with a list of BezierSeg structs that describe the curve.
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:100
void set_num_dimensions(int num)
Specifies the number of significant dimensions in the curve&#39;s vertices.
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
Definition: lpoint3.h:99
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition: bamWriter.h:73
virtual bool is_valid() const
Returns true if the curve is defined.
This abstract class defines the interface only for a Nurbs-style curve, with knots and coordinates in...
bool has_name() const
Returns true if the Namable has a nonempty name set, false if the name is empty.
Definition: namable.I:75
virtual NurbsCurveInterface * get_nurbs_interface()
Returns a pointer to the object as a NurbsCurveInterface object if it happens to be a NURBS-style cur...
A parametric curve defined by a sequence of control vertices, each with an in and out tangent...
Definition: hermiteCurve.h:88
virtual bool get_bezier_seg(BezierSeg &) const
Fills the BezierSeg structure with a description of the curve segment as a Bezier, if possible, but does not change the _t member of the structure.
virtual bool stitch(const ParametricCurve *a, const ParametricCurve *b)
Regenerates this curve as one long curve: the first curve connected end-to-end with the second one...
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:39
virtual PN_stdfloat get_max_t() const
Returns the upper bound of t for the entire curve.
void remove_all_cvs()
Removes all CV&#39;s from the curve.
The name of a file, such as a texture file or an Egg file.
Definition: filename.h:44
int get_cv_type(int n) const
Returns the given CV&#39;s continuity type, HC_CUT, HC_FREE, HC_G1, or HC_SMOOTH, or 0 if there is no suc...
bool set_cv_type(int n, int type)
Changes the given CV&#39;s continuity type.
virtual bool adjust_pt(PN_stdfloat t, PN_stdfloat px, PN_stdfloat py, PN_stdfloat pz, PN_stdfloat tx, PN_stdfloat ty, PN_stdfloat tz)
Recomputes the curve such that it passes through the point (px, py, pz) with the tangent (tx...
virtual bool adjust_tangent(PN_stdfloat t, PN_stdfloat tx, PN_stdfloat ty, PN_stdfloat tz)
Recomputes the curve such that it has the tangent (tx, ty, tz) at time t, but keeps the same position...
void set_curve_type(int type)
Sets the flag indicating the use to which the curve is intended to be put.
PN_stdfloat calc_length() const
Approximates the length of the entire curve to within a few decimal places.
string get_basename_wo_extension() const
Returns the basename part of the filename, without the file extension.
Definition: filename.I:460
bool set_cv_tstart(int n, PN_stdfloat tstart)
Changes the given CV&#39;s parametric starting time.
void unregister_drawer(ParametricCurveDrawer *drawer)
Removes a previously registered drawer from the list of automatically-refreshed drawers.
virtual bool convert_to_hermite(HermiteCurve *hc) const
Stores an equivalent curve representation in the indicated Hermite curve, if possible.
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
A class to retrieve the individual data elements previously stored in a Datagram. ...
const LVecBase3 & get_cv_out(int n) const
Returns the out tangent of the given CV.
bool open_write(ofstream &stream, bool truncate=true) const
Opens the indicated ifstream for writing the file, if possible.
Definition: filename.cxx:2045
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
const LVecBase3 & get_cv_in(int n) const
Returns the in tangent of the given CV.
bool set_cv_in(int n, PN_stdfloat x, PN_stdfloat y, PN_stdfloat z)
Changes the given CV&#39;s in tangent.
bool normalize()
Normalizes the vector in place.
Definition: lvecBase3.h:782
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
Definition: datagram.h:43
PN_stdfloat find_length(PN_stdfloat start_t, PN_stdfloat length_offset) const
Returns the parametric value corresponding to the indicated distance along the curve from the startin...
virtual bool safe_to_transform() const
Returns true if it is generally safe to transform this particular kind of PandaNode by calling the xf...