= Collision and Intersection
:author:
:revnumber:
:revdate: 2016/03/17 20:48
:relfileprefix: ../../
:imagesdir: ../..
ifdef::env-github,env-browser[:outfilesuffix: .adoc]


The term collision can be used to refer to <<jme3/advanced/physics_listeners#,physical interactions>> (where <<jme3/advanced/physics#,physical objects>> collide, push and bump off one another), and also to non-physical _intersections_ in 3D space. This article is about the non-physical (mathematical) collisions.

Non-physical collision detection is interesting because it uses less computing resources than physical collision detection. The non-physical calculations are faster because they do not have any side effects such as pushing other objects or bumping off of them. Tasks such as <<jme3/advanced/mouse_picking#,mouse picking>> are easily implemented using mathematical techniques such as ray casting and intersections.  Experienced developers optimize their games by finding ways to simulate certain (otherwise expensive physical) interactions in a non-physical way.

*Example:* One example for an optimization is a physical vehicle's wheels. You could make the wheels fully physical disks, and have jME calculate every tiny force – sounds very accurate? It's total overkill and too slow for a racing game. A more performant solution is to cast four invisible rays down from the vehicle and calculate the intersections with the floor. These non-physical wheels require (in the simplest case) only four calculations per tick to achieve an effect that players can hardly distinguish from the real thing.


== Collidable

The interface com.jme3.collision.Collidable declares one method that returns how many collisions were found between two Collidables: `collideWith(Collidable other, CollisionResults results)`.

*  A `com.jme3.collision.CollisionResults` object is an ArrayList of comparable `com.jme3.collision.CollisionResult` objects.
*  You can iterate over the CollisionResults to identify the other parties involved in the collision. +
Note that jME counts _all_ collisions, this means a ray intersecting a box will be counted as two hits, one on the front where the ray enters, and one on the back where the ray exits.

[cols="2", options="header"]
|===

a|CollisionResults Method
a|Usage

<a|size()
a|Returns the number of CollisionResult objects.

a|getClosestCollision()
a|Returns the CollisionResult with the lowest distance.

a|getFarthestCollision()
a|Returns the CollisionResult with the farthest distance.

<a|getCollision(i)
a|Returns the CollisionResult at index i.

|===

A CollisionResult object contains information about the second party of the collision event.
[cols="2", options="header"]
|===

a|CollisionResult Method
a|Usage

a|getContactPoint()
a|Returns the contact point coordinate on the second party, as Vector3f.

a|getContactNormal()
a|Returns the Normal vector at the contact point, as Vector3f.

a|getDistance()
a|Returns the distance between the Collidable and the second party, as float.

a|getGeometry()
a|Returns the Geometry of the second party.

a|getTriangle(t)
a|Binds t to the triangle t on the second party's mesh that was hit.

a|getTriangleIndex()
a|Returns the index of the triangle on the second party's mesh that was hit.

|===


=== Code Sample

Assume you have two collidables a and b and want to detect collisions between them. The collision parties can be Geometries, Nodes with Geometries attached (including the rootNode), Planes, Quads, Lines, or Rays. An important restriction is that you can only collide geometry vs bounding volumes or rays. (This means for example that a must be of Type Node or Geometry and b respectively of Type BoundingBox, BoundingSphere or Ray.)

The following code snippet can be triggered by listeners (e.g. after an input action such as a click), or timed in the update loop.

[source,java]
----

  // Calculate detection results
  CollisionResults results = new CollisionResults();
  a.collideWith(b, results);
  System.out.println("Number of Collisions between" +
      a.getName()+ " and " + b.getName() + ": " + results.size());
  // Use the results
  if (results.size() > 0) {
    // how to react when a collision was detected
    CollisionResult closest  = results.getClosestCollision();
    System.out.println("What was hit? " + closest.getGeometry().getName() );
    System.out.println("Where was it hit? " + closest.getContactPoint() );
    System.out.println("Distance? " + closest.getDistance() );
  } else {
    // how to react when no collision occured
  }
}
----

You can also loop over all results and trigger different reactions depending on what was hit and where it was hit. In this example, we simply print info about them.

[source,java]
----

  // Calculate Results
  CollisionResults results = new CollisionResults();
  a.collideWith(b, results);
  System.out.println("Number of Collisions between" + a.getName()+ " and "
   + b.getName() " : " + results.size());
  // Use the results
  for (int i = 0; i < results.size(); i++) {
    // For each hit, we know distance, impact point, name of geometry.
    float     dist = results.getCollision(i).getDistance();
    Vector3f    pt = results.getCollision(i).getContactPoint();
    String   party = results.getCollision(i).getGeometry().getName();
    int        tri = results.getCollision(i).getTriangleIndex();
    Vector3f  norm = results.getCollision(i).getTriangle(new Triangle()).getNormal();
    System.out.println("Details of Collision #" + i + ":");
    System.out.println("  Party " + party + " was hit at " + pt + ", " + dist + " wu away.");
    System.out.println("  The hit triangle #" + tri + " has a normal vector of " + norm);
  }

----

Knowing the distance of the collisions is useful for example when you intersect Lines and Rays with other objects.


== Bounding Volumes

A `com.jme3.bounding.BoundingVolume` is an interface for dealing with containment of a collection of points. All BoundingVolumes are `Collidable` and are used as optimization to calculate non-physical collisions more quickly: It's always faster to calculate an intersection between simple shapes like spheres and boxes than between complex shapes like models.

jME3 computes bounding volumes for all objects. These bounding volumes are later used for frustum culling, which is making sure only objects visible on-screen are actually sent for rendering.

All fast-paced action and shooter games use BoundingVolumes as an optimization. Wrap all complex models into simpler shapes – in the end, you get equally useful collision detection results, but faster. link:http://en.wikipedia.org/wiki/Bounding_volume[More about bounding volumes...]

Supported types:

// image::http://www.jmonkeyengine.com/jme/wiki-data/userref/capsule.png[Capsule,width="150",height="110",align="right"]


*  Type.AABB = Axis-aligned bounding box, that means it doesn't rotate, which makes it less precise. A `com.jme3.bounding.BoundingBox` is an axis-aligned cuboid used as a container for a group of vertices of a piece of geometry. A BoundingBox has a center and extents from that center along the x, y and z axis. This is the default bounding volume, since it is fairly fast to generate and gives better accuracy than the bounding sphere.
*  Type.Sphere: `com.jme3.bounding.BoundingSphere` is a sphere used as a container for a group of vertices of a piece of geometry. A BoundingSphere has a center and a radius.
*  Type.OBB = Oriented bounding box. This bounding box is more precise because it can rotate with its content, but is computationally more expensive. (Currently not supported.)
*  Type.Capsule = Cylinder with rounded ends, also called “swept sphere. Typically used for mobile characters. (Currently not supported.)


[NOTE]
====
Note: If you are looking for bounding volumes for physical objects, use <<jme3/advanced/physics#,CollisionShapes>>.
====



=== Usage

For example you can use Bounding Volumes on custom meshes, or complex non-physical shapes.

[source,java]
----
mesh.setBound(new BoundingSphere());
mesh.updateBound();
----


== Mesh and Scene Graph Collision

One of the supported ``Collidable``s are meshes and scene graph objects. To execute a collision detection query against a scene graph, use `Spatial.collideWith()`. This will traverse the scene graph and return any mesh collisions that were detected. Note that the first collision against a particular scene graph may take a long time, this is because a special data structure called link:http://en.wikipedia.org/wiki/Bounding_interval_hierarchy[Bounding Interval Hierarchy (BIH)] needs to be generated for the meshes. At a later point, the mesh could change and the BIH tree would become out of date, in that case, call link:{link-javadoc}/com/jme3/scene/Mesh.html#createCollisionData--[Mesh.createCollisionData()] on the changed mesh to update the BIH tree.


== Intersection

A `com.jme3.math.Ray` is an infinite line with a beginning, a direction, and no end; whereas a `com.jme3.math.Line` is an infinite line with only a direction (no beginning, no end).

Rays are used to perform line-of-sight calculations. This means you can detect what users were “aiming at when they clicked or pressed a key. You can also use this to detect whether game characters can see something (or someone) or not.

*  *Click to select:* You can determine what a user has clicked by casting a ray from the camera forward in the direction of the camera. Now identify the closest collision of the ray with the rootNode, and you have the clicked object.
*  *Line of sight:* Cast a ray from a player in the direction of another player. Then you detect all collisions of this ray with other entities (walls versus foliage versus window panes) and use this to calculate how likely it is that one can see the other.


[TIP]
====
These simple but powerful ray-surface intersection tests are called Ray Casting. As opposed to the more advanced Ray Tracing technique, Ray Casting does not follow the ray's reflection after the first hit – the ray just goes straight on.
====


Learn the details of how to implement <<jme3/advanced/mouse_picking#,Mouse Picking>> here.

'''

TODO:

*  Bounding Interval Hierarchy (`com.jme3.collision.bih.BIHNode`)
*  com.jme3.scene.CollisionData
