Yandersen

08-24-2015, 09:12 PM

Hi!

Basic task - to find the intersection point between a line segment with corner points S1 and S2 and a triangle with vertices A,B,C.

To do this I wrote a function that calculates partial coefficients or "weights" of each triangle' vertices at the intersection point (Pint), so it can be found as Pint=Wa*A+Wb*B+Wc*C.

I intuitively did it through volumes, though I haven't seen such algorithm anywhere, so I would like a confirmation if this is correct (it seems so...). Here is a working code of this function:

//Macros for calculating determinant of 3x3 matrix composed from 3 vectors

#define Determinant3xV(a,b,c) (a[0]*b[1]*c[2]+a[1]*b[2]*c[0]+a[2]*b[0]*c[1]-a[2]*b[1]*c[0]-a[1]*b[0]*c[2]-a[0]*b[2]*c[1])

//------------------------------------------------------------------------------

//Function checks if specified line' segment S1-S2 crosses triangle with given

//vertexes (A,B,C), and writes each triangle' vertex' attribute-part-value (at

//the intersection point) to PartsABC[3] variable

bool PolarizeTriangleWithSegment(const float S1[3], const float S2[3],

const float A[3], const float B[3], const float C[3],

float *PartsABC){

//Calculate vectors

float R[3] = {S2[0]-S1[0], S2[1]-S1[1], S2[2]-S1[2]},

S1A[3] = {A[0]-S1[0], A[1]-S1[1], A[2]-S1[2]},

S1B[3] = {B[0]-S1[0], B[1]-S1[1], B[2]-S1[2]},

S1C[3] = {C[0]-S1[0], C[1]-S1[1], C[2]-S1[2]},

S2A[3] = {A[0]-S2[0], A[1]-S2[1], A[2]-S2[2]},

S2B[3] = {B[0]-S2[0], B[1]-S2[1], B[2]-S2[2]},

S2C[3] = {C[0]-S2[0], C[1]-S2[1], C[2]-S2[2]};

//Calculate 6X volumes

float S1ABC = Determinant3xV(S1A,S1B,S1C);

float S2BAC = Determinant3xV(S2B,S2A,S2C);

if(S1ABC*S2BAC<0.f)return false; //No intersection with segment

float S1ABCS2 = S1ABC + S2BAC;

if(S1ABCS2==0.f)return false; //Triangle is degenerate or S1==S2

//Calculate volumes' parts

PartsABC[0] = Determinant3xV(S1B,S1C,R)/S1ABCS2;

if(PartsABC[0]<0.f)return false; //No intersection with segment

PartsABC[1] = Determinant3xV(S1C,S1A,R)/S1ABCS2;

if(PartsABC[1]<0.f)return false; //No intersection with segment

PartsABC[2] = Determinant3xV(S1A,S1B,R)/S1ABCS2;

if(PartsABC[2]<0.f)return false; //No intersection with segment

//Weights are calculated; Pint = PartsABC[0]*A + PartsABC[1]*B + PartsABC[2]*C

return true;

}

Is this correct?

Basic task - to find the intersection point between a line segment with corner points S1 and S2 and a triangle with vertices A,B,C.

To do this I wrote a function that calculates partial coefficients or "weights" of each triangle' vertices at the intersection point (Pint), so it can be found as Pint=Wa*A+Wb*B+Wc*C.

I intuitively did it through volumes, though I haven't seen such algorithm anywhere, so I would like a confirmation if this is correct (it seems so...). Here is a working code of this function:

//Macros for calculating determinant of 3x3 matrix composed from 3 vectors

#define Determinant3xV(a,b,c) (a[0]*b[1]*c[2]+a[1]*b[2]*c[0]+a[2]*b[0]*c[1]-a[2]*b[1]*c[0]-a[1]*b[0]*c[2]-a[0]*b[2]*c[1])

//------------------------------------------------------------------------------

//Function checks if specified line' segment S1-S2 crosses triangle with given

//vertexes (A,B,C), and writes each triangle' vertex' attribute-part-value (at

//the intersection point) to PartsABC[3] variable

bool PolarizeTriangleWithSegment(const float S1[3], const float S2[3],

const float A[3], const float B[3], const float C[3],

float *PartsABC){

//Calculate vectors

float R[3] = {S2[0]-S1[0], S2[1]-S1[1], S2[2]-S1[2]},

S1A[3] = {A[0]-S1[0], A[1]-S1[1], A[2]-S1[2]},

S1B[3] = {B[0]-S1[0], B[1]-S1[1], B[2]-S1[2]},

S1C[3] = {C[0]-S1[0], C[1]-S1[1], C[2]-S1[2]},

S2A[3] = {A[0]-S2[0], A[1]-S2[1], A[2]-S2[2]},

S2B[3] = {B[0]-S2[0], B[1]-S2[1], B[2]-S2[2]},

S2C[3] = {C[0]-S2[0], C[1]-S2[1], C[2]-S2[2]};

//Calculate 6X volumes

float S1ABC = Determinant3xV(S1A,S1B,S1C);

float S2BAC = Determinant3xV(S2B,S2A,S2C);

if(S1ABC*S2BAC<0.f)return false; //No intersection with segment

float S1ABCS2 = S1ABC + S2BAC;

if(S1ABCS2==0.f)return false; //Triangle is degenerate or S1==S2

//Calculate volumes' parts

PartsABC[0] = Determinant3xV(S1B,S1C,R)/S1ABCS2;

if(PartsABC[0]<0.f)return false; //No intersection with segment

PartsABC[1] = Determinant3xV(S1C,S1A,R)/S1ABCS2;

if(PartsABC[1]<0.f)return false; //No intersection with segment

PartsABC[2] = Determinant3xV(S1A,S1B,R)/S1ABCS2;

if(PartsABC[2]<0.f)return false; //No intersection with segment

//Weights are calculated; Pint = PartsABC[0]*A + PartsABC[1]*B + PartsABC[2]*C

return true;

}

Is this correct?