mainfrm.cpp

2D Collsion Detection in Real-time Demonstration This is the sample application that accompanies G

// CHECK FOR DOUBLE SIDED EDGES
void CMainFrame::CheckDoubleSided()
{
	short inner,outer;
	for (outer = 0; outer < m_edgecnt; outer++)
	{
		for (inner = 0; inner < m_edgecnt; inner++)
		{
			// THEY SHARE AN EDGE IF
			if (OnSamePos(outer,m_edgelist[inner].nextedge) &&
				OnSamePos(inner,m_edgelist[outer].nextedge))
			{
				m_edgelist[inner].backedge = outer;
				m_edgelist[inner].backsector = m_edgelist[outer].sector;
				m_edgelist[outer].backedge = inner;
				m_edgelist[outer].backsector = m_edgelist[inner].sector;
			}
		}		
	}
}

void CMainFrame::InsertPoint()
{
	tEdge	*this_edge,*new_edge;
	tPoint2D t_pnt;
	if (m_nearest_edge >= 0)
	{
		t_pnt.x = m_nearest_pnt.x;
		t_pnt.y = m_nearest_pnt.y;
		SnapPoint(&t_pnt);
		this_edge = &m_edgelist[m_nearest_edge];
		new_edge = &m_edgelist[m_edgecnt];
		new_edge->pos.x = t_pnt.x;
		new_edge->pos.y = t_pnt.y;
		new_edge->sector = this_edge->sector;
		new_edge->backsector = -1;
		new_edge->backedge = -1;
		new_edge->prevedge = m_nearest_edge;
		m_edgelist[this_edge->nextedge].prevedge = m_edgecnt;
		new_edge->nextedge = this_edge->nextedge;
		this_edge->nextedge = m_edgecnt;
		m_edgecnt++;
		m_sectorlist[this_edge->sector].edgecnt++;
	}
}

void CMainFrame::DeleteEdge(short which)
{
	short loop;	
	tEdge *t_edge;
	t_edge = &m_edgelist[which];
	char message[80];
	sprintf(message,"Delete # %d",which);
	MessageBox(message,"Delete Edge",MB_OK);
	// FIX THE POINTERS TO THIS EDGE
	// DO IT FOR THE SECTORS
	for (loop = 0; loop < m_sectorcnt; loop ++)
	{
		if (m_sectorlist[loop].edge == which)
		{
			m_sectorlist[loop].edge = t_edge->nextedge;
			m_edgelist[m_edgelist[loop].nextedge].prevedge = 
				m_edgelist[m_sectorlist[loop].edge].prevedge;
		}
	}
	// DO IT FOR THE EDGES
	for (loop = 0; loop < m_edgecnt; loop++)
	{
		if (m_edgelist[loop].nextedge == which)
		{
			m_edgelist[loop].nextedge = t_edge->nextedge;
			m_edgelist[m_edgelist[loop].nextedge].prevedge = 
				m_edgelist[loop].prevedge;
		}
	}

	// RESET THE MEMORY AND THE POINTERS
	for (loop = which; loop < m_edgecnt; loop++)
	{
		memcpy( &m_edgelist[loop],&m_edgelist[loop+1],sizeof(tEdge) );
	}
	m_edgecnt--;	// DECREMENT THE EDGECNT
	// RESET THE POINTERS IN THE SECTORS
	for (loop = 0; loop < m_sectorcnt; loop ++)
	{
		if (m_sectorlist[loop].edge >= which)
			m_sectorlist[loop].edge--;
	}
	// RESET THE POINTERS IN THE EDGES
	for (loop = 0; loop < m_edgecnt; loop ++)
	{
		if (m_edgelist[loop].nextedge >= which)
			m_edgelist[loop].nextedge--;
		if (m_edgelist[loop].prevedge>= which)
			m_edgelist[loop].prevedge--;
	}
}

void CMainFrame::DeleteSector()
{
	char message[80];
	short loop, t_sector;	
	if (m_nearest_edge > -1)
	{
		t_sector = m_edgelist[m_nearest_edge].sector;
		if (m_cursector == &m_sectorlist[t_sector])
		{
			m_cursector = NULL;
		}
		// DELETE IN THE EDGES
		for (loop = 0; loop < m_edgecnt; loop ++)
		{
			if (m_edgelist[loop].sector == t_sector)
			{
				DeleteEdge(loop);
				loop --;
			}
		}
		// DELETE THE ACTUAL SECTOR
		for (loop = t_sector; loop < m_sectorcnt; loop ++)
		{
			memcpy( &m_sectorlist[loop],&m_sectorlist[loop+1],sizeof(tSector) );
		}
		m_sectorcnt--;	
	}
	sprintf(message,"Sectors = %d  Edges = %d",m_sectorcnt,m_edgecnt);
	SetStatusText(1,message);
}

// CLOSES AN EDITING SECTOR IF IT IS OPEN
void CMainFrame::CloseSector()
{
	char message[80];
	sprintf(message,"Close Sector %d?",m_sectorcnt);
	if (MessageBox(message,"Delete Edge",MB_YESNO))
	{
		if (m_cursector != NULL)	// I AM WORKING ON ONE
		{
			m_curedge->nextedge = m_cursector->edge;
			m_firstedge->prevedge = m_edgecnt - 1;	// LINK BACK THE START TO THE END
			m_cursector->flags = SECTOR_FLAGS_CLOSED;
			m_cursector->ceil_tex = 0;
			m_cursector->floor_tex = 0;
			m_cursector->floor_height = 0;
			m_cursector->ceil_height = 2048;
			m_cursector = NULL;
			CheckDoubleSided();
		}
	}
}

void CMainFrame::SnapPoint(tPoint2D *point)
{
	if (m_snap && m_gridsize > 1)
	{
		if (point->x > 0) point->x += (m_gridsize / 2);
		else point->x -= (m_gridsize / 2);
		point->x = (point->x / m_gridsize) * m_gridsize;
		if (point->y > 0) point->y += (m_gridsize / 2);
		else point->y -= (m_gridsize / 2);
		point->y = (point->y / m_gridsize) * m_gridsize;
	}
}

//////////////////////////////////////////////////////////////////
// CheckDeleteEdges
// Purpose:	To find if moving a point caused an edge to be deleted
//////////////////////////////////////////////////////////////////
void CMainFrame::CheckDeleteEdges(tPoint2D *a,tPoint2D *b)
{
	short loop,next;
	for (loop = 0; loop < m_edgecnt; loop++)
	{
		next = m_edgelist[loop].nextedge;
		if (next > -1)
		{
			if (a->x == m_edgelist[loop].pos.x && a->y == m_edgelist[loop].pos.y &&
				b->x == m_edgelist[next].pos.x && 
				b->y == m_edgelist[next].pos.y)
			{
				DeleteEdge(loop);
				loop--;
			}
			if (b->x == m_edgelist[loop].pos.x && b->y == m_edgelist[loop].pos.y &&
				a->x == m_edgelist[next].pos.x && 
				a->y == m_edgelist[next].pos.y)
			{
				DeleteEdge(loop);
				loop--;
			}
			// IF IT IS A SINGLE POINT, DELETE IT
			if (m_edgelist[loop].pos.x == 
				m_edgelist[next].pos.x && 
				m_edgelist[loop].pos.y == 
				m_edgelist[next].pos.y )
			{
				DeleteEdge(loop);
				loop--;
			}
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// Procedure:	GetNearestPoint
// Purpose:		Find the nearest point on a line segment
// Arguments:	Two endpoints to a line segment a and b,
//				and a test point c
// Returns:		Sets the nearest point on the segment in nearest
///////////////////////////////////////////////////////////////////////////////
void CMainFrame::GetNearestPoint(tPoint2D *a,tPoint2D *b,tPoint2D *c,tPoint2D *nearest)
{
/// Local Variables ///////////////////////////////////////////////////////////
	long dot_ta,dot_tb;
///////////////////////////////////////////////////////////////////////////////
	// SEE IF a IS THE NEAREST POINT - ANGLE IS OBTUSE
	dot_ta = (c->x - a->x)*(b->x - a->x) + (c->y - a->y)*(b->y - a->y);
	if (dot_ta <= 0)	// It is off the a vertex
	{
		nearest->x = a->x;
		nearest->y = a->y;
		return;
	}
	dot_tb = (c->x - b->x)*(a->x - b->x) + (c->y - b->y)*(a->y - b->y);
	// SEE IF b IS THE NEAREST POINT - ANGLE IS OBTUSE
	if (dot_tb <= 0)
	{
		nearest->x = b->x;
		nearest->y = b->y;
		return;
	}
	// FIND THE REAL NEAREST POINT ON THE LINE SEGMENT - BASED ON RATIO
	nearest->x = a->x + ((b->x - a->x) * dot_ta)/(dot_ta + dot_tb);
	nearest->y = a->y + ((b->y - a->y) * dot_ta)/(dot_ta + dot_tb);
}

short CMainFrame::GetNearestEdge(CPoint point) 
{
	short loop,winner = -1,next;
	long distance = 20000,tempdist;
	tPoint2D *a,*b,temp,nearest;
	temp.x = (long)((point.x + m_offX - (m_sizeX / 2)) / m_scale);
	temp.y = -(long)((point.y + m_offY - (m_sizeY / 2)) / m_scale);
	// CHECK ALL POINTS
	for (loop = 0; loop < m_edgecnt; loop++)
	{
		a = &m_edgelist[loop].pos;
		next = m_edgelist[loop].nextedge;
		if (next >= 0)
		{
			b = &m_edgelist[next].pos;
			GetNearestPoint(a,b,&temp,&nearest); 
			tempdist =  (nearest.x - temp.x) * (nearest.x - temp.x) + 
						(nearest.y - temp.y) * (nearest.y - temp.y);
			if (tempdist < distance)
			{
				distance = tempdist;
				winner = loop;
				m_nearest_pnt.x = nearest.x;
				m_nearest_pnt.y = nearest.y;
			}
		}
	}
	return winner;
}

// DISTANCE THRESHOLD TO WALLS - SORT OF ARBITRARY -  ABOUT A FOOT
#define DISTANCE_THRESH		256

//////////////////////////////////////////////////////////////////
// Procedure:	CheckCollision
// Purpose:		Make Sure view is not too close to wall
// Returns:		TRUE if Valid Position, else FALSE
//////////////////////////////////////////////////////////////////
BOOL CMainFrame::CheckCollision(short sector, tPoint3D *test) 
{
	short loop,next,cur;
	long tempdist,temp2;
	tPoint2D *a,*b,temp,nearest;
	// CHECK ALL POINTS

	temp.x = test->x;
	temp.y = test->z;

	// IF MY TEST POINT IS OUTSIDE THE CURRENT SECTOR, GET A NEW ONE
	// TODO: COULD BE OPTIMISED BASED ON WHEN YOU CROSS A DOUBLE SIDED EDGE
	//       NO NEED NOW IT IS FAST ENOUGH
	if (!PointInPoly(&m_sectorlist[sector], &temp))
	{
		// GET THE SECTOR THAT THE TEST POINT IS IN
		sector = m_cam_sector = InsideSector(&temp);
	}

	if (sector > -1)
	{
		cur = m_sectorlist[sector].edge;

		for (loop = 0; loop < m_sectorlist[sector].edgecnt; loop++)
		{
			a = &m_edgelist[cur].pos;
			next = m_edgelist[cur].nextedge;
			if (next >= 0)		// IF THERE IS A NEXT
			{
				b = &m_edgelist[next].pos;
				// IF THE EDGE IS DOUBLE SIDED JUST CHECK ENDPOINTS
				if (m_edgelist[cur].backedge > -1)
				{
					// CHECK ONLY THE SQUARED DISTANCE - NO NEED FOR A SQRT
					tempdist =  (a->x - test->x) * (a->x - test->x) + 
								(a->y - test->z) * (a->y - test->z);
					temp2 =		(b->x - test->x) * (b->x - test->x) + 
								(b->y - test->z) * (b->y - test->z);
					// WHICH IS THE CLOSEST
					if (temp2 < tempdist)
						tempdist = temp2;
				}
				else	// EDGE IS NOT DOUBLE SIDED SO FIND NEAREST POINT ON LINE
				{
					GetNearestPoint(a,b,&temp,&nearest); 
					// CHECK ONLY THE SQUARED DISTANCE - NO NEED FOR A SQRT
					tempdist =  (nearest.x - test->x) * (nearest.x - test->x) + 
								(nearest.y - test->z) * (nearest.y - test->z);
				}
				if (tempdist < DISTANCE_THRESH)
				{
					return FALSE;		// TOO CLOSE
				}
			}
			cur = next;
		}

		return TRUE;	// VALID POSITION
	}
	else
		return FALSE;	// OUTSIDE SECTOR

}

#ifdef USE_VERSION2
// FIGURE OUT WHICH QUADRANT THE VERTEX IS RELATIVE TO THE HIT POINT
#define WHICH_QUAD(vertex, hitPos) \
  ( (vertex.x > hitPos->x) ? ((vertex.y > hitPos->y) ? 1 : 4) : ( (vertex.y > hitPos->y) ? 2 : 3) )
// GET THE X INTERCEPT OF THE LINE FROM THE CURRENT VERTEX TO THE NEXT
#define X_INTERCEPT(point1, point2,  hitY) \
  (point2.x - ( ((point2.y - hitY) * (point1.x - point2.x)) / (point1.y - point2.y) ) )

//////////////////////////////////////////////////////////////////
// Procedure:	PointInPoly (SUM OF ANGLES CROSSING VERSION)
// Purpose:		Check if a point is inside a polygon
// Returns:		TRUE if Point is inside polygon, else FALSE
//////////////////////////////////////////////////////////////////
BOOL CMainFrame::PointInPoly(tSector *sector, tPoint2D *hitPos)
{
	short	edge, first, next;
	short	quad, next_quad, delta, total;

	edge = first = sector->edge;    
	quad = WHICH_QUAD(m_edgelist[edge].pos, hitPos);
	total = 0;		// COUNT OF ABSOLUTE SECTORS CROSSED
	/* LOOP THROUGH THE VERTICES IN A SECTOR */
	do {
		next = m_edgelist[edge].nextedge;					
		next_quad = WHICH_QUAD(m_edgelist[next].pos, hitPos);
		delta = next_quad - quad;		// HOW MANY QUADS HAVE I MOVED
		// SPECIAL CASES TO HANDLE CROSSINGS OF MORE THEN ONE QUAD
		switch (delta) {							
			case  2: // IF WE CROSSED THE MIDDLE, FIGURE OUT IF IT WAS CLOCKWISE OR COUNTER
			case -2: 
				// US THE X POSITION AT THE HIT POINT TO DETERMINE WHICH WAY AROUND
				if (X_INTERCEPT(m_edgelist[edge].pos, m_edgelist[next].pos, hitPos->y) > hitPos->x)	
					delta =  - (delta);					
				break;							
			case  3:			// MOVING 3 QUADS IS LIKE MOVING BACK 1
				delta = -1; 
				break;					
			case -3:			// MOVING BACK 3 IS LIKE MOVING FORWARD 1
				delta =	 1; 
				break;				
		}
		/* ADD IN THE DELTA */
		total += delta;
		quad = next_quad;		// RESET FOR NEXT STEP
		edge = next;
	} while (edge != first);

	/* AFTER ALL IS DONE IF THE TOTAL IS 4 THEN WE ARE INSIDE */
	if ((total == +4) || (total == -4)) return TRUE; else return FALSE;
}

#else
//////////////////////////////////////////////////////////////////
// Procedure:	PointInPoly (EDGE CROSSING VERSION)
// Purpose:		Check if a point is inside a polygon
// Returns:		TRUE if Point is inside polygon, else FALSE
//////////////////////////////////////////////////////////////////
BOOL CMainFrame::PointInPoly(tSector *sector, tPoint2D *hitPos)
{
	short  edge, first, next;
	tPoint2D *pnt1,*pnt2;
	BOOL	inside = FALSE;		// INITIAL TEST CONDITION
	BOOL  flag1,flag2;

	edge = first = sector->edge;		// SET UP INITIAL CONDITIONS
	pnt1 = &m_edgelist[edge].pos;
    flag1 = ( hitPos->y >= pnt1->y ) ;	// IS THE FIRST VERTEX OVER OR UNDER THE LINE
	/* LOOP THROUGH THE VERTICES IN A SECTOR */
	do {
		next = m_edgelist[edge].nextedge;	// CHECK THE NEXT VERTEX
		pnt2 = &m_edgelist[next].pos;
	    flag2 = ( hitPos->y >= pnt2->y );	// IS IT OVER OR UNDER

		if (flag1 != flag2)		// MAKE SURE THE EDGE ACTUALLY CROSSES THE TEST X AXIS
		{
			// CALCULATE WHETHER THE SEGMENT ACTUALLY CROSSES THE X TEST AXIS
			// A TRICK FROM GRAPHIC GEMS IV TO GET RID OF THE X INTERCEPT DIVIDE
			if (((pnt2->y - hitPos->y) * (pnt1->x - pnt2->x) >=
				(pnt2->x - hitPos->x) * (pnt1->y - pnt2->y)) == flag2 )
				inside = !inside;	// IF IT CROSSES TOGGLE THE INSIDE FLAG (ODD IS IN, EVEN OUT)
		}
		pnt1 = pnt2;	// RESET FOR NEXT STEP
		edge = next;
		flag1 = flag2;
	} while (edge != first);
	return inside;
}
#endif

//////////////////////////////////////////////////////////////////
// Procedure:	InsideSector
// Purpose:		Find What sector a Point is in
// Returns:		Number of Sector that point is in or -1
// Notes:		Could be optimized based on adjacent sectors
//////////////////////////////////////////////////////////////////
short CMainFrame::InsideSector(tPoint2D *hitPos)
{
	unsigned short loop;
	short ret = -1;
	char message[80];
	for (loop = 0; loop < m_sectorcnt; loop++)	// FOR ALL THE SECTORS
	{
		if ((m_sectorlist[loop].flags & SECTOR_FLAGS_CLOSED) == 1)
		{
			if (PointInPoly(&m_sectorlist[loop],hitPos))
			{
				ret = loop;
				break;
			}
		}
	}

	sprintf(message,"Cam in Sector = %d",ret);
	SetStatusText(1,message);
	return ret;
}