home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / coders / mesa-1.2.8 / src-glu / nurbsutl.c < prev    next >
C/C++ Source or Header  |  1996-05-27  |  24KB  |  985 lines
  1. /* nurbsutl.c */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  1.2
  6.  * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25. $Id: nurbsutl.c,v 1.8 1996/02/20 20:48:43 brianp Exp $
  26.  
  27. $Log: nurbsutl.c,v $
  28.  * Revision 1.8  1996/02/20  20:48:43  brianp
  29.  * applied Bogdan's February 20th patches (fixes patch cracks)
  30.  *
  31.  * Revision 1.7  1996/01/26  15:32:08  brianp
  32.  * added Bogdan Sikorski's January 25th and 26th patches
  33.  *
  34.  * Revision 1.6  1995/12/12  21:33:36  brianp
  35.  * fixed a few C+ errors/warnings in castings
  36.  *
  37.  * Revision 1.5  1995/11/03  14:15:13  brianp
  38.  * Bogdan's November 3, 1995 updates
  39.  *
  40.  * Revision 1.4  1995/09/20  18:25:57  brianp
  41.  * removed Bogdan's old email address
  42.  *
  43.  * Revision 1.3  1995/08/04  13:09:59  brianp
  44.  * include gluP.h to define NULL, just in case
  45.  *
  46.  * Revision 1.2  1995/07/28  21:37:30  brianp
  47.  * updates from Bogdan on July 28
  48.  *
  49.  * Revision 1.1  1995/07/28  14:45:10  brianp
  50.  * Initial revision
  51.  *
  52.  */
  53.  
  54.  
  55. /*
  56.  * NURBS implementation written by Bogdan Sikorski (bogdan@cira.it)
  57.  * See README2 for more info.
  58.  */
  59.  
  60.  
  61. #include <math.h>
  62. #include "nurbs.h"
  63.  
  64. GLenum
  65. test_knot(GLint nknots, GLfloat *knot, GLint order)
  66. {
  67.     GLsizei i;
  68.     GLint knot_mult;
  69.     GLfloat tmp_knot;
  70.  
  71.     tmp_knot=knot[0];
  72.     knot_mult=1;
  73.     for(i=1;i<nknots;i++)
  74.     {
  75.         if(knot[i] < tmp_knot)
  76.             return GLU_NURBS_ERROR4;
  77.         if(fabs(tmp_knot-knot[i]) > EPSILON)
  78.         {
  79.             if(knot_mult>order)
  80.                 return GLU_NURBS_ERROR5;
  81.             knot_mult=1;
  82.             tmp_knot=knot[i];
  83.         }
  84.         else
  85.             ++knot_mult;
  86.     }
  87.     return GLU_NO_ERROR;
  88. }
  89.  
  90. /* qsort function */
  91. static int
  92. knot_sort(const void *a, const void *b)
  93. {
  94.     GLfloat x,y;
  95.  
  96.     x=*((GLfloat *)a);
  97.     y=*((GLfloat *)b);
  98.     if(fabs(x-y) < EPSILON)
  99.         return 0;
  100.     if(x > y)
  101.         return 1;
  102.     return -1;
  103. }
  104.  
  105. /* insert into dest knot all values within the valid range from src knot */
  106. /* that do not appear in dest */
  107. void
  108. collect_unified_knot(knot_str_type *dest, knot_str_type *src,
  109.     GLfloat maximal_min_knot, GLfloat minimal_max_knot)
  110. {
  111.     GLfloat *src_knot,*dest_knot;
  112.     GLint src_t_min,src_t_max,dest_t_min,dest_t_max;
  113.     GLint src_nknots,dest_nknots;
  114.     GLint i,j,k,new_cnt;
  115.     GLboolean    not_found_flag;
  116.  
  117.     src_knot=src->unified_knot;
  118.     dest_knot=dest->unified_knot;
  119.     src_t_min=src->t_min;
  120.     src_t_max=src->t_max;
  121.     dest_t_min=dest->t_min;
  122.     dest_t_max=dest->t_max;
  123.     src_nknots=src->unified_nknots;
  124.     dest_nknots=dest->unified_nknots;
  125.  
  126.     k=new_cnt=dest_nknots;
  127.     for(i=src_t_min;i<=src_t_max;i++)
  128.         if(src_knot[i] - maximal_min_knot > -EPSILON &&
  129.         src_knot[i] - minimal_max_knot < EPSILON)
  130.     {
  131.         not_found_flag=GL_TRUE;
  132.         for(j=dest_t_min;j<=dest_t_max;j++)
  133.             if(fabs(dest_knot[j]-src_knot[i]) < EPSILON)
  134.             {
  135.                 not_found_flag=GL_FALSE;
  136.                 break;
  137.             }
  138.         if(not_found_flag)
  139.         {
  140.             /* knot from src is not in dest - add this knot to dest */
  141.             dest_knot[k++]=src_knot[i];
  142.             ++new_cnt;
  143.             ++(dest->t_max); /* the valid range widens */
  144.             ++(dest->delta_nknots); /* increment the extra knot value counter */
  145.         }
  146.     }
  147.     dest->unified_nknots=new_cnt;
  148.     qsort((void *)dest_knot,(size_t)new_cnt,(size_t)sizeof(GLfloat),
  149.         &knot_sort);
  150. }
  151.  
  152. /* basing on the new common knot range for all attributes set */
  153. /* t_min and t_max values for each knot - they will be used later on */
  154. /* by explode_knot() and calc_new_ctrl_pts */
  155. static void
  156. set_new_t_min_t_max(knot_str_type *geom_knot, knot_str_type *color_knot,
  157.     knot_str_type *normal_knot, knot_str_type *texture_knot,
  158.     GLfloat maximal_min_knot, GLfloat minimal_max_knot)
  159. {
  160.     GLuint    t_min,t_max,cnt;
  161.  
  162.     if(minimal_max_knot-maximal_min_knot < EPSILON)
  163.     {
  164.         /* knot common range empty */
  165.         geom_knot->t_min=geom_knot->t_max=0;
  166.         color_knot->t_min=color_knot->t_max=0;
  167.         normal_knot->t_min=normal_knot->t_max=0;
  168.         texture_knot->t_min=texture_knot->t_max=0;
  169.     }
  170.     else
  171.     {
  172.         if(geom_knot->unified_knot!=NULL)
  173.         {
  174.             cnt=geom_knot->unified_nknots;
  175.             for(t_min=0;t_min<cnt;t_min++)
  176.                 if(fabs((geom_knot->unified_knot)[t_min] - maximal_min_knot) <
  177.                         EPSILON)
  178.                     break;
  179.             for(t_max=cnt-1;t_max;t_max--)
  180.                 if(fabs((geom_knot->unified_knot)[t_max] - minimal_max_knot) < 
  181.                         EPSILON)
  182.                     break;
  183.         }
  184.         else
  185.         if(geom_knot->nknots)
  186.         {
  187.             cnt=geom_knot->nknots;
  188.             for(t_min=0;t_min<cnt;t_min++)
  189.                 if(fabs((geom_knot->knot)[t_min] - maximal_min_knot) < EPSILON)
  190.                     break;
  191.             for(t_max=cnt-1;t_max;t_max--)
  192.                 if(fabs((geom_knot->knot)[t_max] - minimal_max_knot) < EPSILON)
  193.                     break;
  194.         }
  195.         geom_knot->t_min=t_min;
  196.         geom_knot->t_max=t_max;
  197.         if(color_knot->unified_knot!=NULL)
  198.         {
  199.             cnt=color_knot->unified_nknots;
  200.             for(t_min=0;t_min<cnt;t_min++)
  201.                 if(fabs((color_knot->unified_knot)[t_min] - maximal_min_knot) <
  202.                         EPSILON)
  203.                     break;
  204.             for(t_max=cnt-1;t_max;t_max--)
  205.                 if(fabs((color_knot->unified_knot)[t_max] - minimal_max_knot) < 
  206.                         EPSILON)
  207.                     break;
  208.             color_knot->t_min=t_min;
  209.             color_knot->t_max=t_max;
  210.         }
  211.         if(normal_knot->unified_knot!=NULL)
  212.         {
  213.             cnt=normal_knot->unified_nknots;
  214.             for(t_min=0;t_min<cnt;t_min++)
  215.                 if(fabs((normal_knot->unified_knot)[t_min] - maximal_min_knot) <
  216.                         EPSILON)
  217.                     break;
  218.             for(t_max=cnt-1;t_max;t_max--)
  219.                 if(fabs((normal_knot->unified_knot)[t_max] - minimal_max_knot) < 
  220.                         EPSILON)
  221.                     break;
  222.             normal_knot->t_min=t_min;
  223.             normal_knot->t_max=t_max;
  224.         }
  225.         if(texture_knot->unified_knot!=NULL)
  226.         {
  227.             cnt=texture_knot->unified_nknots;
  228.             for(t_min=0;t_min<cnt;t_min++)
  229.                 if(fabs((texture_knot->unified_knot)[t_min] - maximal_min_knot) 
  230.                         < EPSILON)
  231.                     break;
  232.             for(t_max=cnt-1;t_max;t_max--)
  233.                 if(fabs((texture_knot->unified_knot)[t_max] - minimal_max_knot) 
  234.                         < EPSILON)
  235.                     break;
  236.             texture_knot->t_min=t_min;
  237.             texture_knot->t_max=t_max;
  238.         }
  239.     }
  240. }
  241.  
  242. /* modify all knot valid ranges in such a way that all have the same */
  243. /* range, common to all knots */
  244. /* do this by knot insertion */
  245. GLenum
  246. select_knot_working_range(GLUnurbsObj *nobj,knot_str_type *geom_knot,
  247.     knot_str_type *color_knot, knot_str_type *normal_knot,
  248.     knot_str_type *texture_knot)
  249. {
  250.     GLint max_nknots;
  251.     GLfloat maximal_min_knot,minimal_max_knot;
  252.     GLint i;
  253.  
  254.     /* find the maximum modified knot length */
  255.     max_nknots=geom_knot->nknots;
  256.     if(color_knot->unified_knot)
  257.         max_nknots+=color_knot->nknots;
  258.     if(normal_knot->unified_knot)
  259.         max_nknots+=normal_knot->nknots;
  260.     if(texture_knot->unified_knot)
  261.         max_nknots+=texture_knot->nknots;
  262.     maximal_min_knot=(geom_knot->knot)[geom_knot->t_min];
  263.     minimal_max_knot=(geom_knot->knot)[geom_knot->t_max];
  264.     /* any attirb data ? */
  265.     if(max_nknots!=geom_knot->nknots)
  266.     {
  267.         /* allocate space for the unified knots */
  268.         if((geom_knot->unified_knot=
  269.                 (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  270.         {
  271.             call_user_error(nobj,GLU_OUT_OF_MEMORY);
  272.             return GLU_ERROR;
  273.         }
  274.         /* copy the original knot to the unified one */
  275.         geom_knot->unified_nknots=geom_knot->nknots;
  276.         for(i=0;i<geom_knot->nknots;i++)
  277.             (geom_knot->unified_knot)[i]=(geom_knot->knot)[i];
  278.         if(color_knot->unified_knot)
  279.         {
  280.             if((color_knot->knot)[color_knot->t_min] - maximal_min_knot >
  281.                     EPSILON)
  282.                 maximal_min_knot=(color_knot->knot)[color_knot->t_min];
  283.             if(minimal_max_knot - (color_knot->knot)[color_knot->t_max] >
  284.                     EPSILON)
  285.                 minimal_max_knot=(color_knot->knot)[color_knot->t_max];
  286.             if((color_knot->unified_knot=
  287.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  288.             {
  289.                 free(geom_knot->unified_knot);
  290.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  291.                 return GLU_ERROR;
  292.             }
  293.             /* copy the original knot to the unified one */
  294.             color_knot->unified_nknots=color_knot->nknots;
  295.             for(i=0;i<color_knot->nknots;i++)
  296.                 (color_knot->unified_knot)[i]=(color_knot->knot)[i];
  297.         }
  298.         if(normal_knot->unified_knot)
  299.         {
  300.             if((normal_knot->knot)[normal_knot->t_min] - maximal_min_knot >
  301.                     EPSILON)
  302.                 maximal_min_knot=(normal_knot->knot)[normal_knot->t_min];
  303.             if(minimal_max_knot - (normal_knot->knot)[normal_knot->t_max] >
  304.                     EPSILON)
  305.                 minimal_max_knot=(normal_knot->knot)[normal_knot->t_max];
  306.             if((normal_knot->unified_knot=
  307.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  308.             {
  309.                 free(geom_knot->unified_knot);
  310.                 free(color_knot->unified_knot);
  311.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  312.                 return GLU_ERROR;
  313.             }
  314.             /* copy the original knot to the unified one */
  315.             normal_knot->unified_nknots=normal_knot->nknots;
  316.             for(i=0;i<normal_knot->nknots;i++)
  317.                 (normal_knot->unified_knot)[i]=(normal_knot->knot)[i];
  318.         }
  319.         if(texture_knot->unified_knot)
  320.         {
  321.             if((texture_knot->knot)[texture_knot->t_min] - maximal_min_knot >
  322.                     EPSILON)
  323.                 maximal_min_knot=(texture_knot->knot)[texture_knot->t_min];
  324.             if(minimal_max_knot - (texture_knot->knot)[texture_knot->t_max] >
  325.                     EPSILON)
  326.                 minimal_max_knot=(texture_knot->knot)[texture_knot->t_max];
  327.             if((texture_knot->unified_knot=
  328.                     (GLfloat *)malloc(sizeof(GLfloat)*max_nknots))==NULL)
  329.             {
  330.                 free(geom_knot->unified_knot);
  331.                 free(color_knot->unified_knot);
  332.                 free(normal_knot->unified_knot);
  333.                 call_user_error(nobj,GLU_OUT_OF_MEMORY);
  334.                 return GLU_ERROR;
  335.             }
  336.             /* copy the original knot to the unified one */
  337.             texture_knot->unified_nknots=texture_knot->nknots;
  338.             for(i=0;i<texture_knot->nknots;i++)
  339.                 (texture_knot->unified_knot)[i]=(texture_knot->knot)[i];
  340.         }
  341.         /* work on the geometry knot with all additional knot values */
  342.         /* appearing in attirbutive knots */
  343.         if(minimal_max_knot-maximal_min_knot < EPSILON)
  344.         {
  345.             /* empty working range */
  346.             geom_knot->unified_nknots=0;
  347.             color_knot->unified_nknots=0;
  348.             normal_knot->unified_nknots=0;
  349.             texture_knot->unified_nknots=0;
  350.         }
  351.         else
  352.         {
  353.             if(color_knot->unified_knot)
  354.                 collect_unified_knot(geom_knot,color_knot,maximal_min_knot,
  355.                     minimal_max_knot);
  356.             if(normal_knot->unified_knot)
  357.                 collect_unified_knot(geom_knot,normal_knot,maximal_min_knot,
  358.                     minimal_max_knot);
  359.             if(texture_knot->unified_knot)
  360.                 collect_unified_knot(geom_knot,texture_knot,maximal_min_knot,
  361.                     minimal_max_knot);
  362.             /* since we have now built the "unified" geometry knot */
  363.             /* add same knot values to all attributive knots */
  364.             if(color_knot->unified_knot)
  365.                 collect_unified_knot(color_knot,geom_knot,maximal_min_knot,
  366.                     minimal_max_knot);
  367.             if(normal_knot->unified_knot)
  368.                 collect_unified_knot(normal_knot,geom_knot,maximal_min_knot,
  369.                     minimal_max_knot);
  370.             if(texture_knot->unified_knot)
  371.                 collect_unified_knot(texture_knot,geom_knot,maximal_min_knot,
  372.                     minimal_max_knot);
  373.         }
  374.     }
  375.     set_new_t_min_t_max(geom_knot,color_knot,normal_knot,texture_knot,
  376.         maximal_min_knot,minimal_max_knot);
  377.     return GLU_NO_ERROR;
  378. }
  379.  
  380. void
  381. free_unified_knots(knot_str_type *geom_knot, knot_str_type *color_knot,
  382.     knot_str_type *normal_knot, knot_str_type *texture_knot)
  383. {
  384.     if(geom_knot->unified_knot)
  385.         free(geom_knot->unified_knot);
  386.     if(color_knot->unified_knot)
  387.         free(color_knot->unified_knot);
  388.     if(normal_knot->unified_knot)
  389.         free(normal_knot->unified_knot);
  390.     if(texture_knot->unified_knot)
  391.         free(texture_knot->unified_knot);
  392. }
  393.  
  394. GLenum
  395. explode_knot(knot_str_type *the_knot)
  396. {
  397.     GLfloat *knot,*new_knot;
  398.     GLint nknots,n_new_knots=0;
  399.     GLint t_min,t_max;
  400.     GLint ord;
  401.     GLsizei i,j,k;
  402.     GLfloat tmp_float;
  403.  
  404.     if(the_knot->unified_knot)
  405.     {
  406.         knot=the_knot->unified_knot;
  407.         nknots=the_knot->unified_nknots;
  408.     }
  409.     else
  410.     {
  411.         knot=the_knot->knot;
  412.         nknots=the_knot->nknots;
  413.     }
  414.     ord=the_knot->order;
  415.     t_min=the_knot->t_min;
  416.     t_max=the_knot->t_max;
  417.  
  418.     for(i=t_min;i<=t_max;)
  419.     {
  420.         tmp_float=knot[i];
  421.         for(j=0;j<ord && (i+j)<=t_max;j++)
  422.             if(fabs(tmp_float-knot[i+j])>EPSILON)
  423.                 break;
  424.         n_new_knots+=ord-j;
  425.         i+=j;
  426.     }
  427.     /* alloc space for new_knot */
  428.     if((new_knot=(GLfloat *)malloc(sizeof(GLfloat)*(nknots+n_new_knots)))==NULL)
  429.     {
  430.         return GLU_OUT_OF_MEMORY;
  431.     }
  432.     /* fill in new knot */
  433.     for(j=0;j<t_min;j++)
  434.         new_knot[j]=knot[j];
  435.     for(i=j;i<=t_max;i++)
  436.     {
  437.         tmp_float=knot[i];
  438.         for(k=0;k<ord;k++)
  439.         {
  440.             new_knot[j++]=knot[i];
  441.             if(tmp_float==knot[i+1])
  442.                 i++;
  443.         }
  444.     }
  445.     for(i=t_max+1;i<(int)nknots;i++)
  446.         new_knot[j++]=knot[i];
  447.     /* fill in the knot structure */
  448.     the_knot->new_knot=new_knot;
  449.     the_knot->delta_nknots+=n_new_knots;
  450.     the_knot->t_max+=n_new_knots;
  451.     return GLU_NO_ERROR;
  452. }
  453.  
  454. GLenum
  455. calc_alphas(knot_str_type *the_knot)
  456. {
  457.     GLfloat tmp_float;
  458.     int i,j,k,m,n;
  459.     int order;
  460.     GLfloat *alpha,*alpha_new,*tmp_alpha;
  461.     GLfloat denom;
  462.     GLfloat *knot,*new_knot;
  463.  
  464.  
  465.     knot=the_knot->knot;
  466.     order=the_knot->order;
  467.     new_knot=the_knot->new_knot;
  468.     n=the_knot->nknots-the_knot->order;
  469.     m=n+the_knot->delta_nknots;
  470.     if((alpha=(GLfloat *)malloc(sizeof(GLfloat)*n*m))==NULL)
  471.     {
  472.         return GLU_OUT_OF_MEMORY;
  473.     }
  474.     if((alpha_new=(GLfloat *)malloc(sizeof(GLfloat)*n*m))==NULL)
  475.     {
  476.         free(alpha);
  477.         return GLU_OUT_OF_MEMORY;
  478.     }
  479.     for(j=0;j<m;j++)
  480.     {
  481.         for(i=0;i<n;i++)
  482.         {
  483.             if((knot[i] <= new_knot[j]) && (new_knot[j] < knot[i+1]))
  484.                 tmp_float=1.0;
  485.             else
  486.                 tmp_float=0.0;
  487.             alpha[i+j*n]=tmp_float;
  488.         }
  489.     }
  490.     for(k=1;k<order;k++)
  491.     {
  492.         for(j=0;j<m;j++)
  493.             for(i=0;i<n;i++)
  494.             {
  495.                 denom=knot[i+k]-knot[i];
  496.                 if(fabs(denom)<EPSILON)
  497.                     tmp_float=0.0;
  498.                 else
  499.                     tmp_float=(new_knot[j+k]-knot[i])/denom*
  500.                         alpha[i+j*n];
  501.                 denom=knot[i+k+1]-knot[i+1];
  502.                 if(fabs(denom)>EPSILON)
  503.                     tmp_float+=(knot[i+k+1]-new_knot[j+k])/denom*
  504.                         alpha[(i+1)+j*n];
  505.                 alpha_new[i+j*n]=tmp_float;
  506.             }
  507.         tmp_alpha=alpha_new;
  508.         alpha_new=alpha;
  509.         alpha=tmp_alpha;
  510.     }
  511.     the_knot->alpha=alpha;
  512.     free(alpha_new);
  513.     return GLU_NO_ERROR;
  514. }
  515.  
  516. GLenum
  517. calc_new_ctrl_pts(GLfloat *ctrl,GLint stride,knot_str_type *the_knot,
  518.     GLint dim,GLfloat **new_ctrl,GLint *ncontrol)
  519. {
  520.     GLsizei i,j,k,l,m,n;
  521.     GLsizei index1,index2;
  522.     GLfloat *alpha;
  523.     GLfloat *new_knot;
  524.  
  525.     new_knot=the_knot->new_knot;
  526.     n=the_knot->nknots-the_knot->order;
  527.     alpha=the_knot->alpha;
  528.  
  529.     m=the_knot->t_max+1-the_knot->t_min-the_knot->order;
  530.     k=the_knot->t_min;
  531.     /* allocate space for new control points */
  532.     if((*new_ctrl=(GLfloat *)malloc(sizeof(GLfloat)*dim*m))==NULL)
  533.     {
  534.         return GLU_OUT_OF_MEMORY;
  535.     }
  536.     for(j=0;j<m;j++)
  537.     {
  538.         for(l=0;l<dim;l++)
  539.             (*new_ctrl)[j*dim+l]=0.0;
  540.         for(i=0;i<n;i++)
  541.         {
  542.             index1=i+(j+k)*n;
  543.             index2=i*stride;
  544.             for(l=0;l<dim;l++)
  545.                 (*new_ctrl)[j*dim+l]+=alpha[index1]*ctrl[index2+l];
  546.         }
  547.     }
  548.     *ncontrol=(GLint)m;
  549.     return GLU_NO_ERROR;
  550. }
  551.  
  552. static GLint
  553. calc_factor(GLfloat *pts,GLint order,GLint indx,GLint stride,GLfloat tolerance,
  554.     GLint dim)
  555. {
  556.     GLdouble model[16],proj[16];
  557.     GLint viewport[4];
  558.     GLdouble x,y,z,w,winx1,winy1,winz,winx2,winy2;
  559.     GLint i;
  560.     GLdouble len,dx,dy;
  561.  
  562.     glGetDoublev(GL_MODELVIEW_MATRIX,model);
  563.     glGetDoublev(GL_PROJECTION_MATRIX,proj);
  564.     glGetIntegerv(GL_VIEWPORT,viewport);
  565.     if(dim==4)
  566.     {
  567.         w=(GLdouble)pts[indx+3];
  568.         x=(GLdouble)pts[indx]/w;
  569.         y=(GLdouble)pts[indx+1]/w;
  570.         z=(GLdouble)pts[indx+2]/w;
  571.         gluProject(x,y,z,model,proj,viewport,&winx1,&winy1,&winz);
  572.         len=0.0;
  573.         for(i=1;i<order;i++)
  574.         {
  575.             w=(GLdouble)pts[indx+i*stride+3];
  576.             x=(GLdouble)pts[indx+i*stride]/w;
  577.             y=(GLdouble)pts[indx+i*stride+1]/w;
  578.             z=(GLdouble)pts[indx+i*stride+2]/w;
  579.             if(gluProject(x,y,z,model,proj,viewport,&winx2,&winy2,&winz))
  580.             {
  581.                 dx=winx2-winx1;
  582.                 dy=winy2-winy1;
  583.                 len+=sqrt(dx*dx+dy*dy);
  584.             }
  585.             winx1=winx2; winy1=winy2;
  586.         }
  587.     }
  588.     else
  589.     {
  590.         x=(GLdouble)pts[indx];
  591.         y=(GLdouble)pts[indx+1];
  592.         if(dim==2)
  593.             z=0.0;
  594.         else
  595.             z=(GLdouble)pts[indx+2];
  596.         gluProject(x,y,z,model,proj,viewport,&winx1,&winy1,&winz);
  597.         len=0.0;
  598.         for(i=1;i<order;i++)
  599.         {
  600.             x=(GLdouble)pts[indx+i*stride];
  601.             y=(GLdouble)pts[indx+i*stride+1];
  602.             if(dim==2)
  603.                 z=0.0;
  604.             else
  605.                 z=(GLdouble)pts[indx+i*stride+2];
  606.             if(gluProject(x,y,z,model,proj,viewport,&winx2,&winy2,&winz))
  607.             {
  608.                 dx=winx2-winx1;
  609.                 dy=winy2-winy1;
  610.                 len+=sqrt(dx*dx+dy*dy);
  611.             }
  612.             winx1=winx2; winy1=winy2;
  613.         }
  614.     }
  615.     len /= tolerance;
  616.     return ((GLint)len+1);
  617. }
  618.  
  619. static GLenum
  620. calc_sampling_3D(new_ctrl_type *new_ctrl, GLfloat tolerance, GLint dim,
  621.     GLint uorder, GLint vorder, GLint **ufactors, GLint **vfactors)
  622. {
  623.     GLfloat        *ctrl;
  624.     GLint        tmp_factor1,tmp_factor2;
  625.     GLint        ufactor_cnt,vfactor_cnt;
  626.     GLint        offset1,offset2,offset3;
  627.     GLint        i,j;
  628.  
  629.     ufactor_cnt=new_ctrl->s_bezier_cnt;
  630.     vfactor_cnt=new_ctrl->t_bezier_cnt;
  631.     if((*ufactors=(GLint *)malloc(sizeof(GLint)*ufactor_cnt*3))
  632.             ==NULL)
  633.     {
  634.         return GLU_OUT_OF_MEMORY;
  635.     }
  636.     if((*vfactors=(GLint *)malloc(sizeof(GLint)*vfactor_cnt*3))
  637.             ==NULL)
  638.     {
  639.         free(ufactors);
  640.         return GLU_OUT_OF_MEMORY;
  641.     }
  642.     ctrl=new_ctrl->geom_ctrl;
  643.     offset1=new_ctrl->geom_t_stride*vorder;
  644.     offset2=new_ctrl->geom_s_stride*uorder;
  645.     for(j=0;j<vfactor_cnt;j++)
  646.     {
  647.         *(*vfactors+j*3+1)=tmp_factor1=calc_factor(ctrl,vorder,
  648.             j*offset1,dim,tolerance,dim);
  649.         /* loop ufactor_cnt-1 times */
  650.         for(i=1;i<ufactor_cnt;i++)
  651.         {
  652.             tmp_factor2=calc_factor(ctrl,vorder,
  653.                 j*offset1+i*offset2,dim,tolerance,dim);
  654.             if(tmp_factor2>tmp_factor1)
  655.                 tmp_factor1=tmp_factor2;
  656.         }
  657.         /* last time for the opposite edge */
  658.         *(*vfactors+j*3+2)=tmp_factor2=calc_factor(ctrl,vorder,
  659.             j*offset1+i*offset2-new_ctrl->geom_s_stride,
  660.             dim,tolerance,dim);
  661.         if(tmp_factor2>tmp_factor1)
  662.             *(*vfactors+j*3)=tmp_factor2;
  663.         else
  664.             *(*vfactors+j*3)=tmp_factor1;
  665.     }
  666.     offset3=new_ctrl->geom_s_stride;
  667.     offset2=new_ctrl->geom_s_stride*uorder;
  668.     for(j=0;j<ufactor_cnt;j++)
  669.     {
  670.         *(*ufactors+j*3+1)=tmp_factor1=calc_factor(ctrl,uorder,
  671.             j*offset2,offset3,tolerance,dim);
  672.         /* loop vfactor_cnt-1 times */
  673.         for(i=1;i<vfactor_cnt;i++)
  674.         {
  675.             tmp_factor2=calc_factor(ctrl,uorder,
  676.                 j*offset2+i*offset1,offset3,tolerance,dim);
  677.             if(tmp_factor2>tmp_factor1)
  678.                 tmp_factor1=tmp_factor2;
  679.         }
  680.         /* last time for the opposite edge */
  681.         *(*ufactors+j*3+2)=tmp_factor2=calc_factor(ctrl,uorder,
  682.             j*offset2+i*offset1-new_ctrl->geom_t_stride,
  683.             offset3,tolerance,dim);
  684.         if(tmp_factor2>tmp_factor1)
  685.             *(*ufactors+j*3)=tmp_factor2;
  686.         else
  687.             *(*ufactors+j*3)=tmp_factor1;
  688.     }
  689.     return GL_NO_ERROR;
  690. }
  691.  
  692. static GLenum
  693. calc_sampling_2D(GLfloat *ctrl, GLint cnt, GLint order,
  694.     GLfloat tolerance, GLint dim, GLint **factors)
  695. {
  696.     GLint        factor_cnt;
  697.     GLint        tmp_factor;
  698.     GLint        offset;
  699.     GLint        i;
  700.  
  701.     factor_cnt=cnt/order;
  702.     if((*factors=(GLint *)malloc(sizeof(GLint)*factor_cnt))==NULL)
  703.     {
  704.         return GLU_OUT_OF_MEMORY;
  705.     }
  706.     offset=order*dim;
  707.     for(i=0;i<factor_cnt;i++)
  708.     {
  709.         tmp_factor=calc_factor(ctrl,order,i*offset,dim,tolerance,dim);
  710.         if(tmp_factor == 0)
  711.             (*factors)[i]=1;
  712.         else
  713.             (*factors)[i]=tmp_factor;
  714.     }
  715.     return GL_NO_ERROR;
  716. }
  717.  
  718. static void
  719. set_sampling_and_culling( GLUnurbsObj *nobj )
  720. {
  721.     if(nobj->auto_load_matrix==GL_FALSE)
  722.     {
  723.         GLint i;
  724.         GLfloat m[4];
  725.  
  726.         glPushAttrib( (GLbitfield) (GL_VIEWPORT_BIT | GL_TRANSFORM_BIT));
  727.         for(i=0;i<4;i++)
  728.             m[i]=nobj->sampling_matrices.viewport[i];
  729.         glViewport(m[0],m[1],m[2],m[3]);
  730.         glMatrixMode(GL_PROJECTION);
  731.         glPushMatrix();
  732.         glLoadMatrixf(nobj->sampling_matrices.proj);
  733.         glMatrixMode(GL_MODELVIEW);
  734.         glPushMatrix();
  735.         glLoadMatrixf(nobj->sampling_matrices.model);
  736.     }
  737. }
  738.  
  739. static void
  740. revert_sampling_and_culling( GLUnurbsObj *nobj )
  741. {
  742.     if(nobj->auto_load_matrix==GL_FALSE)
  743.     {
  744.         glMatrixMode(GL_MODELVIEW);
  745.         glPopMatrix();
  746.         glMatrixMode(GL_PROJECTION);
  747.         glPopMatrix();
  748.         glPopAttrib();
  749.     }
  750. }
  751.  
  752. GLenum
  753. glu_do_sampling_3D( GLUnurbsObj *nobj, new_ctrl_type *new_ctrl,
  754.     GLint **sfactors, GLint **tfactors)
  755. {
  756.     GLint    dim;
  757.     GLenum    err;
  758.  
  759.     *sfactors=NULL;
  760.     *tfactors=NULL;
  761.     dim=nobj->surface.geom.dim;
  762.     set_sampling_and_culling(nobj);
  763.     if((err=calc_sampling_3D(new_ctrl,nobj->sampling_tolerance,dim,
  764.         nobj->surface.geom.sorder,nobj->surface.geom.torder,
  765.         sfactors,tfactors))==GLU_ERROR)
  766.     {
  767.         revert_sampling_and_culling(nobj);
  768.         call_user_error(nobj,err);
  769.         return GLU_ERROR;
  770.     }
  771.     revert_sampling_and_culling(nobj);
  772.     return GLU_NO_ERROR;
  773. }
  774.  
  775. GLenum
  776. glu_do_sampling_2D( GLUnurbsObj *nobj, GLfloat *ctrl, GLint cnt, GLint order,
  777.     GLint dim, GLint **factors)
  778. {
  779.     GLenum err;
  780.  
  781.     *factors=NULL;
  782.     set_sampling_and_culling(nobj);
  783.     if((err=calc_sampling_2D(ctrl,cnt,order,nobj->sampling_tolerance,dim,
  784.         factors))==GLU_ERROR)
  785.     {
  786.         revert_sampling_and_culling(nobj);
  787.         call_user_error(nobj,err);
  788.         return GLU_ERROR;
  789.     }
  790.     revert_sampling_and_culling(nobj);
  791.     return GLU_NO_ERROR;
  792. }
  793.  
  794. /* TODO - i don't like this culling - this one just tests if at least one */
  795. /* ctrl point lies within the viewport . Also the point_in_viewport() */
  796. /* should be included in the fnctions for efficiency reasons */
  797.  
  798. static GLboolean
  799. point_in_viewport(GLfloat *pt, GLint dim)
  800. {
  801.     GLdouble model[16],proj[16];
  802.     GLint viewport[4];
  803.     GLdouble x,y,z,w,winx,winy,winz;
  804.  
  805.     glGetDoublev(GL_MODELVIEW_MATRIX,model);
  806.     glGetDoublev(GL_PROJECTION_MATRIX,proj);
  807.     glGetIntegerv(GL_VIEWPORT,viewport);
  808.     if(dim==3)
  809.     {
  810.         x=(GLdouble)pt[0];
  811.         y=(GLdouble)pt[1];
  812.         z=(GLdouble)pt[2];
  813.         gluProject(x,y,z,model,proj,viewport,&winx,&winy,&winz);
  814.     }
  815.     else
  816.     {
  817.         w=(GLdouble)pt[3];
  818.         x=(GLdouble)pt[0]/w;
  819.         y=(GLdouble)pt[1]/w;
  820.         z=(GLdouble)pt[2]/w;
  821.         gluProject(x,y,z,model,proj,viewport,&winx,&winy,&winz);
  822.     }
  823.     if((GLint)winx >= viewport[0] && (GLint)winx < viewport[2] &&
  824.             (GLint)winy >= viewport[1] && (GLint)winy < viewport[3])
  825.         return GL_TRUE;
  826.     return GL_FALSE;
  827. }
  828.  
  829. GLboolean
  830. fine_culling_test_3D(GLUnurbsObj *nobj,GLfloat *pts,GLint s_cnt,GLint t_cnt,
  831.     GLint s_stride,GLint t_stride, GLint dim)
  832. {
  833.     GLint     i,j;
  834.  
  835.     if(nobj->culling==GL_FALSE)
  836.         return GL_FALSE;
  837.     set_sampling_and_culling(nobj);
  838.     
  839.     if(dim==3)
  840.     {
  841.         for(i=0;i<s_cnt;i++)
  842.             for(j=0;j<t_cnt;j++)
  843.                 if(point_in_viewport(pts+i*s_stride+j*t_stride,dim))
  844.                 {
  845.                     revert_sampling_and_culling(nobj);
  846.                     return GL_FALSE;
  847.                 }
  848.     }
  849.     else
  850.     {
  851.         for(i=0;i<s_cnt;i++)
  852.             for(j=0;j<t_cnt;j++)
  853.                 if(point_in_viewport(pts+i*s_stride+j*t_stride,dim))
  854.                 {
  855.                     revert_sampling_and_culling(nobj);
  856.                     return GL_FALSE;
  857.                 }
  858.     }
  859.     revert_sampling_and_culling(nobj);
  860.     return GL_TRUE;
  861. }
  862.  
  863. /*GLboolean
  864. fine_culling_test_3D(GLUnurbsObj *nobj,GLfloat *pts,GLint s_cnt,GLint t_cnt,
  865.     GLint s_stride,GLint t_stride, GLint dim)
  866. {
  867.     GLint        visible_cnt;
  868.     GLfloat        feedback_buffer[5];
  869.     GLsizei        buffer_size;
  870.     GLint         i,j;
  871.  
  872.     if(nobj->culling==GL_FALSE)
  873.         return GL_FALSE;
  874.     buffer_size=5;
  875.     set_sampling_and_culling(nobj);
  876.     
  877.     glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
  878.     glRenderMode(GL_FEEDBACK);
  879.     if(dim==3)
  880.     {
  881.         for(i=0;i<s_cnt;i++)
  882.         {
  883.             glBegin(GL_LINE_LOOP);
  884.             for(j=0;j<t_cnt;j++)
  885.                 glVertex3fv(pts+i*s_stride+j*t_stride);
  886.             glEnd();
  887.         }
  888.         for(j=0;j<t_cnt;j++)
  889.         {
  890.             glBegin(GL_LINE_LOOP);
  891.             for(i=0;i<s_cnt;i++)
  892.                 glVertex3fv(pts+i*s_stride+j*t_stride);
  893.             glEnd();
  894.         }
  895.     }
  896.     else
  897.     {
  898.         for(i=0;i<s_cnt;i++)
  899.         {
  900.             glBegin(GL_LINE_LOOP);
  901.             for(j=0;j<t_cnt;j++)
  902.                 glVertex4fv(pts+i*s_stride+j*t_stride);
  903.             glEnd();
  904.         }
  905.         for(j=0;j<t_cnt;j++)
  906.         {
  907.             glBegin(GL_LINE_LOOP);
  908.             for(i=0;i<s_cnt;i++)
  909.                 glVertex4fv(pts+i*s_stride+j*t_stride);
  910.             glEnd();
  911.         }
  912.     }
  913.     visible_cnt=glRenderMode(GL_RENDER);
  914.  
  915.     revert_sampling_and_culling(nobj);
  916.     return (GLboolean)(visible_cnt==0);
  917. }*/
  918.  
  919. GLboolean
  920. fine_culling_test_2D(GLUnurbsObj *nobj,GLfloat *pts,GLint cnt,
  921.     GLint stride, GLint dim)
  922. {
  923.     GLint     i;
  924.  
  925.     if(nobj->culling==GL_FALSE)
  926.         return GL_FALSE;
  927.     set_sampling_and_culling(nobj);
  928.     
  929.     if(dim==3)
  930.     {
  931.         for(i=0;i<cnt;i++)
  932.             if(point_in_viewport(pts+i*stride,dim))
  933.             {
  934.                 revert_sampling_and_culling(nobj);
  935.                 return GL_FALSE;
  936.             }
  937.     }
  938.     else
  939.     {
  940.         for(i=0;i<cnt;i++)
  941.             if(point_in_viewport(pts+i*stride,dim))
  942.             {
  943.                 revert_sampling_and_culling(nobj);
  944.                 return GL_FALSE;
  945.             }
  946.     }
  947.     revert_sampling_and_culling(nobj);
  948.     return GL_TRUE;
  949. }
  950.  
  951. /*GLboolean
  952. fine_culling_test_2D(GLUnurbsObj *nobj,GLfloat *pts,GLint cnt,
  953.     GLint stride, GLint dim)
  954. {
  955.     GLint        visible_cnt;
  956.     GLfloat        feedback_buffer[5];
  957.     GLsizei        buffer_size;
  958.     GLint         i;
  959.  
  960.     if(nobj->culling==GL_FALSE)
  961.         return GL_FALSE;
  962.     buffer_size=5;
  963.     set_sampling_and_culling(nobj);
  964.     
  965.     glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
  966.     glRenderMode(GL_FEEDBACK);
  967.     glBegin(GL_LINE_LOOP);
  968.     if(dim==3)
  969.     {
  970.         for(i=0;i<cnt;i++)
  971.             glVertex3fv(pts+i*stride);
  972.     }
  973.     else
  974.     {
  975.         for(i=0;i<cnt;i++)
  976.             glVertex4fv(pts+i*stride);
  977.     }
  978.     glEnd();
  979.     visible_cnt=glRenderMode(GL_RENDER);
  980.  
  981.     revert_sampling_and_culling(nobj);
  982.     return (GLboolean)(visible_cnt==0);
  983. }*/
  984.  
  985.