a.k.a. polygon clipping algorithm in 3d
a.k.a. finding collision manifold between 2 colliding polygons
most algorithms polygon clipping described in detail 2d , described being extendable 3d without details. example sutherland-hodgman clipping algorithm
having been unable find 3d implementations or pseudo code on internet asking here (and attempting answer own question)
the algorithm take 2 shapes such shown below: 
and output intersection of 2 shapes shown below: 
note although sutherland-hodgman algorithm finds intersection of 2 polygons (and others) make distinction between clipped polygon , clipping polygon; clipped polygon may concave or convex, clipping shape must convex. however, implementation in extending 3d requires both shapes convex, suggests not true 3d sutherland-hodgman algorithm , other answers (using algorithm) lifting requirement appreciated
the 2d sutherland-hodgman clipping algorithm clips each edge of clipped shape each edge of clipping shape. 3d algorithm, however, clips each edge of each face of clipped shape each face of clipping shape (not each edge of each face of clipping shape).
my algorithm "inspired" approach had add step edges come out correctly. clipped both ways; clipping 1 shape other doing reverse , adding two; causes requirement both shapes convex. failing include "both ways" misses of faces shown below
the pseudo code algorithm follows
each clippiing face each clipped face each edge of each clipped face clip clippiing face per www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml end end each edge of each clipping face(this step leads requirement both shapes convex) clip clipped face clippiing face per www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml end end this algorithm implimented in java shown below: (note jmonkey engine used 3d visualisation demarked can stripped out)
import java.util.arraylist; //visualisation imports ############### //requires: jmonkey engine import com.jme3.asset.assetmanager; import com.jme3.math.colorrgba; import com.jme3.scene.node; /** * * @author richard tingle */ //note: right handed co-ordinates set; x,y normal, z towards public class polygon3d { //based on sudocode http://jhave.org/learner/misc/sutherlandhodgman/sutherlandhodgmanclipping.shtml arraylist<face> faces=new arraylist<face>(); public polygon3d(){} public polygon3d(arraylist<face> faces){ this.faces=faces; } public int getnumberoffaces(){ return faces.size(); } public void addface(face face){ //for building face face faces.add(face); } public face getface(int facenumber){ return faces.get(facenumber); } public polygon3d clip(polygon3d clippingpolygon){ polygon3d workingpolygon=this; for(int i=0; i<clippingpolygon.getnumberoffaces();i++){ workingpolygon=clip(workingpolygon, clippingpolygon.getface(i)); } return workingpolygon; } private polygon3d clip(polygon3d inpolygon, face clippingface){ //each edges of each face of inpolygon clipped clipping face polygon3d outpolygon=new polygon3d(); for(int i=0;i<inpolygon.getnumberoffaces();i++){ face clippedface=inpolygon.getface(i).clipface(clippingface); if (clippedface!=null){ outpolygon.addface(clippedface); } } //additional step, clipping face clipped inpolygon //this step causes requirement both clipping , clipped //shapes convex face workingface=clippingface; for(int i=0;i<inpolygon.getnumberoffaces();i++){ if (workingface==null){ //no need bonus face in case break; } workingface=workingface.clipface(inpolygon.getface(i)); } if (workingface!=null){ outpolygon.addface(workingface); } return outpolygon; } //visualisation ############### //requires: jmonkey engine public void render(assetmanager assetmanager, node node, colorrgba color){ for(int i=0;i<getnumberoffaces();i++){ node.attachchild(getface(i).getgeometry(assetmanager,color)); } } } import java.util.arraylist; import javax.vecmath.vector3d; //visualisation imports ############### //requires: jmonkey engine import com.jme3.asset.assetmanager; import com.jme3.material.material; import com.jme3.math.colorrgba; import com.jme3.scene.geometry; import com.jme3.scene.mesh; import com.jme3.scene.vertexbuffer; /** * * @author richard tingle */ public class face{ arraylist<vector3d> verticies=new arraylist<vector3d>(); //note: face assumes verticies in same place, //is not checked , failure comform lead errors //face must have @ least 3 verticies time used, , //face must convex. vertex winding must anticlockwise, //a function rewind available rewind if clockwise winding used //clockwise or anticlockwise winding must used, randomly putting in //verticies not end public face(){}; public face(arraylist<vector3d> verticies){this.verticies=verticies;} public void addvertex(vector3d vertex){ if ( double.isnan(vertex.x)){ throw new runtimeexception("nan vertex"); } if ( double.isinfinite(vertex.x)|| double.isinfinite(vertex.y)|| double.isinfinite(vertex.z)){ throw new runtimeexception("infinite vertex"); } if (verticies.contains(vertex)){ //degenerate vertex, not add }else{ verticies.add(vertex); } } public void rewind(vector3d internalpoint){ //the winding of verticies must such looks anticlockwise //from "outside", however, method allows points added //either clockwise or anticlockwise winding , final point //anywhere on inside of shape specified in method , if //wrong winding used rewinds anticlockwise winding if (pointisinsideface(internalpoint)==false){ //winding incorrect, reverese winding arraylist<vector3d> verticiesrewound=new arraylist<vector3d>(verticies.size()); for(int i=verticies.size()-1;i>=0;i--){ verticiesrewound.add(verticies.get(i)); } verticies=verticiesrewound; } } public int getnumberofedges(){ return verticies.size(); //(note because last vertex connects first noofedges==noofverticies) } public vector3d getvertex(int vertex){ return verticies.get(vertex); } public vector3d getstartofedge(int edgeno){ return verticies.get(edgeno); } public vector3d getendofedge(int edgeno){ return verticies.get((edgeno+1)%verticies.size()); //%verticies.size() allows loop around last edge } private double getpointvsfacedeterminant(vector3d point){ //this method bit meaningless used in //pointisinsideface(vector3d point) //and //getintersectionpoint //the returned determinant measure of side //(and how far) point lies plane //for work face must have anticlockwise winding when looked @ //from outside //we define faces having verticies in such order //when looked @ outside points ordered anticlockswise //so function equivalent to: pointisinsideshape //see http://math.stackexchange.com/questions/214187/point-on-the-left-or-right-side-of-a-plane-in-3d-space //assuming face convex, need first 3 points determine //the "winding" of face if (verticies.size()<3){ throw new runtimeexception("degenerate face: face has less 3 verticies"); } vector3d a=verticies.get(0); vector3d b=verticies.get(1); vector3d c=verticies.get(2); vector3d x=point; vector3d bdash=new vector3d(); bdash.sub(b, x); vector3d cdash=new vector3d(); cdash.sub(c, x); vector3d xdash=new vector3d(); xdash.sub(x, a); //find determinant of 3 3 matrix described in link (see also: http://www.mathsisfun.com/algebra/matrix-determinant.html) double determinant=bdash.x*(cdash.y*xdash.z-cdash.z*xdash.y)-bdash.y*(cdash.x*xdash.z-cdash.z*xdash.x)+bdash.z*(cdash.x*xdash.y-cdash.y*xdash.x); return determinant; } public boolean pointisinsideface(vector3d point){ //for work face must have anticlockwise winding when looked @ //from outside //we define faces having verticies in such order //when looked @ outside points ordered anticlockswise //so function equivalent to: pointisinsideshape //see http://math.stackexchange.com/questions/214187/point-on-the-left-or-right-side-of-a-plane-in-3d-space //find determinant of 3 3 matrix described in link (see also: http://www.mathsisfun.com/algebra/matrix-determinant.html) double determinant=getpointvsfacedeterminant(point); if (determinant<=0){ // <= because define on face "inside face" return true; }else{ return false; } } public vector3d getintersectionpoint(vector3d raypoint1, vector3d raypoint2){ //note: method treats face if infinite plane //this treating plane why convex shapes must used //see http://mathworld.wolfram.com/plane.html //changed above method can upset parallel lines double determinantpoint1=getpointvsfacedeterminant(raypoint1); double determinantpoint2=getpointvsfacedeterminant(raypoint2); if (determinantpoint1==determinantpoint2){ //paralell line, if we've got method it'll //be in plane, line in plane, middle seems //most reasonable point vector3d average=new vector3d(); average.add(raypoint1, raypoint2); average.scale(0.5); return average; }else{ //we want return point determinant have been //zero //linear interpolation vector3d intersect=new vector3d(); intersect.sub(raypoint2, raypoint1); intersect.scale((0-determinantpoint1)/(determinantpoint2-determinantpoint1)); intersect.add(raypoint1); return intersect; } } public face clipface(face clippingface){ //based on sudocode www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml //note, face may entirely clipped clipping face //or clipped degenerate edge, in case null returned face workingface=new face(); for(int i=0;i<this.getnumberofedges();i++){ //clips edges of working polygon against plane based upon clipping face //for each edge there 4 cases, must determine //where refer starting , ending verticies of workingface //where refer "the face" clipping face //and endedge. edge of clipping polygon //case 1) both starting verticies inside face //case 2) starting vertex inside face, ending vertex inside //case 3) both verticies outside face //case 4) starting outside face, ending inside vector3d point1=getstartofedge(i); vector3d point2=getendofedge(i); if (clippingface.pointisinsideface(point1) && clippingface.pointisinsideface(point2)){ //case 1, end point added workingface.addvertex(point2); }else if (clippingface.pointisinsideface(point1) && clippingface.pointisinsideface(point2)==false){ //case 2, intersection added vector3d intersection=clippingface.getintersectionpoint(point1, point2); workingface.addvertex(intersection); }else if (clippingface.pointisinsideface(point1)==false && clippingface.pointisinsideface(point2)==false){ //case 3, both verticies outside clip shape line, no vertexes added }else{ //case 4 ending vertex inside , starting vertex outside //the line //the intercept , end point added vector3d intersection=clippingface.getintersectionpoint(point1, point2); boolean one=clippingface.pointisinsideface(point1); boolean two=clippingface.pointisinsideface(point2); one=clippingface.pointisinsideface(point1); two=clippingface.pointisinsideface(point2); intersection=clippingface.getintersectionpoint(point1, point2); workingface.addvertex(intersection); workingface.addvertex(point2); } } if (workingface.getnumberofedges()>=3){ return workingface; }else{ return null; //degenerate or culled face } } private int getnumberofsegments(){ return verticies.size()-2; } //visualisation ############### //requires: jmonkey engine public geometry getgeometry(assetmanager assetmanager,colorrgba color){ mesh m = new mesh(); m.setmode(mesh.mode.lineloop); float[] verticiesforbuffer=new float[3*(getnumberofedges())]; int[] indicies=new int[getnumberofedges()]; for(int i=0;i<getnumberofedges();i++){ vector3d vertex=getvertex(i); verticiesforbuffer[i*3]=(float)vertex.x; verticiesforbuffer[i*3+1]=(float)vertex.y; verticiesforbuffer[i*3+2]=(float)vertex.z; indicies[i]=i; } m.setbuffer(vertexbuffer.type.position, 3, verticiesforbuffer); m.setbuffer(vertexbuffer.type.index, 1, indicies); m.updatebound(); m.updatecounts(); geometry geom = new geometry("box", m); material mat = new material(assetmanager, "common/matdefs/misc/unshaded.j3md"); mat.setcolor("color", color); geom.setmaterial(mat); return geom; } } the following main class creates images shown , renders them using jmonkey engine library
import javax.vecmath.vector3d; //visualisation imports ############### //requires: jmonkey engine import com.jme3.app.simpleapplication; import com.jme3.math.colorrgba; import com.jme3.renderer.rendermanager; public class main extends simpleapplication { public static void main(string[] args) { main app = new main(); app.start(); } @override public void simpleinitapp(){ polygon3d poly1= getcubepolygon(new vector3d(-2,-2,-2),new vector3d(2,2,2),0.5); polygon3d poly2= getcubepolygon(new vector3d(-1,-5,-1),new vector3d(1,5,1),-2.5); polygon3d poly3= poly1.clip(poly2); //poly1.render(assetmanager, rootnode, colorrgba.blue); //comment out see individual shapes //poly2.render(assetmanager, rootnode, colorrgba.green); poly3.render(assetmanager, rootnode,colorrgba.red); } public polygon3d getcubepolygon(vector3d mins, vector3d maxs, double xskew){ //xskew makes top , bottom x different (so not cube) vector3d hhh=new vector3d(maxs.x+xskew,maxs.y,maxs.z); vector3d hhl=new vector3d(maxs.x+xskew,maxs.y,mins.z); vector3d hlh=new vector3d(maxs.x-xskew,mins.y,maxs.z); vector3d hll=new vector3d(maxs.x-xskew,mins.y,mins.z); vector3d lhh=new vector3d(mins.x+xskew,maxs.y,maxs.z); vector3d lhl=new vector3d(mins.x+xskew,maxs.y,mins.z); vector3d llh=new vector3d(mins.x-xskew,mins.y,maxs.z); vector3d lll=new vector3d(mins.x-xskew,mins.y,mins.z); vector3d centre=new vector3d(0.5*(mins.x+maxs.x),0.5*(mins.y+maxs.y),0.5*(mins.z+maxs.z)); //just rewinding face top=new face(); face bottom=new face(); face north=new face(); face south=new face(); face east=new face(); face west=new face(); north.addvertex(hll); north.addvertex(hhl); north.addvertex(hhh); north.addvertex(hlh); north.rewind(centre); south.addvertex(lll); south.addvertex(lhl); south.addvertex(lhh); south.addvertex(llh); south.rewind(centre); top.addvertex(hhh); top.addvertex(hhl); top.addvertex(lhl); top.addvertex(lhh); top.rewind(centre); bottom.addvertex(hlh); bottom.addvertex(hll); bottom.addvertex(lll); bottom.addvertex(llh); bottom.rewind(centre); east.addvertex(hhh); east.addvertex(hlh); east.addvertex(llh); east.addvertex(lhh); east.rewind(centre); west.addvertex(hhl); west.addvertex(hll); west.addvertex(lll); west.addvertex(lhl); west.rewind(centre); polygon3d poly=new polygon3d(); poly.addface(top); poly.addface(bottom); poly.addface(north); poly.addface(south); poly.addface(east); poly.addface(west); return poly; } } 
Comments
Post a Comment