ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/triangulate.c
(Generate patch)

Comparing ray/src/common/triangulate.c (file contents):
Revision 2.5 by greg, Thu Dec 22 18:50:48 2016 UTC vs.
Revision 2.6 by greg, Mon Apr 19 19:40:03 2021 UTC

# Line 34 | Line 34 | static const char RCSid[] = "$Id$";
34   #define false   0
35   #endif
36  
37 < static const double EPSILON = 0.0000000001;
37 > #define EPSILON         0.0000000001
38  
39   static int
40   polySnip(const Vert2_list *contour, int u, int v, int w, int n, int *V)
# Line 52 | Line 52 | polySnip(const Vert2_list *contour, int u, int v, int
52    Cy = contour->v[V[w]].mY;
53  
54    cross = ((Bx - Ax)*(Cy - Ay)) - ((By - Ay)*(Cx - Ax));
55 <  if (EPSILON > cross) return EPSILON > -cross ? -1 : false; /* Negative if colinear points */
55 >  if (cross < EPSILON)
56 >        return cross < -EPSILON ? -1 : false; /* Negative if colinear points */
57  
58    for (p=0;p<n;p++)
59    {
60      if( (p == u) | (p == v) | (p == w) ) continue;
61      Px = contour->v[V[p]].mX;
62      Py = contour->v[V[p]].mY;
63 <    if ((Px == Ax && Py == Ay) || (Px == Bx && Py == By) ||
64 <                (Px == Cx && Py == Cy)) continue; /* Handle donuts */
63 >    if ((Px == Ax) & (Py == Ay) || (Px == Bx) & (Py == By) ||
64 >                (Px == Cx) & (Py == Cy)) continue; /* Handle donuts */
65      if (insideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
66    }
67  
# Line 82 | Line 83 | polyAlloc(int nv)
83          return pnew;
84   }
85  
86 + /*
87 +  Area is positive if vertices listed counter-clockwise, negative if clockwise
88 + */
89   double
90   polyArea(const Vert2_list *contour)
91   {
# Line 104 | Line 108 | insideTriangle(double Ax, double Ay,
108                        double Bx, double By,
109                        double Cx, double Cy,
110                        double Px, double Py)
107 –
111   {
112    double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
113    double cCROSSap, bCROSScp, aCROSSbp;
# Line 120 | Line 123 | insideTriangle(double Ax, double Ay,
123    cCROSSap = cx*apy - cy*apx;
124    bCROSScp = bx*cpy - by*cpx;
125  
126 <  return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));
126 >  return ((aCROSSbp >= 0.0) & (bCROSScp >= 0.0) & (cCROSSap >= 0.0));
127   };
128  
129   int
# Line 128 | Line 131 | polyTriangulate(const Vert2_list *contour, tri_out_t *
131   {
132    /* allocate and initialize list of Vertices in polygon */
133  
134 <  int nv, m, u, v, w, count, result;
134 >  int nv, u, v, w, count, result;
135    int *V;
136  
137    if ( contour->nv < 3 ) return false;
# Line 138 | Line 141 | polyTriangulate(const Vert2_list *contour, tri_out_t *
141  
142    /* we want a counter-clockwise polygon in V */
143  
144 <  if ( 0.0 < polyArea(contour) )
144 >  if ( polyArea(contour) > 0.0 )
145      for (v=0; v<contour->nv; v++) V[v] = v;
146    else
147 <    for(v=0; v<contour->nv; v++) V[v] = (contour->nv-1)-v;
147 >    for (v=0; v<contour->nv; v++) V[v] = (contour->nv-1)-v;
148  
149    nv = contour->nv;
150  
151    /*  remove nv-2 Vertices, creating 1 triangle every time */
152    count = 2*nv;   /* error detection */
153  
154 <  for(m=0, v=nv-1; nv>2; )
154 >  v = nv-1;
155 >  while (nv > 2)
156    {
157      /* if we loop, it is probably a non-simple polygon */
158 <    if (0 >= count--)
158 >    if (count-- <= 0)
159      {
160        /* Triangulate: ERROR - probable bad polygon */
161 +      free(V);
162        return false;
163      }
164  
165      /* three consecutive vertices in current polygon, <u,v,w> */
166 <    u = v  ; if (nv <= u) u = 0;     /* previous */
167 <    v = u+1; if (nv <= v) v = 0;     /* new v    */
168 <    w = v+1; if (nv <= w) w = 0;     /* next     */
166 >    u = v  ; u *= (nv > u);     /* previous */
167 >    v = u+1; v *= (nv > v);     /* new v    */
168 >    w = v+1; w *= (nv > w);     /* next     */
169  
170      result = polySnip(contour, u, v, w, nv, V);
171      if (result > 0) /* successfully found a triangle */
172      {
168 –      int a,b,c;
169 –
170 –      /* true names of the vertices */
171 –      a = V[u]; b = V[v]; c = V[w];
172 –
173        /* output Triangle */
174 <      if (!(*cb)(contour, a, b, c)) return false;
175 <
176 <      m++;
174 >      if (!(*cb)(contour, V[u], V[v], V[w])) {
175 >        free(V);
176 >        return false;
177 >      }
178      }
179      if (result) /* successfully found a triangle or three consecutive colinear points */
180      {

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines