diff options
Diffstat (limited to 'tool_src/BspLib/Polygon.h')
| -rw-r--r-- | tool_src/BspLib/Polygon.h | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/tool_src/BspLib/Polygon.h b/tool_src/BspLib/Polygon.h new file mode 100644 index 0000000..d83de32 --- /dev/null +++ b/tool_src/BspLib/Polygon.h @@ -0,0 +1,280 @@ +//----------------------------------------------------------------------------- +// BSPLIB HEADER: Polygon.h +// +// Copyright (c) 1996-1998 by Markus Hadwiger +// All Rights Reserved. +//----------------------------------------------------------------------------- + +#ifndef _POLYGON_H_ +#define _POLYGON_H_ + +// bsplib header files +#include "BspLibDefs.h" +#include "Chunk.h" +#include "Face.h" +#include "Plane.h" +#include "SystemIO.h" + + +BSPLIB_NAMESPACE_BEGIN + + +class BoundingBox; + + +// vertex index (element of vertex index list) -------------------------------- +// +class VIndx { + +public: + VIndx( int indx = -1, VIndx *next = NULL ) { vertindx = indx; nextvertindx = next; } + ~VIndx() { delete nextvertindx; } + + int getIndx() const { return vertindx; } + void setIndx( int indx ) { vertindx = indx; } + + VIndx* getNext() const { return nextvertindx; } + void setNext( VIndx *next ) { nextvertindx = next; } + +private: + int vertindx; // -1 means end of list, regardless of nextvertindx + VIndx* nextvertindx; // pointer to next VIndx in singly linked list +}; + + +class BSPNode; +class BspObject; + + +// single polygon (element of polygon list) ----------------------------------- +// +class Polygon : public virtual SystemIO { + + friend class PolygonListRep; + + void Error() const; + + // possible classifications of polygon with respect to splitting plane + enum { + POLY_IN_FRONT_SUBSPACE, + POLY_IN_BACK_SUBSPACE, + POLY_STRADDLES_SPLITTER, + POLY_IN_SAME_PLANE, + }; + + // frontsubspace/backsubspace identifiers + enum { + FRONT_SUBSPACE = 1, + BACK_SUBSPACE = -1 + }; + +public: + + // splitter selection criteria + enum { + SPLITTERCRIT_FIRST_POLY = 0x0000, // always choose first polygon in list + SPLITTERCRIT_SAMPLE_FIRST_N = 0x0101, // test first n polygons in list + SPLITTERCRIT_SAMPLE_ALL = 0x0002, // test entire list and choose best + SPLITTERCRIT_RANDOM_SAMPLE = 0x0103, // sample n polygons randomly + SPLITTERCRITMASK_SAMPLESIZ = 0x0100, // flagmask if samplesize (n) needed + }; + + // message flags + enum { + MESSAGE_SPLITTING_POLYGON = 0x0001, + MESSAGE_STARTVERTEX_IN_SPLITTER_PLANE = 0x0002, + MESSAGE_VERTEX_IN_SPLITTER_PLANE = 0x0004, + MESSAGE_NEW_SPLITVERTEX = 0x0008, + MESSAGE_REUSING_SPLITVERTEX = 0x0010, + MESSAGE_TRACEVERTEX_INSERTED = 0x0020, + MESSAGE_SPLITTING_QUADRILATERAL = 0x0040, + MESSAGE_INVOCATION = 0x0080, + MESSAGE_CHECKING_POLYGON_PLANES = 0x0100, + MESSAGEMASK_DISPLAY_ALL = 0xffff + }; + +public: + Polygon( BspObject *bobj, int pno = 0, int fno = 0, Polygon *next = NULL, int num = 1 ); + ~Polygon() { delete vertindxs; delete nextpolygon; } + + Polygon* NewPolygon(); // create new polygon with sequential id as head of list + Polygon* InsertPolygon( Polygon *poly ); // insert existing polygon as head of list + Polygon* DeleteHead(); // delete this, return rest of list (DANGEROUS!) + Polygon* FindPolygon( int id ); // return polygon in list having specified id + int SumVertexNumsEntireList(); // sum up vertex numbers for all polygons of list + + void PrependNewVIndx( int indx ); // create new VIndx and prepend it to list (vertindxs) + void AppendNewVIndx( int indx = -1 ); // create new VIndx and append it to list (vertindxs) + void AppendVIndx( VIndx *vindx ); // append existing VIndx to list (vertindxs) + VIndx* UnlinkLastVIndx(); // return last VIndx in list after unlinking it + + void CalcPlaneNormals(); // calc normals for all polygons in list + void CheckEdges(); // check edges for contained vertices (scans list!) + Polygon* CheckPlanesAndMappings(); // check planes and mappings of all polygons in list + + // calculate bounding box encompassing all polygons in list + void CalcBoundingBox( BoundingBox* &boundingbox ); + + // classify polygon with respect to this polygon + int CheckIntersection( Polygon *testpoly ); + // check if other polygon's normal is contained in this one's positive halfspace (predicate) + int NormalDirectionSimilar( Polygon *testpoly ); + // split other polygon along this polygon; insert split pieces into their respective halfspaces + void SplitPolygon( Polygon *poly, Polygon* &frontsubspace, Polygon* &backsubspace ); + // partition space encompassing entire polygon list; return created BSP tree's root + BSPNode* PartitionSpace(); + + // correct numberings (polygon-id, face-id, and vertex indexes) to new base + void CorrectBase( BspObject *newbaseobj, int vertexindxbase, int faceidbase, int polygonidbase ); + void CorrectBaseByTable( BspObject *newbaseobj, int *vtxindxmap, int faceidbase, int polygonidbase ); + + int getId() const { return polygonno; } + void setId( int pno ) { polygonno = pno; } + + int getFaceId() const { return faceno; } + void setFaceId( int fno ) { faceno = fno; } + + int getNumPolygons() const { return numpolygons; } + void setNumPolygons( int len ) { numpolygons = len; } + + Polygon* getNext() const { return nextpolygon; } + void setNext( Polygon *next ) { nextpolygon = next; } + + int getNumVertices() const { return numvertindxs; } + + VIndx* getVList() const { return vertindxs; } + BspObject* getBaseObject() const { return baseobject; } + + VertexChunk& getVertexList(); + FaceChunk& getFaceList(); + + int HasArea() const; + + int getFirstVertexIndx() const; + int getSecondVertexIndx() const; + int getThirdVertexIndx() const; + + Vertex3 getFirstVertex() const; + Vertex3 getSecondVertex() const; + Vertex3 getThirdVertex() const; + + Plane getPlane() const { return ((Polygon *const)this)->getFaceList()[ faceno ].getPlane(); } + Vector3 getPlaneNormal() const { return ((Polygon *const)this)->getFaceList()[ faceno ].getPlaneNormal(); } + + void FillVertexIndexArray( dword *arr ) const; // write list of vertices into array + void WriteVertexList( FILE *fp, int cr ) const; // write list of vertices to file + void WritePolyList( FILE *fp ) const; // write list of polygon ids to file + + int CalcSplitterTestProbability(); + +public: + static int getSplitterSelection() { return splitter_crit; } + static void setSplitterSelection( int criterion ) { splitter_crit = criterion; } + + static int getSampleSize() { return sample_size; } + static void setSampleSize( int siz ) { sample_size = siz; } + + static int getTriangulationFlag() { return triangulate_all; } + static void setTriangulationFlag( int flag ) { triangulate_all = flag; } + + static int getNormalizeVectorsFlag() { return normalize_vectors; } + static void setNormalizeVectorsFlag( int flag ) { normalize_vectors = flag; } + + static int getDisplayMessagesFlag() { return display_messages; } + static void setDisplayMessagesFlag( int flag ) { display_messages = flag; } + + static void ResetCallCount() { partition_callcount = 0; } + +private: + static int splitter_crit; // splitter selection criterion to use + static int sample_size; // sample size for splitter sampling + static int triangulate_all; // triangulate polygons with more than three vertices + static int normalize_vectors; // always normalize direction vectors + static int display_messages; // display a message every time PartitionSpace() is invoked + static int partition_callcount;// call counter for PartitionSpace() + static int test_probability; // probability to test single polygon if SPLITTERCRIT_RANDOM_SAMPLE + static char str_scratchpad[]; // string scratch pad + +private: + int polygonno; // global number of this polygon + int faceno; // global number of face this polygon is contained in + int numpolygons; // length of singly linked polygon list + int numvertindxs; // number of entries in vertex index list attached to this polygon + VIndx* vertindxs; // pointer to first VIndx + VIndx* vindxinsertpos; // pointer to last VIndx (NULL means insert-position is at head) + BspObject* baseobject; // pointer to object this polygon belongs to + Polygon* nextpolygon; // pointer to next polygon in list +}; + +// determine if the polygon has area ------------------------------------------ +inline int Polygon::HasArea() const +{ + // collinear vertices are not checked here, the polygon need only have + // at least three vertices to count as having area! + return ( vertindxs && vertindxs->getNext() && vertindxs->getNext()->getNext() ); +} + +// get first vertex of polygon ------------------------------------------------ +inline int Polygon::getFirstVertexIndx() const +{ + CHECK_DEREFERENCING( + if ( vertindxs == NULL ) + Error(); + ); + return vertindxs->getIndx(); +} +inline Vertex3 Polygon::getFirstVertex() const +{ + CHECK_DEREFERENCING( + if ( vertindxs == NULL ) + Error(); + ); + return ((Polygon *const)this)->getVertexList()[ vertindxs->getIndx() ]; +} + +// get second vertex of polygon ----------------------------------------------- +inline int Polygon::getSecondVertexIndx() const +{ + CHECK_DEREFERENCING( + if ( ( vertindxs == NULL ) || ( vertindxs->getNext() == NULL ) ) + Error(); + ); + return vertindxs->getNext()->getIndx(); +} +inline Vertex3 Polygon::getSecondVertex() const +{ + CHECK_DEREFERENCING( + if ( ( vertindxs == NULL ) || ( vertindxs->getNext() == NULL ) ) + Error(); + ); + return ((Polygon *const)this)->getVertexList()[ vertindxs->getNext()->getIndx() ]; +} + +// get third vertex of polygon ------------------------------------------------ +inline int Polygon::getThirdVertexIndx() const +{ + CHECK_DEREFERENCING( + if ( ( vertindxs == NULL ) || + ( vertindxs->getNext() == NULL ) || + ( vertindxs->getNext()->getNext() == NULL ) ) + Error(); + ); + return vertindxs->getNext()->getNext()->getIndx(); +} +inline Vertex3 Polygon::getThirdVertex() const +{ + CHECK_DEREFERENCING( + if ( ( vertindxs == NULL ) || + ( vertindxs->getNext() == NULL ) || + ( vertindxs->getNext()->getNext() == NULL ) ) + Error(); + ); + return ((Polygon *const)this)->getVertexList()[ vertindxs->getNext()->getNext()->getIndx() ]; +} + + +BSPLIB_NAMESPACE_END + + +#endif // _POLYGON_H_ + |