Closest body

[Julio Jerez]

Code: Select all

Edit: This code is concurrency unsafe? I guess so cos it just crashed.
I guess I will try to run it after NewtonUpdate on the same thread.
Does it need NewtonCriticalSection?

Oh I forget about that, the code will be unsafe if runn in parealler wit a newton update,
can you test it with out mutiothreaded just to see hwo it works, it is eassy to make thread safe.

I can make Newton thread safe eassilly, by making the memory manager thread safe, bu fist see if it works for you.

[KingSnail]

OK I understand about the algorithm now.

I have it running after the NewtonUpdate in the same thread as NewtonUpdate now.

It crashes because of something else now (I posted screenshot last post).
typename dgList<T>::dgListNode *dgList<T>::GetFirst() const <---- inside there.

[Julio Jerez]

In the image it say facemap node is NULL, tha should no happens.
the algorithm needs three points or more,

if teh convehull return wa smade it sodul no crash, at least I never see it crashing

[KingSnail]

I have 5 points added to the array, strange.

[Julio Jerez]

5 point will definitlly have a convex hull, onless thay are collinear

can you copy those point and test in the project file that I send you?

[KingSnail]

Yes ofcourse

[KingSnail]

The problem I have it seems is that this code crashes if points do not make a successful convex hull.
It works fine with the points that you gave but when I try to add my own points it cant make convex hull and simply crashes.
Is there a minimum amount of points that are required to build a convex hull to prevent crashes?

Sorry its been almost a year since I worked with this code.

[Julio Jerez]

not that function should not crash as long as the points do not fall onto a straight line. That funtion is very robust, almost uncrashable.
The reason for that is that the funtion in 3d is the equivalente to when in 2d you have two points and you want to make a line,
or if you have three points and you want to make a triangle, of 4 points and you wna to make a tetrahedrum, and so on.
N points always, and I mean always have a convex hull.
A proof of that is thta you can imagine teh set of point in teh real world you cna always wrapen then with a cheat of shimwrap.
the shrimwrap is teh convex hull.
In fact that funtion is the same function that teh engine use to make convex hulls.
If it crash the must be a unrelated bug some where.

[KingSnail]

So if I have 1000 players and maybe they could all stand in a line, that could make this function crash.
Is there a way to make this function be self aware if its not a line then instead of making convex hull
then do another algorithm?

Or for example 3 players stand on exactly the same spot, that cant make a convex hull right, so
instead it could do linear search? or something?

I also notice that the function crashes with less than 4 points

[Julio Jerez]

I find very unlikly that so many point will fall o a stright line. but even if they did I do not think it will crash, it will return NULL.
maybe the code after that is trying to dereference NULL.

if you have two or tree, points standing on teh same place the function will return NULL.
but those are special cases, and if it happen you kow that any oteh point is the closest
Believe me that is the most soffisticated method you can implement for what you want, it is among the fastesr too. and it provid perfect reliably solution.
That algorithm is use on top of the line artificial inteligence for path finding and a whole bunch of other things.
I do no if you seen it, by is some comercial and movies every time the show a computer drigram of some military facility, you see the net of point coneceted by line forming a convex hulls.
those diagram are Voronoi digrams. ther alway thonk is make peopel that teh techonolog is advance.
Even optimizing compiler uses that algorim in higher dimensions to determine from a set of instruction which set in the most optimal accortind to some CPU cost.

can I see how you wrote it?

[KingSnail]

Code: Select all

#include "stdafx.h"
#include "ClosestNeighborg.h"

#define PLAYERS_COUNT 4
#define CLOSE_PLAYER_OUTPUT_COUNT 1

int _tmain(int argc, _TCHAR* argv[])
{
   dgMemoryAllocator allocator;

   dgInt32 count = 0;
   dgBigVector points[PLAYERS_COUNT];

   // populated the map with point representing the entities
   while (count < sizeof (points)/ sizeof (points[0])) {
      // make sure no point is duplicated
      dgBigVector p (100.0f * (float (rand()) / RAND_MAX - 1.0f), 100.0f * (float (rand()) / RAND_MAX - 1.0f), 0, 0);
      int i = 0;
      for (; i < count; i ++) {
         dgBigVector dist (p - points[i]);
         if ((dist % dist) < 1.0e-6) {
            break;
         }
      }
      if (i == count) {
         points[count] = p;
         count ++;
      }
   }

   int testc = 0;

   // how to use it
   ClosestNeighborg closertNighborg (&allocator, points, count);
   for (int i = 0; i < CLOSE_PLAYER_OUTPUT_COUNT; i ++) {
      int arrayOut[CLOSE_PLAYER_OUTPUT_COUNT];
      int index = rand () % (sizeof (points) / sizeof (points[0]));
      int count = closertNighborg.GetClosestPoints (index, arrayOut, sizeof (arrayOut) / sizeof (arrayOut[0]));

     testc = count;
      //count *=1;
   }

   return 0;
}

Code: Select all

#pragma once

#include "stdafx.h"
#include "dg.h"

class ClosestNeighborg: public dgConvexHull3d
{
   class FaceList: public dgList<dgConvexHull3d::dgListNode*>
   {
      public:
      FaceList (dgMemoryAllocator* const allocator)
         :dgList<dgConvexHull3d::dgListNode*>(allocator)
      {
      }
   };

   class FaceMap: public dgTree<FaceList, int>
   {
      public:
      FaceMap (dgMemoryAllocator* const allocator)
         :dgTree<FaceList, int>(allocator)
      {
      }
   };

   public:
   ClosestNeighborg(dgMemoryAllocator* const allocator, dgBigVector* const points, dgInt32 count)
      :dgConvexHull3d (allocator)
      ,m_lru(0)
      ,m_faceMap (allocator)
      ,m_mask(256, allocator)
   {
      for (dgInt32 i = 0; i < count; i ++) {
         points[i].m_z = points[i].m_x * points[i].m_x + points[i].m_y * points[i].m_y;
         points[i].m_w = i;
      }
      m_mask[count - 1] = 0;
      memset (&m_mask[0], 0, sizeof (unsigned));

      BuildHull (&points[0].m_x, sizeof (dgBigVector), count, 0.0, 0x7fffffff);
   }

   int GetClosestPoints (int index, int* const arrayOut, int maxCount)
   {
      FaceMap::dgTreeNode* const faceMapNode = m_faceMap.Find(index);
      _ASSERTE (faceMapNode);

      int count = 0;
      m_lru ++;
      unsigned* markIndex = &m_mask[0];
      markIndex[index] = m_lru;
      FaceList& faceList = faceMapNode->GetInfo();     
      for (FaceList::dgListNode* faceNode = faceList.GetFirst(); faceNode; faceNode = faceNode->GetNext()) {
         dgConvexHull3DFace* const face = &faceNode->GetInfo()->GetInfo();
         if (IsLowerHull (face)) {
            for (int i = 0; i < 3; i ++) {
               int k = face->m_index[i];
               const dgBigVector& vertex = GetVertex(k);
               k = int (vertex.m_w);
               if (markIndex[k] != m_lru) {
                  arrayOut[count] = k;
                  markIndex[k] = m_lru;
                  count ++;
                  _ASSERTE (count < maxCount);

               }
            }
         }
      }
      return count;
   }

   // for incremental update wne a point move, but let us see hwo tehis work first.
   void AddPoint(int point)
   {
   }

   void RemovePoint(int point)
   {

   }

   void DebugRender()
   {
      for (ClosestNeighborg::dgListNode* node = GetFirst(); node; node = node->GetNext()) {
         dgConvexHull3DFace* const face = &node->GetInfo();
         if (IsLowerHull (face)) {
            dgVector vertex0 (GetVertex(face->m_index[0]));
            dgVector vertex1 (GetVertex(face->m_index[1]));
            dgVector vertex2 (GetVertex(face->m_index[2]));

            vertex0.m_z = 0.0f;
            vertex1.m_z = 0.0f;
            vertex2.m_z = 0.0f;

            // Render this triangle (vertex0, vertex1, vertex2);
         }
      }
   }

   private:
   virtual dgListNode* AddFace (dgInt32 i0, dgInt32 i1, dgInt32 i2)
   {
      dgListNode* const face = dgConvexHull3d::AddFace(i0, i1, i2);

      const dgBigVector& vertex0 = GetVertex(i0);
      const dgBigVector& vertex1 = GetVertex(i1);
      const dgBigVector& vertex2 = GetVertex(i2);

      int index[3];
      index[0] = int (vertex0.m_w);
      index[1] = int (vertex1.m_w);
      index[2] = int (vertex2.m_w);
      for (int i = 0; i < 3; i ++) {
         FaceMap::dgTreeNode* node = m_faceMap.Find(index[i]);
         if (!node) {
            FaceList faceList (GetAllocator());
            node = m_faceMap.Insert(faceList, index[i]);
         }
         FaceList& faceList = node->GetInfo();
         faceList.Append(face);
      }
      return face;
   }

   virtual void DeleteFace (dgListNode* const node)
   {
      dgConvexHull3DFace* const face = &node->GetInfo();

      for (int i = 0; i < 3; i ++) {
         int index = face->m_index[i];
         const dgBigVector& vertex = GetVertex(index);
         index = int (vertex.m_w);

         FaceMap::dgTreeNode* const mapNode = m_faceMap.Find(index);
         _ASSERTE (mapNode);

         FaceList& faceList = mapNode->GetInfo();
         for (FaceList::dgListNode* faceNode = faceList.GetFirst(); faceNode; faceNode = faceNode->GetNext()) {
            if (faceNode->GetInfo() == node) {
               faceList.Remove(faceNode);
               _ASSERTE (faceList.GetCount());
               break;
            }
         }
      }

      dgConvexHull3d::DeleteFace(node);
   }

   bool IsLowerHull (dgConvexHull3DFace* const face) const
   {
      const dgBigVector& vertex0 = GetVertex(face->m_index[0]);
      const dgBigVector& vertex1 = GetVertex(face->m_index[1]);
      const dgBigVector& vertex2 = GetVertex(face->m_index[2]);

      dgBigVector e0 (vertex1 - vertex0);
      dgBigVector e1 (vertex2 - vertex0);
      dgBigVector n (e0 * e1);
      return (n.m_z < 0.0f);
   }

   int m_lru;
   FaceMap m_faceMap;
   dgArray<unsigned> m_mask;
};

That work but as soon as I
#define PLAYERS_COUNT 3
instead of 4
then it crash

[Julio Jerez]

can you show me the line where is crashes? It is most likely an esassy to fix bug.

[KingSnail]

int count = closertNighborg.GetClosestPoints (index, arrayOut, sizeof (arrayOut) / sizeof (arrayOut[0]));

It crashes there, inside dglist where it tries to 'return m_first;'
Access violation

[Julio Jerez]

Yet it is what I though, if point count is 3 or less, then the convex hull has zero volume.what it means is that all points are closest points to ani other point.
You only have to do this.

Code: Select all

int GetClosestPoints (int index, int* const arrayOut, int maxCount)
{
  FaceMap::dgTreeNode* const faceMapNode = m_faceMap.Find(index);
  _ASSERTE (faceMapNode);

  int count = 0;
  m_lru ++;
  unsigned* markIndex = &m_mask[0];
  markIndex[index] = m_lru;
  FaceList& faceList = faceMapNode->GetInfo();     
  if (faceList.GetCount()) {
     for (FaceList::dgListNode* faceNode = faceList.GetFirst(); faceNode; faceNode = faceNode->GetNext()) {
       dgConvexHull3DFace* const face = &faceNode->GetInfo()->GetInfo();
       if (IsLowerHull (face)) {
         for (int i = 0; i < 3; i ++) {
            int k = face->m_index[i];
            const dgBigVector& vertex = GetVertex(k);
            k = int (vertex.m_w);
            if (markIndex[k] != m_lru) {
              arrayOut[count] = k;
              markIndex[k] = m_lru;
              count ++;
              _ASSERTE (count < maxCount);

            }
         }
       }
     }
  } else {
     // this is a spceial case whe all point are closest
     for (int i =    0; i < GetVertexdCount(); i ++) {
        const dgBigVector& vertex = GetVertex(k);
        k = int (vertex.m_w);
        if (k != index) {
           arrayOut[count] = k;
           count ++;
           _ASSERTE (count < maxCount);
        }
     }
  }
  return count;
}

[KingSnail]

I changed it and it still seems to crash

also k is undefined in this line k = int (vertex.m_w); (second loop)
where should k be defined?

Error 1 error C2065: 'k' : undeclared identifier c:\users\r\desktop\voulge\juliotest\juliotest\ClosestNeighborg.h 74