1 /*
2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
9 **
10 ** http://oss.sgi.com/projects/FreeB
11 **
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
17 **
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
23 **
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
33 */
34 
35 /*
36  * slicer.c++
37  *
38  */
39 
40 //#include <stdlib.h>
41 //#include <stdio.h>
42 //#include <math.h>
43 //#include "glimports.h"
44 //#include "mystdio.h"
45 //#include "myassert.h"
46 //#include "bufpool.h"
47 #include "slicer.h"
48 #include "backend.h"
49 //#include "arc.h"
50 //#include "gridtrimvertex.h"
51 #include "simplemath.h"
52 //#include "trimvertex.h"
53 #include "varray.h"
54 
55 #include "polyUtil.h" //for area()
56 
57 //static int count=0;
58 
59 /*USE_OPTTT is initiated in trimvertex.h*/
60 
61 #ifdef USE_OPTTT
62 	#include <GL/gl.h>
63 #endif
64 
65 //#define USE_READ_FLAG //whether to use new or old tesselator
66                           //if defined, it reads "flagFile",
67                           // if the number is 1, then use new tess
68                           // otherwise, use the old tess.
69                          //if not defined, then use new tess.
70 #ifdef USE_READ_FLAG
71 static Int read_flag(char* name);
72 Int newtess_flag = read_flag("flagFile");
73 #endif
74 
75 //#define COUNT_TRIANGLES
76 #ifdef COUNT_TRIANGLES
77 Int num_triangles = 0;
78 Int num_quads = 0;
79 #endif
80 
81 #define max(a,b) ((a>b)? a:b)
82 #define ZERO 0.00001 /*determing whether a loop is a rectngle or not*/
83 #define equalRect(a,b) ((glu_abs(a-b) <= ZERO)? 1:0) //only used in tessellating a rectangle
84 
85 #if 0 // UNUSED
86 static Int is_Convex(Arc_ptr loop)
87 {
88   if(area(loop->tail(), loop->head(), loop->next->head()) <0 )
89     return 0;
90   for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
91     {
92       if(area(jarc->tail(), jarc->head(), jarc->next->head()) < 0)
93 	return 0;
94     }
95   return 1;
96 }
97 #endif
98 
99 /******triangulate a monotone polygon**************/
100 #include "monoTriangulation.h"
101 #if 0 // UNUSED
102 static int is_U_monotone(Arc_ptr loop)
103 {
104   int n_changes=0;
105   int prev_sign;
106   int cur_sign;
107   Arc_ptr temp;
108 
109   cur_sign = compV2InX(loop->head(), loop->tail());
110 
111   n_changes  = (compV2InX(loop->prev->head(), loop->prev->tail())
112 		!= cur_sign);
113 
114   for(temp=loop->next; temp != loop; temp = temp->next)
115     {
116       prev_sign = cur_sign;
117       cur_sign = compV2InX(temp->head(), temp->tail());
118       if(cur_sign != prev_sign)
119        {
120 #ifdef DEBUG
121 	 printf("***change signe\n");
122 #endif
123 	 n_changes++;
124        }
125     }
126   if(n_changes == 2) return 1;
127   else
128     return 0;
129 }
130 #endif
131 
132 inline int compInY(REAL a[2], REAL b[2])
133 {
134   if(a[1] < b[1])
135     return -1;
136   else if (a[1] > b[1])
137     return 1;
138   else if(a[0] > b[0])
139     return 1;
140   else return -1;
141 }
142 
143 void monoTriangulationLoop(Arc_ptr loop, Backend& backend, primStream* pStream)
144 {
145   int i;
146   //find the top, bottom, increasing and decreasing chain
147   //then call monoTrianulation
148   Arc_ptr jarc, temp;
149   Arc_ptr top;
150   Arc_ptr bot;
151   top = bot = loop;
152   if(compInY(loop->tail(), loop->prev->tail()) < 0)
153     {
154       //first find bot
155       for(temp = loop->next; temp != loop; temp = temp->next)
156 	{
157 	  if(compInY(temp->tail(), temp->prev->tail()) > 0)
158 	    break;
159 	}
160       bot = temp->prev;
161       //then find top
162       for(temp=loop->prev; temp != loop; temp = temp->prev)
163 	{
164 	  if(compInY(temp->tail(), temp->prev->tail()) > 0)
165 	    break;
166 	}
167       top = temp;
168     }
169   else //loop > loop->prev
170     {
171       for(temp=loop->next; temp != loop; temp = temp->next)
172 	{
173 	  if(compInY(temp->tail(), temp->prev->tail()) < 0)
174 	    break;
175 	}
176       top = temp->prev;
177       for(temp=loop->prev; temp != loop; temp = temp->prev)
178 	{
179 	  if(compInY(temp->tail(), temp->prev->tail()) < 0)
180 	    break;
181 	}
182       bot = temp;
183     }
184   //creat increase and decrease chains
185   vertexArray inc_chain(50); //this is a dynamci array
186   for(i=1; i<=top->pwlArc->npts-2; i++)
187     {
188       //the first vertex is the top which doesn't below to inc_chain
189       inc_chain.appendVertex(top->pwlArc->pts[i].param);
190     }
191   for(jarc=top->next; jarc != bot; jarc = jarc->next)
192     {
193       for(i=0; i<=jarc->pwlArc->npts-2; i++)
194 	{
195 	  inc_chain.appendVertex(jarc->pwlArc->pts[i].param);
196 	}
197 
198     }
199   vertexArray dec_chain(50);
200   for(jarc = top->prev; jarc != bot; jarc = jarc->prev)
201     {
202       for(i=jarc->pwlArc->npts-2; i>=0; i--)
203 	{
204 	  dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
205 	}
206     }
207   for(i=bot->pwlArc->npts-2; i>=1; i--)
208     {
209       dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
210     }
211 
212   monoTriangulationRec(top->tail(), bot->tail(), &inc_chain, 0,
213 		       &dec_chain, 0, &backend);
214 
215 }
216 
217 /********tesselate a rectanlge (OPTIMIZATION**************/
218 static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend);
219 
220 static Int is_rect(Arc_ptr loop)
221 {
222   Int nlines =1;
223   for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
224     {
225       nlines++;
226       if(nlines == 5)
227 	break;
228     }
229   if(nlines != 4)
230     return 0;
231 
232 
233 /*
234 printf("here1\n");
235 printf("loop->tail=(%f,%f)\n", loop->tail()[0], loop->tail()[1]);
236 printf("loop->head=(%f,%f)\n", loop->head()[0], loop->head()[1]);
237 printf("loop->next->tail=(%f,%f)\n", loop->next->tail()[0], loop->next->tail()[1]);
238 printf("loop->next->head=(%f,%f)\n", loop->next->head()[0], loop->next->head()[1]);
239 if(fglu_abs(loop->tail()[0] - loop->head()[0])<0.000001)
240 	printf("equal 1\n");
241 if(loop->next->tail()[1] == loop->next->head()[1])
242 	printf("equal 2\n");
243 */
244 
245   if( (glu_abs(loop->tail()[0] - loop->head()[0])<=ZERO) &&
246       (glu_abs(loop->next->tail()[1] - loop->next->head()[1])<=ZERO) &&
247       (glu_abs(loop->prev->tail()[1] - loop->prev->head()[1])<=ZERO) &&
248       (glu_abs(loop->prev->prev->tail()[0] - loop->prev->prev->head()[0])<=ZERO)
249      )
250     return 1;
251   else if
252     ( (glu_abs(loop->tail()[1] - loop->head()[1]) <= ZERO) &&
253       (glu_abs(loop->next->tail()[0] - loop->next->head()[0]) <= ZERO) &&
254       (glu_abs(loop->prev->tail()[0] - loop->prev->head()[0]) <= ZERO) &&
255       (glu_abs(loop->prev->prev->tail()[1] - loop->prev->prev->head()[1]) <= ZERO)
256      )
257       return 1;
258   else
259     return 0;
260 }
261 
262 
263 //a line with the same u for opt
264 #ifdef USE_OPTTT
265 static void evalLineNOGE_BU(TrimVertex *verts, int n, Backend& backend)
266 {
267   int i;
268   backend.preEvaluateBU(verts[0].param[0]);
269   for(i=0; i<n; i++)
270     backend.tmeshvertNOGE_BU(&verts[i]);
271 }
272 #endif
273 
274 //a line with the same v for opt
275 #ifdef USE_OPTTT
276 static void evalLineNOGE_BV(TrimVertex *verts, int n, Backend& backend)
277 {
278   int i;
279   backend.preEvaluateBV(verts[0].param[1]);
280 
281   for(i=0; i<n; i++)
282     backend.tmeshvertNOGE_BV(&verts[i]);
283 }
284 #endif
285 
286 #ifdef USE_OPTTT
287 static void evalLineNOGE(TrimVertex *verts, int n, Backend& backend)
288 {
289 
290   if(verts[0].param[0] == verts[n-1].param[0]) //all u;s are equal
291     evalLineNOGE_BU(verts, n, backend);
292   else if(verts[0].param[1] == verts[n-1].param[1]) //all v's are equal
293     evalLineNOGE_BV(verts, n, backend);
294   else
295     {
296       int i;
297       for(i=0; i<n; i++)
298 	backend.tmeshvertNOGE(&verts[i]);
299     }
300 }
301 #endif
302 
303 inline void  OPT_OUTVERT(TrimVertex& vv, Backend& backend)
304 {
305 
306 #ifdef USE_OPTTT
307   glNormal3fv(vv.cache_normal);
308   glVertex3fv(vv.cache_point);
309 #else
310 
311   backend.tmeshvert(&vv);
312 
313 #endif
314 
315 }
316 
317 static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend);
318 
319 static void triangulateRect(Arc_ptr loop, Backend& backend, int TB_or_LR, int ulinear, int vlinear)
320 {
321   //we know the loop is a rectangle, but not sure which is top
322   Arc_ptr top, bot, left, right;
323   if(loop->tail()[1] == loop->head()[1])
324     {
325       if(loop->tail()[1] > loop->prev->prev->tail()[1])
326 	{
327 
328 	top = loop;
329 	}
330       else{
331 
332 	top = loop->prev->prev;
333 	}
334     }
335   else
336     {
337       if(loop->tail()[0] > loop->prev->prev->tail()[0])
338 	{
339 	  //loop is the right arc
340 
341 	  top = loop->next;
342 	}
343       else
344 	{
345 
346 	  top = loop->prev;
347 	}
348     }
349   left = top->next;
350   bot  = left->next;
351   right= bot->next;
352 
353   //if u, v are both nonlinear, then if the
354   //boundary is tessellated dense, we also
355   //sample the inside to get a better tesslletant.
356   if( (!ulinear) && (!vlinear))
357     {
358       int nu = top->pwlArc->npts;
359       if(nu < bot->pwlArc->npts)
360 	nu = bot->pwlArc->npts;
361       int nv = left->pwlArc->npts;
362       if(nv < right->pwlArc->npts)
363 	nv = right->pwlArc->npts;
364 /*
365       if(nu > 2 && nv > 2)
366 	{
367 	  triangulateRectGen(top, nu-2,  nv-2, backend);
368 	  return;
369 	}
370 */
371     }
372 
373   if(TB_or_LR == 1)
374     triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
375   else if(TB_or_LR == -1)
376     triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);
377   else
378     {
379       Int maxPointsTB = top->pwlArc->npts + bot->pwlArc->npts;
380       Int maxPointsLR = left->pwlArc->npts + right->pwlArc->npts;
381 
382       if(maxPointsTB < maxPointsLR)
383 	triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);
384       else
385 	triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
386     }
387 }
388 
389 static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend)
390 { //if(maxPointsTB >= maxPointsLR)
391     {
392 
393       Int d, topd_left, topd_right, botd_left, botd_right, i,j;
394       d = left->npts /2;
395 
396 #ifdef USE_OPTTT
397       evalLineNOGE(top->pts, top->npts, backend);
398       evalLineNOGE(bot->pts, bot->npts, backend);
399       evalLineNOGE(left->pts, left->npts, backend);
400       evalLineNOGE(right->pts, right->npts, backend);
401 #endif
402 
403       if(top->npts == 2) {
404 	backend.bgntfan();
405 	OPT_OUTVERT(top->pts[0], backend);//the root
406 	for(i=0; i<left->npts; i++){
407 	  OPT_OUTVERT(left->pts[i], backend);
408 	}
409 	for(i=1; i<= bot->npts-2; i++){
410 	  OPT_OUTVERT(bot->pts[i], backend);
411 	}
412 	backend.endtfan();
413 
414 	backend.bgntfan();
415 	OPT_OUTVERT(bot->pts[bot->npts-2], backend);
416 	for(i=0; i<right->npts; i++){
417 	  OPT_OUTVERT(right->pts[i], backend);
418 	}
419 	backend.endtfan();
420       }
421       else if(bot->npts == 2) {
422 	backend.bgntfan();
423 	OPT_OUTVERT(bot->pts[0], backend);//the root
424 	for(i=0; i<right->npts; i++){
425 	  OPT_OUTVERT(right->pts[i], backend);
426 	}
427 	for(i=1; i<= top->npts-2; i++){
428 	  OPT_OUTVERT(top->pts[i], backend);
429 	}
430 	backend.endtfan();
431 
432 	backend.bgntfan();
433 	OPT_OUTVERT(top->pts[top->npts-2], backend);
434 	for(i=0; i<left->npts; i++){
435 	  OPT_OUTVERT(left->pts[i], backend);
436 	}
437 	backend.endtfan();
438       }
439       else { //both top and bot have >=3 points
440 
441 	backend.bgntfan();
442 
443 	OPT_OUTVERT(top->pts[top->npts-2], backend);
444 
445 	for(i=0; i<=d; i++)
446 	  {
447 	    OPT_OUTVERT(left->pts[i], backend);
448 	  }
449 	backend.endtfan();
450 
451 	backend.bgntfan();
452 
453 	OPT_OUTVERT(bot->pts[1], backend);
454 
455 	OPT_OUTVERT(top->pts[top->npts-2], backend);
456 
457 	for(i=d; i< left->npts; i++)
458 	  {
459 	    OPT_OUTVERT(left->pts[i], backend);
460 	  }
461 	backend.endtfan();
462 
463 	d = right->npts/2;
464 	//output only when d<right->npts-1 and
465 	//
466 	if(d<right->npts-1)
467 	  {
468 	    backend.bgntfan();
469 	    //      backend.tmeshvert(& top->pts[1]);
470 	    OPT_OUTVERT(top->pts[1], backend);
471 	    for(i=d; i< right->npts; i++)
472 	      {
473 		//	  backend.tmeshvert(& right->pts[i]);
474 
475 		OPT_OUTVERT(right->pts[i], backend);
476 
477 	      }
478 	    backend.endtfan();
479 	  }
480 
481 	backend.bgntfan();
482 	//      backend.tmeshvert(& bot->pts[bot->npts-2]);
483 	OPT_OUTVERT( bot->pts[bot->npts-2], backend);
484 	for(i=0; i<=d; i++)
485 	  {
486 	    //	  backend.tmeshvert(& right->pts[i]);
487 	    OPT_OUTVERT(right->pts[i], backend);
488 
489 	  }
490 
491 	//      backend.tmeshvert(& top->pts[1]);
492 	OPT_OUTVERT(top->pts[1], backend);
493 
494 	backend.endtfan();
495 
496 
497 	topd_left = top->npts-2;
498 	topd_right = 1; //topd_left>= topd_right
499 
500 	botd_left = 1;
501 	botd_right = bot->npts-2; //botd_left<= bot_dright
502 
503 
504 	if(top->npts < bot->npts)
505 	  {
506 	    int delta=bot->npts - top->npts;
507 	    int u = delta/2;
508 	    botd_left = 1+ u;
509 	    botd_right = bot->npts-2-( delta-u);
510 
511 	    if(botd_left >1)
512 	      {
513 		backend.bgntfan();
514 		//	  backend.tmeshvert(& top->pts[top->npts-2]);
515 		OPT_OUTVERT(top->pts[top->npts-2], backend);
516 		for(i=1; i<= botd_left; i++)
517 		  {
518 		    //	      backend.tmeshvert(& bot->pts[i]);
519 		    OPT_OUTVERT(bot->pts[i] , backend);
520 		  }
521 		backend.endtfan();
522 	      }
523 	    if(botd_right < bot->npts-2)
524 	      {
525 		backend.bgntfan();
526 		OPT_OUTVERT(top->pts[1], backend);
527 		for(i=botd_right; i<= bot->npts-2; i++)
528 		  OPT_OUTVERT(bot->pts[i], backend);
529 		backend.endtfan();
530 	      }
531 	  }
532 	else if(top->npts> bot->npts)
533 	  {
534 	    int delta=top->npts-bot->npts;
535 	    int u = delta/2;
536 	    topd_left = top->npts-2 - u;
537 	    topd_right = 1+delta-u;
538 
539 	    if(topd_left < top->npts-2)
540 	      {
541 		backend.bgntfan();
542 		//	  backend.tmeshvert(& bot->pts[1]);
543 		OPT_OUTVERT(bot->pts[1], backend);
544 		for(i=topd_left; i<= top->npts-2; i++)
545 		  {
546 		    //	      backend.tmeshvert(& top->pts[i]);
547 		    OPT_OUTVERT(top->pts[i], backend);
548 		  }
549 		backend.endtfan();
550 	      }
551 	    if(topd_right > 1)
552 	      {
553 		backend.bgntfan();
554 		OPT_OUTVERT(bot->pts[bot->npts-2], backend);
555 		for(i=1; i<= topd_right; i++)
556 		  OPT_OUTVERT(top->pts[i], backend);
557 		backend.endtfan();
558 	      }
559 	  }
560 
561 	if(topd_left <= topd_right)
562 	  return;
563 
564 	backend.bgnqstrip();
565 	for(j=botd_left, i=topd_left; i>=topd_right; i--,j++)
566 	  {
567 	    //	  backend.tmeshvert(& top->pts[i]);
568 	    //	  backend.tmeshvert(& bot->pts[j]);
569 	    OPT_OUTVERT(top->pts[i], backend);
570 	    OPT_OUTVERT(bot->pts[j], backend);
571 	  }
572 	backend.endqstrip();
573 
574       }
575     }
576 }
577 
578 
579 static void triangulateRectCenter(int n_ulines, REAL* u_val,
580 				  int n_vlines, REAL* v_val,
581 				  Backend& backend)
582 {
583 
584   // XXX this code was patched by Diego Santa Cruz <Diego.SantaCruz@epfl.ch>
585   // to fix a problem in which glMapGrid2f() was called with bad parameters.
586   // This has beens submitted to SGI but not integrated as of May 1, 2001.
587   if(n_ulines>1 && n_vlines>1) {
588     backend.surfgrid(u_val[0], u_val[n_ulines-1], n_ulines-1,
589                      v_val[n_vlines-1], v_val[0], n_vlines-1);
590     backend.surfmesh(0,0,n_ulines-1,n_vlines-1);
591   }
592 
593   return;
594 
595   /*
596   for(i=0; i<n_vlines-1; i++)
597     {
598 
599       backend.bgnqstrip();
600       for(j=0; j<n_ulines; j++)
601 	{
602 	  trimVert.param[0] = u_val[j];
603 	  trimVert.param[1] = v_val[i+1];
604 	  backend.tmeshvert(& trimVert);
605 
606 	  trimVert.param[1] = v_val[i];
607 	  backend.tmeshvert(& trimVert);
608 	}
609       backend.endqstrip();
610 
611     }
612     */
613 }
614 
615 //it works for top, bot, left ad right, you need ot select correct arguments
616 static void triangulateRectTopGen(Arc_ptr arc, int n_ulines, REAL* u_val, Real v, int dir, int is_u, Backend& backend)
617 {
618 
619   if(is_u)
620     {
621       int i,k;
622       REAL* upper_val = (REAL*) malloc(sizeof(REAL) * arc->pwlArc->npts);
623       assert(upper_val);
624       if(dir)
625 	{
626 	  for(k=0,i=arc->pwlArc->npts-1; i>=0; i--,k++)
627 	    {
628 	      upper_val[k] = arc->pwlArc->pts[i].param[0];
629 	    }
630 	  backend.evalUStrip(arc->pwlArc->npts, arc->pwlArc->pts[0].param[1],
631 			     upper_val,
632 			     n_ulines, v, u_val);
633 	}
634       else
635 	{
636 	  for(k=0,i=0;  i<arc->pwlArc->npts; i++,k++)
637 	    {
638 	      upper_val[k] = arc->pwlArc->pts[i].param[0];
639 
640 	    }
641 
642 	  backend.evalUStrip(
643 			     n_ulines, v, u_val,
644 			     arc->pwlArc->npts, arc->pwlArc->pts[0].param[1], upper_val
645 			     );
646 	}
647 
648       free(upper_val);
649       return;
650     }
651   else //is_v
652     {
653       int i,k;
654       REAL* left_val = (REAL*) malloc(sizeof(REAL) * arc->pwlArc->npts);
655       assert(left_val);
656       if(dir)
657 	{
658 	  for(k=0,i=arc->pwlArc->npts-1; i>=0; i--,k++)
659 	    {
660 	      left_val[k] = arc->pwlArc->pts[i].param[1];
661 	    }
662 	  backend.evalVStrip(arc->pwlArc->npts, arc->pwlArc->pts[0].param[0],
663 			     left_val,
664 			     n_ulines, v, u_val);
665 	}
666       else
667 	{
668 	  for(k=0,i=0;  i<arc->pwlArc->npts; i++,k++)
669 	    {
670 	      left_val[k] = arc->pwlArc->pts[i].param[1];
671 	    }
672 	   backend.evalVStrip(
673 			     n_ulines, v, u_val,
674 			     arc->pwlArc->npts, arc->pwlArc->pts[0].param[0], left_val
675 			     );
676 	}
677       free(left_val);
678       return;
679     }
680 
681   //the following is a different version of the above code. If you comment
682   //the above code, the following code will still work. The reason to leave
683   //the folliwng code here is purely for testing purpose.
684   /*
685   int i,j;
686   PwlArc* parc = arc->pwlArc;
687   int d1 = parc->npts-1;
688   int d2 = 0;
689   TrimVertex trimVert;
690   trimVert.nuid = 0;//????
691   REAL* temp_u_val = u_val;
692   if(dir ==0) //have to reverse u_val
693     {
694       temp_u_val = (REAL*) malloc(sizeof(REAL) * n_ulines);
695       assert(temp_u_val);
696       for(i=0; i<n_ulines; i++)
697 	temp_u_val[i] = u_val[n_ulines-1-i];
698     }
699   u_val = temp_u_val;
700 
701   if(parc->npts > n_ulines)
702     {
703       d1 = n_ulines-1;
704 
705       backend.bgntfan();
706       if(is_u){
707 	trimVert.param[0] = u_val[0];
708 	trimVert.param[1] = v;
709       }
710       else
711 	{
712 	trimVert.param[1] = u_val[0];
713 	trimVert.param[0] = v;
714       }
715 
716       backend.tmeshvert(& trimVert);
717       for(i=d1; i< parc->npts; i++)
718 	backend.tmeshvert(& parc->pts[i]);
719       backend.endtfan();
720 
721 
722     }
723   else if(parc->npts < n_ulines)
724     {
725       d2 = n_ulines-parc->npts;
726 
727 
728       backend.bgntfan();
729       backend.tmeshvert(& parc->pts[parc->npts-1]);
730       for(i=0; i<= d2; i++)
731 	{
732 	  if(is_u){
733 	    trimVert.param[0] = u_val[i];
734 	    trimVert.param[1] = v;
735 	  }
736 	  else
737 	    {
738 	      trimVert.param[1] = u_val[i];
739 	      trimVert.param[0] = v;
740 	    }
741 	  backend.tmeshvert(&trimVert);
742 	}
743       backend.endtfan();
744 
745     }
746   if(d1>0){
747 
748 
749     backend.bgnqstrip();
750     for(i=d1, j=d2; i>=0; i--, j++)
751       {
752 	backend.tmeshvert(& parc->pts[i]);
753 
754 	if(is_u){
755 	  trimVert.param[0] = u_val[j];
756 	  trimVert.param[1] = v;
757 	}
758 	else{
759 	  trimVert.param[1] = u_val[j];
760 	  trimVert.param[0] = v;
761 	}
762 	backend.tmeshvert(&trimVert);
763 
764 
765 
766       }
767     backend.endqstrip();
768 
769 
770   }
771   if(dir == 0)  //temp_u_val was mallocated
772     free(temp_u_val);
773  */
774 }
775 
776 //n_ulines is the number of ulines inside, and n_vlines is the number of vlines
777 //inside, different from meanings elsewhere!!!
778 static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend)
779 {
780 
781   int i;
782   //we know the loop is a rectangle, but not sure which is top
783   Arc_ptr top, bot, left, right;
784 
785   if(equalRect(loop->tail()[1] ,  loop->head()[1]))
786     {
787 
788       if(loop->tail()[1] > loop->prev->prev->tail()[1])
789 	{
790 
791 	top = loop;
792 	}
793       else{
794 
795 	top = loop->prev->prev;
796 	}
797     }
798   else
799     {
800       if(loop->tail()[0] > loop->prev->prev->tail()[0])
801 	{
802 	  //loop is the right arc
803 
804 	  top = loop->next;
805 	}
806       else
807 	{
808 
809 	  top = loop->prev;
810 	}
811     }
812 
813   left = top->next;
814   bot  = left->next;
815   right= bot->next;
816 
817 #ifdef COUNT_TRIANGLES
818   num_triangles += loop->pwlArc->npts +
819                  left->pwlArc->npts +
820                  bot->pwlArc->npts +
821 		  right->pwlArc->npts
822 		      + 2*n_ulines + 2*n_vlines
823 			-8;
824   num_quads += (n_ulines-1)*(n_vlines-1);
825 #endif
826 /*
827   backend.surfgrid(left->tail()[0], right->tail()[0], n_ulines+1,
828 		   top->tail()[1], bot->tail()[1], n_vlines+1);
829 //  if(n_ulines>1 && n_vlines>1)
830     backend.surfmesh(0,0,n_ulines+1,n_vlines+1);
831 return;
832 */
833   REAL* u_val=(REAL*) malloc(sizeof(REAL)*n_ulines);
834   assert(u_val);
835   REAL* v_val=(REAL*)malloc(sizeof(REAL) * n_vlines);
836   assert(v_val);
837   REAL u_stepsize = (right->tail()[0] - left->tail()[0])/( (REAL) n_ulines+1);
838   REAL v_stepsize = (top->tail()[1] - bot->tail()[1])/( (REAL) n_vlines+1);
839   Real temp=left->tail()[0]+u_stepsize;
840   for(i=0; i<n_ulines; i++)
841     {
842       u_val[i] = temp;
843       temp += u_stepsize;
844     }
845   temp = bot->tail()[1] + v_stepsize;
846   for(i=0; i<n_vlines; i++)
847     {
848       v_val[i] = temp;
849       temp += v_stepsize;
850     }
851 
852   triangulateRectTopGen(top, n_ulines, u_val, v_val[n_vlines-1], 1,1, backend);
853   triangulateRectTopGen(bot, n_ulines, u_val, v_val[0], 0, 1, backend);
854   triangulateRectTopGen(left, n_vlines, v_val, u_val[0], 1, 0, backend);
855   triangulateRectTopGen(right, n_vlines, v_val, u_val[n_ulines-1], 0,0, backend);
856 
857 
858 
859 
860   //triangulate the center
861   triangulateRectCenter(n_ulines, u_val, n_vlines, v_val, backend);
862 
863   free(u_val);
864   free(v_val);
865 
866 }
867 
868 
869 
870 
871 /**********for reading newtess_flag from a file**********/
872 #ifdef USE_READ_FLAG
873 static Int read_flag(char* name)
874 {
875   Int ret;
876   FILE* fp = fopen(name, "r");
877   if(fp == NULL)
878     {
879       fprintf(stderr, "can't open file %s\n", name);
880       exit(1);
881     }
882   fscanf(fp, "%i", &ret);
883   fclose(fp);
884   return ret;
885 }
886 #endif
887 
888 /***********nextgen tess****************/
889 #include "sampleMonoPoly.h"
890 directedLine* arcToDLine(Arc_ptr arc)
891 {
892   int i;
893   Real vert[2];
894   directedLine* ret;
895   sampledLine* sline = new sampledLine(arc->pwlArc->npts);
896   for(i=0; i<arc->pwlArc->npts; i++)
897     {
898       vert[0] = arc->pwlArc->pts[i].param[0];
899       vert[1] = arc->pwlArc->pts[i].param[1];
900       sline->setPoint(i, vert);
901     }
902   ret = new directedLine(INCREASING, sline);
903   return ret;
904 }
905 
906 /*an pwlArc may not be a straight line*/
907 directedLine* arcToMultDLines(directedLine* original, Arc_ptr arc)
908 {
909   directedLine* ret = original;
910   int is_linear = 0;
911   if(arc->pwlArc->npts == 2 )
912     is_linear = 1;
913   else if(area(arc->pwlArc->pts[0].param, arc->pwlArc->pts[1].param, arc->pwlArc->pts[arc->pwlArc->npts-1].param) == 0.0)
914     is_linear = 1;
915 
916   if(is_linear)
917     {
918       directedLine *dline = arcToDLine(arc);
919       if(ret == NULL)
920 	ret = dline;
921       else
922 	ret->insert(dline);
923       return ret;
924     }
925   else /*not linear*/
926     {
927       for(Int i=0; i<arc->pwlArc->npts-1; i++)
928 	{
929 	  Real vert[2][2];
930 	  vert[0][0] = arc->pwlArc->pts[i].param[0];
931 	  vert[0][1] = arc->pwlArc->pts[i].param[1];
932 	  vert[1][0] = arc->pwlArc->pts[i+1].param[0];
933 	  vert[1][1] = arc->pwlArc->pts[i+1].param[1];
934 
935 	  sampledLine *sline = new sampledLine(2, vert);
936 	  directedLine *dline = new directedLine(INCREASING, sline);
937 	  if(ret == NULL)
938 	    ret = dline;
939 	  else
940 	    ret->insert(dline);
941 	}
942       return ret;
943     }
944 }
945 
946 
947 
948 directedLine* arcLoopToDLineLoop(Arc_ptr loop)
949 {
950   directedLine* ret;
951 
952   if(loop == NULL)
953     return NULL;
954   ret = arcToMultDLines(NULL, loop);
955 //ret->printSingle();
956   for(Arc_ptr temp = loop->next; temp != loop; temp = temp->next){
957     ret = arcToMultDLines(ret, temp);
958 //ret->printSingle();
959   }
960 
961   return ret;
962 }
963 
964 /*
965 void Slicer::evalRBArray(rectBlockArray* rbArray, gridWrap* grid)
966 {
967   TrimVertex *trimVert = (TrimVertex*)malloc(sizeof(TrimVertex));
968   trimVert -> nuid = 0;//????
969 
970   Real* u_values = grid->get_u_values();
971   Real* v_values = grid->get_v_values();
972 
973   Int i,j,k,l;
974 
975   for(l=0; l<rbArray->get_n_elements(); l++)
976     {
977       rectBlock* block = rbArray->get_element(l);
978       for(k=0, i=block->get_upGridLineIndex(); i>block->get_lowGridLineIndex(); i--, k++)
979 	{
980 
981 	  backend.bgnqstrip();
982 	  for(j=block->get_leftIndices()[k+1]; j<= block->get_rightIndices()[k+1]; j++)
983 	    {
984 	      trimVert->param[0] = u_values[j];
985 	      trimVert->param[1] = v_values[i];
986 	      backend.tmeshvert(trimVert);
987 
988 	      trimVert->param[1] = v_values[i-1];
989 	      backend.tmeshvert(trimVert);
990 
991 	    }
992 	  backend.endqstrip();
993 
994 	}
995     }
996 
997   free(trimVert);
998 }
999 */
1000 
1001 void Slicer::evalRBArray(rectBlockArray* rbArray, gridWrap* grid)
1002 {
1003   Int i,j,k;
1004 
1005   Int n_vlines=grid->get_n_vlines();
1006   //the reason to switch the position of v_max and v_min is because of the
1007   //the orientation problem. glEvalMesh generates quad_strip clockwise, but
1008   //we need counter-clockwise.
1009   backend.surfgrid(grid->get_u_min(), grid->get_u_max(), grid->get_n_ulines()-1,
1010 		   grid->get_v_max(), grid->get_v_min(), n_vlines-1);
1011 
1012 
1013   for(j=0; j<rbArray->get_n_elements(); j++)
1014     {
1015       rectBlock* block = rbArray->get_element(j);
1016       Int low = block->get_lowGridLineIndex();
1017       Int high = block->get_upGridLineIndex();
1018 
1019       for(k=0, i=high; i>low; i--, k++)
1020 	{
1021 	  backend.surfmesh(block->get_leftIndices()[k+1], n_vlines-1-i, block->get_rightIndices()[k+1]-block->get_leftIndices()[k+1], 1);
1022 	}
1023     }
1024 }
1025 
1026 
1027 void Slicer::evalStream(primStream* pStream)
1028 {
1029   Int i,j,k;
1030   k=0;
1031 /*  TrimVertex X;*/
1032   TrimVertex *trimVert =/*&X*/  (TrimVertex*)malloc(sizeof(TrimVertex));
1033   trimVert -> nuid = 0;//???
1034   Real* vertices = pStream->get_vertices(); //for efficiency
1035   for(i=0; i<pStream->get_n_prims(); i++)
1036     {
1037 
1038      //ith primitive  has #vertices = lengths[i], type=types[i]
1039       switch(pStream->get_type(i)){
1040       case PRIMITIVE_STREAM_FAN:
1041 
1042 	backend.bgntfan();
1043 
1044 	for(j=0; j<pStream->get_length(i); j++)
1045 	  {
1046 	    trimVert->param[0] = vertices[k];
1047 	    trimVert->param[1] = vertices[k+1];
1048 	    backend.tmeshvert(trimVert);
1049 
1050 //	    backend.tmeshvert(vertices[k], vertices[k+1]);
1051 	    k += 2;
1052 	  }
1053 	backend.endtfan();
1054 	break;
1055 
1056       default:
1057 	fprintf(stderr, "evalStream: not implemented yet\n");
1058 	exit(1);
1059 
1060       }
1061     }
1062   free(trimVert);
1063 }
1064 
1065 
1066 
1067 
1068 void Slicer::slice_new(Arc_ptr loop)
1069 {
1070 //count++;
1071 //if(count == 78) count=1;
1072 //printf("count=%i\n", count);
1073 //if( ! (4<= count && count <=4)) return;
1074 
1075 
1076   Int num_ulines;
1077   Int num_vlines;
1078   Real uMin, uMax, vMin, vMax;
1079   Real mydu, mydv;
1080   uMin = uMax = loop->tail()[0];
1081   vMin = vMax = loop->tail()[1];
1082   mydu = (du>0)? du: -du;
1083   mydv = (dv>0)? dv: -dv;
1084 
1085   for(Arc_ptr jarc=loop->next; jarc != loop; jarc = jarc->next)
1086    {
1087 
1088      if(jarc->tail()[0] < uMin)
1089        uMin = jarc->tail()[0];
1090      if(jarc->tail()[0] > uMax)
1091        uMax = jarc->tail()[0];
1092      if(jarc->tail()[1] < vMin)
1093        vMin = jarc->tail()[1];
1094      if(jarc->tail()[1] > vMax)
1095        vMax = jarc->tail()[1];
1096    }
1097 
1098   if (uMax == uMin)
1099     return; // prevent divide-by-zero.  Jon Perry.  17 June 2002
1100 
1101   if(mydu > uMax - uMin)
1102     num_ulines = 2;
1103   else
1104     {
1105       num_ulines = 3 + (Int) ((uMax-uMin)/mydu);
1106     }
1107   if(mydv>=vMax-vMin)
1108     num_vlines = 2;
1109   else
1110     {
1111       num_vlines = 2+(Int)((vMax-vMin)/mydv);
1112     }
1113 
1114   Int isRect = is_rect(loop);
1115 
1116   if(isRect && (num_ulines<=2 || num_vlines<=2))
1117     {
1118       if(vlinear)
1119 	triangulateRect(loop, backend, 1, ulinear, vlinear);
1120       else if(ulinear)
1121 	triangulateRect(loop, backend, -1, ulinear, vlinear);
1122       else
1123 	triangulateRect(loop, backend, 0, ulinear, vlinear);
1124     }
1125 
1126    else if(isRect)
1127     {
1128       triangulateRectGen(loop, num_ulines-2, num_vlines-2, backend);
1129     }
1130   else if( (num_ulines<=2 || num_vlines <=2) && ulinear)
1131     {
1132       monoTriangulationFunBackend(loop, compV2InY, &backend);
1133     }
1134   else if( (!ulinear) && (!vlinear) && (num_ulines == 2) && (num_vlines > 2))
1135     {
1136       monoTriangulationFunBackend(loop, compV2InY, &backend);
1137     }
1138   else
1139     {
1140       directedLine* poly = arcLoopToDLineLoop(loop);
1141 
1142       gridWrap grid(num_ulines, num_vlines, uMin, uMax, vMin, vMax);
1143       primStream pStream(20, 20);
1144       rectBlockArray rbArray(20);
1145 
1146       sampleMonoPoly(poly, &grid, ulinear, vlinear, &pStream, &rbArray);
1147 
1148       evalStream(&pStream);
1149 
1150       evalRBArray(&rbArray, &grid);
1151 
1152 #ifdef COUNT_TRIANGLES
1153       num_triangles += pStream.num_triangles();
1154       num_quads += rbArray.num_quads();
1155 #endif
1156       poly->deleteSinglePolygonWithSline();
1157     }
1158 
1159 #ifdef COUNT_TRIANGLES
1160   printf("num_triangles=%i\n", num_triangles);
1161   printf("num_quads = %i\n", num_quads);
1162 #endif
1163 }
1164 
1165 void Slicer::slice(Arc_ptr loop)
1166 {
1167 #ifdef USE_READ_FLAG
1168   if(read_flag("flagFile"))
1169     slice_new(loop);
1170   else
1171     slice_old(loop);
1172 
1173 #else
1174     slice_new(loop);
1175 #endif
1176 
1177 }
1178 
1179 
1180 
1181 Slicer::Slicer( Backend &b )
1182 	: CoveAndTiler( b ), Mesher( b ), backend( b )
1183 {
1184     oneOverDu = 0;
1185     du = 0;
1186     dv = 0;
1187     isolines = 0;
1188     ulinear = 0;
1189     vlinear = 0;
1190 }
1191 
1192 Slicer::~Slicer()
1193 {
1194 }
1195 
1196 void
1197 Slicer::setisolines( int x )
1198 {
1199     isolines = x;
1200 }
1201 
1202 void
1203 Slicer::setstriptessellation( REAL x, REAL y )
1204 {
1205     assert(x > 0 && y > 0);
1206     du = x;
1207     dv = y;
1208     setDu( du );
1209 }
1210 
1211 void
1212 Slicer::slice_old( Arc_ptr loop )
1213 {
1214     loop->markverts();
1215 
1216     Arc_ptr extrema[4];
1217     loop->getextrema( extrema );
1218 
1219     unsigned int npts = loop->numpts();
1220     TrimRegion::init( npts, extrema[0] );
1221 
1222     Mesher::init( npts );
1223 
1224     long ulines = uarray.init( du, extrema[1], extrema[3] );
1225 //printf("ulines = %i\n", ulines);
1226     Varray varray;
1227     long vlines = varray.init( dv, extrema[0], extrema[2] );
1228 //printf("vlines = %i\n", vlines);
1229     long botv = 0;
1230     long topv;
1231     TrimRegion::init( varray.varray[botv] );
1232     getGridExtent( &extrema[0]->pwlArc->pts[0], &extrema[0]->pwlArc->pts[0] );
1233 
1234     for( long quad=0; quad<varray.numquads; quad++ ) {
1235 	backend.surfgrid( uarray.uarray[0],
1236 		       uarray.uarray[ulines-1],
1237 	 	       ulines-1,
1238 		       varray.vval[quad],
1239 		       varray.vval[quad+1],
1240 		       varray.voffset[quad+1] - varray.voffset[quad] );
1241 
1242 	for( long i=varray.voffset[quad]+1; i <= varray.voffset[quad+1]; i++ ) {
1243     	    topv = botv++;
1244     	    advance( topv - varray.voffset[quad],
1245 		     botv - varray.voffset[quad],
1246 		     varray.varray[botv] );
1247 	    if( i == vlines )
1248 		getPts( extrema[2] );
1249 	    else
1250 		getPts( backend );
1251 	    getGridExtent();
1252             if( isolines ) {
1253 	        outline();
1254 	    } else {
1255 		if( canTile() )
1256 		    coveAndTile();
1257 		else
1258 		    mesh();
1259 	    }
1260         }
1261    }
1262 }
1263 
1264 
1265 void
1266 Slicer::outline( void )
1267 {
1268     GridTrimVertex upper, lower;
1269     Hull::init( );
1270 
1271     backend.bgnoutline();
1272     while( (nextupper( &upper )) ) {
1273 	if( upper.isGridVert() )
1274 	    backend.linevert( upper.g );
1275 	else
1276 	    backend.linevert( upper.t );
1277     }
1278     backend.endoutline();
1279 
1280     backend.bgnoutline();
1281     while( (nextlower( &lower )) ) {
1282 	if( lower.isGridVert() )
1283 	    backend.linevert( lower.g );
1284 	else
1285 	    backend.linevert( lower.t );
1286     }
1287     backend.endoutline();
1288 }
1289 
1290 
1291 void
1292 Slicer::outline( Arc_ptr jarc )
1293 {
1294     jarc->markverts();
1295 
1296     if( jarc->pwlArc->npts >= 2 ) {
1297 	backend.bgnoutline();
1298 	for( int j = jarc->pwlArc->npts-1; j >= 0; j--  )
1299 	    backend.linevert( &(jarc->pwlArc->pts[j]) );
1300 	backend.endoutline();
1301     }
1302 }
1303 
1304 
1305