/* :ts=8 */ /* Yes some of us still use vi ! */ /************************************************************************/ /* */ /* This file contains code to tesselate the current object. */ /* */ /* This is done by iterative evaluation of the splines, and this isn't */ /* the fastest or best method. */ /* */ /* A better method would be some kind of recursive subdivision which */ /* stops when the surfaces are nearly flat. */ /* */ /************************************************************************/ #include #include #include #include #include #include #include "general.h" #include "globals.h" #include "intui.h" #include "spl_math.h" #include "tesselate.h" #define Max_Nbr_Connections 2000 #define Max_Nbr_Patches 1000 /* Blending functions for cubic polynomials (Bernstein pol.) */ /* Below u1 is (1.0 - u) */ #define B03(u, u1) ((u1) * (u1) * (u1)) #define B13(u, u1) (3.0 * (u) * (u1) * (u1)) #define B23(u, u1) (3.0 * (u) * (u) * (u1)) #define B33(u, u1) ((u) * (u) *(u)) /* Cubic hermite polynomials: */ #define H03(u, u1) (B03(u, u1) + B13(u, u1)) #define H13(u, u1) (0.33333 * B13(u, u1)) #define H23(u, u1) (0.33333 * B23(u, u1)) #define H33(u, u1) (B23(u, u1) + B33(u, u1)) #define F0(u, u1) H03(u, u1) #define F1(u, u1) H33(u, u1) /* Another possibility for F0 and F1 is: */ /* #define F0(u, u1) (u1) */ /* #define F1(u, u1) (u) */ #define Parm(Idx, u, u1) ((Connections[Idx].Dir > 0) ? (u) : (u1)) typedef struct { short From; short To; Spline_T *Spline; Knot_T *Knot; Byte_T Count; short Dir; } Connection_T; typedef struct { short P1, P2, P3, P4; } Patch_T; static int Step_S = 10; /* Number of steps (s). */ static int Step_T = 10; /* Number of steps (t). */ static Vector_T *Row0 = NULL; static Vector_T *Row1 = NULL; static Vector_T *Row2 = NULL; static Connection_T Connections[Max_Nbr_Connections]; static int Nbr_Connections; static Patch_T Patches[Max_Nbr_Patches]; static int Nbr_Patches; Boolean_T Face_Is_Ok(Vector_T Point0, Vector_T Point1, Vector_T Point2) /************************************************************************/ /* */ /* Check if the three points defines a triangle. */ /* Return TRUE if they do. */ /* */ /************************************************************************/ { double X1, Y1, Z1; double X2, Y2, Z2; double Vx, Vy, Vz; X1 = Point1[0] - Point0[0]; Y1 = Point1[1] - Point0[1]; Z1 = Point1[2] - Point0[2]; X2 = Point2[0] - Point0[0]; Y2 = Point2[1] - Point0[1]; Z2 = Point2[2] - Point0[2]; /* Cross product: */ Vx = Y1 * Z2 - Z1 * Y2; Vy = Z1 * X2 - X1 * Z2; Vz = X1 * Y2 - Y1 * X2; if (ABS(Vx) < FTINY && ABS(Vy) < FTINY && ABS(Vz) < FTINY) return(FALSE); return(TRUE); } /* Face_Is_Ok */ Compute_Row(double S, register Vector_T *Row, int Step_Size, Matrix4_T M1, short C1, Matrix4_T M2, short C2, Matrix4_T M3, short C3, Matrix4_T M4, short C4) /************************************************************************/ /* */ /* Compute row of values for a given 'S'. */ /* M1, M2, M3 and M4 is the for precomputed matrices for spline */ /* generation. C1, C2, C3 and C4 is indices into the connection list */ /* for the four connections in this patch. */ /* */ /* C2 is -1 for 2 spline patch */ /* C4 is -1 for 2 or 3 spline patch */ /* */ /************************************************************************/ { double T, T1, S1; double F0s, F0t, F1s, F1t; register int i; Vector4_T Ps0, Ps1, P0t, P1t; Vector4_T P00, P10, P01, P11; if (S < -FTINY || S > 1.0+FTINY) return; S1 = 1.0 - S; Compute_Position(P00, Parm(C1, 0.0, 1.0), M1); Compute_Position(P10, Parm(C1, 1.0, 0.0), M1); Compute_Position(P01, Parm(C3, 1.0, 0.0), M3); Compute_Position(P11, Parm(C3, 0.0, 1.0), M3); if (C2 < 0) Compute_Position(P1t, Parm(C1, 1.0, 0.0), M1); if (C4 < 0) Compute_Position(P0t, Parm(C1, 0.0, 1.0), M1); i = 0; while (i <= Step_Size) { T = (double) i / Step_Size; T1 = 1.0 - T; /* Compute P(S,T), place in Row[i] */ Compute_Position(Ps0, Parm(C1, S, S1), M1); if (C2 >= 0) Compute_Position(P1t, Parm(C2, T, T1), M2); Compute_Position(Ps1, Parm(C3, S1, S), M3); if (C4 >= 0) Compute_Position(P0t, Parm(C4, T1, T), M4); F0s = F0(S, S1); /* Precompute these to speed things up */ F0t = F0(T, T1); F1s = F1(S, S1); F1t = F1(T, T1); Row[i][0] = F0s * P0t[0] + F1s * P1t[0] + F0t * Ps0[0] + F1t * Ps1[0] - F0s * F0t * P00[0] - F0s * F1t * P01[0] - F1s * F0t * P10[0] - F1s * F1t * P11[0]; Row[i][1] = F0s * P0t[1] + F1s * P1t[1] + F0t * Ps0[1] + F1t * Ps1[1] - F0s * F0t * P00[1] - F0s * F1t * P01[1] - F1s * F0t * P10[1] - F1s * F1t * P11[1]; Row[i][2] = F0s * P0t[2] + F1s * P1t[2] + F0t * Ps0[2] + F1t * Ps1[2] - F0s * F0t * P00[2] - F0s * F1t * P01[2] - F1s * F0t * P10[2] - F1s * F1t * P11[2]; i++; } /* while */ } /* Compute_Row */ int Tesselate_Patch(Tesselate_Info_T *TI, short C1, short C2, short C3, short C4) /************************************************************************/ /* */ /* Tesselate the patch given by the splines C1, C2, C3 and C4. */ /* */ /* C2 is -1 for a 2 spline patch */ /* C4 is -1 for a 2 or 3 spline patch */ /* */ /************************************************************************/ { int i, j; Vector_T *Tmp_Row; Matrix4_T M1, M2, M3, M4; static int Old_Step_S = -1; static int Old_Step_T = -1; if (TI->Patch_Begin != NULL) TI->Patch_Begin(); Step_S = Step_T = Patch_Resolution; if (Step_T != Old_Step_T || Row0 == NULL || Row1 == NULL || Row2 == NULL) { if (Row0 != NULL) free(Row0); if (Row1 != NULL) free(Row1); if (Row2 != NULL) free(Row2); Row0 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) ); if (Row0 == NULL) { Display_Error_Message("malloc error"); CloseStuff(); exit(9); } /* if */ Row1 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) ); if (Row1 == NULL) { Display_Error_Message("malloc error"); CloseStuff(); exit(9); } /* if */ Row2 = (Vector_T *) malloc( (Step_T+3) * sizeof(Vector_T) ); if (Row2 == NULL) { Display_Error_Message("malloc error"); CloseStuff(); exit(9); } /* if */ } /* if */ Old_Step_S = Step_S; Old_Step_T = Step_T; Precompute_Kochanek_Bartels(M1, Connections[C1].Spline, Connections[C1].Knot); if (C2 >= 0) Precompute_Kochanek_Bartels(M2, Connections[C2].Spline, Connections[C2].Knot); Precompute_Kochanek_Bartels(M3, Connections[C3].Spline, Connections[C3].Knot); if (C4 >= 0) Precompute_Kochanek_Bartels(M4, Connections[C4].Spline, Connections[C4].Knot); /* Initialize the first rows */ /* It is not neccessary to initialize Row0, as it is */ /* computed as the first step in the main loop. */ Compute_Row(0.0, Row1, Step_T, M1, C1, M2, C2, M3, C3, M4, C4); Compute_Row(1.0/Step_S, Row2, Step_T, M1, C1, M2, C2, M3, C3, M4, C4); for (i = 0; i < Step_S; i++) { /* compute next row */ Tmp_Row = Row0; Row0 = Row1; Row1 = Row2; Row2 = Tmp_Row; Compute_Row((double)(i + 2) / Step_S, Row2, Step_T, M1, C1, M2, C2, M3, C3, M4, C4); for (j = 0; j < Step_T; j++) { if ( (i + j) & 1 ) { TI->Patch_Generate_Face( Row0[j], Row1[j], Row0[j+1], Row1[j+1]); } else { TI->Patch_Generate_Face( Row1[j], Row1[j+1], Row0[j], Row0[j+1]); } } /* for */ } /* for */ if (TI->Patch_End != NULL) TI->Patch_End(); } /* Tesselate_Patch */ static void Sort4(short *i1, short *i2, short *i3, short *i4) /************************************************************************/ /* */ /* Sort the four numbers i1, i2, i3 and i4. */ /* */ /************************************************************************/ { short t; if (*i2 < *i1) { t = *i1; *i1 = *i2; *i2 = t; } if (*i4 < *i3) { t = *i3; *i3 = *i4; *i4 = t; } if (*i3 < *i2) { t = *i3; *i3 = *i2; *i2 = t; } if (*i2 < *i1) { t = *i1; *i1 = *i2; *i2 = t; } if (*i4 < *i3) { t = *i3; *i3 = *i4; *i4 = t; } if (*i3 < *i2) { t = *i3; *i3 = *i2; *i2 = t; } } /* Sort4 */ static Boolean_T Patch_Add(short P1, short P2, short P3, short P4) /************************************************************************/ /* */ /* Add the patch defined by P1, P2, P3 and P4 to the patch table. */ /* Return TRUE if the patch already existed in the table. */ /* */ /* (Linear search!!! Optimize please :) */ /* */ /************************************************************************/ { int i; Sort4(&P1, &P2, &P3, &P4); for (i = 0; i < Nbr_Patches; i++) { if (Patches[i].P1 == P1 && Patches[i].P2 == P2 && Patches[i].P3 == P3 && Patches[i].P4 == P4) return(TRUE); } /* for */ if (Nbr_Patches < Max_Nbr_Patches-1) { Patches[Nbr_Patches].P1 = P1; Patches[Nbr_Patches].P2 = P2; Patches[Nbr_Patches].P3 = P3; Patches[Nbr_Patches].P4 = P4; Nbr_Patches++; } else { Display_Error_Message("No more space for patches"); CloseStuff(); exit(1); } /* if .. else .. */ return(FALSE); } /* Patch_Add */ static int Find_From_Connection(short From, short To) /************************************************************************/ /* */ /* Find a connection starting in 'From' and NOT leading to 'To'. */ /* */ /************************************************************************/ { int i; for (i = 0; i < Nbr_Connections; i++) if (Connections[i].Count < 2 && Connections[i].From == From && Connections[i].To != To) return(i); return(-1); } /* Find_From_Connection */ static int Find_From_To_Connection(short From, short To) /************************************************************************/ /* */ /* Find a connection starting in 'From' and leading to 'To'. */ /* */ /************************************************************************/ { int i; for (i = 0; i < Nbr_Connections; i++) if (Connections[i].Count < 2 && Connections[i].From == From && Connections[i].To == To) return(i); return(-1); } /* Find_From_Connection */ static int Find_From_To_Spline_Connection(Spline_T *Spline, short From, short To) /************************************************************************/ /* */ /* Find a connection starting in 'From' and leading to 'To'. */ /* The found connection must NOT be given by 'Spline'. */ /* */ /************************************************************************/ { int i; for (i = 0; i < Nbr_Connections; i++) if (Connections[i].Spline != Spline && Connections[i].Count < 2 && Connections[i].From == From && Connections[i].To == To) return(i); return(-1); } /* Find_From_To_Spline_Connection */ static void Remove_Connection(int Id) /************************************************************************/ /* */ /* Increase usage count for the connection given by 'Id'. */ /* Each connection may be used two times. */ /* */ /************************************************************************/ { int Id2; Id2 = Find_From_To_Connection(Connections[Id].To, Connections[Id].From); Connections[Id].Count++; if (Id2 >= 0) Connections[Id2].Count++; } /* Remove_Connection */ int CompareFunc(Connection_T *Con1, Connection_T *Con2) /************************************************************************/ /* */ /* Compare two connections. This is used by 'qsort'. */ /* */ /************************************************************************/ { if (Con1->From < Con2->From) return(-1); if (Con1->From > Con2->From) return(1); if (Con1->To < Con2->To) return(-1); if (Con1->To > Con2->To) return(1); return(0); } /* CompareFunc */ Boolean_T Tesselate_Object(Tesselate_Info_T *TI) /************************************************************************/ /* */ /* This function is called to tesselate the current object. */ /* */ /* This is done by dividing the object into patches, and then tesselate */ /* these patches. */ /* */ /* The argument 'TI' defines what to do with the result. */ /* */ /* TI is a structure which contains pointers to 3 functions: */ /* */ /* void (*Patch_Begin)(void): */ /* This function is called before tesselation of a new patch starts*/ /* It could for instance be used to initialize variables. */ /* This function pointer may be a NULL pointer. */ /* */ /* void (*Patch_Generate_Face)(Vector_T Point0, Vector_T Point1, */ /* Vector_T Point2, Vector_T Point3): */ /* This function is called for each found 'rectangle'. */ /* The rectangle isn't necessarily flat, and may be degenerate, so */ /* normally, the routine should split it into two triangles and */ /* test that the triangles isn't degenerate. */ /* */ /* void (*Patch_End)(void): */ /* This function is called after tesselation of a patch is done. */ /* It can be used to free memory, write data to a file or whatever.*/ /* This function pointer may be a NULL pointer. */ /* */ /* 'Tesselate_Object' will return TRUE in case of error. */ /* */ /************************************************************************/ { Spline_T *Spline; Knot_T *Knot; int j; int Patch_Count; short P1, P2, P3, P4; short C1, C2, C3, C4; Nbr_Connections = 0; Nbr_Patches = 0; /* Add all splines to the connection list: */ Display_Status("Adding splines to connection list"); for (Spline = Splines; Spline != NULL; Spline = Spline->Next) { if (Spline->Nbr_Knots > 1) { for (j = 1, Knot = Spline->First; j < Spline->Nbr_Knots; j++, Knot = Knot->Next) { if (Is_Hidden(Points[Knot->Point_Id])) continue; if (Nbr_Connections >= Max_Nbr_Connections-2) { Display_Message("No more space for connections"); return(TRUE); } Connections[Nbr_Connections].From = Knot->Point_Id; Connections[Nbr_Connections].To = Knot->Next->Point_Id; Connections[Nbr_Connections].Spline = Spline; Connections[Nbr_Connections].Knot = Knot; Connections[Nbr_Connections].Dir = 1; Connections[Nbr_Connections++].Count = 0; Connections[Nbr_Connections].From = Knot->Next->Point_Id; Connections[Nbr_Connections].To = Knot->Point_Id; Connections[Nbr_Connections].Spline = Spline; Connections[Nbr_Connections].Knot = Knot; Connections[Nbr_Connections].Dir = -1; Connections[Nbr_Connections++].Count = 0; } /* for */ if (Spline->Loop & !Is_Hidden(Points[Knot->Point_Id])){ if (Nbr_Connections >= Max_Nbr_Connections-2) { Display_Message("No more space for connections"); return(TRUE); } Connections[Nbr_Connections].From = Knot->Point_Id; Connections[Nbr_Connections].To = Spline->First->Point_Id; Connections[Nbr_Connections].Spline = Spline; Connections[Nbr_Connections].Knot = Knot; Connections[Nbr_Connections].Dir = 1; Connections[Nbr_Connections++].Count = 0; Connections[Nbr_Connections].From = Spline->First->Point_Id; Connections[Nbr_Connections].To = Knot->Point_Id; Connections[Nbr_Connections].Spline = Spline; Connections[Nbr_Connections].Knot = Knot; Connections[Nbr_Connections].Dir = -1; Connections[Nbr_Connections++].Count = 0; } /* if */ } /* if */ } /* for */ /* Sort the connection list: */ sprintf(Error_Msg, "Sorting %d connections.", Nbr_Connections); Display_Status(Error_Msg); qsort((char *)Connections, Nbr_Connections, sizeof(Connection_T), CompareFunc); /* Find all two spline patches */ Patch_Count = 0; for (C1 = 0; C1 < Nbr_Connections; C1++) { P1 = Connections[C1].From; P2 = Connections[C1].To; if (Connections[C1].Count >= 2) continue; C2 = Find_From_To_Spline_Connection(Connections[C1].Spline, P2, P1); if (C2 != -1) { /* Won't accept both points on same spline */ if (Connections[C1].Spline == Connections[C2].Spline) continue; if (!Patch_Add(Connections[C1].From, Connections[C2].From, -1, -1)) { /* Found, C1, C2 */ sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count); Display_Status(Error_Msg); Tesselate_Patch(TI, C1, -1, C2, -1); Remove_Connection(C1); Remove_Connection(C2); } goto NextA; /* Stop loop */ } /* if */ NextA: ; } /* for */ /* Find all three spline patches */ for (C1 = 0; C1 < Nbr_Connections; C1++) { P1 = Connections[C1].From; P2 = Connections[C1].To; if (Connections[C1].Count >= 2) continue; C2 = Find_From_Connection(P2, P1); if (C2 == -1) goto NextB; do { P3 = Connections[C2].To; if (P3 == P1) continue; C3 = Find_From_To_Connection(P3, P1); if (C3 != -1) { /* We won't accept all three points on same spline */ if (Connections[C1].Spline == Connections[C2].Spline && Connections[C2].Spline == Connections[C3].Spline) continue; if (!Patch_Add(Connections[C1].From, Connections[C2].From, Connections[C3].From, -1)) { /* Found, C1, C2, C3 */ sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count); Display_Status(Error_Msg); Tesselate_Patch(TI, C1, C2, C3, -1); Remove_Connection(C1); Remove_Connection(C2); Remove_Connection(C3); } goto NextB; /* Stop loop */ } /* if */ } while (++C2 < Nbr_Connections && Connections[C2].From == P2); NextB: ; } /* for */ /* Find all four spline patches */ for (C1 = 0; C1 < Nbr_Connections; C1++) { P1 = Connections[C1].From; P2 = Connections[C1].To; if (Connections[C1].Count >= 2) continue; C2 = Find_From_Connection(P2, P1); if (C2 == -1) continue; do { P3 = Connections[C2].To; if (P3 == P1) continue; C3 = Find_From_Connection(P3, P2); if (C3 == -1) continue; do { P4 = Connections[C3].To; if (P4 == P2) continue; C4 = Find_From_To_Connection(P4, P1); if (C4 != -1) { /* We won't accept all four points on same spline */ if (Connections[C1].Spline == Connections[C2].Spline && Connections[C2].Spline == Connections[C3].Spline && Connections[C3].Spline == Connections[C4].Spline) continue; if (!Patch_Add(Connections[C1].From, Connections[C2].From, Connections[C3].From, Connections[C4].From)) { /* Found, C1, C2, C3, C4 */ sprintf(Error_Msg, "Tesselating patches (%d)", ++Patch_Count); Display_Status(Error_Msg); Tesselate_Patch(TI, C1, C2, C3, C4); Remove_Connection(C1); Remove_Connection(C2); Remove_Connection(C3); Remove_Connection(C4); } goto Next1; /* Stop loop */ } /* if */ } while (++C3 < Nbr_Connections && Connections[C3].From == P3); } while (++C2 < Nbr_Connections && Connections[C2].From == P2); Next1: ; } /* for */ if (Row0 != NULL) free(Row0); if (Row1 != NULL) free(Row1); if (Row2 != NULL) free(Row2); Row0 = Row1 = Row2 = NULL; Display_Status("Tesselation done"); return(FALSE); } /* Tesselate_Object */