home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / graphics / 3d / icoons / source / tesselate.c < prev    next >
C/C++ Source or Header  |  1992-10-09  |  20KB  |  736 lines
  1. /* :ts=8 */    /* Yes some of us still use vi ! */
  2. /************************************************************************/
  3. /*                                                                      */
  4. /* This file contains code to tesselate the current object.        */
  5. /*                                                                      */
  6. /* This is done by iterative evaluation of the splines, and this isn't    */
  7. /* the fastest or best method.                        */
  8. /*                                                                      */
  9. /* A better method would be some kind of recursive subdivision which    */
  10. /* stops when the surfaces are nearly flat.                */
  11. /*                                                                      */
  12. /************************************************************************/
  13.  
  14. #include <math.h>
  15. #include <stdio.h>
  16. #include <string.h>
  17. #include <ctype.h>
  18. #include <errno.h>
  19. #include <stdlib.h>
  20.  
  21. #include "general.h"
  22. #include "globals.h"
  23. #include "intui.h"
  24. #include "spl_math.h"
  25. #include "tesselate.h"
  26.  
  27. #define Max_Nbr_Connections    2000
  28. #define Max_Nbr_Patches        1000
  29.  
  30. /* Blending functions for cubic polynomials (Bernstein pol.)     */
  31.  
  32. /* Below u1 is (1.0 - u)                    */
  33.  
  34. #define B03(u, u1)        ((u1) * (u1) * (u1))
  35. #define B13(u, u1)        (3.0 * (u) * (u1) * (u1))
  36. #define B23(u, u1)        (3.0 * (u) * (u) * (u1))
  37. #define B33(u, u1)        ((u) * (u) *(u))
  38.  
  39. /* Cubic hermite polynomials: */
  40. #define H03(u, u1)        (B03(u, u1) + B13(u, u1))
  41. #define H13(u, u1)        (0.33333 * B13(u, u1))
  42. #define H23(u, u1)        (0.33333 * B23(u, u1))
  43. #define H33(u, u1)        (B23(u, u1) + B33(u, u1))
  44.  
  45. #define F0(u, u1)        H03(u, u1)
  46. #define F1(u, u1)        H33(u, u1)
  47.  
  48. /* Another possibility for  F0 and F1 is:    */
  49. /* #define F0(u, u1)         (u1)        */
  50. /* #define F1(u, u1)         (u)        */
  51.  
  52. #define Parm(Idx, u, u1)     ((Connections[Idx].Dir > 0) ? (u) : (u1))
  53.  
  54.  
  55. typedef struct {
  56.     short        From;
  57.     short        To;
  58.     Spline_T    *Spline;
  59.     Knot_T        *Knot;
  60.     Byte_T        Count;
  61.     short        Dir;
  62. } Connection_T;
  63.  
  64.  
  65. typedef struct {
  66.     short         P1, P2, P3, P4;
  67. } Patch_T;
  68.  
  69.  
  70. static int     Step_S         = 10;    /* Number of steps (s).        */
  71. static int     Step_T         = 10;    /* Number of steps (t).        */
  72. static Vector_T  *Row0        = NULL;
  73. static Vector_T  *Row1        = NULL;
  74. static Vector_T  *Row2         = NULL;
  75.  
  76. static Connection_T    Connections[Max_Nbr_Connections];
  77. static int        Nbr_Connections;
  78. static Patch_T        Patches[Max_Nbr_Patches];
  79. static int        Nbr_Patches;
  80.  
  81. Boolean_T Face_Is_Ok(Vector_T Point0, Vector_T Point1, Vector_T Point2)
  82. /************************************************************************/
  83. /*                                    */
  84. /* Check if the three points defines a triangle.            */
  85. /* Return TRUE if they do.                        */
  86. /*                                    */
  87. /************************************************************************/
  88. {
  89.     double    X1, Y1, Z1;
  90.     double    X2, Y2, Z2;
  91.     double     Vx, Vy, Vz;
  92.  
  93.     X1 = Point1[0] - Point0[0];
  94.     Y1 = Point1[1] - Point0[1];
  95.     Z1 = Point1[2] - Point0[2];
  96.  
  97.     X2 = Point2[0] - Point0[0];
  98.     Y2 = Point2[1] - Point0[1];
  99.     Z2 = Point2[2] - Point0[2];
  100.  
  101.         /* Cross product:    */
  102.     Vx = Y1 * Z2 - Z1 * Y2;
  103.     Vy = Z1 * X2 - X1 * Z2;
  104.     Vz = X1 * Y2 - Y1 * X2;
  105.  
  106.     if (ABS(Vx) < FTINY && 
  107.         ABS(Vy) < FTINY && 
  108.         ABS(Vz) < FTINY) return(FALSE);
  109.  
  110.     return(TRUE);
  111.  
  112. } /* Face_Is_Ok */
  113.  
  114. Compute_Row(double S, register Vector_T *Row, int Step_Size, 
  115.     Matrix4_T M1, short C1, 
  116.     Matrix4_T M2, short C2, 
  117.     Matrix4_T M3, short C3, 
  118.     Matrix4_T M4, short C4)
  119. /************************************************************************/
  120. /*                                    */
  121. /* Compute row of values for a given 'S'.                */
  122. /* M1, M2, M3 and M4 is the for precomputed matrices for spline     */
  123. /* generation. C1, C2, C3 and C4 is indices into the connection list    */
  124. /* for the four connections in this patch.                */
  125. /*                                    */
  126. /* C2 is -1 for 2 spline patch                        */
  127. /* C4 is -1 for 2 or 3 spline patch                    */
  128. /*                                    */
  129. /************************************************************************/
  130. {
  131.     double      T, T1, S1;
  132.     double      F0s, F0t, F1s, F1t;
  133.     register int  i;
  134.     Vector4_T      Ps0, Ps1, P0t, P1t;
  135.     Vector4_T      P00, P10, P01, P11;
  136.     
  137.     if (S < -FTINY || S > 1.0+FTINY) return;
  138.     S1 = 1.0 - S;
  139.  
  140.     Compute_Position(P00, Parm(C1, 0.0, 1.0), M1);
  141.     Compute_Position(P10, Parm(C1, 1.0, 0.0), M1);
  142.     Compute_Position(P01, Parm(C3, 1.0, 0.0), M3);
  143.     Compute_Position(P11, Parm(C3, 0.0, 1.0), M3);
  144.  
  145.     if (C2 < 0) Compute_Position(P1t, Parm(C1, 1.0, 0.0), M1);
  146.     if (C4 < 0) Compute_Position(P0t, Parm(C1, 0.0, 1.0), M1);
  147.     i   = 0;
  148.  
  149.  
  150.     while (i <= Step_Size) {
  151.  
  152.     T = (double) i / Step_Size;
  153.         T1 = 1.0 - T;
  154.  
  155.     /* Compute P(S,T), place in Row[i] */
  156.  
  157.     Compute_Position(Ps0, Parm(C1, S, S1), M1);
  158.     if (C2 >= 0) Compute_Position(P1t, Parm(C2, T, T1), M2);
  159.     Compute_Position(Ps1, Parm(C3, S1, S), M3);
  160.     if (C4 >= 0) Compute_Position(P0t, Parm(C4, T1, T), M4);
  161.  
  162.          F0s = F0(S, S1);    /* Precompute these to speed things up */
  163.          F0t = F0(T, T1);
  164.          F1s = F1(S, S1);
  165.          F1t = F1(T, T1);
  166.  
  167.     Row[i][0] = F0s * P0t[0] + F1s * P1t[0] + 
  168.             F0t * Ps0[0] + F1t * Ps1[0] -
  169.             F0s * F0t * P00[0] -
  170.             F0s * F1t * P01[0] -
  171.             F1s * F0t * P10[0] -
  172.             F1s * F1t * P11[0];
  173.  
  174.     Row[i][1] = F0s * P0t[1] + F1s * P1t[1] + 
  175.             F0t * Ps0[1] + F1t * Ps1[1] -
  176.             F0s * F0t * P00[1] -
  177.             F0s * F1t * P01[1] -
  178.             F1s * F0t * P10[1] -
  179.             F1s * F1t * P11[1];
  180.  
  181.  
  182.     Row[i][2] = F0s * P0t[2] + F1s * P1t[2] + 
  183.             F0t * Ps0[2] + F1t * Ps1[2] -
  184.             F0s * F0t * P00[2] -
  185.             F0s * F1t * P01[2] -
  186.             F1s * F0t * P10[2] -
  187.             F1s * F1t * P11[2];
  188.  
  189.  
  190.  
  191.     i++;
  192.  
  193.     } /* while */
  194.  
  195.  
  196. } /* Compute_Row */
  197.  
  198. int    Tesselate_Patch(Tesselate_Info_T *TI, 
  199.             short C1, short C2, short C3, short C4)
  200. /************************************************************************/
  201. /*                                    */
  202. /* Tesselate the patch given by the splines C1, C2, C3 and C4.        */
  203. /*                                    */
  204. /* C2 is -1 for a 2 spline patch                     */
  205. /* C4 is -1 for a 2 or 3 spline patch                    */
  206. /*                                    */
  207. /************************************************************************/
  208. {
  209.     int            i, j;
  210.     Vector_T        *Tmp_Row;
  211.     Matrix4_T        M1, M2, M3, M4;
  212.     static int        Old_Step_S = -1;
  213.     static int        Old_Step_T = -1;
  214.  
  215.     if (TI->Patch_Begin != NULL) TI->Patch_Begin();
  216.  
  217.     Step_S = Step_T = Patch_Resolution;
  218.  
  219.     if (Step_T != Old_Step_T || 
  220.     Row0 == NULL || Row1 == NULL || Row2 == NULL) {
  221.  
  222.     if (Row0 != NULL) free(Row0);
  223.     if (Row1 != NULL) free(Row1);
  224.     if (Row2 != NULL) free(Row2);
  225.  
  226.         Row0 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) );
  227.         if (Row0 == NULL) {
  228.         Display_Error_Message("malloc error");
  229.           CloseStuff();
  230.         exit(9);
  231.     } /* if */
  232.  
  233.         Row1 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) );
  234.         if (Row1 == NULL) {
  235.         Display_Error_Message("malloc error");
  236.           CloseStuff();
  237.         exit(9);
  238.     } /* if */
  239.  
  240.         Row2 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) );
  241.         if (Row2 == NULL) {
  242.         Display_Error_Message("malloc error");
  243.           CloseStuff();
  244.         exit(9);
  245.     } /* if */
  246.  
  247.     } /* if */
  248.  
  249.     Old_Step_S = Step_S;
  250.     Old_Step_T = Step_T;
  251.  
  252.     Precompute_Kochanek_Bartels(M1, 
  253.                 Connections[C1].Spline,
  254.             Connections[C1].Knot);
  255.  
  256.     if (C2 >= 0)  Precompute_Kochanek_Bartels(M2, 
  257.                 Connections[C2].Spline,
  258.             Connections[C2].Knot);
  259.  
  260.     Precompute_Kochanek_Bartels(M3, 
  261.                 Connections[C3].Spline,
  262.             Connections[C3].Knot);
  263.  
  264.     if (C4 >= 0)  Precompute_Kochanek_Bartels(M4, 
  265.                 Connections[C4].Spline,
  266.             Connections[C4].Knot);
  267.  
  268.     /* Initialize the first rows                */
  269.     /* It is not neccessary to initialize Row0, as it is    */
  270.     /* computed as the first step in the main loop.        */
  271.  
  272.     Compute_Row(0.0,        Row1, Step_T, M1, C1, M2, C2, M3, C3, M4, C4);
  273.     Compute_Row(1.0/Step_S, Row2, Step_T, M1, C1, M2, C2, M3, C3, M4, C4);
  274.     
  275.         
  276.     for (i = 0; i < Step_S; i++) {
  277.  
  278.                         /* compute next row */
  279.     Tmp_Row = Row0;
  280.     Row0    = Row1;
  281.     Row1    = Row2;
  282.     Row2    = Tmp_Row;
  283.  
  284.     Compute_Row((double)(i + 2) / Step_S, Row2, Step_T, 
  285.                 M1, C1, M2, C2, M3, C3, M4, C4);
  286.  
  287.     for (j = 0; j < Step_T; j++) {
  288.  
  289.         if ( (i + j) & 1 ) {
  290.  
  291.         TI->Patch_Generate_Face(
  292.                 Row0[j], Row1[j], Row0[j+1], Row1[j+1]);
  293.  
  294.         } else {
  295.  
  296.         TI->Patch_Generate_Face(
  297.                  Row1[j], Row1[j+1], Row0[j], Row0[j+1]);
  298.  
  299.         }
  300.  
  301.     } /* for */
  302.  
  303.     } /* for */
  304.  
  305.     if (TI->Patch_End != NULL) TI->Patch_End();
  306.  
  307. } /* Tesselate_Patch */
  308.  
  309. static 
  310. void Sort4(short *i1, short *i2, short *i3, short *i4)
  311. /************************************************************************/
  312. /*                                    */
  313. /* Sort the four numbers i1, i2, i3 and i4.                */
  314. /*                                    */
  315. /************************************************************************/
  316. {
  317.     short t;
  318.  
  319.     if (*i2 < *i1) { t = *i1; *i1 = *i2; *i2 = t; }
  320.     if (*i4 < *i3) { t = *i3; *i3 = *i4; *i4 = t; }
  321.     if (*i3 < *i2) { t = *i3; *i3 = *i2; *i2 = t; }
  322.     if (*i2 < *i1) { t = *i1; *i1 = *i2; *i2 = t; }
  323.     if (*i4 < *i3) { t = *i3; *i3 = *i4; *i4 = t; }
  324.     if (*i3 < *i2) { t = *i3; *i3 = *i2; *i2 = t; }
  325.  
  326. } /* Sort4 */
  327.  
  328. static 
  329. Boolean_T Patch_Add(short P1, short P2, short P3, short P4)
  330. /************************************************************************/
  331. /*                                    */
  332. /* Add the patch defined by P1, P2, P3 and P4 to the patch table.    */
  333. /* Return TRUE if the patch already existed in the table.        */
  334. /*                                    */
  335. /* (Linear search!!! Optimize please :)                    */
  336. /*                                    */
  337. /************************************************************************/
  338. {
  339.     int        i;
  340.  
  341.     Sort4(&P1, &P2, &P3, &P4);
  342.  
  343.     for (i = 0; i < Nbr_Patches; i++) {
  344.  
  345.         if (Patches[i].P1 == P1 &&
  346.             Patches[i].P2 == P2 &&
  347.             Patches[i].P3 == P3 &&
  348.             Patches[i].P4 == P4) return(TRUE);
  349.  
  350.     } /* for */
  351.  
  352.     if (Nbr_Patches < Max_Nbr_Patches-1) {
  353.  
  354.         Patches[Nbr_Patches].P1 = P1;
  355.         Patches[Nbr_Patches].P2 = P2;
  356.         Patches[Nbr_Patches].P3 = P3;
  357.         Patches[Nbr_Patches].P4 = P4;
  358.  
  359.     Nbr_Patches++;
  360.  
  361.     } else {
  362.  
  363.     Display_Error_Message("No more space for patches");
  364.     CloseStuff();
  365.     exit(1);
  366.  
  367.     } /* if .. else .. */
  368.  
  369.     return(FALSE);
  370.  
  371. } /* Patch_Add */
  372.  
  373. static 
  374. int Find_From_Connection(short From, short To)
  375. /************************************************************************/
  376. /*                                    */
  377. /* Find a connection starting in 'From' and NOT leading to 'To'.    */
  378. /*                                    */
  379. /************************************************************************/
  380. {
  381.     int    i;
  382.  
  383.     for (i = 0; i < Nbr_Connections; i++)
  384.         if (Connections[i].Count < 2 &&
  385.         Connections[i].From == From && Connections[i].To != To) 
  386.                                 return(i);
  387.  
  388.     return(-1);
  389.  
  390. } /* Find_From_Connection */
  391.  
  392. static 
  393. int Find_From_To_Connection(short From, short To)
  394. /************************************************************************/
  395. /*                                    */
  396. /* Find a connection starting in 'From' and leading to 'To'.        */
  397. /*                                    */
  398. /************************************************************************/
  399. {
  400.     int    i;
  401.  
  402.     for (i = 0; i < Nbr_Connections; i++)
  403.         if (Connections[i].Count < 2 &&
  404.         Connections[i].From == From && Connections[i].To == To) 
  405.                                 return(i);
  406.  
  407.     return(-1);
  408.  
  409. } /* Find_From_Connection */
  410.  
  411. static 
  412. int Find_From_To_Spline_Connection(Spline_T *Spline, short From, short To)
  413. /************************************************************************/
  414. /*                                    */
  415. /* Find a connection starting in 'From' and leading to 'To'.        */
  416. /* The found connection must NOT be given by 'Spline'.            */
  417. /*                                    */
  418. /************************************************************************/
  419. {
  420.     int    i;
  421.  
  422.     for (i = 0; i < Nbr_Connections; i++)
  423.         if (Connections[i].Spline != Spline &&
  424.         Connections[i].Count < 2 &&
  425.         Connections[i].From == From && Connections[i].To == To) 
  426.                                 return(i);
  427.  
  428.     return(-1);
  429.  
  430. } /* Find_From_To_Spline_Connection */
  431.  
  432. static 
  433. void Remove_Connection(int Id)
  434. /************************************************************************/
  435. /*                                    */
  436. /* Increase usage count for the connection given by 'Id'.        */
  437. /* Each connection may be used two times.                */
  438. /*                                    */
  439. /************************************************************************/
  440. {
  441.     int    Id2;
  442.  
  443.     Id2 = Find_From_To_Connection(Connections[Id].To, 
  444.                       Connections[Id].From);
  445.  
  446.     Connections[Id].Count++;
  447.     
  448.     if (Id2 >= 0) Connections[Id2].Count++;
  449.  
  450. } /* Remove_Connection */
  451.  
  452. int CompareFunc(Connection_T *Con1, Connection_T *Con2)
  453. /************************************************************************/
  454. /*                                    */
  455. /* Compare two connections. This is used by 'qsort'.            */
  456. /*                                    */
  457. /************************************************************************/
  458. {
  459.     if (Con1->From < Con2->From) return(-1);
  460.     if (Con1->From > Con2->From) return(1);
  461.     if (Con1->To   < Con2->To)   return(-1);
  462.     if (Con1->To   > Con2->To)   return(1);
  463.     return(0);
  464.  
  465. } /* CompareFunc */
  466.  
  467. Boolean_T Tesselate_Object(Tesselate_Info_T *TI)
  468. /************************************************************************/
  469. /*                                    */
  470. /* This function is called to tesselate the current object.        */
  471. /*                                    */
  472. /* This is done by dividing the object into patches, and then tesselate    */
  473. /* these patches.                            */
  474. /*                                    */
  475. /* The argument 'TI' defines what to do with the result.        */
  476. /*                                    */
  477. /* TI is a structure which contains pointers to 3 functions:        */
  478. /*                                    */
  479. /*  void (*Patch_Begin)(void):                        */
  480. /*    This function is called before tesselation of a new patch starts*/
  481. /*     It could for instance be used to initialize variables.        */
  482. /*    This function pointer may be a NULL pointer.            */
  483. /*                                    */
  484. /*  void (*Patch_Generate_Face)(Vector_T Point0, Vector_T Point1,     */
  485. /*                        Vector_T Point2, Vector_T Point3):    */
  486. /*     This function is called for each found 'rectangle'.        */
  487. /*    The rectangle isn't necessarily flat, and may be degenerate, so    */
  488. /*    normally, the routine should split it into two triangles and    */
  489. /*     test that the triangles isn't degenerate.            */
  490. /*                                    */
  491. /*  void (*Patch_End)(void):                        */
  492. /*    This function is called after tesselation of a patch is done.    */
  493. /*    It can be used to free memory, write data to a file or whatever.*/
  494. /*    This function pointer may be a NULL pointer.            */
  495. /*                                    */
  496. /* 'Tesselate_Object' will return TRUE in case of error.        */
  497. /*                                    */
  498. /************************************************************************/
  499. {
  500.     Spline_T    *Spline;
  501.     Knot_T    *Knot;
  502.     int     j;
  503.     int        Patch_Count;
  504.     short    P1, P2, P3, P4;
  505.     short    C1, C2, C3, C4;
  506.  
  507.     Nbr_Connections = 0;
  508.     Nbr_Patches        = 0;
  509.  
  510.     /* Add all splines to the connection list:    */
  511.     Display_Status("Adding splines to connection list");
  512.  
  513.     for (Spline = Splines; Spline != NULL; Spline = Spline->Next) {
  514.  
  515.         if (Spline->Nbr_Knots > 1) {
  516.  
  517.         for (j = 1, Knot = Spline->First; 
  518.              j < Spline->Nbr_Knots; j++, Knot = Knot->Next) {
  519.  
  520.         if (Is_Hidden(Points[Knot->Point_Id])) continue;
  521.  
  522.         if (Nbr_Connections >= Max_Nbr_Connections-2) {
  523.             Display_Message("No more space for connections");
  524.             return(TRUE);
  525.         }
  526.         Connections[Nbr_Connections].From    = Knot->Point_Id;
  527.         Connections[Nbr_Connections].To      = Knot->Next->Point_Id;
  528.         Connections[Nbr_Connections].Spline  = Spline;
  529.         Connections[Nbr_Connections].Knot    = Knot;
  530.         Connections[Nbr_Connections].Dir     = 1;
  531.         Connections[Nbr_Connections++].Count = 0;
  532.  
  533.         Connections[Nbr_Connections].From    = Knot->Next->Point_Id;
  534.         Connections[Nbr_Connections].To      = Knot->Point_Id;
  535.         Connections[Nbr_Connections].Spline  = Spline;
  536.         Connections[Nbr_Connections].Knot    = Knot;
  537.         Connections[Nbr_Connections].Dir     = -1;
  538.         Connections[Nbr_Connections++].Count = 0;
  539.  
  540.         } /* for */
  541.  
  542.         if (Spline->Loop & !Is_Hidden(Points[Knot->Point_Id])){
  543.  
  544.         if (Nbr_Connections >= Max_Nbr_Connections-2) {
  545.             Display_Message("No more space for connections");
  546.             return(TRUE);
  547.         }
  548.  
  549.         Connections[Nbr_Connections].From    = Knot->Point_Id;
  550.         Connections[Nbr_Connections].To =  Spline->First->Point_Id;
  551.         Connections[Nbr_Connections].Spline  =  Spline;
  552.         Connections[Nbr_Connections].Knot    =  Knot;
  553.         Connections[Nbr_Connections].Dir     =  1;
  554.         Connections[Nbr_Connections++].Count =  0;
  555.  
  556.         Connections[Nbr_Connections].From = Spline->First->Point_Id;
  557.         Connections[Nbr_Connections].To      =  Knot->Point_Id;
  558.         Connections[Nbr_Connections].Spline  =  Spline;
  559.         Connections[Nbr_Connections].Knot    = Knot;
  560.         Connections[Nbr_Connections].Dir     =  -1;
  561.         Connections[Nbr_Connections++].Count =  0;
  562.  
  563.         } /* if */
  564.  
  565.     } /* if */
  566.  
  567.     } /* for */
  568.     
  569.     /* Sort the connection list:    */
  570.     sprintf(Error_Msg, "Sorting %d connections.", Nbr_Connections);
  571.     Display_Status(Error_Msg);
  572.     qsort((char *)Connections, Nbr_Connections, 
  573.                 sizeof(Connection_T), CompareFunc);
  574.  
  575.     /* Find all two spline patches    */
  576.  
  577.     Patch_Count = 0;
  578.  
  579.     for (C1 = 0; C1 < Nbr_Connections; C1++) {
  580.  
  581.         P1 = Connections[C1].From;
  582.         P2 = Connections[C1].To;
  583.  
  584.     if (Connections[C1].Count >= 2) continue;
  585.  
  586.     C2 = Find_From_To_Spline_Connection(Connections[C1].Spline, 
  587.                                 P2, P1);
  588.     if (C2 != -1) {
  589.  
  590.             /* Won't accept both points on same spline */
  591.         if (Connections[C1].Spline ==
  592.             Connections[C2].Spline) continue;
  593.  
  594.         if (!Patch_Add(Connections[C1].From,
  595.                Connections[C2].From,
  596.                -1,
  597.                -1)) {
  598.             /* Found, C1, C2 */
  599.  
  600.     sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count);
  601.     Display_Status(Error_Msg);
  602.             Tesselate_Patch(TI, C1, -1, C2, -1);
  603.  
  604.             Remove_Connection(C1);
  605.             Remove_Connection(C2);
  606.         }
  607.         goto NextA; /* Stop loop */
  608.  
  609.     } /* if */
  610.  
  611. NextA: ;
  612.     } /* for */
  613.  
  614.  
  615.     /* Find all three spline patches    */
  616.  
  617.     for (C1 = 0; C1 < Nbr_Connections; C1++) {
  618.  
  619.         P1 = Connections[C1].From;
  620.         P2 = Connections[C1].To;
  621.  
  622.     if (Connections[C1].Count >= 2) continue;
  623.  
  624.     C2 = Find_From_Connection(P2, P1);
  625.     if (C2 == -1) goto NextB;
  626.         do {
  627.  
  628.         P3 = Connections[C2].To;
  629.         if (P3 == P1) continue;
  630.  
  631.         C3 = Find_From_To_Connection(P3, P1);
  632.         if (C3 != -1) {
  633.  
  634.             /* We won't accept all three points on same spline */
  635.         if (Connections[C1].Spline ==
  636.             Connections[C2].Spline &&
  637.             Connections[C2].Spline ==
  638.             Connections[C3].Spline) continue;
  639.  
  640.             if (!Patch_Add(Connections[C1].From,
  641.                    Connections[C2].From,
  642.                    Connections[C3].From,
  643.                    -1)) {
  644.             /* Found, C1, C2, C3 */
  645.  
  646.     sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count);
  647.     Display_Status(Error_Msg);
  648.             Tesselate_Patch(TI, C1, C2, C3, -1);
  649.  
  650.             Remove_Connection(C1);
  651.             Remove_Connection(C2);
  652.             Remove_Connection(C3);
  653.           }
  654.         goto NextB; /* Stop loop */
  655.  
  656.         } /* if */
  657.  
  658.     } while (++C2 < Nbr_Connections && Connections[C2].From == P2);
  659. NextB: ;
  660.     } /* for */
  661.  
  662.  
  663.     /* Find all four spline patches    */
  664.  
  665.     for (C1 = 0; C1 < Nbr_Connections; C1++) {
  666.  
  667.         P1 = Connections[C1].From;
  668.         P2 = Connections[C1].To;
  669.  
  670.     if (Connections[C1].Count >= 2) continue;
  671.  
  672.     C2 = Find_From_Connection(P2, P1);
  673.     if (C2 == -1) continue;
  674.  
  675.         do {
  676.  
  677.         P3 = Connections[C2].To;
  678.         if (P3 == P1) continue;
  679.  
  680.         C3 = Find_From_Connection(P3, P2);
  681.         if (C3 == -1) continue;
  682.         do {
  683.  
  684.             P4 = Connections[C3].To;
  685.             if (P4 == P2) continue;
  686.  
  687.             C4 = Find_From_To_Connection(P4, P1);
  688.  
  689.             if (C4 != -1) {
  690.  
  691.             /* We won't accept all four points on same spline */
  692.  
  693.         if (Connections[C1].Spline ==
  694.             Connections[C2].Spline &&
  695.             Connections[C2].Spline ==
  696.             Connections[C3].Spline &&
  697.             Connections[C3].Spline ==
  698.             Connections[C4].Spline) continue;
  699.  
  700.               if (!Patch_Add(Connections[C1].From,
  701.                    Connections[C2].From,
  702.                    Connections[C3].From,
  703.                    Connections[C4].From)) {
  704.                 /* Found, C1, C2, C3, C4 */
  705.  
  706.     sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count);
  707.     Display_Status(Error_Msg);
  708.             Tesselate_Patch(TI, C1, C2, C3, C4);
  709.  
  710.               Remove_Connection(C1);
  711.               Remove_Connection(C2);
  712.               Remove_Connection(C3);
  713.               Remove_Connection(C4);
  714.             }
  715.             goto Next1; /* Stop loop */
  716.  
  717.             } /* if */
  718.  
  719.         } while (++C3 < Nbr_Connections && Connections[C3].From == P3);
  720.  
  721.     } while (++C2 < Nbr_Connections && Connections[C2].From == P2);
  722.  
  723. Next1: ;
  724.     } /* for */
  725.  
  726.     if (Row0 != NULL) free(Row0);
  727.     if (Row1 != NULL) free(Row1);
  728.     if (Row2 != NULL) free(Row2);
  729.     Row0 = Row1 = Row2 = NULL;
  730.  
  731.     Display_Status("Tesselation done");
  732.  
  733.     return(FALSE);
  734.  
  735. } /* Tesselate_Object */
  736.