Fastest intersection test for two meshes

[hintuc_de]

How we can do subj with the required precision?

 

1. All meshes have different geometry, unigine *.mesh format.

2. One mesh may be inside into other mesh and test must be fast too in this situation.

3. And all surfaces of first and second mesh may be transform by setTransform methods.

4. We need do it in C++ api and UnigineScript.

 

p.s.: Many members ask about it in different words.

https://developer.unigine.com/forum/topic/804-doing-intersection-test-between-two-shapes/

https://developer.unigine.com/forum/topic/777-continuous-collision-performance/

https://developer.unigine.com/forum/topic/645-intersection-testing-in-large-worlds/

https://developer.unigine.com/forum/topic/846-questions-about-objectmeshs-collisionintersection-functions/

https://developer.unigine.com/forum/topic/778-performing-intersection-tests-using-an-oriented-box/

 

 

p.s. 2: BUG in this methods, it has doesn't work if surface was transformed.

// triangle collision
int getCollision(const BoundBox &bb,Vector &ctriangles,int surface);
int getCollision(const BoundSphere &bs,Vector &ctriangles,int surface);
int getCollision(const BoundFrustum &bf,Vector &ctriangles,int surface);
int getCollision(const vec3 &p0,const vec3 &p1,Vector &ctriangles,int surface);

[hintuc_de]

BUG in this methods, it has doesn't work if surface was transformed.

 

// line intersections
  	 int getIntersection(const vec3 &p0,const vec3 &p1,int surface);
  	 int getIntersection(const vec3 &p0,const vec3 &p1,vec3 &ret_point,vec4 &ret_plane,int &ret_triangle,int surface);
  	 int getIntersection(const vec3 &p0,const vec3 &p1,vec3 &ret_point,vec3 &ret_normal,vec4 &ret_texcoord,int surface);

 

For example simple test:

 

// use framework/mesh

 

1. mesh, it's capsule with radius x = 0.3, radius y = 0.3, heightZ = 1.8, center in center mesh

2. mesh->getIntersection(vec3(-10.0f, 0.0f, 0.0f), vec3(10.0f, 0.0f, 0.0f), 0); // return 1

3. mesh->setTransform(translate(-5.0f, 0.0f, 0.0f), 0);

4. mesh->getIntersection(vec3(-10.0f, 0.0f, 0.0f), vec3(10.0f, 0.0f, 0.0f), 0); // return 1 and ret_point vec3(-4.7, 0.0, 0.0);

5. mesh->getIntersection(vec3(-6.0f, 0.0f, 0.0f), vec3(-4.0f, 0.0f, 0.0f), 0); // return 0 // Why ?

[manguste]

You should transform all coordinates into the local space of the object first. Only after that you can pass them as arguments, because all these functions work in the local space.

[hintuc_de]

How we can do subj with the required precision?

[hintuc_de]

Does anybody require this problem ?

[manguste]

How we can do subj with the required precision?

Please explain in more detail what you want to achieve.

[hintuc_de]

How we can do subj with the required precision?

1. All meshes have different geometry, unigine *.mesh format.

2. One mesh may be inside into other mesh and test must be fast too in this situation.

3. And all surfaces of first and second mesh may be transform by setTransform methods.

4. We need do it in C++ api and UnigineScript.

 

// if meshs don't intersect return 0
// if meshs intersect return 1
int IntersectTest(Mesh *mesh1, Mesh *mesh2, double precision);

 

Как нам сделать проверку на пересечение двух мешей с заданной точностью?

1. Все меши имеют различную геометрию, и заданы в *.mesh формате unigine.

2. Один меш может быть вложет внутри другого меша и проверка должна не терять производительность.

3. И все поверхности первого и второго меша могут быть транформированны при помощи метода setTransform (поворот, перемещение, масштаб, различные комбинации 1-3)

4. Проверка требуется как на С++ api так и на UnigineScript, хотя в принципе можно только на C++, так как потом можно экспортнуть метод.

[hintuc_de]

What are details you needed?

[binstream]

Why do you need it? May be there is a better way to achieve your goal.

[hintuc_de]

В нашей игре объекты появляются случайным образом с наложением слулчайных трансформаций и нужно сделать контрольную проверку не пересекаются ли они между собой.

 

Translate:

In our game objects appear randomly with the imposition of random transformation and control check should be done not intersect if they are to each other.

[Guest anet]

We internally use another way to achieve this.

At first all possible positions for objects are generated. These positions are generated to avoid intersections already. This could be done either by hand or programmatically.

After this we generate random numbers for indices inside an array of pre-generated positions.

 

If you want to use intersection functions, use one of the following:

* int engine.world.getIntersectionNodesData(variable p0, variable p1, int type, int ret_id)

* int engine.world.getIntersectionNodes(variable p0, variable p1, int type, int ret_id)

* int engine.world.getIntersectionObjectsData(variable p0, variable p1, int ret_id)

* int engine.world.getIntersectionObjects(variable p0, variable p1, int ret_id)

* Object engine.world.getIntersection(vec3 p0, vec3 p1, int mask, int ret[])

* Object engine.world.getIntersection(vec3 p0, vec3 p1, int mask, Node exclude[], int ret[])

Note, that:

You may want to call updateSpatial() before finding intersections.

This could be the cause of the bug with not working intersections after applying transformations.

 

See this page for reference: https://developer.un...ariable_int_int

 

It is not very clear, what do you mean by precision of intersections. Could you please be more specific and describe why do you need to specify precision?

 

And why do you want to find intersections from C++ API?

[Guest anet]

There is also another way to check intersections.

PhysicalTrigger can also be used for it. See https://developer.un...physicaltrigger for reference.

To check intersections you will need to create PhysicalTrigger, apply transform and call updateContacts() method. After this you can get all intersections using getNumContacts(), getContactPoint() and other methods.

[alexei.garbuzenko]

Sorry for the offtopic, but this is the only place with red-posters related to intersections:

I were unable to get engine.game.getIntersection() to work. I.e. for points p0 and p1 engine.world.getIntersection(p0, p1, .. ) gives correct result, while engine.game.getIntersection(p0, p1, 2.0f, ...) always return NULL. What is the problem? May be some kind of properties or complex masks are needed?

[frustum]

engine.world.getIntersection() returns intersection with objects.

engine.game.getIntersection() returns intersection with obstacles.

engine.physics.getIntersection() returns intersection with shapes and collision objects.

[alexei.garbuzenko]

engine.world.getIntersection() returns intersection with objects.

engine.game.getIntersection() returns intersection with obstacles.

engine.physics.getIntersection() returns intersection with shapes and collision objects.

 

Ok. Thanks for detailing (however documentation should be slightly changed to clarify that).

Is it possible to check cylinder intersection with objects somehow? I.e. if I need to check is it possible to walk between two stones before making the movement, it would be very handy to perform single single cylinder check instead of several ray checks.

[frustum]

PhysicalTrigger is an ideal candidate for such tasks.

 

PhysicalTrigger tigger = new PhysicalTrigger(SHAPE_CYLINDER,vec3(radius,height,0.0f));

trigger.setWorldTransform(transform);
trigger.updateContacts();
forloop(int i = 0; trigger.getNumContacts()) {
 // process trigger contacts
}

[alexei.garbuzenko]

I don't want to get callback after that collision, I need to predict and prevent it before it is going to happen.

[frustum]

You shouldn't use callbacks. Contact information will be available after updateContacts() function immediately.

Contact information is: collision point, normal, depth and shape or object surface.

PhysicalTrigger is a sensor.

[alexei.garbuzenko]

Ok, thank you. I'll give it a try.

[manguste]

Ok. Thanks for detailing (however documentation should be slightly changed to clarify that).

Fixed.