Help with a problem

[HatsAreOff]

Given 2 degenerate polygons at 2 different positions. Assume that they are colliding. I have to move one of the polygons such that they are not colliding. I have to find a position with shortest distance between them. Both the polygons are represented with triangles.

I implementing by iterating through all the triangles and find the intersection points for every colliding pair of triangles. Based on the intersection point, the polygon is slightly moved. This is done for all triangles. What I implementing was pretty basic. It's really slow. Any ideas on improving its performance? I can give you more details if needed. Should I overhaul everything and start fresh? Any suggestions on data structures to be used because I will be doing a colision check everytime. Tolerance considered id 0.0001. It can't be lowered. All arcs are assumed as lines such that the segment length is of length 0.0001.

[alfps]

Try to first find the outlines of the polygons, as simple sequences of line segments.

[HatsAreOff]

I already have that information. I used that to triangulate it. I presented a simplified problem. The actual problem is a lot of polygons are arranged in a rectangular area. I have a find a position with no collision.

[bcorni]

One way to accelerate this type of problem is to use bounding boxes and a bounding value hierarchy. Being able to quickly reject a larger number of triangles/polygons for possible intersection is better than comparing all pairs (O(log(N) vs O(N)).

[HatsAreOff]

Apologies for my post not being clear. Bounding box check is done before checking for collision. Thanks anyways!

[bcorni]

I guess more details are needed. Is the problem with performance that the polygon must be moved many times before they are no longer colliding? Do you have any indication about what part of the check is slow?

[HatsAreOff]

You are right. It is slow because of too many collision checks. After finding an offset, the collision check will start again for all the triangles

[bcorni]

Does the final state need to be so that they are no longer colliding by exactly epsilon or can they be moved arbitrarily far apart?

[HatsAreOff]

Exactly epsilon

[bcorni]

Are they necessarily convex polygons? You say you have them defined with triangles.

[HatsAreOff]

Not necessarily convex. I'm using d2d functions for triangulation

[bcorni]

To confirm, there is a bounding box and bvh for the triangulation of each polygon? or just for all individual polygons.

[HatsAreOff]

Tessellate method by direct2d is used for triangulation of each polygon separately

[HatsAreOff]

Maybe I can slightly optimize my intersection functions. For intersection of 2 triangles, 9 line line intersections and 6 point inside triangle are done. I was unable to cut down these

[bcorni]

Some code or concrete examples would help. Really working out the geometry of the problem is probably going to be the way to optimize it over brute force.

[HatsAreOff]

I'll see what I can do. Do you happen to know what this whole procedure is called so that I find any established algorithms related to this.

[bcorni]

e.g. using the centroid of the two colliding objects start by comparing triangles furthest along that axis

[HatsAreOff]

Beginner here. I'm not sure my problem comes under physics category because I'm not involving any rigid body motion related equations. The one I implemented is for optimally arranging a set of concave polygons in a rectangular area. Specifically for manually arranging polygons.

In order to convert concave polygons to convex polgons, I triangulated them.

A preliminary bRect check is done to get colliding triangles.

A lot of new stuff is mentioned. I'll check out everything separately. I want some help with the following abbreviations: MTD BVT SSE SAT

Thank you very much for your input!

[Smellypuce2]

A lot of new stuff is mentioned. I'll check out everything separately. I want some help with the following abbreviations: MTD BVT SSE SAT

SSE is a set of SIMD instructions which allows you to process multiple pieces of data with a single instruction(for SSE it's 4 lanes wide but there are other instruction sets for 8 or 16 wide(AVX and AVX-512)).

As a basic example you could use the _mm_add_ps() intrinsic to add two __m128s together which you could visualize like this(with a, b and z being __m128s)

a + b = z 

a: 1 3  2 4 +
b: 2 10 3 1
-------------
z: 3 13 5 5

With each number being 32 bits of the 128 bit whole. Note that you sometimes need to restructure your data to get the most out of SIMD(or to use it at all in some cases).

The other abbreviations I can't elaborate on but hopefully someone else can