找到两个3D多边形的交集 [英] Finding the intersection of two 3D polygons
本文介绍了找到两个3D多边形的交集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
a.k.a。 3D中的多边形裁剪算法
a.k.a. Polygon clipping algorithm in 3D
a.k.a。找到2个碰撞多边形之间的碰撞流形
a.k.a. Finding the collision manifold between 2 colliding polygons
多边形裁剪的大多数算法都是针对2D进行详细描述的，并描述为可扩展到3D但没有细节。例如 sutherland-hodgman剪辑算法
Most algorithms for polygon clipping are described in detail for 2D and described as being extendable to 3D but without details. For example the sutherland-hodgman clipping algorithm
我无法在互联网上找到任何3D实现或伪代码，我现在在这里问（并尝试回答我自己的问题）
Having been unable to find any 3D implementations or pseudo code on the internet I am now asking here (and attempting to answer my own question)
该算法将采用两种形状，如下所示：
The algorithm would take two shapes such as those shown below:
并输出两种形状的交集，如下所示：
And would output the intersection of the two shapes as shown below:
请注意，尽管Sutherland-Hodgman算法找到了两个多边形的交集，但它（以及大多数其他多边形）做出了区分剪切多边形和剪切多边形之间;修剪的多边形可以是凹的或凸的，但是修剪的形状必须是凸的。 然而，我在扩展到3D时的实现要求两个形状都是凸，这表明它不是真正的3D sutherland-hodgman算法，而其他答案（使用任何算法）解除这个要求将非常多赞赏
Note that although the Sutherland-Hodgman algorithm finds the intersection of two polygons it (and most others) make a distinction between the clipped polygon and the clipping polygon; the clipped polygon may be concave or convex, but the clipping shape must be convex. However, my implementation in extending to 3D requires that both shapes be convex, this suggests that it is not a true 3D sutherland-hodgman algorithm and other answers (using any algorithm) lifting this requirement would be very much appreciated
推荐答案
2D sutherland-hodgman剪裁算法通过剪裁形状的每个边缘剪切剪裁形状的每个边缘。然而，3D算法通过裁剪形状的每个面（不是剪裁形状的每个面的每个边缘）剪切剪裁形状的每个面的每个边缘。
The 2D sutherland-hodgman clipping algorithm clips each edge of the clipped shape by each edge of the clipping shape. The 3D algorithm, however, clips each edge of each face of the clipped shape by each face of the clipping shape (NOT each edge of each face of the clipping shape).
我的算法受到这种方法的启发，但我不得不添加一个额外的步骤来使所有边缘正确地出现。基本上我剪了两种方式;用另一个剪切一个形状然后反向并添加两个;这导致要求两个形状都是凸的。未能包含这种双向错过了一些面孔，如下所示
My algorithm is "inspired" by this approach but I had to add an extra step to get all the edges to come out correctly. Basically I clipped both ways; clipping one shape by the other then doing the reverse and adding the two; this causes the requirement that both shapes be convex. Failing to include this "both ways" misses some of the faces as shown below
此算法的伪代码如下：
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
这个算法在java中得到了充分体现，如下所示：
（注意JMonkey引擎用于3D可视化，但是它被标记为所以它是ca很容易被剥离出来）
This algorithm is implimented in java as shown below: (Note JMonkey engine is used for 3D visualisation but is demarked so it can be easily stripped out)
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;
}
}
以下主类创建显示的图像并使用JMonkey引擎库呈现它们
The following main class creates the images shown and renders them using the JMonkey engine library
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;
}
}
这篇关于找到两个3D多边形的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
