In my engine I can load quake 3 .bsp files, and I implemented sphere-brush collision detection with the help of this tutorial:
http://www.devmaster.net/articles/quake3collision/
I am discarding all the BSP stuff and just storing the brushes in a big array.
My system seemed to work with all of the quake 3 levels I tested.
Now I downloaded GTKRadiant, created some simple geometry, and discovered a big problem I have with my system.
Say that I have two brushes: a cube, and an adjacent prism, so I can reach the top of the cube walking on the prism. This is a side view of it:
______
/| |
/ | |
/__|_____|
I discovered that if I try to get to the cube walking from left to right, I cannot reach the top of the cube: i remain strucked at the end of the prism, just a bit before reaching the cube. This is what goes on: The player goes right, I detect the collision with the prism and slide the player velocity along the plane, so it is going up-right now, then I check all the brushes again and this time I detect a collision with the left plane of the cube, that stops the player.
In theory I should not collide with the cube when I modify my velocity sliding on the prism, but I do, because basically when I check for a collision with a brush, I'm actually testing a ray against an "inflated" brush, extending all the planes by the sphere radius (This is what the tutorial does, anyway).
But doing this, I'm detecting non-existant collisions with, for example, a cube edge!
If you aren't following me, think of a cube: if I inflate it by 1 unit, this means that I move the up plane by 1 and the left plane by 1, but the top-left corner was actually moved by ~1.4!
The proper way, I think, would be to use a cylinder for brush edges and a sphere for brush corners, but this is not possible due to the structure of brush data, wich is just an array of planes.
I wonder if and how Quake3 solves this problem, I'm probably going to take a look at the source code.
This is my source:
bool CBrush::TraceSphere( const D3DXVECTOR3& Start, const D3DXVECTOR3& End,
float SphereRadius, float* pDistance, D3DXPLANE* pPlane )
{
float EnterDistance = -1.0f; // Farthest distance the line enters a plane [-1, 1]
float LeaveDistance = 1.0f; // Closest distance the line exits a plane [-1, 1]
for( unsigned int i = 0; i < m_Planes.size(); ++i )
{
float StartDistance = D3DXPlaneDotCoord( &m_Planes, &Start ) - SphereRadius;
<span class="cpp-keyword">float</span> EndDistance = D3DXPlaneDotCoord( &m_Planes, &End ) - SphereRadius;
<span class="cpp-comment">// If both Start and End are outside the plane, the line is not intersecting</span>
<span class="cpp-keyword">if</span>( ( StartDistance > <span class="cpp-number">0</span>.0f ) && ( EndDistance > <span class="cpp-number">0</span>.0f ) )
{
<span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;
}
<span class="cpp-comment">// If both Start and End are inside the plane, ignore the plane</span>
<span class="cpp-keyword">if</span>( ( StartDistance <= <span class="cpp-number">0</span>.0f ) && ( EndDistance <= <span class="cpp-number">0</span>.0f ) )
{
<span class="cpp-keyword">continue</span>;
}
<span class="cpp-comment">// If we get here the line is intersecting the plane</span>
<span class="cpp-comment">// Check if we are entering the plane</span>
<span class="cpp-keyword">if</span>( StartDistance > EndDistance )
{
<span class="cpp-comment">// Compute the distance until we enter the plane [-1,1]</span>
<span class="cpp-keyword">float</span> Dist = StartDistance / ( StartDistance - EndDistance );
<span class="cpp-keyword">if</span>( Dist > EnterDistance )
{
EnterDistance = Dist;
<span class="cpp-keyword">if</span>( pPlane )
{
( *pPlane ) = m_Planes;
}
}
}
<span class="cpp-keyword">else</span>
{
<span class="cpp-comment">// Compute the distance until we leave the plane [-1,1]</span>
<span class="cpp-keyword">float</span> Dist = StartDistance / ( StartDistance - EndDistance );
<span class="cpp-keyword">if</span>( Dist < LeaveDistance )
{
LeaveDistance = Dist;
}
}
}
<span class="cpp-keyword">if</span>( LeaveDistance < EnterDistance )
{
<span class="cpp-comment">// We leave the brush before entering it. No collision.</span>
<span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;
}
<span class="cpp-keyword">else</span>
{
<span class="cpp-comment">// Output the distance until the line touches the brush</span>
<span class="cpp-keyword">if</span>( pDistance )
{
( *pDistance ) = EnterDistance;
}
<span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>;
}
}
</pre></div><!–ENDSCRIPT–>
