Menu
▾
▴
[Hgengine-cvs] SF.net SVN: hgengine:[555] Mercury2/src
|
From: <axl...@us...> - 2009-10-10 22:21:55
|
Revision: 555
http://hgengine.svn.sourceforge.net/hgengine/?rev=555&view=rev
Author: axlecrusher
Date: 2009-10-10 22:21:49 +0000 (Sat, 10 Oct 2009)
Log Message:
-----------
add spatial hash and triangle class
Added Paths:
-----------
Mercury2/src/DataStructures/
Mercury2/src/DataStructures/SpatialHash.h
Mercury2/src/DataTypes/
Mercury2/src/DataTypes/MTriangle.cpp
Mercury2/src/DataTypes/MTriangle.h
Added: Mercury2/src/DataStructures/SpatialHash.h
===================================================================
--- Mercury2/src/DataStructures/SpatialHash.h (rev 0)
+++ Mercury2/src/DataStructures/SpatialHash.h 2009-10-10 22:21:49 UTC (rev 555)
@@ -0,0 +1,127 @@
+#ifndef SPATIALHASH_H
+#define SPATIALHASH_H
+
+#include <stdint.h>
+#include <list>
+#include <math.h>
+
+template<typename T>
+class SpatialHash
+{
+ public:
+ SpatialHash()
+ :m_hashTable(NULL), m_spacing(1.0f)
+ {
+ m_xSize = m_ySize = m_zSize = 0;
+ }
+
+ ~SpatialHash()
+ {
+ DeleteHash();
+ }
+
+ void Allocate(uint32_t xmax, uint32_t ymax, uint32_t zmax, uint32_t spacing)
+ {
+ DeleteHash();
+
+ m_spacing = spacing;
+
+ m_xSize = (abs(xmax)/m_spacing) + 1;
+ m_ySize = (abs(ymax)/m_spacing) + 1;
+ m_zSize = (abs(zmax)/m_spacing) + 1;
+
+ uint32_t size = m_xSize*m_ySize*m_zSize;
+ m_hashTable = new std::list<T>[size];
+ }
+
+ void Insert(float x, float y, float z, const T& d)
+ {
+ unsigned int ix = abs(x) / m_spacing;
+ unsigned int iy = abs(y) / m_spacing;
+ unsigned int iz = abs(z) / m_spacing;
+
+ if (ix >= m_xSize || iy >= m_ySize || iz >= m_zSize)
+ {
+ printf("%d >= %d || %d >= %d || %d >= %d\n", ix, m_xSize, iy, m_ySize, iz, m_zSize);
+ return;
+ }
+
+ //check for and skip duplicate
+ std::list<T>& cell = m_hashTable[ Index( ix, iy, iz ) ];
+ typename std::list<T>::iterator i = cell.begin();
+ for (;i != cell.end(); ++i) if (*i == d) return;
+
+ cell.push_back( d );
+// printf("added at %d %d %d\n", ix, iy, iz);
+ }
+
+ std::list<T> FindByXY(float x, float y)
+ {
+ int ix = x / m_spacing;
+ int iy = y / m_spacing;
+
+ std::list<T> r;
+
+ for (uint32_t iz = 0; iz < m_zSize; ++iz)
+ CopyIntoList(m_hashTable[Index(ix, iy, iz)], r);
+
+ return r;
+ }
+ private:
+ inline uint32_t Index(uint32_t x, uint32_t y, uint32_t z)
+ {
+ return x + (m_xSize * y) + (m_xSize * m_ySize * z);
+ }
+
+ void DeleteHash()
+ {
+ if (m_hashTable) delete[] m_hashTable;
+ m_spacing = 1;
+ m_xSize = m_ySize = m_zSize = 0;
+ }
+
+ void CopyIntoList(std::list<T>& in, std::list<T>& r)
+ {
+ typename std::list<T>::iterator i = in.begin();
+ for (;i != in.end(); ++i) r.push_back(*i);
+ }
+
+ std::list<T>* m_hashTable;
+ uint32_t m_spacing;
+ uint32_t m_xSize, m_ySize, m_zSize;
+};
+
+#endif
+
+
+/****************************************************************************
+ * Copyright (C) 2009 by Joshua Allen *
+ * *
+ * *
+ * All rights reserved. *
+ * *
+ * Redistribution and use in source and binary forms, with or without *
+ * modification, are permitted provided that the following conditions *
+ * are met: *
+ * * Redistributions of source code must retain the above copyright *
+ * notice, this list of conditions and the following disclaimer. *
+ * * Redistributions in binary form must reproduce the above *
+ * copyright notice, this list of conditions and the following *
+ * disclaimer in the documentation and/or other materials provided *
+ * with the distribution. *
+ * * Neither the name of the Mercury Engine nor the names of its *
+ * contributors may be used to endorse or promote products derived *
+ * from this software without specific prior written permission. *
+ * *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT *
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR *
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT *
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE *
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
+ ***************************************************************************/
Added: Mercury2/src/DataTypes/MTriangle.cpp
===================================================================
--- Mercury2/src/DataTypes/MTriangle.cpp (rev 0)
+++ Mercury2/src/DataTypes/MTriangle.cpp 2009-10-10 22:21:49 UTC (rev 555)
@@ -0,0 +1,96 @@
+#include <MTriangle.h>
+
+#include <stdio.h>
+
+MTriangle::MTriangle()
+{
+}
+
+MTriangle::MTriangle(const MercuryVertex a, const MercuryVertex& b, const MercuryVertex& c)
+{
+ m_verts[0] = a;
+ m_verts[1] = b;
+ m_verts[2] = c;
+}
+
+MercuryVertex MTriangle::Barycentric(const MercuryVertex& p)
+{
+ MercuryVector v[3];
+ v[0] = m_verts[1] - m_verts[0];
+ v[1] = m_verts[2] - m_verts[0];
+ v[2] = p - m_verts[0];
+
+ float dp[5];
+ dp[0] = v[0].DotProduct(v[0]);
+ dp[1] = v[0].DotProduct(v[1]);
+ dp[2] = v[0].DotProduct(v[2]);
+ dp[3] = v[1].DotProduct(v[1]);
+ dp[4] = v[1].DotProduct(v[2]);
+
+ // Compute barycentric coordinates
+ float invDenom = 1 / (dp[0] * dp[3] - dp[1] * dp[1]);
+ float ru = (dp[3] * dp[2] - dp[1] * dp[4]) * invDenom;
+ float rv = (dp[0] * dp[4] - dp[1] * dp[2]) * invDenom;
+
+ return MercuryVertex(ru, rv, 1-(ru+rv));
+}
+
+bool MTriangle::IsInTriangle(const MercuryVertex& p)
+{
+ MercuryVertex v = Barycentric(p);
+
+ //no edges
+// return (v.GetX() > 0) && (v.GetY() > 0) && (v.GetX() + v.GetY() < 1);
+
+ //includes edges
+ return (v.GetX() >= 0) && (v.GetY() >= 0) && (v.GetX() + v.GetY() <= 1);
+}
+
+float MTriangle::Area()
+{
+ MercuryVector v[2];
+ v[0] = m_verts[1] - m_verts[0];
+ v[1] = m_verts[2] - m_verts[0];
+ MercuryVector r( v[0].CrossProduct( v[1] ) );
+ return r.Length() * 0.5;
+}
+
+bool MTriangle::operator == (const MTriangle& rhs)
+{
+ if (m_verts[0] != rhs.m_verts[0]) return false;
+ if (m_verts[1] != rhs.m_verts[1]) return false;
+ if (m_verts[2] != rhs.m_verts[2]) return false;
+ return true;
+}
+
+/****************************************************************************
+ * Copyright (C) 2009 by Joshua Allen *
+ * *
+ * *
+ * All rights reserved. *
+ * *
+ * Redistribution and use in source and binary forms, with or without *
+ * modification, are permitted provided that the following conditions *
+ * are met: *
+ * * Redistributions of source code must retain the above copyright *
+ * notice, this list of conditions and the following disclaimer. *
+ * * Redistributions in binary form must reproduce the above *
+ * copyright notice, this list of conditions and the following *
+ * disclaimer in the documentation and/or other materials provided *
+ * with the distribution. *
+ * * Neither the name of the Mercury Engine nor the names of its *
+ * contributors may be used to endorse or promote products derived *
+ * from this software without specific prior written permission. *
+ * *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT *
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR *
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT *
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE *
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
+ ***************************************************************************/
Added: Mercury2/src/DataTypes/MTriangle.h
===================================================================
--- Mercury2/src/DataTypes/MTriangle.h (rev 0)
+++ Mercury2/src/DataTypes/MTriangle.h 2009-10-10 22:21:49 UTC (rev 555)
@@ -0,0 +1,55 @@
+#ifndef MTRIANGLE_H
+#define MTRIANGLE_H
+
+#include <MercuryVertex.h>
+
+class MTriangle
+{
+ public:
+ MTriangle();
+ MTriangle(const MercuryVertex a, const MercuryVertex& b, const MercuryVertex& c);
+
+ MercuryVertex Barycentric(const MercuryVertex& p);
+ bool IsInTriangle( const MercuryVertex& p );
+
+ float Area();
+
+ bool operator == (const MTriangle& rhs);
+ private:
+
+ MercuryVertex m_verts[3];
+};
+
+#endif
+
+/****************************************************************************
+ * Copyright (C) 2009 by Joshua Allen *
+ * *
+ * *
+ * All rights reserved. *
+ * *
+ * Redistribution and use in source and binary forms, with or without *
+ * modification, are permitted provided that the following conditions *
+ * are met: *
+ * * Redistributions of source code must retain the above copyright *
+ * notice, this list of conditions and the following disclaimer. *
+ * * Redistributions in binary form must reproduce the above *
+ * copyright notice, this list of conditions and the following *
+ * disclaimer in the documentation and/or other materials provided *
+ * with the distribution. *
+ * * Neither the name of the Mercury Engine nor the names of its *
+ * contributors may be used to endorse or promote products derived *
+ * from this software without specific prior written permission. *
+ * *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT *
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR *
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT *
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE *
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
+ ***************************************************************************/
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
