SMIL  0.9.1
DImageDraw.h
1 /*
2  * Copyright (c) 2011-2016, Matthieu FAESSEL and ARMINES
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * * Neither the name of Matthieu FAESSEL, or ARMINES nor the
14  * names of its contributors may be used to endorse or promote products
15  * derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 
30 #ifndef _D_IMAGE_DRAW_H
31 #define _D_IMAGE_DRAW_H
32 
33 #include <vector>
34 #include <algorithm>
35 
36 #include "Core/include/DCommon.h"
37 
38 namespace smil
39 {
40 
47  inline std::vector<IntPoint> bresenhamPoints(int p1x, int p1y, int p2x, int p2y, int xMax=0, int yMax=0)
48  {
49  vector<IntPoint> points;
50  int F, x, y;
51 
52  bool swapped = false;
53  if (p1x > p2x) // Swap points if p1 is on the right of p2
54  {
55  swap(p1x, p2x);
56  swap(p1y, p2y);
57  swapped = true;
58  }
59 
60  // Handle trivial cases separately for algorithm speed up.
61  // Trivial case 1: m = +/-INF (Vertical line)
62  if (p1x == p2x)
63  {
64  if (p1y > p2y) // Swap y-coordinates if p1 is above p2
65  {
66  swap(p1y, p2y);
67  }
68 
69  x = p1x;
70  y = p1y;
71  if (!xMax || (x>=0 && x<xMax))
72  while (y <= p2y)
73  {
74  points.push_back(IntPoint(x,y,0));
75  y++;
76  }
77  return points;
78  }
79  // Trivial case 2: m = 0 (Horizontal line)
80  else if (p1y == p2y)
81  {
82  x = p1x;
83  y = p1y;
84 
85  if (!yMax || (y>=0 && y<yMax))
86  while (x <= p2x)
87  {
88  points.push_back(IntPoint(x,y,0));
89  x++;
90  }
91  return points;
92  }
93 
94 
95  int dy = p2y - p1y; // y-increment from p1 to p2
96  int dx = p2x - p1x; // x-increment from p1 to p2
97  int dy2 = (dy << 1); // dy << 1 == 2*dy
98  int dx2 = (dx << 1);
99  int dy2_minus_dx2 = dy2 - dx2; // precompute constant for speed up
100  int dy2_plus_dx2 = dy2 + dx2;
101 
102 
103  if (dy >= 0) // m >= 0
104  {
105  // Case 1: 0 <= m <= 1 (Original case)
106  if (dy <= dx)
107  {
108  F = dy2 - dx; // initial F
109 
110  x = p1x;
111  y = p1y;
112  while (x <= p2x)
113  {
114  if (!xMax || (x>=0 && x<xMax && y>=0 && y<yMax))
115  points.push_back(IntPoint(x,y,0));
116  if (F <= 0)
117  {
118  F += dy2;
119  }
120  else
121  {
122  y++;
123  F += dy2_minus_dx2;
124  }
125  x++;
126  }
127  }
128  // Case 2: 1 < m < INF (Mirror about y=x line
129  // replace all dy by dx and dx by dy)
130  else
131  {
132  F = dx2 - dy; // initial F
133 
134  y = p1y;
135  x = p1x;
136  while (y <= p2y)
137  {
138  if (!xMax || (x>=0 && x<xMax && y>=0 && y<yMax))
139  points.push_back(IntPoint(x,y,0));
140  if (F <= 0)
141  {
142  F += dx2;
143  }
144  else
145  {
146  x++;
147  F -= dy2_minus_dx2;
148  }
149  y++;
150  }
151  }
152  }
153  else // m < 0
154  {
155  // Case 3: -1 <= m < 0 (Mirror about x-axis, replace all dy by -dy)
156  if (dx >= -dy)
157  {
158  F = -dy2 - dx; // initial F
159 
160  x = p1x;
161  y = p1y;
162  while (x <= p2x)
163  {
164  if (!xMax || (x>=0 && x<xMax && y>=0 && y<yMax))
165  points.push_back(IntPoint(x,y,0));
166  if (F <= 0)
167  {
168  F -= dy2;
169  }
170  else
171  {
172  y--;
173  F -= dy2_plus_dx2;
174  }
175  x++;
176  }
177  }
178  // Case 4: -INF < m < -1 (Mirror about x-axis and mirror
179  // about y=x line, replace all dx by -dy and dy by dx)
180  else
181  {
182  F = dx2 + dy; // initial F
183 
184  y = p1y;
185  x = p1x;
186  while (y >= p2y)
187  {
188  if (!xMax || (x>=0 && x<xMax && y>=0 && y<yMax))
189  points.push_back(IntPoint(x,y,0));
190  if (F <= 0)
191  {
192  F += dx2;
193  }
194  else
195  {
196  x++;
197  F += dy2_plus_dx2;
198  }
199  y--;
200  }
201  }
202  }
203  // If input points have been swapped, reverse the vector
204  if (swapped)
205  std::reverse(points.begin(), points.end());
206  return points;
207  }
208 
211 } // namespace smil
212 
213 
214 #endif // _D_IMAGE_DRAW_HPP
215 
Definition: DColorConvert.h:38