January 21, 2021, 08:19:13 AM

### Author Topic: Collisions  (Read 879 times)

#### JBR

• Full Member
• Posts: 123
##### Collisions
« on: March 11, 2020, 12:32:47 AM »
Hi, never used the collision system before.

Lets say I have 100 3d crafts and I want to fire a bullet and then see which craft has been hit.

The craft is basic, but will include more demanding meshes. (low poly though)

So, is polygon collision the way to go or is there a more sneaky, faster way.

Thanks,  Jim.

#### Matty

• Hero Member
• Posts: 1339
##### Re: Collisions
« Reply #1 on: March 11, 2020, 01:54:39 AM »
Yes.

A 3d grid array or 3 dimensional array representing the space the ships fly in.

Each cell holds a list of ships and is updated when ships cross the boundaries.

Then your bullets only need to check for collisions against ships in their own grid cell thus reducing the number of checks dramatically.

If many cells are empty that bullets pass through they can be completely disregarded for collision checks.
I eat cheese in the trees when its eight degrees

#### ImJustAnotherCoder

• Jr. Member
• Posts: 22
##### Re: Collisions
« Reply #2 on: March 11, 2020, 03:28:14 AM »
Quote
So, is polygon collision the way to go or is there a more sneaky, faster way.

Checking each polygon of each object against every polygon of other objects is very inefficient and will be in the order of O(n2) for each polygon. There are much better methods, and they aren't 'sneaky' .

Breaking the 3D world into some kind of partition compartments is correct solution to this problem and will give you a huge boost in speed. There are many ways to do this, one is as Matty suggests - divide the world into a static 3d grid and put your objects into this grid. Other methods involve alternative partitioning algorithms that vary in complexity in terms of creation and search.

A partitioning scheme will give a data structure of objects that holds which objects 'can possibly collide' with each other. This step is known as the 'broad phase' of collision detection.

You then want to loop through each of those structures and check if the objects within them are actually colliding. This is called the 'narrow phase' of collision detection.

For each of the objects that can possibly collide you should use a bounding geometry to check for a possible collision. Some possible bounding geometries are spheres, boxes, capsules. Once you have a collision with bounding geometries you can choose if detection is good enough at this level or go to the next step of polygon collision.

The 'broadphase' detection phase above can be seen as an optimization of collision detection, although it is accepted as the norm to implement some version of this nowadays.

Quote
Lets say I have 100 3d crafts and I want to fire a bullet and then see which craft has been hit.
However if the bullet is fired instantly - such as a laser - then you would use a ray-cast to check against all other 'shootable' objects for a collision. You can use the above partitioning algorithms for increased performance if you find that things are slowing down. You would at least use bounding geometry to check against the ray before implementing polygon collision. to help keep things moving at a faster pace.

#### JBR

• Full Member
• Posts: 123
##### Re: Collisions
« Reply #3 on: March 14, 2020, 07:23:48 PM »
Thanks guys, your ideas will come in handy.

Jim

#### angros47

• Jr. Member
• Posts: 51
##### Re: Collisions
« Reply #4 on: March 15, 2020, 09:05:36 PM »
Polygon collision is pretty slow, but sphere collision is faster.

Also, to check if a bullet (or a laser beam) has hit the target, EntityPick could be used, instead of collision checking

#### Matty

• Hero Member
• Posts: 1339
##### Re: Collisions
« Reply #5 on: March 15, 2020, 11:34:06 PM »
For a laser beam because pick commands are slow a simple dot product of the two unit vectors from laser to enemy ship and direction laser pointing will return a value very close to 1.0 (it is the cosine of the angle between the two vectors) if they are in line.  A useful first dheck...for speed.
I eat cheese in the trees when its eight degrees

#### JBR

• Full Member
• Posts: 123
##### Re: Collisions
« Reply #6 on: March 16, 2020, 07:40:29 PM »
https://stackoverflow.com/questions/42740765/intersection-between-line-and-triangle-in-3d

Answer 1 seems easy but I could not get it to work!

I'm considering modelling the crafts with spheres (easy to check) and use tformpoint to get the 'spheres' in 3d when needed.

The spheres would be a best fit to the polygon.

Jim.

#### JBR

• Full Member
• Posts: 123
##### Re: Collisions
« Reply #7 on: March 16, 2020, 11:33:47 PM »
Yes something is working!

PositionEntity Pivot,100,0,0

EntityPickMode Mesh,2

The Pivot is the parent of the mesh and the mesh has the triangle data.

Hit:TEntity = EntityPick( Camera, 500 )

EntityX(Hit,True)     I need the true to get the x=100 otherwise it is 0.

Does all this sound ok to you guys?

Jim.

(How do I free up the Hit:TEntity value - can't use freeentity as it would remove the Mesh)?
Avoiding memory leaks.

#### angros47

• Jr. Member
• Posts: 51
##### Re: Collisions
« Reply #8 on: March 17, 2020, 04:18:00 PM »
Hit:TEntity is just a reference to another object, you don't need to free it. The command EntityPick does not create a new object, it returns the handle of an already existing object.

#### JBR

• Full Member
• Posts: 123
##### Re: Collisions
« Reply #9 on: March 17, 2020, 10:34:47 PM »
Thanks, Jim.