//-----------------------------------------------------------------------------
// Torque Game Engine 
// Copyright (C) GarageGames.com, Inc.
//-----------------------------------------------------------------------------

#include "map2dif/morianUtil.h"
#include "map2dif/editGeometry.h"
#include "platform/platformAssert.h"
#include "math/mMath.h"
#include "map2dif/csgBrush.h"

// Global brush arena...
BrushArena gBrushArena(1024);



S32 euclidGCD(S32 one, S32 two)
{
   AssertFatal(one > 0 && two > 0, "Error");

   S32 m = one >= two ? one : two;
   S32 n = one >= two ? two : one;

   while (true) {
      S32 test = m % n;
      if (test == 0)
         return n;

      m = n;
      n = test;
   }
}

S32 planeGCD(S32 x, S32 y, S32 z, S32 d)
{
   S32* pNonZero = NULL;
   if (x != 0)      pNonZero = &x;
   else if (y != 0) pNonZero = &y;
   else if (z != 0) pNonZero = &z;
   else if (d != 0) pNonZero = &d;
   else {
      AssertFatal(false, "Cannot pass all zero to GCD!");
      return 1;
   }

   if (x == 0) return planeGCD(*pNonZero, y, z, d);
   if (y == 0) return planeGCD(x, *pNonZero, z, d);
   if (z == 0) return planeGCD(x, y, *pNonZero, d);
   if (d == 0) return planeGCD(x, y, z, *pNonZero);

   if (x < 0) x = -x;
   if (y < 0) y = -y;
   if (z < 0) z = -z;
   if (d < 0) d = -d;

   // Do a Euclid on these...
   return euclidGCD(euclidGCD(euclidGCD(x, y), z), d);
}

void dumpWinding(const Winding& winding, const char* prefixString)
{
   for (U32 i = 0; i < winding.numIndices; i++) {
      const Point3D& rPoint = gWorkingGeometry->getPoint(winding.indices[i]);
      dPrintf("%s(%d) %lg, %lg, %lg\n", prefixString, winding.indices[i], rPoint.x, rPoint.y, rPoint.z);
   }
}

//------------------------------------------------------------------------------
F64 getWindingSurfaceArea(const Winding& rWinding, U32 planeEQIndex)
{
   // DMMTODO poly area...
   Point3D areaNormal(0, 0, 0);
   for (U32 i = 0; i < rWinding.numIndices; i++) {
      U32 j = (i + 1) % rWinding.numIndices;

      Point3D temp;
      mCross(gWorkingGeometry->getPoint(rWinding.indices[i]),
             gWorkingGeometry->getPoint(rWinding.indices[j]), &temp);

      areaNormal += temp;
   }

   F64 area = mDot(gWorkingGeometry->getPlaneEQ(planeEQIndex).normal, areaNormal);
   if (area < 0.0)
      area *= -0.5;
   else
      area *= 0.5;

   return area;
}

//------------------------------------------------------------------------------
// Simple in-place clipper.  Should be all that's required...
//
bool clipWindingToPlaneFront(Winding* winding, const PlaneEQ& rClipPlane)
{
   U32 start;
   for (start = 0; start < winding->numIndices; start++) {
      const Point3D& rPoint = gWorkingGeometry->getPoint(winding->indices[start]);
      if (rClipPlane.whichSide(rPoint) == PlaneFront)
         break;
   }

   if (start == winding->numIndices) {
      winding->numIndices = 0;
      return true;
   }

   U32 finalIndices[MaxWindingPoints];
   U32 numFinalIndices = 0;

   U32 baseStart = start;
   U32 end       = (start + 1) % winding->numIndices;

   bool modified = false;
   while (end != baseStart) {
      const Point3D& rStartPoint = gWorkingGeometry->getPoint(winding->indices[start]);
      const Point3D& rEndPoint   = gWorkingGeometry->getPoint(winding->indices[end]);

      PlaneSide fSide = rClipPlane.whichSide(rStartPoint);
      PlaneSide eSide = rClipPlane.whichSide(rEndPoint);

      S32 code = fSide * 3 + eSide;
      switch (code) {
        case 4:   // f f
        case 3:   // f o
        case 1:   // o f
        case 0:   // o o
         // No Clipping required
         finalIndices[numFinalIndices++] = winding->indices[start];
         start = end;
         end   = (end + 1) % winding->numIndices;
         break;


        case 2: { // f b
            // In this case, we emit the front point, Insert the intersection,
            //  and advancing to point to first point that is in front or on...
            //
            finalIndices[numFinalIndices++] = winding->indices[start];

            Point3D vector = rEndPoint - rStartPoint;
            F64 t = -(rClipPlane.distanceToPlane(rStartPoint) / mDot(rClipPlane.normal, vector));
            
            Point3D intersection = rStartPoint + (vector * t);
            AssertFatal(rClipPlane.whichSide(intersection) == PlaneOn,
                        "CSGPlane::clipWindingToPlaneFront: error in computing intersection");
            finalIndices[numFinalIndices++] = gWorkingGeometry->insertPoint(intersection);

            U32 endSeek = (end + 1) % winding->numIndices;
            while (rClipPlane.whichSide(gWorkingGeometry->getPoint(winding->indices[endSeek])) == PlaneBack)
               endSeek = (endSeek + 1) % winding->numIndices;

            PlaneSide esSide = rClipPlane.whichSide(gWorkingGeometry->getPoint(winding->indices[endSeek]));
            if (esSide == PlaneFront) {
               end   = endSeek;
               start = (end + (winding->numIndices - 1)) % winding->numIndices;

               const Point3D& rNewStartPoint = gWorkingGeometry->getPoint(winding->indices[start]);
               const Point3D& rNewEndPoint   = gWorkingGeometry->getPoint(winding->indices[end]);

               vector = rNewEndPoint - rNewStartPoint;
               t = -(rClipPlane.distanceToPlane(rNewStartPoint) / mDot(rClipPlane.normal, vector));
            
               intersection = rNewStartPoint + (vector * t);
               AssertFatal(rClipPlane.whichSide(intersection) == PlaneOn,
                           "CSGPlane::clipWindingToPlaneFront: error in computing intersection");
            
               winding->indices[start] = gWorkingGeometry->insertPoint(intersection);
               AssertFatal(winding->indices[start] != winding->indices[end], "Error");
            } else {
               start = endSeek;
               end   = (endSeek + 1) % winding->numIndices;
            }
            modified = true;
         }
         break;

        case -1: {// o b
            // In this case, we emit the front point, and advance to point to first
            //  point that is in front or on...
            //
            finalIndices[numFinalIndices++] = winding->indices[start];

            U32 endSeek = (end + 1) % winding->numIndices;
            while (rClipPlane.whichSide(gWorkingGeometry->getPoint(winding->indices[endSeek])) == PlaneBack)
               endSeek = (endSeek + 1) % winding->numIndices;

            PlaneSide esSide = rClipPlane.whichSide(gWorkingGeometry->getPoint(winding->indices[endSeek]));
            if (esSide == PlaneFront) {
               end   = endSeek;
               start = (end + (winding->numIndices - 1)) % winding->numIndices;

               const Point3D& rNewStartPoint = gWorkingGeometry->getPoint(winding->indices[start]);
               const Point3D& rNewEndPoint   = gWorkingGeometry->getPoint(winding->indices[end]);

               Point3D vector = rNewEndPoint - rNewStartPoint;
               F64  t      = -(rClipPlane.distanceToPlane(rNewStartPoint) / mDot(rClipPlane.normal, vector));
            
               Point3D intersection = rNewStartPoint + (vector * t);
               AssertFatal(rClipPlane.whichSide(intersection) == PlaneOn,
                           "CSGPlane::clipWindingToPlaneFront: error in computing intersection");
            
               winding->indices[start] = gWorkingGeometry->insertPoint(intersection);
               AssertFatal(winding->indices[start] != winding->indices[end], "Error");
            } else {
               start = endSeek;
               end   = (endSeek + 1) % winding->numIndices;
            }
            modified = true;
         }
         break;

        case -2:  // b f
        case -3:  // b o
        case -4:  // b b
         // In the algorithm used here, this should never happen...
         AssertISV(false, "CSGPlane::clipWindingToPlaneFront: error in polygon clipper");
         break;

        default:
         AssertFatal(false, "CSGPlane::clipWindingToPlaneFront: bad outcode");
         break;
      }

   }
   
   // Emit the last point.
   AssertFatal(rClipPlane.whichSide(gWorkingGeometry->getPoint(winding->indices[start])) != PlaneBack,
               "CSGPlane::clipWindingToPlaneFront: bad final point in clipper");
   finalIndices[numFinalIndices++] = winding->indices[start];
   AssertFatal(numFinalIndices >= 3, "Error, line out of clip!");

   // Copy the new rWinding, and we're set!
   //
   dMemcpy(winding->indices, finalIndices, numFinalIndices * sizeof(U32));
   winding->numIndices = numFinalIndices;
   AssertISV(winding->numIndices <= MaxWindingPoints,
             avar("Increase maxWindingPoints.  Talk to DMoore (%d, %d)",
                  MaxWindingPoints, numFinalIndices));

   // DEBUG POINT: No colinear points in the winding
   // DEBUG POINT: all points unique in the winding

   return modified;
}


bool clipWindingToPlaneFront(Winding* winding, U32 planeEQIndex)
{
   // DEBUG POINT: winding contains no colinear points...

   const PlaneEQ& rClipPlane = gWorkingGeometry->getPlaneEQ(planeEQIndex);
   return clipWindingToPlaneFront(winding, rClipPlane);
}


U32 windingWhichSide(const Winding& rWinding, U32 windingPlaneIndex, U32 planeIndex)
{
   AssertFatal(rWinding.numIndices > 2, "Error, winding with invalid number of indices...");

   if (gWorkingGeometry->isCoplanar(windingPlaneIndex, planeIndex))
      return PlaneSpecialOn;

   const PlaneEQ& rPlane = gWorkingGeometry->getPlaneEQ(planeIndex);

   U32 retSide = 0;
   for (U32 i = 0; i < rWinding.numIndices; i++) {
      switch (rPlane.whichSide(gWorkingGeometry->getPoint(rWinding.indices[i]))) {
        case PlaneOn:
         retSide |= PlaneSpecialOn;
         break;
        case PlaneFront:
         retSide |= PlaneSpecialFront;
         break;
        case PlaneBack:
         retSide |= PlaneSpecialBack;
         break;
      }
   }

   return retSide;
}

struct EdgeConnection {
   U32 start;
   U32 end;
} boxEdges[] = {
   { 0, 1 },
   { 1, 2 },
   { 2, 3 },
   { 3, 0 },
   { 4, 5 },
   { 5, 6 },
   { 6, 7 },
   { 7, 4 },
   { 3, 7 },
   { 0, 4 },
   { 1, 5 },
   { 2, 6 }
};

void createBoundedWinding(const Point3D& minBound,
                          const Point3D& maxBound,
                          U32         planeEQIndex,
                          Winding*       finalWinding)
{
   Point3D boxPoints[8];
   boxPoints[0].set(minBound.x, minBound.y, minBound.z);
   boxPoints[1].set(maxBound.x, minBound.y, minBound.z);
   boxPoints[2].set(maxBound.x, minBound.y, maxBound.z);
   boxPoints[3].set(minBound.x, minBound.y, maxBound.z);
   boxPoints[4].set(minBound.x, maxBound.y, minBound.z);
   boxPoints[5].set(maxBound.x, maxBound.y, minBound.z);
   boxPoints[6].set(maxBound.x, maxBound.y, maxBound.z);
   boxPoints[7].set(minBound.x, maxBound.y, maxBound.z);

   const PlaneEQ& rPlaneEQ = gWorkingGeometry->getPlaneEQ(planeEQIndex);

   PlaneSide sides[8];
   for (U32 i = 0; i < 8; i++)
      sides[i] = rPlaneEQ.whichSide(boxPoints[i]);

   UniqueVector unorderedWinding;
   for (U32 i = 0; i < 8; i++)
      if (sides[i] == PlaneOn)
         unorderedWinding.pushBackUnique(gWorkingGeometry->insertPoint(boxPoints[i]));

   for (U32 i = 0; i < sizeof(boxEdges) / sizeof(EdgeConnection); i++) {
      if ((sides[boxEdges[i].start] == PlaneBack && sides[boxEdges[i].end]   == PlaneFront) ||
          (sides[boxEdges[i].end]   == PlaneBack && sides[boxEdges[i].start] == PlaneFront)) {
         // Emit the intersection...
         //
         Point3D vector = boxPoints[boxEdges[i].end] - boxPoints[boxEdges[i].start];
         F64 t = -(rPlaneEQ.distanceToPlane(boxPoints[boxEdges[i].start]) / mDot(rPlaneEQ.normal, vector));
         
         Point3D intersection = boxPoints[boxEdges[i].start] + (vector * t);
         unorderedWinding.pushBackUnique(gWorkingGeometry->insertPoint(intersection));
      }
   }

   if (unorderedWinding.size() <= 2) {
      AssertISV(false, "createBoundedWinding: Bad face on brush.  < 3 points.  DMMNOTE: Handle better?");
      finalWinding->numIndices = 0;
      return;
   }

   Vector<U32> modPoints = unorderedWinding;

   // Create a centroid first...
   Point3D centroid(0, 0, 0);
   for (U32 i = 0; i < modPoints.size(); i++)
      centroid += gWorkingGeometry->getPoint(modPoints[i]);
   centroid /= F64(modPoints.size());

   // Ok, we have a centroid.  We (arbitrarily) take the last point, and start from
   //  there...
   finalWinding->indices[0] = modPoints[modPoints.size() - 1];
   finalWinding->numIndices = 1;
   modPoints.erase(modPoints.size() - 1);

   while (modPoints.size() != 0) {
      // Find the largest dot product of a point with a positive facing
      //  cross product.
      //
      F64 maxDot  = -1e10;
      S32 maxIndex = -1;

      const Point3D& currPoint = gWorkingGeometry->getPoint(finalWinding->indices[finalWinding->numIndices - 1]);
      Point3D currVector       = currPoint - centroid;
      currVector.normalize();

      for (U32 i = 0; i < modPoints.size(); i++) {
         const Point3D& testPoint = gWorkingGeometry->getPoint(modPoints[i]);
         Point3D testVector       = testPoint - centroid;
         testVector.normalize();

         Point3D crossVector;
         mCross(currVector, testVector, &crossVector);

         if (mDot(crossVector, rPlaneEQ.normal) < 0.0) {
            // Candidate
            F32 val = mDot(testVector, currVector);
            if (val > maxDot) {
               maxDot   = val;
               maxIndex = i;
            }
         }
      }
      AssertISV(maxIndex != -1, "createBoundedWinding: no point found for winding?");

      finalWinding->indices[finalWinding->numIndices++] = modPoints[maxIndex];
      modPoints.erase(maxIndex);
   }
}


struct FooeyDebug {
   Point3D p;
   F64     d;
};

void splitBrush(CSGBrush*& inBrush,
                U32        planeEQIndex,
                CSGBrush*& outFront,
                CSGBrush*& outBack)
{
   AssertFatal(outFront == NULL && outBack == NULL, "Must be null on entry");

   CSGBrush* pFront = gBrushArena.allocateBrush();
   CSGBrush* pBack  = gBrushArena.allocateBrush();

   pFront->copyBrush(inBrush);
   pBack->copyBrush(inBrush);

   bool regen = false;
   for (S32 i = S32(pFront->mPlanes.size()) - 1; i >= 0; i--) {
      CSGPlane& rPlane = pFront->mPlanes[i];
      
      if (rPlane.planeEQIndex == planeEQIndex ||
          rPlane.planeEQIndex == gWorkingGeometry->getPlaneInverse(planeEQIndex))
         continue;

      if (rPlane.clipWindingToPlaneFront(planeEQIndex) == true) {
         // Winding was modified
         regen = true;

         if (rPlane.winding.numIndices == 0) {
            // Plane is completely gone.  nuke it.
            pFront->mPlanes.erase(i);
         }
      }
   }
   if (pFront->mPlanes.size() <= 1) {
      // Nuke it.
      gBrushArena.freeBrush(pFront);
      pFront = NULL;
   } else {
      // Otherwise, we have a good brush still.  Check to see if we need to add
      //  a plane, and regen, or can just return it...
      if (regen == true) {
         pFront->mPlanes.increment();
         CSGPlane& rPlane = pFront->mPlanes.last();

         rPlane.planeEQIndex = gWorkingGeometry->getPlaneInverse(planeEQIndex);
         rPlane.pTextureName = NULL;
         rPlane.flags        = 0;

         for (U32 i = 0; i < pFront->mPlanes.size(); i++)
            pFront->mPlanes[i].winding.numIndices = 0;

         pFront->selfClip();
      }

      outFront = pFront;
   }

   //-------------------------------------- now do the back...
   regen = false;
   for (S32 i = S32(pBack->mPlanes.size()) - 1; i >= 0; i--) {
      CSGPlane& rPlane = pBack->mPlanes[i];
      
      if (rPlane.planeEQIndex == planeEQIndex ||
          rPlane.planeEQIndex == gWorkingGeometry->getPlaneInverse(planeEQIndex))
         continue;

      if (rPlane.clipWindingToPlaneFront(gWorkingGeometry->getPlaneInverse(planeEQIndex)) == true) {
         // Winding was modified
         regen = true;

         if (rPlane.winding.numIndices == 0) {
            // Plane is completely gone.  nuke it.
            pBack->mPlanes.erase(i);
         }
      }
   }
   if (pBack->mPlanes.size() <= 1) {
      // Nuke it.
      gBrushArena.freeBrush(pBack);
      pBack = NULL;
   } else {
      // Otherwise, we have a good brush still.  Check to see if we need to add
      //  a plane, and regen, or can just return it...
      if (regen == true) {
         pBack->mPlanes.increment();
         CSGPlane& rPlane = pBack->mPlanes.last();

         rPlane.planeEQIndex = planeEQIndex;
         rPlane.pTextureName = NULL;
         rPlane.flags        = 0;

         for (U32 i = 0; i < pBack->mPlanes.size(); i++)
            pBack->mPlanes[i].winding.numIndices = 0;

         pBack->selfClip();
      }

      outBack = pBack;
   }
}


void assessPlane(const U32    testPlane,
                 const CSGBrush& rTestBrush,
                 S32*          numCoplanar,
                 S32*          numTinyWindings,
                 S32*          numSplits,
                 S32*          numFront,
                 S32*          numBack)
{
   for (U32 i = 0; i < rTestBrush.mPlanes.size(); i++) {
      if (gWorkingGeometry->isCoplanar(testPlane, rTestBrush.mPlanes[i].planeEQIndex)) {
         // Easy.  Brush abuts the plane.
         (*numCoplanar)++;
         if (testPlane == rTestBrush.mPlanes[i].planeEQIndex)
            (*numBack)++;
         else
            (*numFront)++;
         return;
      }
   }

   // Ah well, more work...
   const PlaneEQ& rPlane = gWorkingGeometry->getPlaneEQ(testPlane);

   static UniqueVector uniquePoints(64);
   for (U32 i = 0; i < rTestBrush.mPlanes.size(); i++) {
      for (U32 j = 0; j < rTestBrush.mPlanes[i].winding.numIndices; j++)
         uniquePoints.pushBackUnique(rTestBrush.mPlanes[i].winding.indices[j]);
   }

   F64 maxFront = 0.0;
   F64 minBack  = 0.0;

   for (U32 i = 0; i < uniquePoints.size(); i++) {
      const Point3D& rPoint = gWorkingGeometry->getPoint(uniquePoints[i]);

      F64 dist = rPlane.distanceToPlane(rPoint);
      if (dist > maxFront)
         maxFront = dist;
      if (dist < minBack)
         minBack = dist;
   }   

   //AssertFatal(maxFront > gcPlaneDistanceEpsilon || minBack < -gcPlaneDistanceEpsilon,
   //            "This should only happen for coplanar windings...");

   if (maxFront >  gcPlaneDistanceEpsilon)
      (*numFront)++;

   if (minBack  < -gcPlaneDistanceEpsilon)
      (*numBack)++;

   if (maxFront >  gcPlaneDistanceEpsilon &&
       minBack  < -gcPlaneDistanceEpsilon)
      (*numSplits)++;


   if ((maxFront > 0.0 && maxFront < 1.0) ||
       (minBack  < 0.0 && minBack  > -1.0))
      (*numTinyWindings)++;

   // done.
   uniquePoints.clear();
}


//------------------------------------------------------------------------------
bool windingsEquivalent(const Winding& winding1, const Winding& winding2)
{
   if (winding1.numIndices != winding2.numIndices)
      return false;

   U32 oneCurr = 0;
   S32 twoCurr  = -1;
   for (U32 i = 0; i < winding2.numIndices; i++) {
      if (winding2.indices[i] == winding1.indices[0]) {
         twoCurr = i;
         break;
      }
   }
   if (twoCurr == -1)
      return false;

   for (U32 i = 0; i < winding1.numIndices; i++) {
      if (winding1.indices[oneCurr] != winding2.indices[twoCurr])
         return false;

      oneCurr = (oneCurr + 1) % winding1.numIndices;
      twoCurr = (twoCurr + 1) % winding2.numIndices;
   }

   return true;
}


//------------------------------------------------------------------------------
bool canCollapseWinding(const Winding& winding1, const Winding& winding2)
{
   // We are looking for an edge that is backwards in winding2 that is present
   //  in winding1.  Note that this is not a general purpose algorithm, it's
   //  very tailored to the break*Winding function from the BSP.
   //
   AssertFatal(winding1.numIndices >= 3 && winding2.numIndices >= 3, "improper windings");

   // First, lets check the ambient light condition...
   if (winding1.numZoneIds == 0 || winding2.numZoneIds == 0)
      return false;

   if (gWorkingGeometry->mZones[winding1.zoneIds[0]]->ambientLit != 
       gWorkingGeometry->mZones[winding2.zoneIds[0]]->ambientLit)
      return false;

   for (U32 i = 0; i < winding1.numIndices; i++) {
      U32 edgeStart = winding1.indices[(i + 1) % winding1.numIndices];
      U32 edgeEnd   = winding1.indices[i];

      for (U32 j = 0; j < winding2.numIndices; j++) {
         if (winding2.indices[j] == edgeStart &&
             winding2.indices[(j + 1) % winding2.numIndices] == edgeEnd) {
            // Yay!
            return true;
         }
      }
   }

   return false;
}

//------------------------------------------------------------------------------
bool pointsAreColinear(U32 p1, U32 p2, U32 p3)
{
   const Point3D& rP1 = gWorkingGeometry->getPoint(p1);
   const Point3D& rP2 = gWorkingGeometry->getPoint(p2);
   const Point3D& rP3 = gWorkingGeometry->getPoint(p3);

   // We are testing the distance from p3 to the line defined
   //  by p1 and p2.
   //
   F64 f = rP2.x - rP1.x;
   F64 g = rP2.y - rP1.y;
   F64 h = rP2.z - rP1.z;

   // P0 in our case is rP1.  Note the the following is taken from
   //  "A Programmer's Geometry"
   //
   F64 denom = f*f + g*g + h*h;
   if (denom < gcPlaneDistanceEpsilon * gcPlaneDistanceEpsilon) {
      // If two points are the same, then all three are colinear...
      return true;
   }

   F64 xj0 = rP3.x - rP1.x;
   F64 yj0 = rP3.y - rP1.y;
   F64 zj0 = rP3.z - rP1.z;

   F64 fygx = f * yj0 - g * xj0;
   F64 fzhx = f * zj0 - h * xj0;
   F64 gzhy = g * zj0 - h * yj0;

   F64 v1 =  g * fygx + h * fzhx;
   F64 v2 =  h * gzhy - f * fygx;
   F64 v3 = -f * fzhx - g * gzhy;

   F64 dist = mSqrt(v1*v1 + v2*v2 + v3*v3) / denom;

   if (dist < gcPlaneDistanceEpsilon)
      return true;
   else
      return false;
}


//------------------------------------------------------------------------------
bool collapseWindings(Winding& into, const Winding& from)
{
   if (canCollapseWinding(into, from) == false)
      return false;

   // DEBUG POINT: Check that into contains no colinear
   // DEBUG POINT: Check that from contains no colinear

   U32 oneStart;
   U32 twoStart;

   bool found = false;
   for (U32 i = 0; i < into.numIndices && !found; i++) {
      U32 edgeStart = into.indices[(i + 1) % into.numIndices];
      U32 edgeEnd   = into.indices[i];

      for (U32 j = 0; j < from.numIndices && !found; j++) {
         if (from.indices[j] == edgeStart &&
             from.indices[(j + 1) % from.numIndices] == edgeEnd) {
            found = true;
            oneStart = i;
            twoStart = j;
         }
      }
   }
   AssertFatal(found == true, "error, something missing in dodge city, no common edge!");

   AssertFatal((into.numIndices + from.numIndices - 2) < MaxWindingPoints,
               "Uh, need to increase MaxWindingPoints.  Talk to DMoore");
   U32 newIndices[64];
   U32 newCount = 0;

   for (U32 i = 0; i <= oneStart; i++) {
      newIndices[newCount++] = into.indices[i];
   }
   for (U32 i = (twoStart + 2) % from.numIndices; i != twoStart;) {
      newIndices[newCount++] = from.indices[i];

      i = (i+1) % from.numIndices;
   }
   for (U32 i = (oneStart + 1) % into.numIndices; i > 0;) {
      newIndices[newCount++] = into.indices[i];

      i = (i+1) % into.numIndices;
   }

   // Remove any colinear edges...
   for (U32 i = 0; i < newCount; i++) {
      U32 index0 = i;
      U32 index1 = (i + 1) % newCount;
      U32 index2 = (i + 2) % newCount;

      if (pointsAreColinear(newIndices[index0], newIndices[index1], newIndices[index2])) {
         // Remove the edge...
         U32 size = (newCount - index1 - 1) * sizeof(U32);
         dMemmove(&newIndices[index1], &newIndices[index1+1], size);
         newCount--;
      }
   }
   AssertFatal(newCount >= 3 && newCount <= MaxWindingPoints, "Ah, crap, something goofed in collapseWindings.  Talk to DMoore");

   // See if the new winding is convex
   Point3D reference;
   for (U32 i = 0; i < newCount; i++) {
      U32 j = (i + 1) % newCount;
      U32 k = (i + 2) % newCount;

      Point3D vec1 = gWorkingGeometry->getPoint(newIndices[i]) - gWorkingGeometry->getPoint(newIndices[j]);
      Point3D vec2 = gWorkingGeometry->getPoint(newIndices[k]) - gWorkingGeometry->getPoint(newIndices[j]);

      Point3D result;
      mCross(vec1, vec2, &result);
      if (i == 0) {
         reference = result;
      } else {
         F64 dot = mDot(reference, result);
         if (dot < 0.0) {
            return false;
         }
      }
   }

   // Copy the new rWinding, and we're set!
   //
   dMemcpy(into.indices, newIndices, newCount * sizeof(U32));
   into.numIndices = newCount;

   // Make sure the nodes are merged
   for (U32 i = 0; i < from.numNodes; i++) {
      bool found = false;
      for (U32 j = 0; j < into.numNodes; j++) {
         if (into.solidNodes[j] == from.solidNodes[i]) {
            found = true;
            break;
         }
      }
      if (found == false) {
         AssertFatal(into.numNodes < MaxWindingNodes, "Error, too many solid nodes affecting poly.  Plase ask DMoore to increase the allowed number!");
         into.solidNodes[into.numNodes++] = from.solidNodes[i];
      }
   }
   for (U32 i = 0; i < from.numZoneIds; i++)
      into.insertZone(from.zoneIds[i]);

   // DEBUG POINT: into must contain no colinear

   return true;
}


//------------------------------------------------------------------------------
void extendName(char* pName, const char* pExt)
{
   AssertFatal(pName != NULL && dStrlen(pName) != 0 && pExt != NULL && pExt[0] == '.',
               "Error, bad inputs to reextendName");

   dStrcat(pName, pExt);
}


void reextendName(char* pName, const char* pExt)
{
   AssertFatal(pName != NULL && dStrlen(pName) != 0 && pExt != NULL && pExt[0] == '.',
               "Error, bad inputs to reextendName");

   char* pDot = dStrrchr(pName, '.');
   if (pDot != NULL) {
      if (dStricmp(pDot, pExt) != 0) {
         dStrcpy(pDot, pExt);
      }
   } else {
      dStrcat(pName, pExt);
   }
}

bool createBaseWinding(const Vector<U32>& rPoints, const Point3D& normal, Winding* pWinding)
{
   if (rPoints.size() <= 2) {
      dPrintf("::createBaseWinding: Bad face on brush.  < 3 points.  DMMNOTE: Handle better?\n");
      return false;
   }
   if (rPoints.size() > 32) {
      dPrintf("::createBaseWinding: Bad face on brush.  > 32 points.  DMMNOTE: Increase max winding points?\n");
      return false;
   }


   Vector<U32> modPoints = rPoints;

   // Create a centroid first...
   Point3D centroid(0, 0, 0);
   for (U32 i = 0; i < modPoints.size(); i++)
      centroid += gWorkingGeometry->getPoint(modPoints[i]);
   centroid /= F64(modPoints.size());

   // Ok, we have a centroid.  We (arbitrarily) take the last point, and start from
   //  there...
   pWinding->indices[0] = modPoints[modPoints.size() - 1];
   pWinding->numIndices = 1;
   modPoints.erase(modPoints.size() - 1);

   while (modPoints.size() != 0) {
      // Find the largest dot product of a point with a positive facing
      //  cross product.
      //
      F64 maxDot  = -1e10;
      S32 maxIndex = -1;

      const Point3D& currPoint = gWorkingGeometry->getPoint(pWinding->indices[pWinding->numIndices - 1]);
      Point3D currVector       = currPoint - centroid;
      currVector.normalize();

      for (U32 i = 0; i < modPoints.size(); i++) {

         const Point3D& testPoint = gWorkingGeometry->getPoint(modPoints[i]);
         Point3D testVector       = testPoint - centroid;
         testVector.normalize();

         Point3D crossVector;
         mCross(currVector, testVector, &crossVector);
         crossVector.normalize();

         if (mDot(crossVector, normal) < 0.0) {
            // Candidate
            F64 val  = mDot(testVector, currVector);
            F64 dVal = mDot(testVector, currVector);

            if (val > maxDot) {
               maxDot   = val;
               maxIndex = i;
            }
         }
      }
      //AssertISV(maxIndex != -1, "::createBaseWinding: no point found for winding?");
      if(maxIndex == -1)
         return false;

      pWinding->indices[pWinding->numIndices++] = modPoints[maxIndex];
      modPoints.erase(maxIndex);
   }

   pWinding->numNodes = 0;
   pWinding->numZoneIds = 0;

   return true;
}


BrushArena::BrushArena(U32 _arenaSize)
{
   arenaValid    = true;
   arenaSize     = _arenaSize;
   mFreeListHead = NULL;
}

BrushArena::~BrushArena()
{
   arenaValid = false;
   for (U32 i = 0; i < mBuffers.size(); i++) {
      delete [] mBuffers[i];
      mBuffers[i] = NULL;
   }
   mFreeListHead = NULL;
   arenaSize     = 0;
}

void BrushArena::newBuffer()
{
   // Otherwise, we set up some more free windings...
   CSGBrush* pNewBuffer = new CSGBrush[arenaSize];
   mBuffers.push_back(pNewBuffer);
   for (U32 i = 0; i < arenaSize - 1; i++) {
      pNewBuffer[i].pNext = &pNewBuffer[i+1];
   }
   pNewBuffer[arenaSize - 1].pNext = NULL;

   mFreeListHead = pNewBuffer;
}

CSGBrush* BrushArena::allocateBrush()
{
   AssertFatal(arenaValid == true, "Arena invalid!");

   if (mFreeListHead == NULL)
      newBuffer();
   AssertFatal(mFreeListHead != NULL, "error, that shouldn't happen!");

   CSGBrush* pRet     = mFreeListHead;
   mFreeListHead      = pRet->pNext;
   pRet->pNext        = NULL;
   pRet->mIsAmbiguous = false;
   pRet->mPlanes.clear();
   return pRet;
}

void BrushArena::freeBrush(CSGBrush* junk)
{
   AssertFatal(arenaValid == true, "Arena invalid!");
   AssertFatal(junk->pNext == NULL, "Error, this is still on the free list!");

   junk->pNext   = mFreeListHead;
   mFreeListHead = junk;
}


bool intersectWGPlanes(U32 i, U32 j, U32 k,
                       Point3D* pOutput)
{
   const PlaneEQ& rPlaneEQ1 = gWorkingGeometry->getPlaneEQ(i);
   const PlaneEQ& rPlaneEQ2 = gWorkingGeometry->getPlaneEQ(j);
   const PlaneEQ& rPlaneEQ3 = gWorkingGeometry->getPlaneEQ(k);

   F64 bc  = (rPlaneEQ2.normal.y * rPlaneEQ3.normal.z) - (rPlaneEQ3.normal.y * rPlaneEQ2.normal.z);
   F64 ac  = (rPlaneEQ2.normal.x * rPlaneEQ3.normal.z) - (rPlaneEQ3.normal.x * rPlaneEQ2.normal.z);
   F64 ab  = (rPlaneEQ2.normal.x * rPlaneEQ3.normal.y) - (rPlaneEQ3.normal.x * rPlaneEQ2.normal.y);
   F64 det = (rPlaneEQ1.normal.x * bc) - (rPlaneEQ1.normal.y * ac) + (rPlaneEQ1.normal.z * ab);

   if (mFabs(det) < 1e-9) {
      // Parallel planes
      return false;
   }

   F64 dc     = (rPlaneEQ2.dist * rPlaneEQ3.normal.z) - (rPlaneEQ3.dist * rPlaneEQ2.normal.z);
   F64 db     = (rPlaneEQ2.dist * rPlaneEQ3.normal.y) - (rPlaneEQ3.dist * rPlaneEQ2.normal.y);
   F64 ad     = (rPlaneEQ3.dist * rPlaneEQ2.normal.x) - (rPlaneEQ2.dist * rPlaneEQ3.normal.x);
   F64 detInv = 1.0 / det;

   pOutput->x = ((rPlaneEQ1.normal.y * dc) - (rPlaneEQ1.dist     * bc) - (rPlaneEQ1.normal.z * db)) * detInv;
   pOutput->y = ((rPlaneEQ1.dist     * ac) - (rPlaneEQ1.normal.x * dc) - (rPlaneEQ1.normal.z * ad)) * detInv;
   pOutput->z = ((rPlaneEQ1.normal.y * ad) + (rPlaneEQ1.normal.x * db) - (rPlaneEQ1.dist     * ab)) * detInv;

   return true;
}