polydbg.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

  /*finally */
  if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0)
    return 1;
  return 0;
}


/*return the number of intersections*/
Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly)
{
  directedLine* temp;
  Int count=0;
  if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail()))
    count++;

  for(temp=poly->getNext(); temp != poly; temp = temp->getNext())
    if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail()))
      count++;
/*printf("ray intersect poly: count=%i\n", count);*/
  return count;
}

Int DBG_pointInsidePoly(Real v[2], directedLine* poly)
{
/*
printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
printf("the polygon is\n");
poly->printList();
*/
  /*for debug purpose*/
  assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 )
	 == (DBG_rayIntersectPoly(v,1,Real(0.1234), poly) % 2 )
	 );
  if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1)
    return 1;
  else
    return 0;
}

/*return the number of polygons which contain thie polygon
 * as a subset
 */
Int DBG_enclosingPolygons(directedLine* poly, directedLine* list)
{
  directedLine* temp;
  Int count=0;
/*
printf("%i\n", DBG_pointInsidePoly(poly->head(),
				   list->getNextPolygon()
				   ->getNextPolygon()
				   ->getNextPolygon()
				   ->getNextPolygon()
));
*/

  for(temp = list; temp != NULL; temp = temp->getNextPolygon())
    {
      if(poly != temp)
	if(DBG_pointInsidePoly(poly->head(), temp))
	  count++;
/*	printf("count=%i\n", count);*/
    }
  return count;
}

void  DBG_reverse(directedLine* poly)
{
  if(poly->getDirection() == INCREASING)
    poly->putDirection(DECREASING);
  else
    poly->putDirection(INCREASING);

  directedLine* oldNext = poly->getNext();
  poly->putNext(poly->getPrev());
  poly->putPrev(oldNext);

  directedLine* temp;
  for(temp=oldNext; temp!=poly; temp = oldNext)
    {
      if(temp->getDirection() == INCREASING)
	temp->putDirection(DECREASING);
      else
	temp->putDirection(INCREASING);

      oldNext = temp->getNext();
      temp->putNext(temp->getPrev());
      temp->putPrev(oldNext);
    }
  printf("reverse done\n");
}

Int DBG_checkConnectivity(directedLine *polygon)
{
  if(polygon == NULL) return 1;
  directedLine* temp;
  if(polygon->head()[0] != polygon->getPrev()->tail()[0] ||
     polygon->head()[1] != polygon->getPrev()->tail()[1])
    return 0;
  for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext())
    {
      if(temp->head()[0] != temp->getPrev()->tail()[0] ||
	 temp->head()[1] != temp->getPrev()->tail()[1])
	return 0;
    }
  return 1;
}

/*print out error message.
 *If it cannot modify the polygon list to make it satify the
 *requirements, return 1.
 *otherwise modify the polygon list, and return 0
 */
Int DBG_check(directedLine *polyList)
{
  directedLine* temp;
  if(polyList == NULL) return 0;

  /*if there are intersections, print out error message
   */
  if(DBG_polygonListIntersect(polyList))
    {
      fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
    return 1;
    }

  /*check the connectivity of each polygon*/
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
    {
      if(! DBG_checkConnectivity(temp))
	{
	  fprintf(stderr, "DBG_check, polygon not connected\n");
	  return 1;
	}
    }

  /*check the orientation of each polygon*/
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
    {


      Int correctDir;

      if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
	correctDir = 1; /*counterclockwise*/
      else
	correctDir = 0; /*clockwise*/

      Int actualDir = DBG_isCounterclockwise(temp);

      if(correctDir != actualDir)
	{
	  fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");

	  DBG_reverse(temp);
	}

    }
  return 0;
}

/**************handle self intersections*****************/
//determine whether e interects [begin, end] or not
static directedLine* DBG_edgeIntersectChainD(directedLine *e,
			       directedLine *begin, directedLine *end)
{
  directedLine *temp;
  for(temp=begin; temp != end; temp = temp->getNext())
    {
      if(DBG_edgesIntersect(e, temp))
	 return temp;
    }
  if(DBG_edgesIntersect(e, end))
    return end;
  return NULL;
}

//given a polygon, cut the edges off and finally obtain a
//a polygon without intersections. The cut-off edges are
//dealloated. The new polygon is returned.
directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur)
{
  directedLine *begin, *end, *next;
  begin = polygon;
  end = polygon;
  cutOccur = 0;
  while( (next = end->getNext()) != begin)
    {
      directedLine *interc = NULL;
      if( (interc = DBG_edgeIntersectChainD(next, begin, end)))
	{
	  int fixed = 0;
	  if(DBG_edgesIntersect(next, interc->getNext()))
	     {
	       //trying to fix it
	       Real buf[2];
	       int i;
	       Int n=5;
	       buf[0] = interc->tail()[0];
	       buf[1] = interc->tail()[1];

	       for(i=1; i<n; i++)
		 {
		   Real r = ((Real)i) / ((Real) n);
		   Real u = (1-r) * interc->head()[0] + r * interc->tail()[0];
		   Real v = (1-r) * interc->head()[1] + r * interc->tail()[1];
		   interc->tail()[0] = interc->getNext()->head()[0] = u;
		   interc->tail()[1] = interc->getNext()->head()[1] = v;
		   if( (! DBG_edgesIntersect(next, interc)) &&
		      (! DBG_edgesIntersect(next, interc->getNext())))
		     break; //we fixed it
		 }
	       if(i==n) // we didn't fix it
		 {
		   fixed = 0;
		   //back to original
		   interc->tail()[0] = interc->getNext()->head()[0] = buf[0];
		   interc->tail()[1] = interc->getNext()->head()[1] = buf[1];
		 }
	       else
		 {
		   fixed = 1;
		 }
	     }
	  if(fixed == 0)
	    {
	      cutOccur = 1;
	      begin->deleteSingleLine(next);

	      if(begin != end)
		{
		  if(DBG_polygonSelfIntersect(begin))
		    {
		      directedLine* newEnd = end->getPrev();
		      begin->deleteSingleLine(end);
		      end = newEnd;
		    }
		}
	    }
	  else
	    {
	      end = end->getNext();
	    }
	}
      else
	{
	  end = end->getNext();
	}
    }
  return begin;
}

//given a polygon, cut the edges off and finally obtain a
//a polygon without intersections. The cut-off edges are
//dealloated. The new polygon is returned.
#if 0 // UNUSED
static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon)
{
  directedLine *crt;//current polygon
  directedLine *begin;
  directedLine *end;
  directedLine *temp;
  crt = polygon;
  int find=0;
  while(1)
    {
//printf("loop\n");
      //if there are less than 3 edges, we should stop
      if(crt->getPrev()->getPrev() == crt)
	return NULL;

      if(DBG_edgesIntersect(crt, crt->getNext()) ||
	(crt->head()[0] == crt->getNext()->tail()[0] &&
	crt->head()[1] == crt->getNext()->tail()[1])
	 )
	{
	  find = 1;
	  crt=crt->deleteChain(crt, crt->getNext());
	}
      else
	{
	  //now we know crt and crt->getNext do not intersect
	  begin = crt;
	  end = crt->getNext();
//printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]);
//printf("end=(%f,%f)\n", end->head()[0], end->head()[1]);
	  for(temp=end->getNext(); temp!=begin; temp= temp->getNext())
	    {
//printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]);
	       directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end);
	       if(intersect != NULL)
		{
		  crt = crt->deleteChain(intersect, temp);
		  find=1;
		  break; //the for loop
		}
	      else
		{
		  end = temp;
		}
	    }
	}
      if(find == 0)
	return crt;
      else
	find = 0;    //go to next loop
}
}
#endif

directedLine* DBG_cutIntersectionAllPoly(directedLine* list)
{
  directedLine* temp;
  directedLine* tempNext=NULL;
  directedLine* ret = NULL;
  int cutOccur=0;
  for(temp=list; temp != NULL; temp = tempNext)
    {
      directedLine *left;
      tempNext = temp->getNextPolygon();

      left = DBG_cutIntersectionPoly(temp, cutOccur);
      if(left != NULL)
	ret=left->insertPolygon(ret);
    }
  return ret;
}

sampledLine*  DBG_collectSampledLinesAllPoly(directedLine *polygonList)
{
  directedLine *temp;
  sampledLine* tempHead = NULL;
  sampledLine* tempTail = NULL;
  sampledLine* cHead = NULL;
  sampledLine* cTail = NULL;

  if(polygonList == NULL)
    return NULL;

  DBG_collectSampledLinesPoly(polygonList, cHead, cTail);

  assert(cHead);
  assert(cTail);
  for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
    {
      DBG_collectSampledLinesPoly(temp, tempHead, tempTail);
      cTail->insert(tempHead);
      cTail = tempTail;
    }
  return cHead;
}

void  DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail)
{
  directedLine *temp;
  retHead = NULL;
  retTail = NULL;
  if(polygon == NULL)
    return;

  retHead = retTail = polygon->getSampledLine();
  for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext())
    {
      retHead = temp->getSampledLine()->insert(retHead);
    }
}