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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
43 #include "glimports.h"
50 #include "gridtrimvertex.h"
51 #include "simplemath.h"
52 #include "trimvertex.h"
55 #include "polyUtil.h" //for area()
59 /*USE_OPTTT is initiated in trimvertex.h*/
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.
71 static Int
read_flag(char* name
);
72 Int newtess_flag
= read_flag("flagFile");
75 //#define COUNT_TRIANGLES
76 #ifdef COUNT_TRIANGLES
77 Int num_triangles
= 0;
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
86 static Int
is_Convex(Arc_ptr loop
)
88 if(area(loop
->tail(), loop
->head(), loop
->next
->head()) <0 )
90 for(Arc_ptr jarc
= loop
->next
; jarc
!= loop
; jarc
= jarc
->next
)
92 if(area(jarc
->tail(), jarc
->head(), jarc
->next
->head()) < 0)
99 /******triangulate a monotone polygon**************/
100 #include "monoTriangulation.h"
102 static int is_U_monotone(Arc_ptr loop
)
109 cur_sign
= compV2InX(loop
->head(), loop
->tail());
111 n_changes
= (compV2InX(loop
->prev
->head(), loop
->prev
->tail())
114 for(temp
=loop
->next
; temp
!= loop
; temp
= temp
->next
)
116 prev_sign
= cur_sign
;
117 cur_sign
= compV2InX(temp
->head(), temp
->tail());
118 if(cur_sign
!= prev_sign
)
121 printf("***change signe\n");
126 if(n_changes
== 2) return 1;
132 inline int compInY(REAL a
[2], REAL b
[2])
136 else if (a
[1] > b
[1])
143 void monoTriangulationLoop(Arc_ptr loop
, Backend
& backend
, primStream
* pStream
)
146 //find the top, bottom, increasing and decreasing chain
147 //then call monoTrianulation
152 if(compInY(loop
->tail(), loop
->prev
->tail()) < 0)
155 for(temp
= loop
->next
; temp
!= loop
; temp
= temp
->next
)
157 if(compInY(temp
->tail(), temp
->prev
->tail()) > 0)
162 for(temp
=loop
->prev
; temp
!= loop
; temp
= temp
->prev
)
164 if(compInY(temp
->tail(), temp
->prev
->tail()) > 0)
169 else //loop > loop->prev
171 for(temp
=loop
->next
; temp
!= loop
; temp
= temp
->next
)
173 if(compInY(temp
->tail(), temp
->prev
->tail()) < 0)
177 for(temp
=loop
->prev
; temp
!= loop
; temp
= temp
->prev
)
179 if(compInY(temp
->tail(), temp
->prev
->tail()) < 0)
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
++)
188 //the first vertex is the top which doesn't below to inc_chain
189 inc_chain
.appendVertex(top
->pwlArc
->pts
[i
].param
);
191 for(jarc
=top
->next
; jarc
!= bot
; jarc
= jarc
->next
)
193 for(i
=0; i
<=jarc
->pwlArc
->npts
-2; i
++)
195 inc_chain
.appendVertex(jarc
->pwlArc
->pts
[i
].param
);
199 vertexArray
dec_chain(50);
200 for(jarc
= top
->prev
; jarc
!= bot
; jarc
= jarc
->prev
)
202 for(i
=jarc
->pwlArc
->npts
-2; i
>=0; i
--)
204 dec_chain
.appendVertex(jarc
->pwlArc
->pts
[i
].param
);
207 for(i
=bot
->pwlArc
->npts
-2; i
>=1; i
--)
209 dec_chain
.appendVertex(jarc
->pwlArc
->pts
[i
].param
);
212 monoTriangulationRec(top
->tail(), bot
->tail(), &inc_chain
, 0,
213 &dec_chain
, 0, &backend
);
217 /********tesselate a rectanlge (OPTIMIZATION**************/
218 static void triangulateRectGen(Arc_ptr loop
, int n_ulines
, int n_vlines
, Backend
& backend
);
220 static Int
is_rect(Arc_ptr loop
)
223 for(Arc_ptr jarc
= loop
->next
; jarc
!= loop
; jarc
= jarc
->next
)
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)
241 if(loop->next->tail()[1] == loop->next->head()[1])
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
)
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
)
263 //a line with the same u for opt
265 static void evalLineNOGE_BU(TrimVertex
*verts
, int n
, Backend
& backend
)
268 backend
.preEvaluateBU(verts
[0].param
[0]);
270 backend
.tmeshvertNOGE_BU(&verts
[i
]);
274 //a line with the same v for opt
276 static void evalLineNOGE_BV(TrimVertex
*verts
, int n
, Backend
& backend
)
279 backend
.preEvaluateBV(verts
[0].param
[1]);
282 backend
.tmeshvertNOGE_BV(&verts
[i
]);
287 static void evalLineNOGE(TrimVertex
*verts
, int n
, Backend
& backend
)
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
);
298 backend
.tmeshvertNOGE(&verts
[i
]);
303 inline void OPT_OUTVERT(TrimVertex
& vv
, Backend
& backend
)
307 glNormal3fv(vv
.cache_normal
);
308 glVertex3fv(vv
.cache_point
);
311 backend
.tmeshvert(&vv
);
317 static void triangulateRectAux(PwlArc
* top
, PwlArc
* bot
, PwlArc
* left
, PwlArc
* right
, Backend
& backend
);
319 static void triangulateRect(Arc_ptr loop
, Backend
& backend
, int TB_or_LR
, int ulinear
, int vlinear
)
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])
325 if(loop
->tail()[1] > loop
->prev
->prev
->tail()[1])
332 top
= loop
->prev
->prev
;
337 if(loop
->tail()[0] > loop
->prev
->prev
->tail()[0])
339 //loop is the right arc
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
))
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
;
367 triangulateRectGen(top, nu-2, nv-2, backend);
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
);
379 Int maxPointsTB
= top
->pwlArc
->npts
+ bot
->pwlArc
->npts
;
380 Int maxPointsLR
= left
->pwlArc
->npts
+ right
->pwlArc
->npts
;
382 if(maxPointsTB
< maxPointsLR
)
383 triangulateRectAux(left
->pwlArc
, right
->pwlArc
, bot
->pwlArc
, top
->pwlArc
, backend
);
385 triangulateRectAux(top
->pwlArc
, bot
->pwlArc
, left
->pwlArc
, right
->pwlArc
, backend
);
389 static void triangulateRectAux(PwlArc
* top
, PwlArc
* bot
, PwlArc
* left
, PwlArc
* right
, Backend
& backend
)
390 { //if(maxPointsTB >= maxPointsLR)
393 Int d
, topd_left
, topd_right
, botd_left
, botd_right
, i
,j
;
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
);
405 OPT_OUTVERT(top
->pts
[0], backend
);//the root
406 for(i
=0; i
<left
->npts
; i
++){
407 OPT_OUTVERT(left
->pts
[i
], backend
);
409 for(i
=1; i
<= bot
->npts
-2; i
++){
410 OPT_OUTVERT(bot
->pts
[i
], backend
);
415 OPT_OUTVERT(bot
->pts
[bot
->npts
-2], backend
);
416 for(i
=0; i
<right
->npts
; i
++){
417 OPT_OUTVERT(right
->pts
[i
], backend
);
421 else if(bot
->npts
== 2) {
423 OPT_OUTVERT(bot
->pts
[0], backend
);//the root
424 for(i
=0; i
<right
->npts
; i
++){
425 OPT_OUTVERT(right
->pts
[i
], backend
);
427 for(i
=1; i
<= top
->npts
-2; i
++){
428 OPT_OUTVERT(top
->pts
[i
], backend
);
433 OPT_OUTVERT(top
->pts
[top
->npts
-2], backend
);
434 for(i
=0; i
<left
->npts
; i
++){
435 OPT_OUTVERT(left
->pts
[i
], backend
);
439 else { //both top and bot have >=3 points
443 OPT_OUTVERT(top
->pts
[top
->npts
-2], backend
);
447 OPT_OUTVERT(left
->pts
[i
], backend
);
453 OPT_OUTVERT(bot
->pts
[1], backend
);
455 OPT_OUTVERT(top
->pts
[top
->npts
-2], backend
);
457 for(i
=d
; i
< left
->npts
; i
++)
459 OPT_OUTVERT(left
->pts
[i
], backend
);
464 //output only when d<right->npts-1 and
469 // backend.tmeshvert(& top->pts[1]);
470 OPT_OUTVERT(top
->pts
[1], backend
);
471 for(i
=d
; i
< right
->npts
; i
++)
473 // backend.tmeshvert(& right->pts[i]);
475 OPT_OUTVERT(right
->pts
[i
], backend
);
482 // backend.tmeshvert(& bot->pts[bot->npts-2]);
483 OPT_OUTVERT( bot
->pts
[bot
->npts
-2], backend
);
486 // backend.tmeshvert(& right->pts[i]);
487 OPT_OUTVERT(right
->pts
[i
], backend
);
491 // backend.tmeshvert(& top->pts[1]);
492 OPT_OUTVERT(top
->pts
[1], backend
);
497 topd_left
= top
->npts
-2;
498 topd_right
= 1; //topd_left>= topd_right
501 botd_right
= bot
->npts
-2; //botd_left<= bot_dright
504 if(top
->npts
< bot
->npts
)
506 int delta
=bot
->npts
- top
->npts
;
509 botd_right
= bot
->npts
-2-( delta
-u
);
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
++)
518 // backend.tmeshvert(& bot->pts[i]);
519 OPT_OUTVERT(bot
->pts
[i
] , backend
);
523 if(botd_right
< bot
->npts
-2)
526 OPT_OUTVERT(top
->pts
[1], backend
);
527 for(i
=botd_right
; i
<= bot
->npts
-2; i
++)
528 OPT_OUTVERT(bot
->pts
[i
], backend
);
532 else if(top
->npts
> bot
->npts
)
534 int delta
=top
->npts
-bot
->npts
;
536 topd_left
= top
->npts
-2 - u
;
537 topd_right
= 1+delta
-u
;
539 if(topd_left
< top
->npts
-2)
542 // backend.tmeshvert(& bot->pts[1]);
543 OPT_OUTVERT(bot
->pts
[1], backend
);
544 for(i
=topd_left
; i
<= top
->npts
-2; i
++)
546 // backend.tmeshvert(& top->pts[i]);
547 OPT_OUTVERT(top
->pts
[i
], backend
);
554 OPT_OUTVERT(bot
->pts
[bot
->npts
-2], backend
);
555 for(i
=1; i
<= topd_right
; i
++)
556 OPT_OUTVERT(top
->pts
[i
], backend
);
561 if(topd_left
<= topd_right
)
565 for(j
=botd_left
, i
=topd_left
; i
>=topd_right
; i
--,j
++)
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
);
579 static void triangulateRectCenter(int n_ulines
, REAL
* u_val
,
580 int n_vlines
, REAL
* v_val
,
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);
596 for(i=0; i<n_vlines-1; i++)
600 for(j=0; j<n_ulines; j++)
602 trimVert.param[0] = u_val[j];
603 trimVert.param[1] = v_val[i+1];
604 backend.tmeshvert(& trimVert);
606 trimVert.param[1] = v_val[i];
607 backend.tmeshvert(& trimVert);
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
)
622 REAL
* upper_val
= (REAL
*) malloc(sizeof(REAL
) * arc
->pwlArc
->npts
);
626 for(k
=0,i
=arc
->pwlArc
->npts
-1; i
>=0; i
--,k
++)
628 upper_val
[k
] = arc
->pwlArc
->pts
[i
].param
[0];
630 backend
.evalUStrip(arc
->pwlArc
->npts
, arc
->pwlArc
->pts
[0].param
[1],
636 for(k
=0,i
=0; i
<arc
->pwlArc
->npts
; i
++,k
++)
638 upper_val
[k
] = arc
->pwlArc
->pts
[i
].param
[0];
644 arc
->pwlArc
->npts
, arc
->pwlArc
->pts
[0].param
[1], upper_val
654 REAL
* left_val
= (REAL
*) malloc(sizeof(REAL
) * arc
->pwlArc
->npts
);
658 for(k
=0,i
=arc
->pwlArc
->npts
-1; i
>=0; i
--,k
++)
660 left_val
[k
] = arc
->pwlArc
->pts
[i
].param
[1];
662 backend
.evalVStrip(arc
->pwlArc
->npts
, arc
->pwlArc
->pts
[0].param
[0],
668 for(k
=0,i
=0; i
<arc
->pwlArc
->npts
; i
++,k
++)
670 left_val
[k
] = arc
->pwlArc
->pts
[i
].param
[1];
674 arc
->pwlArc
->npts
, arc
->pwlArc
->pts
[0].param
[0], left_val
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.
686 PwlArc* parc = arc->pwlArc;
687 int d1 = parc->npts-1;
690 trimVert.nuid = 0;//????
691 REAL* temp_u_val = u_val;
692 if(dir ==0) //have to reverse u_val
694 temp_u_val = (REAL*) malloc(sizeof(REAL) * n_ulines);
696 for(i=0; i<n_ulines; i++)
697 temp_u_val[i] = u_val[n_ulines-1-i];
701 if(parc->npts > n_ulines)
707 trimVert.param[0] = u_val[0];
708 trimVert.param[1] = v;
712 trimVert.param[1] = u_val[0];
713 trimVert.param[0] = v;
716 backend.tmeshvert(& trimVert);
717 for(i=d1; i< parc->npts; i++)
718 backend.tmeshvert(& parc->pts[i]);
723 else if(parc->npts < n_ulines)
725 d2 = n_ulines-parc->npts;
729 backend.tmeshvert(& parc->pts[parc->npts-1]);
730 for(i=0; i<= d2; i++)
733 trimVert.param[0] = u_val[i];
734 trimVert.param[1] = v;
738 trimVert.param[1] = u_val[i];
739 trimVert.param[0] = v;
741 backend.tmeshvert(&trimVert);
750 for(i=d1, j=d2; i>=0; i--, j++)
752 backend.tmeshvert(& parc->pts[i]);
755 trimVert.param[0] = u_val[j];
756 trimVert.param[1] = v;
759 trimVert.param[1] = u_val[j];
760 trimVert.param[0] = v;
762 backend.tmeshvert(&trimVert);
771 if(dir == 0) //temp_u_val was mallocated
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
)
782 //we know the loop is a rectangle, but not sure which is top
783 Arc_ptr top
, bot
, left
, right
;
785 if(equalRect(loop
->tail()[1] , loop
->head()[1]))
788 if(loop
->tail()[1] > loop
->prev
->prev
->tail()[1])
795 top
= loop
->prev
->prev
;
800 if(loop
->tail()[0] > loop
->prev
->prev
->tail()[0])
802 //loop is the right arc
817 #ifdef COUNT_TRIANGLES
818 num_triangles
+= loop
->pwlArc
->npts
+
822 + 2*n_ulines
+ 2*n_vlines
824 num_quads
+= (n_ulines
-1)*(n_vlines
-1);
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);
833 REAL
* u_val
=(REAL
*) malloc(sizeof(REAL
)*n_ulines
);
835 REAL
* v_val
=(REAL
*)malloc(sizeof(REAL
) * n_vlines
);
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
++)
845 temp
= bot
->tail()[1] + v_stepsize
;
846 for(i
=0; i
<n_vlines
; i
++)
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
);
860 //triangulate the center
861 triangulateRectCenter(n_ulines
, u_val
, n_vlines
, v_val
, backend
);
871 /**********for reading newtess_flag from a file**********/
873 static Int
read_flag(char* name
)
876 FILE* fp
= fopen(name
, "r");
879 fprintf(stderr
, "can't open file %s\n", name
);
882 fscanf(fp
, "%i", &ret
);
888 /***********nextgen tess****************/
889 #include "sampleMonoPoly.h"
890 directedLine
* arcToDLine(Arc_ptr arc
)
895 sampledLine
* sline
= new sampledLine(arc
->pwlArc
->npts
);
896 for(i
=0; i
<arc
->pwlArc
->npts
; i
++)
898 vert
[0] = arc
->pwlArc
->pts
[i
].param
[0];
899 vert
[1] = arc
->pwlArc
->pts
[i
].param
[1];
900 sline
->setPoint(i
, vert
);
902 ret
= new directedLine(INCREASING
, sline
);
906 /*an pwlArc may not be a straight line*/
907 directedLine
* arcToMultDLines(directedLine
* original
, Arc_ptr arc
)
909 directedLine
* ret
= original
;
911 if(arc
->pwlArc
->npts
== 2 )
913 else if(area(arc
->pwlArc
->pts
[0].param
, arc
->pwlArc
->pts
[1].param
, arc
->pwlArc
->pts
[arc
->pwlArc
->npts
-1].param
) == 0.0)
918 directedLine
*dline
= arcToDLine(arc
);
927 for(Int i
=0; i
<arc
->pwlArc
->npts
-1; i
++)
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];
935 sampledLine
*sline
= new sampledLine(2, vert
);
936 directedLine
*dline
= new directedLine(INCREASING
, sline
);
948 directedLine
* arcLoopToDLineLoop(Arc_ptr loop
)
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();
965 void Slicer::evalRBArray(rectBlockArray* rbArray, gridWrap* grid)
967 TrimVertex *trimVert = (TrimVertex*)malloc(sizeof(TrimVertex));
968 trimVert -> nuid = 0;//????
970 Real* u_values = grid->get_u_values();
971 Real* v_values = grid->get_v_values();
975 for(l=0; l<rbArray->get_n_elements(); l++)
977 rectBlock* block = rbArray->get_element(l);
978 for(k=0, i=block->get_upGridLineIndex(); i>block->get_lowGridLineIndex(); i--, k++)
982 for(j=block->get_leftIndices()[k+1]; j<= block->get_rightIndices()[k+1]; j++)
984 trimVert->param[0] = u_values[j];
985 trimVert->param[1] = v_values[i];
986 backend.tmeshvert(trimVert);
988 trimVert->param[1] = v_values[i-1];
989 backend.tmeshvert(trimVert);
1001 void Slicer::evalRBArray(rectBlockArray
* rbArray
, gridWrap
* grid
)
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);
1013 for(j
=0; j
<rbArray
->get_n_elements(); j
++)
1015 rectBlock
* block
= rbArray
->get_element(j
);
1016 Int low
= block
->get_lowGridLineIndex();
1017 Int high
= block
->get_upGridLineIndex();
1019 for(k
=0, i
=high
; i
>low
; i
--, k
++)
1021 backend
.surfmesh(block
->get_leftIndices()[k
+1], n_vlines
-1-i
, block
->get_rightIndices()[k
+1]-block
->get_leftIndices()[k
+1], 1);
1027 void Slicer::evalStream(primStream
* pStream
)
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
++)
1038 //ith primitive has #vertices = lengths[i], type=types[i]
1039 switch(pStream
->get_type(i
)){
1040 case PRIMITIVE_STREAM_FAN
:
1044 for(j
=0; j
<pStream
->get_length(i
); j
++)
1046 trimVert
->param
[0] = vertices
[k
];
1047 trimVert
->param
[1] = vertices
[k
+1];
1048 backend
.tmeshvert(trimVert
);
1050 // backend.tmeshvert(vertices[k], vertices[k+1]);
1057 fprintf(stderr
, "evalStream: not implemented yet\n");
1068 void Slicer::slice_new(Arc_ptr loop
)
1071 //if(count == 78) count=1;
1072 //printf("count=%i\n", count);
1073 //if( ! (4<= count && count <=4)) return;
1078 Real uMin
, uMax
, vMin
, vMax
;
1080 uMin
= uMax
= loop
->tail()[0];
1081 vMin
= vMax
= loop
->tail()[1];
1082 mydu
= (du
>0)? du
: -du
;
1083 mydv
= (dv
>0)? dv
: -dv
;
1085 for(Arc_ptr jarc
=loop
->next
; jarc
!= loop
; jarc
= jarc
->next
)
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];
1099 return; // prevent divide-by-zero. Jon Perry. 17 June 2002
1101 if(mydu
> uMax
- uMin
)
1105 num_ulines
= 3 + (Int
) ((uMax
-uMin
)/mydu
);
1111 num_vlines
= 2+(Int
)((vMax
-vMin
)/mydv
);
1114 Int isRect
= is_rect(loop
);
1116 if(isRect
&& (num_ulines
<=2 || num_vlines
<=2))
1119 triangulateRect(loop
, backend
, 1, ulinear
, vlinear
);
1121 triangulateRect(loop
, backend
, -1, ulinear
, vlinear
);
1123 triangulateRect(loop
, backend
, 0, ulinear
, vlinear
);
1128 triangulateRectGen(loop
, num_ulines
-2, num_vlines
-2, backend
);
1130 else if( (num_ulines
<=2 || num_vlines
<=2) && ulinear
)
1132 monoTriangulationFunBackend(loop
, compV2InY
, &backend
);
1134 else if( (!ulinear
) && (!vlinear
) && (num_ulines
== 2) && (num_vlines
> 2))
1136 monoTriangulationFunBackend(loop
, compV2InY
, &backend
);
1140 directedLine
* poly
= arcLoopToDLineLoop(loop
);
1142 gridWrap
grid(num_ulines
, num_vlines
, uMin
, uMax
, vMin
, vMax
);
1143 primStream
pStream(20, 20);
1144 rectBlockArray
rbArray(20);
1146 sampleMonoPoly(poly
, &grid
, ulinear
, vlinear
, &pStream
, &rbArray
);
1148 evalStream(&pStream
);
1150 evalRBArray(&rbArray
, &grid
);
1152 #ifdef COUNT_TRIANGLES
1153 num_triangles
+= pStream
.num_triangles();
1154 num_quads
+= rbArray
.num_quads();
1156 poly
->deleteSinglePolygonWithSline();
1159 #ifdef COUNT_TRIANGLES
1160 printf("num_triangles=%i\n", num_triangles
);
1161 printf("num_quads = %i\n", num_quads
);
1165 void Slicer::slice(Arc_ptr loop
)
1167 #ifdef USE_READ_FLAG
1168 if(read_flag("flagFile"))
1181 Slicer::Slicer( Backend
&b
)
1182 : CoveAndTiler( b
), Mesher( b
), backend( b
)
1197 Slicer::setisolines( int x
)
1203 Slicer::setstriptessellation( REAL x
, REAL y
)
1205 assert(x
> 0 && y
> 0);
1212 Slicer::slice_old( Arc_ptr loop
)
1217 loop
->getextrema( extrema
);
1219 unsigned int npts
= loop
->numpts();
1220 TrimRegion::init( npts
, extrema
[0] );
1222 Mesher::init( npts
);
1224 long ulines
= uarray
.init( du
, extrema
[1], extrema
[3] );
1225 //printf("ulines = %i\n", ulines);
1227 long vlines
= varray
.init( dv
, extrema
[0], extrema
[2] );
1228 //printf("vlines = %i\n", vlines);
1231 TrimRegion::init( varray
.varray
[botv
] );
1232 getGridExtent( &extrema
[0]->pwlArc
->pts
[0], &extrema
[0]->pwlArc
->pts
[0] );
1234 for( long quad
=0; quad
<varray
.numquads
; quad
++ ) {
1235 backend
.surfgrid( uarray
.uarray
[0],
1236 uarray
.uarray
[ulines
-1],
1239 varray
.vval
[quad
+1],
1240 varray
.voffset
[quad
+1] - varray
.voffset
[quad
] );
1242 for( long i
=varray
.voffset
[quad
]+1; i
<= varray
.voffset
[quad
+1]; i
++ ) {
1244 advance( topv
- varray
.voffset
[quad
],
1245 botv
- varray
.voffset
[quad
],
1246 varray
.varray
[botv
] );
1248 getPts( extrema
[2] );
1266 Slicer::outline( void )
1268 GridTrimVertex upper
, lower
;
1271 backend
.bgnoutline();
1272 while( (nextupper( &upper
)) ) {
1273 if( upper
.isGridVert() )
1274 backend
.linevert( upper
.g
);
1276 backend
.linevert( upper
.t
);
1278 backend
.endoutline();
1280 backend
.bgnoutline();
1281 while( (nextlower( &lower
)) ) {
1282 if( lower
.isGridVert() )
1283 backend
.linevert( lower
.g
);
1285 backend
.linevert( lower
.t
);
1287 backend
.endoutline();
1292 Slicer::outline( Arc_ptr jarc
)
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();