src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc - public/gem5-resources - Git at Google

 /*
 ** License Applicability. Except to the extent portions of this file are
 ** made subject to an alternative license as permitted in the SGI Free
 ** Software License B, Version 1.1 (the "License"), the contents of this
 ** file are subject only to the provisions of the License. You may not use
 ** this file except in compliance with the License. You may obtain a copy
 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
 **
 ** http://oss.sgi.com/projects/FreeB
 **
 ** Note that, as provided in the License, the Software is distributed on an
 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
 **
 ** Original Code. The Original Code is: OpenGL Sample Implementation,
 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
 ** Copyright in any portions created by third parties is as indicated
 ** elsewhere herein. All Rights Reserved.
 **
 ** Additional Notice Provisions: The application programming interfaces
 ** established by SGI in conjunction with the Original Code are The
 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
 ** Window System(R) (Version 1.3), released October 19, 1998. This software
 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
 ** published by SGI, but has not been independently verified as being
 ** compliant with the OpenGL(R) version 1.2.1 Specification.
 **
 ** $Date: 2012/03/29 17:22:17 $ $Revision: 1.1.1.1 $
 */
 /*
  *monoPolyPart.C
  *
  *To partition a v-monotone polygon into some uv-monotone polygons.
  *The algorithm is different from the general monotone partition algorithm.
  *while the general monotone partition algorithm works for this special case,
  *but it is more expensive (O(nlogn)). The algorithm implemented here takes
  *advantage of the fact that the input is a v-monotone polygon and it is
  *conceptually simpler and  computationally cheaper (a linear time algorithm).
  *The algorithm is described in Zicheng Liu's  paper
  * "Quality-Oriented Linear Time Tessellation".
  */

 #include <stdlib.h>
 #include <stdio.h>
 #include "directedLine.h"
 #include "monoPolyPart.h"

 /*a vertex is u_maximal if both of its two neightbors are to the left of this
  *vertex
  */
 static Int is_u_maximal(directedLine* v)
 {
   if (compV2InX(v->getPrev()->head(), v->head()) == -1 &&
       compV2InX(v->getNext()->head(), v->head()) == -1)
     return 1;
   else
     return 0;
 }

 /*a vertex is u_minimal if both of its two neightbors are to the right of this
  *vertex
  */
 static Int is_u_minimal(directedLine* v)
 {
   if (compV2InX(v->getPrev()->head(), v->head()) == 1 &&
       compV2InX(v->getNext()->head(), v->head()) == 1)
     return 1;
   else
     return 0;
 }

 /*poly: a v-monotone polygon
  *return: a linked list of uv-monotone polygons.
  */
 directedLine* monoPolyPart(directedLine* polygon)
 {
   //handle special cases:
   if(polygon == NULL)
     return NULL;
   if(polygon->getPrev() == polygon)
     return polygon;
   if(polygon->getPrev() == polygon->getNext())
     return polygon;
   if(polygon->getPrev()->getPrev() == polygon->getNext())
     return polygon;

   //find the top and bottom vertexes
   directedLine *tempV, *topV, *botV;
   topV = botV = polygon;
   for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
     {
       if(compV2InY(topV->head(), tempV->head())<0) {
 	topV = tempV;
       }
       if(compV2InY(botV->head(), tempV->head())>0) {
 	botV = tempV;
       }
     }

   //initilization
   directedLine *A, *B, *C, *D, *G, *H;
   //find A:the first u_maximal vertex on the left chain
   //and C: the left most vertex between top and A
   A = NULL;
   C = topV;
   for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext())
     {
       if(tempV->head()[0] < C->head()[0])
 	C = tempV;

       if(is_u_maximal(tempV))
 	{
 	  A = tempV;
 	  break;
 	}
     }
   if(A == NULL)
     {
       A = botV;
       if(A->head()[0] < C->head()[0])
 	C = A;
     }

   //find B: the first u_minimal vertex on the right chain
   //and  D: the right most vertex between top and B
   B = NULL;
   D = topV;
   for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
     {
       if(tempV->head()[0] > D->head()[0])
 	D = tempV;
       if(is_u_minimal(tempV))
 	{
 	  B = tempV;
 	  break;
 	}
     }
   if(B == NULL)
     {
       B = botV;
       if(B->head()[0] > D->head()[0])
 	D = B;
     }

   //error checking XXX
   if(C->head()[0] >= D->head()[0])
     return polygon;

   //find G on the left chain that is right above B
   for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1;  tempV=tempV->getNext());
   G = tempV->getPrev();
   //find H on the right chain that is right above A
   for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
   H = tempV->getNext();

   //Main Loop
   directedLine* ret = NULL;
   directedLine* currentPolygon = polygon;
   while(1)
     {
       //if both B and D are equal to botV, then this polygon is already
       //u-monotone
       if(A == botV && B == botV)
 	{
 	  ret = currentPolygon->insertPolygon(ret);
 	  return ret;
 	}
       else //not u-monotone
 	{
 	  directedLine *ret_p1, *ret_p2;
 	  if(compV2InY(A->head(),B->head()) == 1) //A is above B
 	    {
 	      directedLine* E = NULL;
 	      for(tempV = C; tempV != D; tempV = tempV->getPrev())
 		{
 		  if(tempV->head()[0] >= A->head()[0])
 		    {
 		      E = tempV;
 		      break;
 		    }
 		}

 	      if(E == NULL)
 		E = D;
 	      if(E->head()[0]> H->head()[0])
 		E = H;
 	      //connect AE and output polygon ECA
 	      polygon->connectDiagonal_2slines(A, E,
 					       &ret_p1,
 					       &ret_p2,
 					       NULL);
 	      ret = ret_p2->insertPolygon(ret);
 	      currentPolygon = ret_p1;

 	      if(E == D)
 		D = ret_p1;
 	      if(E == H)
 		H = ret_p1;
               if(G->head()[1] >= A->head()[1])
 		G = A;
 	      //update A to be the next u-maxiaml vertex on left chain
 	      //and C the leftmost vertex between the old A and the new A
 	      C = A;
 	      for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext())
 		{

 		  if(tempV->head()[0] < C->head()[0])
 		    C = tempV;
 		  if(is_u_maximal(tempV))
 		    {
 		      A = tempV;
 		      break;
 		    }
 		}

 	      if(tempV == botV)
 		{
 		  A = botV;
 		  if(botV->head()[0] < C->head()[0])
 		    C = botV;
 		}
 	      //update H

               if(A == botV)
 		H = botV;
               else
 		{
 		  for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
 		  H = tempV->getNext();
 		}

 	    }
 	  else //A is below B
 	    {

 	      directedLine* F = NULL;
 	      for(tempV = D; tempV != C; tempV = tempV->getNext())
 		{
 		  if(tempV->head()[0] <= B->head()[0])
 		    {
 		      F = tempV;
 		      break;
 		    }
 		}
 	      if(F == NULL)
 		F = C;
 	      if(F->head()[0] < G->head()[0])
 		F = G;

 	      //connect FB
 	      polygon->connectDiagonal_2slines(F, B,
 					       &ret_p1,
 					       &ret_p2,
 					       NULL);
 	      ret = ret_p2->insertPolygon(ret);
 	      currentPolygon = ret_p1;
 	      B = ret_p1;
 	      if(H ->head()[1] >= B->head()[1])
 		H = ret_p1;

 	      //update B to be the next u-minimal vertex on right chain
 	      //and D the rightmost vertex between the old B and the new B
 	      D = B;
 	      for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev())
 		{
 		  if(tempV->head()[0] > D->head()[0])
 		    D = tempV;
 		  if(is_u_minimal(tempV))
 		    {
 		      B = tempV;
 		      break;
 		    }
 		}
 	      if(tempV == botV)
 		{
 		  B = botV;
 		  if(botV->head()[0] > D->head()[0])
 		    D = botV;
 		}
 	      //update G
               if(B == botV)
 		G = botV;
               else
 		{
 		  for(tempV = G; compV2InY(tempV->head(), B->head()) == 1;  tempV = tempV->getNext());
 		  G = tempV->getPrev();
 		}
 	    } //end of A is below B
 	} //end not u-monotone
     } //end of main loop
 }
	/*
	** License Applicability. Except to the extent portions of this file are
	** made subject to an alternative license as permitted in the SGI Free
	** Software License B, Version 1.1 (the "License"), the contents of this
	** file are subject only to the provisions of the License. You may not use
	** this file except in compliance with the License. You may obtain a copy
	** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
	** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
	**
	** http://oss.sgi.com/projects/FreeB
	**
	** Note that, as provided in the License, the Software is distributed on an
	** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
	** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
	** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
	** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
	**
	** Original Code. The Original Code is: OpenGL Sample Implementation,
	** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
	** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
	** Copyright in any portions created by third parties is as indicated
	** elsewhere herein. All Rights Reserved.
	**
	** Additional Notice Provisions: The application programming interfaces
	** established by SGI in conjunction with the Original Code are The
	** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
	** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
	** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
	** Window System(R) (Version 1.3), released October 19, 1998. This software
	** was created using the OpenGL(R) version 1.2.1 Sample Implementation
	** published by SGI, but has not been independently verified as being
	** compliant with the OpenGL(R) version 1.2.1 Specification.
	**
	** $Date: 2012/03/29 17:22:17 $ $Revision: 1.1.1.1 $
	*/
	/*
	*monoPolyPart.C
	*
	*To partition a v-monotone polygon into some uv-monotone polygons.
	*The algorithm is different from the general monotone partition algorithm.
	*while the general monotone partition algorithm works for this special case,
	*but it is more expensive (O(nlogn)). The algorithm implemented here takes
	*advantage of the fact that the input is a v-monotone polygon and it is
	*conceptually simpler and computationally cheaper (a linear time algorithm).
	*The algorithm is described in Zicheng Liu's paper
	* "Quality-Oriented Linear Time Tessellation".
	*/

	#include <stdlib.h>
	#include <stdio.h>
	#include "directedLine.h"
	#include "monoPolyPart.h"

	/*a vertex is u_maximal if both of its two neightbors are to the left of this
	*vertex
	*/
	static Int is_u_maximal(directedLine* v)
	{
	if (compV2InX(v->getPrev()->head(), v->head()) == -1 &&
	compV2InX(v->getNext()->head(), v->head()) == -1)
	return 1;
	else
	return 0;
	}

	/*a vertex is u_minimal if both of its two neightbors are to the right of this
	*vertex
	*/
	static Int is_u_minimal(directedLine* v)
	{
	if (compV2InX(v->getPrev()->head(), v->head()) == 1 &&
	compV2InX(v->getNext()->head(), v->head()) == 1)
	return 1;
	else
	return 0;
	}

	/*poly: a v-monotone polygon
	*return: a linked list of uv-monotone polygons.
	*/
	directedLine* monoPolyPart(directedLine* polygon)
	{
	//handle special cases:
	if(polygon == NULL)
	return NULL;
	if(polygon->getPrev() == polygon)
	return polygon;
	if(polygon->getPrev() == polygon->getNext())
	return polygon;
	if(polygon->getPrev()->getPrev() == polygon->getNext())
	return polygon;

	//find the top and bottom vertexes
	directedLine tempV, topV, *botV;
	topV = botV = polygon;
	for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
	{
	if(compV2InY(topV->head(), tempV->head())<0) {
	topV = tempV;
	}
	if(compV2InY(botV->head(), tempV->head())>0) {
	botV = tempV;
	}
	}

	//initilization
	directedLine A, B, C, D, G, H;
	//find A:the first u_maximal vertex on the left chain
	//and C: the left most vertex between top and A
	A = NULL;
	C = topV;
	for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext())
	{
	if(tempV->head()[0] < C->head()[0])
	C = tempV;

	if(is_u_maximal(tempV))
	{
	A = tempV;
	break;
	}
	}
	if(A == NULL)
	{
	A = botV;
	if(A->head()[0] < C->head()[0])
	C = A;
	}

	//find B: the first u_minimal vertex on the right chain
	//and D: the right most vertex between top and B
	B = NULL;
	D = topV;
	for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
	{
	if(tempV->head()[0] > D->head()[0])
	D = tempV;
	if(is_u_minimal(tempV))
	{
	B = tempV;
	break;
	}
	}
	if(B == NULL)
	{
	B = botV;
	if(B->head()[0] > D->head()[0])
	D = B;
	}

	//error checking XXX
	if(C->head()[0] >= D->head()[0])
	return polygon;

	//find G on the left chain that is right above B
	for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1; tempV=tempV->getNext());
	G = tempV->getPrev();
	//find H on the right chain that is right above A
	for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
	H = tempV->getNext();

	//Main Loop
	directedLine* ret = NULL;
	directedLine* currentPolygon = polygon;
	while(1)
	{
	//if both B and D are equal to botV, then this polygon is already
	//u-monotone
	if(A == botV && B == botV)
	{
	ret = currentPolygon->insertPolygon(ret);
	return ret;
	}
	else //not u-monotone
	{
	directedLine ret_p1, ret_p2;
	if(compV2InY(A->head(),B->head()) == 1) //A is above B
	{
	directedLine* E = NULL;
	for(tempV = C; tempV != D; tempV = tempV->getPrev())
	{
	if(tempV->head()[0] >= A->head()[0])
	{
	E = tempV;
	break;
	}
	}

	if(E == NULL)
	E = D;
	if(E->head()[0]> H->head()[0])
	E = H;
	//connect AE and output polygon ECA
	polygon->connectDiagonal_2slines(A, E,
	&ret_p1,
	&ret_p2,
	NULL);
	ret = ret_p2->insertPolygon(ret);
	currentPolygon = ret_p1;

	if(E == D)
	D = ret_p1;
	if(E == H)
	H = ret_p1;
	if(G->head()[1] >= A->head()[1])
	G = A;
	//update A to be the next u-maxiaml vertex on left chain
	//and C the leftmost vertex between the old A and the new A
	C = A;
	for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext())
	{

	if(tempV->head()[0] < C->head()[0])
	C = tempV;
	if(is_u_maximal(tempV))
	{
	A = tempV;
	break;
	}
	}

	if(tempV == botV)
	{
	A = botV;
	if(botV->head()[0] < C->head()[0])
	C = botV;
	}
	//update H

	if(A == botV)
	H = botV;
	else
	{
	for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
	H = tempV->getNext();
	}

	}
	else //A is below B
	{

	directedLine* F = NULL;
	for(tempV = D; tempV != C; tempV = tempV->getNext())
	{
	if(tempV->head()[0] <= B->head()[0])
	{
	F = tempV;
	break;
	}
	}
	if(F == NULL)
	F = C;
	if(F->head()[0] < G->head()[0])
	F = G;

	//connect FB
	polygon->connectDiagonal_2slines(F, B,
	&ret_p1,
	&ret_p2,
	NULL);
	ret = ret_p2->insertPolygon(ret);
	currentPolygon = ret_p1;
	B = ret_p1;
	if(H ->head()[1] >= B->head()[1])
	H = ret_p1;

	//update B to be the next u-minimal vertex on right chain
	//and D the rightmost vertex between the old B and the new B
	D = B;
	for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev())
	{
	if(tempV->head()[0] > D->head()[0])
	D = tempV;
	if(is_u_minimal(tempV))
	{
	B = tempV;
	break;
	}
	}
	if(tempV == botV)
	{
	B = botV;
	if(botV->head()[0] > D->head()[0])
	D = botV;
	}
	//update G
	if(B == botV)
	G = botV;
	else
	{
	for(tempV = G; compV2InY(tempV->head(), B->head()) == 1; tempV = tempV->getNext());
	G = tempV->getPrev();
	}
	} //end of A is below B
	} //end not u-monotone
	} //end of main loop
	}