To sum it up: The entire code, and also the ideas to accelerate it and to compensate for numerical errors is a big bunch of crap, imvho.

Line-face intersection the Parallax way. This is a standard method, but a slow one. It works by reducing the problem to a 2D case by ignoring the dimension where the normal has its biggest component (i.e. is closest to being perpendicular to). Since Parallax tried to use quads instead of triangles as often as possible - even where that was a bad idea since the quad's two faces weren't co-planar, they had to use it. It still doesn't work right for quads with two non-planar triangles.

This is the original code:

Code: Select all

`//see if a point in inside a face by projecting into 2d`

uint check_point_to_face(vms_vector *checkp, side *s,int facenum,int nv,int *vertex_list)

{

vms_vector_array *checkp_array;

vms_vector_array norm;

vms_vector t;

int biggest;

///

int i,j,edge;

uint edgemask;

fix check_i,check_j;

vms_vector_array *v0,*v1;

#ifdef COMPACT_SEGS

get_side_normal(sp, s-sp->sides, facenum, (vms_vector *)&norm );

#else

memcpy( &norm, &s->normals[facenum], sizeof(vms_vector_array));

#endif

checkp_array = (vms_vector_array *)checkp;

//now do 2d check to see if point is in side

//project polygon onto plane by finding largest component of normal

t.x = labs(norm.xyz[0]); t.y = labs(norm.xyz[1]); t.z = labs(norm.xyz[2]);

if (t.x > t.y) if (t.x > t.z) biggest=0; else biggest=2;

else if (t.y > t.z) biggest=1; else biggest=2;

if (norm.xyz[biggest] > 0) {

i = ij_table[biggest][0];

j = ij_table[biggest][1];

}

else {

i = ij_table[biggest][1];

j = ij_table[biggest][0];

}

//now do the 2d problem in the i,j plane

check_i = checkp_array->xyz[i];

check_j = checkp_array->xyz[j];

for (edge=edgemask=0;edge<nv;edge++) {

vec2d edgevec,checkvec;

fix d;

v0 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+edge]];

v1 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+((edge+1)%nv)]];

edgevec.i = v1->xyz[i] - v0->xyz[i];

edgevec.j = v1->xyz[j] - v0->xyz[j];

checkvec.i = check_i - v0->xyz[i];

checkvec.j = check_j - v0->xyz[j];

d = fixmul(checkvec.i,edgevec.j) - fixmul(checkvec.j,edgevec.i);

if (d < 0) //we are outside of triangle

edgemask |= (1<<edge);

}

return edgemask;

}

This is the same code, but has been streamlined substantially by me:

Code: Select all

`uint CSide::PointToFaceRelation (CFixVector& intersection, short iFace, CFixVector vNormal)`

{

CFixVector t;

int h, i, j, nEdge, nVerts, projPlane;

uint nEdgeMask;

CFixVector* v0, *v1;

CFixVector2D vEdge, vCheck, vRef;

//project polygon onto plane by finding largest component of Normal

t.Set (labs (vNormal.v.coord.x), labs (vNormal.v.coord.y), labs (vNormal.v.coord.z));

if (t.v.coord.x > t.v.coord.y)

projPlane = (t.v.coord.x > t.v.coord.z) ? 0 : 2;

else

projPlane = (t.v.coord.y > t.v.coord.z) ? 1 : 2;

if (vNormal.v.vec [projPlane] > 0) {

i = ijTable [projPlane][0];

j = ijTable [projPlane][1];

}

else {

i = ijTable [projPlane][1];

j = ijTable [projPlane][0];

}

//now do the 2d problem in the projection plane

vRef.i = intersection.v.vec [i];

vRef.j = intersection.v.vec [j];

nVerts = 5 - m_nFaces;

h = iFace * 3;

v1 = VERTICES + m_vertices [h + nEdge];

for (nEdge = 1, nEdgeMask = 0; nEdge <= nVerts; nEdge++) {

v0 = v1;

v1 = VERTICES + m_vertices [h + nEdge % nVerts];

vEdge.i = v1->v.vec [i] - v0->v.vec [i];

vEdge.j = v1->v.vec [j] - v0->v.vec [j];

vCheck.i = vRef.i - v0->v.vec [i];

vCheck.j = vRef.j - v0->v.vec [j];

if (FixMul64 (vCheck.i, vEdge.j) - FixMul64 (vCheck.j, vEdge.i) < 0) //we are outside of triangle

nEdgeMask |= (1 << (nEdge - 1));

}

return nEdgeMask;

}

This is a faster and more elegant method (Barycentric method, courtesy the internets). Basically it expresses the reference point relative to a triangle corner, using two triangle edges: P = A + u * (C - A) + v * (B - A), where P is the reference point (intersection of the line with the triangle's plane), and A,B,C are the triangle vertices. The point is inside the triangle if (u >= 0 && v > 0 && u + v <= 1). You can also easily tell "behind" which edges of the triangle the reference point is when it's outside the triangle. All segment sides need to be split into triangles for this method, but this doesn't hurt anymore, given the speed and amount of memory even low-end computers have these days.

Code: Select all

`// return 0 if point inside triangle, otherwise bit-wise coded edges the point is behind as seen from inside the triangle`

ubyte PointIsOutsideFace (CFloatVector* refP, CFloatVector vNormal, CFloatVector* vertices, short nVerts)

{

CFloatVector v0 = vertices [2] - vertices [0];

CFloatVector v1 = vertices [1] - vertices [0];

CFloatVector v2 = *refP - vertices [0];

float dot00 = CFloatVector::Dot (v0, v0);

float dot11 = CFloatVector::Dot (v1, v1);

float dot01 = CFloatVector::Dot (v0, v1);

float dot02 = CFloatVector::Dot (v0, v2);

float dot12 = CFloatVector::Dot (v1, v2);

float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);

float u = (dot11 * dot02 - dot01 * dot12) * invDenom;

float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

return (int (u < -0.001f)) + ((int (v < -0.001f)) << 1) + ((int (u + v > 1.001f)) << 2); // compensate for numerical errors

}

I wonder how many more problems and flaws (i.e. robots penetrating walls) would suddenly and miraculously disappear if this math would be done right.

In my book, "Parallax" stands for "Painful Programing" already.