libmgcd

0.1

Introduction

LIBMGCD is a C implementation of Multi Grid Contact Detection method (MGCD).The multigrid idea is integrated with contact detection problems. Both the time complexity and memory consumption of the MGCD are O(N). Unlike other methods, whose efficiencies are influenced strongly by the object size distribution, the performance of MGCD is insensitive to the object size distribution.

Introduction

When performing 2D detection, LIBMGCD needs :

 sizeof(Int)*(AABBCount+nx*ny) for the finest grid using screening method,
 sizeof(Int)*(AABBCount+2*nx*ny) bytes for other grids using screening method;
 sizeof(Int)*(2*AABBCount+2*nx+ny)+nx+ny bytes for the finest grid using nbs method,
 sizeof(Int)*(2*AABBCount+4*nx+ny)+nx+ny bytes for other grids using nbs method.
 

When performing 3D detection, LIBMGCD needs :

 sizeof(Int)*(AABBCount+nx*ny*nz) bytes for the finest grid using screening method,
 sizeof(Int)*(AABBCount+2*nx*ny*nz) bytes for other grids using screening method;
 sizeof(Int)*(3*AABBCount+2*nx+2*ny+nz)+nx+ny+nz bytes for the finest grid using nbs method,
 sizeof(Int)*(3*AABBCount+4*nx+2*ny+nz)+nx+ny+nz bytes for other grids using nbs method.
 

where nx, ny, nz is the cell count in x, y and z direction of coresponding grid.

Installation

Follow these steps to build and install the mgcd library, suppose you are in the root directory of this libmgcd distibution:

 $./configure --prefix = path_to_install 
 $make  
 $make install 
 

After these, the mgcd library and the sample program will be installed to a directory indicated by path_to_install.

Example

The following code demonstrate how to use the mgcd api, and it can be found in path_to_install/examples after installing libmgcd.

 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
 #include "mgcd.h"

 #define FRAND() (rand()%1000/1000.0)

 void ramdomBoxBuilder3D(Float minx , Float miny, Float minz,
                         Float maxx , Float maxy, Float maxz,
                         Float dx, Float dy, Float dz,
                         struct AABB3D * buf,  
                         Int start, Int count
                         ){
     unsigned seed = (unsigned)time(NULL);

     Float rx ;
     Float ry = dy/2;
     Float rz = dz/2;
     Float wx = maxx - minx;
     Float wy = maxy - miny;
     Float wz = maxz - minz;
     Int i ;

     rx = dx/2;
     srand (seed);
     for(i= 0 ; i<count ; ++i){

         buf [start + i].x = FRAND() * wx + minx;
         buf [start + i].y = FRAND() * wy + miny;
         buf [start + i].z = FRAND() * wz + minz;
         buf [start + i].rx = rx;
         buf [start + i].ry = ry;
         buf [start + i].rz = rz;  
     }
 }

 void test3D (){
     Int countNbs, countScr;  
     int c1 = 10000;
     int c2 = 2560000;

     struct AABB3D * elems = malloc((c1+c2)*sizeof(*elems));
     Float grids [] = {0.1, 0.01};
     ramdomBoxBuilder3D(0, 0, 0, 
                        5, 5, 5,
                        0.1, 0.1, 0.1,
                        elems, 0, c1);

     ramdomBoxBuilder3D(0, 0, 0, 
                        5, 5, 5,
                        0.01, 0.01, 0.01,
                        elems, c1, c2);

     printf("mgcd 3D nbs ... \n");
     countNbs = mgcdContactDetect3D (grids, 2, elems, c1+c2, "NBS", NULL, NULL);

     printf("mgcd 3D scr ... \n");
     countScr = mgcdContactDetect3D (grids, 2, elems, c1+c2, "SCR", NULL, NULL);

     printf("nbs : %d\n", countNbs);
     printf("scr : %d\n", countNbs);

     fflush(stdout);
     free (elems);
 }

 int main (){
     test3D();
     return 0;
 } 

---