← Back to branch summary

~brandontschaefer/+junk/break-x

« back to all changes in this revision

Viewing changes to mi/miscanfill.h

  • Committer: Brandon Schaefer
  • Date: 2014-09-30 19:38:40 UTC
  • Revision ID: brandon.schaefer@canonical.com-20140930193840-a65z6qk8ze02cgsb
* Init commit to back this up

Show diffs side-by-side

added added

removed removed

Lines of Context:
mi/miscanfill.h
 
1
/*
 
2
 
 
3
Copyright 1987, 1998  The Open Group
 
4
 
 
5
Permission to use, copy, modify, distribute, and sell this software and its
 
6
documentation for any purpose is hereby granted without fee, provided that
 
7
the above copyright notice appear in all copies and that both that
 
8
copyright notice and this permission notice appear in supporting
 
9
documentation.
 
10
 
 
11
The above copyright notice and this permission notice shall be included
 
12
in all copies or substantial portions of the Software.
 
13
 
 
14
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 
15
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 
16
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 
17
IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
 
18
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 
19
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 
20
OTHER DEALINGS IN THE SOFTWARE.
 
21
 
 
22
Except as contained in this notice, the name of The Open Group shall
 
23
not be used in advertising or otherwise to promote the sale, use or
 
24
other dealings in this Software without prior written authorization
 
25
from The Open Group.
 
26
 
 
27
*/
 
28
 
 
29
#ifdef HAVE_DIX_CONFIG_H
 
30
#include <dix-config.h>
 
31
#endif
 
32
 
 
33
#ifndef SCANFILLINCLUDED
 
34
#define SCANFILLINCLUDED
 
35
/*
 
36
 *     scanfill.h
 
37
 *
 
38
 *     Written by Brian Kelleher; Jan 1985
 
39
 *
 
40
 *     This file contains a few macros to help track
 
41
 *     the edge of a filled object.  The object is assumed
 
42
 *     to be filled in scanline order, and thus the
 
43
 *     algorithm used is an extension of Bresenham's line
 
44
 *     drawing algorithm which assumes that y is always the
 
45
 *     major axis.
 
46
 *     Since these pieces of code are the same for any filled shape,
 
47
 *     it is more convenient to gather the library in one
 
48
 *     place, but since these pieces of code are also in
 
49
 *     the inner loops of output primitives, procedure call
 
50
 *     overhead is out of the question.
 
51
 *     See the author for a derivation if needed.
 
52
 */
 
53
 
 
54
/*
 
55
 *  In scan converting polygons, we want to choose those pixels
 
56
 *  which are inside the polygon.  Thus, we add .5 to the starting
 
57
 *  x coordinate for both left and right edges.  Now we choose the
 
58
 *  first pixel which is inside the pgon for the left edge and the
 
59
 *  first pixel which is outside the pgon for the right edge.
 
60
 *  Draw the left pixel, but not the right.
 
61
 *
 
62
 *  How to add .5 to the starting x coordinate:
 
63
 *      If the edge is moving to the right, then subtract dy from the
 
64
 *  error term from the general form of the algorithm.
 
65
 *      If the edge is moving to the left, then add dy to the error term.
 
66
 *
 
67
 *  The reason for the difference between edges moving to the left
 
68
 *  and edges moving to the right is simple:  If an edge is moving
 
69
 *  to the right, then we want the algorithm to flip immediately.
 
70
 *  If it is moving to the left, then we don't want it to flip until
 
71
 *  we traverse an entire pixel.
 
72
 */
 
73
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
 
74
    int dx;      /* local storage */ \
 
75
\
 
76
    /* \
 
77
     *  if the edge is horizontal, then it is ignored \
 
78
     *  and assumed not to be processed.  Otherwise, do this stuff. \
 
79
     */ \
 
80
    if ((dy) != 0) { \
 
81
        xStart = (x1); \
 
82
        dx = (x2) - xStart; \
 
83
        if (dx < 0) { \
 
84
            m = dx / (dy); \
 
85
            m1 = m - 1; \
 
86
            incr1 = -2 * dx + 2 * (dy) * m1; \
 
87
            incr2 = -2 * dx + 2 * (dy) * m; \
 
88
            d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
 
89
        } else { \
 
90
            m = dx / (dy); \
 
91
            m1 = m + 1; \
 
92
            incr1 = 2 * dx - 2 * (dy) * m1; \
 
93
            incr2 = 2 * dx - 2 * (dy) * m; \
 
94
            d = -2 * m * (dy) + 2 * dx; \
 
95
        } \
 
96
    } \
 
97
}
 
98
 
 
99
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
 
100
    if (m1 > 0) { \
 
101
        if (d > 0) { \
 
102
            minval += m1; \
 
103
            d += incr1; \
 
104
        } \
 
105
        else { \
 
106
            minval += m; \
 
107
            d += incr2; \
 
108
        } \
 
109
    } else {\
 
110
        if (d >= 0) { \
 
111
            minval += m1; \
 
112
            d += incr1; \
 
113
        } \
 
114
        else { \
 
115
            minval += m; \
 
116
            d += incr2; \
 
117
        } \
 
118
    } \
 
119
}
 
120
 
 
121
/*
 
122
 *     This structure contains all of the information needed
 
123
 *     to run the bresenham algorithm.
 
124
 *     The variables may be hardcoded into the declarations
 
125
 *     instead of using this structure to make use of
 
126
 *     register declarations.
 
127
 */
 
128
typedef struct {
 
129
    int minor;                  /* minor axis        */
 
130
    int d;                      /* decision variable */
 
131
    int m, m1;                  /* slope and slope+1 */
 
132
    int incr1, incr2;           /* error increments */
 
133
} BRESINFO;
 
134
 
 
135
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
 
136
        BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \
 
137
                     bres.m, bres.m1, bres.incr1, bres.incr2)
 
138
 
 
139
#define BRESINCRPGONSTRUCT(bres) \
 
140
        BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2)
 
141
 
 
142
#endif