# Tutorial - Collision Trees

Template:Languages
In Tutorial two we managed to create a small scene with few objects bouncing over a large background box. The problem with that demo was that we made everything using collision primitives. Modeling the world with collision primitives is not practical nor it is efficient. For that Newton provides two special kinds of collision primitives: User defined collision and Collision Trees.

These collision geometries are not as flexible as boxes, and sphere; because forces and velocity cannot affect them, however they can be moved by the application by directly manipulating the body transformation matrix. When these primitives are assigned to a rigid body, they nullify the mass property. The benefit these collision geometries provide to the application is that they can have any arbitrary shape or form. They can be made out of an unlimited number of polygons, therefore making them ideal to represent the static background collision geometry of the level.

User defined collision will be covered in the Advanced Collision tutorial. For now we will just say this collision geometry is useful for meshes with a known access pattern, like height maps or procedural geometries. For most geometry, collision tree is the best choice.

Open the project Tutorial 3 Using Collision Tree A. Find the function InitScene() the only difference between this function and the equivalent on the previous tutorial, is that now we load a pre made level geometry for the static background geometry. This done by the code fragment:

```// Load level geometry and add it to the display list
level = new LevelPrimitive ("data\\level.dat", nWorld);
```

The rest of this file remained the same as before.

Open the file LevelPrimitive.cpp; this file implements all the functionality for loading and creating the background geometry.

The first thing done in the constructor of this class is

```// Create the collision tree geometry
collision = NewtonCreateTreeCollision(nWorld, LevelCollisionCallback);
```

The second argument to this call is another Newton callback event function, which allows the application to extract and modify information stored in the user id with each face of the collision geometry. A common use for this callback is for debugging purpose by showing the outline of the geometry colliding with some other body. However the more advanced purpose for this function in to simulate special effects like: per surface material properties on the level geometry, conditional collision like surfaces that are collideable but break after impact (breaking glass), even modifiable surface material like dry surface that became wet after some event, or even special effect surfaces like conveyor belt. The possibilities are only limited by the expertise and creativity of the user.

Note: If your application is not going to modify per polygon attribute at run time. You can still use the call back for debugging purpose, but you can gain a little bit of performance by just passing the null pointer to the Level collision call back for final release.

The next call is the

```// prepare to create collsion geometry
NewtonTreeCollisionBeginBuild(collision);
```

This prepares the collision tree to begin to accept faces. Only one collision tree can be built at any one time, not doing so will create unpredictable results.

Next the data file is opened and an openly display list for fast rendering is created. The function iterate trough every face of the level geometry adding them to the collision tree and to the openly display list.

```// Open the level data
file = fopen (name, "rb");

m_list = glGenLists(1);
glNewList (m_list, GL_COMPILE);

for (fscanf (file, "%d", &count); count; fscanf (file, "%d", &count)) {
for (i = 0; i < count; i ++) {
fscanf (file, "%(%f %f %f%)", &point[i].m_x, &point[i].m_y, &point[i].m_z);
}
// add this face to the collsion tree
NewtonTreeCollisionAddFace(collision, count, &point[0].m_x, sizeof (dVector), 1);

// add this face to the display list
glBegin(GL_POLYGON);

// calculate the normal
dVector normal ((point[1] - point[0]) * (point[2] - point[0]));
normal = normal.Scale (1.0f / sqrtf (normal % normal));
glNormal3f(normal.m_x, normal.m_y, normal.m_z);

// submit the face
for (i = 0; i < count; i ++) {
glVertex3f(point[i].m_x, point[i].m_y, point[i].m_z);
}
// end the list
glEnd();
}
glEndList ();
```

The line

```// Add this face to the collision tree
NewtonTreeCollisionAddFace(collision, count, &point[0].m_x, sizeof (dVector), 1);
```

adds each face to the collision tree. Notice that the last parameter to this function is set to one. This is the user data that will be stored with the face in the tree. This parameter should be read from the data file and it should be associated with the type of surface of the level geometry. Usually an authoring tool specifies this, but since this is a very simple tutorial we will set to a hard coded value.

After all the faces are added to collision then the function call

```// Finalize the collision tree build
NewtonTreeCollisionEndBuild(collision, 1);
```

tells Newton to compile the collision geometry. When the last parameter is set to zero, the tree compiler will make the collision tree out of the same geometry. This is fast and could be used for testing purposes. However for final versions this parameter should always be set to one. The memory saving can by for 200% to 1200%, and runtime performance gain can be as high as 5 time faster, depending on how much redundancy information is in the original data. The optimizer does not change the topology of the mesh it only extract redundant information.

The rest of the code create the rigid body just like we did before

```// Release the collision tree (release the app from book keeping Newton objects
NewtonReleaseCollision (nWorld, collision);

// set the global position of this body
NewtonBodySetMatrix (level, &m_matrix[0][0]);

dVector boxP0;
dVector boxP1;
// get the position of the aabb of this geometry
NewtonCollisionCalculateAABB (collision, &m_matrix[0][0], &boxP0.m_x, &boxP1.m_x);

boxP0.m_x -= 10.0f;
boxP0.m_y -= 10.0f;
boxP0.m_z -= 10.0f;
boxP1.m_x += 10.0f;
boxP1.m_y += 10.0f;
boxP1.m_z += 10.0f;

// set the world size
NewtonSetWorldSize (nWorld, &boxP0.m_x, &boxP1.m_x);
```

The only interesting thing here is that we use the side of the Level geometry to set the side of the Newton world.

Note: It is a good idea to simplify collision geometry as much as possible. Highly tessellated collision geometry for background geometry may look good but they do not improve much collision resolution, they however impose a costly burden on the constraint solver part of the engine. Newton is very good at optimizing the geometry and preprocessing contacts, but if you add too complex curve surfaces then you will have problems with performance and accuracy.