meshmdl.cpp

Go to the documentation of this file.

/*
**  Command & Conquer Generals Zero Hour(tm)
**  Copyright 2025 Electronic Arts Inc.
**
**  This program 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 3 of the License, or
**  (at your option) any later version.
**
**  This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
*/
 
/***********************************************************************************************
 ***              C O N F I D E N T I A L  ---  W E S T W O O D  S T U D I O S               ***
 ***********************************************************************************************
 *                                                                                             *
 *                 Project Name : WW3D                                                         *
 *                                                                                             *
 *                     $Archive:: /Commando/Code/ww3d2/meshmdl.cpp                            $*
 *                                                                                             *
 *                    Org Author:: Greg Hjelstrom                                               *
 *                                                                                             *
 *                      $Author:: Kenny Mitchell                                               * 
 *                                                                                             * 
 *                     $Modtime:: 06/26/02 4:04p                                             $*
 *                                                                                             *
 *                    $Revision:: 48                                                          $*
 *                                                                                             *
 * 06/26/02 KM Matrix name change to avoid MAX conflicts                                       *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 
#include "meshmdl.h"
#include "matinfo.h"
#include "aabtree.h"
#include "htree.h"
#include "vp.h"
#include "visrasterizer.h"
#include "dx8polygonrenderer.h"
#include "bwrender.h"
#include "camera.h"
#include "dx8renderer.h"
#include "hashtemplate.h"
 
 
/*
** Temporary Buffers
** These buffers are used by the skin code for temporary storage of the deformed vertices and 
** vertex normals.  
*/
static DynamicVectorClass<Vector3>   _TempVertexBuffer;
static DynamicVectorClass<Vector3>   _TempNormalBuffer;
static DynamicVectorClass<Vector4>   _TempTransformedVertexBuffer;
static DynamicVectorClass<unsigned long> _TempClipFlagBuffer;
 
 
/*
**
** MeshModelClass Implementation
**
*/
 
 
MeshModelClass::MeshModelClass(void) :
    DefMatDesc(NULL),
    AlternateMatDesc(NULL),
    CurMatDesc(NULL),
    MatInfo(NULL),
    GapFiller(NULL)
{
    Set_Flag(DIRTY_BOUNDS,true);
 
    DefMatDesc = W3DNEW MeshMatDescClass;
    CurMatDesc = DefMatDesc;
    
    MatInfo = NEW_REF( MaterialInfoClass, () );
    
    return ;
}
 
MeshModelClass::MeshModelClass(const MeshModelClass & that) :
    MeshGeometryClass(that),
    DefMatDesc(NULL),
    AlternateMatDesc(NULL),
    CurMatDesc(NULL),
    MatInfo(NULL),
    GapFiller(NULL),
    HasBeenInUse(false)
{
    DefMatDesc = W3DNEW MeshMatDescClass(*(that.DefMatDesc));
    if (that.AlternateMatDesc != NULL) {
        AlternateMatDesc = W3DNEW MeshMatDescClass(*(that.AlternateMatDesc));
    }
    CurMatDesc = DefMatDesc;
 
    clone_materials(that);
    return ;
}
 
MeshModelClass::~MeshModelClass(void)
{
//  WWDEBUG_SAY(("Note: Mesh %s was never used\n",Get_Name()));
    TheDX8MeshRenderer.Unregister_Mesh_Type(this);
 
    Reset(0,0,0);
    REF_PTR_RELEASE(MatInfo);
 
    if (DefMatDesc != NULL) {
        delete DefMatDesc;
    }
    if (AlternateMatDesc != NULL) {
        delete AlternateMatDesc;
    }
    return ;
}
 
MeshModelClass & MeshModelClass::operator = (const MeshModelClass & that)
{
    if (this != &that) {
        // Remove all polygon renderers, this will remove the mesh from the rendering system.
        // The mesh will be initialized to rendering system the next time it is rendered.
        TheDX8MeshRenderer.Unregister_Mesh_Type(this);
 
        MeshGeometryClass::operator = (that);
 
        *DefMatDesc = *(that.DefMatDesc);
        CurMatDesc = DefMatDesc;
 
        if (AlternateMatDesc != NULL) {
            delete AlternateMatDesc;
            AlternateMatDesc = NULL;
        }
 
        if (that.AlternateMatDesc != NULL) {
            AlternateMatDesc = W3DNEW MeshMatDescClass(*(that.AlternateMatDesc));
        }
 
        clone_materials(that);
 
        if (GapFiller) {
            // DMS - using approriate deallocation method
            delete GapFiller;
            GapFiller=NULL;
        }
        if (that.GapFiller) GapFiller=W3DNEW GapFillerClass(*that.GapFiller);
    }
    return * this;
}
 
void MeshModelClass::Reset(int polycount,int vertcount,int passcount)
{
    //DMS - We must delete the gapfiller object BEFORE the geometry is reset.  Otherwise,
    // the number of stages and passes gets reset and the gapfiller cannot deallocate properly.
    delete GapFiller;
    GapFiller=NULL;
 
    Reset_Geometry(polycount,vertcount);
 
    // Release everything we have and reset to initial state
 
    TheDX8MeshRenderer.Unregister_Mesh_Type(this);
 
    MatInfo->Reset();
    DefMatDesc->Reset(polycount,vertcount,passcount);
    if (AlternateMatDesc != NULL) {
        delete AlternateMatDesc;
        AlternateMatDesc = NULL;
    }
    CurMatDesc = DefMatDesc;
 
    return ;
}
 
void MeshModelClass::Register_For_Rendering()
{
    HasBeenInUse=true;
//WW3D::Set_NPatches_Level(1);
    if (WW3D::Get_NPatches_Level()>1) {
        if (WW3D::Get_NPatches_Gap_Filling_Mode()!=WW3D::NPATCHES_GAP_FILLING_DISABLED) {
            Init_For_NPatch_Rendering();
        }
        else if (GapFiller) {
            delete GapFiller;
            GapFiller=NULL;
        }
    }
    else {
        if (WW3D::Get_NPatches_Gap_Filling_Mode()==WW3D::NPATCHES_GAP_FILLING_FORCE) {
            Init_For_NPatch_Rendering();
        }
        else if (GapFiller) {
            delete GapFiller;
            GapFiller=NULL;
        }
    }
 
    TheDX8MeshRenderer.Register_Mesh_Type(this);
}
 
void MeshModelClass::Replace_Texture(TextureClass* texture,TextureClass* new_texture)
{
    WWASSERT(texture);
    WWASSERT(new_texture);
    for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
        for (int pass=0;pass<Get_Pass_Count();++pass) {
            if (Has_Texture_Array(pass,stage)) {
                for (int i=0;i<Get_Polygon_Count();++i) {
                    if (Peek_Texture(i,pass,stage)==texture) {
                        Set_Texture(i,new_texture,pass,stage);
                    }
                }
            }
            else {
                if (Peek_Single_Texture(pass,stage)==texture) {
                    Set_Single_Texture(new_texture,pass,stage);
                }
            }
            // If this mesh model has been initialized for rendering we need to tell the rendering
            // system to change texturing as well.
            DX8FVFCategoryContainer* fvf_category=Peek_FVF_Category_Container();
            if (fvf_category) {
                fvf_category->Change_Polygon_Renderer_Texture(PolygonRendererList,texture,new_texture,pass,stage);
            }
        }
    }
}
 
void MeshModelClass::Replace_VertexMaterial(VertexMaterialClass* vmat,VertexMaterialClass* new_vmat)
{
    WWASSERT(vmat);
    WWASSERT(new_vmat);
    
    for (int pass=0;pass<Get_Pass_Count();++pass) {
        if (Has_Material_Array(pass)) {
            for (int i=0;i<Get_Vertex_Count();++i) {
                if (Peek_Material(i,pass)==vmat) {
                    Set_Material(i,new_vmat,pass);
                }
            }
        }
        else {
            if (Peek_Single_Material(pass)==vmat) {
                Set_Single_Material(new_vmat,pass);
            }
        }
        // If this mesh model has been initialized for rendering we need to tell the rendering
        // system to change texturing as well.
        DX8FVFCategoryContainer* fvf_category=Peek_FVF_Category_Container();
        if (fvf_category) {
            fvf_category->Change_Polygon_Renderer_Material(PolygonRendererList,vmat,new_vmat,pass);
        }
    }   
}
 
DX8FVFCategoryContainer* MeshModelClass::Peek_FVF_Category_Container()
{
    if (PolygonRendererList.Is_Empty()) return NULL;
    DX8PolygonRendererClass* polygon_renderer=PolygonRendererList.Get_Head();
    WWASSERT(polygon_renderer);
    DX8TextureCategoryClass* texture_category=polygon_renderer->Get_Texture_Category();
    WWASSERT(texture_category);
    DX8FVFCategoryContainer* fvf_category=texture_category->Get_Container();
    WWASSERT(fvf_category);
    return fvf_category;
}
 
void MeshModelClass::Shadow_Render(SpecialRenderInfoClass & rinfo,const Matrix3D & tm,const HTreeClass * htree)
{
    if (rinfo.BWRenderer != NULL) {
        if (_TempTransformedVertexBuffer.Length() < VertexCount) _TempTransformedVertexBuffer.Resize(VertexCount);
        Vector4* transf_ptr=&(_TempTransformedVertexBuffer[0]);
        get_deformed_screenspace_vertices(transf_ptr,rinfo,tm,htree);
 
        Vector2* tptr = reinterpret_cast<Vector2 *>(transf_ptr);
        Vector4* optr = transf_ptr;
        for (int a=0;a<VertexCount;++a,++optr) *tptr++=Vector2((*optr)[0],-(*optr)[1]);
 
        rinfo.BWRenderer->Set_Vertex_Locations(reinterpret_cast<Vector2*>(transf_ptr),VertexCount);
        rinfo.BWRenderer->Render_Triangles(reinterpret_cast<const unsigned long*>(Poly->Get_Array()),PolyCount*3);
        return;
    }
}
 
void MeshModelClass::Make_Geometry_Unique()
{
    WWASSERT(Vertex);
 
    ShareBufferClass<Vector3> * unique_verts = NEW_REF(ShareBufferClass<Vector3>,(*Vertex));
    REF_PTR_SET(Vertex,unique_verts);
    REF_PTR_RELEASE(unique_verts);
    
    ShareBufferClass<Vector3> * norms = NEW_REF(ShareBufferClass<Vector3>,(*VertexNorm));
    REF_PTR_SET(VertexNorm,norms);
    REF_PTR_RELEASE(norms);
 
#if (!OPTIMIZE_PLANEEQ_RAM)
    ShareBufferClass<Vector4> * peq = NEW_REF(ShareBufferClass<Vector4>,(*PlaneEq, "MeshModelClass::PlaneEq")); 
    REF_PTR_SET(PlaneEq,peq);
    REF_PTR_RELEASE(peq);
#endif
}
 
void MeshModelClass::Make_UV_Array_Unique(int pass,int stage)
{
    CurMatDesc->Make_UV_Array_Unique(pass,stage);
}
 
void MeshModelClass::Make_Color_Array_Unique(int array_index)
{
    CurMatDesc->Make_Color_Array_Unique(array_index);
}
 
void MeshModelClass::Enable_Alternate_Material_Description(bool onoff)
{
    if ((onoff == true) && (AlternateMatDesc != NULL)) {
        if (CurMatDesc != AlternateMatDesc) {
            CurMatDesc = AlternateMatDesc;
            
            if (Get_Flag(SORT) && WW3D::Is_Munge_Sort_On_Load_Enabled())
                compute_static_sort_levels();
 
            if (WW3D::Is_Overbright_Modify_On_Load_Enabled())
                modify_for_overbright();
            
            // TODO: Invalidate just this meshes DX8 data!!!
            TheDX8MeshRenderer.Invalidate();
        }
    } else {
        if (CurMatDesc != DefMatDesc) {
            CurMatDesc = DefMatDesc;
 
            if (Get_Flag(SORT) && WW3D::Is_Munge_Sort_On_Load_Enabled())
                compute_static_sort_levels();
 
            if (WW3D::Is_Overbright_Modify_On_Load_Enabled())
                modify_for_overbright();
 
            // TODO: Invalidate this meshes DX8 data!!!
            TheDX8MeshRenderer.Invalidate();
        }
    }
}
 
bool MeshModelClass::Is_Alternate_Material_Description_Enabled(void)
{
    return CurMatDesc == AlternateMatDesc;
}
/*
void MeshModelClass::Process_Texture_Reduction(void)
{
    MatInfo->Process_Texture_Reduction();
}
*/
bool MeshModelClass::Needs_Vertex_Normals(void)
{
    if (Get_Flag(MeshModelClass::PRELIT_MASK) == 0) {
        return true;
    }
    return CurMatDesc->Do_Mappers_Need_Normals();
}
 
struct TriangleSide
{
    Vector3 loc1;
    Vector3 loc2;
    TriangleSide(const Vector3& l1,const Vector3& l2)
    {
        int i1=*(int*)&l1[0];
        i1=37*i1+*(int*)&l1[1];
        i1=37*i1+*(int*)&l1[2];
        int i2=*(int*)&l2[0];
        i2=37*i2+*(int*)&l2[1];
        i2=37*i2+*(int*)&l2[2];
        if (i1<i2) {
            loc1=l1;
            loc2=l2;
        }
        else {
            loc2=l1;
            loc1=l2;
        }
    }
    TriangleSide() {}
 
    bool operator== (const TriangleSide& s) 
    {
        unsigned i=*(unsigned*)&loc1[0]^*(unsigned*)&s.loc1[0];
        i|=*(unsigned*)&loc1[1]^*(unsigned*)&s.loc1[1];
        i|=*(unsigned*)&loc1[2]^*(unsigned*)&s.loc1[2];
        i|=*(unsigned*)&loc2[0]^*(unsigned*)&s.loc2[0];
        i|=*(unsigned*)&loc2[1]^*(unsigned*)&s.loc2[1];
        i|=*(unsigned*)&loc2[2]^*(unsigned*)&s.loc2[2];
        return !i;
    }
};
 
// Get_Hash_Value specialization for Vector3.
 
template <> inline unsigned int HashTemplateKeyClass<Vector3>::Get_Hash_Value(const Vector3& location)
{
    const unsigned char* buffer=(const unsigned char*)&location;
    unsigned int hval=0;
    for (unsigned int a=0;a<sizeof(Vector3);++a) {
        hval+=37*hval+buffer[a];
    }
    return hval;
}
 
// Get_Hash_Value specialization for TriangleSide.
 
template <> inline unsigned int HashTemplateKeyClass<TriangleSide>::Get_Hash_Value(const TriangleSide& side)
{
    const unsigned char* buffer=(const unsigned char*)&side;
    unsigned int hval=0;
    for (unsigned int a=0;a<sizeof(TriangleSide);++a) {
        hval+=37*hval+buffer[a];
    }
    return hval;
}
 
struct SideIndexInfo
{
    unsigned short vidx1;
    unsigned short vidx2;
    unsigned polygon_index;
    SideIndexInfo() {}
    SideIndexInfo(int i) { WWASSERT(0); }
};
 
 
HashTemplateClass<Vector3, unsigned> LocationHash;
HashTemplateClass<Vector3, unsigned> DuplicateLocationHash;
HashTemplateClass<TriangleSide,SideIndexInfo> SideHash;
 
// ----------------------------------------------------------------------------
//
// Allocate a gap-filler object. The constructor allocates memory for the
// maximum possible amount of gap polygons, which is quite much. After all
// the gap polygons have been added to the arrays, Shrink_Arrays() should
// be called to free up all unneeded memory.
//
// ----------------------------------------------------------------------------
 
GapFillerClass::GapFillerClass(MeshModelClass* mmc_) : mmc(NULL), PolygonCount(0)
{
    //DMS - We cannot take a reference to the mesh model here!  This is because the mesh model
    // class OWNS the GapFiller class (allocated via NEW).  If we take a reference here, there
    // will be an extra reference on the parent object, which will result in the parent object
    // not being destroyed.
    //
//  REF_PTR_SET(mmc,mmc_);
    mmc = mmc_;
 
    ArraySize=mmc->Get_Polygon_Count()*6;  // Each side of each triangle can have 2 polygons added, in the worst case
    PolygonArray=W3DNEWARRAY TriIndex[ArraySize];
    for (int pass=0;pass<mmc->Get_Pass_Count();++pass) {
        for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
            if (mmc->Has_Texture_Array(pass,stage)) {
                TextureArray[pass][stage]=W3DNEWARRAY TextureClass*[ArraySize];
            }
            else TextureArray[pass][stage]=NULL;
        }
 
        if (mmc->Has_Material_Array(pass)) {
            MaterialArray[pass]=W3DNEWARRAY VertexMaterialClass*[ArraySize];
        }
        else MaterialArray[pass]=NULL;
 
        if (mmc->Has_Shader_Array(pass)) {
            ShaderArray[pass]=W3DNEWARRAY ShaderClass[ArraySize];
        }
        else ShaderArray[pass]=NULL;
    }
}
 
GapFillerClass::GapFillerClass(const GapFillerClass& that) : mmc(NULL), PolygonCount(that.PolygonCount)
{
    //DMS - We cannot take a reference to the mesh model here!  This is because the mesh model
    // class OWNS the GapFiller class (allocated via NEW).  If we take a reference here, there
    // will be an extra reference on the parent object, which will result in the parent object
    // not being destroyed.
    //
//  REF_PTR_SET(mmc,that.mmc);
    mmc = that.mmc;
 
    ArraySize=that.ArraySize;
    PolygonArray=W3DNEWARRAY TriIndex[ArraySize];
    for (int pass=0;pass<mmc->Get_Pass_Count();++pass) {
        for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
            if (that.TextureArray[pass][stage]) {
                TextureArray[pass][stage]=W3DNEWARRAY TextureClass*[ArraySize];
                for (unsigned i=0;i<PolygonCount;++i) {
                    TextureArray[pass][stage][i]=that.TextureArray[pass][stage][i];
                    TextureArray[pass][stage][i]->Add_Ref();
                }
            }
            else TextureArray[pass][stage]=NULL;
        }
 
        if (that.MaterialArray[pass]) {
            MaterialArray[pass]=W3DNEWARRAY VertexMaterialClass*[ArraySize];
            for (unsigned i=0;i<PolygonCount;++i) {
                MaterialArray[pass][i]=that.MaterialArray[pass][i];
                MaterialArray[pass][i]->Add_Ref();
            }
        }
        else MaterialArray[pass]=NULL;
 
        if (that.ShaderArray[pass]) {
            ShaderArray[pass]=W3DNEWARRAY ShaderClass[ArraySize];
            for (unsigned i=0;i<PolygonCount;++i) {
                ShaderArray[pass][i]=that.ShaderArray[pass][i];
            }
        }
        else ShaderArray[pass]=NULL;
    }
}
 
// ----------------------------------------------------------------------------
//
// Destruct gap-filler object. Release references to all textures and release
// the arrays.
//
// ----------------------------------------------------------------------------
 
GapFillerClass::~GapFillerClass()
{
    delete[] PolygonArray;
 
    for (int pass=0;pass<mmc->Get_Pass_Count();++pass) {
        for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
            if (TextureArray[pass][stage]) {
 
                for (unsigned i=0;i<PolygonCount;++i) {
                    REF_PTR_RELEASE(TextureArray[pass][stage][i]);
                }
                delete[] TextureArray[pass][stage];
            }
        }
 
        if (MaterialArray[pass]) {
            for (unsigned i=0;i<PolygonCount;++i) {
                REF_PTR_RELEASE(MaterialArray[pass][i]);
            }
            delete[] MaterialArray[pass];
        }
 
        delete[] ShaderArray[pass];
    }
 
    // DMS - Removed - See constructor for details.
//  REF_PTR_RELEASE(mmc);
}
 
// ----------------------------------------------------------------------------
//
// Add polygon to gap filler.
//
// ----------------------------------------------------------------------------
 
void GapFillerClass::Add_Polygon(unsigned polygon_index,unsigned vidx1,unsigned vidx2, unsigned vidx3)
{
    WWASSERT(PolygonCount<ArraySize);
    WWASSERT(vidx1!=vidx2 && vidx1!=vidx3 && vidx2!=vidx3);
Vector3 loc1=mmc->Get_Vertex_Array()[vidx1];
Vector3 loc2=mmc->Get_Vertex_Array()[vidx2];
Vector3 loc3=mmc->Get_Vertex_Array()[vidx3];
WWASSERT(loc1==loc2 || loc1==loc3 || loc2==loc3);
//sdflksdjflsdkf
//vidx1=mmc->Get_Polygon_Array()[polygon_index][0];
//vidx2=mmc->Get_Polygon_Array()[polygon_index][1];
//vidx3=mmc->Get_Polygon_Array()[polygon_index][2];
 
    PolygonArray[PolygonCount]=TriIndex(vidx1,vidx2,vidx3);
    for (int pass=0;pass<mmc->Get_Pass_Count();++pass) {
        if (mmc->Has_Shader_Array(pass)) {
            ShaderArray[pass][PolygonCount]=mmc->Get_Shader(polygon_index,pass);
        }
        if (mmc->Has_Material_Array(pass)) {
//          MaterialArray[pass][PolygonCount]=mmc->Get_Material(polygon_index,pass);
            MaterialArray[pass][PolygonCount]=mmc->Get_Material(mmc->Get_Polygon_Array()[polygon_index][0],pass);
        }
        for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
            if (mmc->Has_Texture_Array(pass,stage)) {
                TextureArray[pass][stage][PolygonCount]=mmc->Get_Texture(polygon_index,pass,stage);
            }
        }
    }
    PolygonCount++;
}
 
// ----------------------------------------------------------------------------
//
// Resize buffers to match the polygon count exatly. After this call no more
// polygons can be added to the buffers.
//
// ----------------------------------------------------------------------------
 
void GapFillerClass::Shrink_Buffers()
{
    if (PolygonCount==ArraySize) return;
 
    // Shrink the polygon array
    TriIndex* new_polygon_array=W3DNEWARRAY TriIndex[PolygonCount];
    memcpy(new_polygon_array,PolygonArray,PolygonCount*sizeof(TriIndex));
    delete[] PolygonArray;
    PolygonArray=new_polygon_array;
 
    for (int pass=0;pass<mmc->Get_Pass_Count();++pass) {
        for (int stage=0;stage<MeshMatDescClass::MAX_TEX_STAGES;++stage) {
            if (TextureArray[pass][stage]) {
                // Shrink the texture array
                TextureClass** new_texture_array=W3DNEWARRAY TextureClass*[PolygonCount];
                memcpy(new_texture_array,TextureArray[pass][stage],PolygonCount*sizeof(TextureClass*));
                delete[] TextureArray[pass][stage];
                TextureArray[pass][stage]=new_texture_array;
            }
        }
 
        if (MaterialArray[pass]) {
            // Shrink the material array
            VertexMaterialClass** new_material_array=W3DNEWARRAY VertexMaterialClass*[PolygonCount];
            memcpy(new_material_array,MaterialArray[pass],PolygonCount*sizeof(VertexMaterialClass*));
            delete[] MaterialArray[pass];
            MaterialArray[pass]=new_material_array;
        }
 
        if (ShaderArray[pass]) {
            // Shrink the shader array
            ShaderClass* new_shader_array=W3DNEWARRAY ShaderClass[PolygonCount];
            memcpy(new_shader_array,ShaderArray[pass],PolygonCount*sizeof(ShaderClass));
            delete[] ShaderArray[pass];
            ShaderArray[pass]=new_shader_array;
        }
    }
    ArraySize=PolygonCount;
}
 
// ----------------------------------------------------------------------------
//
// Hard edges cause gaps to n-patches meshes. This code searches for hard edges
// and adds gaps filler polygons, using existing vertices.
//
// ----------------------------------------------------------------------------
 
void MeshModelClass::Init_For_NPatch_Rendering()
{
    if (!DX8Wrapper::Get_Current_Caps()->Support_NPatches()) return;
    if (!Get_Flag(MeshGeometryClass::ALLOW_NPATCHES)) return;
    if (GapFiller) return;
 
    const Vector3* locations=Get_Vertex_Array();
    unsigned vertex_count=Get_Vertex_Count();
    const TriIndex* polygon_indices=Get_Polygon_Array();
    unsigned polygon_count=Get_Polygon_Count();
 
    LocationHash.Remove_All();
    DuplicateLocationHash.Remove_All();
    SideHash.Remove_All();
 
    for (unsigned i=0;i<vertex_count;++i) {
        if (LocationHash.Exists(locations[i])) {
            if (!DuplicateLocationHash.Exists(locations[i])) {
                DuplicateLocationHash.Insert(locations[i],i);
            }
        }
        else {
            LocationHash.Insert(locations[i],i);
        }
    }
 
    for (i=0;i<polygon_count;++i) {
        bool duplicates[3];
        duplicates[0]=DuplicateLocationHash.Exists(locations[polygon_indices[i][0]]);
        duplicates[1]=DuplicateLocationHash.Exists(locations[polygon_indices[i][1]]);
        duplicates[2]=DuplicateLocationHash.Exists(locations[polygon_indices[i][2]]);
        if (duplicates[0] && duplicates[1]) {
            TriangleSide tri(locations[polygon_indices[i][0]],locations[polygon_indices[i][1]]);
            if (SideHash.Exists(tri)) {
                SideIndexInfo side_index=SideHash.Get(tri);
                unsigned idx1=side_index.vidx1;
                unsigned idx2=side_index.vidx2;
                unsigned idx3=polygon_indices[i][0];
                unsigned idx4=polygon_indices[i][1];
                bool diff=!(idx1^idx3)|!(idx1^idx4)|!(idx2^idx3)|!(idx2^idx4);
                if (!diff) {
                    if (!GapFiller) GapFiller=W3DNEW GapFillerClass(this);
                    GapFiller->Add_Polygon(i,idx4,idx2,idx1);
                    GapFiller->Add_Polygon(side_index.polygon_index,idx3,idx2,idx4);
                }
            }
            else {
                SideIndexInfo side_index;
                side_index.vidx1=polygon_indices[i][0];
                side_index.vidx2=polygon_indices[i][1];
                side_index.polygon_index=i;
                SideHash.Insert(tri,side_index);
            }
        }
        if (duplicates[1] && duplicates[2]) {
            TriangleSide tri(locations[polygon_indices[i][1]],locations[polygon_indices[i][2]]);
            if (SideHash.Exists(tri)) {
                SideIndexInfo side_index=SideHash.Get(tri);
                unsigned idx1=side_index.vidx1;
                unsigned idx2=side_index.vidx2;
                unsigned idx3=polygon_indices[i][1];
                unsigned idx4=polygon_indices[i][2];
                bool diff=!(idx1^idx3)|!(idx1^idx4)|!(idx2^idx3)|!(idx2^idx4);
                if (!diff) {
                    if (!GapFiller) GapFiller=W3DNEW GapFillerClass(this);
                    GapFiller->Add_Polygon(i,idx4,idx2,idx1);
                    GapFiller->Add_Polygon(side_index.polygon_index,idx3,idx2,idx4);
                }
            }
            else {
                SideIndexInfo side_index;
                side_index.vidx1=polygon_indices[i][1];
                side_index.vidx2=polygon_indices[i][2];
                side_index.polygon_index=i;
                SideHash.Insert(tri,side_index);
            }
        }
        if (duplicates[2] && duplicates[0]) {
            TriangleSide tri(locations[polygon_indices[i][2]],locations[polygon_indices[i][0]]);
            if (SideHash.Exists(tri)) {
                SideIndexInfo side_index=SideHash.Get(tri);
                unsigned idx1=side_index.vidx1;
                unsigned idx2=side_index.vidx2;
                unsigned idx3=polygon_indices[i][2];
                unsigned idx4=polygon_indices[i][0];
                bool diff=!(idx1^idx3)|!(idx1^idx4)|!(idx2^idx3)|!(idx2^idx4);
                if (!diff) {
                    if (!GapFiller) GapFiller=W3DNEW GapFillerClass(this);
                    GapFiller->Add_Polygon(i,idx4,idx2,idx1);
                    GapFiller->Add_Polygon(side_index.polygon_index,idx3,idx2,idx4);
                }
            }
            else {
                SideIndexInfo side_index;
                side_index.vidx1=polygon_indices[i][2];
                side_index.vidx2=polygon_indices[i][0];
                side_index.polygon_index=i;
                SideHash.Insert(tri,side_index);
            }
        }
    }
 
    LocationHash.Remove_All();
    DuplicateLocationHash.Remove_All();
    SideHash.Remove_All();
 
    if (GapFiller) GapFiller->Shrink_Buffers();
}