00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <assert.h>
00005 #include <float.h>
00006 #include <math.h>
00007
00064 #include "splitplane.h"
00065 #include "ConvexDecomposition.h"
00066 #include "cd_vector.h"
00067 #include "cd_hull.h"
00068 #include "cd_wavefront.h"
00069 #include "bestfit.h"
00070 #include "planetri.h"
00071 #include "vlookup.h"
00072 #include "meshvolume.h"
00073 #include "bestfitobb.h"
00074 #include "float_math.h"
00075
00076 namespace ConvexDecomposition
00077 {
00078
00079 static void computePlane(const double *A,const double *B,const double *C,double *plane)
00080 {
00081
00082 double vx = (B[0] - C[0]);
00083 double vy = (B[1] - C[1]);
00084 double vz = (B[2] - C[2]);
00085
00086 double wx = (A[0] - B[0]);
00087 double wy = (A[1] - B[1]);
00088 double wz = (A[2] - B[2]);
00089
00090 double vw_x = vy * wz - vz * wy;
00091 double vw_y = vz * wx - vx * wz;
00092 double vw_z = vx * wy - vy * wx;
00093
00094 double mag = sqrt((vw_x * vw_x) + (vw_y * vw_y) + (vw_z * vw_z));
00095
00096 if ( mag < 0.000001f )
00097 {
00098 mag = 0;
00099 }
00100 else
00101 {
00102 mag = 1.0f/mag;
00103 }
00104
00105 double x = vw_x * mag;
00106 double y = vw_y * mag;
00107 double z = vw_z * mag;
00108
00109
00110 double D = 0.0f - ((x*A[0])+(y*A[1])+(z*A[2]));
00111
00112 plane[0] = x;
00113 plane[1] = y;
00114 plane[2] = z;
00115 plane[3] = D;
00116
00117 }
00118
00119 class Rect3d
00120 {
00121 public:
00122 Rect3d(void) { };
00123
00124 Rect3d(const double *bmin,const double *bmax)
00125 {
00126
00127 mMin[0] = bmin[0];
00128 mMin[1] = bmin[1];
00129 mMin[2] = bmin[2];
00130
00131 mMax[0] = bmax[0];
00132 mMax[1] = bmax[1];
00133 mMax[2] = bmax[2];
00134
00135 }
00136
00137 void SetMin(const double *bmin)
00138 {
00139 mMin[0] = bmin[0];
00140 mMin[1] = bmin[1];
00141 mMin[2] = bmin[2];
00142 }
00143
00144 void SetMax(const double *bmax)
00145 {
00146 mMax[0] = bmax[0];
00147 mMax[1] = bmax[1];
00148 mMax[2] = bmax[2];
00149 }
00150
00151 void SetMin(double x,double y,double z)
00152 {
00153 mMin[0] = x;
00154 mMin[1] = y;
00155 mMin[2] = z;
00156 }
00157
00158 void SetMax(double x,double y,double z)
00159 {
00160 mMax[0] = x;
00161 mMax[1] = y;
00162 mMax[2] = z;
00163 }
00164
00165 double mMin[3];
00166 double mMax[3];
00167 };
00168
00169 void splitRect(unsigned int axis,
00170 const Rect3d &source,
00171 Rect3d &b1,
00172 Rect3d &b2,
00173 const double *midpoint)
00174 {
00175 switch ( axis )
00176 {
00177 case 0:
00178 b1.SetMin(source.mMin);
00179 b1.SetMax( midpoint[0], source.mMax[1], source.mMax[2] );
00180
00181 b2.SetMin( midpoint[0], source.mMin[1], source.mMin[2] );
00182 b2.SetMax(source.mMax);
00183
00184 break;
00185 case 1:
00186 b1.SetMin(source.mMin);
00187 b1.SetMax( source.mMax[0], midpoint[1], source.mMax[2] );
00188
00189 b2.SetMin( source.mMin[0], midpoint[1], source.mMin[2] );
00190 b2.SetMax(source.mMax);
00191
00192 break;
00193 case 2:
00194 b1.SetMin(source.mMin);
00195 b1.SetMax( source.mMax[0], source.mMax[1], midpoint[2] );
00196
00197 b2.SetMin( source.mMin[0], source.mMin[1], midpoint[2] );
00198 b2.SetMax(source.mMax);
00199
00200 break;
00201 }
00202 }
00203
00204 bool computeSplitPlane(unsigned int vcount,
00205 const double *vertices,
00206 unsigned int tcount,
00207 const unsigned int *indices,
00208 ConvexDecompInterface *callback,
00209 double *plane)
00210 {
00211 bool cret = false;
00212
00213
00214 double sides[3];
00215 double matrix[16];
00216
00217 computeBestFitOBB( vcount, vertices, sizeof(double)*3, sides, matrix );
00218
00219 double bmax[3];
00220 double bmin[3];
00221
00222 bmax[0] = sides[0]*0.5f;
00223 bmax[1] = sides[1]*0.5f;
00224 bmax[2] = sides[2]*0.5f;
00225
00226 bmin[0] = -bmax[0];
00227 bmin[1] = -bmax[1];
00228 bmin[2] = -bmax[2];
00229
00230
00231 double dx = sides[0];
00232 double dy = sides[1];
00233 double dz = sides[2];
00234
00235
00236 double laxis = dx;
00237
00238 unsigned int axis = 0;
00239
00240 if ( dy > dx )
00241 {
00242 axis = 1;
00243 laxis = dy;
00244 }
00245
00246 if ( dz > dx && dz > dy )
00247 {
00248 axis = 2;
00249 laxis = dz;
00250 }
00251
00252 double p1[3];
00253 double p2[3];
00254 double p3[3];
00255
00256 p3[0] = p2[0] = p1[0] = bmin[0] + dx*0.5f;
00257 p3[1] = p2[1] = p1[1] = bmin[1] + dy*0.5f;
00258 p3[2] = p2[2] = p1[2] = bmin[2] + dz*0.5f;
00259
00260 Rect3d b(bmin,bmax);
00261
00262 Rect3d b1,b2;
00263
00264 splitRect(axis,b,b1,b2,p1);
00265
00266
00267
00268
00269
00270 switch ( axis )
00271 {
00272 case 0:
00273 p2[1] = bmin[1];
00274 p2[2] = bmin[2];
00275
00276 if ( dz > dy )
00277 {
00278 p3[1] = bmax[1];
00279 p3[2] = bmin[2];
00280 }
00281 else
00282 {
00283 p3[1] = bmin[1];
00284 p3[2] = bmax[2];
00285 }
00286
00287 break;
00288 case 1:
00289 p2[0] = bmin[0];
00290 p2[2] = bmin[2];
00291
00292 if ( dx > dz )
00293 {
00294 p3[0] = bmax[0];
00295 p3[2] = bmin[2];
00296 }
00297 else
00298 {
00299 p3[0] = bmin[0];
00300 p3[2] = bmax[2];
00301 }
00302
00303 break;
00304 case 2:
00305 p2[0] = bmin[0];
00306 p2[1] = bmin[1];
00307
00308 if ( dx > dy )
00309 {
00310 p3[0] = bmax[0];
00311 p3[1] = bmin[1];
00312 }
00313 else
00314 {
00315 p3[0] = bmin[0];
00316 p3[1] = bmax[1];
00317 }
00318
00319 break;
00320 }
00321
00322 double tp1[3];
00323 double tp2[3];
00324 double tp3[3];
00325
00326 fm_transform(matrix,p1,tp1);
00327 fm_transform(matrix,p2,tp2);
00328 fm_transform(matrix,p3,tp3);
00329
00330
00331
00332 computePlane(tp1,tp2,tp3,plane);
00333
00334 return true;
00335
00336 }
00337
00338
00339 };