## [Algorithms] quick and dirty bsp's revisited

 [Algorithms] quick and dirty bsp's revisited From: Idahosa Edokpayi - 2002-03-31 11:18:20 ```Here is the new code for my triangle class incorporating most of the recommendations Jackie Chan and Angel Popov made. What I would still like to know is: What happens to triangles that are "on"? They do not intersect, they are not above, and not below yet they are in the BSP and not rejected. This somehow seems like it would be bad thing just waiting to bite an unsuspecting coder in the butt. Also, I want to know, what are the ramifications if I actually do write triangle intersection code using separating axis theorem or whatever I am convinced is the fastest way to do it and I substitute that for my current triangle intersection code? The code I have now detects PLANE intersection. By using strict triangle intersection would I be jacking up the semantics of my BSP system? #ifndef TRIANGLE_H #define TRIANGLE_H #include "mathcore.h" template class triangle { private: vector m_vVertices[3]; plane m_Plane; // speed up BSP comparisons static scalar m_Epsilon; public: triangle(){} triangle( const vector& v1, const vector& v2, const vector& v3 ) { m_vVertices[0] = v1; m_vVertices[1] = v2; m_vVertices[2] = v3; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } triangle( const vector* pvVertices ) { m_vVertices[0] = pvVertices[0]; m_vVertices[1] = pvVertices[1]; m_vVertices[2] = pvVertices[2]; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } ~triangle(){} // modifier void setVertex( const vector& v, const unsigned int index ) { m_vVertices[index%3] = v; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } // operators // assignment triangle& operator=( const triangle& tri ) { m_vVertices[0] = tri .m_vVertices[0]; m_vVertices[1] = tri .m_vVertices[1]; m_vVertices[2] = tri .m_vVertices[2]; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } // array operator const vector& operator[]( const unsigned int index ) const { return m_vVertices[index%3]; } // comparison for BSP partitioning bool operator < ( const triangle& tri ) const { if( SignedDistanceToPoint( m_Plane, tri[0] ) < -triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[1] ) < -triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[2] ) < -triangle::m_Epsilon ) return true; return false; } bool operator > ( const triangle& tri ) const { if( SignedDistanceToPoint( m_Plane, tri[0] ) > triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[1] ) > triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[2] ) > triangle::m_Epsilon ) return true; return false; } // plane intersection bool operator == ( const triangle& tri ) const { return ( !(*this < tri) && !(*this > tri) ); } enum cmp { ABOVE, BELOW, ON, INTERSECTING }; // test point comparison cmp Compare( const vector& v ) { // above or below scalar sTest = SignedDistanceToPoint( m_Plane, v ); if( sTest > triangle::m_Epsilon ) return ABOVE; else if( sTest < -triangle::m_Epsilon ) return BELOW; return ON; } cmp Compare( const triangle& tri ) { // use separating axis fool! return ABOVE; } }; #endif Idahosa Edokpayi ```

 [Algorithms] quick and dirty bsp's revisited From: Idahosa Edokpayi - 2002-03-31 11:18:20 ```Here is the new code for my triangle class incorporating most of the recommendations Jackie Chan and Angel Popov made. What I would still like to know is: What happens to triangles that are "on"? They do not intersect, they are not above, and not below yet they are in the BSP and not rejected. This somehow seems like it would be bad thing just waiting to bite an unsuspecting coder in the butt. Also, I want to know, what are the ramifications if I actually do write triangle intersection code using separating axis theorem or whatever I am convinced is the fastest way to do it and I substitute that for my current triangle intersection code? The code I have now detects PLANE intersection. By using strict triangle intersection would I be jacking up the semantics of my BSP system? #ifndef TRIANGLE_H #define TRIANGLE_H #include "mathcore.h" template class triangle { private: vector m_vVertices[3]; plane m_Plane; // speed up BSP comparisons static scalar m_Epsilon; public: triangle(){} triangle( const vector& v1, const vector& v2, const vector& v3 ) { m_vVertices[0] = v1; m_vVertices[1] = v2; m_vVertices[2] = v3; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } triangle( const vector* pvVertices ) { m_vVertices[0] = pvVertices[0]; m_vVertices[1] = pvVertices[1]; m_vVertices[2] = pvVertices[2]; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } ~triangle(){} // modifier void setVertex( const vector& v, const unsigned int index ) { m_vVertices[index%3] = v; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } // operators // assignment triangle& operator=( const triangle& tri ) { m_vVertices[0] = tri .m_vVertices[0]; m_vVertices[1] = tri .m_vVertices[1]; m_vVertices[2] = tri .m_vVertices[2]; PlaneFromPoints( m_Plane, m_vVertices[0], m_vVertices[1], m_vVertices[2] ); } // array operator const vector& operator[]( const unsigned int index ) const { return m_vVertices[index%3]; } // comparison for BSP partitioning bool operator < ( const triangle& tri ) const { if( SignedDistanceToPoint( m_Plane, tri[0] ) < -triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[1] ) < -triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[2] ) < -triangle::m_Epsilon ) return true; return false; } bool operator > ( const triangle& tri ) const { if( SignedDistanceToPoint( m_Plane, tri[0] ) > triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[1] ) > triangle::m_Epsilon && SignedDistanceToPoint( m_Plane, tri[2] ) > triangle::m_Epsilon ) return true; return false; } // plane intersection bool operator == ( const triangle& tri ) const { return ( !(*this < tri) && !(*this > tri) ); } enum cmp { ABOVE, BELOW, ON, INTERSECTING }; // test point comparison cmp Compare( const vector& v ) { // above or below scalar sTest = SignedDistanceToPoint( m_Plane, v ); if( sTest > triangle::m_Epsilon ) return ABOVE; else if( sTest < -triangle::m_Epsilon ) return BELOW; return ON; } cmp Compare( const triangle& tri ) { // use separating axis fool! return ABOVE; } }; #endif Idahosa Edokpayi ```
 Re: [Algorithms] quick and dirty bsp's revisited From: Angel Popov - 2002-04-01 10:15:19 ```>.... What I would still like to > know is: What happens to triangles that are "on"? That depends on what you will be using the BSP for. If you want to do collision detection - you need a classic BSP where while building it - you just delete the polygons that lie on the plane - you will not need any polygons for the collision detection. Some people may tell you that you need a solid BSP for this, but a classic one will do fine - just treat the Front NULL leaves as empty (e.g. space) and the Back NULL leaves as solid. You will have to CSG your brushes first. If you want to split your world into covex sectors connected with portals (either to use it in a portal engine or for PVS calculations) - you will need to create a solid BSP by pushing the on-plane polygons through the Front node. As in the above case - you will have to CSG your brushes first. If you want to use the BSP for CSG calculations - the things can get quite complex, especialy if you want to handle decals properly - in some cases you will have to push the on-plane polygon through the Front node, then collect the parts that did not end in a solid leaf and push them through the Back node... Tell me if you need more info on this. And finaly if you want to use the BSP for triangle-BSP collision detection it does not realy mater whether you send the polygon through the Front or Back node as you probably don't need to be that precise in your collsion detection. ```