HDK: UT/UT_HashGrid.C Source File

00001 /*
00002  * PROPRIETARY INFORMATION.  This software is proprietary to
00003  * Side Effects Software Inc., and is not to be reproduced,
00004  * transmitted, or disclosed in any way without written permission.
00005  *
00006  * Produced by:
00007  *      Jeff Chadwick
00008  *      Side Effects Software Inc.
00009  *      123 Front Street West, Suite 1401
00010  *      Toronto, Ontario
00011  *      Canada   M5J 2M2
00012  *      416-504-9876
00013  *
00014  * NAME:        Utility Library (C++)
00015  *
00016  * COMMENTS:
00017  *      This class implements a grid-based data structure for
00018  *      storing spacial data (ie. points) with a fixed radius of
00019  *      influence.  It can be used to quickly determine the set
00020  *      of elements affecting a given point in space.
00021  */
00022 
00023 #ifndef __UT_HashGrid_C__
00024 #define __UT_HashGrid_C__
00025 
00026 #include "UT_HashGrid.h"
00027 #include "UT_HashTable.h"
00028 #include "UT_IntArray.h"
00029 #include "UT_Vector3.h"
00030 #include "UT_Vector3Array.h"
00031 
00032 // We limit the number of cells in any one dimension to
00033 // be 2000000, in order to keep the cell index well within
00034 // the size of an int64.
00035 static const int64  ut_MAX_CELLS = 2000000;
00036 static const int64  ut_MAX_CELLS2 = ut_MAX_CELLS * ut_MAX_CELLS;
00037 
00038 static const int    ut_NUM_CELL_NEIGHBOURS = 27;
00039 
00040 template <typename utPtr>
00041 UT_HashGrid<utPtr>::UT_HashGrid(fpreal cellsize, const UT_Vector3 &origin,
00042                         bool fullinit, unsigned int sz)
00043     : myOrigin(origin),
00044       myCellWidth(cellsize),
00045       myMaxElements(0),
00046       myGridSet(),
00047       myCellArray(sz),
00048       myFullInit(fullinit),
00049       myPositions(sz)
00050 {
00051     myCellWidth2 = myCellWidth * myCellWidth;
00052 }
00053 
00054 template <typename utPtr>
00055 UT_HashGrid<utPtr>::~UT_HashGrid()
00056 {
00057 }
00058 
00059 // Insert a new element in to the grid set.
00060 template <typename utPtr>
00061 bool
00062 UT_HashGrid<utPtr>::insert(const UT_Vector3 &p, utPtr t)
00063 {
00064     // Start by getting the cell this point should
00065     // be in, creating it if it does not already
00066     // exist.
00067     UT_HashGridCell<utPtr>      *cell = getCell(p, true);
00068     UT_HashGridCell<utPtr>      *othercell;
00069     int                          i, j, k;
00070     int                          newindex;
00071     int                          pointindex = myPositions.entries();
00072     
00073     myPositions.append(p);
00074 
00075     if (!cell)
00076         return false;
00077 
00078     // Append the element to the cell's list.
00079     newindex = cell->myElements.append(t) + 1;
00080     cell->myIndices.append(pointindex);
00081 
00082     cell->myNumEntries++;
00083 
00084     if (newindex > myMaxElements)
00085         myMaxElements = newindex;
00086 
00087     if (myFullInit)
00088     {
00089         i = cell->myXindex;
00090         j = cell->myYindex;
00091         k = cell->myZindex;
00092 
00093         // Store the proper indices of all of the surrounding
00094         // cells as well.  This takes a bit of work because of our
00095         // indexing scheme.  Naming scheme represents distance along
00096         // number line: il = i_left, ir = i_right, etc.
00097         int                      il, ir, jl, jr, kl, kr;
00098 
00099         il = cell->myIL;
00100         ir = cell->myIR;
00101         jl = cell->myJL;
00102         jr = cell->myJR;
00103         kl = cell->myKL;
00104         kr = cell->myKR;
00105 
00106         othercell = getCell(i, j, kl, true);
00107         if (othercell)
00108         {
00109             othercell->myIndices.append(pointindex);
00110             newindex = othercell->myElements.append(t) + 1;
00111         }
00112 
00113         if (newindex > myMaxElements)
00114             myMaxElements = newindex;
00115 
00116         othercell = getCell(i, j, kr, true);
00117         if (othercell)
00118         {
00119             othercell->myIndices.append(pointindex);
00120             newindex = othercell->myElements.append(t) + 1;
00121         }
00122 
00123         if (newindex > myMaxElements)
00124             myMaxElements = newindex;
00125 
00126         othercell = getCell(i, jl, k, true);
00127         if (othercell)
00128         {
00129             othercell->myIndices.append(pointindex);
00130             newindex = othercell->myElements.append(t) + 1;
00131         }
00132 
00133         if (newindex > myMaxElements)
00134             myMaxElements = newindex;
00135 
00136         othercell = getCell(i, jl, kl, true);
00137         if (othercell)
00138         {
00139             othercell->myIndices.append(pointindex);
00140             newindex = othercell->myElements.append(t) + 1;
00141         }
00142 
00143         if (newindex > myMaxElements)
00144             myMaxElements = newindex;
00145 
00146         othercell = getCell(i, jl, kr, true);
00147         if (othercell)
00148         {
00149             othercell->myIndices.append(pointindex);
00150             newindex = othercell->myElements.append(t) + 1;
00151         }
00152 
00153         if (newindex > myMaxElements)
00154             myMaxElements = newindex;
00155 
00156         othercell = getCell(i, jr, k, true);
00157         if (othercell)
00158         {
00159             othercell->myIndices.append(pointindex);
00160             newindex = othercell->myElements.append(t) + 1;
00161         }
00162 
00163         if (newindex > myMaxElements)
00164             myMaxElements = newindex;
00165 
00166         othercell = getCell(i, jr, kl, true);
00167         if (othercell)
00168         {
00169             othercell->myIndices.append(pointindex);
00170             newindex = othercell->myElements.append(t) + 1;
00171         }
00172 
00173         if (newindex > myMaxElements)
00174             myMaxElements = newindex;
00175 
00176         othercell = getCell(i, jr, kr, true);
00177         if (othercell)
00178         {
00179             othercell->myIndices.append(pointindex);
00180             newindex = othercell->myElements.append(t) + 1;
00181         }
00182 
00183         if (newindex > myMaxElements)
00184             myMaxElements = newindex;
00185 
00186         othercell = getCell(il, j, k, true);
00187         if (othercell)
00188         {
00189             othercell->myIndices.append(pointindex);
00190             newindex = othercell->myElements.append(t) + 1;
00191         }
00192 
00193         if (newindex > myMaxElements)
00194             myMaxElements = newindex;
00195 
00196         othercell = getCell(il, j, kl, true);
00197         if (othercell)
00198         {
00199             othercell->myIndices.append(pointindex);
00200             newindex = othercell->myElements.append(t) + 1;
00201         }
00202 
00203         if (newindex > myMaxElements)
00204             myMaxElements = newindex;
00205 
00206         othercell = getCell(il, j, kr, true);
00207         if (othercell)
00208         {
00209             othercell->myIndices.append(pointindex);
00210             newindex = othercell->myElements.append(t) + 1;
00211         }
00212 
00213         if (newindex > myMaxElements)
00214             myMaxElements = newindex;
00215 
00216         othercell = getCell(il, jl, k, true);
00217         if (othercell)
00218         {
00219             othercell->myIndices.append(pointindex);
00220             newindex = othercell->myElements.append(t) + 1;
00221         }
00222 
00223         if (newindex > myMaxElements)
00224             myMaxElements = newindex;
00225 
00226         othercell = getCell(il, jl, kl, true);
00227         if (othercell)
00228         {
00229             othercell->myIndices.append(pointindex);
00230             newindex = othercell->myElements.append(t) + 1;
00231         }
00232 
00233         if (newindex > myMaxElements)
00234             myMaxElements = newindex;
00235 
00236         othercell = getCell(il, jl, kr, true);
00237         if (othercell)
00238         {
00239             othercell->myIndices.append(pointindex);
00240             newindex = othercell->myElements.append(t) + 1;
00241         }
00242 
00243         if (newindex > myMaxElements)
00244             myMaxElements = newindex;
00245 
00246         othercell = getCell(il, jr, k, true);
00247         if (othercell)
00248         {
00249             othercell->myIndices.append(pointindex);
00250             newindex = othercell->myElements.append(t) + 1;
00251         }
00252 
00253         if (newindex > myMaxElements)
00254             myMaxElements = newindex;
00255 
00256         othercell = getCell(il, jr, kl, true);
00257         if (othercell)
00258         {
00259             othercell->myIndices.append(pointindex);
00260             newindex = othercell->myElements.append(t) + 1;
00261         }
00262 
00263         if (newindex > myMaxElements)
00264             myMaxElements = newindex;
00265 
00266         othercell = getCell(il, jr, kr, true);
00267         if (othercell)
00268         {
00269             othercell->myIndices.append(pointindex);
00270             newindex = othercell->myElements.append(t) + 1;
00271         }
00272 
00273         if (newindex > myMaxElements)
00274             myMaxElements = newindex;
00275 
00276         othercell = getCell(ir, j, k, true);
00277         if (othercell)
00278         {
00279             othercell->myIndices.append(pointindex);
00280             newindex = othercell->myElements.append(t) + 1;
00281         }
00282 
00283         if (newindex > myMaxElements)
00284             myMaxElements = newindex;
00285 
00286         othercell = getCell(ir, j, kl, true);
00287         if (othercell)
00288         {
00289             othercell->myIndices.append(pointindex);
00290             newindex = othercell->myElements.append(t) + 1;
00291         }
00292 
00293         if (newindex > myMaxElements)
00294             myMaxElements = newindex;
00295 
00296         othercell = getCell(ir, j, kr, true);
00297         if (othercell)
00298         {
00299             othercell->myIndices.append(pointindex);
00300             newindex = othercell->myElements.append(t) + 1;
00301         }
00302 
00303         if (newindex > myMaxElements)
00304             myMaxElements = newindex;
00305 
00306         othercell = getCell(ir, jl, k, true);
00307         if (othercell)
00308         {
00309             othercell->myIndices.append(pointindex);
00310             newindex = othercell->myElements.append(t) + 1;
00311         }
00312 
00313         if (newindex > myMaxElements)
00314             myMaxElements = newindex;
00315 
00316         othercell = getCell(ir, jl, kl, true);
00317         if (othercell)
00318         {
00319             othercell->myIndices.append(pointindex);
00320             newindex = othercell->myElements.append(t) + 1;
00321         }
00322 
00323         if (newindex > myMaxElements)
00324             myMaxElements = newindex;
00325 
00326         othercell = getCell(ir, jl, kr, true);
00327         if (othercell)
00328         {
00329             othercell->myIndices.append(pointindex);
00330             newindex = othercell->myElements.append(t) + 1;
00331         }
00332 
00333         if (newindex > myMaxElements)
00334             myMaxElements = newindex;
00335 
00336         othercell = getCell(ir, jr, k, true);
00337         if (othercell)
00338         {
00339             othercell->myIndices.append(pointindex);
00340             newindex = othercell->myElements.append(t) + 1;
00341         }
00342 
00343         if (newindex > myMaxElements)
00344             myMaxElements = newindex;
00345 
00346         othercell = getCell(ir, jr, kl, true);
00347         if (othercell)
00348         {
00349             othercell->myIndices.append(pointindex);
00350             newindex = othercell->myElements.append(t) + 1;
00351         }
00352 
00353         if (newindex > myMaxElements)
00354             myMaxElements = newindex;
00355 
00356         othercell = getCell(ir, jr, kr, true);
00357         if (othercell)
00358         {
00359             othercell->myIndices.append(pointindex);
00360             newindex = othercell->myElements.append(t) + 1;
00361         }
00362 
00363         if (newindex > myMaxElements)
00364             myMaxElements = newindex;
00365     }
00366 
00367     return true;
00368 }
00369 
00370 // Generates a list of elements close to the given point.
00371 template <typename utPtr>
00372 void
00373 UT_HashGrid<utPtr>::findCloseElements(const UT_Vector3 &p,
00374                         UT_PtrArray<utPtr> &list)
00375 {
00376     if (myFullInit)
00377     {
00378         UT_HashGridCell<utPtr>  *cell = getCell(p);
00379         int                      i, n;
00380 
00381         if (cell)
00382         {
00383             n = cell->myElements.entries();
00384 
00385             list.resize(n);
00386             list.entries(0);
00387 
00388             for (i = 0; i < n; i++)
00389             {
00390                 if ((p - myPositions(cell->myIndices(i))).length2() < myCellWidth2)
00391                     list.append(cell->myElements(i));
00392             }
00393         }
00394     }
00395     else
00396     {
00397         UT_HashGridCell<utPtr>  *cell[ut_NUM_CELL_NEIGHBOURS];
00398         int                      numentries = 0;
00399         int                      i, j, k;
00400         int                      cellnum, ptnum, npts;
00401         UT_HashGridCell<utPtr>  *currcell;
00402 
00403         cell[0] = getCell(p);
00404 
00405         if (cell[0])
00406         {
00407             i = cell[0]->myXindex;
00408             j = cell[0]->myYindex;
00409             k = cell[0]->myZindex;
00410         }
00411         else
00412         {
00413             i = (int)SYSfloor(((p.x() - myOrigin.x()) / myCellWidth) + 0.5);
00414             if (i > 0)
00415             {
00416                 i *= 2;
00417                 i -= 1;
00418             }
00419             else
00420                 i *= -2;
00421 
00422             j = (int)SYSfloor(((p.y() - myOrigin.y()) / myCellWidth) + 0.5);
00423             if (j > 0)
00424             {
00425                 j *= 2;
00426                 j -= 1;
00427             }
00428             else
00429                 j *= -2;
00430 
00431             k = (int)SYSfloor(((p.z() - myOrigin.z()) / myCellWidth) + 0.5);
00432             if (k > 0)
00433             {
00434                 k *= 2;
00435                 k -= 1;
00436             }
00437             else
00438                 k *= -2;
00439         }
00440 
00441         // Store the proper indices of all of the surrounding
00442         // cells as well.  This takes a bit of work because of our
00443         // indexing scheme.  Naming scheme represents distance along
00444         // number line: il = i_left, ir = i_right, etc.
00445         int                      il, ir, jl, jr, kl, kr;
00446 
00447         if (cell[0])
00448         {
00449             il = cell[0]->myIL;
00450             ir = cell[0]->myIR;
00451             jl = cell[0]->myJL;
00452             jr = cell[0]->myJR;
00453             kl = cell[0]->myKL;
00454             kr = cell[0]->myKR;
00455         }
00456         else
00457         {
00458             if (i > 1)
00459             {
00460                 il = i + 2;
00461                 ir = i - 2;
00462             }
00463             else if (i == 1)
00464             {
00465                 il = 0;
00466                 ir = 3;
00467             }
00468             else // i == 0
00469             {
00470                 il = 2;
00471                 ir = 1;
00472             }
00473 
00474             if (j > 1)
00475             {
00476                 jl = j + 2;
00477                 jr = j - 2;
00478             }
00479             else if (j == 1)
00480             {
00481                 jl = 0;
00482                 jr = 3;
00483             }
00484             else // j == 0
00485             {
00486                 jl = 2;
00487                 jr = 1;
00488             }
00489 
00490             if (k > 1)
00491             {
00492                 kl = k + 2;
00493                 kr = k - 2;
00494             }
00495             else if (k == 1)
00496             {
00497                 kl = 0;
00498                 kr = 3;
00499             }
00500             else // k == 0
00501             {
00502                 kl = 2;
00503                 kr = 1;
00504             }
00505         }
00506 
00507         if (cell[0])
00508             numentries += cell[0]->myNumEntries;
00509 
00510         // Get all neighbour cells.
00511         cell[1] = getCell(il, jl, kl);
00512         if (cell[1])
00513             numentries += cell[1]->myNumEntries;
00514 
00515         cell[2] = getCell(il, jl, k);
00516         if (cell[2])
00517             numentries += cell[2]->myNumEntries;
00518 
00519         cell[3] = getCell(il, jl, kr);
00520         if (cell[3])
00521             numentries += cell[3]->myNumEntries;
00522 
00523         cell[4] = getCell(il, j, kl);
00524         if (cell[4])
00525             numentries += cell[4]->myNumEntries;
00526 
00527         cell[5] = getCell(il, j, k);
00528         if (cell[5])
00529             numentries += cell[5]->myNumEntries;
00530 
00531         cell[6] = getCell(il, j, kr);
00532         if (cell[6])
00533             numentries += cell[6]->myNumEntries;
00534 
00535         cell[7] = getCell(il, jr, kl);
00536         if (cell[7])
00537             numentries += cell[7]->myNumEntries;
00538 
00539         cell[8] = getCell(il, jr, k);
00540         if (cell[8])
00541             numentries += cell[8]->myNumEntries;
00542 
00543         cell[9] = getCell(il, jr, kr);
00544         if (cell[9])
00545             numentries += cell[9]->myNumEntries;
00546 
00547         cell[10] = getCell(i, jl, kl);
00548         if (cell[10])
00549             numentries += cell[10]->myNumEntries;
00550 
00551         cell[11] = getCell(i, jl, k);
00552         if (cell[11])
00553             numentries += cell[11]->myNumEntries;
00554 
00555         cell[12] = getCell(i, jl, kr);
00556         if (cell[12])
00557             numentries += cell[12]->myNumEntries;
00558 
00559         cell[13] = getCell(i, j, kl);
00560         if (cell[13])
00561             numentries += cell[13]->myNumEntries;
00562 
00563         cell[14] = getCell(i, j, kr);
00564         if (cell[14])
00565             numentries += cell[14]->myNumEntries;
00566 
00567         cell[15] = getCell(i, jr, kl);
00568         if (cell[15])
00569             numentries += cell[15]->myNumEntries;
00570 
00571         cell[16] = getCell(i, jr, k);
00572         if (cell[16])
00573             numentries += cell[16]->myNumEntries;
00574 
00575         cell[17] = getCell(i, jr, kr);
00576         if (cell[17])
00577             numentries += cell[17]->myNumEntries;
00578 
00579         cell[18] = getCell(ir, jl, kl);
00580         if (cell[18])
00581             numentries += cell[18]->myNumEntries;
00582 
00583         cell[19] = getCell(ir, jl, k);
00584         if (cell[19])
00585             numentries += cell[19]->myNumEntries;
00586 
00587         cell[20] = getCell(ir, jl, kr);
00588         if (cell[20])
00589             numentries += cell[20]->myNumEntries;
00590 
00591         cell[21] = getCell(ir, j, kl);
00592         if (cell[21])
00593             numentries += cell[21]->myNumEntries;
00594 
00595         cell[22] = getCell(ir, j, k);
00596         if (cell[22])
00597             numentries += cell[22]->myNumEntries;
00598 
00599         cell[23] = getCell(ir, j, kr);
00600         if (cell[23])
00601             numentries += cell[23]->myNumEntries;
00602 
00603         cell[24] = getCell(ir, jr, kl);
00604         if (cell[24])
00605             numentries += cell[24]->myNumEntries;
00606 
00607         cell[25] = getCell(ir, jr, k);
00608         if (cell[25])
00609             numentries += cell[25]->myNumEntries;
00610 
00611         cell[26] = getCell(ir, jr, kr);
00612         if (cell[26])
00613             numentries += cell[26]->myNumEntries;
00614 
00615         list.resize(numentries);
00616         list.entries(0);
00617 
00618         for (cellnum = 0; cellnum < ut_NUM_CELL_NEIGHBOURS; cellnum++)
00619         {
00620             if (cell[cellnum])
00621             {
00622                 currcell = cell[cellnum];
00623                 npts = currcell->myNumEntries;
00624 
00625                 for (ptnum = 0; ptnum < npts; ptnum++)
00626                 {
00627                     if ((p - myPositions(currcell->myIndices(ptnum))).length2() < myCellWidth2)
00628                         list.append(currcell->myElements(ptnum));
00629                 }
00630             }
00631         }
00632     }
00633 }
00634 
00635 template <typename utPtr>
00636 void
00637 UT_HashGrid<utPtr>::reset(unsigned int sz)
00638 {
00639     myMaxElements = 0;
00640 
00641     myGridSet.clear();
00642 
00643     myCellArray.entries(0);
00644     myCellArray.resize(sz);
00645 
00646     myPositions.entries(0);
00647     myPositions.resize(sz);
00648 }
00649 
00650 template <typename utPtr>
00651 void
00652 UT_HashGrid<utPtr>::reset(fpreal cellsize, const UT_Vector3 &origin,
00653                         bool fullinit, unsigned int sz)
00654 {
00655     reset(sz);
00656 
00657     myCellWidth = cellsize;
00658     myOrigin = origin;
00659     myFullInit = fullinit;
00660 }
00661 
00662 template <typename utPtr>
00663 UT_HashGridCell<utPtr> *
00664 UT_HashGrid<utPtr>::getCell(const UT_Vector3 &p, bool create)
00665 {
00666     int                          xi, yi, zi; // x, y and z indices
00667 
00668     xi = (int)SYSfloor(((p.x() - myOrigin.x()) / myCellWidth) + 0.5);
00669     if (xi > 0)
00670     {
00671         xi *= 2;
00672         xi -= 1;
00673     }
00674     else
00675         xi *= -2;
00676 
00677     yi = (int)SYSfloor(((p.y() - myOrigin.y()) / myCellWidth) + 0.5);
00678     if (yi > 0)
00679     {
00680         yi *= 2;
00681         yi -= 1;
00682     }
00683     else
00684         yi *= -2;
00685 
00686     zi = (int)SYSfloor(((p.z() - myOrigin.z()) / myCellWidth) + 0.5);
00687     if (zi > 0)
00688     {
00689         zi *= 2;
00690         zi -= 1;
00691     }
00692     else
00693         zi *= -2;
00694 
00695     return getCell(xi, yi, zi, create);
00696 }
00697 
00698 template <typename utPtr>
00699 UT_HashGridCell<utPtr> *
00700 UT_HashGrid<utPtr>::getCell(int xi, int yi, int zi, bool create)
00701 {
00702     int64                        index;
00703     int                          arrayindex = -1;
00704     UT_Thing                     cellthing;
00705 
00706     if (xi < 0 || yi < 0 || zi < 0 || xi >= ut_MAX_CELLS
00707             || yi >= ut_MAX_CELLS || zi >= ut_MAX_CELLS)
00708         return NULL;
00709 
00710     index = zi;
00711     index += yi * ut_MAX_CELLS;
00712     index += xi * ut_MAX_CELLS2;
00713 
00714     UT_Hash_Int64                hashkey(index);
00715 
00716     // Locate the cell number from the hash table.
00717     if (myGridSet.findSymbol(hashkey, &cellthing))
00718     {
00719         arrayindex = cellthing;
00720     }
00721 
00722     if (arrayindex >= 0)
00723         return &myCellArray(arrayindex);
00724     else if (create)
00725     {
00726         int                      cellindex = myCellArray.entries();
00727         UT_Thing                 newthing(cellindex);
00728 
00729         UT_HashGridCell<utPtr>   newcell(xi, yi, zi, cellindex);
00730 
00731         myCellArray.append(newcell);
00732 
00733         // Add this cell to the hash table.
00734         myGridSet.addSymbol(hashkey, newthing);
00735 
00736         return &myCellArray(cellindex);
00737     }
00738     else
00739         return NULL;
00740 }
00741 
00742 #endif // __UT_HashGrid.C