Describe the bug I'm digging towards a deeper bug. I have a softw

Stackoverflow Exception on Difference Operation about csg HOT 3 OPEN

kikootwo commented on June 27, 2024

Stackoverflow Exception on Difference Operation

from csg.

Comments (3)

erictuvesson commented on June 27, 2024

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:

from csg.

kikootwo commented on June 27, 2024

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.

from csg.

erictuvesson commented on June 27, 2024

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. :(

from csg.

Stackoverflow Exception on Difference Operation about csg HOT 3 OPEN

Comments (3)

Related Issues (8)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	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());
	}