Sorry for the late reply. I am around now and then...

Are you checking whether a 3d line v1(XYZ) to v2(XYZ) crosses a face? If so then that would be a ray check...

In my code I was originally working with a 2D floor map before creating the final 3D mesh out of the data so I was just checking whether a new edge that was being added was intersecting any other edges already in the floor map. I had to shift v1 a tad as it would intersect anyway. (just digging out some code to help explain it better)

This first bit is the main setup, your's will be completely different but it's easy enough to follow:

void PROC_MAP::generate(int zoom)
{
//
// Added an STL optimisation here...
//
verts.reserve(10);
edges.reserve(10);
faces.reserve(10);
curr_segment = 0; // reset the current segment count to seperate limbs
this->start_poly(); // create the start off poly
int count = map_size; // add this many map pieces
_EDGE* edge; // quicker access to the data than STL
srand( map_seed ); // initialise random number generator
while ( count > 0 )
{
if ( count == map_size ) // first segment is always a corridor
{
if ( add_corridor() ) // if successful then change counters
{
count--; // decrease segment counter
curr_segment++; // next segment (for _FACE type)
}
}
// add a room or a corridor?
else if ( rand() & 1 )
{
// add corridor segments
if ( add_corridor() )
{
count--;
curr_segment++;
}
}
else
{
// add room seg
if ( add_room() ) // returns true if successfully added a room to the map
{
count--;
curr_segment++;
}
}
glutInitScreen();
glutstart2d();
glutPrint(4,12,"Generating...", 4, 1.0f, 1.0f, 1.0f);
glutend2d();
glutSwapBuffers();
}
}

This checks the 2D edge intersection of the main edges list:

bool PROC_MAP::edge_intersect(float x1, float z1, float x2, float z2)
{
int count = (int)edges.size();
int pos = 0;
_EDGE* e = &edges[0]; // faster 'not' using STL (loop could be huge)
_VERT* v = &verts[0];
bool flag = 0;
float x3,z3,x4,z4;
int v1, v2;
while ( flag == 0 && pos < count )
{
v1 = e->v1;
v2 = e->v2;
x3 = v[v1].x;
z3 = v[v1].z;
x4 = v[v2].x;
z4 = v[v2].z;
flag = line_intersect(x1,z1,x2,z2,x3,z3,x4,z4);
e++; // next item in the edge list
pos++;
}
return flag;
}
bool PROC_MAP::line_intersect(float x1, float y1, float x2, float y2,
float x3, float y3, float x4, float y4) {
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
if ( d == 0 ) return 0;
// Get the x and y
float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d;
// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) || // REMOVE STL min() and max()
x < min(x3, x4) || x > max(x3, x4) ) return 0;
if ( y < min(y1, y2) || y > max(y1, y2) ||
y < min(y3, y4) || y > max(y3, y4) ) return 0;
return 1;
}

These next two functions will actually try to attempt to add a corridor segment. If a piece of the newly added segment crosses the main map then it will fail, but only if it hasn't added the minimum amount of segment pieces. The second function is where I have had to nudge one of the vertices so that it will work when checking the intersection:

bool PROC_MAP::add_corridor()
{
// in case I need to delete them, store the original sizes of the arrays
int orig_vsize = (int)verts.size();
int orig_esize = (int)edges.size();
int orig_fsize = (int)faces.size();
// how many segments am I going to add?
int segs = rand() % ( cseg_max - cseg_min ) + cseg_min;
// now find an edge to try out
int edge;
do {
edge = rand() % (orig_esize);
} while ( edges[edge].type != PM_COUTER && edges[edge].type != PM_ROUTER );
// keep the original edge number and type for the future
int orig_edge = edge;
int orig_edge_type = edges[edge].type;
int etype;
// alter the original edges type accordingly
if ( orig_edge_type != PM_ROUTER )
etype = PM_CINNER;
else
etype = PM_RENTRY;
edges[edge].type = etype;
// now add this edge to the new segment so it can be made as a seperate limb
int v1 = edges[edge].v1;
int v2 = edges[edge].v2;
// Don't reverse the new edge as it's only an inner edge and needs to keep its
// orientation for the rest of the corridor algorithm
verts.push_back( _VERT( verts[v1].x, verts[v1].y, verts[v1].z ) );
verts.push_back( _VERT( verts[v2].x, verts[v2].y, verts[v2].z ) );
// set the new edges type based on corridor or room (rooms will have doorways)
edges.push_back( _EDGE( orig_vsize, orig_vsize + 1, etype, curr_segment ) );
// now set the variable 'edge' to point to the new edge
edge = orig_esize;
// now keep trying to add the segments
int seg_count = 0;
do {
edge = add_corridor_seg( edge );
seg_count++;
} while ( edge != 0 && seg_count < segs );
// have we added enough segs to let them stay on the map?
if ( seg_count < cseg_min )
{
// okay, remove the data from the main map data
while ( (int)verts.size() > orig_vsize )
verts.erase( verts.begin() + orig_vsize );
while ( (int)edges.size() > orig_esize )
edges.erase( edges.begin() + orig_esize );
while ( (int)faces.size() > orig_fsize )
faces.erase( faces.begin() + orig_fsize );
// restore the original edges type
edges[orig_edge].type = orig_edge_type;
// now exit returning NULL to calling function
return 0;
}
// it actually looks I'm done and can exit
return 1;
}
// if successfull then returns pointer to the new edge to carry on adding onto
int PROC_MAP::add_corridor_seg( int edge )
{
float d2r90 = Deg2Rad(90);
// get the original verts of the current edge
int v1 = edges[edge].v1;
int v2 = edges[edge].v2;
// these will be used when adding the new edges
int v3, v4;
float x1 = verts[v1].x; // main edge coords start
float z1 = verts[v1].z;
float x2 = verts[v2].x; // end point
float z2 = verts[v2].z;
// get the current edges angle
float edge_angle = atan2( z2-z1, x2-x1 );
float angle_adjust = Deg2Rad( (float)( ( rand() % ( ang_max - ang_min ) ) + ang_min ) );
// get the middle position of the current edge
float xmid = ( x1 + x2 ) / 2.0f;
float zmid = ( z1 + z2 ) / 2.0f;
float new_length = ( rand() % ( size_max -size_min ) ) + size_min;
float new_angle = edge_angle - angle_adjust;
// set the middle coords of the new parallel edge
float newx = xmid + cos( new_angle ) * new_length;
float newz = zmid + sin( new_angle ) * new_length;
float half_new_length = new_length / 2.0f;
// start vert pos of new parallel edge
float x3 = newx + cos( new_angle - d2r90 ) * ( half_new_length );
float z3 = newz + sin( new_angle - d2r90 ) * ( half_new_length );
// end vert pos of the new parallel edge
float x4 = newx + cos( new_angle + d2r90 ) * ( half_new_length );
float z4 = newz + sin( new_angle + d2r90 ) * ( half_new_length );
// nudge original verts a little ( for intersect check )
// otherwise they will intersect with 3 edges as verts are the same
x1 = x1 + cos( new_angle ) * 0.5f;
z1 = z1 + sin( new_angle ) * 0.5f;
x2 = x2 + cos( new_angle ) * 0.5f;
z2 = z2 + sin( new_angle ) * 0.5f;
// if no intersection with current edges then add new poly
if ( edge_intersect( x1, z1, x3, z3 ) == 0 )
{
if ( edge_intersect( x3, z3, x4, z4 ) == 0 )
{
if ( edge_intersect( x4, z4, x2, z2 ) == 0 )
{
// change old edge type if needed
if ( edges[edge].type != PM_RENTRY )
edges[edge].type = PM_CINNER;
// get verts end position
int vcount = (int)verts.size();
// add the new verts to the array
verts.push_back( _VERT( x3, 0, z3 ) );
verts.push_back( _VERT( x4, 0, z4 ) );
/*int v1 = edges[edge].v1;
int v2 = edges[edge].v2;*/
// new vert indices
v3 = vcount;
v4 = vcount + 1;
edges.push_back( _EDGE( v1, v3, PM_COUTER, curr_segment ) );
edges.push_back( _EDGE( v4, v2, PM_COUTER, curr_segment ) );
edges.push_back( _EDGE( v4, v1, PM_CINNER, curr_segment ) );
edges.push_back( _EDGE( v3, v4, PM_COUTER, curr_segment ) );
faces.push_back( _FACE( v1, v3, v4, PM_CFACE, curr_segment ) );
faces.push_back( _FACE( v4, v2, v1, PM_CFACE, curr_segment ) );
edge = (int)edges.size() - 1;
return edge;
}
}
}
return 0;
}

If you want me to I can send you this project in an email so you can study it better...

EDIT: I've also found some of these which I've bookmarked for my own refernce:

http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm
http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf
http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm
Mental arithmetic? Me? (That's for computers) I can't subtract a fart from a plate of beans!

Warning! May contain Nuts!