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;
import com.jme3.asset.AssetManager;
import com.jme3.math.ColorRGBA;
import com.jme3.scene.Node;
public class Polygon3D {
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){
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){
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);
}
}
Face workingFace=clippingFace;
for(int i=0;i<inPolygon.getNumberOfFaces();i++){
if (workingFace==null){
break;
}
workingFace=workingFace.clipFace(inPolygon.getFace(i));
}
if (workingFace!=null){
outPolygon.addFace(workingFace);
}
return outPolygon;
}
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;
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;
public class Face{
ArrayList<Vector3d> verticies=new ArrayList<Vector3d>();
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)){
}else{
verticies.add(vertex);
}
}
public void rewind(Vector3d internalPoint){
if (pointIsInsideFace(internalPoint)==false){
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();
}
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());
}
private double getPointVsFaceDeterminant(Vector3d point){
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);
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){
double determinant=getPointVsFaceDeterminant(point);
if (determinant<=0){
return true;
}else{
return false;
}
}
public Vector3d getIntersectionPoint(Vector3d rayPoint1, Vector3d rayPoint2){
double determinantPoint1=getPointVsFaceDeterminant(rayPoint1);
double determinantPoint2=getPointVsFaceDeterminant(rayPoint2);
if (determinantPoint1==determinantPoint2){
Vector3d average=new Vector3d();
average.add(rayPoint1, rayPoint2);
average.scale(0.5);
return average;
}else{
Vector3d intersect=new Vector3d();
intersect.sub(rayPoint2, rayPoint1);
intersect.scale((0-determinantPoint1)/(determinantPoint2-determinantPoint1));
intersect.add(rayPoint1);
return intersect;
}
}
public Face clipFace(Face clippingFace){
Face workingFace=new Face();
for(int i=0;i<this.getNumberOfEdges();i++){
Vector3d point1=getStartOfEdge(i);
Vector3d point2=getEndOfEdge(i);
if (clippingFace.pointIsInsideFace(point1) && clippingFace.pointIsInsideFace(point2)){
workingFace.addVertex(point2);
}else if (clippingFace.pointIsInsideFace(point1) && clippingFace.pointIsInsideFace(point2)==false){
Vector3d intersection=clippingFace.getIntersectionPoint(point1, point2);
workingFace.addVertex(intersection);
}else if (clippingFace.pointIsInsideFace(point1)==false && clippingFace.pointIsInsideFace(point2)==false){
}else{
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;
}
}
private int getNumberOfSegments(){
return verticies.size()-2;
}
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;
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);
poly3.render(assetManager, rootNode,ColorRGBA.Red);
}
public Polygon3D getCubePolygon(Vector3d mins, Vector3d maxs, double xSkew){
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));
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;
}
}