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
71static Int read_flag(char* name);
72Int newtess_flag = read_flag("flagFile");
73#endif
74
75//#define COUNT_TRIANGLES
76#ifdef COUNT_TRIANGLES
77Int num_triangles = 0;
78Int 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
86static 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
102static 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
132inline 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
143void 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**************/
218static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend);
219
220static 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/*
234printf("here1\n");
235printf("loop->tail=(%f,%f)\n", loop->tail()[0], loop->tail()[1]);
236printf("loop->head=(%f,%f)\n", loop->head()[0], loop->head()[1]);
237printf("loop->next->tail=(%f,%f)\n", loop->next->tail()[0], loop->next->tail()[1]);
238printf("loop->next->head=(%f,%f)\n", loop->next->head()[0], loop->next->head()[1]);
239if(fglu_abs(loop->tail()[0] - loop->head()[0])<0.000001)
240	printf("equal 1\n");
241if(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
265static 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
276static 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
287static 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
303inline 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
317static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend);
318
319static 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
389static 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
579static 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
616static 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!!!
778static 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);
831return;
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
873static 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"
890directedLine* 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*/
907directedLine* 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
948directedLine* 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/*
965void 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
1001void 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
1027void 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
1068void 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
1165void 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
1181Slicer::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
1192Slicer::~Slicer()
1193{
1194}
1195
1196void
1197Slicer::setisolines( int x )
1198{
1199    isolines = x;
1200}
1201
1202void
1203Slicer::setstriptessellation( REAL x, REAL y )
1204{
1205    assert(x > 0 && y > 0);
1206    du = x;
1207    dv = y;
1208    setDu( du );
1209}
1210
1211void
1212Slicer::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
1265void
1266Slicer::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
1291void
1292Slicer::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