summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/bezierpatch.cc
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2018-04-03 22:35:04 +0000
committerKarl Berry <karl@freefriends.org>2018-04-03 22:35:04 +0000
commit36b8d1341af4a7ab1f5759d75ad1eecfc375c1f4 (patch)
tree12d09b686d2c18f245dc6fd492c09cdcd4c02ebc /Build/source/utils/asymptote/bezierpatch.cc
parentd73e029b665b866fe734e44508746a2cba513fd7 (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.cc372
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]);