Sorry your browser is not supported!

bool CheckLineTri( CVector3 TP1, CVector3 TP2, CVector3 TP3, CVector3 LP1, CVector3 LP2, CVector3 &HitPos)
  {
   CVector3 Normal, IntersectPos;

   // Find Triangle Normal
   Normal = CrossProduct( TP2 - TP1, TP3 - TP1 );
   Normal.Normalize(); // not really needed

   // Find distance from LP1 and LP2 to the plane defined by the triangle
   float Dist1 = (LP1-TP1).Dot( Normal );
   float Dist2 = (LP2-TP1).Dot( Normal );
   if ( (Dist1 * Dist2) >= 0.0f) return false;  // line doesn't cross the triangle.
   if ( Dist1 == Dist2) return false;// line and plane are parallel

   // Find point on the line that intersects with the plane
   IntersectPos = LP1 + (LP2-LP1) * ( -Dist1/(Dist2-Dist1) );

   // Find if the interesection point lies inside the triangle by testing it against all edges
   CVector3 vTest;
   vTest = CrossProduct( Normal, TP2-TP1 );
   if ( Dot( vTest, IntersectPos-TP1) < 0.0f ) return false;
   vTest = CrossProduct( Normal, TP3-TP2 );
   if ( Dot( vTest, IntersectPos-TP2) < 0.0f ) return false;
   vTest = CrossProduct( Normal, TP1-TP3 );
   if ( Dot( vTest, IntersectPos-TP1) < 0.0f ) return false;

   HitPos = IntersectPos;
   return true;
   }

IntersectPos.Scale(Dist);

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();
	}
}

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;
}

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;
}

bool line_vs_tri(int l,int ll,int t,int tt, int tri,int collcord)
{
	dbMakeVector3(500); dbMakeVector3(505);	dbMakeVector3(514); 
	dbMakeVector3(515); dbMakeVector3(516);	dbMakeVector3(517);
	dbMakeVector3(518); dbMakeVector3(519);	dbMakeVector3(520);
	dbMakeVector3(521); dbMakeVector3(522);	dbMakeVector3(523);

// Find Triangle Normal
	dbSubtractVector3(515,tt,t); dbSubtractVector3(516,tri,t);
	dbCrossProductVector3(514,515,516);
	dbNormalizeVector3(500,514);

// Find distance from LP1 and LP2 to the plane defined by the triangle
	dbSubtractVector3(517,l,t); dbSubtractVector3(518,ll,t);
		float dist = dbDotProductVector3(517,500);
		float maddist=dbDotProductVector3(518,500);

	if ( (dist * maddist) >= 0.0)	{	return(false);	}// line doesn't cross the triangle.

	if ( dist == maddist)	{	return(false);	}// line and plane are parallel

// Find point on the line that intersects with the plane
	dbSubtractVector3(519,ll,l);
	dbMultiplyVector3(519,-dist/(maddist-dist));
	dbAddVector3(collcord,l,519);

// Find if the interesection point lies inside the triangle by testing it against all edges
	dbCrossProductVector3(520,500,515);
	dbSubtractVector3(521,collcord,t);
	if(dbDotProductVector3(520,521)<0.0)	{	return(false);	}

	dbSubtractVector3(522,tri,tt);
	dbCrossProductVector3(520,500,522);
	dbSubtractVector3(523,collcord,tt);
	if(dbDotProductVector3(520,523)<0.0)	{	return(false);	}

	dbSubtractVector3(522,t,tri);
	dbCrossProductVector3(520,500,522);
	if(dbDotProductVector3(520,521)<0.0)	{	return(false);	}

	dbDeleteVector3(500); dbDeleteVector3(505);	dbDeleteVector3(514); 
	dbDeleteVector3(515); dbDeleteVector3(516);	dbDeleteVector3(517);
	dbDeleteVector3(518); dbDeleteVector3(519);	dbDeleteVector3(520);
	dbDeleteVector3(521); dbDeleteVector3(522);	dbDeleteVector3(523);

	return(true);
}