diff options
author | Karl Berry <karl@freefriends.org> | 2018-04-03 22:35:04 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2018-04-03 22:35:04 +0000 |
commit | 36b8d1341af4a7ab1f5759d75ad1eecfc375c1f4 (patch) | |
tree | 12d09b686d2c18f245dc6fd492c09cdcd4c02ebc /Build/source/utils/asymptote/bezierpatch.cc | |
parent | d73e029b665b866fe734e44508746a2cba513fd7 (diff) |
asy 2.42 sources
git-svn-id: svn://tug.org/texlive/trunk@47274 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/utils/asymptote/bezierpatch.cc')
-rw-r--r-- | Build/source/utils/asymptote/bezierpatch.cc | 372 |
1 files changed, 340 insertions, 32 deletions
diff --git a/Build/source/utils/asymptote/bezierpatch.cc b/Build/source/utils/asymptote/bezierpatch.cc index f076d4643ac..34b80f05b6d 100644 --- a/Build/source/utils/asymptote/bezierpatch.cc +++ b/Build/source/utils/asymptote/bezierpatch.cc @@ -6,11 +6,16 @@ *****/ #include "bezierpatch.h" +#include "predicates.h" namespace camp { +using ::orient2d; +using ::orient3d; + size_t tstride; -GLfloat *B; + +double viewpoint[3]; #ifdef HAVE_GL @@ -23,6 +28,41 @@ std::vector<GLuint> BezierPatch::tindices; std::vector<GLfloat> BezierPatch::tBuffer; std::vector<GLuint> BezierPatch::tIndices; +std::vector<GLuint>& I=BezierPatch::tIndices; +std::vector<GLfloat>& V=BezierPatch::tBuffer; +bool colors; + +std::vector<GLfloat> zbuffer; +std::vector<GLfloat> xbuffer; +std::vector<GLfloat> ybuffer; + +std::vector<GLfloat> xmin,ymin,zmin; +std::vector<GLfloat> xmax,ymax,zmax; +std::vector<GLfloat> zsum; + +inline double min(double a, double b, double c) +{ + return min(min(a,b),c); +} + +inline double max(double a, double b, double c) +{ + return max(max(a,b),c); +} + +struct iz { + unsigned i; + double z; + iz() {} + void minimum(unsigned i, const std::vector<GLuint>& I) { + this->i=i; + unsigned i3=3*i; + z=min(zbuffer[I[i3]],zbuffer[I[i3+1]],zbuffer[I[i3+2]]); + } +}; + +std::vector<iz> IZ; + GLuint BezierPatch::nvertices=0; GLuint BezierPatch::ntvertices=0; GLuint BezierPatch::Nvertices=0; @@ -33,31 +73,235 @@ extern const double Fuzz2; const double FillFactor=0.1; const double BezierFactor=0.4; -// Partially work around OpenGL transparency bug by sorting transparent -// triangles by their centroid depth. -int compare(const void *a, const void *b) +inline int sgn1(double x) +{ + return x >= 0.0 ? 1 : -1; +} + +inline int sgn(double x) +{ + return (x > 0.0 ? 1 : (x < 0.0 ? -1 : 0)); +} + +bool sameside(const double *a, const double *b, int s0, const double *A, + const double *B, const double *C) +{ + if(sgn(orient2d(a,b,A)) == s0) return true; + if(sgn(orient2d(a,b,B)) == s0) return true; + if(sgn(orient2d(a,b,C)) == s0) return true; + return false; +} + +// returns true iff 2D triangles abc and ABC intersect +bool intersect2D(const double *a, const double *b, const double *c, + const double *A, const double *B, const double *C) +{ + int s0=sgn(orient2d(a,b,c)); // Optimize away + int S0=sgn(orient2d(A,B,C)); // Optimize away + return + sameside(a,b,s0,A,B,C) && + sameside(b,c,s0,A,B,C) && + sameside(c,a,s0,A,B,C) && + sameside(A,B,S0,a,b,c) && + sameside(B,C,S0,a,b,c) && + sameside(C,A,S0,a,b,c); +} + +// returns true iff triangle abc is pierced by line segment AB. +bool pierce(const double *a, const double *b, const double *c, const double *A, const double *B) +{ + int sa=sgn(orient3d(A,b,c,B)); + int sb=sgn(orient3d(A,c,a,B)); + int sc=sgn(orient3d(A,a,b,B)); + return sa == sb && sb == sc; +} + +// returns true iff triangle abc is pierced by an edge of triangle ABC +bool intersect0(const double *a, const double *b, const double *c, + const double *A, const double *B, const double *C, + int sA, int sB, int sC) +{ + if(sA != sB) { + if(pierce(a,b,c,A,B)) return true; + if(sC != sA) { + if(pierce(a,b,c,C,A)) return true; + } else { + if(pierce(a,b,c,B,C)) return true; + } + } else { + if(pierce(a,b,c,B,C)) return true; + if(pierce(a,b,c,C,A)) return true; + } + return false; +} + +// returns true iff triangle abc intersects triangle ABC +bool intersect3D(const double *a, const double *b, const double *c, + const double *A, const double *B, const double *C) +{ + int sA=sgn(orient3d(a,b,c,A)); + int sB=sgn(orient3d(a,b,c,B)); + int sC=sgn(orient3d(a,b,c,C)); + if(sA == sB && sB == sC) return false; + + int sa=sgn(orient3d(A,B,C,a)); + int sb=sgn(orient3d(A,B,C,b)); + int sc=sgn(orient3d(A,B,C,c)); + if(sa == sb && sb == sc) return false; + + return intersect0(a,b,c,A,B,C,sA,sB,sC) || intersect0(A,B,C,a,b,c,sa,sb,sc); +} + +// Return the intersection time of the extension of the line segment PQ +// with the plane perpendicular to n and passing through Z. +inline double intersect(const double *P, const double *Q, const double *n, + const double *Z) +{ + double d=n[0]*Z[0]+n[1]*Z[1]+n[2]*Z[2]; + double denom=n[0]*(Q[0]-P[0])+n[1]*(Q[1]-P[1])+n[2]*(Q[2]-P[2]); + return denom == 0 ? DBL_MAX : (d-n[0]*P[0]-n[1]*P[1]-n[2]*P[2])/denom; +} + +inline triple interp(const double *a, const double *b, double t) +{ + return triple(a[0]+t*(b[0]-a[0]),a[1]+t*(b[1]-a[1]),a[2]+t*(b[2]-a[2])); +} + +inline void interp(GLfloat *dest, + const GLfloat *a, const GLfloat *b, double t) +{ + double onemt=1.0-t; + for(size_t i=0; i < 4; ++i) + dest[i]=onemt*a[i]+t*b[i]; +} + +inline triple interp(const triple& a, const triple& b, double t) { - size_t a0=tstride*((GLuint *) a)[0]; - size_t a1=tstride*((GLuint *) a)[1]; - size_t a2=tstride*((GLuint *) a)[2]; + return a+(b-a)*t; +} + +inline void cross(double *dest, const double *u, const double *v, + const double *w) +{ + double u0=u[0]-w[0]; + double u1=u[1]-w[1]; + double u2=u[2]-w[2]; + double v0=v[0]-w[0]; + double v1=v[1]-w[1]; + double v2=v[2]-w[2]; + dest[0]=u1*v2-u2*v1; + dest[1]=u2*v0-u0*v2; + dest[2]=u0*v1-u1*v0; +} + +unsigned n; +unsigned int count; +const size_t nbuffer=10000; + +// Sort nonintersecting triangles by depth. +int compare(const void *p, const void *P) +{ + unsigned Ia=((GLuint *) p)[0]; + unsigned Ib=((GLuint *) p)[1]; + unsigned Ic=((GLuint *) p)[2]; + + unsigned IA=((GLuint *) P)[0]; + unsigned IB=((GLuint *) P)[1]; + unsigned IC=((GLuint *) P)[2]; + + return zbuffer[Ia]+zbuffer[Ib]+zbuffer[Ic] < + zbuffer[IA]+zbuffer[IB]+zbuffer[IC] ? -1 : 1; + + /* + double a[]={xbuffer[Ia],ybuffer[Ia],zbuffer[Ia]}; + double b[]={xbuffer[Ib],ybuffer[Ib],zbuffer[Ib]}; + double c[]={xbuffer[Ic],ybuffer[Ic],zbuffer[Ic]}; + + double A[]={xbuffer[IA],ybuffer[IA],zbuffer[IA]}; + double B[]={xbuffer[IB],ybuffer[IB],zbuffer[IB]}; + double C[]={xbuffer[IC],ybuffer[IC],zbuffer[IC]}; + + double viewpoint[]={0,0,100000}; - size_t b0=tstride*((GLuint *) b)[0]; - size_t b1=tstride*((GLuint *) b)[1]; - size_t b2=tstride*((GLuint *) b)[2]; - - double x= - T[0]*(B[a0]+B[a1]+B[a2]-B[b0]-B[b1]-B[b2])+ - T[1]*(B[a0+1]+B[a1+1]+B[a2+1]-B[b0+1]-B[b1+1]-B[b2+1])+ - T[2]*(B[a0+2]+B[a1+2]+B[a2+2]-B[b0+2]-B[b1+2]-B[b2+2]); - if(x > 0.0) return 1; - if(x < 0.0) return -1; - return 0; + double sa=-orient3d(A,B,C,a); + double sb=-orient3d(A,B,C,b); + double sc=-orient3d(A,B,C,c); + double s=min(sa,sb,sc); + double S=max(sa,sb,sc); + double eps=1000; + + if(s < -eps && S > eps) { //swap + double sA=-orient3d(a,b,c,A); + double sB=-orient3d(a,b,c,B); + double sC=-orient3d(a,b,c,C); + double s=min(sA,sB,sC); + double S=max(sA,sB,sC); + if(S < -s) S=s; + int sz=sgn1(orient3d(a,b,c,viewpoint)); + if(S < -eps) return -sz; + if(S > eps) return sz; + } + if(S < -s) S=s; + int sz=sgn1(orient3d(A,B,C,viewpoint)); + if(S < -eps) return sz; + if(S > eps) return -sz; + return a[2]+b[2]+c[2] < A[2]+B[2]+C[2] ? -1 : 1; + */ +} + +void split(unsigned i3, GLuint ia, GLuint ib, GLuint ic, + double *a, double *b, double *c, double *N, double *A) { + double td=intersect(a,b,N,A); + double te=intersect(a,c,N,A); + + triple d=interp(a,b,td); + triple e=interp(a,c,te); + + GLuint Ia=tstride*ia; + GLuint Ib=tstride*ib; + GLuint Ic=tstride*ic; + + triple na=triple(V[Ia+3],V[Ia+4],V[Ia+5]); + triple nb=triple(V[Ib+3],V[Ib+4],V[Ib+5]); + triple nc=triple(V[Ic+3],V[Ic+4],V[Ic+5]); + + triple nd=interp(na,nb,td); + triple ne=interp(na,nc,te); + + GLuint id,ie; + + if(colors) { + GLfloat *ca=&V[Ia+6]; + GLfloat *cb=&V[Ib+6]; + GLfloat *cc=&V[Ic+6]; + + GLfloat cd[4],ce[4]; + interp(cd,ca,cb,td); + interp(ce,ca,cc,te); + + id=BezierPatch::tVertex(d,nd,cd); + ie=BezierPatch::tVertex(e,ne,ce); + } else { + id=BezierPatch::tvertex(d,nd); + ie=BezierPatch::tvertex(e,ne); + } + + I[i3]=ia; + I[i3+1]=id; + I[i3+2]=ie; + + I.push_back(id); + I.push_back(ib); + I.push_back(ie); + + I.push_back(ie); + I.push_back(ib); + I.push_back(ic); } void BezierPatch::init(double res, const triple& Min, const triple& Max, bool transparent, GLfloat *colors) { - empty=false; res2=res*res; Res2=BezierFactor*BezierFactor*res2; Epsilon=FillFactor*res; @@ -65,6 +309,7 @@ void BezierPatch::init(double res, const triple& Min, const triple& Max, this->Max=Max; const size_t nbuffer=10000; + indices.reserve(nbuffer); if(transparent) { tbuffer.reserve(nbuffer); tindices.reserve(nbuffer); @@ -78,7 +323,6 @@ void BezierPatch::init(double res, const triple& Min, const triple& Max, } } else { buffer.reserve(nbuffer); - indices.reserve(nbuffer); pindices=&indices; pvertex=&vertex; if(colors) { @@ -586,25 +830,83 @@ void BezierTriangle::render(const triple *p, bool straight, GLfloat *c0) } } +void transform(const std::vector<GLfloat>& b) +{ + unsigned n=b.size()/tstride; +// xbuffer.resize(n); +// ybuffer.resize(n); + zbuffer.resize(n); + + for(unsigned i=0; i < n; ++i) { + unsigned j=tstride*i; +// xbuffer[i]=Tx[0]*b[j]+Tx[1]*b[j+1]+Tx[2]*b[j+2]; +// ybuffer[i]=Ty[0]*b[j]+Ty[1]*b[j+1]+Ty[2]*b[j+2]; + zbuffer[i]=Tz[0]*b[j]+Tz[1]*b[j+1]+Tz[2]*b[j+2]; + } + +} + +// precompute min and max bounds of each triangle +void bounds(const std::vector<GLuint>& I) +{ + unsigned n=I.size()/3; + xmin.resize(n); + xmax.resize(n); + ymin.resize(n); + ymax.resize(n); + zmin.resize(n); + zmax.resize(n); + + for(unsigned i=0; i < n; ++i) { + unsigned i3=3*i; + unsigned Ia=I[i3]; + unsigned Ib=I[i3+1]; + unsigned Ic=I[i3+2]; + + double xa=xbuffer[Ia]; + double xb=xbuffer[Ib]; + double xc=xbuffer[Ic]; + + double ya=ybuffer[Ia]; + double yb=ybuffer[Ib]; + double yc=ybuffer[Ic]; + + double za=zbuffer[Ia]; + double zb=zbuffer[Ib]; + double zc=zbuffer[Ic]; + + xmin[i]=min(xa,xb,xc); + xmax[i]=max(xa,xb,xc); + + ymin[i]=min(ya,yb,yc); + ymax[i]=max(ya,yb,yc); + + zmin[i]=min(za,zb,zc); + zmax[i]=max(za,zb,zc); + } +} + void BezierPatch::draw() { - if(empty) return; - size_t stride=6; - size_t Stride=10; - size_t size=sizeof(GLfloat); - size_t bytestride=stride*size; - size_t Bytestride=Stride*size; + if(nvertices == 0 && ntvertices == 0 && Nvertices == 0 && Ntvertices == 0) + return; + + const size_t stride=6; + const size_t Stride=10; + const size_t size=sizeof(GLfloat); + const size_t bytestride=stride*size; + const size_t Bytestride=Stride*size; glEnableClientState(GL_NORMAL_ARRAY); glEnableClientState(GL_VERTEX_ARRAY); - if(indices.size()) { + if(nvertices > 0) { glVertexPointer(3,GL_FLOAT,bytestride,&buffer[0]); glNormalPointer(GL_FLOAT,bytestride,&buffer[3]); glDrawElements(GL_TRIANGLES,indices.size(),GL_UNSIGNED_INT,&indices[0]); } - if(Indices.size()) { + if(Nvertices > 0) { glEnableClientState(GL_COLOR_ARRAY); glEnable(GL_COLOR_MATERIAL); glVertexPointer(3,GL_FLOAT,Bytestride,&Buffer[0]); @@ -615,19 +917,25 @@ void BezierPatch::draw() glDisableClientState(GL_COLOR_ARRAY); } - if(tindices.size()) { - B=&tbuffer[0]; + if(ntvertices > 0) { tstride=stride; + transform(tbuffer); +// bounds(tindices); + qsort(&tindices[0],tindices.size()/3,3*sizeof(GLuint),compare); + glVertexPointer(3,GL_FLOAT,bytestride,&tbuffer[0]); glNormalPointer(GL_FLOAT,bytestride,&tbuffer[3]); glDrawElements(GL_TRIANGLES,tindices.size(),GL_UNSIGNED_INT,&tindices[0]); } - if(tIndices.size()) { - B=&tBuffer[0]; + if(Ntvertices > 0) { tstride=Stride; + transform(tBuffer); +// bounds(tIndices); + qsort(&tIndices[0],tIndices.size()/3,3*sizeof(GLuint),compare); + glEnableClientState(GL_COLOR_ARRAY); glEnable(GL_COLOR_MATERIAL); glVertexPointer(3,GL_FLOAT,Bytestride,&tBuffer[0]); |