Using a profiling tool, it was found most time was spent in the collision detection module. This was to be expected because of the way the plant growing module makes use of the collision detection module: when a new leaf or vine segment is created, it has to be tested to see if its addition will cause an intersection with something else already in the environment. Any new objects that are placed into the environment have to be of finite size, so care has to be taken to ensure that new objects don't interfere with anything else when first entered into the database. Most of the time is spent determining the interference submatrices of two objects, and then listing all the polygons which are contained within these submatrices. Another function that is used heavily, not surprisingly, is the one that applies transforms to points.
One of the key parameters that affects the performance of the collision detection module, is the order of the sub-division matrix M applied to all objects. Garcia conducted some experiments where the value for M was altered, and the time taken to compute the interference between voxels measured. They determined that there did exist an optimal value for M, and that was about 8 or 9.
Table 
shows the results for the tests carried out with my
program for varying M. These were produced by running the program with the
same values for the different variables, except the program was recompiled
with different values of M. The results are taken from single runs at each
different value of M. Although more test runs should be undertaken at the
each value of M, these results are still representative of the general
behaviour of the simulation program.
Table: performance statistics as M varies
The performance of the global bounding box (as a percentage) was measured as
the number of actual object collisions, divided by the number of global
bounding box tests that gave an interference status. This value isn't
listed in the table as it doesn't vary with M and was generally of the order
of a few percent. In other words, this percentage represented the accuracy
of the bounding box as a predictor to whether a collision was likely. Such a
low value, a few percent, would indicate that the bounding box was
ineffective at reducing the number of unnecessary collision detections. Refer
to chapter for a further discussion.
The "voxels per test" field in table represents the average
number of voxels of an object involved in each collision test. That is after
the global bounding box tests reports an interference status, this value
gives the average number of voxels that are found to interfere from each
object, or the average size of the interference submatrix. These low values
are due in part to the inefficiency of the global bounding box test, which can
fail to pick up the fact that the containers of the objects (and therefore the
objects themselves) don't interfere. This leads to a large number of times
where there are no voxels from the objects interfering, which leads to the low
values obtained.
The next field, "polygon pairs" shows on average, how many polygon-against- polygon tests are carried out per object-against-object tests. Given a pair of objects to test, this is how many polygon against polygon checks we can expect to make (which is a more accurate measure than the number of polygons from each object involved). As expected, with increasing subdivision, the number of polygon pair tests decreases.
The last two fields deal with the effect the degree of spatial subdivision has on the ray testing used by the plant growing module. In this case, the subdivision is also of use to the simulator because the plant growing module fires a large number of test rays into the environment, and the subdivision of the objects speeds up the process. "Polygons tested per ray" represents the average number of polygons a ray is tested against, and voxels traversed per ray means just that. Increasing the subdivision reduces the number of polygons a ray is checked against, but it increases the number of voxels a ray goes through. The calculations required to move through voxels are addition or subtraction, while testing a ray against a polygon is a more expensive task.
These results in themselves don't provide enough information to decide on the optimum value of M. From them, it seems that we should use large values of M for best results. However, increasing M by one means a doubling in the memory requirements needed for the spatial subdivision structure. As often is the case, speed increases can be obtained at the cost of more memory, and memory savings can usually be made at the sacrifice of speed.
Also these figures don't measure the actual time taken by the various routines or how the total running time of the program is affected. Execution times were generated, but through a mistake on my part, the results need to be redone and there isn't the time to do them. In addition, it would also be useful to carry out testing with some larger values of M.