From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- graphics/asymptote/base/bsp.asy | 209 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+) create mode 100644 graphics/asymptote/base/bsp.asy (limited to 'graphics/asymptote/base/bsp.asy') diff --git a/graphics/asymptote/base/bsp.asy b/graphics/asymptote/base/bsp.asy new file mode 100644 index 0000000000..cf9d7e0781 --- /dev/null +++ b/graphics/asymptote/base/bsp.asy @@ -0,0 +1,209 @@ +private import math; +import three; + +real epsilon=10*realEpsilon; + +// Routines for hidden surface removal (via binary space partition): +// Structure face is derived from picture. +struct face { + picture pic; + transform t; + frame fit; + triple normal,point; + triple min,max; + void operator init(path3 p) { + this.normal=normal(p); + if(this.normal == O) abort("path is linear"); + this.point=point(p,0); + min=min(p); + max=max(p); + } + face copy() { + face f=new face; + f.pic=pic.copy(); + f.t=t; + f.normal=normal; + f.point=point; + f.min=min; + f.max=max; + add(f.fit,fit); + return f; + } +} + +picture operator cast(face f) {return f.pic;} +face operator cast(path3 p) {return face(p);} + +struct line { + triple point; + triple dir; +} + +private line intersection(face a, face b) +{ + line L; + L.point=intersectionpoint(a.normal,a.point,b.normal,b.point); + L.dir=unit(cross(a.normal,b.normal)); + return L; +} + +struct half { + pair[] left,right; + + // Sort the points in the pair array z according to whether they lie on the + // left or right side of the line L in the direction dir passing through P. + // Points exactly on L are considered to be on the right side. + // Also push any points of intersection of L with the path operator --(... z) + // onto each of the arrays left and right. + void operator init(pair dir, pair P ... pair[] z) { + pair lastz; + pair invdir=dir != 0 ? 1/dir : 0; + bool left,last; + for(int i=0; i < z.length; ++i) { + left=(invdir*z[i]).y > (invdir*P).y; + if(i > 0 && last != left) { + pair w=extension(P,P+dir,lastz,z[i]); + this.left.push(w); + this.right.push(w); + } + if(left) this.left.push(z[i]); + else this.right.push(z[i]); + last=left; + lastz=z[i]; + } + } +} + +struct splitface { + face back,front; +} + +// Return the pieces obtained by splitting face a by face cut. +splitface split(face a, face cut, projection P) +{ + splitface S; + + void nointersection() { + if(abs(dot(a.point-P.camera,a.normal)) >= + abs(dot(cut.point-P.camera,cut.normal))) { + S.back=a; + S.front=null; + } else { + S.back=null; + S.front=a; + } + } + + if(P.infinity) { + P=P.copy(); + static real factor=1/sqrtEpsilon; + P.camera *= factor*max(abs(a.min),abs(a.max), + abs(cut.min),abs(cut.max)); + } + + if((abs(a.normal-cut.normal) < epsilon || + abs(a.normal+cut.normal) < epsilon)) { + nointersection(); + return S; + } + + line L=intersection(a,cut); + + if(dot(P.camera-L.point,P.camera-P.target) < 0) { + nointersection(); + return S; + } + + pair point=a.t*project(L.point,P); + pair dir=a.t*project(L.point+L.dir,P)-point; + pair invdir=dir != 0 ? 1/dir : 0; + triple apoint=L.point+cross(L.dir,a.normal); + bool left=(invdir*(a.t*project(apoint,P))).y >= (invdir*point).y; + + real t=intersect(apoint,P.camera,cut.normal,cut.point); + bool rightfront=left ^ (t <= 0 || t >= 1); + + face back=a, front=a.copy(); + pair max=max(a.fit); + pair min=min(a.fit); + half h=half(dir,point,max,(min.x,max.y),min,(max.x,min.y),max); + if(h.right.length == 0) { + if(rightfront) front=null; + else back=null; + } else if(h.left.length == 0) { + if(rightfront) back=null; + else front=null; + } + if(front != null) + clip(front.fit,operator --(... rightfront ? h.right : h.left)--cycle, + zerowinding); + if(back != null) + clip(back.fit,operator --(... rightfront ? h.left : h.right)--cycle, + zerowinding); + S.back=back; + S.front=front; + return S; +} + +// A binary space partition +struct bsp +{ + bsp back; + bsp front; + face node; + + // Construct the bsp. + void operator init(face[] faces, projection P) { + if(faces.length != 0) { + this.node=faces.pop(); + face[] front,back; + for(int i=0; i < faces.length; ++i) { + splitface split=split(faces[i],this.node,P); + if(split.front != null) front.push(split.front); + if(split.back != null) back.push(split.back); + } + this.front=bsp(front,P); + this.back=bsp(back,P); + } + } + + // Draw from back to front. + void add(frame f) { + if(back != null) back.add(f); + add(f,node.fit,group=true); + if(labels(node.fit)) layer(f); // Draw over any existing TeX layers. + if(front != null) front.add(f); + } +} + +void add(picture pic=currentpicture, face[] faces, + projection P=currentprojection) +{ + int n=faces.length; + face[] Faces=new face[n]; + for(int i=0; i < n; ++i) + Faces[i]=faces[i].copy(); + + pic.add(new void (frame f, transform t, transform T, + pair m, pair M) { + // Fit all of the pictures so we know their exact sizes. + face[] faces=new face[n]; + for(int i=0; i < n; ++i) { + faces[i]=Faces[i].copy(); + face F=faces[i]; + F.t=t*T*F.pic.T; + F.fit=F.pic.fit(t,T*F.pic.T,m,M); + } + + bsp bsp=bsp(faces,P); + if(bsp != null) bsp.add(f); + }); + + for(int i=0; i < n; ++i) { + picture F=Faces[i].pic; + pic.userBox3(F.userMin3(), F.userMax3()); + pic.bounds.append(F.T, F.bounds); + // The above 2 lines should be replaced with a routine in picture which + // copies only sizing data from another picture. + } +} -- cgit v1.2.3