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*/
37
38#include "gluos.h"
39#include <stdlib.h>
40#include <stdio.h>
41#include <assert.h>
42#include <GL/gl.h>
43#include "bezierEval.h"
44#include "bezierPatchMesh.h"
45
46static int isDegenerate(float A[2], float B[2], float C[2]);
47
48void drawStrips(float *vertex_array, float *normal_array, int *length_array, GLenum *type_array, int num_strips)
49{
50  int i,j,k;
51  k=0;
52  /*k is the index of the first component of the current vertex*/
53  for(i=0; i<num_strips; i++)
54    {
55      glBegin(type_array[i]);
56      for(j=0; j<length_array[i]; j++)
57	{
58	  glNormal3fv(normal_array+k);
59	  glVertex3fv(vertex_array+k);
60	  k += 3;
61	}
62      glEnd();
63    }
64}
65
66void bezierPatchMeshListDelDeg(bezierPatchMesh* list)
67{
68  bezierPatchMesh* temp;
69  for(temp=list; temp != NULL; temp = temp->next)
70    {
71      bezierPatchMeshDelDeg(temp);
72    }
73}
74
75void bezierPatchMeshListDelete(bezierPatchMesh *list)
76{
77  if(list == NULL) return;
78  bezierPatchMeshListDelete(list->next);
79  bezierPatchMeshDelete(list);
80}
81
82
83
84
85bezierPatchMesh* bezierPatchMeshListReverse(bezierPatchMesh* list)
86{
87 bezierPatchMesh* ret=NULL;
88 bezierPatchMesh* temp;
89 bezierPatchMesh* nextone;
90  for(temp = list; temp != NULL; temp = nextone)
91    {
92      nextone = temp->next;
93      ret=bezierPatchMeshListInsert(ret, temp);
94    }
95 return ret;
96}
97
98/*maptype is either GL_MAP2_VERTEX_3 or GL_MAP2_VERTEX_4
99 */
100bezierPatchMesh *bezierPatchMeshMake(int maptype, float umin, float umax, int ustride, int uorder, float vmin, float vmax, int vstride, int vorder, float *ctlpoints,  int size_UVarray, int size_length_array)
101{
102  int i,j,k;
103  int dimension;
104  int the_ustride;
105  int the_vstride;
106
107  if(maptype == GL_MAP2_VERTEX_3) dimension = 3;
108  else if (maptype==GL_MAP2_VERTEX_4) dimension = 4;
109  else {
110    fprintf(stderr, "error in inMap2f, maptype=%i is wrong, maptype,map is invalid\n", maptype);
111    return NULL;
112  }
113
114  bezierPatchMesh *ret = (bezierPatchMesh*) malloc(sizeof(bezierPatchMesh));
115  assert(ret);
116
117  ret->bpatch_normal = NULL;
118  ret->bpatch_color  = NULL;
119  ret->bpatch_texcoord = NULL;
120  ret->bpatch = bezierPatchMake(umin, vmin, umax, vmax, uorder, vorder, dimension);
121
122  /*copy the control points there*/
123  the_ustride = vorder * dimension;
124  the_vstride = dimension;
125  for(i=0; i<uorder; i++)
126    for(j=0; j<vorder; j++)
127      for(k=0; k<dimension; k++)
128	ret->bpatch->ctlpoints[i * the_ustride + j*the_vstride+k] = ctlpoints[i*ustride+j*vstride+k];
129
130
131  ret->size_UVarray = size_UVarray;
132  ret->size_length_array = size_length_array;
133  ret->UVarray = (float*) malloc(sizeof(float) * size_UVarray);
134  assert(ret->UVarray);
135  ret->length_array = (int *)malloc(sizeof(int) * size_length_array);
136  assert(ret->length_array);
137  ret->type_array = (GLenum *)malloc(sizeof(GLenum) * size_length_array);
138  assert(ret->type_array);
139
140  ret->index_UVarray = 0;
141  ret->index_length_array = 0;
142
143  ret->vertex_array = NULL;
144  ret->normal_array = NULL;
145  ret->color_array  = NULL;
146  ret->texcoord_array = NULL;
147
148  ret->next = NULL;
149  return ret;
150}
151
152bezierPatchMesh *bezierPatchMeshMake2(int size_UVarray, int size_length_array)
153{
154  bezierPatchMesh *ret = (bezierPatchMesh*) malloc(sizeof(bezierPatchMesh));
155  assert(ret);
156
157  ret->bpatch = NULL;
158  ret->bpatch_normal = NULL;
159  ret->bpatch_color  = NULL;
160  ret->bpatch_texcoord = NULL;
161
162  ret->size_UVarray = size_UVarray;
163  ret->size_length_array = size_length_array;
164  ret->UVarray = (float*) malloc(sizeof(float) * size_UVarray);
165  assert(ret->UVarray);
166  ret->length_array = (int *)malloc(sizeof(int) * size_length_array);
167  assert(ret->length_array);
168  ret->type_array = (GLenum *)malloc(sizeof(GLenum) * size_length_array);
169  assert(ret->type_array);
170
171  ret->index_UVarray = 0;
172  ret->index_length_array = 0;
173
174  ret->vertex_array = NULL;
175  ret->normal_array = NULL;
176  ret->color_array  = NULL;
177  ret->texcoord_array = NULL;
178
179  ret->next = NULL;
180  return ret;
181}
182
183void bezierPatchMeshPutPatch(bezierPatchMesh *bpm, int maptype, float umin, float umax, int ustride, int uorder, float vmin, float vmax, int vstride, int vorder, float *ctlpoints)
184{
185  switch(maptype){
186  case GL_MAP2_VERTEX_3:
187    bpm->bpatch = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 3, ustride, vstride, ctlpoints);
188    break;
189  case GL_MAP2_VERTEX_4:
190    bpm->bpatch = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 4,ustride, vstride, ctlpoints );
191    break;
192  case GL_MAP2_NORMAL:
193    bpm->bpatch_normal = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 3, ustride, vstride, ctlpoints);
194    break;
195  case GL_MAP2_INDEX:
196    bpm->bpatch_color = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 1, ustride, vstride, ctlpoints);
197    break;
198  case GL_MAP2_COLOR_4:
199    bpm->bpatch_color = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 4, ustride, vstride, ctlpoints);
200    break;
201  case GL_MAP2_TEXTURE_COORD_1:
202    bpm->bpatch_texcoord = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 1, ustride, vstride, ctlpoints);
203    break;
204  case GL_MAP2_TEXTURE_COORD_2:
205    bpm->bpatch_texcoord = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 2, ustride, vstride, ctlpoints);
206    break;
207  case GL_MAP2_TEXTURE_COORD_3:
208    bpm->bpatch_texcoord = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 3, ustride, vstride, ctlpoints);
209    break;
210  case GL_MAP2_TEXTURE_COORD_4:
211    bpm->bpatch_texcoord = bezierPatchMake2(umin, vmin, umax, vmax, uorder, vorder, 4, ustride, vstride, ctlpoints);
212    break;
213  default:
214    fprintf(stderr, "error in bezierPatchMeshPutPatch, maptype=%i is wrong, maptype,map is invalid\n", maptype);
215  }
216}
217
218
219/*delete everything including the arrays. So if you want to output the
220 *pointers of the arrays, you should not use this function to deallocate space.
221 *you should dealocate manually
222 */
223void bezierPatchMeshDelete(bezierPatchMesh *bpm)
224{
225  if(bpm->bpatch != NULL)
226    bezierPatchDelete(bpm->bpatch);
227  if(bpm->bpatch_normal != NULL)
228    bezierPatchDelete(bpm->bpatch_normal);
229  if(bpm->bpatch_color != NULL)
230    bezierPatchDelete(bpm->bpatch_color);
231  if(bpm->bpatch_texcoord != NULL)
232    bezierPatchDelete(bpm->bpatch_texcoord);
233
234  free(bpm->UVarray);
235  free(bpm->length_array);
236  free(bpm->vertex_array);
237  free(bpm->normal_array);
238  free(bpm->type_array);
239  free(bpm);
240}
241
242/*begin a strip
243 *type is the primitive type:
244 */
245void bezierPatchMeshBeginStrip(bezierPatchMesh *bpm, GLenum type)
246{
247  bpm->counter = 0;
248  bpm->type = type;
249}
250
251/*signal the end of the current strip*/
252void bezierPatchMeshEndStrip(bezierPatchMesh *bpm)
253{
254  int i;
255
256  /*if there are no vertices in this strip, then nothing needs to be done*/
257  if(bpm->counter == 0) return;
258
259  /*if the length_array is full, it should be expanded*/
260  if(bpm->index_length_array >= bpm->size_length_array)
261    {
262      int *temp = (int*) malloc(sizeof(int) * (bpm->size_length_array*2 + 1));
263      assert(temp);
264      GLenum *temp_type = (GLenum*) malloc(sizeof(GLenum) * (bpm->size_length_array*2 + 1));
265      assert(temp_type);
266      /*update the size*/
267      bpm->size_length_array = bpm->size_length_array*2 + 1;
268
269      /*copy*/
270      for(i=0; i<bpm->index_length_array; i++)
271	{
272	  temp[i] = bpm->length_array[i];
273	  temp_type[i] = bpm->type_array[i];
274	}
275
276      /*deallocate old array*/
277      free(bpm->length_array);
278      free(bpm->type_array);
279
280      /*point to the new array which is twice as bigger*/
281      bpm->length_array = temp;
282      bpm->type_array = temp_type;
283    }
284  bpm->type_array[bpm->index_length_array] = bpm->type;
285  bpm->length_array[bpm->index_length_array++] = bpm->counter;
286
287}
288
289/*insert (u,v) */
290void bezierPatchMeshInsertUV(bezierPatchMesh *bpm, float u, float v)
291{
292  int i;
293  /*if the UVarray is full, it should be expanded*/
294  if(bpm->index_UVarray+1 >= bpm->size_UVarray)
295    {
296      float *temp = (float*) malloc(sizeof(float) * (bpm->size_UVarray * 2 + 2));
297      assert(temp);
298
299      /*update the size*/
300      bpm->size_UVarray = bpm->size_UVarray*2 + 2;
301
302      /*copy*/
303      for(i=0; i<bpm->index_UVarray; i++)
304	{
305	  temp[i] = bpm->UVarray[i];
306	}
307
308      /*deallocate old array*/
309      free(bpm->UVarray);
310
311      /*pointing to the new arrays*/
312      bpm->UVarray = temp;
313    }
314  /*insert the new UV*/
315  bpm->UVarray[bpm->index_UVarray] = u;
316  bpm->index_UVarray++;
317  bpm->UVarray[bpm->index_UVarray] = v;
318  bpm->index_UVarray++;
319
320  /*update counter: one more vertex*/
321  bpm->counter++;
322
323
324}
325
326void bezierPatchMeshPrint(bezierPatchMesh *bpm)
327{
328  int i;
329  printf("the bezier patch is\n");
330  bezierPatchPrint(bpm->bpatch);
331  printf("index_length_array= %i\n", bpm->index_length_array);
332  printf("size_length_array =%i\n", bpm->size_length_array);
333  printf("index_UVarray =%i\n", bpm->index_UVarray);
334  printf("size_UVarray =%i\n", bpm->size_UVarray);
335  printf("UVarray is\n");
336  for(i=0; i<bpm->index_UVarray; i++)
337    printf("%f ", bpm->UVarray[i]);
338
339  printf("length_array is\n");
340  for(i=0; i<bpm->index_length_array; i++)
341    printf("%i ", bpm->length_array[i]);
342  printf("\n");
343
344}
345
346/*insert a new patch in front of the current linked list and return the new list*/
347bezierPatchMesh* bezierPatchMeshListInsert(bezierPatchMesh* list, bezierPatchMesh* bpm)
348{
349  bpm->next=list;
350  return bpm;
351}
352
353/*print all the patches*/
354void bezierPatchMeshListPrint(bezierPatchMesh* list)
355{
356  bezierPatchMesh *temp;
357  for(temp = list; temp != NULL; temp = temp->next)
358    {
359      bezierPatchMeshPrint(temp);
360    }
361}
362
363int bezierPatchMeshListTotalStrips(bezierPatchMesh* list)
364{
365  int sum=0;
366  bezierPatchMesh *temp;
367  for(temp=list; temp != NULL; temp = temp->next)
368    {
369      sum += temp->index_length_array;
370    }
371  return sum;
372}
373
374int bezierPatchMeshListTotalVert(bezierPatchMesh* list)
375{
376  int sum=0;
377  bezierPatchMesh *temp;
378  for(temp=list; temp != NULL; temp = temp->next)
379    {
380      sum += temp->index_UVarray;
381    }
382  return sum/2;
383}
384
385int bezierPatchMeshListNumTriangles(bezierPatchMesh* list)
386{
387  int sum=0;
388  bezierPatchMesh* temp;
389  for(temp=list; temp != NULL; temp = temp->next)
390    {
391      sum +=  bezierPatchMeshNumTriangles(temp);
392    }
393  return sum;
394}
395
396int bezierPatchMeshNumTriangles(bezierPatchMesh* bpm)
397{
398  int i;
399  int sum=0;
400  for(i=0; i<bpm->index_length_array; i++)
401    {
402      switch(bpm->type_array[i])
403	{
404	case GL_TRIANGLES:
405	  sum += bpm->length_array[i]/3;
406	  break;
407	case GL_TRIANGLE_FAN:
408	  if(bpm->length_array[i] > 2)
409	    sum += bpm->length_array[i]-2;
410	  break;
411	case GL_TRIANGLE_STRIP:
412	  if(bpm->length_array[i] > 2)
413	    sum += bpm->length_array[i]-2;
414	  break;
415	case GL_QUAD_STRIP:
416	  if(bpm->length_array[i]>2)
417	    sum += (bpm->length_array[i]-2);
418	  break;
419	default:
420	  fprintf(stderr,"error in bezierPatchMeshListNumTriangles, type invalid\n");
421	}
422    }
423  return sum;
424}
425
426/*delete degenerate triangles*/
427void bezierPatchMeshDelDeg(bezierPatchMesh* bpm)
428{
429  if(bpm == NULL) return;
430  int i,j,k;
431  int *new_length_array;
432  GLenum *new_type_array;
433  int index_new_length_array;
434  float *new_UVarray;
435  int index_new_UVarray;
436
437  new_length_array = (int*)malloc(sizeof(int) * bpm->index_length_array);
438  assert(new_length_array);
439  new_type_array = (GLenum*)malloc(sizeof(GLenum) * bpm->index_length_array);
440  assert(new_length_array);
441  new_UVarray = (float*) malloc(sizeof(float) * bpm->index_UVarray);
442  assert(new_UVarray);
443
444  index_new_length_array = 0;
445  index_new_UVarray=0;
446  k=0;
447  for(i=0; i<bpm->index_length_array; i++){
448
449    /*(if not degenerate, we have to copy*/
450    if( (bpm->length_array[i] != 3) || (!isDegenerate(bpm->UVarray+k, bpm->UVarray+k+2, bpm->UVarray+k+4)))
451	  {
452	    for(j=0; j<2* bpm->length_array[i]; j++)
453	      new_UVarray[index_new_UVarray++] = bpm->UVarray[k++];
454
455	    new_length_array[index_new_length_array] = bpm->length_array[i];
456	    new_type_array[index_new_length_array] = bpm->type_array[i];
457	    index_new_length_array++;
458	  }
459    else
460      {
461	k += 6;
462      }
463  }
464  free(bpm->UVarray);
465  free(bpm->length_array);
466  free(bpm->type_array);
467  bpm->UVarray=new_UVarray;
468  bpm->length_array=new_length_array;
469  bpm->type_array=new_type_array;
470  bpm->index_UVarray = index_new_UVarray;
471  bpm->index_length_array = index_new_length_array;
472
473}
474
475/*(u,v) to XYZ
476 *the xyz and normals are stored in vertex_array,
477 *and normal_array. the spaces of both are allocated here
478 */
479void bezierPatchMeshEval(bezierPatchMesh* bpm)
480{
481  int i,j,k,l;
482  float u,v;
483  float u0 = bpm->bpatch->umin;
484  float u1 = bpm->bpatch->umax;
485  int uorder = bpm->bpatch->uorder;
486  float v0 = bpm->bpatch->vmin;
487  float v1 = bpm->bpatch->vmax;
488  int vorder = bpm->bpatch->vorder;
489  int dimension = bpm->bpatch->dimension;
490  int ustride = dimension * vorder;
491  int vstride = dimension;
492  float *ctlpoints = bpm->bpatch->ctlpoints;
493
494  bpm->vertex_array = (float*) malloc(sizeof(float)* (bpm->index_UVarray/2) * 3);
495  assert(bpm->vertex_array);
496  bpm->normal_array = (float*) malloc(sizeof(float)* (bpm->index_UVarray/2) * 3);
497  assert(bpm->normal_array);
498
499  k=0;
500  l=0;
501  for(i=0; i<bpm->index_length_array; i++)
502    {
503      for(j=0; j<bpm->length_array[i]; j++)
504	{
505	  u = bpm->UVarray[k];
506	  v = bpm->UVarray[k+1];
507	  bezierSurfEval(u0,u1,uorder, v0, v1, vorder, dimension, ctlpoints, ustride, vstride, u,v, bpm->vertex_array+l);
508	  bezierSurfEvalNormal(u0,u1,uorder, v0, v1, vorder, dimension, ctlpoints, ustride, vstride, u,v, bpm->normal_array+l);
509	  k += 2;
510	  l += 3;
511	}
512    }
513}
514
515void bezierPatchMeshListEval(bezierPatchMesh* list)
516{
517  bezierPatchMesh* temp;
518  for(temp = list; temp != NULL; temp = temp->next)
519    {
520      bezierPatchMeshEval(temp);
521    }
522}
523
524void bezierPatchMeshDraw(bezierPatchMesh* bpm)
525{
526  int i,j,k;
527  k=0;
528  /*k is the index of the first component of the current vertex*/
529  for(i=0; i<bpm->index_length_array; i++)
530    {
531      glBegin(bpm->type_array[i]);
532      for(j=0; j<bpm->length_array[i]; j++)
533	{
534	  glNormal3fv(bpm->normal_array+k);
535	  glVertex3fv(bpm->vertex_array+k);
536	  k+= 3;
537	}
538      glEnd();
539    }
540}
541
542void bezierPatchMeshListDraw(bezierPatchMesh* list)
543{
544  bezierPatchMesh* temp;
545  for(temp = list; temp != NULL; temp = temp->next)
546    {
547      bezierPatchMeshDraw(temp);
548    }
549}
550
551void bezierPatchMeshListCollect(bezierPatchMesh* list, float **vertex_array, float **normal_array, int **length_array, GLenum **type_array, int *num_strips)
552{
553  int i,j,k,l;
554  bezierPatchMesh *temp;
555  int total_num_vertices = bezierPatchMeshListTotalVert(list);
556  (*vertex_array) = (float *) malloc(sizeof(float) * total_num_vertices*3);
557  assert(*vertex_array);
558  (*normal_array) = (float *) malloc(sizeof(float) * total_num_vertices*3);
559  assert(*normal_array);
560
561  *num_strips = bezierPatchMeshListTotalStrips(list);
562
563  *length_array = (int*) malloc(sizeof(int) * (*num_strips));
564  assert(*length_array);
565
566  *type_array = (GLenum*) malloc(sizeof(GLenum) * (*num_strips));
567  assert(*type_array);
568
569  k=0;
570  l=0;
571  for(temp = list; temp != NULL; temp = temp->next)
572    {
573      int x=0;
574      for(i=0; i<temp->index_length_array; i++)
575	{
576	  for(j=0; j<temp->length_array[i]; j++)
577	    {
578	      (*vertex_array)[k] = temp->vertex_array[x];
579	      (*vertex_array)[k+1] = temp->vertex_array[x+1];
580	      (*vertex_array)[k+2] = temp->vertex_array[x+2];
581
582	      (*normal_array)[k] = temp->normal_array[x];
583	      (*normal_array)[k+1] = temp->normal_array[x+1];
584	      (*normal_array)[k+2] = temp->normal_array[x+2];
585
586	      x += 3;
587	      k += 3;
588	    }
589	  (*type_array)[l]  = temp->type_array[i];
590	  (*length_array)[l++] = temp->length_array[i];
591	}
592    }
593}
594
595
596
597static int isDegenerate(float A[2], float B[2], float C[2])
598{
599  if( (A[0] == B[0] && A[1]==B[1]) ||
600      (A[0] == C[0] && A[1]==C[1]) ||
601      (B[0] == C[0] && B[1]==C[1])
602     )
603    return 1;
604  else
605    return 0;
606}
607
608
609
610
611