Brush.cpp

Go to the documentation of this file.

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/


#include "stdafx.h"
#include <assert.h>
#include "qe3.h"
#include "winding.h"


// globals

int g_nBrushId = 0;

const char* Brush_Name(brush_t *b)
{
  static char cBuff[1024];
    b->numberId = g_nBrushId++;
    if (g_qeglobals.m_bBrushPrimitMode)
  {
    sprintf(cBuff, "Brush %i", b->numberId);
    Brush_SetEpair(b, "Name", cBuff);
  }
  return cBuff;
}

brush_t *Brush_Alloc()
{
  brush_t *b = (brush_t*)qmalloc(sizeof(brush_t));
  return b;
}




void PrintWinding (winding_t *w)
{
    int     i;
    
    printf ("-------------\n");
    for (i=0 ; i<w->numpoints ; i++)
        printf ("(%5.2f, %5.2f, %5.2f)\n", w->points[i][0]
        , w->points[i][1], w->points[i][2]);
}

void PrintPlane (plane_t *p)
{
  printf ("(%5.2f, %5.2f, %5.2f) : %5.2f\n",  p->normal[0],  p->normal[1], 
  p->normal[2],  p->dist);
}

void PrintVector (vec3_t v)
{
  printf ("(%5.2f, %5.2f, %5.2f)\n",  v[0],  v[1], v[2]);
}


/*
=============================================================================

            TEXTURE COORDINATES

=============================================================================
*/


/*
==================
textureAxisFromPlane
==================
*/
vec3_t  baseaxis[18] =
{
{0,0,1}, {1,0,0}, {0,-1,0},         // floor
{0,0,-1}, {1,0,0}, {0,-1,0},        // ceiling
{1,0,0}, {0,1,0}, {0,0,-1},         // west wall
{-1,0,0}, {0,1,0}, {0,0,-1},        // east wall
{0,1,0}, {1,0,0}, {0,0,-1},         // south wall
{0,-1,0}, {1,0,0}, {0,0,-1}         // north wall
};

void TextureAxisFromPlane(plane_t *pln, vec3_t xv, vec3_t yv)
{
    int     bestaxis;
    float   dot,best;
    int     i;
    
    best = 0;
    bestaxis = 0;
    
    for (i=0 ; i<6 ; i++)
    {
        dot = DotProduct (pln->normal, baseaxis[i*3]);
        if (dot > best)
        {
            best = dot;
            bestaxis = i;
        }
    }
    
    VectorCopy (baseaxis[bestaxis*3+1], xv);
    VectorCopy (baseaxis[bestaxis*3+2], yv);
}



float   lightaxis[3] = {0.6, 0.8, 1.0};
/*
================
SetShadeForPlane

Light different planes differently to
improve recognition
================
*/
float SetShadeForPlane (plane_t *p)
{
    int     i;
    float   f;

    // axial plane
    for (i=0 ; i<3 ; i++)
        if (fabs(p->normal[i]) > 0.9)
        {
            f = lightaxis[i];
            return f;
        }

    // between two axial planes
    for (i=0 ; i<3 ; i++)
        if (fabs(p->normal[i]) < 0.1)
        {
            f = (lightaxis[(i+1)%3] + lightaxis[(i+2)%3])/2;
            return f;
        }

    // other
    f= (lightaxis[0] + lightaxis[1] + lightaxis[2]) / 3;
    return f;
}

vec3_t  vecs[2];
float   shift[2];

/*
================
Face_Alloc
================
*/
face_t *Face_Alloc( void )
{
    face_t *f = (face_t*)qmalloc( sizeof( *f ) );
    
    if (g_qeglobals.bSurfacePropertiesPlugin)
        f->pData = static_cast<void *>( g_SurfaceTable.m_pfnTexdefAlloc( f ) );

    return f;
}

/*
================
Face_Free
================
*/
void Face_Free( face_t *f )
{
    assert( f != 0 );

    if ( f->face_winding )
    {
        free( f->face_winding );
        f->face_winding = 0;
    }

    if (g_qeglobals.bSurfacePropertiesPlugin)
    {
#ifdef _DEBUG
        if ( !f->pData )
        {
            Sys_Printf("WARNING: unexpected IPluginTexdef is NULL in Face_Free\n");
        }
        else
#endif
        GETPLUGINTEXDEF(f)->DecRef();
    }

    f->texdef.~texdef_t();;

    free( f );
}

/*
================
Face_Clone
================
*/
face_t  *Face_Clone (face_t *f)
{
    face_t  *n;

    n = Face_Alloc();
    n->texdef = f->texdef;

    memcpy (n->planepts, f->planepts, sizeof(n->planepts));

    // all other fields are derived, and will be set by Brush_Build
    return n;
}

/*
================
Face_FullClone

makes an exact copy of the face
================
*/
face_t  *Face_FullClone (face_t *f)
{
    face_t  *n;

    n = Face_Alloc();
    n->texdef = f->texdef;
    memcpy(n->planepts, f->planepts, sizeof(n->planepts));
    memcpy(&n->plane, &f->plane, sizeof(plane_t));
    if (f->face_winding)
        n->face_winding = Winding_Clone(f->face_winding);
    else
        n->face_winding = NULL;
    n->d_texture = Texture_ForName( n->texdef.name );
    return n;
}

/*
================
Clamp
================
*/
void Clamp(float& f, int nClamp)
{
  float fFrac = f - static_cast<int>(f);
  f = static_cast<int>(f) % nClamp;
  f += fFrac;
}

/*
================
Face_MoveTexture
================
*/
void Face_MoveTexture(face_t *f, vec3_t delta)
{
    vec3_t vX, vY;
/*
#ifdef _DEBUG
    if (g_PrefsDlg.m_bBrushPrimitMode)
        Sys_Printf("Warning : Face_MoveTexture not done in brush primitive mode\n");
#endif
*/
    if (g_qeglobals.m_bBrushPrimitMode)
        Face_MoveTexture_BrushPrimit( f, delta );
    else
    {
        TextureAxisFromPlane(&f->plane, vX, vY);

        vec3_t vDP, vShift;
        vDP[0] = DotProduct(delta, vX);
        vDP[1] = DotProduct(delta, vY);

        double fAngle = f->texdef.rotate  / 180 * Q_PI;
        double c = cos(fAngle);
        double s = sin(fAngle);

        vShift[0] = vDP[0] * c - vDP[1] * s;
        vShift[1] = vDP[0] * s + vDP[1] * c;

        if (!f->texdef.scale[0])
            f->texdef.scale[0] = 1;
        if (!f->texdef.scale[1])
            f->texdef.scale[1] = 1;

        f->texdef.shift[0] -= vShift[0] / f->texdef.scale[0];
        f->texdef.shift[1] -= vShift[1] / f->texdef.scale[1];
  
        // clamp the shifts
        Clamp(f->texdef.shift[0], f->d_texture->width);
        Clamp(f->texdef.shift[1], f->d_texture->height);
    }
}

/*
================
Face_SetColor
================
*/
void Face_SetColor (brush_t *b, face_t *f, float fCurveColor) 
{
    float   shade;
    qtexture_t *q;

    q = f->d_texture;

    // set shading for face
    shade = SetShadeForPlane (&f->plane);
    if (g_pParentWnd->GetCamera()->Camera().draw_mode == cd_texture && !b->owner->eclass->fixedsize)
    {
        //if (b->curveBrush)
        //  shade = fCurveColor;
        f->d_color[0] = 
        f->d_color[1] = 
        f->d_color[2] = shade;
    }
    else
    {
        f->d_color[0] = shade*q->color[0];
        f->d_color[1] = shade*q->color[1];
        f->d_color[2] = shade*q->color[2];
    }
}

/*
================
Face_TextureVectors
TTimo: NOTE: this is never to get called while in brush primitives mode
================
*/
void Face_TextureVectors (face_t *f, float STfromXYZ[2][4])
{
    vec3_t      pvecs[2];
    int         sv, tv;
    float       ang, sinv, cosv;
    float       ns, nt;
    int         i,j;
    qtexture_t *q;
    texdef_t    *td;

#ifdef _DEBUG
    //++timo when playing with patches, this sometimes get called and the Warning is displayed
    // find some way out ..
    if (g_qeglobals.m_bBrushPrimitMode && !g_qeglobals.bNeedConvert)
        Sys_Printf("Warning : illegal call of Face_TextureVectors in brush primitive mode\n");
#endif

    td = &f->texdef;
    q = f->d_texture;

    memset (STfromXYZ, 0, 8*sizeof(float));

    if (!td->scale[0])
        td->scale[0] = (g_PrefsDlg.m_bHiColorTextures) ? 0.5 : 1;
    if (!td->scale[1])
        td->scale[1] = (g_PrefsDlg.m_bHiColorTextures) ? 0.5 : 1;

    // get natural texture axis
    TextureAxisFromPlane(&f->plane, pvecs[0], pvecs[1]);

    // rotate axis
    if (td->rotate == 0)
        { sinv = 0 ; cosv = 1; }
    else if (td->rotate == 90)
        { sinv = 1 ; cosv = 0; }
    else if (td->rotate == 180)
        { sinv = 0 ; cosv = -1; }
    else if (td->rotate == 270)
        { sinv = -1 ; cosv = 0; }
    else
    {   
        ang = td->rotate / 180 * Q_PI;
        sinv = sin(ang);
        cosv = cos(ang);
    }

    if (pvecs[0][0])
        sv = 0;
    else if (pvecs[0][1])
        sv = 1;
    else
        sv = 2;
                
    if (pvecs[1][0])
        tv = 0;
    else if (pvecs[1][1])
        tv = 1;
    else
        tv = 2;
                    
    for (i=0 ; i<2 ; i++) {
        ns = cosv * pvecs[i][sv] - sinv * pvecs[i][tv];
        nt = sinv * pvecs[i][sv] +  cosv * pvecs[i][tv];
        STfromXYZ[i][sv] = ns;
        STfromXYZ[i][tv] = nt;
    }

    // scale
    for (i=0 ; i<2 ; i++)
        for (j=0 ; j<3 ; j++)
            STfromXYZ[i][j] = STfromXYZ[i][j] / td->scale[i];

    // shift
    STfromXYZ[0][3] = td->shift[0];
    STfromXYZ[1][3] = td->shift[1];

    for (j=0 ; j<4 ; j++) {
        STfromXYZ[0][j] /= q->width;
        STfromXYZ[1][j] /= q->height;
    }
}

/*
================
Face_MakePlane
================
*/
void Face_MakePlane (face_t *f)
{
    int     j;
    vec3_t  t1, t2, t3;

    // convert to a vector / dist plane
    for (j=0 ; j<3 ; j++)
    {
        t1[j] = f->planepts[0][j] - f->planepts[1][j];
        t2[j] = f->planepts[2][j] - f->planepts[1][j];
        t3[j] = f->planepts[1][j];
    }
    
    CrossProduct(t1,t2, f->plane.normal);
    if (VectorCompare (f->plane.normal, vec3_origin))
        printf ("WARNING: brush plane with no normal\n");
    VectorNormalize (f->plane.normal);
    f->plane.dist = DotProduct (t3, f->plane.normal);
}

/*
================
EmitTextureCoordinates
================
*/
void EmitTextureCoordinates ( float *xyzst, qtexture_t *q, face_t *f)
{
    float   STfromXYZ[2][4];

    Face_TextureVectors (f,  STfromXYZ);
    xyzst[3] = DotProduct (xyzst, STfromXYZ[0]) + STfromXYZ[0][3];
    xyzst[4] = DotProduct (xyzst, STfromXYZ[1]) + STfromXYZ[1][3];
}

//==========================================================================

/*
================
Brush_MakeFacePlanes
================
*/
void Brush_MakeFacePlanes (brush_t *b)
{
    face_t  *f;

    for (f=b->brush_faces ; f ; f=f->next)
    {
        Face_MakePlane (f);
    }
}

/*
================
DrawBrushEntityName
================
*/
void DrawBrushEntityName (brush_t *b)
{
    char    *name;
    //float a, s, c;
    //vec3_t    mid;
    //int       i;

    if (!b->owner)
        return;     // during contruction

    if (b->owner == world_entity)
        return;

    if (b != b->owner->brushes.onext)
        return; // not key brush

// MERGEME
#if 0
    if (!(g_qeglobals.d_savedinfo.exclude & EXCLUDE_ANGLES))
    {
        // draw the angle pointer
        a = FloatForKey (b->owner, "angle");
        if (a)
        {
            s = sin (a/180*Q_PI);
            c = cos (a/180*Q_PI);
            for (i=0 ; i<3 ; i++)
                mid[i] = (b->mins[i] + b->maxs[i])*0.5; 

            qglBegin (GL_LINE_STRIP);
            qglVertex3fv (mid);
            mid[0] += c*8;
            mid[1] += s*8;
            mid[2] += s*8;
            qglVertex3fv (mid);
            mid[0] -= c*4;
            mid[1] -= s*4;
            mid[2] -= s*4;
            mid[0] -= s*4;
            mid[1] += c*4;
            mid[2] += c*4;
            qglVertex3fv (mid);
            mid[0] += c*4;
            mid[1] += s*4;
            mid[2] += s*4;
            mid[0] += s*4;
            mid[1] -= c*4;
            mid[2] -= c*4;
            qglVertex3fv (mid);
            mid[0] -= c*4;
            mid[1] -= s*4;
            mid[2] -= s*4;
            mid[0] += s*4;
            mid[1] -= c*4;
            mid[2] -= c*4;
            qglVertex3fv (mid);
            qglEnd ();
        }
    }
#endif

    if (g_qeglobals.d_savedinfo.show_names)
    {
        name = ValueForKey (b->owner, "classname");
        qglRasterPos3f (b->mins[0]+4, b->mins[1]+4, b->mins[2]+4);
        qglCallLists (strlen(name), GL_UNSIGNED_BYTE, name);
    }
}

/*
=================
Brush_MakeFaceWinding

returns the visible polygon on a face
=================
*/
winding_t *Brush_MakeFaceWinding (brush_t *b, face_t *face)
{
    winding_t   *w;
    face_t      *clip;
    plane_t         plane;
    qboolean        past;

    // get a poly that covers an effectively infinite area
    w = Winding_BaseForPlane (&face->plane);

    // chop the poly by all of the other faces
    past = false;
    for (clip = b->brush_faces ; clip && w ; clip=clip->next)
    {
        if (clip == face)
        {
            past = true;
            continue;
        }
        if (DotProduct (face->plane.normal, clip->plane.normal) > 0.999
            && fabs(face->plane.dist - clip->plane.dist) < 0.01 )
        {   // identical plane, use the later one
            if (past)
            {
                free (w);
                return NULL;
            }
            continue;
        }

        // flip the plane, because we want to keep the back side
        VectorSubtract (vec3_origin,clip->plane.normal, plane.normal);
        plane.dist = -clip->plane.dist;
        
        w = Winding_Clip (w, &plane, false);
        if (!w)
            return w;
    }
    
    if (w->numpoints < 3)
    {
        free(w);
        w = NULL;
    }

    if (!w)
        printf ("unused plane\n");

    return w;
}

/*
=================
Brush_SnapPlanepts
=================
*/
void Brush_SnapPlanepts (brush_t *b)
{
    int     i, j;
    face_t  *f;

  if (g_PrefsDlg.m_bNoClamp)
    return;

    for (f=b->brush_faces ; f; f=f->next)
        for (i=0 ; i<3 ; i++)
            for (j=0 ; j<3 ; j++)
                f->planepts[i][j] = floor (f->planepts[i][j] + 0.5);
}
    
/*
** Brush_Build
**
** Builds a brush rendering data and also sets the min/max bounds
*/
// TTimo
// added a bConvert flag to convert between old and new brush texture formats
// TTimo
// brush grouping: update the group treeview if necessary
void Brush_Build( brush_t *b, bool bSnap, bool bMarkMap, bool bConvert )
{
    bool        bLocalConvert;

#ifdef _DEBUG
    if (!g_qeglobals.m_bBrushPrimitMode && bConvert)
        Sys_Printf("Warning : conversion from brush primitive to old brush format not implemented\n");
#endif

    // if bConvert is set and g_qeglobals.bNeedConvert is not, that just means we need convert for this brush only
    if (bConvert && !g_qeglobals.bNeedConvert)
    {
        bLocalConvert = true;
        g_qeglobals.bNeedConvert = true;
    }

    /*
    ** build the windings and generate the bounding box
    */
    Brush_BuildWindings(b, bSnap);

    Patch_BuildPoints (b);

    /*
    ** move the points and edges if in select mode
    */
    if (g_qeglobals.d_select_mode == sel_vertex || g_qeglobals.d_select_mode == sel_edge)
        SetupVertexSelection ();

    if (b->itemOwner == NULL)
      Group_AddToProperGroup(b);

    if (bMarkMap)
    {
        Sys_MarkMapModified();
    }

    if (bLocalConvert)
        g_qeglobals.bNeedConvert = false;
}

/*
==============
Brush_SplitBrushByFace

The incoming brush is NOT freed.
The incoming face is NOT left referenced.
==============
*/
void Brush_SplitBrushByFace (brush_t *in, face_t *f, brush_t **front, brush_t **back)
{
    brush_t *b;
    face_t  *nf;
    vec3_t  temp;

    b = Brush_Clone (in);
    nf = Face_Clone (f);

    nf->texdef = b->brush_faces->texdef;
    nf->next = b->brush_faces;
    b->brush_faces = nf;

    Brush_Build( b );
    Brush_RemoveEmptyFaces ( b );
    if ( !b->brush_faces )
    {   // completely clipped away
        Brush_Free (b);
        *back = NULL;
    }
    else
    {
        Entity_LinkBrush (in->owner, b);
        *back = b;
    }

    b = Brush_Clone (in);
    nf = Face_Clone (f);
    // swap the plane winding
    VectorCopy (nf->planepts[0], temp);
    VectorCopy (nf->planepts[1], nf->planepts[0]);
    VectorCopy (temp, nf->planepts[1]);

    nf->texdef = b->brush_faces->texdef;
    nf->next = b->brush_faces;
    b->brush_faces = nf;

    Brush_Build( b );
    Brush_RemoveEmptyFaces ( b );
    if ( !b->brush_faces )
    {   // completely clipped away
        Brush_Free (b);
        *front = NULL;
    }
    else
    {
        Entity_LinkBrush (in->owner, b);
        *front = b;
    }
}

/*
=================
Brush_BestSplitFace

returns the best face to split the brush with.
return NULL if the brush is convex
=================
*/
face_t *Brush_BestSplitFace(brush_t *b)
{
    face_t *face, *f, *bestface;
    winding_t *front, *back;
    int splits, tinywindings, value, bestvalue;

    bestvalue = 999999;
    bestface = NULL;
    for (face = b->brush_faces; face; face = face->next)
    {
        splits = 0;
        tinywindings = 0;
        for (f = b->brush_faces; f; f = f->next)
        {
            if (f == face) continue;
            //
            Winding_SplitEpsilon(f->face_winding, face->plane.normal, face->plane.dist, 0.1, &front, &back);

            if (!front)
            {
                Winding_Free(back);
            }
            else if (!back)
            {
                Winding_Free(front);
            }
            else
            {
                splits++;
                if (Winding_IsTiny(front)) tinywindings++;
                if (Winding_IsTiny(back)) tinywindings++;
            }
        }
        if (splits)
        {
            value = splits + 50 * tinywindings;
            if (value < bestvalue)
            {
                bestvalue = value;
                bestface = face;
            }
        }
    }
    return bestface;
}

/*
=================
Brush_MakeConvexBrushes

MrE FIXME: this doesn't work because the old
           Brush_SplitBrushByFace is used
Turns the brush into a minimal number of convex brushes.
If the input brush is convex then it will be returned.
Otherwise the input brush will be freed.
NOTE: the input brush should have windings for the faces.
=================
*/
brush_t *Brush_MakeConvexBrushes(brush_t *b)
{
    brush_t *front, *back, *end;
    face_t *face;

    b->next = NULL;
    face = Brush_BestSplitFace(b);
    if (!face) return b;
    Brush_SplitBrushByFace(b, face, &front, &back);
    //this should never happen
    if (!front && !back) return b;
    Brush_Free(b);
    if (!front)
        return Brush_MakeConvexBrushes(back);
    b = Brush_MakeConvexBrushes(front);
    if (back)
    {
        for (end = b; end->next; end = end->next);
        end->next = Brush_MakeConvexBrushes(back);
    }
    return b;
}

/*
=================
Brush_Convex
=================
*/
int Brush_Convex(brush_t *b)
{
    face_t *face1, *face2;

    for (face1 = b->brush_faces; face1; face1 = face1->next)
    {
        if (!face1->face_winding) continue;
        for (face2 = b->brush_faces; face2; face2 = face2->next)
        {
            if (face1 == face2) continue;
            if (!face2->face_winding) continue;
            if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
                                        face1->plane.normal, face2->plane.normal,
                                        face1->plane.dist, face2->plane.dist))
            {
                return false;
            }
        }
    }
    return true;
}

/*
=================
Brush_MoveVertexes_old1

- The input brush must have face windings.
- The input brush must be a brush with faces that do not intersect.
- The input brush does not have to be convex.
- The vertex will not be moved if the movement either causes the
  brush to have faces that intersect or causes the brush to be
  flipped inside out.
  (For instance a tetrahedron can easily be flipped inside out
  without having faces that intersect.)
- The created brush does not have to be convex.
- Returns true if the vertex movement is performed.
=================
*/

#define MAX_MOVE_FACES      64
#define INTERSECT_EPSILON   0.1
#define POINT_EPSILON       0.3

int Brush_MoveVertex_old1(brush_t *b, vec3_t vertex, vec3_t delta, vec3_t end, bool bSnap)
{
    face_t *f, *face, *newface, *lastface, *nextface;
    face_t *movefaces[MAX_MOVE_FACES];
    int movefacepoints[MAX_MOVE_FACES];
    winding_t *w, tmpw;
    int i, j, k, nummovefaces, result;
    float dot;

    result = false;
    //
    tmpw.numpoints = 3;
    tmpw.maxpoints = 3;
    VectorAdd(vertex, delta, end);
    //snap or not?
    if (bSnap)
        for (i = 0; i < 3; i++)
            end[i] = floor(end[i] / g_qeglobals.d_gridsize + 0.5) * g_qeglobals.d_gridsize;
    //chop off triangles from all brush faces that use the to be moved vertex
    //store pointers to these chopped off triangles in movefaces[]
    nummovefaces = 0;
    for (face = b->brush_faces; face; face = face->next)
    {
        w = face->face_winding;
        if (!w) continue;
        for (i = 0; i < w->numpoints; i++)
        {
            if (Point_Equal(w->points[i], vertex, POINT_EPSILON))
            {
                if (face->face_winding->numpoints <= 3)
                {
                    movefacepoints[nummovefaces] = i;
                    movefaces[nummovefaces++] = face;
                    break;
                }
                dot = DotProduct(end, face->plane.normal) - face->plane.dist;
                //if the end point is in front of the face plane
                if (dot > 0.1)
                {
                    //fanout triangle subdivision
                    for (k = i; k < i + w->numpoints-3; k++)
                    {
                        VectorCopy(w->points[i], tmpw.points[0]);
                        VectorCopy(w->points[(k+1) % w->numpoints], tmpw.points[1]);
                        VectorCopy(w->points[(k+2) % w->numpoints], tmpw.points[2]);
                        //
                        newface = Face_Clone(face);
                        //get the original
                        for (f = face; f->original; f = f->original) ;
                        newface->original = f;
                        //store the new winding
                        if (newface->face_winding) Winding_Free(newface->face_winding);
                        newface->face_winding = Winding_Clone(&tmpw);
                        //get the texture
                        newface->d_texture = Texture_ForName( newface->texdef.name );
                        //add the face to the brush
                        newface->next = b->brush_faces;
                        b->brush_faces = newface;
                        //add this new triangle to the move faces
                        movefacepoints[nummovefaces] = 0;
                        movefaces[nummovefaces++] = newface;
                    }
                    //give the original face a new winding
                    VectorCopy(w->points[(i-2+w->numpoints) % w->numpoints], tmpw.points[0]);
                    VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[1]);
                    VectorCopy(w->points[i], tmpw.points[2]);
                    Winding_Free(face->face_winding);
                    face->face_winding = Winding_Clone(&tmpw);
                    //add the original face to the move faces
                    movefacepoints[nummovefaces] = 2;
                    movefaces[nummovefaces++] = face;
                }
                else
                {
                    //chop a triangle off the face
                    VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[0]);
                    VectorCopy(w->points[i], tmpw.points[1]);
                    VectorCopy(w->points[(i+1) % w->numpoints], tmpw.points[2]);
                    //remove the point from the face winding
                    Winding_RemovePoint(w, i);
                    //get texture crap right
                    Face_SetColor(b, face, 1.0);
                    for (j = 0; j < w->numpoints; j++)
                        EmitTextureCoordinates(w->points[j], face->d_texture, face);
                    //make a triangle face
                    newface = Face_Clone(face);
                    //get the original
                    for (f = face; f->original; f = f->original) ;
                    newface->original = f;
                    //store the new winding
                    if (newface->face_winding) Winding_Free(newface->face_winding);
                    newface->face_winding = Winding_Clone(&tmpw);
                    //get the texture
                    newface->d_texture = Texture_ForName( newface->texdef.name );
                    //add the face to the brush
                    newface->next = b->brush_faces;
                    b->brush_faces = newface;
                    //
                    movefacepoints[nummovefaces] = 1;
                    movefaces[nummovefaces++] = newface;
                }
                break;
            }
        }
    }
    //now movefaces contains pointers to triangle faces that
    //contain the to be moved vertex

    //check if the move is valid
    int l;
    vec3_t p1, p2;
    winding_t *w2;
    plane_t plane;

    face = NULL;
    VectorCopy(vertex, tmpw.points[1]);
    VectorCopy(end, tmpw.points[2]);
    for (face = b->brush_faces; face; face = face->next)
    {
        for (i = 0; i < nummovefaces; i++)
        {
            if (face == movefaces[i])
                break;
        }
        if (i < nummovefaces)
            continue;
        //the delta vector may not intersect with any of the not move faces
        if (Winding_VectorIntersect(face->face_winding, &face->plane, vertex, end, INTERSECT_EPSILON))
            break;
        //if the end point of the to be moved vertex is near this not move face
        if (abs(DotProduct(face->plane.normal, end) - face->plane.dist) < 0.5)
        {
            //the end point may not be inside or very close to the not move face winding
            if (Winding_PointInside(face->face_winding, &face->plane, end, 0.5))
                break;
        }
        for (i = 0; i < nummovefaces; i++)
        {
            w = movefaces[i]->face_winding;
            j = movefacepoints[i];
            for (k = -1; k <= 1; k += 2)
            {
                //check if the new edge will not intersect with the not move face
                VectorCopy(w->points[(j + k + w->numpoints) % w->numpoints], tmpw.points[0]);
                if (Winding_VectorIntersect(face->face_winding, &face->plane, tmpw.points[0], end, INTERSECT_EPSILON))
                {
                    //ok the new edge instersects with the not move face
                    //we can't perform the vertex movement
                    //break;
                }
                //check if the not move face intersects the "movement winding"
                Winding_Plane(&tmpw, plane.normal, &plane.dist);
                w2 = face->face_winding;
                for (l = 0; l < w2->numpoints; l++)
                {
                    VectorCopy(w2->points[l], p1);
                    if (Point_Equal(p1, tmpw.points[0], POINT_EPSILON)) continue;
                    VectorCopy(w2->points[(l+1) % w2->numpoints], p2);
                    if (Point_Equal(p2, tmpw.points[0], POINT_EPSILON)) continue;
                    if (Winding_VectorIntersect(&tmpw, &plane, p1, p2, INTERSECT_EPSILON))
                        break;
                }
                if (l < w2->numpoints)
                {
                    //ok this not move face intersects the "movement winding"
                    //we can't perform the vertex movement
                    break;
                }
            }
            if (k <= 1) break;
        }
        if (i < nummovefaces)
            break;
    }
    if (!face)
    {
        //ok the move was valid
        //now move all the vertexes of the movefaces
        for (i = 0; i < nummovefaces; i++)
        {
            VectorCopy(end, movefaces[i]->face_winding->points[movefacepoints[i]]);
            //create new face plane
            for (j = 0; j < 3; j++)
            {
                VectorCopy(movefaces[i]->face_winding->points[j], movefaces[i]->planepts[j]);
            }
            Face_MakePlane(movefaces[i]);
        }
        result = true;
    }
    //get texture crap right
    for (i = 0; i < nummovefaces; i++)
    {
        Face_SetColor(b, movefaces[i], 1.0);
        for (j = 0; j < movefaces[i]->face_winding->numpoints; j++)
            EmitTextureCoordinates(movefaces[i]->face_winding->points[j], movefaces[i]->d_texture, movefaces[i]);
    }

    //now try to merge faces with their original faces
    lastface = NULL;
    for (face = b->brush_faces; face; face = nextface)
    {
        nextface = face->next;
        if (!face->original)
        {
            lastface = face;
            continue;
        }
        if (!Plane_Equal(&face->plane, &face->original->plane, false))
        {
            lastface = face;
            continue;
        }
        w = Winding_TryMerge(face->face_winding, face->original->face_winding, face->plane.normal, true);
        if (!w)
        {
            lastface = face;
            continue;
        }
        Winding_Free(face->original->face_winding);
        face->original->face_winding = w;
        //get texture crap right
        Face_SetColor(b, face->original, 1.0);
        for (j = 0; j < face->original->face_winding->numpoints; j++)
            EmitTextureCoordinates(face->original->face_winding->points[j], face->original->d_texture, face->original);
        //remove the face that was merged with the original
        if (lastface) lastface->next = face->next;
        else b->brush_faces = face->next;
        Face_Free(face);
    }
    return result;
}

/*
=================
Brush_MoveVertexes_old2

- The input brush must be convex
- The input brush must have face windings.
- The output brush will be convex.
- Returns true if the vertex movement is performed.
=================
*/

#define MAX_MOVE_FACES      64
#define INTERSECT_EPSILON   0.1
#define POINT_EPSILON       0.3

int Brush_MoveVertex_old2(brush_t *b, vec3_t vertex, vec3_t delta, vec3_t end, bool bSnap)
{
    face_t *f, *face, *newface, *lastface, *nextface;
    face_t *movefaces[MAX_MOVE_FACES];
    int movefacepoints[MAX_MOVE_FACES];
    winding_t *w, tmpw;
    int i, j, k, nummovefaces, result;
    float dot;

    result = true;
    //
    tmpw.numpoints = 3;
    tmpw.maxpoints = 3;
    VectorAdd(vertex, delta, end);
    //snap or not?
    if (bSnap)
        for (i = 0; i < 3; i++)
            end[i] = floor(end[i] / g_qeglobals.d_gridsize + 0.5) * g_qeglobals.d_gridsize;
    //chop off triangles from all brush faces that use the to be moved vertex
    //store pointers to these chopped off triangles in movefaces[]
    nummovefaces = 0;
    for (face = b->brush_faces; face; face = face->next)
    {
        w = face->face_winding;
        if (!w) continue;
        for (i = 0; i < w->numpoints; i++)
        {
            if (Point_Equal(w->points[i], vertex, POINT_EPSILON))
            {
                if (face->face_winding->numpoints <= 3)
                {
                    movefacepoints[nummovefaces] = i;
                    movefaces[nummovefaces++] = face;
                    break;
                }
                dot = DotProduct(end, face->plane.normal) - face->plane.dist;
                //if the end point is in front of the face plane
                if (dot > 0.1)
                {
                    //fanout triangle subdivision
                    for (k = i; k < i + w->numpoints-3; k++)
                    {
                        VectorCopy(w->points[i], tmpw.points[0]);
                        VectorCopy(w->points[(k+1) % w->numpoints], tmpw.points[1]);
                        VectorCopy(w->points[(k+2) % w->numpoints], tmpw.points[2]);
                        //
                        newface = Face_Clone(face);
                        //get the original
                        for (f = face; f->original; f = f->original) ;
                        newface->original = f;
                        //store the new winding
                        if (newface->face_winding) Winding_Free(newface->face_winding);
                        newface->face_winding = Winding_Clone(&tmpw);
                        //get the texture
                        newface->d_texture = Texture_ForName( newface->texdef.name );
                        //add the face to the brush
                        newface->next = b->brush_faces;
                        b->brush_faces = newface;
                        //add this new triangle to the move faces
                        movefacepoints[nummovefaces] = 0;
                        movefaces[nummovefaces++] = newface;
                    }
                    //give the original face a new winding
                    VectorCopy(w->points[(i-2+w->numpoints) % w->numpoints], tmpw.points[0]);
                    VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[1]);
                    VectorCopy(w->points[i], tmpw.points[2]);
                    Winding_Free(face->face_winding);
                    face->face_winding = Winding_Clone(&tmpw);
                    //add the original face to the move faces
                    movefacepoints[nummovefaces] = 2;
                    movefaces[nummovefaces++] = face;
                }
                else
                {
                    //chop a triangle off the face
                    VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[0]);
                    VectorCopy(w->points[i], tmpw.points[1]);
                    VectorCopy(w->points[(i+1) % w->numpoints], tmpw.points[2]);
                    //remove the point from the face winding
                    Winding_RemovePoint(w, i);
                    //get texture crap right
                    Face_SetColor(b, face, 1.0);
                    for (j = 0; j < w->numpoints; j++)
                        EmitTextureCoordinates(w->points[j], face->d_texture, face);
                    //make a triangle face
                    newface = Face_Clone(face);
                    //get the original
                    for (f = face; f->original; f = f->original) ;
                    newface->original = f;
                    //store the new winding
                    if (newface->face_winding) Winding_Free(newface->face_winding);
                    newface->face_winding = Winding_Clone(&tmpw);
                    //get the texture
                    newface->d_texture = Texture_ForName( newface->texdef.name );
                    //add the face to the brush
                    newface->next = b->brush_faces;
                    b->brush_faces = newface;
                    //
                    movefacepoints[nummovefaces] = 1;
                    movefaces[nummovefaces++] = newface;
                }
                break;
            }
        }
    }
    //now movefaces contains pointers to triangle faces that
    //contain the to be moved vertex

    //move the vertex
    for (i = 0; i < nummovefaces; i++)
    {
        //move vertex to end position
        VectorCopy(end, movefaces[i]->face_winding->points[movefacepoints[i]]);
        //create new face plane
        for (j = 0; j < 3; j++)
        {
            VectorCopy(movefaces[i]->face_winding->points[j], movefaces[i]->planepts[j]);
        }
        Face_MakePlane(movefaces[i]);
    }
    //if the brush is no longer convex
    if (!Brush_Convex(b))
    {
        for (i = 0; i < nummovefaces; i++)
        {
            //move the vertex back to the initial position
            VectorCopy(vertex, movefaces[i]->face_winding->points[movefacepoints[i]]);
            //create new face plane
            for (j = 0; j < 3; j++)
            {
                VectorCopy(movefaces[i]->face_winding->points[j], movefaces[i]->planepts[j]);
            }
            Face_MakePlane(movefaces[i]);
        }
        result = false;
    }
    //get texture crap right
    for (i = 0; i < nummovefaces; i++)
    {
        Face_SetColor(b, movefaces[i], 1.0);
        for (j = 0; j < movefaces[i]->face_winding->numpoints; j++)
            EmitTextureCoordinates(movefaces[i]->face_winding->points[j], movefaces[i]->d_texture, movefaces[i]);
    }

    //now try to merge faces with their original faces
    lastface = NULL;
    for (face = b->brush_faces; face; face = nextface)
    {
        nextface = face->next;
        if (!face->original)
        {
            lastface = face;
            continue;
        }
        if (!Plane_Equal(&face->plane, &face->original->plane, false))
        {
            lastface = face;
            continue;
        }
        w = Winding_TryMerge(face->face_winding, face->original->face_winding, face->plane.normal, true);
        if (!w)
        {
            lastface = face;
            continue;
        }
        Winding_Free(face->original->face_winding);
        face->original->face_winding = w;
        //get texture crap right
        Face_SetColor(b, face->original, 1.0);
        for (j = 0; j < face->original->face_winding->numpoints; j++)
            EmitTextureCoordinates(face->original->face_winding->points[j], face->original->d_texture, face->original);
        //remove the face that was merged with the original
        if (lastface) lastface->next = face->next;
        else b->brush_faces = face->next;
        Face_Free(face);
    }
    return result;
}

/*
=================
Brush_MoveVertexes

- The input brush must be convex
- The input brush must have face windings.
- The output brush will be convex.
- Returns true if the WHOLE vertex movement is performed.
=================
*/

#define MAX_MOVE_FACES      64

int Brush_MoveVertex(brush_t *b, vec3_t vertex, vec3_t delta, vec3_t end, bool bSnap)
{
    face_t *f, *face, *newface, *lastface, *nextface;
    face_t *movefaces[MAX_MOVE_FACES];
    int movefacepoints[MAX_MOVE_FACES];
    winding_t *w, tmpw;
    vec3_t start, mid;
    plane_t plane;
    int i, j, k, nummovefaces, result, done;
    float dot, front, back, frac, smallestfrac;

    result = true;
    //
    tmpw.numpoints = 3;
    tmpw.maxpoints = 3;
    VectorCopy(vertex, start);
    VectorAdd(vertex, delta, end);
    //snap or not?
    if (bSnap)
        for (i = 0; i < 3; i++)
            end[i] = floor(end[i] / g_qeglobals.d_gridsize + 0.5) * g_qeglobals.d_gridsize;
    //
    VectorCopy(end, mid);
    //if the start and end are the same
    if (Point_Equal(start, end, 0.3)) return false;
    //the end point may not be the same as another vertex
    for (face = b->brush_faces; face; face = face->next)
    {
        w = face->face_winding;
        if (!w) continue;
        for (i = 0; i < w->numpoints; i++)
        {
            if (Point_Equal(w->points[i], end, 0.3))
            {
                VectorCopy(vertex, end);
                return false;
            }
        }
    }
    //
    done = false;
    while(!done)
    {
        //chop off triangles from all brush faces that use the to be moved vertex
        //store pointers to these chopped off triangles in movefaces[]
        nummovefaces = 0;
        for (face = b->brush_faces; face; face = face->next)
        {
            w = face->face_winding;
            if (!w) continue;
            for (i = 0; i < w->numpoints; i++)
            {
                if (Point_Equal(w->points[i], start, 0.2))
                {
                    if (face->face_winding->numpoints <= 3)
                    {
                        movefacepoints[nummovefaces] = i;
                        movefaces[nummovefaces++] = face;
                        break;
                    }
                    dot = DotProduct(end, face->plane.normal) - face->plane.dist;
                    //if the end point is in front of the face plane
                    if (dot > 0.1)
                    {
                        //fanout triangle subdivision
                        for (k = i; k < i + w->numpoints-3; k++)
                        {
                            VectorCopy(w->points[i], tmpw.points[0]);
                            VectorCopy(w->points[(k+1) % w->numpoints], tmpw.points[1]);
                            VectorCopy(w->points[(k+2) % w->numpoints], tmpw.points[2]);
                            //
                            newface = Face_Clone(face);
                            //get the original
                            for (f = face; f->original; f = f->original) ;
                            newface->original = f;
                            //store the new winding
                            if (newface->face_winding) Winding_Free(newface->face_winding);
                            newface->face_winding = Winding_Clone(&tmpw);
                            //get the texture
                            newface->d_texture = Texture_ForName( newface->texdef.name );
                            //add the face to the brush
                            newface->next = b->brush_faces;
                            b->brush_faces = newface;
                            //add this new triangle to the move faces
                            movefacepoints[nummovefaces] = 0;
                            movefaces[nummovefaces++] = newface;
                        }
                        //give the original face a new winding
                        VectorCopy(w->points[(i-2+w->numpoints) % w->numpoints], tmpw.points[0]);
                        VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[1]);
                        VectorCopy(w->points[i], tmpw.points[2]);
                        Winding_Free(face->face_winding);
                        face->face_winding = Winding_Clone(&tmpw);
                        //add the original face to the move faces
                        movefacepoints[nummovefaces] = 2;
                        movefaces[nummovefaces++] = face;
                    }
                    else
                    {
                        //chop a triangle off the face
                        VectorCopy(w->points[(i-1+w->numpoints) % w->numpoints], tmpw.points[0]);
                        VectorCopy(