~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina6/tina-libs/tina/math/mathDraw_polygon.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  * 
  3  * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
  4  * University of Manchester, UK.  All rights reserved.
  5  * 
  6  * Redistribution and use in source and binary forms, with or without modification, 
  7  * are permitted provided that the following conditions are met:
  8  * 
  9  *   . Redistributions of source code must retain the above copyright notice, 
 10  *     this list of conditions and the following disclaimer.
 11  *    
 12  *   . Redistributions in binary form must reproduce the above copyright notice,
 13  *     this list of conditions and the following disclaimer in the documentation 
 14  *     and/or other materials provided with the distribution.
 15  * 
 16  *   . Neither the name of the University of Manchester nor the names of its
 17  *     contributors may be used to endorse or promote products derived from this 
 18  *     software without specific prior written permission.
 19  * 
 20  * 
 21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 31  * POSSIBILITY OF SUCH DAMAGE.
 32  *
 33  **********
 34  * 
 35  * Program :    TINA
 36  * File    :  $Source: /home/tina/cvs/tina-libs/tina/math/mathDraw_polygon.c,v $
 37  * Date    :  $Date: 2005/01/09 17:49:25 $
 38  * Version :  $Revision: 1.4 $
 39  * CVS Id  :  $Id: mathDraw_polygon.c,v 1.4 2005/01/09 17:49:25 paul Exp $
 40  *
 41  * Author  :  Legacy TINA
 42  *
 43  * Notes :
 44  * @(#)Concave polygon scan conversion. apply_inside_poly(): scan
 45  * convert nvert-sided concave non-simple polygon with vertices at p[i]
 46  * for i = [0..nvert-1] by calling func() for each visible span of
 47  * pixels; the polygon can be clockwise or counterclockwise. Algorithm
 48  * does uniform point sampling at pixel centres. Inside-outside test is
 49  * done by Jordan's rule: a point is considered to be inside if an
 50  * emanating ray intersects the polygon an odd number of times. func()
 51  * processes the data on line y from lx to ux inclusive.
 52  * 
 53  * Concave Polygon Scan Conversion, by Paul Heckbert; modified by Jim
 54  * Ivins. See Glassner (editor) 1990 "Graphics Gems" p 681 (Academic
 55  * Press)
 56  *
 57  *********
 58 */
 59 
 60 #include "mathDraw_polygon.h"
 61 
 62 #if HAVE_CONFIG_H
 63 #   include <config.h>
 64 #endif
 65 
 66 #include <math.h>
 67 #include <stdlib.h>
 68 #include <string.h>
 69 #include <tina/sys/sysPro.h>
 70 #include <tina/math/math_DrawDef.h>
 71 #include <tina/math/math_GeomDef.h>
 72 #include <tina/math/math_GeomPro.h>
 73 
 74 static Vec2 *pt = NULL;         /* Array of vertices. */
 75 static Poly_edge *active = NULL;/* Active edge list: edges crossing
 76                                  * scanline y. */
 77 
 78 
 79 
 80 static int compare_ind(const void *u, const void *v)
 81 {
 82     /* Changed by Julian Briggs 2/11/93 to match qsort */
 83     /**
 84       int     ind_u = vec2_y (pt[*(int*)u]);
 85       int     ind_v = vec2_y (pt[*(int*)v]);
 86       **/
 87     int     ind_u = (int) vec2_y(pt[*(int *) u]);
 88     int     ind_v = (int) vec2_y(pt[*(int *) v]);
 89 
 90     return (ind_u == ind_v) ? 0 : (ind_u < ind_v ? -1 : +1);
 91 }
 92 
 93 static int compare_active(const void *u, const void *v)
 94 {
 95     /* Changed by Julian Briggs 2/11/93 to match qsort */
 96     /* return (u->x <= v->x) ? -1 : +1; */
 97     return (((Poly_edge *) u)->x <= ((Poly_edge *) v)->x) ? -1 : +1;
 98 }
 99 
100 static void delete(int i, int *nact)
101 {
102     int     j;
103 
104     for (j = 0; active[j].i != i; j++)
105         if (j >= *nact)
106             return;
107     (*nact)--;
108     memcpy(&active[j], &active[j + 1], (*nact - j) * sizeof(active[0]));
109 }
110 
111 static void insert(int i, int y, int n, int *nact)
112 {
113     int     j;
114     double  dx;
115     Vec2   *p;
116     Vec2   *q;
117 
118     j = i < n - 1 ? i + 1 : 0;
119     if (vec2_x(pt[i]) < vec2_x(pt[j]))
120     {
121         p = &pt[i];
122         q = &pt[j];
123     } else
124     {
125         p = &pt[j];
126         q = &pt[i];
127     }
128 
129     active[*nact].dx = dx = (vec2_x(*q) - vec2_x(*p))
130         / (vec2_y(*q) - vec2_y(*p));
131     active[*nact].x = dx * (y + 0.5 - vec2_y(*p)) + vec2_x(*p);
132     active[*nact].i = i;
133     (*nact)++;
134 }
135 
136 void    apply_inside_poly(int nvert, Vec2 * p, int max_x, int max_y,
137                                   void (*func) (), void *data)
138 {
139     int     nact;               /* Number of active edges. */
140     int     k, ly, uy, y, i, j, lx, ux;
141     int    *ind;                /* Sorted list of vertex indices */
142 
143     pt = p;
144 
145     if ((nvert <= 0) || !p)
146         return;
147 
148     ind = tvector_alloc(0, nvert, int);
149     active = tvector_alloc(0, nvert, Poly_edge);
150 
151     /* Create a y-sorted array of indices ind[k] into ertex list */
152     for (k = 0; k < nvert; k++)
153         ind[k] = k;
154 
155     qsort(ind, nvert, sizeof(ind[0]), compare_ind);
156 
157     nact = 0;
158     k = 0;
159     /* BUGFIX Julian Briggs 1/11/93: ceil & floor take & return double */
160     ly = MAX(0, (int) ceil((double) vec2_y(pt[ind[0]]) - 0.5)); /* Polygon y min */
161     uy = MIN(max_y - 1,
162              (int) floor((double) vec2_y(pt[ind[nvert - 1]]) - 0.5));   /* Polygon y max */
163 
164     for (y = ly; y <= uy; y++)
165     {
166         for (; k < nvert && vec2_y(pt[ind[k]]) <= y + 0.5; k++)
167         {
168             i = ind[k];
169 
170             j = i > 0 ? i - 1 : nvert - 1;      /* Vertex before i */
171             if (vec2_y(pt[j]) <= y - 0.5)
172                 delete(j, &nact);
173             else if (vec2_y(pt[j]) > y + 0.5)
174                 insert(j, y, nvert, &nact);
175 
176             j = i < nvert - 1 ? i + 1 : 0;      /* Vertex after i */
177             if (vec2_y(pt[j]) <= y - 0.5)
178                 delete(i, &nact);
179             else if (vec2_y(pt[j]) > y + 0.5)
180                 insert(i, y, nvert, &nact);
181         }
182 
183         qsort(active, nact, sizeof(active[0]), compare_active);
184 
185         /* Draw horizontal segments for scanline y. Span between j and
186          * j+1 is inside polygon. Span between j+1 and j+2 is outside
187          * polygon. */
188         for (j = 0; j < nact; j += 2)
189         {
190             lx = (int) ceil(active[j].x - 0.5); /* Left end of span */
191             if (lx < 0)
192                 lx = 0;
193 
194             ux = (int) floor(active[j + 1].x - 0.5);    /* Right end of span */
195             if (ux >= max_x)
196                 ux = max_x - 1;
197 
198             (*func) (y, lx, ux, data);
199 
200             active[j].x += active[j].dx;
201             active[j + 1].x += active[j + 1].dx;
202         }
203     }
204     tvector_free(ind, 0, int);
205     tvector_free(active, 0, Poly_edge);
206 }
207 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.