BoolMesh.java (boolean operations on mesh)

@Fabian

following this wiki http://en.wikipedia.org/wiki/UV_mapping,
i put this UV mapping at your SphereBrush.sphereVertex():
return new Vertex(…, …, new Vector2f( 0.5f + (FastMath.atan2(dir.z,dir.x) / FastMath.TWO_PI), 0.5f - (FastMath.asin(dir.y) / FastMath.PI) ));

but it only “worked with glitches” for union() and intersect(),
not at all for subtract()

any other tip as I have no idea how it actually works? :slight_smile:

@Fabian,

ok to see the result I had to show both faces, I just modified the material this way (before applying it to the geometry):
mat.getAdditionalRenderState().setFaceCullMode(FaceCullMode.Off);

now the subtract() result is visible.

of course, this is pure improvisation that I did, so it has glitches and limitations I guess…

@teique,

I’m not entirely sure if this actually has anything to do with your problem, but when I tried the first usage example shown at https://github.com/andychase/fabian-csg#usage (in which a sphere is subtracted from a cube) with setFaceCullMode(FaceCullMode.Off) commented out I found the faces were inverted. This can be fixed by adding a line to Polygon.java:

public void flip() { Vertex[] temp = new Vertex[vertices.length]; for (int i = 0; i < temp.length; i++) { vertices[i].flip(); temp[temp.length - i - 1] = vertices[i]; } vertices = temp; //This is the added line - I guess it was left out by accident, seeing as how temp would never be used otherwise... plane.flip(); }

Even if your problem isn’t caused by flipped faces, this should probably be added anyway…

Also, I have some questions (for Fabian, I presume):

  1. Being a CSG implementation, does that mean this library cannot cope with complex geometry? (CSG is about simple convex solids, right???) If yes, then what are MeshBrushes for?
  2. Using Fabian CSG I found triangles that were nowhere near the other geometry were split into smaller triangles, which seems inefficient. Can this be fixed, or is it a core part of the algorithm?

PS: Are code snippets working right now? I tried adding one, but the single quote mark that appeared looked suspicious, compared to HTML tags for everything else, and teique seemed to be having trouble too.

1 Like

@Plerdi

Very good!! I thought facecull off could be weighty to the engine, now it is fixed thx!

I am having some exception problems when I try to union or subtract a very big sphere from a smaller mesh, sometimes I had this kind of problem also with boolmesh from the other CSG author I mentioned in the OP, so my guess it is a CSG limitation; what I am doing is catch the exception to keep the application running and the boolean operation simply does not happen; as I still dont understand how it works, I have no idea how to overcome that either.

btw, as soon I can, I will try to export, at runtime, the JME simple meshes (shapes), like sphere, cylinder etc. to FabianCSG, and see if it is possible to use these ones instead of the few accompained brushes, because, for ex., I saw that a sphere can have 3 modes of texture disposition, and this UV mapping may be exportable to the CSG too! also, such code could be used to export any mesh to CSG mode I think.

@teique

What exceptions are you getting? I just tried to subtract a tetrahedron from a much larger fairly complex shape, using 2 MeshBrushes, and I got stack overflow with a stack trace full of “org.fabian.csg.Node build (Node.java:62)” and no operation occurring. I fixed this by changing EPSILON in Plane.java to 1e-2 from 1e-5, so if you are getting similar exceptions try this fix and see if it works for you, although the exact epsilon I used may not be suitable for you, especially if you have points and planes close together.
Originally build() was looping because splitPolygon() thought points on the plane weren’t on the plane because epsilon was too small. The new epsilon I used is probably way too big in most cases, so I guess we need to find a good value for epsilon. Someone else will have to do that; I know nothing about choosing good epsilon values!

From looking at splitPolygon() in Plane.java, it looks like the whole algorithm is built around splitting polygons along planes, so it would appear that the answer to my second question is that the excess of faces is part of the core algorithm, and cannot be fixed; faces seem to be generated when polygons are split by planes. I don’t know about your use of the library, but extra unnecessary faces and points could be a problem for my project.

@Plerdi, I was developing other things and overlooked the exception that was happening here. I found that, the CSG subtraction was so big that the whole mesh vanished and remained 0 polygons hehe…

In another test tho, I got this one, may be similar to yours:

java.lang.StackOverflowError
	at org.fabian.csg.Plane.splitPolygon(Plane.java:37)
	at org.fabian.csg.Node.build(Node.java:61)
	at org.fabian.csg.Node.build(Node.java:64)

here is the code:

public void test2(){ //TODO fix, not working Material mat_csg = new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"); Texture tex = assetManager.loadTexture("Textures/Terrain/splat/road.jpg"); mat_csg.setTexture("ColorMap", tex);
CSGNode csg = new CSGNode();
csg.setMaterial(mat_csg);

Spatial s = new Geometry("model", new Torus(10, 10, 3f, 4f));
			
ArrayList&lt;Geometry&gt; g = new ArrayList&lt;&gt;();
GeometryBatchFactory.gatherGeoms(s, g);
Mesh m = new Mesh();
GeometryBatchFactory.mergeGeometries(g, m);
MeshBrush mb = new MeshBrush(m);
csg.addBrush(mb);
//CubeBrush base = new CubeBrush(new Vector3f(0f, 0.5f, 0f), new Vector3f(1f, 0.1f, 1f));
CubeBrush base = new CubeBrush(new Vector3f(0f, 1.5f, 0f), new Vector3f(1f, 0.1f, 1f));
base.setType(BrushType.SUBTRACTIVE);

csg.addBrush(base);
csg.regenerate();
csg.move(0f, 1f, 0f);

getRootNode().attachChild(csg);			

}

What I was thinking is to trap that exception, dynamically change the EPSYLON and retry, until it works. I am thinking on catching it at Node.build(), but the problem is if the member variables have been modified in a way that a retry would not work. So basically, we would have to backup all that data before trying, so we can use the fresh data on the retry. The easiest way would be to code it all outside CSG code. May be cpu and memory consuming but “will” work!

Btw, may be the extra faces and points can be simply cleaned out after the CSG boolean operation. So even if it does not generate what you need, it can still become it later on!

@Plerdi, but thinking again, the best is, in the CSG code, try to dethermine if a stackoverflow may happen and implement the fix on the right spot. A pity I have no idea how it works, but some wild guesses may work hehe…

@teique

I tried your test with the new epsilon of 1e-2, and it worked fine. However, I managed to find the following test that worked on the old 1e-5 epsilon, but not the new 1e-2:

Material mat_csg = new Material(assetManager, "Common/MatDefs/Misc/Unshaded.j3md"); Texture tex = assetManager.loadTexture("Textures/Terrain/splat/road.jpg"); mat_csg.setTexture("ColorMap", tex);
    CSGNode csg = new CSGNode();
    csg.setMaterial(mat_csg);

    CubeBrush cube1 = new CubeBrush(new Vector3f(0f, 0f, 0f), new Vector3f(1f, 1f, 1f));
    csg.addBrush(cube1);

    CubeBrush cube2 = new CubeBrush(new Vector3f(0.01f, 1.5f, 0f), new Vector3f(1f, 1f, 1f));
    cube2.setType(BrushType.SUBTRACTIVE);
    csg.addBrush(cube2);

    csg.regenerate();
    getRootNode().attachChild(csg);

Before I try your suggestion of trial and error I might look into finding the correct epsilon value, because I know there is some way to choose the epsilon based on the numbers you are using:
http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

I will also try to merge faces after the operation, although that might slow things down a bit as it will require a triangulation.

I will see if I can understand that epsilon too, I think it is better. I tried 1e-2 with other tests and it didnt work either.

May be some stacktraces may help too, so here is another (of another test) :slight_smile:

java.lang.StackOverflowError at java.util.ArrayList.grow(ArrayList.java:242) at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:216) at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:208) at java.util.ArrayList.add(ArrayList.java:440) at org.fabian.csg.Plane.splitPolygon(Plane.java:56) at org.fabian.csg.Node.build(Node.java:61) at org.fabian.csg.Node.build(Node.java:64) at org.fabian.csg.Node.build(Node.java:64)

may be we can figure out based on these too, so if you got some stacks drop them so I can check too!

It would appear that all stack overflows caused by Node.build() calling itself are due to a bad epsilon.

@teique said: @Plerdi, but thinking again, the best is, in the CSG code, try to dethermine if a stackoverflow may happen and implement the fix on the right spot. A pity I have no idea how it works, but some wild guesses may work hehe..

IN THEORY, if there is an issue with epsilon, there will be a node built that thinks the polygon that it used to find it’s plane isn’t on its own plane, which can be checked. If the program notices Nodes being created that are all identical after that issue has been detected, there is probably an epsilon issue, so the epsilon can be made larger specially for that node. However, I don’t know about any tests you may have done, but I found that tests using 1e-2 failed silently, so the default epsilon would need to be 1e-5. But of course, we should look into improving the epsilon in the other way first.

I found a way to fix the excess points/faces issue by not splitting the plane-spanning polygons that were outside the bounding box of the other CSG. However, that method has failed on my second test, so either it needs some work or it is a terrible idea. But at least it should be faster than merging polygons afterwards!

(double post)

so epsilon could be a dynamic number!

so the point is to analyse the the mesh and determine the right epsilon right? may be even fix the mesh a bit to it fit properly on an specified epsilon?

On my blind approach, that I still need to try is make a blind loop changing epsilons values, so, if it fails with default one, tries another near one like:
1e-5
9e-6 (more precision just for the luck of it)
2e-5 … 9e-5
8e-6
1e-4 … 9e-4
1e-3 … 9e-3

1e-1

I just need to make such loop and see what happens, it may be cpu consuming, time consuming and memory consuming, but if it works at the end it is ok, and it can always be computed on a background thread!

I think I know how to track it,
at debug, detect at which point the code looses itself, and at that moment,
the variables data can be checked to create workarounds,
so we can predict what and how things go wrong.

as a tip, I got a simple rectangular box mesh (not cubic, like a wall), and modified it several times on several spots with small spheres;
the problem may be related to very small polygons I guess…
I couldnt yet understand exactly what caused the problem.

By “rectangular mesh”, do you literally mean a 2 dimensional mesh, or is it a solid box shape? If it is 2D you may find the library is not able to work with it; after all, it is Constructive SOLID Geometry…
If it is a solid shape, and the solids involved are REALLY small (i.e. the same size as epsilon) it probably is an epsilon issue.

Also, I was thinking of trying to run the coplanar check with 1e-2, and if the result was coplanar retry with doubles or BigDecimals and a smaller epsilon. I tried it with doubles, which didn’t work, but I have managed to get BigDecimals working for the torus test case, (and the smaller epsilon even managed to get down to 0 and still work!) but the cube test where the 1e-2 was previously too big still doesn’t work, so I will try to fix that.

I wrote not precisely, it was like a wall mesh.

I am I bit lost as you can see, I didnt have time yet to understand what epsilon means… and that is why I can only think on wild fixes (retry on failures with slightly diff values).

I believe you are thinking on increasing the precision of the calculations right? there was some explanations why jmonkey uses floats and not doubles, may be it just interferes with engine speed.
But what we need on CSG is precision (and usability).
If it will be slower, at least the end result will not be impossible (as it happens somewhat often right now) or weird (in case we try to make changes to let it work and end with something too weird).

So what you are thinking is on changing everything that is float to double? or just the moment it makes these highly precise calculations, cast to double or bigdecimal? http://stackoverflow.com/questions/3413448/double-vs-bigdecimal

If it is that, what I would wildly do is, if it fail, I retry casting to double, and if fail again I retry with bigdecimal. But I am just wildly thinking again hehe :slight_smile:

The plan is to first try it with floats as this is faster. If the result is coplanar, it will be checked again using BigDecimals (and a smaller epsilon). This way most checks should be able to just keep the speed of float, while the vertices that are close to planes will be given the precision of BigDecimal. The first epsilon will be large, (1e-2 or larger) so that any failures will result in vertices being counted as coplanar (which is rechecked) and genuinely coplanar vertices will never be counted as not on the plane (the epsilon is too big for that).

So, your rectangular wall like mesh, is it enclosed with a clear inside and outside, or is it just a quad, with only a front and back? :slight_smile: nvm, I just saw “box mesh”; it’s fully enclosed, right? :slight_smile:

1 Like

@Plerdi, yep, that is a box like a wall.
I wonder also if just directly setting everything to bigdecimal would be safer/granted, unless it is going to be used very often, then performance would be preferable. In my case it could just be bigdecimals…

@Plerdi, hey any news?

After I make about 5 small subtractions of the main CSG mesh, it will always cause exception; I do not stop the application but I can work with that mesh anymore, so it gets like frozen; my guess is the subtracting shape must not contain too small triangles but I am not sure, just a guess again…

Small triangles could probably make a mess with epsilon, so perhaps that could be the issue. As far as I know, the only exceptions caused by a bad epsilon are StackOverflows caused by Node.build() calling itself, so if that’s the exception you’re getting then the epsilon may well be inappropriate for your small triangles; try changing the epsilon and see if that helps.
When you preform a CSG operation with FabianCSG, the triangles on the mesh will be broken down in to many smaller, unnecessary, triangles. This might add to any issues you were having with small triangles, and I found it rapidly slowed down the speed of operations as I preformed multiple subtractions on the same mesh; my second and third operations took many seconds. Could this be the source of your freezing?

I had a go at implementing the idea of checking the vertex type using floats and then double checking with BigDecimals using the code below. This worked with the [two cubes test][1] above, but not using a torus or with some other tests I tried (the application froze for several minutes, and eventually closed and logged a StackOverflow of Node.build()). I’m not currently working on that, so here’s the source code for what I have so far:

In Plane.java split():

	int polygonType = 0;
	int[] types = new int[polygon.getVertices().length];
	for (int i = 0; i < polygon.getVertices().length; i++) {
                    Vector3f p = polygon.getVertices()[i].getPosition();
		float t = normal.dot(p) - w;
		int type = (t < -EPSILON) ? BACK : (t > EPSILON) ? FRONT : COPLANAR;
                    if(type == COPLANAR){
                        Vector3b a = new Vector3b(points[0]);
                        Vector3b b = new Vector3b(points[1]);
                        Vector3b c = new Vector3b(points[2]);
                        Vector3b n = b.subtractLocal(a).crossLocal(c.subtractLocal(a)).normalizeLocal();
                        BigDecimal bw = n.dot(a);
                        if(flipped){
                            n.negateLocal();
                            bw = bw.negate();
                        }
                        BigDecimal d = n.dot(new Vector3b(p)).subtract(bw);
                        type = (d.doubleValue() < -SMALL_EPSILON) ? BACK : (d.doubleValue() > SMALL_EPSILON) ? FRONT : COPLANAR;
                    }
		polygonType |= type;
		types[i] = type;
	}

Other changes to Plane.java:

public static final double EPSILON = 1e-2;
    public static final double SMALL_EPSILON = 1e-5;
private Vector3f normal;
private float w;
    private Vector3f[] points;
    private boolean flipped = false;
public Plane(Vector3f normal, float w, Vector3f[] p) {
	this.normal = normal;
	this.w = w;
            points = p;
}

public static Plane fromPoints(Vector3f a, Vector3f b, Vector3f c) {
            Vector3f n = b.subtract(a).cross(c.subtract(a)).normalizeLocal();
	return new Plane(n, n.dot(a), new Vector3f[]{a, b, c});
}

public Plane clone() {
	return new Plane(normal.clone(), w, points.clone());
}

public void flip() {
	normal = normal.negate();
	w = -w;
            flipped =! flipped;
}

org.fabian.csg.Vector3b.java:

package org.fabian.csg;

import com.jme3.math.Vector3f;
import java.math.BigDecimal;
import java.math.RoundingMode;

public class Vector3b {
public BigDecimal x;
public BigDecimal y;
public BigDecimal z;

public Vector3b(BigDecimal argx, BigDecimal argy, BigDecimal argz){
    x = argx;
    y = argy;
    z = argz;
}

public Vector3b(Vector3f v){
    x = new BigDecimal(v.x);
    y = new BigDecimal(v.y);
    z = new BigDecimal(v.z);
}

public Vector3b subtractLocal(Vector3b v){
    x = x.subtract(v.x);
    y = y.subtract(v.y);
    z = z.subtract(v.z);
    return this;
}

public Vector3b crossLocal(Vector3b v){
    BigDecimal tempx = y.multiply(v.z).subtract(z.multiply(v.y));
    BigDecimal tempy = z.multiply(v.x).subtract(x.multiply(v.z));
    z = x.multiply(v.y).subtract(y.multiply(v.x));
    x = tempx;
    y = tempy;
    return this;
}

public Vector3b normalizeLocal(){
    BigDecimal length = x.multiply(x).add(y.multiply(y)).add(z.multiply(z));
    double lengthD = length.doubleValue();
    if (lengthD != 1 && lengthD != 0){
        length = sqrt(length, 1000);
        x = x.divide(length, RoundingMode.HALF_UP);
        y = y.divide(length, RoundingMode.HALF_UP);
        z = z.divide(length, RoundingMode.HALF_UP);
    }
    return this;
}

public BigDecimal dot(Vector3b v){
    return x.multiply(v.x).add(y.multiply(v.y)).add(z.multiply(v.z));
}

public Vector3b negateLocal() {
    x = x.negate();
    y = y.negate();
    z = z.negate();
    return this;
}

private static BigDecimal sqrt(BigDecimal A, final int SCALE) {
    BigDecimal x0 = new BigDecimal("0");
    BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
    while (!x0.equals(x1)) {
        x0 = x1;
        x1 = A.divide(x0, SCALE, RoundingMode.HALF_UP);
        x1 = x1.add(x0);
        x1 = x1.divide(new BigDecimal(2), SCALE, RoundingMode.HALF_UP);
    }
    return x1;
}

@Override
public String toString() {
    return "(" + x.stripTrailingZeros() + ", " + y.stripTrailingZeros() + ", " + z.stripTrailingZeros() + ")";
}

}
[1]: BoolMesh.java (boolean operations on mesh) - #29 by Plerdi

1 Like