00001 #include <math.h> 00002 #include <stdlib.h> 00003 #include "vuNormalBlock.h" 00004 00005 vuNormalBlock::vuNormalBlock() 00006 { 00007 m_Size = 0; 00008 m_Current = 0; 00009 m_Norms = 0; 00010 m_Dim = 0; 00011 m_Range = 0.0f; 00012 m_StdDev = 0.0f; 00013 } 00014 00015 vuNormalBlock::vuNormalBlock(const vuNormalBlock& inst) 00016 { 00017 dword i; 00018 00019 m_Size = inst.m_Size; 00020 m_Current = inst.m_Current; 00021 m_Dim = inst.m_Dim; 00022 m_Range = inst.m_Range; 00023 m_StdDev = inst.m_StdDev; 00024 00025 m_Norms = new float[m_Size*3]; 00026 for(i=0;i<m_Size;++i) 00027 m_Norms[i] = inst.m_Norms[i]; 00028 } 00029 00030 vuNormalBlock::~vuNormalBlock() 00031 { 00032 if (m_Norms) 00033 delete [] m_Norms; 00034 } 00035 00036 void vuNormalBlock::setSize(dword size) 00037 { 00038 m_Size = size; 00039 m_Current = 0; 00040 m_Range = 0.0f; 00041 m_StdDev = 0.0f; 00042 00043 if (m_Norms) 00044 delete [] m_Norms; 00045 00046 m_Norms = new float[m_Size*3]; 00047 } 00048 00049 dword vuNormalBlock::getSize(void) const 00050 { 00051 return m_Size; 00052 } 00053 00054 float vuNormalBlock::getRange(void) const 00055 { 00056 return m_Range; 00057 } 00058 00059 float vuNormalBlock::getStdDev(void) const 00060 { 00061 return m_StdDev; 00062 } 00063 00064 void vuNormalBlock::addNormal(const float* norm) 00065 { 00066 m_Norms[m_Current++] = norm[0]; 00067 m_Norms[m_Current++] = norm[1]; 00068 m_Norms[m_Current++] = norm[2]; 00069 } 00070 00071 void vuNormalBlock::computeStats(void) 00072 { 00073 float range[3]; 00074 float stddev[3]; 00075 float min; 00076 float max; 00077 float sum; 00078 float sumsqr; 00079 float tmp; 00080 dword dim; 00081 dword i; 00082 00083 for(dim=0;dim<3;++dim) 00084 { 00085 min = 1000000.0f; 00086 max = -1000000.0f; 00087 sum = 0.0f; 00088 sumsqr = 0.0f; 00089 00090 for(i=0;i<m_Size*3;i+=3) 00091 { 00092 tmp = m_Norms[i+dim]; 00093 if (tmp < min) 00094 min = tmp; 00095 if (tmp > max) 00096 max = tmp; 00097 sum += tmp; 00098 sumsqr += tmp*tmp; 00099 } 00100 range[dim] = max-min; 00101 stddev[dim] = (sumsqr-((sum*sum)/(float)m_Size))/((float)m_Size-1); 00102 } 00103 00104 m_Dim = 0; 00105 for(dim=1;dim<3;++dim) 00106 { 00107 if (range[dim] > range[m_Dim]) 00108 m_Dim = dim; 00109 else if (range[dim] == range[m_Dim]) 00110 { 00111 if (stddev[dim] > stddev[m_Dim]) 00112 m_Dim = dim; 00113 } 00114 } 00115 00116 m_Range = range[m_Dim]; 00117 m_StdDev = stddev[m_Dim]; 00118 } 00119 00120 bool vuNormalBlock::medianSplit(vuNormalBlock& left, vuNormalBlock& right) 00121 { 00122 float median; 00123 dword half; 00124 dword h1; 00125 dword h2; 00126 00127 QuickSort(0, m_Size-1); 00128 00129 if (m_Size&0x01) 00130 half = (m_Size-1)>>1; 00131 else 00132 half = m_Size>>1; 00133 median = m_Norms[half*3+m_Dim]; 00134 00135 h1 = half-1; 00136 while((m_Norms[h1*3+m_Dim]==median) && (h1>0)) 00137 --h1; 00138 00139 h2 = half+1; 00140 while((m_Norms[h2*3+m_Dim]==median) && (h2<(m_Size-1))) 00141 ++h2; 00142 00143 if ((h2-half) < (half-h1)) 00144 half = h2; 00145 else 00146 half = h1+1; 00147 00148 if (half == 0 || half == m_Size) 00149 return false; 00150 00151 left.setSize(half); 00152 right.setSize(m_Size-half); 00153 00154 half *= 3; 00155 00156 for(h1=0;h1<half;++h1) 00157 left.m_Norms[h1] = m_Norms[h1]; 00158 00159 for(h1=half;h1<m_Size*3;++h1) 00160 right.m_Norms[h1-half] = m_Norms[h1]; 00161 00162 left.computeStats(); 00163 right.computeStats(); 00164 00165 return true; 00166 } 00167 00168 void vuNormalBlock::computeAverage(float* f) const 00169 { 00170 float len; 00171 dword i; 00172 00173 f[0] = 0.0f; 00174 f[1] = 0.0f; 00175 f[2] = 0.0f; 00176 for(i=0;i<m_Size*3;i+=3) 00177 { 00178 f[0] += m_Norms[i]; 00179 f[1] += m_Norms[i+1]; 00180 f[2] += m_Norms[i+2]; 00181 } 00182 00183 len = (float)sqrt((double)((f[0]*f[0])+(f[1]*f[1])+(f[2]*f[2]))); 00184 if (len > 0.0f) 00185 { 00186 f[0] /= len; 00187 f[1] /= len; 00188 f[2] /= len; 00189 } 00190 } 00191 00192 vuNormalBlock& vuNormalBlock::operator=(const vuNormalBlock& rhs) 00193 { 00194 if (this != &rhs) 00195 { 00196 dword i; 00197 00198 m_Size = rhs.m_Size; 00199 m_Current = rhs.m_Current; 00200 m_Range = rhs.m_Range; 00201 m_StdDev = rhs.m_StdDev; 00202 00203 if (m_Norms) 00204 delete [] m_Norms; 00205 m_Norms = new float[m_Size*3]; 00206 00207 for(i=0;i<m_Size;++i) 00208 m_Norms[i] = rhs.m_Norms[i]; 00209 } 00210 return *this; 00211 } 00212 00213 int vuNormalBlock::Partition(int p, int r) 00214 { 00215 float t; 00216 float x; 00217 int i; 00218 int j; 00219 00220 x = m_Norms[p*3+m_Dim]; 00221 i = p-1; 00222 j = r+1; 00223 while(true) 00224 { 00225 do{ --j; } while(m_Norms[j*3+m_Dim] > x); 00226 do{ ++i; } while(m_Norms[i*3+m_Dim] < x); 00227 if(i < j) 00228 { 00229 t = m_Norms[i*3]; m_Norms[i*3] = m_Norms[j*3]; m_Norms[j*3] = t; 00230 t = m_Norms[i*3+1]; m_Norms[i*3+1] = m_Norms[j*3+1]; m_Norms[j*3+1] = t; 00231 t = m_Norms[i*3+2]; m_Norms[i*3+2] = m_Norms[j*3+2]; m_Norms[j*3+2] = t; 00232 } 00233 else 00234 return j; 00235 } 00236 } 00237 00238 int vuNormalBlock::RandomPartition(int p, int r) 00239 { 00240 float t; 00241 int i; 00242 00243 i = (rand()%(r-p))+p+1; 00244 t = m_Norms[p*3]; m_Norms[p*3] = m_Norms[i*3]; m_Norms[i*3] = t; 00245 t = m_Norms[p*3+1]; m_Norms[p*3+1] = m_Norms[i*3+1]; m_Norms[i*3+1] = t; 00246 t = m_Norms[p*3+2]; m_Norms[p*3+2] = m_Norms[i*3+2]; m_Norms[i*3+2] = t; 00247 return Partition(p, r); 00248 } 00249 00250 void vuNormalBlock::QuickSort(int p, int r) 00251 { 00252 int q; 00253 if (p < r) 00254 { 00255 q = RandomPartition(p, r); 00256 QuickSort(p, q); 00257 QuickSort(q+1, r); 00258 } 00259 }