Collision detection between shape geometry(using array of points) and plane geometry

Questions
1

Hi Everyone,

I am trying to implement bins filling algorithm by allowing user to create freehand polygon by drawing lines and then making shape geometry from points/vertices of lines. Then trying to add the bin meshes in scene using min and max of the drawn polygon. After that, I am trying to keep the bins meshes that have collision with drawn polygon and are not interesting with lines.

However, the shape polygon to plane collision doesnt seems to work as expected. It always returns true. which causes all bins loading.

image
image.png1920×1080 205 KB

Can someone help me in detecting correct collision in this case?
Here is the code i am using

var polygonPoints = pointsArr;//polygon points array

		//Polygon region geometry
        var extrudeSettings = { depth: 8, bevelEnabled: true, bevelSegments: 2, steps: 2, bevelSize: 1, bevelThickness: 1 };
        var polygonShape = new THREE.Shape(polygonPoints);
        var polygonGeometry = new THREE.ExtrudeBufferGeometry(polygonShape, extrudeSettings);
        var polygonMesh = new THREE.Mesh(polygonGeometry , new THREE.MeshPhongMaterial({ color: 0xf08000 }));
        scene.add(polygonMesh);

        //bins geometry
        var planeGeometry = new THREE.PlaneGeometry(binPaneSize.x, binPaneSize.y);
        var planematerial = new THREE.MeshBasicMaterial({ color: 0xffff00, side: THREE.DoubleSide });
        var binMesh = new THREE.Mesh(planeGeometry, planematerial);

        var polygonOutBounds = {
            minX: Math.min.apply(Math, polygonPoints.map(function (o) { return o.x; })),
            minY: Math.min.apply(Math, polygonPoints.map(function (o) { return o.y; })),
            maxX: Math.max.apply(Math, polygonPoints.map(function (o) { return o.x; })),
            maxY: Math.max.apply(Math, polygonPoints.map(function (o) { return o.y; }))
        };
        
        for (var i = polygonOutBounds.minX; i < polygonOutBounds.maxX; i += binPaneSize.x + binPaneOffset.x) {
            for (var j = polygonOutBounds.minY; j < polygonOutBounds.maxY; j += binPaneSize.y + binPaneOffset.y) {
                console.log(i + " - " + j);
                var _binMesh = binMesh.clone();
                scene.add(_binMesh);
                _binMesh.position.set(i, j, 2);
                if (!WebglEngine.DetectCollisionOfObjects(polygonMesh,_binMesh )) {
                    console.log('test');
                    scene.remove(_binMesh);
                }
            }
        }

Function for collision detection.

	    	DetectCollisionOfObjects: function (object1, object2) {
            object1.geometry.computeBoundingBox(); //not needed if its already calculated
            object2.geometry.computeBoundingBox();
            object1.updateMatrixWorld();
            object2.updateMatrixWorld();

            var obj1 = object1.geometry.boundingBox.clone();
            obj1.applyMatrix4(object1.matrixWorld);

            var obj2 = object2.geometry.boundingBox.clone();
            obj2.applyMatrix4(object2.matrixWorld);
            
            return obj1.intersectsBox(obj2);
        },
2

It seems your issue is a bit unclear. Demonstrating the collision test with a simple live example might help to understand what’s going wrong.

Tip: Please avoid using clone() in your DetectCollisionOfObjects function. Creating objects in functions which are frequently invocated is a bad practise since object creation and the related GC overhead are expensive operations in JavaScript. The solution is to create two intermediate bounding boxes in module or closure (IIFE) scope and then reuse these instances via copy().

obj1.copy( object1.geometry.boundingBox );
obj2.copy( object2.geometry.boundingBox );
3

Hi @Mugen87: Here is the codepen link for sample demo. https://codepen.io/MilindAnantwar/pen/qBWyWdO

I want to keep the bins/plane that are overlapping/colliding with the shape geometry created out of points array.

4

It’s still not very obvious (to me, at least) what you want to achieve. ELI5! :wink:

OrbitControls don’t seem to work very well with camera z-up. The easiest solution for z-up is to wrap z-up objects in a container with rotation.x =0.5*Math.PI.

5

As you can see in the following example, the AABB of polygonMesh (the helper object with red lines) extends over all bin shapes. That’s the reason why all intersection tests are positive.

https://jsfiddle.net/yfab42k8/1/

6

How should i change the code in order to have AABB of polgonmesh to be its own area and not the rectangle shape(helper with red lines)

7

I’m not sure I understand. An AABB has always the shape of a box and is always axis-aligned.

It seems what you actually need is a collision detection test between an AABB (representing your bins) and a concave polygon (representing polygonMesh) which is not trivial to implement.

8
BrainstormInstead of checking the intersections, would it be an option to render the polygon to a rendertarget with matching resolution, and use the rendertarget texture to guide the coloring of the bins? Or, similarly, throw a bunch of rays at the polygon and use the results? Hm, none of these solutions will be exact. :thinking:

An exact solution would be, for each bin, to first check whether a line segment from the bin center to outside the grid intersects an odd number of edges. If not, return false. Intersect the bin rectangle with all the edges. If it intersects at least one, return false. Else return true. (The two tests can be swapped, but both must be passed.)

1 Like
9

Thank @Mugen87 and @EliasHasle

I am planning to use following javascript solution that accepts point and polygonpointsarray and return if point is lying inside. I will do this for all four vertices of plane. If all returns true, then plane is inside polygon.

10

Not necessarily. The polygon could have inward spikes that pierce the edges of the rectangle. But if you check the center point and then intersect the edges against the bin rectangle, you can have an exact solution (as outlined above).

11

Thanks @EliasHasle. I did not get how to achieve the traversing from bin center to edges. Do i need to use raycaster here? Can you provide some example/link that demonstrate center to edge collision detection?

Also, I had one little doubt here. I think the outside object/panels that are outside the polygon will pass the first test that you mentioned?

12

@milind_anantwar
Hi!
Take a look at this post and its codepen example: Check points is inside a polygon - doesn't work correct - #2 by prisoner849
It is for checking, if the center of a bin is inside of the polygon.

Read this topic: [SOLVED] How to find intersection between two Rays?
It’s about intersection of line segments (just line segments, methematical ones :slight_smile:, not THREE.LineSegments())
You can use it for checking, if any line segment of bin rectangle instersects with any line segment of the polygon.

1 Like
13

Hm, no. If you make sure that the reference point is outside the polygon, all line segments to points outside the polygon will intersect an even (mostly 0) number of polygon edges. All line segments to points inside the polygon will intersect an odd number of polygon edges. This is the principle used in the StackOverflow page you linked. There may be some issues with points that lie on the edges etc., which I guess you can try to sort out.

It is also an option to first check the bounding box of the line segment against the rectangle, and then check if all corners of the rectangle lie on the same side of the line segment, by checking the signs of the dot products of a normal (90 degrees rotated, i.e. swap x,y will do) from the line segment with the vectors from a point on the line segment to each of the corners.

1 Like