2D BSP implementation

So I'm have read alot information about Q3 BSP format and BSP itself. And now I'm have problems with conceptions and algorithm of building such BSP container consider HGE game engine. So I'm planning to use it for oprimise rendering of thousands quads( i.e hgeSprite) And I'm planning to use if for collision detection, so All I designed for game is (pseudocode)



void Renderer::Draw( void )
{
    // BSP tree to pick up quads thats visible for viewport 
    // (viewport can rotating about it's center)
    hgeSprite* spritesList = StaticGeometry->TestViewPort( camera.origin,
    camera.angle, camera.resolution );

    // So to HGE we send only such sprites that is in screen space
    DrawSpriteList( spritesList );

    // for dynamics we just test their OBB bounding boxes with camera OBB
    spritesList = DynamicGeometry->TestViewPort( camera.origin,
    camera.angle, camera.resolution );
    
    // now it's time to go about rendering characters, particles and other
    DrawSpriteList( spriteList );
}

// so for collision is going to be something like TraceLine, TraceBox, TraceSphere

bool_t TraceLine( const LVec2D &source, const LVec2D &destination, trace_t &result )
{
    hgeSprites *pSprites = 
    StaticGeometry->TestLine( source, destination, trace_t );
    if ( !pSprites )
      return false; // found nothing
    
    trace_t result, prevResult;
    // guess we store NULL as last node
    while ( *pSprites++ != NULL )
    {
       prevResult = result;
       result = Collision::TestRayVsGeometry( pSprites->GetCollisionShape() );
    }
    // let's return our closest sprite that is touched by ray
    result = Collision::RaySolver::SortForClosestObject( prevResult, result );

    // repeat for Dynamic, then SortForClosestObject between static 
    // and dynamic results
}

Of course Sprite list it's just abstaction, there will be LinkedList list; that store copy of allocated data for StaticGeometry that loaded by LevelLoad routine, it's just for readability. So I think this code is explain alot of my vision on problem of collision test and rendering, and that are actually worked, except that funtions that should return just couple of visible (touchable) sprites, retull all (thousands) objects. And I also dunno how to be with dynamic data, maybe store it's like OBB tree and test for O(n) between camera OBB and sprites OBBs For static geometry I have no idea how to implement it for quads that in's axis aligned, but static. And especially for tracing a line. So maybe you guys can help me with that by some examples, maybe some documentation for 2D and advices? Thanks in advance! Vitaly.

Topic Locked