Another CSG solution

Btw, some time ago, I was also having issues with INTERSECTION (that created big meshes while tiny were expected), so now I prepared a test case to check if it was still present, but the issue seems gone! Probably in function of the many changes/fixed you provided :smile:

But, while testing with this new code, I went into this exception:

	java.lang.IllegalArgumentException: CSGSolid.splitFaces - too many splits:629502
		at net.wcomohundro.jme3.csg.iob.CSGSolid.splitFaces(CSGSolid.java:206)
		at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.composeSolid(CSGShapeIOB.java:614)
		at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.intersection(CSGShapeIOB.java:311)
		at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.intersection(CSGShapeIOB.java:1)
		at net.wcomohundro.jme3.csg.CSGShape.intersection(CSGShape.java:670)
		at net.wcomohundro.jme3.csg.CSGGeometry.regenerate(CSGGeometry.java:398)
		at net.wcomohundro.jme3.csg.CSGGeometry.regenerate(CSGGeometry.java:345)

The actual problem with this is that regenerate() may take too long to end with exception. The minimum here took about 30s, but I saw it last like 5min (the most I waited anyway).

So, I would like to suggest this patch at CSGSolid.java (the throw InterruptedException line), but I dont know if it can cause any trouble elsewhere:

public void splitFaces(...){
  ...
  loop1:	for( int i = 0, j = initialLimit; i < (j = mFaces.size()); i += 1 ) {
    if(Thread.currentThread().isInterrupted())throw new InterruptedException();

With that, we can monitor the thread and interrupt it safely/cleanly at that spot (as just below it has another throw).

The actual point on interrupting is that small changes in the location of shapes may simply allow it to work as expected. Or alternatively, we can skip the regenerate() to release CPU if it is taking too long.

This new (a bit messy) test case below can be run differently by setting bThreaded = true, what demonstrates the InterruptedException “quick recover functionality” (if false it will simply pop the splitFaces() exception). Also, it will work without the InterruptedException patch, so the time these threads take to complete, the exceptions and the CPU usage will be noticeable:

public class TestCSGintersection extends SimpleApplication{
	public static void main(String[] 	pArgs) {
	    SimpleApplication app = new TestCSGintersection();		    
	    app.start();
	}
	
	private boolean	bThreaded = false; // set to true to skip the exceptions and retry
	private int	iMaxSluggishThreads = Runtime.getRuntime().availableProcessors();
	
	private CSGGeometry	geom;
	private CSGShape	shapePrev;
	private CSGShape	shapeSphere;
	private CSGShape	shapeSphereI;
	private int iInteractionCount;
	private boolean bDancing=false;
	ArrayList<RThread> aSluggishThreads = new ArrayList<RThread>();
	ArrayList<Vector3f> apos = new ArrayList<Vector3f>();
	ArrayList<Vector3f> aposI = new ArrayList<Vector3f>();
	private Material	mat;
	private long	ltimep;
	private CSGGeometry	geomI;
	private BoundingBox	bbPrev = new BoundingBox();
	
	public TestCSGintersection() {
		super( new StatsAppState(), new FlyCamAppState(), new DebugKeysAppState() );
	}
	
	@Override
	public void simpleInitApp() {
  	geom = new CSGGeometry("hi");
  	
  	CSGShape aCube = new CSGShape("Box", new CSGBox(1,1,1));
  	geom.addShape(aCube);
  	geom.regenerate();
  	
    mat = new Material( assetManager, "Common/MatDefs/Misc/ShowNormals.j3md" );
  	geom.setMaterial( mat );
  	
  	shapeSphere	= new CSGShape( "Sphere", new CSGSphere( 5, 5, 0.3f ) );
  	shapeSphereI = new CSGShape( "Sphere", new CSGSphere( 5, 5, 0.3f ) );
  	
   	rootNode.attachChild( geom );
   		
  	geomI = new CSGGeometry("hiI");
  	geomI.setMaterial(mat);
  	geomI.move(new Vector3f(2,0,0));
  	rootNode.attachChild(geomI);
   	
  	testErrSplits();
  	
  	System.out.println("private void testErrSplits(){");
  }
	
	/**
	 * intersection pos is predicted
	 */
	private void testErrSplits(){
		apos.add(new Vector3f(0.83990216f,0.01416303f,0.41397852f)); //1, [0:1454110976715ms][0:(0.0, 0.0, 0.0);0.0]
		apos.add(new Vector3f(0.14809741f,0.30853847f,0.32987046f)); //2, [1:58ms][1:(0.1648531, 0.2834636, 0.3);0.4444414]
		apos.add(new Vector3f(0.54515183f,0.29772508f,0.26086247f)); //3, [2:11ms][2:(0.2713526, 0.28531697, 0.3);0.49501315]
		apos.add(new Vector3f(0.50555390f,0.28294140f,0.73018849f)); //4, [3:8ms][3:(0.2713526, 0.27231753, 0.3);0.4876362]
		apos.add(new Vector3f(0.67798418f,0.78858733f,0.27823582f)); //5, [4:3ms][4:(0.27135253, 0.28531694, 0.29456878);0.4917405]
		apos.add(new Vector3f(0.00424497f,0.13861489f,0.73975629f)); //6, [5:5ms][5:(0.23324549, 0.24334115, 0.28711078);0.44277644]
		apos.add(new Vector3f(0.37070101f,0.58056056f,0.03278502f)); //7, [6:4ms][6:(0.24722548, 0.28531694, 0.24818724);0.45179987]
		//errDelay:29.85s
		/*
		java.lang.IllegalArgumentException: CSGSolid.splitFaces - too many splits:629502
			at net.wcomohundro.jme3.csg.iob.CSGSolid.splitFaces(CSGSolid.java:206)
			at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.composeSolid(CSGShapeIOB.java:614)
			at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.intersection(CSGShapeIOB.java:311)
			at net.wcomohundro.jme3.csg.iob.CSGShapeIOB.intersection(CSGShapeIOB.java:1)
			at net.wcomohundro.jme3.csg.CSGShape.intersection(CSGShape.java:670)
			at net.wcomohundro.jme3.csg.CSGGeometry.regenerate(CSGGeometry.java:398)
			at net.wcomohundro.jme3.csg.CSGGeometry.regenerate(CSGGeometry.java:345)
		*/
	}
	
  @Override
  public void simpleUpdate(float tpf) {
  	org.lwjgl.input.Mouse.setGrabbed(false);
  	
  	if(shapePrev==null)shapePrev = new CSGShape("Box", new CSGBox(1,1,1));
  	geom.addShape(shapePrev);
  	
  	String fromArray="";
  	if(apos.size()>0){
  		shapeSphere.setLocalTranslation(apos.remove(0));
  		fromArray="A:";
  	}else{
  		shapeSphere.setLocalTranslation(geom.getLocalTranslation());
    	shapeSphere.move(randPos(null).multLocal(0.9f));
  	}
  	
  	System.out.println("apos.add(new Vector3f"+dump(shapeSphere.getLocalTranslation())+"); //"
  			+fromArray+(++iInteractionCount)+", "
  			+"["+(iInteractionCount-1)+":"+(System.currentTimeMillis()-ltimep)+"ms]"
  			+"["+(iInteractionCount-1)+":"+bbPrev.getExtent(null)+";"+bbPrev.getExtent(null).length()+"]"
  	);
  	ltimep = System.currentTimeMillis();
  	
  	geom.addShape( shapeSphere, CSGOperator.DIFFERENCE );
  	
  	try{
    	shapePrev = geom.regenerate();
    	if(bThreaded ){
      	while(!threadedDance()){
      		System.err.println("//Too many threads "+aSluggishThreads.size()+", unable to start a new."+System.currentTimeMillis()+"...");
      		Thread.sleep(3000);
      	}
    	}else{
    		intersectionDance();
    	}
  	}catch(Exception ex){
  		System.err.println("//errDelay:"+(System.currentTimeMillis()-ltimep)/1000f+"s");
  		System.err.println("/*");
  		ex.printStackTrace();
  		System.err.println("*/");
  		exit1();
  	}
  	
  	geom.removeAllShapes();
  }
  
  private class RThread extends Thread{
  	RRun r;
  	public RThread(RRun r,int i){
  		super(r);
  		this.r=r;
    	setName("thread:"+i);
  	}
  	public RRun r(){
  		return r;
  	}
  }
  private class RRun implements Runnable{
  	long lTime=System.currentTimeMillis();
		boolean bSuccess=false;
		int i;
		public RRun(int i){
			this.i=i;
		}
		@Override
		public void run() {
			try{
				intersectionDance();
				bSuccess=true;
	  	}catch(Exception ex){
	  		System.err.println("// EXCEPTION: thread:"+i+", "+getLifeTime()+", "+ex.getMessage());
	  		return; //would still be dancing... 
	  	}
			bDancing=false;
		}
		public String getLifeTime(){
			return ""+(System.currentTimeMillis()-lTime)/1000f+"s";
		}
  }
  
  private boolean threadedDance(){
  	boolean bStartedNewThread=false;
  	// avoid clog cpu
  	if(aSluggishThreads.size() < iMaxSluggishThreads ){
  		bDancing=true;
    	RThread t = new RThread(new RRun(iInteractionCount),iInteractionCount);
    	t.start();
    	bStartedNewThread=true;
    	
    	aSluggishThreads.add(t);
  	
	//  	int iHundredths=10;//100;
	  	int iHundredths=500;
	  	try {
	  		int iSleepCount=0;
	  		while(++iSleepCount<iHundredths){
	    		Thread.sleep(10);
	  			if(!t.isAlive()){
	//      		System.err.println("// THREAD-ENDED "+t.getName());
	  				aSluggishThreads.remove(t); //ended properly and in time
	  				break;
	  			}
	  		}
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
	  	
	  	if(bDancing){
	  		System.err.println("// THREAD-INTERRUPTING "+t.getName()+" intersection calc totThreads="+aSluggishThreads.size());
	  		t.setPriority(Thread.MIN_PRIORITY);
	  		t.interrupt();
	  	}
  	}
  	
		for(RThread t2 : aSluggishThreads.toArray(new RThread[0])){
			if(!t2.isAlive()){
				if(t2.r().bSuccess){
      		System.err.println("// THREAD actually ended properly: "+t2.getName()+", "+t2.r().getLifeTime());
				}//else was the exception log message
				aSluggishThreads.remove(t2);
			}
		}
		
		return bStartedNewThread;
  }
  
  private void intersectionDance(){
  	geomI.removeAllShapes(); //begin cleaning
  	
  	CSGShape shapePrevToI = new CSGShape("cloneToI",geom.getMesh().deepClone());
  	geomI.addShape(shapePrevToI);
  	
  	Vector3f pos = shapeSphere.getLocalTranslation();
  	shapeSphereI.setLocalTranslation(pos);
  	shapeSphereI.move(randPos(pos.length()).multLocal(0.1f));
  	geomI.addShape(shapeSphereI, CSGOperator.INTERSECTION);
  	
 		CSGShape shapeI = geomI.regenerate(); // <---<<
  	boundsCheck();
  }
  
  private void boundsCheck(){
	//	geomI.updateGeometricState();
		geomI.updateModelBound();
		BoundingBox bb = ((BoundingBox)geomI.getModelBound());
		bbPrev = bb;
		if(bb.getExtent(null).length() > 2f){
			System.err.println("//"+bb.toString());
			exit1();
		}
  }
  
  /**
   * 
   * @param fSeed grants predictable randoms for predefined positions array
   * @return
   */
  private Vector3f randPos(Float fSeed){
  	Random rnd = fSeed==null ? FastMath.rand : new Random(fSeed.longValue());
  	//return new Vector3f(rnd.nextFloat()*2f-1f, rnd.nextFloat()*2f-1f, rnd.nextFloat()*2f-1f);
  	return new Vector3f(rnd.nextFloat(), rnd.nextFloat(), rnd.nextFloat());
  }
  
	private String dump(Vector3f pos) {
		return String.format("(%01.8ff,%01.8ff,%01.8ff)",pos.x,pos.y,pos.z);
	}
	
	private void exit1(){
		System.err.println("}");
		System.exit(1);
	}
  
}

PS.: oh also another subject, I think GeometryBatchFactory can be helpful with CSGGeonode to provide a single mesh with many materials mixed and overall lightweight.

The bogus triangle example you posted in [20] above was very helpful in unearthing a couple of low level bugs that kicked in when triangles were very to close to each other. These have been fixed and the new code is available in SVN. The [20] example now seems to work properly.
The new processing looks pretty good to me (but that is what I said last time) Your eyes seem much better atuned at spotting such anomalies than mine, so please keep reporting on anything you may find.

I have implemented the interrupted thread processing you mentioned, but have not yet run your threading test case. I am working through a more comprehensive error reporting mechanism, but it is still in its early stages. Feel free to tinker and post back any comments.

1 Like

I have had a chance to work with your IntersectionTest and the infinite split problem. I tuned up the face-to-face scan in the split processor and optimized it to eliminate unnecessary checks after a face split occurs. And with the optimization in place, your test case no longer causes infinite splits.

I am thinking that the split problem was caused by something like this. Face7 in SolidA overlaps with Face10 in SolidB and must be split. After the optimization, the subfaces of 7 can start their checks with Face11 in SolidB. After all, we broke 7 apart to eliminate the overlap, so faces 1 thru 10 in B have already been handled. But before the optimization, we ran a full check on the newly added subfaces against all the SolidB faces. My guess is that because of rounding/near zero problems, one of the subfaces of 7A collided with 10B again, and then we split that subface. And then that subsubface of 7 collided with 10B and again and again and again…

If you find another example of the infinite split problem, please post it. I would like to eliminate all such hassles if possible.

FYI – the CSGTestSceneLoader now interrupts its background action thread on KEY_DELETE. The interrupted processing seems to work just fine. The thread monitor is checked in both the heavy load loops: split faces and raytrace.

1 Like

If anyone out there wants to use the jme3 SDK, I have rebuilt the CSG jar and posted it to SourceForge. It includes all the fixes mentioned in this thread.

3 Likes

I have just checked a new fix into SVN. It eliminates bogus overlapping triangles from two blended solids that start with a common surface.

2 Likes

I encountered another bogus triangle test case, which I have tracked down and fixed.
The changes are in SVN, and I have rebuilt the jars and posted everything back to SourceForge. The sample Windows executable now contains various applications, which you select via a dialog on startup

2 Likes

Nice, very glad to see that you are keeping this working :smile:

Can’t await to finally reach the destruction parts for my ships and use this more

1 Like

hey!

I tested a git clone, and it is working with jme3.1-beta1! but only the net.wcomohundro.jme3 code tree.

I would like to suggest, when releasing it, to put that core code tree as a separate jar to be an easy project plugin :slight_smile:

I am using this build.xml file:

<?xml version="1.0" ?>
<!-- Configuration of the Ant build system to generate a Jar file --> 
<project name="WCOmoCSG" default="CreateJar">
  <target name="CreateJar" description="Create Jar file">
    <jar jarfile="WCOmoCSG.jar" basedir="bin" includes="**/*.class" />
  </target>
  <target name="CreateSourcesJar" description="Create Sources Jar file">
    <jar jarfile="WCOmoCSG-sources.jar" basedir="src" includes="**/*.java" />
  </target>
</project>

and as it seems you are using eclipse too, here is to the point instructions http://stackoverflow.com/a/12200309/1422630 (make sure to read the comments as they improved that answer).

PS.: I actually had to remove the other code tree, so I did not specify the net path yet.

Good suggestion, I will try to break the code apart in a future release. Thanks for the sample Ant build.

1 Like

How do I compile that with ant? I tried build.xml above but this creates empty .jar file with META-INF only

Sorry, but I never really followed up with the Ant build script, so I honestly do not know what might be going wrong.
FYI - while the CSG code continues to work for me, I am building with older jMonkey code. I can not say what might happen with the newest revisions of jMonkey. Upgrading to the latest release of jMonkey is on my todo list, but it is not yet done (and I have no target date in mind)

How did you pack your code to jar? I wanted to upgrade this to work with new versions but there was no sources inside jar. I think I could just drop all the files in my project tree and use them

P.S. What version of jme you’re using?

  1. I run everything through Eclipse and do not use the jMonkey IDE at all.
  2. Full CSG source is available via SourceForge
    (jMonkeyCSG / Code / [r280]). It has a ‘snapshot’
    option that will load all the source into a zip for you.
  3. When I was actively developing, I was pulling the latest jme3 source
    directly from GitHub. The last time I pulled, jMonkey was at version 5454,
    which was before they did the 3.1 release.
  4. I leverage the XML loader extensively to do my testing. But that means I had
    to patch several places in the jme3 core where the existing XML read mechanism
    would corrupt the target entity. You can see which jme3 core sources I changed
    by looking in the source code com.jme3 package. All the CSG source is isolated
    in its own package.
  5. CSG might possibly run without any of the jme3 core changes, but not via XML
    loading. I have never really tested that, so don’t hold your breath.

I have completed changes necessary to get the CSG code back in line with the jme3 releases. My latest version is now completely compatible with the jme3 3.2.1 SDK. Everything is checked back into SourceForge, and the ReadMe there describes the changes to the jar structure. You can now easily incorporate CSG into your jme3 IDE just by adding a single jar into your project.

I hope this helps. Please post any issues via the SourceForge Tickets.

3 Likes

Seriously, this is so cool!