Tìm giao điểm của hai đa giác 3D

Question

aka Polygon thuật toán clipping trong không gian 3D

aka Tìm các đa dạng va chạm giữa 2 đa giác va chạm

Hầu hết các thuật toán để đa giác cắt được mô tả một cách chi tiết cho 2D và mô tả như là mở rộng để 3D nhưng không có chi tiết. Ví dụ sutherland-hodgman clipping algorithm

Đã không thể tìm thấy bất kỳ việc triển khai 3D hoặc mã giả trên internet Tôi bây giờ hỏi ở đây (và cố gắng trả lời câu hỏi của riêng tôi)

Thuật toán sẽ mất hai hình dạng như những thể hiện dưới đây:

Và sẽ ra giao điểm của hai hình như hình dưới đây:

Lưu ý rằng mặc dù các thuật toán Sutherland-Hodgman tìm giao điểm của t wo đa giác nó (và hầu hết những người khác) tạo ra sự khác biệt giữa đa giác bị cắt và đa giác cắt; đa giác bị cắt có thể lõm hoặc lồi, nhưng hình dạng cắt phải lồi. Tuy nhiên, thực hiện của tôi trong việc mở rộng sang 3D đòi hỏi cả hai hình dạng được lồi, điều này cho thấy rằng nó không phải là một thực thuật toán 3D Sutherland-Hodgman và câu trả lời khác (sử dụng bất kỳ thuật toán) nâng yêu cầu này sẽ được rất nhiều đánh giá cao

Answer 1

Các thuật toán cắt sutherland-hodgman 2D clip mỗi cạnh của hình dạng cắt bớt bởi mỗi cạnh của hình cắt. Tuy nhiên, thuật toán 3D sẽ kẹp từng cạnh của mỗi khuôn mặt của hình cắt bớt bởi mỗi khuôn mặt của hình cắt (KHÔNG phải từng cạnh của mỗi khuôn mặt của hình cắt).

Thuật toán của tôi được "lấy cảm hứng" theo cách tiếp cận này nhưng tôi phải thêm một bước phụ để có được tất cả các cạnh xuất hiện chính xác. Về cơ bản tôi cắt bớt cả hai cách; cắt một hình dạng bằng cách khác sau đó làm ngược lại và thêm hai; điều này làm cho yêu cầu cả hai hình dạng bị lồi. Không bao gồm này "cả hai cách" bỏ lỡ một số trong những gương mặt như hình dưới đây

Mã giả cho thuật toán này như sau

for each clippiING face 
     for each clippED face 
      for each edge of each clippED face 
       clip by clippiING face as per www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml 
      end 
     end 

     for each edge of each clippiNG face(this step leads to requirement that both shapes be convex) 
      clip clippED face by clippiING face as per www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml 
     end 
    end 

thuật toán này được implimented trong java như hình dưới đây : (Lưu ý công cụ JMonkey được sử dụng để hiển thị 3D nhưng bị hủy bỏ để có thể dễ dàng bị tước bỏ)

import java.util.ArrayList; 

//VISUALISATION ONLY 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 as normal, z towards us 

public class Polygon3D { 
    //based on sudocode from 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 by 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 the inPolygon is clipped by the 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 is also clipped by the inPolygon 
     //this step is what causes the requirement for both clipping and clipped 
     //shapes to be convex 
     Face workingFace=clippingFace; 
     for(int i=0;i<inPolygon.getNumberOfFaces();i++){ 
      if (workingFace==null){ 
       //no need for bonus face in this case 
       break; 
      } 
      workingFace=workingFace.clipFace(inPolygon.getFace(i)); 
     } 
     if (workingFace!=null){ 
      outPolygon.addFace(workingFace); 
     } 


     return outPolygon; 
    } 

    //VISUALISATION ONLY ############### 
    //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 ONLY 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 that all its verticies are in the same place, this 
    //is not checked and failure to comform to this will lead to errors 
    //Face MUST have at least 3 verticies by the time it is used, and the 
    //face itself must be convex. Vertex winding must be anticlockwise, but 
    //a function rewind is available to rewind if clockwise winding is used 
    //clockwise or anticlockwise winding must be used, randomly putting in 
    //verticies will not end well 

    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, do not add 
     }else{ 
      verticies.add(vertex); 
     } 


    } 

    public void rewind(Vector3d internalPoint){ 
     //the winding of the verticies MUST be such that it looks anticlockwise 
     //from the "outside", however, this method allows points to be added with 
     //either clockwise or anticlockwise winding and then a final point that is 
     //anywhere on the inside of the shape specified in this method and if the 
     //wrong winding was used this rewinds it to anticlockwise winding 

     if (pointIsInsideFace(internalPoint)==false){ 
      //winding is 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 the last vertex connects to the 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 for last edge 
    } 

    private double getPointVsFaceDeterminant(Vector3d point){ 
     //this method is a bit meaningless but its used in 
     //pointIsInsideFace(Vector3d point) 
     //and 
     //getIntersectionPoint 

     //the returned determinant is basically a measure of which side 
     //(and how far) a point lies from the plane 

     //FOR THIS TO WORK FACE MUST HAVE ANTICLOCKWISE WINDING WHEN LOOKED AT 
     //FROM OUTSIDE 

     //we define faces as having their verticies in such an order that 
     //when looked at from the outside the points are ordered anticlockswise 
     //SO this function is 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 is convex, we only need the first 3 points to determine 
     //the "winding" of the face 

     if (verticies.size()<3){ 
      throw new RuntimeException("Degenerate Face: Face has less than 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 the 3 by 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 THIS TO WORK FACE MUST HAVE ANTICLOCKWISE WINDING WHEN LOOKED AT 
     //FROM OUTSIDE 

     //we define faces as having their verticies in such an order that 
     //when looked at from the outside the points are ordered anticlockswise 
     //SO this function is 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 the 3 by 3 matrix described in link (see also: http://www.mathsisfun.com/algebra/matrix-determinant.html) 
     double determinant=getPointVsFaceDeterminant(point); 
     if (determinant<=0){ 
      // <= because we define on the face to be "inside the face" 
      return true; 
     }else{ 
      return false; 
     } 


    } 

    public Vector3d getIntersectionPoint(Vector3d rayPoint1, Vector3d rayPoint2){ 
     //NOTE: This method treats the face as if it was an infinite plane 
     //this treating as a plane is why convex shapes must be used 


     //see http://mathworld.wolfram.com/Plane.html 
     //changed from above method as that can get upset with parallel lines 

     double determinantPoint1=getPointVsFaceDeterminant(rayPoint1); 
     double determinantPoint2=getPointVsFaceDeterminant(rayPoint2); 

     if (determinantPoint1==determinantPoint2){ 
      //paralell line, if we've got into this method then it'll probably 
      //be in the plane, the line is in the plane, the middle seems the 
      //most reasonable point 

      Vector3d average=new Vector3d(); 
      average.add(rayPoint1, rayPoint2); 
      average.scale(0.5); 

      return average; 
     }else{ 
      //we want to return the point where the determinant would 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 from www.jhave.org/learner/misc/sutherlandhodgman/sutherlandhogdmanclipping.shtml 

     //Note, this face may be entirely clipped by the clipping face 
     //or clipped to a degenerate edge, in this case null is returned 

     Face workingFace=new Face(); 

     for(int i=0;i<this.getNumberOfEdges();i++){ 
      //clips all the edges of the working polygon against a plane based upon the clipping face 
      //for each edge there are 4 cases, we must determine which it is 
      //where we refer to starting and ending verticies they are of workingFace 
      //where we refer to "the Face" that is the clipping face 
      //and endEdge. The edge of the clipping polygon 
      //case 1) both starting verticies are inside face 
      //case 2) starting vertex is inside face, ending vertex is inside 
      //case 3) Both verticies are outside the face 
      //case 4) starting is outside the face, ending is inside 

      Vector3d point1=getStartOfEdge(i); 
      Vector3d point2=getEndOfEdge(i); 

      if (clippingFace.pointIsInsideFace(point1) && clippingFace.pointIsInsideFace(point2)){ 
       //case 1, the end point is added 
       workingFace.addVertex(point2); 
      }else if (clippingFace.pointIsInsideFace(point1) && clippingFace.pointIsInsideFace(point2)==false){ 
       //case 2, only the intersection is added 
       Vector3d intersection=clippingFace.getIntersectionPoint(point1, point2); 
       workingFace.addVertex(intersection); 
      }else if (clippingFace.pointIsInsideFace(point1)==false && clippingFace.pointIsInsideFace(point2)==false){ 
       //case 3, both verticies are outside the clip shape line, no vertexes added 
      }else{ 
       //case 4 the ending vertex is inside and the starting vertex is outside 
       //the line 
       //the intercept and the end point are 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 completely culled face 
     } 

    } 

    private int getNumberOfSegments(){ 
     return verticies.size()-2; 
    } 


    //VISUALISATION ONLY ############### 
    //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; 
    } 

} 

Lớp chủ yếu sau đây tạo ra những hình ảnh hiển thị và làm cho họ sử dụng công cụ JMonkey thư viện

import javax.vecmath.Vector3d; 

//VISUALISATION ONLY 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 to 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 the top and bottom x different (so its not actually a 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 for 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; 
    } 

}