Revision: 17630
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=17630
Author: eman
Date: 2008-11-29 23:51:11 +0100 (Sat, 29 Nov 2008)
Log Message:
-----------
More excellent work from Laurynas Duburas
Non-destructive Refine for NURBS, works for weighted, uniform and cyclic
surfaces/curves.
Hopefully this algorithm can be propigated to reduce/increase degree functions.
Note: Currently no proper UI, just a Refine button that adds a Knot in the
middle of the surface, will eventually need interactive UI.
Modified Paths:
--------------
branches/nurbs/blender/intern/nurbana/intern/NURBS_Knot.cpp
branches/nurbs/blender/intern/nurbana/intern/NURBS_Knot.h
branches/nurbs/blender/intern/nurbana/intern/Object_Base.cpp
branches/nurbs/blender/intern/nurbana/intern/Object_Base.h
branches/nurbs/blender/intern/nurbana/intern/Object_NURBS.cpp
branches/nurbs/blender/intern/nurbana/intern/Object_NURBS.h
branches/nurbs/blender/source/blender/src/buttons_editing.c
branches/nurbs/blender/source/blender/src/editcurve.c
Modified: branches/nurbs/blender/intern/nurbana/intern/NURBS_Knot.cpp
===================================================================
--- branches/nurbs/blender/intern/nurbana/intern/NURBS_Knot.cpp 2008-11-29
22:16:23 UTC (rev 17629)
+++ branches/nurbs/blender/intern/nurbana/intern/NURBS_Knot.cpp 2008-11-29
22:51:11 UTC (rev 17630)
@@ -123,8 +123,34 @@
return(mid);
} //eof NURBS_Knot::FindSpan()
+/*
+ Searches for knot span having u.
+ If u is less than first knot value KnotVector[first], changes u's value to
KnotVector[first] and returns appropriate span.
+ If u is more than last knot value KnotVector[last], changes u's value to
KnotVector[last - 1] and returns appropriate span.
+*/
+int NURBS_Knot::FindSpanRef(nbReal &u, int first, int last, const nbReal
*KnotVector) {
+ int low = first;
+ int high = last;
+ int mid = (low + high) / 2;
+ if (u >= KnotVector [last])
+ u = KnotVector [last - 1];
+ else if (u <= KnotVector [first])
+ u = KnotVector [first];
+ while (u < KnotVector[mid] || u >= KnotVector[mid+1]) {
+ if (u < KnotVector[mid])
+ high = mid;
+ else
+ low= mid;
+ mid = (low + high) / 2;
+ } //eow
+
+ return (mid);
+} //eof NURBS_Knot::FindSpan()
+
+
+
void NURBS_Knot::Difference(nbReal *KV1, int L1, nbReal *KV2, int L2, nbReal
*KV3, int &L3) {
// Given two Knot Vectors on same domain, store difference in KV3
int KV1i,KV2i;
@@ -174,85 +200,140 @@
void NURBS_Knot::Refine(Object_NURBS *obj, nbReal *X, int r, bool UV) {
- int a,b,i,j,k,l,m,n,ind,degree;
- Point3d *Qw,*Curve;
- nbReal *Ubar,alfa;
+ int i,j,k,l,ind;
+ Point3d *Qw, *bufferQw, *Curve, *bufferCurve;
+ nbReal *Ubar, *bufferUbar, *knotVectCpy, *bufferKnotVectCpy, alfa;
+ const bool cyclic = obj -> Cyclic(UV);//for convenience
+ const int pitch = (UV ? obj -> Length(0) : obj -> Length(0) + r);
+ const int degree = obj -> Order(UV) - 1;
+ //extra space will be allocated before buffers Qw, Curve and Ubar for
cyclics
+ const int extra = cyclic ? degree : 0;
+ const int oldKnotCount = obj -> Length(UV) + obj -> Order(UV);
+ const int oldKnotCount2 = obj -> Order(UV) + obj -> getLength(UV, 1);
+ const int newKnotCount = oldKnotCount + r;
+ // knot count including virtual knots
+ const int newKnotCount2 = oldKnotCount2 + r;
+ const int newLength = obj -> Length(UV) + r;
+ const int first = cyclic ? 0 : degree;
+ const int last = cyclic ? oldKnotCount - 1 : oldKnotCount - degree - 1;
+ const int a = FindSpanRef(X[0], first, last, obj -> KnotVector(UV));
// Allocate Memory for Qw
- Qw= (Point3d*)MEM_callocN(sizeof(Point3d)*(obj -> Length(UV) + r +
1),"Refine() Qw");
- Curve= (Point3d*)MEM_callocN(sizeof(Point3d)*(obj -> Length(UV) + r +
1),"Refine() Curve");
- Ubar= (nbReal*)MEM_callocN(sizeof(nbReal)*(obj -> Length(UV) + obj ->
Order(UV) + r + 1),"Refine() Ubar");
+ bufferQw = (Point3d*) MEM_callocN(sizeof(Point3d) * (obj -> Length(UV)
+ r + extra + extra + 1), "Refine() Qw");// + 1 is for Qw[k-degree-1] =
Qw[k-degree]
+ bufferCurve = (Point3d*) MEM_callocN(sizeof(Point3d) * (obj ->
Length(UV) + r + extra + extra), "Refine() Curve");
+ bufferUbar = (nbReal*) MEM_callocN(sizeof(nbReal) * (oldKnotCount2 + r
+ extra), "Refine() Ubar");
+ bufferKnotVectCpy = (nbReal*) MEM_callocN(sizeof(nbReal) *
(oldKnotCount2 + extra), "Refine() knotVectCpy");
+ //skips extra space, if there is such
+ Qw = bufferQw + extra + 1;
+ Curve = bufferCurve + extra;
+ Ubar = bufferUbar + extra;
+ knotVectCpy = bufferKnotVectCpy + extra;
+ //fill knot vector copy(copy by itself is needed only for alfa
calculation and Ubar initialization)
+ memcpy(knotVectCpy, obj -> KnotVector(UV), oldKnotCount2 *
sizeof(*knotVectCpy));
+ //fill extra space around knotVectCpy if cyclic case
+ if (extra) {
+ nbReal firstK = knotVectCpy [0], lastK = knotVectCpy
[oldKnotCount - 1];
+ for (int i = 1; i <= extra; i++) {
+ knotVectCpy [-i] = firstK - (lastK - knotVectCpy
[oldKnotCount - i - 1]);
+ //knotVectCpy [m + i - 1] = lastK + knotVectCpy [i] -
firstK;
+ }
+ }
+
// Allocate memory for curve
- if (UV) {
- obj -> SetLength(obj -> Length(0),obj -> Length(1)+r);
- n= obj -> Length(0) * (obj -> Length(1) + r) - r - 1;
- for (i= obj -> Length(0) * obj -> Length(1) - 1; i >= 0; i--) {
- // printf("n,i: %d,%d\n",n,i);
- obj -> CtlPts()[n].x= obj -> CtlPts()[i].x;
- obj -> CtlPts()[n].y= obj -> CtlPts()[i].y;
- obj -> CtlPts()[n].z= obj -> CtlPts()[i].z;
- !(i % obj -> Length(1)) ? n-= r+1: n--;
- } //eof
- } else {
- obj -> SetLength(obj -> Length(0)+r,obj -> Length(1));
- } //fi
+ if (UV)
+ obj -> SetLengthRef(obj -> Length(0), newLength);
+ else
+ obj -> SetLengthRef(newLength, obj -> Length(1));
// Decrement r
r--;
- for (n= 0; n < obj -> Length(!UV); n++) {
+ for (int rowOffset = 0, n = 0; n < obj -> Length(!UV); n++, rowOffset
+= pitch) {
+ Point3d *oldPoints = obj -> CtlPts();
// Populate Curve
- if (UV) {
- for (i= 0; i < obj -> Length(1); i++) {
- Curve[i].x= obj -> CtlPts()[i + n*(obj ->
Length(1) + r + 1)].x;
- Curve[i].y= obj -> CtlPts()[i + n*(obj ->
Length(1) + r + 1)].y;
- Curve[i].z= obj -> CtlPts()[i + n*(obj ->
Length(1) + r + 1)].z;
+ if (!UV) {
+ oldPoints += rowOffset; //moves pointer to the n-th row
+ for (i= 0; i < obj -> Length(UV); i++, oldPoints++) {
+ Curve[i].x = oldPoints -> x;
+ Curve[i].y = oldPoints -> y;
+ Curve[i].z = oldPoints -> z;
+ Curve[i].H = oldPoints -> H;
+ if (1.0 != oldPoints -> H) {
+ nbReal w = oldPoints -> H;
+ Curve[i].x *= w;
+ Curve[i].y *= w;
+ Curve[i].z *= w;
+ }
} //eof
} else {
- for (i= 0; i < obj -> Length(0); i++) {
- Curve[i].x= obj -> CtlPts()[i*obj -> Length(1)
+ n].x;
- Curve[i].y= obj -> CtlPts()[i*obj -> Length(1)
+ n].y;
- Curve[i].z= obj -> CtlPts()[i*obj -> Length(1)
+ n].z;
+ oldPoints += n;// moves pointer to the n-th column
+ for (i= 0; i < obj -> Length(UV); i++, oldPoints +=
pitch) {//skips to new line by adding pitch
+ Curve[i].x = oldPoints -> x;
+ Curve[i].y = oldPoints -> y;
+ Curve[i].z = oldPoints -> z;
+ Curve[i].H = oldPoints -> H;
+ if (1.0 != oldPoints -> H) {
+ nbReal w = oldPoints -> H;
+ Curve[i].x *= w;
+ Curve[i].y *= w;
+ Curve[i].z *= w;
+ }
} //eof
} //fi
+ // fills space between realCurve and Curve (for cyclics)
+ if (cyclic) {
+ Point3d *copyTo = Curve - 1;
+ Point3d *copyFrom = Curve + obj -> Length (UV) - 1;
+ for (i = 0; i < extra; i++, copyTo--, copyFrom--) {
+ copyTo -> x = copyFrom -> x;
+ copyTo -> y = copyFrom -> y;
+ copyTo -> z = copyFrom -> z;
+ copyTo -> H = copyFrom -> H;
+ }
+ copyTo = Curve + obj -> Length (UV);
+ copyFrom = Curve;
+ for (i = 0; i < extra; i++, copyTo++, copyFrom++) {
+ copyTo -> x = copyFrom -> x;
+ copyTo -> y = copyFrom -> y;
+ copyTo -> z = copyFrom -> z;
+ copyTo -> H = copyFrom -> H;
+ }
+ }
+ // end populate Curve
+ const int b = FindSpanRef(X[r], first, last, obj ->
KnotVector(UV)) + 1;
- m= obj -> Length(UV) + obj -> Order(UV);
- degree= obj -> Order(UV) - 1;
-
- a= FindSpan(obj -> Length(UV),degree,X[0],obj ->
KnotVector(UV));
- b= FindSpan(obj -> Length(UV),degree,X[r],obj ->
KnotVector(UV));
- b++;
-
- // Populate QW with Curve
- for (i= 0; i <= a-degree; i++) {
- Qw[i].x= Curve[i].x;
- Qw[i].y= Curve[i].y;
- Qw[i].z= Curve[i].z;
+ // Populate QW with Curve leaving gap for new CP's
+ for (i = 0 - extra; i <= a - degree; i++) {
+ Qw[i].x = Curve[i].x;
+ Qw[i].y = Curve[i].y;
+ Qw[i].z = Curve[i].z;
+ Qw[i].H = Curve[i].H;
} //eof
- for (i= b-1; i <= obj -> Length(UV); i++) {
- Qw[i+r+1].x= Curve[i].x;
- Qw[i+r+1].y= Curve[i].y;
- Qw[i+r+1].z= Curve[i].z;
+ for (i = b - 1; i < obj -> Length(UV) + extra; i++) {
+ Qw[i + r + 1].x = Curve[i].x;
+ Qw[i + r + 1].y = Curve[i].y;
+ Qw[i + r + 1].z = Curve[i].z;
+ Qw[i + r + 1].H = Curve[i].H;
} //eof
- for (i= 0; i <= a; i++)
- Ubar[i]= obj -> KnotVector(UV)[i];
+ //copies starting knots to Ubar
+ memcpy(Ubar - extra, knotVectCpy - extra, (a + 1 + extra) *
sizeof(*Ubar));
+ //copies knots after gap
+ memcpy(Ubar + b + degree, knotVectCpy + b + degree - 1,
(oldKnotCount2 - (b + degree) + 1) * sizeof(*Ubar));
- for (i= b+degree; i <= m; i++)
- Ubar[i+r+1]= obj -> KnotVector(UV)[i];
+ i = b + degree - 1;
+ k = b + degree + r;
- i= b+degree-1;
- k= b+degree+r;
-
for (j= r; j >= 0; j--) {
while (X[j] <= obj -> KnotVector(UV)[i] && i > a) {
Qw[k-degree-1].x= Curve[i-degree-1].x;
Qw[k-degree-1].y= Curve[i-degree-1].y;
Qw[k-degree-1].z= Curve[i-degree-1].z;
+ Qw[k-degree-1].H= Curve[i-degree-1].H;
Ubar[k]= obj -> KnotVector(UV)[i];
k--;
@@ -262,52 +343,96 @@
Qw[k-degree-1].x= Qw[k-degree].x;
Qw[k-degree-1].y= Qw[k-degree].y;
Qw[k-degree-1].z= Qw[k-degree].z;
+ Qw[k-degree-1].H= Qw[k-degree].H;
- for (l= 1; l <= degree; l++) {
+ for (l = 1; l <= degree; l++) {
ind= k-degree+l;
- alfa= Ubar[k+l]-X[j];
+ alfa = Ubar[k+l]-X[j];
if (fabs(alfa) == 0.0) {
Qw[ind-1].x= Qw[ind].x;
Qw[ind-1].y= Qw[ind].y;
Qw[ind-1].z= Qw[ind].z;
+ Qw[ind-1].H= Qw[ind].H;
} else {
- alfa= alfa/(Ubar[k+l]-obj ->
KnotVector(UV)[i-degree+l]);
+ alfa /= Ubar[k+l] -
knotVectCpy[i-degree+l];
Qw[ind-1].x= alfa*Qw[ind-1].x +
(1.0-alfa)*Qw[ind].x;
Qw[ind-1].y= alfa*Qw[ind-1].y +
(1.0-alfa)*Qw[ind].y;
Qw[ind-1].z= alfa*Qw[ind-1].z +
(1.0-alfa)*Qw[ind].z;
+ Qw[ind-1].H= alfa*Qw[ind-1].H +
(1.0-alfa)*Qw[ind].H;
} //fi
} //eof
Ubar[k]= X[j];
+ //newly inserted knot appears at the end of knot vector
also ...
+ if (cyclic && (b < 2 * degree)) {
+ //shift virtual knots
+ memmove(Ubar + newKnotCount + b - degree, Ubar
+ newKnotCount + b - degree - 1, (2 * degree - b) * sizeof(*Ubar));
+ // and write down new one
+ Ubar[newKnotCount + b - degree - 1] = obj ->
KnotVector(UV)[oldKnotCount - degree + r - j - 1] + X[j];
+ //FIXME knotVectCpy also needs update for
multiple inserts
+ }
k--;
} //eof
-
+ if (cyclic) {
+ int pre = b - degree;
+ Point3d *copyTo;
+ Point3d *copyFrom;
+ // copy cp's changed in pre buffer space
+ if (pre < 0) {
+ Point3d *copyTo = Qw + obj -> Length(UV) + r +
1 + pre;
+ Point3d *copyFrom = Qw + pre;
+ memcpy(copyTo, copyFrom, -pre *
sizeof(*copyTo));
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
