$search
00001 /* 00002 Szymon Rusinkiewicz 00003 Stanford Graphics Lab 00004 00005 trimesh_bounding.cc 00006 Code for bounding box and bounding sphere. 00007 */ 00008 00009 #include <stdio.h> 00010 #include <float.h> 00011 #include "triutil.h" 00012 #include "trimesh.h" 00013 00014 #define BIGNUM FLT_MAX 00015 00016 namespace trimesh { 00017 00018 void TriMesh::FindBBox() 00019 { 00020 printf("Computing bounding box... "); fflush(stdout); 00021 00022 if (bbox) 00023 delete bbox; 00024 bbox = new BBox; 00025 bbox->xmin = bbox->ymin = bbox->zmin = BIGNUM; 00026 bbox->xmax = bbox->ymax = bbox->zmax = -BIGNUM; 00027 00028 for (int i=0; i < numvertices; i++) { 00029 bbox->xmin = min(bbox->xmin, vertices[i][0]); 00030 bbox->xmax = max(bbox->xmax, vertices[i][0]); 00031 bbox->ymin = min(bbox->ymin, vertices[i][1]); 00032 bbox->ymax = max(bbox->ymax, vertices[i][1]); 00033 bbox->zmin = min(bbox->zmin, vertices[i][2]); 00034 bbox->zmax = max(bbox->zmax, vertices[i][2]); 00035 } 00036 00037 bbox->xlen = bbox->xmax - bbox->xmin; 00038 bbox->ylen = bbox->ymax - bbox->ymin; 00039 bbox->zlen = bbox->zmax - bbox->zmin; 00040 00041 printf("Done.\n"); fflush(stdout); 00042 } 00043 00044 00045 // Based on the bounding sphere code by Jack Ritter in _Graphics Gems_ 00046 void TriMesh::FindBSphere() 00047 { 00048 if (bsphere) 00049 delete bsphere; 00050 bsphere = new BSphere; 00051 00052 printf("Computing bounding sphere... "); fflush(stdout); 00053 00054 // Pass I - find minima/maxima in each coord 00055 float xx=BIGNUM, xy, xz, yx, yy=BIGNUM, yz, zx, zy, zz=BIGNUM; 00056 float XX=-BIGNUM, XY, XZ, YX, YY=-BIGNUM, YZ, ZX, ZY, ZZ=-BIGNUM; 00057 00058 for (int i = 0; i < numvertices; i++) { 00059 float x = vertices[i][0]; 00060 float y = vertices[i][1]; 00061 float z = vertices[i][2]; 00062 if (x < xx) { xx = x; xy = y; xz = z; } 00063 if (x > XX) { XX = x; XY = y; XZ = z; } 00064 if (y < yy) { yx = x; yy = y; yz = z; } 00065 if (y > YY) { YX = x; YY = y; YZ = z; } 00066 if (z < zz) { zx = x; zy = y; zz = z; } 00067 if (z > ZZ) { ZX = x; ZY = y; ZZ = z; } 00068 } 00069 00070 // Set [xyz]span to square of dist btw [xyz]{min,max} 00071 float dx, dy, dz; 00072 00073 dx = XX-xx; dy = XY-xy; dz = XZ-xz; 00074 float xspan = dx*dx+dy*dy+dz*dz; 00075 00076 dx = YX-yx; dy = YY-yy; dz = YZ-yz; 00077 float yspan = dx*dx+dy*dy+dz*dz; 00078 00079 dx = ZX-zx; dy = ZY-zy; dz = ZZ-zz; 00080 float zspan = dx*dx+dy*dy+dz*dz; 00081 00082 // Set dia[12] to maximally separated pair 00083 float dia1x = xx, dia1y = xy, dia1z = xz; 00084 float dia2x = XX, dia2y = XY, dia2z = XZ; 00085 float maxspan = xspan; 00086 if (yspan > maxspan) { 00087 maxspan = yspan; 00088 dia1x = yx, dia1y = yy, dia1z = yz; 00089 dia2x = YX, dia2y = YY, dia2z = YZ; 00090 } 00091 if (zspan > maxspan) { 00092 maxspan = zspan; 00093 dia1x = zx, dia1y = zy, dia1z = zz; 00094 dia2x = ZX, dia2y = ZY, dia2z = ZZ; 00095 } 00096 00097 // Find initial center 00098 float cx = (dia1x+dia2x)*0.5f; 00099 float cy = (dia1y+dia2y)*0.5f; 00100 float cz = (dia1z+dia2z)*0.5f; 00101 00102 // Find initial radius, r^2 00103 dx = dia2x-cx; 00104 dy = dia2y-cy; 00105 dz = dia2z-cz; 00106 float r2 = dx*dx+dy*dy+dz*dz; 00107 float r = sqrt(r2); 00108 00109 // Pass II - increment sphere until everything fits 00110 for (int i = 0; i < numvertices; i++) { 00111 dx = vertices[i][0] - cx; 00112 dy = vertices[i][1] - cy; 00113 dz = vertices[i][2] - cz; 00114 float current_r2 = dx*dx+dy*dy+dz*dz; 00115 if (current_r2 > r2) { 00116 float current_r = sqrt(current_r2); 00117 r = (r+current_r)*0.5f; 00118 r2 = r*r; 00119 float dr = current_r - r; 00120 float r_current_r = 1.0f / current_r; 00121 cx = (r*cx + dr*vertices[i][0]) * r_current_r; 00122 cy = (r*cy + dr*vertices[i][1]) * r_current_r; 00123 cz = (r*cz + dr*vertices[i][2]) * r_current_r; 00124 } 00125 } 00126 00127 bsphere->center[0] = cx; 00128 bsphere->center[1] = cy; 00129 bsphere->center[2] = cz; 00130 bsphere->r = r; 00131 00132 // For certain pathological inputs, the above algorithm produces a 00133 // ReallyBad (tm) result. As a sanity check, make sure that the 00134 // bsphere of the bbox isn't smaller... -- SMR 00135 00136 float xmin = BIGNUM, ymin = BIGNUM, zmin = BIGNUM; 00137 float xmax = -BIGNUM, ymax = -BIGNUM, zmax = -BIGNUM; 00138 for (int i=0; i < numvertices; i++) { 00139 xmin = min(xmin, vertices[i][0]); 00140 xmax = max(xmax, vertices[i][0]); 00141 ymin = min(ymin, vertices[i][1]); 00142 ymax = max(ymax, vertices[i][1]); 00143 zmin = min(zmin, vertices[i][2]); 00144 zmax = max(zmax, vertices[i][2]); 00145 } 00146 00147 r = 0.5f * sqrt(sqr(xmax-xmin) + sqr(ymax-ymin) + sqr(zmax-zmin)); 00148 if (r < bsphere->r) { 00149 bsphere->r = r; 00150 bsphere->center[0] = 0.5f * (xmin+xmax); 00151 bsphere->center[1] = 0.5f * (ymin+ymax); 00152 bsphere->center[2] = 0.5f * (zmin+zmax); 00153 } 00154 00155 printf("Done.\n"); fflush(stdout); 00156 } 00157 00158 } // namespace trimesh 00159