Menu
▾
▴
[Mevislabmodules-svn] SF.net SVN: mevislabmodules:[140] trunk/Community/General/Sources/ML/ MLCSOCommunityModules
|
From: <bar...@us...> - 2009-06-24 07:28:02
|
Revision: 140
http://mevislabmodules.svn.sourceforge.net/mevislabmodules/?rev=140&view=rev
Author: bartdedobbelaer
Date: 2009-06-24 07:27:57 +0000 (Wed, 24 Jun 2009)
Log Message:
-----------
- Moved MathUtils MinimalDistancePointClouds to MLCSOCommunityModules
Modified Paths:
--------------
trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.cpp
trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.h
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModules.pro
Added Paths:
-----------
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModulesDefs.h
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.cpp
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.h
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.cpp
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.h
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.cpp
trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.h
Modified: trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.cpp
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.cpp 2009-06-23 18:15:00 UTC (rev 139)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.cpp 2009-06-24 07:27:57 UTC (rev 140)
@@ -122,8 +122,8 @@
if (_csoList != NULL) {
if ((_csoList->numCSO() >= 2) && (_csoList->getCSOAt(0)->getIsFinished()) && (_csoList->getCSOAt(1)->getIsFinished())) {
- MATHUTILS_NAMESPACE::MinimalDistancePointClouds* pointSetsMinDist = NULL;
- ML_CHECK_NEW(pointSetsMinDist, MATHUTILS_NAMESPACE::MinimalDistancePointClouds);
+ MinimalDistancePointClouds* pointSetsMinDist = NULL;
+ ML_CHECK_NEW(pointSetsMinDist, MinimalDistancePointClouds);
std::vector<vec3>pointSet1;
std::vector<vec3>pointSet2;
Modified: trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.h
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.h 2009-06-23 18:15:00 UTC (rev 139)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/CSODistance/CSODistance.h 2009-06-24 07:27:57 UTC (rev 140)
@@ -2,10 +2,9 @@
#ifndef __CSODistance_H
#define __CSODistance_H
-#include "../MLCSOCommunityModulesSystem.h"
+#include "../MLCSOCommunityModulesDefs.h"
-#include <CSOBase/CSOList.h>
-#include <MinimalDistancePointClouds.h>
+#include "../MinimalDistancePointClouds/MinimalDistancePointClouds.h"
#include <mlXMarkerList.h>
ML_START_NAMESPACE
Modified: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModules.pro
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModules.pro 2009-06-23 18:15:00 UTC (rev 139)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModules.pro 2009-06-24 07:27:57 UTC (rev 140)
@@ -17,7 +17,7 @@
# add dependencies of this project here
-CONFIG += dll ML MLBase MLTools MathUtils newmat MLCSO boost
+CONFIG += dll ML MLBase MLTools newmat MLCSO boost
MLAB_PACKAGES += MeVisLab_Standard
@@ -32,10 +32,17 @@
HEADERS += \
MLCSOCommunityModulesInit.h \
MLCSOCommunityModulesSystem.h \
+ MLCSOCommunityModulesDefs.h \
+ MinimalDistancePointClouds\MinimalDistancePointClouds.h \
+ MinimalDistancePointClouds\TileSphere.h \
+ MinimalDistancePointClouds\TileSphereHashTable.h \
CSODistance\CSODistance.h
SOURCES += \
MLCSOCommunityModulesInit.cpp \
+ MinimalDistancePointClouds\MinimalDistancePointClouds.cpp \
+ MinimalDistancePointClouds\TileSphere.cpp \
+ MinimalDistancePointClouds\TileSphereHashTable.cpp \
CSODistance\CSODistance.cpp
RELATEDFILES += \
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModulesDefs.h
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModulesDefs.h (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MLCSOCommunityModulesDefs.h 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,30 @@
+// **InsertLicense** code
+//----------------------------------------------------------------------------------
+//! Often used definitions in CSO module library.
+/*!
+// \file CSOModuleDefs.h
+// \author Bart De Dobbelaer
+// \date 06/2009
+*/
+//----------------------------------------------------------------------------------
+
+#ifndef __CSOModuleDefs_h
+#define __CSOModuleDefs_h
+
+#include "MLCSOCommunityModulesSystem.h"
+
+#include <CSOBase/CSOList.h>
+
+#include <mlLibraryInitMacros.h>
+
+#include <math.h>
+#include <string>
+#include <vector>
+#include <map>
+#include <fstream>
+#include <sstream>
+
+
+#endif // __CSOModuleDefs_h
+
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.cpp
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.cpp (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.cpp 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,404 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! The MinimalDistancePointClouds implements
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+/*!
+// \file MinimalDistancePointClouds.cpp
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+#include "MinimalDistancePointClouds.h"
+
+
+ML_START_NAMESPACE
+
+//////////////////////////////////////////////////////////////////////////
+
+MinimalDistancePointClouds::MinimalDistancePointClouds()
+{
+ ML_TRACE_IN("MinimalDistancePointClouds::MinimalDistancePointClouds() ");
+
+ _pointSet1 = NULL;
+ _pointSet2 = NULL;
+
+ _hashTable = NULL;
+
+ _size1 = 0;
+ _size2 = 0;
+
+ _sphereIndex = 0;
+ _entries = -1;
+ _partition = -1;
+
+ _tileSphere1 = NULL;
+ _tileSphere2 = NULL;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+MinimalDistancePointClouds::~MinimalDistancePointClouds()
+{
+ ML_TRACE_IN("MinimalDistancePointClouds::~MinimalDistancePointClouds()");
+
+ ML_DELETE_ARR(_pointSet1);
+ ML_DELETE_ARR(_pointSet2);
+
+ ML_DELETE(_tileSphere1);
+ ML_DELETE(_tileSphere2);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setPointSets(const std::vector<ml::vec3>& pointCloud1, const std::vector<ml::vec3>& pointCloud2)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setPointSets()");
+
+ unsigned int i = 0;
+ unsigned int entry = 0;
+
+ ML_DELETE_ARR(_pointSet1);
+ ML_DELETE_ARR(_pointSet2);
+
+ _size1 = pointCloud1.size();
+ _size2 = pointCloud2.size();
+
+ ML_CHECK_NEW(_pointSet1, float[3 * _size1]);
+ ML_CHECK_NEW(_pointSet2, float[3 * _size2]);
+
+ // copy positions of the nodes to float array
+
+ for (i = 0; i < _size1; i++){
+
+ const ml::vec3& currPos = pointCloud1[i];
+
+ _pointSet1[entry++] = static_cast<float>(currPos[0]);
+ _pointSet1[entry++] = static_cast<float>(currPos[1]);
+ _pointSet1[entry++] = static_cast<float>(currPos[2]);
+ }
+
+ entry = 0;
+
+ for (i = 0; i < _size2; i++){
+
+ const ml::vec3& currPos = pointCloud2[i];
+
+ _pointSet2[entry++] = static_cast<float>(currPos[0]);
+ _pointSet2[entry++] = static_cast<float>(currPos[1]);
+ _pointSet2[entry++] = currPos[2];
+ }
+
+ if ((_pointSet1 != NULL) && (_pointSet2 != NULL)){
+
+ ML_DELETE(_tileSphere1);
+ ML_DELETE(_tileSphere2);
+
+ _tileSphere1 = generateTree(_pointSet1, _size1);
+ _tileSphere2 = generateTree(_pointSet2, _size2);
+
+ // Determine size of both spheres
+ _tileSphere1->getDeFactoSize();
+ _tileSphere2->getDeFactoSize();
+
+
+ } else {
+ std::cout << "MinimalDistancePointClouds::setPointSets: One of the arguments was NULL" << std::endl;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setFirstSinglePoint(const ml::vec3& point)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setFirstSinglePoint()");
+
+
+ ML_DELETE_ARR(_pointSet1);
+ ML_CHECK_NEW (_pointSet1, float[3]);
+
+ // copy node position to point set.
+
+ _pointSet1[0] = static_cast<float>(point[0]);
+ _pointSet1[1] = static_cast<float>(point[1]);
+ _pointSet1[2] = static_cast<float>(point[2]);
+ _size1 = 1;
+
+ // The second tileSphere is already set
+
+ ML_DELETE(_tileSphere1);
+
+ _tileSphere1 = generateTree(_pointSet1, _size1);
+ _tileSphere1->getDeFactoSize();
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setFirstPointSet(const std::vector<ml::vec3>& pointCloud)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setFirstPointSet()");
+
+ unsigned int i = 0;
+ unsigned int entry = 0;
+
+ // copy node positions to point set.
+
+ _size1 = pointCloud.size();
+
+ ML_DELETE_ARR(_pointSet1);
+ ML_CHECK_NEW (_pointSet1, float[3 * _size1]);
+
+
+ for (i = 0; i < _size1; i++){
+
+ const ml::vec3& currPos = pointCloud[i];
+
+ _pointSet1[entry++] = static_cast<float>(currPos[0]);
+ _pointSet1[entry++] = static_cast<float>(currPos[1]);
+ _pointSet1[entry++] = static_cast<float>(currPos[2]);
+ }
+
+ // The second tileSphere is already set
+
+ if (_pointSet1 != NULL){
+
+ ML_DELETE(_tileSphere1);
+
+ _tileSphere1 = generateTree(_pointSet1, _size1);
+ _tileSphere1->getDeFactoSize();
+
+ } else {
+ std::cout << "MinimalDistancePointClouds::setFirstPointSets: The argument was NULL" << std::endl;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::computeDistance(ml::vec3& point1, ml::vec3& point2)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::computeDistance()");
+
+ // Both tileSpheres exist
+ if (_tileSphere1 && _tileSphere2){
+
+ // Initialize index
+ _sphereIndex = 0;
+
+ // Generate hash table
+ ML_CHECK_NEW(_hashTable, TileSphereHashTable);
+
+ float distance;
+ float* p1 = NULL; // Return coordinates
+ float* p2 = NULL;
+
+ // Compute the minimal distance of both point sets
+ distance = _tileSphere1->computeDistance(_tileSphere2, p1, p2);
+
+ if ((p1 != NULL) && (p2 != NULL)){
+
+ point1[0] = p1[0];
+ point1[1] = p1[1];
+ point1[2] = p1[2];
+
+ point2[0] = p2[0];
+ point2[1] = p2[1];
+ point2[2] = p2[2];
+ } else {
+ std::cout << "MinimalDistancePointClouds::computeDistance: resulting points were NULL" << std::endl;
+ }
+
+ ML_DELETE(_hashTable);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::computeDistance(float*& point1, float*& point2)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::computeDistance(float*& point1, float*& point2) ");
+
+ // Both tileSpheres exist
+ if (_tileSphere1 && _tileSphere2){
+
+ // Initialize index
+ _sphereIndex = 0;
+
+ // Generate hash table
+ ML_CHECK_NEW(_hashTable, TileSphereHashTable);
+
+ // Compute the minimal distance of both point sets
+ (void)_tileSphere1->computeDistance(_tileSphere2, point1, point2);
+
+ ML_DELETE(_hashTable);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setError(float error)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setError(float error) ");
+
+ if (error > 1) { error = 1; }
+ if (error < 0) { error = 0; }
+
+ _error = error;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphere* MinimalDistancePointClouds::generateTree(float* pointSet, long size)
+{
+ ML_TRACE_IN("TileSphere* MinimalDistancePointClouds::generateTree(float* pointSet, long size) ");
+
+ // Do we have a valid point set?
+ if ((pointSet != NULL) && (size != 0)) {
+
+ // Calculate parameters for the TileSphere:
+ // A single sphere should not contain more than 2000 entries.
+ // The size parameter should not become smaller than the number of sub spheres times 2000.
+ // The less sub spheres, the faster the algorithm will be.
+ // If the total amount of points is less than (2^3)*2000, the number of points
+ // in one sphere may be reduced.
+ // This guarantees (except for worst cases of spatial point distribution) optimal
+ // runtime behavior.
+ int partition = 0;
+ int entries = 0;
+
+ if (_partition == -1) {
+
+ partition = 1 + (int)pow(((float)size / (float)_entries), (1.0f / 3.0f));
+
+ if (partition < 2){ partition = 2; }
+
+ entries = size / (int)pow(partition, 3);
+
+ if (entries < 3){ entries = 3; }
+
+ } else {
+ partition = _partition;
+ entries = _entries;
+ }
+
+ TileSphere* tileSphere = NULL;
+ ML_CHECK_NEW(tileSphere, TileSphere(this, partition, entries, _error));
+
+ float* pointPos = pointSet;
+ float minX=0, maxX=0, minY=0, maxY=0, minZ=0, maxZ=0;
+
+ // compute Bounding Box
+ getBB(pointSet, size, minX, maxX, minY, maxY, minZ, maxZ);
+
+ // and assign the Bounding Box to the main sphere
+ tileSphere->setBB(minX, maxX, minY, maxY, minZ, maxZ);
+
+ // insert all points
+ //long tmpSphereCounter = _sphereIndex;
+ long counter=0;
+
+ for (counter = 0; counter < size; counter++) {
+ tileSphere->addPoint(pointPos);
+ pointPos += 3;
+ }
+
+ return tileSphere;
+ }
+
+ // If the point set was not valid, return a new (and empty) TileSphere.
+ TileSphere* dummy = NULL;
+ ML_CHECK_NEW(dummy, TileSphere);
+ return dummy;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::getBB(float* pointSet, long size, float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::getBB(float* pointSet, long size, float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ)");
+
+ // Return the bounding box of a point set
+ if ((pointSet != NULL) && (size > 0)) {
+ float* pointPos = pointSet;
+ minX = maxX = *(pointPos++);
+ minY = maxY = *(pointPos++);
+ minZ = maxZ = *(pointPos++);
+
+ long counter=0;
+
+ for (counter = 1; counter < size; counter++) {
+ if (minX > *pointPos) { minX = *pointPos; }
+ if (maxX < *pointPos) { maxX = *pointPos; }
+ pointPos++;
+ if (minY > *pointPos) { minY = *pointPos; }
+ if (maxY < *pointPos) { maxY = *pointPos; }
+ pointPos++;
+ if (minZ > *pointPos) { minZ = *pointPos; }
+ if (maxZ < *pointPos) { maxZ = *pointPos; }
+ pointPos++;
+ } // for
+ } // if
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::verbose(bool onOff)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::verbose(bool onOff) ");
+
+ _verbose = onOff;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setNumEntries(int entries)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setNumEntries(int entries) ");
+
+ _entries = entries;
+ _partition = -1;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void MinimalDistancePointClouds::setParams(int entries, int partition)
+{
+ ML_TRACE_IN("void MinimalDistancePointClouds::setParams(int entries, int partition) ");
+
+ _entries = entries;
+ _partition = partition;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+int MinimalDistancePointClouds::getUniqueIndex()
+{
+ ML_TRACE_IN("int MinimalDistancePointClouds::getUniqueIndex()");
+
+ return _sphereIndex++;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphereHashTable* MinimalDistancePointClouds::getHashTable()
+{
+ ML_TRACE_IN("TileSphereHashTable* MinimalDistancePointClouds::getHashTable() ");
+
+ return _hashTable;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+
+ML_END_NAMESPACE
+
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.h
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.h (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/MinimalDistancePointClouds.h 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,124 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! The MinimalDistancePointClouds implements
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+/*!
+// \file MinimalDistancePointClouds.h
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+
+
+#ifndef __MinimalDistancePointClouds_H
+#define __MinimalDistancePointClouds_H
+
+#include "../MLCSOCommunityModulesDefs.h"
+
+#include "TileSphere.h"
+#include "TileSphereHashTable.h"
+
+#include "mlVec3.h"
+
+
+ML_START_NAMESPACE
+
+//! The MinimalDistancePointClouds implements
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+class MinimalDistancePointClouds
+{
+
+public:
+
+ //! Constructor.
+ MinimalDistancePointClouds();
+ //! Destructor.
+ virtual ~MinimalDistancePointClouds();
+
+ //! This method passes the two point clouds in the form of two standard vectors.
+ void setPointSets(const std::vector<ml::vec3>& pointCloud1, const std::vector<ml::vec3>& pointCloud2);
+ //! Sets only the first point set anew. The second one (with all its TileSphere tree computations)
+ //! is left as it was.
+ void setFirstPointSet(const std::vector<ml::vec3>& pointCloud);
+ //! Set only the first point set anew, which consists only of a single point.
+ //! The second pointSet is left as it was.
+ void setFirstSinglePoint(const ml::vec3& point);
+
+
+ //! This parameter describes how many points can be put as maximum into one sub sphere,
+ //! but the designed value can be lower. The default value is 2000.
+ //! The concrete value for \c _entries and \c _partition will be computed automatically.
+ void setNumEntries(int entries);
+ //! Sets fix values for both objects for \c _entries and \c _partition.
+ void setParams(int entries, int partition);
+ //! Describes the maintainable error. 0 = 0% and 1 = 100%. The default value is 0.
+ void setError(float error);
+
+ //! Returns a copy of the both points with the minimal distance.
+ //! The method \c setPointSets must have been called before.
+ void computeDistance(float* &point1, float* &point2);
+ //! Returns two points with minimal distance as vec3.
+ //! The method \c setPointSets must have been called before.
+ void computeDistance(ml::vec3& point1, ml::vec3& point2);
+
+
+ //! Returns an unique index for each tile sphere.
+ int getUniqueIndex();
+ //! Returns a pointer to the hash table.
+ TileSphereHashTable* getHashTable();
+
+ //! Dumps the console with additional debugging info.
+ void verbose(bool onOff);
+
+
+private:
+
+ //! The one point set.
+ float* _pointSet1;
+ //! The other point set.
+ float* _pointSet2;
+ //! The sizes of the point sets.
+ int _size1, _size2;
+ //! The internal sphere index.
+ unsigned int _sphereIndex;
+ //! The internal hash table.
+ TileSphereHashTable* _hashTable;
+
+ //! Pointer to the first tileSphere.
+ TileSphere* _tileSphere1;
+ //! Pointer to the second tileSphere.
+ TileSphere* _tileSphere2;
+
+ //! The maintainable error.
+ float _error;
+
+ //! Dumps the console with additional debugging info.
+ bool _verbose;
+
+ //! Set by \c setNumEntries.
+ int _entries, _partition;
+
+ //! Generates the tree of spheres for each point set.
+ TileSphere* generateTree(float* pointSet, long size);
+
+ //! Gets the BB of the main point set.
+ void getBB(float* pointSet, long size, float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ);
+};
+
+ML_END_NAMESPACE
+
+
+#endif // __MinimalDistancePointClouds_H
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.cpp
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.cpp (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.cpp 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,573 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! TileSphere is used in the class \c MinimalDistancePointClouds.
+//! It defines a single sub sphere for
+//! a fast nearest pair search algortihm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+//! TileSphere will generate her own sub spheres if necessary
+/*!
+// \file TileSphere.cpp
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+#include "TileSphere.h"
+#include "MinimalDistancePointClouds.h"
+
+
+ML_START_NAMESPACE
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphere::TileSphere()
+{
+ ML_TRACE_IN("TileSphere::TileSphere() ");
+
+ _initSphere(NULL, 2, 1103, 0);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphere::TileSphere(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error)
+{
+ ML_TRACE_IN("TileSphere::TileSphere(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error) ");
+
+ _initSphere(minimalDistance, maxPartition, numElements, error);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphere::~TileSphere()
+{
+ ML_TRACE_IN("TileSphere::~TileSphere()");
+
+ ML_DELETE_ARR(_tileSpheres);
+ ML_DELETE_ARR(_subset);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::setParameter(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error)
+{
+ ML_TRACE_IN("void TileSphere::setParameter(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error) ");
+
+ _minimalDistance = minimalDistance;
+ _maxEntries = numElements;
+ _partition = maxPartition;
+ _cubicPartition = _partition * _partition * _partition;
+ _sphereIndex = minimalDistance->getUniqueIndex();
+ _error = error;
+
+ _subset = NULL;
+ ML_CHECK_NEW(_subset, float*[numElements]);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+float TileSphere::computeDistance(TileSphere* tileSphere, float*& point1, float*& point2)
+{
+ ML_TRACE_IN("float TileSphere::computeDistance(TileSphere* tileSphere, float*& point1, float*& point2)");
+
+ float distance = -1;
+ // Determine current distance
+ if ((point1 != NULL) && (point2 != NULL)){
+ distance = _distance(point1, point2);
+ }
+
+ if (tileSphere != NULL) {
+
+ // Register this call in the hash table
+ _minimalDistance->getHashTable()->addPair(this, tileSphere);
+
+ // Distance can not be less..
+ if (fabs(distance) < FLT_EPSILON){
+ return 0;
+ }
+
+ // Descend recursively in both sets until leafs are reached.
+ // On the way, split the sphere with the largest radius.
+
+ if ((_radius > tileSphere->_getRadius()) && _hasSubSpheresFlag) {
+ distance = tileSphere->computeDistance(this->_getPreciserSphere(tileSphere, distance), point2, point1);
+ } else {
+ if ((_radius < tileSphere->_getRadius()) && tileSphere->_hasSubSpheres()) {
+ distance = this->computeDistance(tileSphere->_getPreciserSphere(this, distance), point1, point2);
+ } else {
+ // This branch is active if the one sphere was smaller,
+ // but the other did not contain any sub spheres.
+ if (_hasSubSpheresFlag) {
+ distance = tileSphere->computeDistance(this->_getPreciserSphere(tileSphere, distance), point2, point1);
+ }
+ if (tileSphere->_hasSubSpheres()) {
+ distance = this->computeDistance(tileSphere->_getPreciserSphere(this, distance), point1, point2);
+ }
+ }
+ }
+
+ if (!_hasSubSpheresFlag && !tileSphere->_hasSubSpheres()) {
+ // Compute direct distance between two sets of points.
+
+ float** otherSubset = NULL;
+ unsigned int otherSize = 0;
+ float tmpDistance = 0;
+ float tmpDistance2 = 0;
+ float *tmpPoint1 = NULL;
+ float *tmpPoint2 = NULL;
+
+ int otherSizeParameter=0;
+ tileSphere->_getSubset(otherSubset, otherSizeParameter);
+ otherSize = static_cast<unsigned int>(otherSizeParameter);
+
+ if (distance == -1) {
+ distance = _distance(_subset[0], otherSubset[0]);
+ point1 = _subset[0];
+ point2 = otherSubset[0];
+ }
+
+ tmpDistance2 = _fastDistance(_subset[0], otherSubset[0]);
+ tmpPoint1 = _subset[0];
+ tmpPoint2 = otherSubset[0];
+
+ unsigned int counter=0, otherCounter=0;
+
+ // Test all points pairwise
+ for (otherCounter = 0; otherCounter < otherSize; otherCounter++) {
+ for (counter = 0; counter < _numEntries; counter++) {
+ tmpDistance = _fastDistance(_subset[counter], otherSubset[otherCounter]);
+ if (tmpDistance2 > tmpDistance) {
+ tmpDistance2 = tmpDistance;
+ tmpPoint1 = _subset[counter];
+ tmpPoint2 = otherSubset[otherCounter];
+ }
+ }
+ }
+
+ tmpDistance2 = sqrtf(tmpDistance2);
+ if (distance > tmpDistance2) {
+ distance = tmpDistance2;
+ point1 = tmpPoint1;
+ point2 = tmpPoint2;
+ }
+ }
+ if (_hasSubSpheresFlag) {
+ // Compare the distance with all distances to other spheres
+ // and test if there are other spheres within the same range.
+ TileSphere* tmp = this->_getPreciserSphere(tileSphere, distance);
+ while (tmp != NULL) {
+ distance = tileSphere->computeDistance(tmp, point1, point2);
+ tmp = this->_getPreciserSphere(tileSphere, distance);
+ }
+ }
+ if (tileSphere->_hasSubSpheres()) {
+ // Compare the distance with all distances to each other spheres
+ // and test if there are other spheres within the same range.
+ TileSphere* tmp = tileSphere->_getPreciserSphere(this, distance);
+ while (tmp != NULL) {
+ distance = this->computeDistance(tmp, point1, point2);
+ tmp = tileSphere->_getPreciserSphere(this, distance);
+ }
+ }
+ }
+
+ return distance;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+unsigned int TileSphere::getSphereIndex()
+{
+ ML_TRACE_IN("unsigned int TileSphere::getSphereIndex() ");
+
+ return _sphereIndex;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::getDeFactoSize()
+{
+ ML_TRACE_IN("void TileSphere::getDeFactoSize()");
+
+ // Computes the central point of the BB and acquire the farthest
+ // sub sphere/point of the sub spheres/pointset for the radius
+ float minX=0, maxX=0, minY=0, maxY=0, minZ=0, maxZ=0;
+ bool unInit = true;
+
+ unsigned int counter=0;
+
+ if (_hasSubSpheresFlag) {
+ // Computes the BB of the contained spheres
+ float buffer=0;
+ for (counter = 0; counter < _cubicPartition; counter++) {
+ _tileSpheres[counter].getDeFactoSize();
+ // not every sphere has
+ if (_tileSpheres[counter]._radius != -1) {
+ if (unInit) {
+ minX = _tileSpheres[counter]._position[0] - _tileSpheres[counter]._radius;
+ maxX = _tileSpheres[counter]._position[0] + _tileSpheres[counter]._radius;
+ minY = _tileSpheres[counter]._position[1] - _tileSpheres[counter]._radius;
+ maxY = _tileSpheres[counter]._position[1] + _tileSpheres[counter]._radius;
+ minZ = _tileSpheres[counter]._position[2] - _tileSpheres[counter]._radius;
+ maxZ = _tileSpheres[counter]._position[2] + _tileSpheres[counter]._radius;
+ unInit = false;
+ } else {
+ buffer = _tileSpheres[counter]._position[0] - _tileSpheres[counter]._radius;
+ if (minX > buffer) { minX = buffer; }
+ buffer = _tileSpheres[counter]._position[0] + _tileSpheres[counter]._radius;
+ if (maxX < buffer) { maxX = buffer; }
+ buffer = _tileSpheres[counter]._position[1] - _tileSpheres[counter]._radius;
+ if (minY > buffer) { minY = buffer; }
+ buffer = _tileSpheres[counter]._position[1] + _tileSpheres[counter]._radius;
+ if (maxY < buffer) { maxY = buffer; }
+ buffer = _tileSpheres[counter]._position[2] - _tileSpheres[counter]._radius;
+ if (minZ > buffer) { minZ = buffer; }
+ buffer = _tileSpheres[counter]._position[2] + _tileSpheres[counter]._radius;
+ if (maxZ < buffer) { maxZ = buffer; }
+ }
+ }
+ }
+ } else {
+ if (_numEntries != 0) {
+ unInit = false;
+ float* pointPos = _subset[0];
+ minX = maxX = * pointPos;
+ minY = maxY = *(pointPos + 1);
+ minZ = maxZ = *(pointPos + 2);
+
+ for (counter = 1; counter < _numEntries; counter++) {
+ pointPos = _subset[counter];
+ if (minX > *pointPos) { minX = *pointPos; }
+ if (maxX < *pointPos) { maxX = *pointPos; }
+ pointPos++;
+ if (minY > *pointPos) { minY = *pointPos; }
+ if (maxY < *pointPos) { maxY = *pointPos; }
+ pointPos++;
+ if (minZ > *pointPos) { minZ = *pointPos; }
+ if (maxZ < *pointPos) { maxZ = *pointPos; }
+ }
+ }
+ }
+ if (!unInit) {
+ _position[0] = (maxX + minX) * 0.5f;
+ _position[1] = (maxY + minY) * 0.5f;
+ _position[2] = (maxZ + minZ) * 0.5f;
+ if (_hasSubSpheresFlag) {
+ bool init = true;
+ float tmpDist=0;
+ for (counter = 0; counter < _cubicPartition; counter++) {
+ if (_tileSpheres[counter]._getRadius() != -1) {
+ if (init) {
+ _radius = _distance(_position, _tileSpheres[counter]._getPosition()) + _tileSpheres[counter]._getRadius();
+ init = false;
+ } else {
+ tmpDist = _distance(_position, _tileSpheres[counter]._getPosition()) + _tileSpheres[counter]._getRadius();
+ if (tmpDist > _radius){
+ _radius = tmpDist;
+ }
+ }
+ }
+ }
+ } else {
+ float tmpDist;
+ _radius = _distance(_position, _subset[0]);
+ for (counter = 1; counter < _numEntries; counter++) {
+ tmpDist = _distance(_position, _subset[counter]);
+ if (tmpDist > _radius){
+ _radius = tmpDist;
+ }
+ }
+ }
+ } else {
+ _radius = -1;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::getStatistics(int &_treeDepth, int &_usedSpheres, int &_leafSpheres, int &_maxEnt)
+{
+ ML_TRACE_IN("void TileSphere::getStatistics(int &_treeDepth, int &_usedSpheres, int &_leafSpheres, int &_maxEnt) ");
+
+ int treeDepth = 0, treeDepthTmp = 0;
+ float** dummy = NULL;
+ int subsetSize = 0;
+
+ unsigned int counter=0;
+
+ // Has sub spheres
+ if (_hasSubSpheresFlag) {
+ for (counter = 0; counter < _cubicPartition; counter++) {
+ _tileSpheres[counter]._getSubset(dummy, subsetSize);
+ if (subsetSize != 0 || _tileSpheres[counter]._hasSubSpheres()) {
+ _tileSpheres[counter].getStatistics(treeDepthTmp, _usedSpheres, _leafSpheres, _maxEnt);
+ if (treeDepthTmp > treeDepth) {
+ treeDepth = treeDepthTmp;
+ }
+ }
+ }
+ } else {
+ // Has set of points
+ if (_numEntries > _maxEnt){ _maxEnt = _numEntries; }
+ _leafSpheres++;
+ }
+
+ treeDepth++;
+ _usedSpheres++;
+
+ _treeDepth = treeDepth;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::setBB(float minX, float maxX, float minY, float maxY, float minZ, float maxZ)
+{
+ ML_TRACE_IN("void TileSphere::setBB(float minX, float maxX, float minY, float maxY, float minZ, float maxZ) ");
+
+ // Assigns a bounding box to the tileSphere.
+ _minX = minX;
+ _maxX = maxX;
+ _minY = minY;
+ _maxY = maxY;
+ _minZ = minZ;
+ _maxZ = maxZ;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::_getBB(float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ)
+{
+ ML_TRACE_IN("void TileSphere::_getBB(float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ) ");
+
+ // Gets the bounding box of the tileSphere.
+ minX = _minX;
+ maxX = _maxX;
+ minY = _minY;
+ maxY = _maxY;
+ minZ = _minZ;
+ maxZ = _maxZ;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::addPoint(float* position)
+{
+ ML_TRACE_IN("void TileSphere::addPoint(float* position) ");
+
+ // Adds a point into the tile sphere.
+ float minX=0, maxX=0, minY=0, maxY=0, minZ=0, maxZ=0;
+
+ int counter = 0;
+
+ // If the sphere has sub spheres, add point into the according sub sphere.
+ if (_hasSubSpheresFlag) {
+ for (counter = 0; counter < _cubicPartition; counter++) {
+ _tileSpheres[counter]._getBB(minX, maxX, minY, maxY, minZ, maxZ);
+
+ if ((*(position) >= minX) &&
+ (*(position) <= maxX) &&
+ (*(position + 1) >= minY) &&
+ (*(position + 1) <= maxY) &&
+ (*(position + 2) >= minZ) &&
+ (*(position + 2) <= maxZ))
+ {
+ _tileSpheres[counter].addPoint(position);
+ }
+ }
+ } else {
+ // If there is no further sub-division, integrate point into subset.
+ _subset[_numEntries] = position;
+ _numEntries++;
+ // If capacity is reached, establish sub spheres and transfer the containing points.
+ if (_numEntries == static_cast<unsigned int>(_maxEntries)) {
+ // Establish further sub spheres.
+ if (_hasSubSpheresFlag == false) {
+ ML_DELETE_ARR(_tileSpheres);
+ ML_CHECK_NEW (_tileSpheres, TileSphere[_cubicPartition]);
+ _hasSubSpheresFlag = true;
+ }
+
+ int xCounter=0, yCounter=0, zCounter=0;
+
+ float partitionDiv = 1.0f / static_cast<float>(_partition);
+
+ float stepX = (_maxX - _minX) * partitionDiv;
+ float stepY = (_maxY - _minY) * partitionDiv;
+ float stepZ = (_maxZ - _minZ) * partitionDiv;
+
+ float newMaxX = 0.0f;
+ float newMaxY = 0.0f;
+ float newMaxZ = 0.0f;
+
+ // Constitute BBs for the sub spheres.
+ for (xCounter = 0; xCounter < _partition; xCounter++) {
+ for (yCounter = 0; yCounter < _partition; yCounter++) {
+ for (zCounter = 0; zCounter < _partition; zCounter++) {
+ _tileSpheres[counter].setParameter(_minimalDistance, _partition, _numEntries, _error);
+
+ // to avoid rounding errors, take the real maximum value at the upper border
+ newMaxX = (xCounter+1 < _partition) ? (_minX + stepX * xCounter + stepX) : _maxX;
+ newMaxY = (yCounter+1 < _partition) ? (_minY + stepY * yCounter + stepY) : _maxY;
+ newMaxZ = (zCounter+1 < _partition) ? (_minZ + stepZ * zCounter + stepZ) : _maxZ;
+
+ _tileSpheres[counter].setBB(
+ _minX + stepX * xCounter,
+ newMaxX,
+ _minY + stepY * yCounter,
+ newMaxY,
+ _minZ + stepZ * zCounter,
+ newMaxZ);
+
+ counter++;
+ }
+ }
+ }
+ // Transfer points
+ for (counter = 0; counter < _maxEntries; counter++){
+ addPoint(_subset[counter]);
+ }
+ }
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::_initSphere(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error)
+{
+ ML_TRACE_IN("void TileSphere::_initSphere(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error) ");
+
+ _numEntries = 0;
+ _hasSubSpheresFlag = false;
+ _radius = -1;
+ _tileSpheres = NULL;
+ _subset = NULL;
+
+ if (minimalDistance != NULL){
+ setParameter(minimalDistance, maxPartition, numElements, error);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+float TileSphere::_getRadius()
+{
+ ML_TRACE_IN("float TileSphere::_getRadius()");
+
+ return _radius;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+float* TileSphere::_getPosition()
+{
+ ML_TRACE_IN("float* TileSphere::_getPosition()");
+
+ return _position;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphere::_getSubset(float** &subset, int &size)
+{
+ ML_TRACE_IN("void TileSphere::_getSubset(float** &subset, int &size)");
+
+ subset = _subset;
+ size = _numEntries;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+bool TileSphere::_hasSubSpheres()
+{
+ ML_TRACE_IN("bool TileSphere::_hasSubSpheres()");
+
+ return _hasSubSpheresFlag;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphere* TileSphere::_getPreciserSphere(TileSphere* referenceSphere, float closestDistance)
+{
+ ML_TRACE_IN("TileSphere* TileSphere::_getPreciserSphere(TileSphere* referenceSphere, float closestDistance) ");
+
+ bool unInit = true;
+ bool firstRun = false;
+
+ if (closestDistance == -1){
+ firstRun = true;
+ }
+
+ TileSphere *closestTileSphere = NULL, *tmpSphere = NULL;
+ float tmpDistance=0;
+
+ unsigned int counter=0;
+
+ // Traverse each sub sphere.
+
+ for (counter = 0; counter < _cubicPartition; counter++) {
+
+ // Only examine further if the sphere contains more details.
+ if ((_tileSpheres[counter]._getRadius() != -1) &&
+ !_minimalDistance->getHashTable()->existPair(&_tileSpheres[counter], referenceSphere))
+ {
+ if (unInit) {
+ // Initialize variables once if they are yet uninitialized.
+ tmpDistance = _distance(&_tileSpheres[counter], referenceSphere);
+ if (firstRun) {
+ unInit = false;
+ closestTileSphere = &_tileSpheres[counter];
+ closestDistance = tmpDistance;
+ } else {
+ if ((tmpDistance * (1 + _error)) < closestDistance) {
+ unInit = false;
+ closestTileSphere = &_tileSpheres[counter];
+ closestDistance = tmpDistance;
+ }
+ }
+ } else {
+ tmpSphere = &_tileSpheres[counter];
+ tmpDistance = _distance(tmpSphere, referenceSphere);
+ if (firstRun) {
+ if (tmpDistance < closestDistance) {
+ closestDistance = tmpDistance;
+ closestTileSphere = tmpSphere;
+ }
+ } else {
+ if ((tmpDistance * (1 + _error)) < closestDistance) {
+ closestDistance = tmpDistance;
+ closestTileSphere = tmpSphere;
+ }
+ }
+ }
+ }
+ }
+
+ return closestTileSphere;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+float TileSphere::_distance(TileSphere* tileSphere1, TileSphere* tileSphere2)
+{
+ ML_TRACE_IN("float TileSphere::_distance(TileSphere* tileSphere1, TileSphere* tileSphere2)");
+
+ float radiusSum = tileSphere1->_getRadius() + tileSphere2->_getRadius();
+
+ float result = _distance(tileSphere1->_getPosition(), tileSphere2->_getPosition()) - radiusSum;
+
+ return (result>=0)?result:0;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+
+ML_END_NAMESPACE
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.h
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.h (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphere.h 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,158 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! TileSphere is used in the class \c MinimalDistancePointClouds.
+//! It defines a single sub sphere for
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+//! TileSphere will generate its own sub spheres if necessary.
+/*!
+// \file TileSphere.h
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+
+#ifndef __TileSphere_H
+#define __TileSphere_H
+
+#include "../MLCSOCommunityModulesDefs.h"
+
+#include <mlVec3.h>
+#include "TileSphereHashTable.h"
+
+
+ML_START_NAMESPACE
+
+// Forward declaration
+class MinimalDistancePointClouds;
+
+
+//! TileSphere is used in the class \c MinimalDistancePointClouds.
+//! It defines a single sub sphere for
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+//! TileSphere will generate its own sub spheres if necessary.
+class TileSphere
+{
+
+public:
+
+ //! Default Constructor.
+ TileSphere();
+ //! Constructor with a pointer on the main class and presets for the distance computation.
+ TileSphere(MinimalDistancePointClouds* minimalDistance, int maxPartition = 2, int numElements = 1103, float error = 0);
+ //! Destructor.
+ virtual ~TileSphere();
+
+ //! Must be called, when TileSphere was instantiated with the default constructor.
+ void setParameter(MinimalDistancePointClouds* minimalDistance, int maxPartition, int numElements, float error);
+
+ //! Defines which points will be put into this sphere.
+ void setBB(float minX, float maxX, float minY, float maxY, float minZ, float maxZ);
+ //! Put a point into this sphere (or one of its sub spheres).
+ void addPoint(float* position);
+ //! Computes the optimal bounding sphere.
+ void getDeFactoSize();
+ //! Computes the distance and returns references to the nearest points of both sets.
+ float computeDistance(TileSphere* tileSphere, float*& point1, float*& point2);
+
+ //! Computes the distance and returns a references to the entryNumbers of the nearest nodes of both sets.
+ float computeDistance(TileSphere* tileSphere, unsigned int& node1, unsigned int& nodet2);
+
+
+ //! Returns the index of the TileSphere.
+ unsigned int getSphereIndex();
+
+ //! Returns statistics for debugging purposes.
+ void getStatistics(int &_treeDepth, int &usedSpheres, int &leafSpheres, int &_maxEnt);
+
+
+private:
+
+ //! Initializes the tile sphere.
+ void _initSphere(MinimalDistancePointClouds* minimalDistance, int partition, int numElements, float error);
+ //! Pointer to the main class.
+ MinimalDistancePointClouds* _minimalDistance;
+ //! Pointer to the sub spheres.
+ TileSphere* _tileSpheres;
+
+ //! Stores the sphere index.
+ unsigned int _sphereIndex;
+
+ //! The maintainable error.
+ float _error;
+
+ //! Stores whether this sphere has sub spheres.
+ bool _hasSubSpheresFlag;
+ //! Stores the number of sub spheres, according to _partition to the power of 3.
+ unsigned int _partition;
+ //! The cubic of the partition.
+ unsigned int _cubicPartition;
+
+
+ //! Pointer to the contained points.
+ float** _subset;
+ //! Number of contained points.
+ unsigned int _numEntries;
+ //! Maximum number of contained points.
+ int _maxEntries;
+
+ //! Extend of the point set.
+ float _minX, _maxX, _minY, _maxY, _minZ, _maxZ;
+ //! Position vector of the tile sphere.
+ float _position[3];
+ //! Radius of the tile sphere.
+ float _radius;
+
+ //! Returns the BB of the tile sphere.
+ void _getBB(float& minX, float& maxX, float& minY, float& maxY, float& minZ, float& maxZ);
+ //! Returns the position vector of the tile sphere.
+ float* _getPosition();
+ //! Returns the radius of the tile sphere.
+ float _getRadius();
+ //! Returns the contained subset and its size.
+ void _getSubset(float** &subset, int &size);
+ //! True if this sphere has sub spheres.
+ bool _hasSubSpheres();
+
+ //! Returns a preciser sub sphere, which is closest to this sphere.
+ //! The method will return NULL, if there is no closer sphere then \c distance
+ //! or if the closest sphere was already visited.
+ TileSphere* _getPreciserSphere(TileSphere* referenceSphere, float distance);
+
+ //! Returns the euclidean distance between two spheres. It returns not the distance between the
+ //! both position vectors, but the distance between the sphere hulls.
+ float _distance(TileSphere* tileSphere1, TileSphere* tileSphere2);
+
+ //! Returns the euclidean distance between two points.
+ inline float _distance(register float* point1, register float* point2) {
+ register float d1 = * point1 - * point2;
+ register float d2 = *(point1 + 1) - *(point2 + 1);
+ register float d3 = *(point1 + 2) - *(point2 + 2);
+ return sqrtf(d1*d1 + d2*d2 + d3*d3);
+ }
+
+ //! Returns the distance between two points without calculating the square root.
+ inline float _fastDistance(register float* point1, register float* point2) {
+ register float d1 = * point1 - * point2;
+ register float d2 = *(point1 + 1) - *(point2 + 1);
+ register float d3 = *(point1 + 2) - *(point2 + 2);
+ return (d1*d1 + d2*d2 + d3*d3);
+ }
+};
+
+
+ML_END_NAMESPACE
+
+#endif // __TileSphere_H
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.cpp
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.cpp (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.cpp 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,148 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! TileSphereHashTable is used in the classes \c MinimalDistancePointClouds and \c TileSphere.
+//! It defines a single sub sphere for an efficient nearest pair search algorithm.
+//! TileSphere will generate its own sub spheres if necessary
+/*!
+// \file TileSphereHashTable.cpp
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+#include "TileSphereHashTable.h"
+#include "TileSphere.h"
+
+
+ML_START_NAMESPACE
+
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphereHashTable::TileSphereHashTable()
+{
+ ML_TRACE_IN("TileSphereHashTable::TileSphereHashTable()");
+
+ _hashSize = 1103; // prime number
+ _hashTable = NULL;
+ ML_CHECK_NEW(_hashTable, std::vector<MLuint32>[_hashSize]);
+
+ _addedPairs =
+ _hits =
+ _misses = 0;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+TileSphereHashTable::~TileSphereHashTable()
+{
+ ML_TRACE_IN("TileSphereHashTable::~TileSphereHashTable() ");
+
+ ML_DELETE_ARR(_hashTable);
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphereHashTable::addPair(TileSphere* tileSphere1, TileSphere* tileSphere2)
+{
+ ML_TRACE_IN("void TileSphereHashTable::addPair(TileSphere* tileSphere1, TileSphere* tileSphere2) ");
+
+ MLuint32 tmpIndex1 = tileSphere1->getSphereIndex();
+ MLuint32 tmpIndex2 = tileSphere2->getSphereIndex();
+
+ // if one of the indices is larger than 16bit, the entry value is no longer unique
+ if ( (tmpIndex1 <= ML_UINT16_MAX) && (tmpIndex2 <= ML_UINT16_MAX) ){
+ MLuint16 index1 = (MLuint16)tileSphere1->getSphereIndex();
+ MLuint16 index2 = (MLuint16)tileSphere2->getSphereIndex();
+
+ int hashKey = 0;
+ MLuint32 entry = 0;
+
+ // Always smaller index first.
+ // Concatenate both indices to one entry value.
+ if (index1 < index2){
+ entry = (index1 << 16) | index2;
+ } else{
+ entry = (index2 << 16) | index1;
+ }
+
+ hashKey = (int)entry % _hashSize;
+
+ _hashTable[hashKey].push_back(entry);
+
+ _addedPairs++;
+ }
+ else {
+ std::cout << "TileSphereHashTable::addPair: one of the indices was greater than ML_UINT16_MAX" << std::endl;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+bool TileSphereHashTable::existPair(TileSphere* tileSphere1, TileSphere* tileSphere2)
+{
+ ML_TRACE_IN("bool TileSphereHashTable::existPair(TileSphere* tileSphere1, TileSphere* tileSphere2) ");
+
+ MLuint32 tmpIndex1 = tileSphere1->getSphereIndex();
+ MLuint32 tmpIndex2 = tileSphere2->getSphereIndex();
+
+ // if one of the indices is larger than 16bit, the entry value is no longer unique
+ if ( (tmpIndex1 <= ML_UINT16_MAX) && (tmpIndex2 <= ML_UINT16_MAX) ) {
+ MLuint16 index1 = (MLuint16)tileSphere1->getSphereIndex();
+ MLuint16 index2 = (MLuint16)tileSphere2->getSphereIndex();
+
+ int hashKey = 0;
+ MLuint32 entry = 0;
+
+ // Always smaller index first.
+ // Concatenate both indices to one entry value.
+ if (index1 < index2){
+ entry = (index1 << 16) | index2;
+ } else{
+ entry = (index2 << 16) | index1;
+ }
+
+ hashKey = (int)entry % _hashSize;
+
+ std::vector<MLuint32>::iterator i;
+
+ for(i = _hashTable[hashKey].begin(); i != _hashTable[hashKey].end(); i++) {
+ if (*i == entry) {
+ _hits++;
+ return true;
+ }
+ }
+ _misses++;
+ }
+ else {
+ std::cout << "TileSphereHashTable::existPair: one of the indices was greater than ML_UINT16_MAX" << std::endl;
+ }
+
+ return false;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+void TileSphereHashTable::getStatistics(int &addedPairs, int &hits, int &misses)
+{
+ ML_TRACE_IN("void TileSphereHashTable::getStatistics(int &addedPairs, int &hits, int &misses) ");
+
+ addedPairs = _addedPairs;
+ hits = _hits;
+ misses = _misses;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+
+ML_END_NAMESPACE
+
Added: trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.h
===================================================================
--- trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.h (rev 0)
+++ trunk/Community/General/Sources/ML/MLCSOCommunityModules/MinimalDistancePointClouds/TileSphereHashTable.h 2009-06-24 07:27:57 UTC (rev 140)
@@ -0,0 +1,74 @@
+//----------------------------------------------------------------------------------
+//
+// Copyright 2001, MeVis gGmbH
+// ALL RIGHTS RESERVED
+//
+// THE CONTENT OF THIS WORK CONTAINS CONFIDENTIAL AND PROPRIETARY
+// INFORMATION OF MEVIS GGMBH. ANY DUPLICATION, MODIFICATION,
+// DISTRIBUTION, OR DISCLOSURE IN ANY FORM, IN WHOLE, OR IN PART, IS STRICTLY
+// PROHIBITED WITHOUT THE PRIOR EXPRESS WRITTEN PERMISSION OF MEVIS GGMBH
+//
+//----------------------------------------------------------------------------------
+//! TileSphereHashTable is used in the classes \c MinimalDistancePointClouds and \c TileSphere.
+//! The TileSphereHashTable is the underlying data structure for
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+/*!
+// \file TileSphereHashTable.h
+// \author Christian Tietjen, Olaf Konrad, last changed by $Author: okonrad $
+// \date 11/2005
+*/
+//----------------------------------------------------------------------------------
+
+
+#ifndef __TileSphereHashTable_H
+#define __TileSphereHashTable_H
+
+#include "../MLCSOCommunityModulesDefs.h"
+
+
+ML_START_NAMESPACE
+
+// Forward declaration
+class TileSphere;
+
+
+//! TileSphereHashTable is used in the classes \c MinimalDistancePointClouds and \c TileSphere.
+//! The TileSphereHashTable is the underlying data structure for
+//! a fast nearest pair search algorithm described by Sean Quinlan
+//! in 'Efficient Distance Computation between Non-Convex Objects'.
+class TileSphereHashTable
+{
+
+public:
+
+ //! Constructor.
+ TileSphereHashTable();
+ //! Destructor.
+ virtual ~TileSphereHashTable();
+
+ //! Adds a pair of spheres into the hash table.
+ void addPair(TileSphere* tileSphere1, TileSphere* tileSphere2);
+ //! Checks whether the given pair exists or not.
+ bool existPair(TileSphere* tileSphere1, TileSphere* tileSphere2);
+
+ //! Hash table statistics.
+ void getStatistics(int &addedPairs, int &hits, int &misses);
+
+
+private:
+
+ //! Size of the hash table.
+ int _hashSi...
[truncated message content] |
