////////////////////////////////////////// ////////// hid.h 1995/06/01 ////////// ////////////////////////////////////////// #if !defined HID_H #define HID_H #include <fstream> #include <cstdlib> #include "diamond.h" #include "linetype.h" #include "parameter.h" #include "perspective.h" #include "list.h" #include "qsort.h" #include "tool2d.h" #include "tool3d.h" #include "vector.h" using namespace std ; //---------------------// //----- constants -----// //---------------------// //---------------------// //----- proto types -----// //---------------------// class Vertex2WithLineType ; class Polygon2D ; class Polygon3D ; class Hid ; //-------------------------------------// //----- class Vertex2WithLineType -----// //-------------------------------------// class Vertex2WithLineType { public: Vector2 position ; LineType* linetype ; Vector3* position3D_p ; int label ; public: //----- constructor 1 Vertex2WithLineType(void) : position() { linetype = NULL ; position3D_p = NULL ; label = -1 ;} //----- constructor 2 Vertex2WithLineType( Vector2& P, LineType* lt , Vector3* P3D_p = NULL , int label_given = -1 ) { position.x = P.x ; position.y = P.y ; linetype = lt ; position3D_p = P3D_p ; label = label_given ; } //----- operator = void operator=( const Vertex2WithLineType& rhs ) { position.x = (rhs.position).x ; position.y = (rhs.position).y ; linetype = rhs.linetype ; position3D_p = rhs.position3D_p ; label = rhs.label ; } }; // Vertex2WithLineType //-------------------------// //----- class Polygon2D -----// //-------------------------// class Polygon2D { public: ColorType* color ; //----- line types of edges LineType** edgeType ; //----- number of vertices int numVertex ; //----- vertex position in world coordinate, Vector2* vertex2D ; //----- object label int objectLabel ; //----- parent Polygon3D Polygon3D* parent3D_p ; public: //----- constructor 1 Polygon2D ( void ) ; //----- constructor 2 Polygon2D ( Vector2* position , LineType** linetype , int num , ColorType* color_p , int object_label , Polygon3D* parent_polygon3D_p ) ; //----- set data void set ( Vector2* vertex2D_given , LineType** edgeType_given , int numVertex_given , ColorType* color_p , int object_label , Polygon3D* parent_polygon3D_p ); //----- set data void set ( List<Vertex2WithLineType>& list_vlt , ColorType* color_p , int object_label , Polygon3D* parent_polygon3D_p ); //----- destructor ~Polygon2D () ; //----- clear all data members void clear(void); //----- copy //----- Polygon2D::opeartor = () void operator = ( const Polygon2D& rhs ); void operator = ( Polygon2D& rhs ); //----- remove zero-length edge if any //..... Return: number of vertices in resultant polygon int removeZeroLengthEdge( double epsilon = 1.0e-6 ); //----- int getObjectLabel() const { return objectLabel ; } int getNumVertex () const { return numVertex ; } Vector2* getVertex2D () { return vertex2D ; } ColorType* getColor () { return color ; } LineType** getEdgeType () { return edgeType ; } } ; // Polygon2D //-------------------------------// //----- type Polygon2D_p -----// //-------------------------------// typedef Polygon2D* Polygon2D_p ; //-------------------------// //----- class Polygon3D -----// //-------------------------// class Polygon3D { private: enum { DEFAULT_VERTEX_NUMBER = 4 } ; public: //----- integer label for general purpose int label ; //----- object label int objectLabel ; //----- facet label int facetLabel ; int* neighboringFacet ; int numNeighboringFacet ; int flag_convex ; //----- color ColorType color ; //----- line types of edges LineType** edgeType ; //----- number of vertices int numVertex ; //----- vertex position in world coordinate, Vector3** vertex ; Vector3* vertex3D ; // usually null //----- normal vector in world coordinate Vector3 normalVector; //----- vertex position in 2D screen coordinate Vector2* vertex2D ; //----- boxel ( in 3D screen coordinate ) double xmin, xmax ; double ymin, ymax ; double zmin, zmax ; double umin, umax ; // not used (initialization only ) double vmin, vmax ; // not used (initialization only ) //----- convex sub polyons //..... Expressed in 2D screen coord ( = viewport coord). List<Polygon2D> subPolygonList ; //----- data for root polygon (as a facet of object) Vector3* vertex3D_org ; LineType** edgeType_org ; int numVertex_org ; public: //----- constructor Polygon3D( void ); //----- desctuctor ~Polygon3D(){ this->clear() ; } //----- clear dynamical memories void clear(); //----- set all data members except for "label", "flag_convex", //..... and "subPolygonList" //..... * "subPolygonList" is cleared. //..... * If normal_vector_p == NULL, //..... member normalVector is automatically //..... calculated inside this function //..... * if vertex3D_given != NULL, vertex3D[]'s are set //..... and vertex[]'s are reset to their address. //..... //..... Return: error (0) or normal (1) //..... int set( Vector3** vertex_given , LineType** edgeType_given , int numVertex_given , ColorType color_given , Vector3* normal_vector_p , Perspective* camera_p , double epsilon3d , int object_label , int facet_label , int* neighboring_facet , int num_neighboring_facet_given , Vector3* vertex3D_given = NULL ) ; int set( List<Vertex2WithLineType>& list_vlt , ColorType color_given , Vector3* normal_vector_p , Perspective* camera_p , double epsilon3d , int object_label , int facet_label , int* neighboring_facet , int num_neighboring_facet_given , Vector3* vertex3D_given = NULL ) ; //----- own vertex position data by itself void setVertex3D(); //----- access functions void setLabel( int label_given ) { label = label_given ; } int getLabel () const { return label ; } int getObjectLabel () const { return objectLabel ; } int getFacetLabel () const { return facetLabel ; } ColorType getColor () const { return color ; } LineType** getEdgeType () const { return edgeType ; } const LineType& getEdgeType ( int index ) { return *(edgeType[index]) ; } int getNumVertex () const { return numVertex ; } Vector3** getVertex () const { return vertex ; } const Vector3& getVertex ( int index ) { return *(vertex[ index ]) ; } Vector3 getNormalVector () const { return normalVector ; } Vector2* getVertex2D () const { return vertex2D ; } const Vector2& getVertex2D ( int index ) { return vertex2D[ index ] ; } //----- convexity void setConvexity( int on_off ) { if( on_off == 0 ) { flag_convex = 0 ;} else { flag_convex = 1 ; } } int getConvexity() const { return flag_convex ; } //----- substitution void operator = ( const Polygon3D& rhs ) ; //----- set data members vertex2D, xmin, xmax, ymin, ymax, zmin, zmax //..... Return: error (0) or normal (1) int setImage( Perspective* camera_p, double epsilon = 1.0e-6 ); //----- set subPolygonList void setSubPolygonList(); //----- see if given polygon is neigboring one int isNeighborOf( const Polygon3D& polygon3d ) ; //----- removeZeroLengthImageEdge() int removeZeroLengthImageEdge( double epsilon2d , double epsilon3d , Perspective* camera_p ) ; //----- from2DTo3D() //..... Return: normal (1) or error (0) int from2DTo3D( const Polygon2D& polygon2d , Hid* hid_p, double epsilon3d ); //----- set vertex3D_org and numVertex_org //..... (data for original polygon as a facet of object) void setOriginalData( Vector3* vertex3D_given , LineType** edgetype_given, int num_vertex_given ); void setOriginalData( Vector3** vertex_given , LineType** edgetype_given, int num_vertex_given ); int isOriginalDataSet() const ; } ; // Polygon3D //-------------------------------// //----- type Polygon3D_p -----// //-------------------------------// typedef Polygon3D* Polygon3D_p ; //------------------------// //----- class Hid -----// //------------------------// class Hid { private: //---- const enum { NOT_HIDDEN2 = -1 , NOT_HIDDEN = 0 , HIDDEN = 1 }; enum { INDEPENDENT = 0 } ; //----- 3D data List<Polygon3D> polygon3DList ; List<Polygon3D> convexPolygon3DList ; int numPolygon3D ; Polygon3D* polygon3d ; List<Vector3> auxiliaryVertexPosition ; //----- 2D data int numPolygon2D ; Polygon2D* polygon2d ; //----- linetype for perforation line //..... Used in decomposition into convex polygon LineType perforationLineType ; //----- camera Perspective* camera_p ; Vector3 eyePosition ; //----- polygon label int polygon_counter ; //----- List<Polygon2D> polygon2DList; //----- bounding diamonds for parts of polygon2d[] int boundingDiamondInterval ; Diamond* boundingDiamondArray ; //----- int beginning_object_label_per_session ; int num_non_transparent_facet_per_session ; public: //----- Initialize parameters used in incremental hidden-surface removal void initializeIncrementalHid(); int getBeginningObjectLabelPerSession() const { return beginning_object_label_per_session ;} int getNumNonTransparentFacetPerSession() const { return num_non_transparent_facet_per_session ;} void setBeginningObjectLabelPerSession ( int label ) { beginning_object_label_per_session = label ;} void setNumNonTransparentFacetPerSession( int num ) { num_non_transparent_facet_per_session = num ;} //----- see if polygon a is hidden by polygon b //..... RETURN: //..... NOT_HIDDEN = 0 if P is not hidden by Q //..... NOT_HIDDEN2 = -1 if P is not hidden by Q, //..... and P.zmax < Q.zmin //..... HIDDEN = 1 if P may be hidden by Q int isHidden( Polygon2D* sub_a, Polygon3D_p a , Polygon3D_p b , int* relation_2d , double epsilon3d = 1.0e-6 , double epsilon2d = 1.0e-6 ); //----- max min test for 8 direction //..... Return //..... 0: if a is independent of b //..... on screen. //..... 1: else int maxMinTest( Polygon3D* a , Polygon3D* b , double epsilon2d = 1.0e-6 ) ; int maxMinTest( Polygon3D_p* a , Polygon3D_p* b , double epsilon2d = 1.0e-6 ) ; //----- Polygon3D::depthOverlapTest() //..... Depth overlapping test //..... Return //..... 1: if (*a)->zmax < (*b)->zmin. //..... -1: if (*b)->zmax < (*a)->zmin. //..... 0: else (ovrlaps in z direction) //..... (zmax, zmin are eye coordinate.) int depthOverlapTest( Polygon3D_p* a , Polygon3D_p* b , double epsilon3d = 1.0e-6 ) ; //------ relative position of polygons //..... Note: Available only if polygon( vertex3d, num_vertex) is //......included by or equal to *polygon_p //..... //..... Return: Tool3D::POSITIVE_SIDE, Tool3D::NEGATIVE_SIDE, Tool3D::UNKNOWN int includedPolygonVsPlaneTest( Vector3* vertex3d_a, Vector2* vertex2d_a , const Vector3& noraml_a , int num_vertex_a , const Vector3& normal_b, const Vector3& P_on_b , double epsilon3d = 1.0e-6 ); //----- included vertex points vs plane test //..... See if vertices of polygon a, which are included by polygon b is //..... in positive or negative side of plane b. //..... //..... Return: Tool3D::POSITIVE_SIDE, Tool3D::NEGATIVE_SIDE, Tool3D::UNKNOWN //..... //..... Argument: //..... vertex3d_a: 3-dim vertex positions of polygon a //..... vertex2d_a: 2-dim vertex positions of polygon a on screen //..... normal_a: normal vector of plane a including polygon a //..... num_vertex_a: number of vertices of polygon a //..... normal_b: normal vector of plane b including polygon b //..... P_on_b : an arbitrary position on plane b //..... vertex2d_b: 2-dim vertex positions of polygon b on screen //..... num_vertex_a: number of vertices of polygon b int crossedPolygonVsPlaneTest( Vector3* vertex3d_a, Vector2* vertex2d_a , const Vector3& normal_a , int num_vertex_a , const Vector3& normal_b , const Vector3& P_on_b, Vector2* vertex2d_b, int num_vertex_b, double epsilon3d = 1.0e-6 , double epsilon = 1.0e-6 ) ; //----- polygon-polygon test //..... -1 if polygon a is further from eye //..... 1 if polygon b is further from eye //..... 0 undecided //..... -2 images do not intersect on screen int polygonPolygonTest( Vector3* vertex3d_a, Vector2* vertex2d_a, int num_vertex_a, Polygon3D* b , int max_intersection, double epsilon3d = 1.0e-6 , double epsilon = 1.0e-6 ); //----- subtraction and devision to convex subpolygons: //..... a_polygon - b_polygon int hide_A( const Polygon2D& a_polygon, const Polygon2D& b_polygon, int b_polygon_label , List<Polygon2D>* output_list_p , List<int>* list_label_p , double epsilon = 1.0e-6 ); public: //----- constructor 1 Hid( Perspective* camera_p_given = NULL ); //----- destructor 1 ~Hid() { this->clear() ; } //----- clear all void clear() ; //----- clear polygon data //..... camera data etc are not cleared void clearPolygon(); //----- clear polygon lists void clearPolygon2DList() { polygon2DList.clear(); } void clearPolygon3DList() { polygon3DList.clear(); } void clearConvexPolygon3DList() { convexPolygon3DList.clear(); } void clearAuxiliaryVertexPositionList() { auxiliaryVertexPosition.clear(); } //----- clear polygon arrays void clearPolygon2DArray() { delete [] polygon2d ; polygon2d = NULL ; numPolygon2D = 0 ; } void clearPolygon3DArray() { delete [] polygon3d ; polygon3d = NULL ; numPolygon3D = 0 ; } //----- manipulation of polygon3DList int addItem_Polygon3DList ( Polygon3D& poly3d , int clipping_mode = 1 ) ; // mode_clipping = 0 ( no cllipping) // = 1 ( clipping) // = 2 ( landscape clipping) int getItem_Polygon3DList ( Polygon3D& poly3d ) ; int getNItem_Polygon3DList () ; void toTail_Polygon3DList () ; int upward_Polygon3DList () ; //----- convert list to array //..... Return: number of substituted items to Array. //..... Note: After this function is called, polygon3DList is cleared. int setPolygon3DToArray( List<Polygon3D>& polygon3d_list_given ) ; //----- install polygon3D array "polygon3d" void install(){ return ; } //----- set and get camera void setCamera( Perspective* camera_p_given ) ; Perspective* getCamera( ) { return camera_p ; } //----- get eye position Vector3 getEyePosition() { return eyePosition ; } //----- get number of items in array polygon3d int getNumPolygon3D(){ return numPolygon3D ;} //----- get label-th item in the array "polygon3d" Polygon3D& getPolygon3D( int label ) ; //----- get number of items in array polygon2d int getNumPolygon2D(){ return numPolygon2D ;} //----- get label-th item in the array "polygon2d" Polygon2D& getPolygon2D( int label ) ; //----- equivalent to getPolygon2D() Polygon2D& operator [] ( int label ) ; //----- point: viewport_coord ---> world coordinate inside given plane //..... Return: 0 if error, 1 if normal //..... Argument: //..... point2d: viewport coord ( 2-dim ) //..... normal : normal vector of plane, //..... P_on : a point on plane //..... point3d_p : output int point2DToPoint3D ( const Vector2& point2d, const Vector3& normal , const Vector3& P_on , Vector3* point3d_p , double epsilon3d = 1.0e-6 ); //----- get visible part of subpolygons and set them //..... to array "polygon2d" void extractVisiblePart( int beginning_object_label , int ending_object_label , double epsilon3d = 1.0e-6 , double epsilon = 1.0e-6 ); //----- perform hidden part elimination //..... Return: numPolygon2D //..... Note: After this function is called, polygon3DList is cleared. void doHiddenPartElimination( int beginning_object_label , int ending_object_label , double epsilon3d = 1.0e-6 , double epsilon = 1.0e-6 ); void doNotHiddenPartElimination( double epsilon3d = 1.0e-6 ) ; //----- convert polygon3DList to Polygon3DArray() //..... (1) Sorted //..... (2) Convexated //..... (2) polygon3DList is deleted void movePolygon3DListToArray( double epsilon3d , double epsilon2d ); //----- move polygonn2DList to polygon2d array //..... Polygon2DList is cleared. //..... Old data stored in polygon2d array is abandoned. int movePolygon2DListToArray(void) ; //----- Hid::removeZeroLengthEdge() //..... Return: number of vertices in resultant polygon int removeZeroLengthEdge( List<Vertex2WithLineType>& list_vlt , double epsilon = 1.0e-6 ); //----- get first convave vertex label //..... Return: vertex label ( if found ) //..... -1 ( if not found ) int getFirstConcaveVertex( List<Vertex2WithLineType>& list_vlt , double epsilon = 1.0e-6 ) ; //----- convexate Polygon3D //..... Return : num obtained convex polygon //..... WARNING: After the former function is called, //..... input_Polygon3D_list is int convexate( List<Polygon3D>& input_Polygon3D_list , List<Polygon3D>* output_Polygon3D_list_p , double epsilon3d = 1.0e-6 , double epsilon2d = 1.0e-6 ); int convexate( Polygon3D& polygon3D_input , List<Polygon3D>* output_Polygon3D_list_p , double epsilon3d = 1.0e-6 , double epsilon2d = 1.0e-6 ) ; void resetRemovedVertexForConvexation( const Polygon3D& polygon3D_input , List<Vertex2WithLineType>& list_vlt , double epsilon2d , double epsilon_nodim ) ; //----- Hid::halfLineVsPolygon() //..... get intersection "X" between halfline AB and //..... polygon list_vlt. //..... If plural intersections exist, the one with //..... mininum line parameter t_AB of halfline AB //..... is returned. //..... Arguments: //..... A: starting point of halfline AB //..... B: another point on halfline AB //..... list_vlt: polygon //..... starting_label: from here searching starts //..... max_search: searching is done until //..... starting_label + max_search -1 //.... *X_p: intersection if exists, //..... *t_AB_p: line paramater of intersection on halfline AB //..... ( t = 0 for A and t = 1 for B ) //..... *t_edge: line paramater of intersection on edge //..... *edge_label_p: integer label of edge where intersection occurs, //..... Return: //..... 1 if halfline PQ intersects with polygon //..... 0 if halfline PQ does not intersects with polygon int halfLineVsPolygon( Vector2& A, Vector2& B , List<Vertex2WithLineType>& list_vlt , int starting_label, int max_search , Vector2* X_p , double* t_AB_p , double* t_edge_p , int* edge_label_p , double epsilon = 1.0e-6 ); int halfLineVsPolygonForConvexation( Vector2& A, Vector2& B , Vector2& C , List<Vertex2WithLineType>& list_vlt , int starting_label, int max_search , Vector2* X_p , double* t_AB_p , double* t_edge_p , int* edge_label_p , double epsilon = 1.0e-6 ); //----- get number of vertices of given type of orientation int getNumVertexOfGivenOrt ( List<Vertex2WithLineType>& list_vlt , int ort_type , double epsilon = 1.0e-6 ); int getNumOrtZeroVertex ( List<Vertex2WithLineType>& list_vlt , double epsilon = 1.0e-6 ); int getNumConcaveVertex ( List<Vertex2WithLineType>& list_vlt , double epsilon = 1.0e-6 ); int getNumConvexVertex ( List<Vertex2WithLineType>& list_vlt , double epsilon = 1.0e-6 ); //----- write result of hidden line/surface removal to file int writePolygonOut( char* output_file , char* begin_facet , char terminal_char , const Parameter& parameter ) ; int writePolygonOut( const Polygon2D& poly2d , ofstream& vertex_out , ofstream& facet_out , int& vertex_label , char terminal_char , double epsilon3d ); //----- recoverOriginalPolygon3D() void recoverOriginalPolygon3D( Polygon3D& polygon3D_input, Polygon3D* polygon3D_output_p , double epsilon3d ); //----- total bounding diamond of polygon2d[] int getBoundingDiamond( double* xmin , double* xmax , double* ymin , double* ymax , double* umin , double* umax , double* vmin , double* vmax ); //----- bounding diamonds for parts of polygon2d[] int getBoundingDiamondInterval() const { return boundingDiamondInterval ;} void clearBoundingDiamondArray() { delete [] boundingDiamondArray ; boundingDiamondArray = NULL ; boundingDiamondInterval = 0 ; } int setBoundingDiamondArray( int diamond_interval ) ; //----- multiple max-min test //..... RETURN: //..... 0: Given area is independent of //..... polygons from polygon3d[index] //..... to polygon3d[index_end]. //..... The index_end is returned to the last argument. //..... 1: Else or unknown. int multiMaxMinTest( double xmin_given , double xmax_given , double ymin_given , double ymax_given , double umin_given , double umax_given , double vmin_given , double vmax_given , int index_given , double epsilon2d, int* index_end_p ) ; } ; // Hid #endif ////////////////////////////// end of hid.h