Changeset 4929 in orxonox.OLD for orxonox/trunk/src/lib

Timestamp:

Jul 21, 2005, 6:07:23 PM (19 years ago)

Author:

patrick

Message:

orxonox/trunk: implemented a point in triangle function

Location:

orxonox/trunk/src/lib/graphics/spatial_separation

Files:

• quadtree.cc (modified) (2 diffs)
• quadtree.h (modified) (1 diff)
• quadtree_node.cc (modified) (1 diff)
• quadtree_node.h (modified) (2 diffs)

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.cc

@@ -167 +167 @@
   int j = (int)(v.z / quadLength);
 
-  /* check if object is still inside the terrain */
+  /* check if object is still inside the terrain - this check is not complete @todo check all 4 bounds */
   if( i < this->maxIndex && j < this->maxIndex)
     this->nodes[i + j * this->maxIndex]->includesPoint(position);
@@ -176 +176 @@
 
 /**
+ *  maps a position to a triangle
+ * @param position the position so look for
+ * @return the triangle
+
+  this function will return the quadtree that contains the position
+ */
+sTriangleExt* Quadtree::getTriangleFromPosition(const Vector& position)
+{
+  QuadtreeNode* q = this->getQuadtreeFromPosition(position);
+  return q->getTriangle(position);
+}
+
+
+/**
  *  draws the debug quadtree boxes around the model
  */

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree.h

@@ -28 +28 @@
 
     QuadtreeNode* getQuadtreeFromPosition(const Vector& position);
+    sTriangleExt* getTriangleFromPosition(const Vector& position);
 
     void drawTree() const;

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree_node.cc

@@ -389 +389 @@
 
 
+sTriangleExt* QuadtreeNode::getTriangle(const Vector& position)
+{
+
+}
+
+bool QuadtreeNode::pointInTriangle(const Vector&p, const Vector& a, const Vector& b, const Vector& c)
+{
+  if( this->sameSide(p, a, b, c) && this->sameSide(p, b, a, c) && sameSide(p, c, a, b))
+    return true;
+  return false;
+  /*
+  function PointInTriangle(p, a,b,c)
+  if SameSide(p,a, b,c) and SameSide(p,b, a,c)
+  and SameSide(p,c, a,b) then return true
+  else return false
+  */
+}
+
+
+bool QuadtreeNode::sameSide(const Vector& p1, const Vector&p2, const Vector& a, const Vector& b)
+{
+  Vector cp1 = (b - a).cross(p1 - a);
+  Vector cp2 = (b - a).cross(p2 - a);
+
+  if( unlikely(cp1.dot(cp2) >= 0)) return true;
+  return false;
+}
+
+
 /**
  *  draws all the debug quadtree squares

orxonox/trunk/src/lib/graphics/spatial_separation/quadtree_node.h

@@ -37 +37 @@
     void buildHashTable(QuadtreeNode** nodeList, int* index);
     bool includesPoint(const Vector& v);
+    sTriangleExt* getTriangle(const Vector& position);
     float getHeight(const Vector& position);
     inline Rectangle* getDimension() { return this->pDimension; }
@@ -51 +52 @@
     Rectangle* getDimFromModel();
 
+    bool sameSide(const Vector& p1, const Vector&p2, const Vector& a, const Vector& b);
+    bool pointInTriangle(const Vector&p, const Vector& a, const Vector& b, const Vector& c);
 
   protected: