Real-time Virtual Reality applications require accuracy but are also time dependent; therefore, in these environments, the time consumption is particularly important. For that reason, when facing the problem of Collision Detection for a Virtual Reality application, we firstly focus our attention on optimizing time performance for collisions among objects. Spatial Partitioning algorithms have been broadly used in Collision Detection. In particular, voxel-based methods are simple and quick, but finding the optimum voxel size is not trivial. We propose a methodology to easily determine the optimal voxel size for Collision Detection algorithms. Using an algorithm which represents volumetric objects with tetrahedra as an example, a performance cost function is defined in order to analytically bound the voxel size that gives the best computation times. This is made by inferring and estimating all the parameters involved. Thus, the cost function is delimited to depend only on geometric data. By doing so, it is possible to determine the optimal voxelization for any algorithm and scenario. Several solutions have been researched and compared. Experimental results with theoretical and real 3D models have validated the methodology. The reliability of our research has also been compared with traditional experimental solutions given by previous works.