又名3D 中的多边形裁剪算法
又名找到 2 个碰撞多边形之间的碰撞流形
大多数用于多边形裁剪的算法都针对 2D 进行了详细描述，并描述为可扩展到 3D 但没有详细信息。例如 sutherland-hodgman clipping algorithm
由于无法在互联网上找到任何 3D 实现或伪代码，我现在在这里提问(并试图回答我自己的问题)
该算法将采用两种形状，如下所示:
并且会输出两个形状的交集，如下所示:
请注意，尽管 Sutherland-Hodgman 算法找到了两个多边形的交集，但它(以及大多数其他算法)在裁剪多边形和裁剪多边形之间进行了区分；裁剪多边形可以是凹的或凸的，但裁剪形状必须是凸的。 但是，我扩展到 3D 的实现要求两个形状都是凸的，这表明它不是真正的 3D sutherland-hodgman 算法和其他答案(使用任何算法)提升这个要求会非常多赞赏
最佳答案
2D sutherland-hodgman 裁剪算法通过裁剪形状的每条边裁剪裁剪形状的每条边。然而，3D 算法通过剪裁形状的每个面剪裁剪裁形状的每个面的每个边(不是剪裁形状每个面的每个边)。
我的算法受到这种方法的“启发”，但我必须添加一个额外的步骤才能使所有边都正确显示。基本上我双向剪裁；用另一个形状剪裁一个形状，然后进行相反的操作并添加两个；这导致要求两个形状都是凸的。未能包含此“双向”会错过一些面孔，如下所示
该算法的伪代码如下
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 可视化，但已标记，因此可以轻松剥离)
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 引擎库渲染它们
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;
}
}
关于java - 找到两个 3D 多边形的交点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16389217/