Stackoverflow Exception on Difference Operation

[kikootwo]

Describe the bug
I'm digging towards a deeper bug. I have a software that performs thousands of CSG operations, I am getting hard exits of the application (no exception or anything) with an access violation error code. When I log each operation, I found the last one it did was a difference (subtract) operation. I extracted the geometry for that operation and tried to manually do a difference operation between these two and I get a stack overflow exception. The geometry is pretty simple. The current CSG library that I am using succeeds this operation. I am looking to change to this CSG library (since it is ~4x faster that our current one).

To Reproduce

1. I have 2 specific shapes that I am trying to do a difference operation between. I will provide their 'hashes' as well as methods for getting the vertices from the hashes.

string hash1 = "MTAuMDQxNjY3IC0wLjI0MjAyODk4IDAKNDcuOTE2NjY4IDAuNDE2NjY2NjYgMAo0Ny45MTY2NjggLTAuNDE2NjY2NjYgMAoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgMAoxMC4wNDE2NjcgLTAuMjQyMDI4OTggMAo0Ny45MTY2NjggLTAuNDE2NjY2NjYgMAoxMC4wNDE2NjcgMC40MTY2NjY2NiAwCjQ3LjkxNjY2OCAwLjQxNjY2NjY2IDAKMTAuMDQxNjY3IC0wLjI0MjAyODk4IDAKMS44NzUgLTAuNDE2NjY2NyAwCjAgLTAuNDE2NjY2NjYgMAoxLjg3NSAtMC4zODQwNTc5NyAwCjEuODc1IC0wLjM4NDA1Nzk3IDAKMCAtMC40MTY2NjY2NiAwCjAgMC40MTY2NjY2NiAwCjEuODc1IDAuNDE2NjY2NyAwCjEuODc1IC0wLjM4NDA1Nzk3IDAKMCAwLjQxNjY2NjY2IDAKNDcuOTE2NjY4IC0wLjQxNjY2NjY2IDAKNDcuOTE2NjY4IC0wLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAtMC40MTY2NjY2NiAyLjMwNTIxNzUKMTAuMDQxNjY3IC0wLjQxNjY2NjY2IDAKNDcuOTE2NjY4IC0wLjQxNjY2NjY2IDAKMTAuMDQxNjY3IC0wLjQxNjY2NjY2IDIuMzA1MjE3NQoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgMTEKMTAuMDQxNjY3IC0wLjQxNjY2NjY2IDIuMzA1MjE3NQo0Ny45MTY2NjggLTAuNDE2NjY2NjYgMTEKMTAuMDQxNjY3IC0wLjQxNjY2NjY2IDExCjAgLTAuNDE2NjY2NjYgMTEKMCAtMC40MTY2NjY2NiA3LjkxNjY2NwoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgNy45MTY2NjcKMTAuMDQxNjY3IC0wLjQxNjY2NjY2IDExCjAgLTAuNDE2NjY2NjYgNy45MTY2NjcKMCAtMC40MTY2NjY2NiA3LjkxNjY2NwowIC0wLjQxNjY2NjY2IDExCjAgLTAuMTgzMDgwODIgNy45MTY2NjcKMCAwLjQxNjY2NjY2IDcuOTE2NjY3CjAgLTAuMTgzMDgwODIgNy45MTY2NjcKMCAtMC40MTY2NjY2NiAxMQowIDAuNDE2NjY2NjYgMTEKMCAwLjQxNjY2NjY2IDcuOTE2NjY3CjAgLTAuNDE2NjY2NjYgMTEKMCAtMC40MTY2NjY2NiA3LjkxNjY2NwowIC0wLjE4MzA4MDgyIDcuOTE2NjY3CjAgMC40MTY2NjY2NiAwCjAgLTAuNDE2NjY2NjYgMAowIC0wLjQxNjY2NjY2IDcuOTE2NjY3CjAgMC40MTY2NjY2NiAwCjAgMC40MTY2NjY2NiA3LjkxNjY2NwowIDAuNDE2NjY2NjYgMAowIC0wLjE4MzA4MDgyIDcuOTE2NjY3CjEwLjA0MTY2NyAwLjQxNjY2NjY2IDAKMTAuMDQxNjY3IDAuNDE2NjY2NjYgOC42OTQ3ODIKNDcuOTE2NjY4IDAuNDE2NjY2NjYgMAo0Ny45MTY2NjggMC40MTY2NjY2NiAxMQo0Ny45MTY2NjggMC40MTY2NjY2NiAwCjEwLjA0MTY2NyAwLjQxNjY2NjY2IDguNjk0NzgyCjEwLjA0MTY2NyAwLjQxNjY2NjY2IDExCjQ3LjkxNjY2OCAwLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAwLjQxNjY2NjY2IDguNjk0NzgyCjAgMC40MTY2NjY2NiA3LjkxNjY2NwowIDAuNDE2NjY2NjYgMTEKMTAuMDQxNjY3IDAuNDE2NjY2NjYgOC42OTQ3ODIKMTAuMDQxNjY3IDAuNDE2NjY2NjYgNy45MTY2NjcKMCAwLjQxNjY2NjY2IDcuOTE2NjY3CjEwLjA0MTY2NyAwLjQxNjY2NjY2IDguNjk0NzgyCjEwLjA0MTY2NyAwLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAwLjQxNjY2NjY2IDguNjk0NzgyCjAgMC40MTY2NjY2NiAxMQo0Ny45MTY2NjggMC40MTY2NjY2NiAwCjQ3LjkxNjY2OCAwLjQxNjY2NjY2IDExCjQ3LjkxNjY2OCAtMC40MTY2NjY2NiAwCjQ3LjkxNjY2OCAtMC40MTY2NjY2NiAxMQo0Ny45MTY2NjggLTAuNDE2NjY2NjYgMAo0Ny45MTY2NjggMC40MTY2NjY2NiAxMQoxMC4wNDE2NjcgMC40MTY2NjY2NiAxMQoxMC4wNDE2NjcgLTAuMjQyMDI4OTggMTEKNDcuOTE2NjY4IDAuNDE2NjY2NjYgMTEKNDcuOTE2NjY4IC0wLjQxNjY2NjY2IDExCjQ3LjkxNjY2OCAwLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAtMC4yNDIwMjg5OCAxMQoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgMTEKNDcuOTE2NjY4IC0wLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAtMC4yNDIwMjg5OCAxMQowIDAuNDE2NjY2NjYgMTEKMCAtMC40MTY2NjY2NiAxMQoxMC4wNDE2NjcgLTAuMjQyMDI4OTggMTEKMTAuMDQxNjY3IDAuNDE2NjY2NjYgMTEKMCAwLjQxNjY2NjY2IDExCjEwLjA0MTY2NyAtMC4yNDIwMjg5OCAxMQoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgMTEKMTAuMDQxNjY3IC0wLjI0MjAyODk4IDExCjAgLTAuNDE2NjY2NjYgMTEKMTAuMDQxNjY4IC0wLjQxNjY2NjYzIDMuNzI2MzMzNgoxMC4wNDE2NjggLTAuNDE2NjY2NSA0LjU4MzMzMzUKMTAuMDQxNjY3IDAuNDE2NjY2NjYgMy45MTY2NjY3CjEwLjA0MTY2OCAtMC40MTY2NjY2NiAxLjgxMjc1MDYKMTAuMDQxNjY4IC0wLjQxNjY2NjYzIDMuNzI2MzMzNgoxMC4wNDE2NjcgMC40MTY2NjY2NiAzLjkxNjY2NjcKMTAuMDQxNjY4IC0wLjQxNjY2NjYzIDEuNDIzNDUzRS0wNwoxMC4wNDE2NjggLTAuNDE2NjY2NjYgMS44MTI3NTA2CjEwLjA0MTY2NyAwLjQxNjY2NjY2IDMuOTE2NjY2NwoxMC4wNDE2NjYgMC40MTY2NjY2NiAxLjIxNjQwNTFFLTA3CjEwLjA0MTY2OCAtMC40MTY2NjY2MyAxLjQyMzQ1M0UtMDcKMTAuMDQxNjY3IDAuNDE2NjY2NjYgMy45MTY2NjY3CjEwLjA0MTY2NiAtMC40MTY2NjY2NiA0LjU4MzMzMwoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgNy45MTY2NjcKMTAuMDQxNjY3IDAuNDE2NjY2NSA3LjkxNjY2NwoxMC4wNDE2NjcgMC40MTY2NjY2MyAzLjkxNjY2NjUKMTAuMDQxNjY2IC0wLjQxNjY2NjY2IDQuNTgzMzMzCjEwLjA0MTY2NyAwLjQxNjY2NjUgNy45MTY2NjcKMTAuMDQxNjY4IC0wLjQxNjY2NjY2IDEuODEyNzUwNgoxMC4wNDE2NjggLTAuNDE2NjY2NyAzLjYwMjM5OTMKMTAuMDQxNjY4IC0wLjQxNjY2NjYzIDMuNzI2MzMzNgo1Ljk1ODMzNCAwLjQxNjY2NjUgNy45MTY2NjcKMTAuMDQxNjY3IDAuNDE2NjY2NiA3LjkxNjY2NwoxMC4wNDE2NjcgLTAuNDE2NjY2NjMgNy45MTY2NjcKNS4yNzc3NzggLTAuNDE2NjY2NjYgNy45MTY2NjcKNS45NTgzMzQgMC40MTY2NjY1IDcuOTE2NjY3CjEwLjA0MTY2NyAtMC40MTY2NjY2MyA3LjkxNjY2Nwo1LjI3Nzc3OCAtMC40MTY2NjY2MyA3LjkxNjY2NwoxLjg3NSAtMC40MTY2NjY2NiA3LjkxNjY2NwoxLjg3NSAwLjQxNjY2NjUgNy45MTY2NjcKNS45NTgzMzM1IDAuNDE2NjY2NiA3LjkxNjY2Nwo1LjI3Nzc3OCAtMC40MTY2NjY2MyA3LjkxNjY2NwoxLjg3NSAwLjQxNjY2NjUgNy45MTY2NjcKMS44NzUgMC40MTY2NjY2NiA2LjY5MjA0OAoxLjg3NTAwMDEgMC40MTY2NjY2IDcuOTE2NjY3CjEuODc1IC0wLjQxNjY2NjYzIDcuOTE2NjY3CjEuODc1IDAuNDE2NjY2NjMgMy45MTY2NjcKMS44NzUgMC40MTY2NjY2NiA2LjY5MjA0OAoxLjg3NSAtMC40MTY2NjY2MyA3LjkxNjY2NwoxLjg3NSAtMC40MTY2NjY3IDMuMjUwMDAwNQoxLjg3NSAwLjQxNjY2NjYzIDMuOTE2NjY3CjEuODc1IC0wLjQxNjY2NjYzIDcuOTE2NjY3CjEuODc1IC0wLjQxNjY2NjY2IDUuNTE2NTYxNQoxLjg3NSAtMC40MTY2NjY3IDMuMjUwMDAwNQoxLjg3NSAtMC40MTY2NjY2MyA3LjkxNjY2NwoxLjg3NSAwLjQxNjY2NjUgMS4yMTY0MDU0RS0wNwoxLjg3NTAwMDIgMC40MTY2NjY2IDMuOTE2NjY3MgoxLjg3NTAwMDIgLTAuNDE2NjY2NjMgMy4yNTAwMDA1CjEuODc1MDAwMSAtMC40MTY2NjY2NiAxLjAwOTM1NzY1RS0wNwoxLjg3NSAwLjQxNjY2NjUgMS4yMTY0MDU0RS0wNwoxLjg3NTAwMDIgLTAuNDE2NjY2NjMgMy4yNTAwMDA1CjEuODc1IDAuNDE2NjY2NyAwCjAgMC40MTY2NjY2NiAwCjAgMC40MTY2NjY2NiA3LjkxNjY2NwoxLjg3NSAwLjQxNjY2NjcgNy45MTY2NjcKMS44NzUgMC40MTY2NjY3IDAKMCAwLjQxNjY2NjY2IDcuOTE2NjY3CjEwLjA0MTY2NiAwLjQxNjY2NjY2IDEuMjE2NDA1MUUtMDcKMTAuMDQxNjY3IDAuNDE2NjY2NjYgMy45MTY2NjY3CjEwLjA0MTY2OCAwLjQxNjY2NjcgMy45MTY2NjY3CjEuODc1IC0wLjQxNjY2NjcgMAoxLjg3NSAtMC40MTY2NjY3IDAuNDMwNDM0NzYKMCAtMC40MTY2NjY2NiAwCjAgLTAuNDE2NjY2NjYgNy45MTY2NjcKMCAtMC40MTY2NjY2NiAwCjEuODc1IC0wLjQxNjY2NjcgMC40MzA0MzQ3NgoxLjg3NSAtMC40MTY2NjY3IDcuOTE2NjY3CjAgLTAuNDE2NjY2NjYgNy45MTY2NjcKMS44NzUgLTAuNDE2NjY2NyAwLjQzMDQzNDc2CjEuODc1IC0wLjQxNjY2NjY2IDUuNTE2NTYxNQoxLjg3NSAtMC40MTY2NjY3IDMuMjUwMDAwNQoxLjg3NSAtMC40MTY2NjY3IDMuMjUwMDAwNQoxMC4wNDE2NjggLTAuNDE2NjY2NjYgMS44MTI3NTA2CjEwLjA0MTY2OCAtMC40MTY2NjY3IDMuNTI0NjM3NQoxMC4wNDE2NjggLTAuNDE2NjY2NyAzLjYwMjM5OTMKMTAuMDQxNjY2IC0wLjQxNjY2NjY2IDQuNTgzMzMzCjEwLjA0MTY2NyAtMC40MTY2NjY3IDQuNTgzMzMzNQoxMC4wNDE2NjcgLTAuNDE2NjY2NjYgNy45MTY2NjcKMS44NzUgLTAuNDE2NjY2NjYgNS41MTY1NjE1CjEuODc1IC0wLjQxNjY2NjcgMy4yNTAwMDA1CjEuODc1IC0wLjQxNjY2NjcgMy4yNTAwMDA1Cg==";

string hash2 = "MjUuODc1IC00LjU4MzMzMzUgLTAuMDgzMzMzMjU0CjM0LjA0MTY2OCAtNC41ODMzMzM1IDcuOTE2NjY3CjI1Ljg3NSAtNC41ODMzMzM1IDcuOTE2NjY3CjM0LjA0MTY2OCAtNC41ODMzMzM1IDcuOTE2NjY3CjI1Ljg3NSAtNC41ODMzMzM1IC0wLjA4MzMzMzI1NAozNC4wNDE2NjggLTQuNTgzMzMzNSAtMC4wODMzMzMyNTQKMzQuMDQxNjY4IC00LjU4MzMzMzUgLTAuMDgzMzMzMjU0CjM0LjA0MTY2OCA1LjQxNjY2NjUgLTAuMDgzMzMzMjU0CjM0LjA0MTY2OCAtNC41ODMzMzM1IDcuOTE2NjY3CjM0LjA0MTY2OCA1LjQxNjY2NjUgNy45MTY2NjcKMzQuMDQxNjY4IC00LjU4MzMzMzUgNy45MTY2NjcKMzQuMDQxNjY4IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQKMzQuMDQxNjY4IC00LjU4MzMzMzUgNy45MTY2NjcKMzQuMDQxNjY4IDUuNDE2NjY2NSA3LjkxNjY2NwoyNS44NzUgLTQuNTgzMzMzNSA3LjkxNjY2NwoyNS44NzUgNS40MTY2NjY1IDcuOTE2NjY3CjI1Ljg3NSAtNC41ODMzMzM1IDcuOTE2NjY3CjM0LjA0MTY2OCA1LjQxNjY2NjUgNy45MTY2NjcKMjUuODc1IC00LjU4MzMzMzUgNy45MTY2NjcKMjUuODc1IDUuNDE2NjY2NSA3LjkxNjY2NwoyNS44NzUgLTQuNTgzMzMzNSAtMC4wODMzMzMyNTQKMjUuODc1IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQKMjUuODc1IC00LjU4MzMzMzUgLTAuMDgzMzMzMjU0CjI1Ljg3NSA1LjQxNjY2NjUgNy45MTY2NjcKMjUuODc1IC00LjU4MzMzMzUgLTAuMDgzMzMzMjU0CjI1Ljg3NSA1LjQxNjY2NjUgLTAuMDgzMzMzMjU0CjM0LjA0MTY2OCAtNC41ODMzMzM1IC0wLjA4MzMzMzI1NAozNC4wNDE2NjggNS40MTY2NjY1IC0wLjA4MzMzMzI1NAozNC4wNDE2NjggLTQuNTgzMzMzNSAtMC4wODMzMzMyNTQKMjUuODc1IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQKMzQuMDQxNjY4IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQKMjUuODc1IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQKMzQuMDQxNjY4IDUuNDE2NjY2NSA3LjkxNjY2NwoyNS44NzUgNS40MTY2NjY1IDcuOTE2NjY3CjM0LjA0MTY2OCA1LjQxNjY2NjUgNy45MTY2NjcKMjUuODc1IDUuNDE2NjY2NSAtMC4wODMzMzMyNTQK";

Code for turning the hash into vertices:

string hash = (Hash from Above)
List<Vector3> vertices = new List<Vector3>();
hash = Encoding.UTF8.GetString(Convert.FromBase64String(hash));
List<string> verts = hash.Split('\n').ToList();
foreach (string s in verts.Where(x => !string.IsNullOrEmpty(x)))
{
    string[] pts = s.Split(' ');
    float.TryParse(pts[0], out var x);
    float.TryParse(pts[1], out var y);
    float.TryParse(pts[2], out var z);
    vertices.Add(new Vector3(x, y, z));
}

Expected behavior
The red cube should cut out from the purple rectangle

Screenshots

Desktop (please complete the following information):

• OS: windows 10, .net 5.0.8 Windows WPF Application

Please let me know if there is anything else I can provide to help with the debugging of this issue.

Thanks!

[erictuvesson]

Hi,

I did a little bit of digging and came to the conclusion that the issue is when making a big polygon of all the vertices.
It creates a endless loop creating BSP nodes.
Should look into adding some check so it doesn't just crash without exception.

CSG/src/CSG/Algorithms/Plane.cs

Lines 36 to 126 in 79a60a3

	public void SplitPolygon(Polygon polygon,
	List<Polygon> coplanarFront,
	List<Polygon> coplanarBack,
	List<Polygon> front,
	List<Polygon> back)
	{
	var (type, types) = PossibleTypes(polygon);
	switch (type)
	{
	default:
	case PolygonType.Coplanar:
	{
	if (Vector3.Dot(this.Normal, polygon.Plane.Normal) > 0)
	{
	coplanarFront.Add(polygon);
	}
	else
	{
	coplanarBack.Add(polygon);
	}
	}
	break;
	case PolygonType.Front:
	{
	front.Add(polygon);
	}
	break;
	case PolygonType.Back:
	{
	back.Add(polygon);
	}
	break;
	case PolygonType.Spanning:
	{
	List<Vertex> f = new List<Vertex>();
	List<Vertex> b = new List<Vertex>();
	for (int i = 0; i < polygon.Vertices.Count; i++)
	{
	int j = (i + 1) % polygon.Vertices.Count;
	var ti = types[i];
	var tj = types[j];
	var vi = polygon.Vertices[i];
	var vj = polygon.Vertices[j];
	if (ti != PolygonType.Back)
	{
	f.Add(vi);
	}
	if (ti != PolygonType.Front)
	{
	b.Add(vi);
	}
	if ((ti | tj) == PolygonType.Spanning)
	{
	var t = (this.W - Vector3.Dot(this.Normal, vi.Position)) /
	Vector3.Dot(this.Normal, vj.Position - vi.Position);
	var vertex = Helpers.Interpolate(vi, vj, t);
	f.Add(vertex);
	b.Add(vertex);
	}
	}
	if (f.Count >= 3) front.Add(new Polygon(f));
	if (b.Count >= 3) back.Add(new Polygon(b));
	}
	break;
	}
	}
	private (PolygonType, PolygonType[]) PossibleTypes(Polygon polygon)
	{
	PolygonType result = 0;
	var types = new List<PolygonType>();
	for (int i = 0; i < polygon.Vertices.Count; i++)
	{
	float t = Vector3.Dot(this.Normal, polygon.Vertices[i].Position) - this.W;
	var type = (t < -EPSILON) ? PolygonType.Back :
	((t > EPSILON) ? PolygonType.Front : PolygonType.Coplanar);
	types.Add(type);
	result |= type;
	}
	return (result, types.ToArray());
	}

I have not used this library in a production setting yet, so I am not sure how stable it is at scale.

I am a bit surprised this library is faster than something else, I find this extremely slow.
I started working on a big update to the internal workings which will start moving it to real-time performance, unfortunately it got put on hold for now.

---

I assumed that every 3 vertex builds a triangle based on the data, and got this result.

Hash1:

Hash2:

Subtract:

[kikootwo]

First of all, thank you for the prompt and detailed reply!

I should have been more specific, you were correct in your assumption that the vertices are a large list of triangle data. Every 3 make up a triangle. In my implementation, I am doing the same thing as you (without the fancy linq chunk). I make 1 polygon per triangle.

I tried your newest committed code. I no longer get the stack overflow exception, but I am hitting your new BSPMaxDepthException. I tried returning there, instead of throwing an exception, but then the model is missing its back face. I even tried replacing my polygon building with your linq query version and got the same polygons and the same final result.

Maybe I misunderstood, were you saying this is a known limitation? Or am I still doing something wrong here?

And finally to comment on the speed: Yes, CSG modelling is slow. But you should take pride in the fact that your library is essentially the only C# implementation that I have found actively being developed and in rudimentary tests, performs 4x faster than the other solution I am using.

[erictuvesson]

I had a look at it, and tried one solution that made it not crash, but it caused a lot of artifacts.

I don't have have the bandwidth right now to look more at the issue. :(