BSP tree math

Znam 4e ima mnogo tutoriali iz internet. Algoritymyt e edin i sy6t i mi e qsen, no za matematikata skirta zad nego ne moga da kaja taka. Imam idei koito mi se struwaha wqrni, no se okaza 4e ne e to4no taka. Wyprosite mi sa nqkolko:

1.Ako e dadena rawnina s normalno urawnenie A*x+B*y+C*z+D i vektor(to4ka) s koordinati (X,Y,Z) kak moje da se opredeli ot koq strana na rawninata e to4kata?
(Spored men if( (A*X+B*Y+C*Z+D)==0) wytre else if((A*X+B*Y+C*Z+D)>0 ) otpred
else otzad)
2. Po daden polygon - primerno opredelen s 4 wektora a,b,c,d kak da naprawq rawnina?(Spored men s wektorno proizwedenie (a-b)X(d-a) namiram normalniq wektor, prawq go edini4en i ot tam namiram A,B,C,D)

Drugoto koeto mi e nujno za naprawata na nai-triwialno BSP dyrwo mislq 4e go znam. Wsy6nost mai ostana samo razdelqne na polygon ot rawnina:)


Blagodarq predwaritelno na wseki spestil mi o6te edna bezsynna no6t!!

Хубаво е да разбереш какво всъщност значат тези A,B,C и D в това уравнение - (A,B,C) е нормалния вектор (не нормализиран в общия случай) на равнината, а D е растоянието от центъра на координатната система до равнината в мерна единица дължината на (А,B,C) вектора. T.e. ako (A,B,C) ти е наистина нормализиран, тогава D ти е растоянието до (0,0,0). От тук вече се досещаш че като заместиш каква да е точка в уравнението на равнината получаваш като резултат растоянието от тази точка до равнината. За проверка дали точка лежи в равнината се ползва проверка за нула с епсилон - правиш скаларното произведение с равнината s=(Ax+By+Cz+D) и после if(s>-epsilon && s<epsilon) значи точката лежи на равнината. За повече информация по тази тема виж:
[линк]

За равнина в 3D са необходими 3 точки, правиш векторно произведение, като обаче преди това нормализираш двата вектора които ще 'векторизираш' - така получаваш директно нормализиран вектор, който както сигурно се досещаш от по-горе е (A,B,C) на твоето уравнение. D = - ( A.x0 + B.y0 + C.z0) за някоя (xo,yo,zo) от точките от тази равнина (нали имаш поне 3 които знаеш...). За раделяне на полигон от равнина ще ти постна моя код, че ме мързи да пиша псевдокод
Виж CutCommon, другото е за по-добро readability
И да - виж [линк]

class Winding
{
public:
Winding() {}
Winding( const Winding & rhs );
Winding( const Planef & plane, float size );

void Clear() { vert.Clear(); }
int32 Count() const { return vert.Count(); }
void AddVertex( const Vec3f & vec ) { vert.PushBack( vec ); }
void CreateFromPlane( const Planef & plane, float size );

void operator = ( const Winding & rhs );
Vec3f & operator [] ( int32 idx ) const throw();

void CutFront( const Planef & plane, Winding & front );
void Cut ( const Planef & plane, Winding & front, Winding & back );
protected:
Array<Vec3f> vert;
private:
void CutCommon( const Planef & plane, Winding * pFront, Winding * pBack );
};

void Winding::CutCommon( const Planef & plane, Winding * pFront, Winding * pBack )
{
Assert( pFront );

int32 nLast = 0;
float fLast = (float)0;

pFront->Clear();
if( pBack ) pBack->Clear();
if( Count() == 0 ) return;

for( int32 i = 0; i <= (int32)Count(); ++i )
{
Vec3f * pCur = ( i == (int32)Count()) ? &vert[0] : &vert;
float f = plane( *pCur );

if( ! Zero_f( f ))
{
if( f > (float)0 )
{
if( nLast == -1 )
{
Vec3f vec( Lerp( vert[i-1], *pCur, fLast / ( fLast - f ) ));
pFront->AddVertex( vec );
if( pBack ) pBack->AddVertex( vec );
}
if( i < (int32)Count())
pFront->AddVertex( *pCur );
nLast = 1;
}
else
{
if( nLast == 1 )
{
Vec3f vec( Lerp( vert[i-1], *pCur, fLast / ( fLast - f ) ));
pFront->AddVertex( vec );
if( pBack ) pBack->AddVertex( vec );
}
if( pBack )
if( i < (int32)Count())
pBack->AddVertex( *pCur );
nLast = -1;
}
}
else
{
pFront->AddVertex( *pCur );
if( pBack ) pBack->AddVertex( *pCur );
nLast = 0;
}
fLast = f;
}
}

The ones who live by the sword get shot by the ones who don't.

const float Epsilon_f = 0.001f;

bool Zero_f( float x )
{
return x > -Epsilon_f && x < Epsilon_f;
}

template< class T, class F >
inline T Lerp( const T & a, const T & b, F k )
{
return a + ( b - a ) * k;
}

The ones who live by the sword get shot by the ones who don't.

Mersi. No za syjalenie pak ima bygowe :( 6te derzaq:)