PrimitivesDrawer.cpp
Go to the documentation of this file.
1 // ****************************************************************************
2 // This file is part of the Integrating Vision Toolkit (IVT).
3 //
4 // The IVT is maintained by the Karlsruhe Institute of Technology (KIT)
5 // (www.kit.edu) in cooperation with the company Keyetech (www.keyetech.de).
6 //
7 // Copyright (C) 2014 Karlsruhe Institute of Technology (KIT).
8 // All rights reserved.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are met:
12 //
13 // 1. Redistributions of source code must retain the above copyright
14 // notice, this list of conditions and the following disclaimer.
15 //
16 // 2. Redistributions in binary form must reproduce the above copyright
17 // notice, this list of conditions and the following disclaimer in the
18 // documentation and/or other materials provided with the distribution.
19 //
20 // 3. Neither the name of the KIT nor the names of its contributors may be
21 // used to endorse or promote products derived from this software
22 // without specific prior written permission.
23 //
24 // THIS SOFTWARE IS PROVIDED BY THE KIT AND CONTRIBUTORS “AS IS” AND ANY
25 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 // DISCLAIMED. IN NO EVENT SHALL THE KIT OR CONTRIBUTORS BE LIABLE FOR ANY
28 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 // ****************************************************************************
35 // ****************************************************************************
36 // Filename: PrimitivesDrawer.cpp
37 // Author: Pedram Azad
38 // Date: 2005
39 // ****************************************************************************
40 // Changes: 03.03.2010, Derick Beng Youh
41 // * Added function FillPolygon
42 // ****************************************************************************
43 
44 // ****************************************************************************
45 // Includes
46 // ****************************************************************************
47 
48 #include <new> // for explicitly using correct new/delete operators on VC DSPs
49 
50 // IVT
51 #include "PrimitivesDrawer.h"
52 #include "Image/ByteImage.h"
53 #include "Math/Math2d.h"
54 #include "Structs/Structs.h"
55 #include "Helpers/helpers.h"
56 
57 // system
58 #include <math.h>
59 #include <limits>
60 
61 
62 
63 // ****************************************************************************
64 // Helper functions
65 // ****************************************************************************
66 
67 static bool is_indeterminate(const float fValue)
68 {
69  return fValue != fValue;
70 }
71 
72 static bool is_infinite(const float fValue)
73 {
74  return fabsf(fValue) == std::numeric_limits<float>::infinity();
75 }
76 
77 
78 // ****************************************************************************
79 // Functions
80 // ****************************************************************************
81 
82 void PrimitivesDrawer::DrawPoint(CByteImage *pImage, const Vec2d &point, int r, int g, int b)
83 {
84  DrawPoint(pImage, int(point.x + 0.5f), int(point.y + 0.5f), r, g, b);
85 }
86 
87 void PrimitivesDrawer::DrawPoint(CByteImage *pImage, int x, int y, int r, int g, int b)
88 {
89  const int width = pImage->width;
90  const int height = pImage->height;
91  const int nPixels = width * height;
92 
93  if (x < 0 || x >= width || y < 0 || y >= height)
94  return;
95 
96  if (pImage->type == CByteImage::eGrayScale)
97  {
98  pImage->pixels[y * width + x] = (r + (g << 1) + b) >> 2;
99  }
100  else if (pImage->type == CByteImage::eRGB24)
101  {
102  const int offset = 3 * (y * width + x);
103  pImage->pixels[offset] = r;
104  pImage->pixels[offset + 1] = g;
105  pImage->pixels[offset + 2] = b;
106  }
107  else if (pImage->type == CByteImage::eRGB24Split)
108  {
109  const int offset = y * width + x;
110  pImage->pixels[offset] = r;
111  pImage->pixels[offset + nPixels] = g;
112  pImage->pixels[offset + (nPixels << 1)] = b;
113  }
114 }
115 
116 void PrimitivesDrawer::DrawPointBlended(CByteImage *pImage, const Vec2d &point, int r, int g, int b, float blend)
117 {
118  DrawPointBlended(pImage, int(point.x + 0.5f), int(point.y + 0.5f), r, g, b, blend);
119 }
120 
121 void PrimitivesDrawer::DrawPointBlended(CByteImage *pImage, int x, int y, int r, int g, int b, float blend)
122 {
123  const int width = pImage->width;
124  const int height = pImage->height;
125  const int nPixels = width * height;
126 
127  if (x < 0 || x >= width || y < 0 || y >= height)
128  return;
129 
130  if (pImage->type == CByteImage::eGrayScale)
131  {
132  const float o = (float) pImage->pixels[y * width + x];
133  const float n = (float) ((r + (g << 1) + b + 1) >> 2);
134 
135  pImage->pixels[y * width + x] = (int) ((1.0f - blend) * o + blend * n);
136  }
137  else if (pImage->type == CByteImage::eRGB24)
138  {
139  const int offset = 3 * (y * width + x);
140  int ro = pImage->pixels[offset];
141  int go = pImage->pixels[offset + 1];
142  int bo = pImage->pixels[offset + 2];
143 
144  r = (int) ((1.0f - blend) * (float) ro + blend * (float) r);
145  g = (int) ((1.0f - blend) * (float) go + blend * (float) g);
146  b = (int) ((1.0f - blend) * (float) bo + blend * (float) b);
147 
148  pImage->pixels[offset] = r;
149  pImage->pixels[offset + 1] = g;
150  pImage->pixels[offset + 2] = b;
151  }
152  else if (pImage->type == CByteImage::eRGB24Split)
153  {
154  const int offset = y * width + x;
155 
156  int ro = pImage->pixels[offset];
157  int go = pImage->pixels[offset + nPixels];
158  int bo = pImage->pixels[offset + (nPixels << 1)];
159 
160  r = (int) ((1.0f - blend) * (float) ro + blend * (float) r);
161  g = (int) ((1.0f - blend) * (float) go + blend * (float) g);
162  b = (int) ((1.0f - blend) * (float) bo + blend * (float) b);
163 
164  pImage->pixels[offset] = r;
165  pImage->pixels[offset + nPixels] = g;
166  pImage->pixels[offset + (nPixels << 1)] = b;
167  }
168 }
169 
170 void PrimitivesDrawer::DrawPoints(CByteImage *pImage, const CVec2dArray &points, int r, int g, int b)
171 {
172  const int nPoints = points.GetSize();
173 
174  for (int i = 0; i < nPoints; i++)
175  DrawPoint(pImage, points[i], r, g, b);
176 }
177 
178 
179 void PrimitivesDrawer::DrawRegion(CByteImage *pImage, const MyRegion &region, int r, int g, int b, int thickness)
180 {
181  if (thickness == -1)
182  {
183  for (int y = region.min_y; y <= region.max_y; y++)
184  for (int x = region.min_x; x <= region.max_x; x++)
185  DrawPoint(pImage, x, y, r, g, b);
186  }
187  else
188  {
189  const Vec2d p1 = { float(region.min_x), float(region.min_y) };
190  const Vec2d p2 = { float(region.max_x), float(region.min_y) };
191  const Vec2d p3 = { float(region.max_x), float(region.max_y) };
192  const Vec2d p4 = { float(region.min_x), float(region.max_y) };
193 
194  DrawLine(pImage, p1, p2, r, g, b, thickness);
195  DrawLine(pImage, p2, p3, r, g, b, thickness);
196  DrawLine(pImage, p3, p4, r, g, b, thickness);
197  DrawLine(pImage, p4, p1, r, g, b, thickness);
198  }
199 }
200 
201 void PrimitivesDrawer::DrawLine(CByteImage *pImage, const Vec2d &p1, const Vec2d &p2, int r, int g, int b, int thickness)
202 {
204  return;
205 
206  if (is_infinite(p1.x) || is_infinite(p1.y) || is_infinite(p2.x) || is_infinite(p2.y))
207  return;
208 
209  const float dx = p1.x - p2.x;
210  const float dy = p1.y - p2.y;
211 
212  if (thickness == 1)
213  {
214  if (fabsf(dx) < 0.01f && fabsf(dy) < 0.01f)
215  {
216  PrimitivesDrawer::DrawPoint(pImage, p1, r, g, b);
217  }
218  else if (fabsf(dy) < fabsf(dx))
219  {
220  const float slope = dy / dx;
221  const int max_x = int(p2.x + 0.5f);
222  float y = p1.y + 0.5f;
223 
224  if (p1.x < p2.x)
225  {
226  for (int x = int(p1.x + 0.5f); x <= max_x; x++, y += slope)
227  PrimitivesDrawer::DrawPoint(pImage, x, int(y), r, g, b);
228  }
229  else
230  {
231  for (int x = int(p1.x + 0.5f); x >= max_x; x--, y -= slope)
232  PrimitivesDrawer::DrawPoint(pImage, x, int(y), r, g, b);
233  }
234  }
235  else
236  {
237  const float slope = dx / dy;
238  const int max_y = int(p2.y + 0.5f);
239  float x = p1.x + 0.5f;
240 
241  if (p1.y < p2.y)
242  {
243  for (int y = int(p1.y + 0.5f); y <= max_y; y++, x += slope)
244  PrimitivesDrawer::DrawPoint(pImage, int(x), y, r, g, b);
245  }
246  else
247  {
248  for (int y = int(p1.y + 0.5f); y >= max_y; y--, x -= slope)
249  PrimitivesDrawer::DrawPoint(pImage, int(x), y, r, g, b);
250  }
251  }
252  }
253  else
254  {
255  const float radius = 0.5f * thickness;
256 
257  if (fabsf(dx) < 0.01f && fabsf(dy) < 0.01f)
258  {
259  PrimitivesDrawer::DrawCircle(pImage, p1, radius, r, g, b, -1);
260  }
261  else if (fabsf(dy) < fabsf(dx))
262  {
263  const float slope = dy / dx;
264  const int max_x = int(p2.x + 0.5f);
265  float y = p1.y + 0.5f;
266 
267  if (p1.x < p2.x)
268  {
269  for (int x = int(p1.x + 0.5f); x <= max_x; x++, y += slope)
270  PrimitivesDrawer::DrawCircle(pImage, float(x), floor(y), radius, r, g, b, -1);
271  }
272  else
273  {
274  for (int x = int(p1.x + 0.5f); x >= max_x; x--, y -= slope)
275  PrimitivesDrawer::DrawCircle(pImage, float(x), floor(y), radius, r, g, b, -1);
276  }
277  }
278  else
279  {
280  const float slope = dx / dy;
281  const int max_y = int(p2.y + 0.5f);
282  float x = p1.x + 0.5f;
283 
284  if (p1.y < p2.y)
285  {
286  for (int y = int(p1.y + 0.5f); y <= max_y; y++, x += slope)
287  PrimitivesDrawer::DrawCircle(pImage, floor(x), float(y), radius, r, g, b, -1);
288  }
289  else
290  {
291  for (int y = int(p1.y + 0.5f); y >= max_y; y--, x -= slope)
292  PrimitivesDrawer::DrawCircle(pImage, floor(x), float(y), radius, r, g, b, -1);
293  }
294  }
295  }
296 }
297 
298 void PrimitivesDrawer::DrawLine(CByteImage *pImage, const PointPair2d &line, int r, int g, int b, int thickness)
299 {
300  DrawLine(pImage, line.p1, line.p2, r, g, b, thickness);
301 }
302 
303 void DrawCircleAA(CByteImage *pImage, float mx, float my, float radius, int r, int g, int b, int thickness)
304 {
305  const int min_x = int(mx - radius);
306  const int min_y = int(my - radius);
307  const int max_x = int(mx + radius);
308  const int max_y = int(my + radius);
309  int i;
310 
311  const float r2 = radius * radius;
312 
313  if (thickness == -1)
314  {
315  for (i = min_y; i <= max_y; i++)
316  {
317  const float d = r2 - (my - (float)i) * (my - (float)i);
318 
319  if (d >= 0)
320  {
321  const float x = sqrtf((float)d);
322 
323  int sx = (int)ceil(mx - x);
324  int ex = (int)floor(mx + x);
325 
326  float sb = (float)sx - (mx - x);
327  float eb = (mx + x) - (float)ex;
328 
329  PrimitivesDrawer::DrawPointBlended(pImage, sx, i, r, g, b, sb);
330 
331  for (int j = sx+1; j <= ex-1; j++)
332  PrimitivesDrawer::DrawPoint(pImage, j, i, r, g, b);
333 
334  PrimitivesDrawer::DrawPointBlended(pImage, ex, i, r, g, b, eb);
335  }
336  }
337  }
338  else
339  {
340  if (thickness == 1)
341  {
342  for (i = min_y; i <= max_y; i++)
343  {
344  const float d = r2 - (my - (float)i) * (my - (float)i);
345 
346  if (d >= 0)
347  {
348  const float x = sqrtf(d);
349 
350  int sx = (int)ceil(mx - x);
351  int ex = (int)floor(mx + x);
352 
353  float sb = (float)sx - (mx - x);
354  float eb = (mx + x) - (float)ex;
355 
356  PrimitivesDrawer::DrawPointBlended(pImage, sx-1, i, r, g, b, sb);
357  PrimitivesDrawer::DrawPointBlended(pImage, sx, i, r, g, b, 1.0f - sb);
358 
359  PrimitivesDrawer::DrawPointBlended(pImage, ex, i, r, g, b, 1.0f - eb);
360  PrimitivesDrawer::DrawPointBlended(pImage, ex+1, i, r, g, b, eb);
361  }
362  }
363 
364  for (i = min_x; i <= max_x; i++)
365  {
366  const float d = r2 - (mx - (float)i) * (mx - (float)i);
367 
368  if (d >= 0)
369  {
370  const float y = sqrtf(d);
371 
372  int sy = (int)ceil(my - y);
373  int ey = (int)floor(my + y);
374 
375  float sb = (float)sy - (my - y);
376  float eb = (my + y) - (float)ey;
377 
378  PrimitivesDrawer::DrawPointBlended(pImage, i, sy-1, r, g, b, sb);
379  PrimitivesDrawer::DrawPointBlended(pImage, i, sy, r, g, b, 1.0f - sb);
380 
381  PrimitivesDrawer::DrawPointBlended(pImage, i, ey, r, g, b, 1.0f - eb);
382  PrimitivesDrawer::DrawPointBlended(pImage, i, ey+1, r, g, b, eb);
383  }
384  }
385  }
386  else
387  {
388  const float radius = 0.5f * (float)thickness;
389 
390  for (i = min_x; i <= max_x; i++)
391  {
392  const float d = r2 - (mx - i) * (mx - i);
393 
394  if (d >= 0.0f)
395  {
396  const float y = sqrtf(d);
397  DrawCircleAA(pImage, float(i), floor(my + y), radius, r, g, b, -1);
398  DrawCircleAA(pImage, float(i), floor(my - y), radius, r, g, b, -1);
399  }
400  }
401 
402  for (i = min_y; i <= max_y; i++)
403  {
404  const float d = r2 - (my - i) * (my - i);
405 
406  if (d >= 0.0f)
407  {
408  const float x = sqrtf(d);
409  DrawCircleAA(pImage, floor(mx + x), float(i), radius, r, g, b, -1);
410  DrawCircleAA(pImage, floor(mx - x), float(i), radius, r, g, b, -1);
411  }
412  }
413  }
414  }
415 }
416 
417 void PrimitivesDrawer::DrawCircle(CByteImage *pImage, float mx, float my, float radius, int r, int g, int b, int thickness, bool antiAlias)
418 {
419  if (antiAlias)
420  {
421  DrawCircleAA(pImage, mx, my, radius, r, g, b, thickness);
422  return;
423  }
424 
425  const int mx_int = my_round(mx);
426  const int my_int = my_round(my);
427  const int radius_int = my_round(radius);
428 
429  mx = float(mx_int);
430  my = float(my_int);
431 
432  const int min_x = mx_int - radius_int;
433  const int min_y = my_int - radius_int;
434  const int max_x = mx_int + radius_int;
435  const int max_y = my_int + radius_int;
436 
437  const int r2 = radius_int * radius_int;
438 
439  if (thickness == -1)
440  {
441  int i;
442 
443  for (i = min_y; i <= max_y; i++)
444  {
445  const int d = r2 - (my_int - i) * (my_int - i);
446 
447  if (d >= 0)
448  {
449  const int x = int(sqrtf(float(d)) + 0.5f);
450 
451  const int sx = mx_int - x;
452  const int ex = mx_int + x;
453 
454  for (int j = sx; j <= ex; j++)
455  PrimitivesDrawer::DrawPoint(pImage, j, i, r, g, b);
456  }
457  }
458 
459  for (i = min_x; i <= max_x; i++)
460  {
461  const int d = r2 - (mx_int - i) * (mx_int - i);
462 
463  if (d >= 0)
464  {
465  const int y = int(sqrtf(float(d)) + 0.5f);
466 
467  PrimitivesDrawer::DrawPoint(pImage, i, my_int - y, r, g, b);
468  PrimitivesDrawer::DrawPoint(pImage, i, my_int + y, r, g, b);
469  }
470  }
471  }
472  else
473  {
474  if (thickness == 1)
475  {
476  int i;
477 
478  for (i = min_y; i <= max_y; i++)
479  {
480  const int d = r2 - (my_int - i) * (my_int - i);
481 
482  if (d >= 0)
483  {
484  const int x = int(sqrtf(float(d)) + 0.5f);
485 
486  PrimitivesDrawer::DrawPoint(pImage, mx_int - x, i, r, g, b);
487  PrimitivesDrawer::DrawPoint(pImage, mx_int + x, i, r, g, b);
488  }
489  }
490 
491  for (i = min_x; i <= max_x; i++)
492  {
493  const int d = r2 - (mx_int - i) * (mx_int - i);
494 
495  if (d >= 0)
496  {
497  const int y = int(sqrtf(float(d)) + 0.5f);
498 
499  PrimitivesDrawer::DrawPoint(pImage, i, my_int - y, r, g, b);
500  PrimitivesDrawer::DrawPoint(pImage, i, my_int + y, r, g, b);
501  }
502  }
503  }
504  else
505  {
506  const float fThicknessRadius = 0.5f * thickness;
507 
508  int i;
509 
510  for (i = min_x; i <= max_x; i++)
511  {
512  const int d = r2 - (mx_int - i) * (mx_int - i);
513 
514  if (d >= 0)
515  {
516  const int y = int(sqrtf(float(d)) + 0.5f);
517 
518  PrimitivesDrawer::DrawCircle(pImage, float(i), float(my_int - y), fThicknessRadius, r, g, b, -1);
519  PrimitivesDrawer::DrawCircle(pImage, float(i), float(my_int + y), fThicknessRadius, r, g, b, -1);
520  }
521  }
522 
523  for (i = min_y; i <= max_y; i++)
524  {
525  const int d = r2 - (my_int - i) * (my_int - i);
526 
527  if (d >= 0)
528  {
529  const int x = int(sqrtf(float(d)) + 0.5f);
530 
531  PrimitivesDrawer::DrawCircle(pImage, float(mx_int - x), float(i), fThicknessRadius, r, g, b, -1);
532  PrimitivesDrawer::DrawCircle(pImage, float(mx_int + x), float(i), fThicknessRadius, r, g, b, -1);
533  }
534  }
535  }
536  }
537 }
538 
539 void PrimitivesDrawer::DrawCircle(CByteImage *pImage, const Vec2d &center, float radius, int r, int g, int b, int thickness, bool antiAlias)
540 {
541  DrawCircle(pImage, center.x, center.y, radius, r, g, b, thickness, antiAlias);
542 }
543 
544 void PrimitivesDrawer::DrawCircle(CByteImage *pImage, const Circle2d &circle, int r, int g, int b, int thickness, bool antiAlias)
545 {
546  DrawCircle(pImage, circle.center.x, circle.center.y, circle.radius, r, g, b, thickness, antiAlias);
547 }
548 
549 void PrimitivesDrawer::DrawLineNormal(CByteImage *pImage, float nx, float ny, float c, int r, int g, int b, int thickness)
550 {
551  if (thickness == 1)
552  {
553  if (fabsf(nx) > fabsf(ny))
554  {
555  const float m = -ny / nx;
556  const float cc = -c / nx;
557 
558  for (int y = 0; y < pImage->height; y++)
559  {
560  Vec2d p = { floor(m * y + cc + 0.5f), float(y) };
561  PrimitivesDrawer::DrawPoint(pImage, p, r, g, b);
562  }
563  }
564  else
565  {
566  const float m = -nx / ny;
567  const float cc = -c / ny;
568 
569  for (int x = 0; x < pImage->width; x++)
570  {
571  Vec2d p = { float(x), floor(m * x + cc + 0.5f) };
572  PrimitivesDrawer::DrawPoint(pImage, p, r, g, b);
573  }
574  }
575  }
576  else
577  {
578  const float radius = 0.5f * thickness;
579 
580  if (fabsf(nx) > fabsf(ny))
581  {
582  const float m = -ny / nx;
583  const float cc = -c / nx;
584 
585  for (int y = 0; y < pImage->height; y++)
586  {
587  Vec2d p = { floor(m * y + cc + 0.5f), float(y) };
588  PrimitivesDrawer::DrawCircle(pImage, p, radius, r, g, b);
589  }
590  }
591  else
592  {
593  const float m = -nx / ny;
594  const float cc = -c / ny;
595 
596  for (int x = 0; x < pImage->width; x++)
597  {
598  Vec2d p = { float(x), floor(m * x + cc + 0.5f) };
599  PrimitivesDrawer::DrawCircle(pImage, p, radius, r, g, b);
600  }
601  }
602  }
603 }
604 
605 void PrimitivesDrawer::DrawLinePolar(CByteImage *pImage, float theta, float r, int color_r, int color_g, int color_b, int thickness)
606 {
607  DrawLineNormal(pImage, cosf(theta), sinf(theta), -r, color_r, color_g, color_b, thickness);
608 }
609 
610 void PrimitivesDrawer::DrawLine(CByteImage *pImage, const StraightLine2d &line, int r, int g, int b, int thickness)
611 {
612  DrawLineNormal(pImage, line.normalVector.x, line.normalVector.y, line.c, r, g, b, thickness);
613 }
614 
615 void PrimitivesDrawer::DrawCross(CByteImage *pImage, const Vec2d &point, int length, int r, int g, int b)
616 {
617  const int x = int(point.x + 0.5f);
618  const int y = int(point.y + 0.5f);
619 
620  const int l = length / 2;
621 
622  for (int i = -l; i <= l; i++)
623  {
624  PrimitivesDrawer::DrawPoint(pImage, x + i, y, r, g, b);
625  PrimitivesDrawer::DrawPoint(pImage, x, y + i, r, g, b);
626  }
627 }
628 
629 
630 
631 
632 struct Edge
633 {
635  {
636  next = 0;
637  }
638 
639  // maximum y-coordinate between p1 and p2
640  int max_y;
641 
642  // point of intersection between an edge and a scanline
644 
645  // inverse of the gradient of an edge dx / dy
647 
648  // the next edge in the linked list
650 };
651 
652 struct Vec2dInt
653 {
654  int x;
655  int y;
656 };
657 
658 static void InsertEdge(Edge *ppEdgeList, Edge *pEdge)
659 {
660  // inserts edge into linked list in order of increasing x_intersection field
661  Edge *q = ppEdgeList;
662  Edge *p = q->next;
663 
664  while (p)
665  {
666  if (pEdge->x_intersection < p->x_intersection)
667  break;
668 
669  q = p;
670  p = p->next;
671  }
672 
673  pEdge->next = q->next;
674  q->next = pEdge;
675 }
676 
677 // ****************************************************************************
678 // Store lower-y coordinate and inverse slope for each edge.
679 // Adjust and store max_y coordinate for edges that are the lower member
680 // of a monotically increasing or decreasing pair of edges.
681 // ****************************************************************************
682 static void MakeEdgeRecord(const Vec2dInt &lower, const Vec2dInt &upper, int yComp, Edge *pEdge, Edge **ppEdgeList, int height)
683 {
684  pEdge->inverse_gradient = float(upper.x - lower.x) / float(upper.y - lower.y);
685  pEdge->x_intersection = float(lower.x);
686 
687  if (upper.y < yComp)
688  pEdge->max_y = upper.y - 1;
689  else
690  pEdge->max_y = upper.y;
691 
692  if (lower.y >= 0 && lower.y < height)
693  InsertEdge(ppEdgeList[lower.y], pEdge);
694 }
695 
696 // ****************************************************************************
697 // For nIndex, return y-coordinate of the next non-horizontal edge which
698 // can be created by connecting the vertices in pPoints in their respective
699 // order to one another.
700 //
701 // nIndex: index of Vec2dInt to start with
702 // pPoints: array of points
703 // nPoints: number of points
704 // ****************************************************************************
705 static int NextY(int nIndex, const Vec2dInt *pPoints, int nVertices)
706 {
707  //j = k % count - 1
708  int j = nIndex + 1 > nVertices - 1 ? 0 : nIndex + 1;
709 
710  while (pPoints[nIndex].y == pPoints[j].y)
711  {
712  if (j + 1 > nVertices - 1)
713  j = 0;
714  else
715  j++;
716  }
717 
718  return pPoints[j].y;
719 }
720 
721 // ****************************************************************************
722 // Function used for creating a list of all edges, according to the points in
723 // in pPoints, respecting their order, that is pts[0]->pts[1]->..pts[n-1]->pts[0]
724 //
725 // pPoints: array of points of the polygon with order of connection
726 // nPoints: the number of points of the polygon
727 // ppEdges: result parameter for the list of edges to be computed
728 //****************************************************************************
729 static void BuildEdgeList(const Vec2dInt *pPoints, int nPoints, Edge **ppResultEdges, int height)
730 {
731  int nPreviousY = pPoints[nPoints - 2].y;
732  Vec2dInt v1 = { pPoints[nPoints - 1].x, pPoints[nPoints - 1].y };
733 
734  for (int i = 0; i < nPoints; i++)
735  {
736  Vec2dInt v2 = pPoints[i];
737 
738  if (v1.y != v2.y) // non-horizontal line
739  {
740  Edge *pEdge = new Edge();
741 
742  if (v1.y < v2.y)
743  MakeEdgeRecord(v1, v2, NextY(i, pPoints, nPoints), pEdge, ppResultEdges, height); // up-going edge
744  else
745  MakeEdgeRecord(v2, v1, nPreviousY, pEdge, ppResultEdges, height); // down-going edge
746  }
747 
748  nPreviousY = v1.y;
749  v1 = v2;
750  }
751 }
752 
753 
754 
755 
756 // ****************************************************************************
757 // During the algorithm, when a scanline intersects an edge on its
758 // upper-coordinates, when the scanning is done from up downward, then the edge
759 // is said to become active, so this method is used to always build a list of
760 // active edges during the scanning procedure.
761 //
762 // y: the y-coordinate of the scan line at every stage of scanning
763 // pActiveEdge: list of edges that are already active
764 // ppEdges: list of all the edges of the polygon each of which is tested,
765 // if it intersects the scanline (y)
766 // ****************************************************************************
767 static void BuildActiveList(int y, Edge *pActiveEdge, Edge **ppEdges)
768 {
769  Edge *p = ppEdges[y]->next;
770 
771  while (p)
772  {
773  Edge *q = p->next;
774  InsertEdge(pActiveEdge, p);
775  p = q;
776  }
777 }
778 
779 // ****************************************************************************
780 // Having all the active edges of each scan stage, all the pixels that lie
781 // horizontally between each pair of intersection points are filled with the
782 // desired color.
783 // ****************************************************************************
784 static void FillScan(CByteImage *pImage, int y, Edge *pActiveEdge, int r, int g, int b)
785 {
786  const int width = pImage->width;
787  const int height = pImage->height;
788  const int nPixels = width * height;
789 
790  if (y < 0 || y >= height)
791  return;
792 
793  unsigned char *pixels = pImage->type == CByteImage::eRGB24 ? pImage->pixels + 3 * y * width : pImage->pixels + y * width;
794 
795  Edge *p1 = pActiveEdge->next;
796 
797  while (p1 && p1->next)
798  {
799  const Edge *p2 = p1->next;
800 
801  const int x1 = MY_MIN(MY_MAX(int(p1->x_intersection + 0.5f), 0), pImage->width - 1);
802  const int x2 = MY_MAX(MY_MIN(int(p2->x_intersection + 0.5f), pImage->width - 1), 0);
803 
804  if (pImage->type == CByteImage::eRGB24)
805  {
806  for (int x = x1, offset = 3 * x1; x <= x2; x++, offset += 3)
807  {
808  pixels[offset] = r;
809  pixels[offset + 1] = g;
810  pixels[offset + 2] = b;
811  }
812  }
813  else if (pImage->type == CByteImage::eRGB24Split)
814  {
815  memset(pixels + x1, r, x2 - x1 + 1);
816  memset(pixels + x1 + nPixels, g, x2 - x1 + 1);
817  memset(pixels + x1 + (nPixels << 1), b, x2 - x1 + 1);
818  }
819 
820  p1 = p2->next;
821  }
822 }
823 
824 static void FillScan(CByteImage *pImage, int y, Edge *pActiveEdge, int g)
825 {
826  if (y < 0 || y >= pImage->height)
827  return;
828 
829  unsigned char *pixels = pImage->pixels + y * pImage->width;
830 
831  Edge *p1 = pActiveEdge->next;
832 
833  while (p1 && p1->next)
834  {
835  const Edge *p2 = p1->next;
836 
837  const int x1 = MY_MIN(MY_MAX(int(p1->x_intersection + 0.5f), 0), pImage->width - 1);
838  const int x2 = MY_MAX(MY_MIN(int(p2->x_intersection + 0.5f), pImage->width - 1), 0);
839 
840  memset(pixels + x1, g, x2 - x1 + 1);
841 
842  p1 = p2->next;
843  }
844 }
845 
846 static void DeleteAfter(Edge *pEdge)
847 {
848  // delete edge from linked list
849  Edge *p = pEdge->next;
850  pEdge->next = p->next;
851  delete p;
852 }
853 
854 static void UpdateActiveList(int y, Edge *pActiveEdge)
855 {
856  // delete completed edges
857  // update attribute x_intersection field for others which are still active
858  Edge *q = pActiveEdge;
859  Edge *p = pActiveEdge->next;
860 
861  while (p)
862  {
863  if (y >= p->max_y)
864  {
865  p = p->next;
866  DeleteAfter(q);
867  }
868  else
869  {
871  q = p;
872  p = p->next;
873  }
874  }
875 }
876 
877 static void ResortActiveList(Edge *pActiveEdge)
878 {
879  // resort active list after it has been updated
880  Edge *p = pActiveEdge->next;
881  pActiveEdge->next = 0;
882 
883  while (p)
884  {
885  Edge *q = p->next;
886  InsertEdge(pActiveEdge, p);
887  p = q;
888  }
889 }
890 
891 
892 // ****************************************************************************
893 // Implementation of the scan line fill algorithm by Derick Beng Yuh.
894 //
895 // pImage: the target image
896 // pPoints: array of points of the polygon with order of connection
897 // nPoints: the number of points of the polygon
898 // r, g, b: target color in RGB
899 // ****************************************************************************
900 static void FillPolygon(CByteImage *pImage, const Vec2d *pPoints, int nPoints, int r, int g, int b)
901 {
902  const int height = pImage->height;
903 
904  int i;
905 
906  // allocate memory for edges
907  Edge **ppEdges = new Edge*[height];
908  for (i = 0; i < height; i++)
909  ppEdges[i] = new Edge();
910 
911  // convert float points to int
912  Vec2dInt *pPointsInt = new Vec2dInt[nPoints];
913  for (i = 0; i < nPoints; i++)
914  {
915  pPointsInt[i].x = int(pPoints[i].x + 0.5f);
916  pPointsInt[i].y = int(pPoints[i].y + 0.5f);
917  }
918 
919  if (pPoints[0].x == pPoints[nPoints - 1].x && pPoints[0].y == pPoints[nPoints - 1].y)
920  nPoints--;
921 
922  // constuct edges
923  BuildEdgeList(pPointsInt, nPoints, ppEdges, height);
924 
925  // free memory
926  delete [] pPointsInt;
927 
928  Edge *pActiveEdge = new Edge();
929 
930  // run algorithm
931  for (i = 0; i < height; i++)
932  {
933  BuildActiveList(i, pActiveEdge, ppEdges);
934 
935  if (pActiveEdge->next)
936  {
937  if (pImage->type == CByteImage::eGrayScale)
938  FillScan(pImage, i, pActiveEdge, (r + (g << 1) + b + 2) >> 2);
939  else
940  FillScan(pImage, i, pActiveEdge, r, g, b);
941 
942  UpdateActiveList(i, pActiveEdge);
943  ResortActiveList(pActiveEdge);
944  }
945  }
946 
947  // free memory for edges
948  for (i = 0; i < height; i++)
949  delete ppEdges[i];
950  delete [] ppEdges;
951  delete pActiveEdge;
952 }
953 
954 void PrimitivesDrawer::DrawPolygon(CByteImage *pImage, const Vec2d *pPoints, int nPoints, int r, int g, int b, int thickness)
955 {
956  if (nPoints < 3)
957  {
958  printf("error: at least three points must be provided for PrimitivesDrawer::DrawPolygon\n");
959  return;
960  }
961 
962  if (thickness == -1)
963  {
964  FillPolygon(pImage, pPoints, nPoints, r, g, b);
965  }
966  else
967  {
968  for (int i = 0; i < nPoints - 1; i++)
969  DrawLine(pImage, pPoints[i], pPoints[i + 1], r, g, b, thickness);
970 
971  if (pPoints[0].x != pPoints[nPoints - 1].x || pPoints[0].y != pPoints[nPoints - 1].y)
972  DrawLine(pImage, pPoints[nPoints - 1], pPoints[0], r, g, b, thickness);
973  }
974 }
975 
976 void PrimitivesDrawer::DrawPolygon(CByteImage *pImage, const CVec2dArray &points, int r, int g, int b, int thickness)
977 {
978  const int nPoints = points.GetSize();
979 
980  Vec2d *pPoints = new Vec2d[nPoints];
981 
982  for (int i = 0; i < nPoints; i++)
983  Math2d::SetVec(pPoints[i], points[i]);
984 
985  DrawPolygon(pImage, pPoints, nPoints, r, g, b, thickness);
986 
987  delete [] pPoints;
988 }
989 
990 void PrimitivesDrawer::DrawEllipse(CByteImage *pImage, const Ellipse2d &ellipse, int r, int g, int b, int thickness)
991 {
992  const float mx = ellipse.center.x;
993  const float my = ellipse.center.y;
994 
995  const int min_x = int(mx - ellipse.radius_x + 0.5f);
996  const int min_y = int(my - ellipse.radius_y + 0.5f);
997  const int max_x = int(mx + ellipse.radius_x + 0.5f);
998  const int max_y = int(my + ellipse.radius_y + 0.5f);
999 
1000  const int rx = int(ellipse.radius_x + 0.5f);
1001  const int ry = int(ellipse.radius_y + 0.5f);
1002 
1003  int i;
1004 
1005  const float a2 = ellipse.radius_x * ellipse.radius_x;
1006  const float b2 = ellipse.radius_y * ellipse.radius_y;
1007  const float a2divb2 = a2 / b2;
1008  const float b2diva2 = b2 / a2;
1009 
1010  const float ca = cosf(ellipse.angle);
1011  const float sa = sinf(ellipse.angle);
1012 
1013  if (thickness == -1)
1014  {
1015  printf("error: filling of ellipses has not been implemented yet in PrimitivesDrawer::DrawEllipse\n");
1016  }
1017  else
1018  {
1019  if (thickness == 1)
1020  {
1021  for (i = -ry; i <= ry; i++)
1022  {
1023  const float y = float(i);
1024  const float d = a2 - a2divb2 * y * y;
1025 
1026  if (d >= 0.0f)
1027  {
1028  const float x = sqrtf(d);
1029 
1030  const float xr = ca * x - sa * y;
1031  const float yr = sa * x + ca * y;
1032 
1033  PrimitivesDrawer::DrawPoint(pImage, int(mx + xr + 0.5f), int(my + yr + 0.5f), r, g, b);
1034  PrimitivesDrawer::DrawPoint(pImage, int(mx - xr + 0.5f), int(my - yr + 0.5f) , r, g, b);
1035  }
1036  }
1037 
1038  for (i = -rx; i <= rx; i++)
1039  {
1040  const float x = float(i);
1041  const float d = b2 - b2diva2 * x * x;
1042 
1043  if (d >= 0.0f)
1044  {
1045  const float y = sqrtf(d);
1046 
1047  const float xr = ca * x - sa * y;
1048  const float yr = sa * x + ca * y;
1049 
1050  PrimitivesDrawer::DrawPoint(pImage, int(mx + xr + 0.5f), int(my + yr + 0.5f), r, g, b);
1051  PrimitivesDrawer::DrawPoint(pImage, int(mx - xr + 0.5f), int(my - yr + 0.5f), r, g, b);
1052  }
1053  }
1054  }
1055  else
1056  {
1057  const float thickness_radius = 0.5f * thickness;
1058 
1059  for (i = -ry; i <= ry; i++)
1060  {
1061  const float y = float(i);
1062  const float d = a2 - a2divb2 * y * y;
1063 
1064  if (d >= 0.0f)
1065  {
1066  const float x = sqrtf(d);
1067 
1068  const float xr = ca * x - sa * y;
1069  const float yr = sa * x + ca * y;
1070 
1071  PrimitivesDrawer::DrawCircle(pImage, mx + xr, my + yr, thickness_radius, r, g, b, -1);
1072  PrimitivesDrawer::DrawCircle(pImage, mx - xr, my - yr, thickness_radius, r, g, b, -1);
1073  }
1074  }
1075 
1076  for (i = -rx; i <= rx; i++)
1077  {
1078  const float x = float(i);
1079  const float d = b2 - b2diva2 * x * x;
1080 
1081  if (d >= 0.0f)
1082  {
1083  const float y = sqrtf(d);
1084 
1085  const float xr = ca * x - sa * y;
1086  const float yr = sa * x + ca * y;
1087 
1088  PrimitivesDrawer::DrawCircle(pImage, mx + xr, my + yr, thickness_radius, r, g, b, -1);
1089  PrimitivesDrawer::DrawCircle(pImage, mx - xr, my - yr, thickness_radius, r, g, b, -1);
1090  }
1091  }
1092  }
1093  }
1094 }
1095 
1096 void PrimitivesDrawer::DrawRectangle(CByteImage *pImage, const Rectangle2d &rectangle, int r, int g, int b, int thickness)
1097 {
1098  Vec2d cornerPoints[4];
1099  Math2d::ComputeRectangleCornerPoints(rectangle, cornerPoints);
1100 
1101  DrawPolygon(pImage, cornerPoints, 4, r, g, b, thickness);
1102 }
GLubyte g
Definition: glext.h:5166
GLfloat GLfloat GLfloat v2
Definition: glext.h:3532
int min_x
Definition: Structs.h:333
void DrawPolygon(CByteImage *pImage, const Vec2d *pPoints, int nPoints, int r, int g, int b, int thickness=1)
Draws a polygon into a CByteImage.
static void MakeEdgeRecord(const Vec2dInt &lower, const Vec2dInt &upper, int yComp, Edge *pEdge, Edge **ppEdgeList, int height)
Data structure for the representation of a 2D circle.
Definition: Structs.h:118
Vec2d center
The center of the ellipse.
Definition: Structs.h:142
float y
Definition: Math2d.h:84
static int NextY(int nIndex, const Vec2dInt *pPoints, int nVertices)
GLdouble GLdouble GLdouble GLdouble q
Definition: glext.h:3235
int width
The width of the image in pixels.
Definition: ByteImage.h:257
GLenum GLsizei n
Definition: glext.h:4209
float inverse_gradient
static void BuildActiveList(int y, Edge *pActiveEdge, Edge **ppEdges)
Data structure for the representation of 8-bit grayscale images and 24-bit RGB (or HSV) color images ...
Definition: ByteImage.h:80
Data structure for the representation of a 2D rectangle.
Definition: Structs.h:89
void ComputeRectangleCornerPoints(const Rectangle2d &rectangle, Vec2d resultCornerPoints[4])
Definition: Math2d.cpp:298
GLintptr offset
Definition: glext.h:3389
#define MY_MAX(a, b)
Definition: helpers.h:63
unsigned char * pixels
The pointer to the the pixels.
Definition: ByteImage.h:283
void DrawCircleAA(CByteImage *pImage, float mx, float my, float radius, int r, int g, int b, int thickness)
GLsizei const GLfloat * points
Definition: glext.h:4388
float angle
The rotiation angle of the ellipse, given in radians.
Definition: Structs.h:161
float radius
The radius of the circle.
Definition: Structs.h:128
void DrawLinePolar(CByteImage *pImage, float theta, float r, int color_r, int color_g, int color_b, int thickness=1)
Draws a straight line into a CByteImage, given its parameters in polar form.
Vec2d normalVector
The normalized normal vector of the straight line.
Definition: Structs.h:247
void DrawEllipse(CByteImage *pImage, const Ellipse2d &ellipse, int r=255, int g=255, int b=255, int thickness=1)
Draws an ellipse into a CByteImage.
float radius_y
The radius in vertical direction of the ellipse (vertical refers to when angle = 0).
Definition: Structs.h:152
GLenum GLint x
Definition: glext.h:3125
float x
Definition: Math2d.h:84
const GLubyte * c
Definition: glext.h:5181
void DrawPointBlended(CByteImage *pImage, const Vec2d &point, int r=255, int g=255, int b=255, float blend=1.0f)
Draws a point into a CByteImage, with blending.
static void UpdateActiveList(int y, Edge *pActiveEdge)
void DrawCircle(CByteImage *pImage, float mx, float my, float radius, int r=255, int g=255, int b=255, int thickness=1, bool bAntiAlias=false)
Draws a circle into a CByteImage.
void DrawRectangle(CByteImage *pImage, const Rectangle2d &rectangle, int r, int g, int b, int thickness=1)
Draws a rectangle into a CByteImage.
void DrawPoint(CByteImage *pImage, const Vec2d &point, int r=255, int g=255, int b=255)
Draws a point into a CByteImage.
static void DeleteAfter(Edge *pEdge)
Vec2d p1
Definition: Structs.h:73
int min_y
Definition: Structs.h:334
static bool is_indeterminate(const float fValue)
static void ResortActiveList(Edge *pActiveEdge)
GLint GLint GLsizei GLsizei GLsizei GLint GLenum GLenum const GLvoid * pixels
Definition: glext.h:3154
float x_intersection
Edge * next
int height
The height of the image in pixels.
Definition: ByteImage.h:264
int my_round(double x)
Definition: helpers.cpp:325
void DrawCross(CByteImage *pImage, const Vec2d &point, int length, int r, int g, int b)
Draws a small cross into a CByteImage.
Data structure for the representation of a 2D ellipse.
Definition: Structs.h:137
void DrawLine(CByteImage *pImage, const PointPair2d &line, int r=255, int g=255, int b=255, int thickness=1)
Draws a line segment into a CByteImage, given its two end points.
GLubyte GLubyte b
Definition: glext.h:5166
GLfloat GLfloat GLfloat GLfloat nx
Definition: glext.h:5174
static void FillPolygon(CByteImage *pImage, const Vec2d *pPoints, int nPoints, int r, int g, int b)
#define MY_MIN(a, b)
Definition: helpers.h:64
static bool is_infinite(const float fValue)
GLenum GLsizei width
Definition: glext.h:3122
GLenum GLsizei GLsizei height
Definition: glext.h:3132
int max_x
Definition: Structs.h:335
Data structure for the representation of a 2D straight line.
Definition: Structs.h:179
float radius_x
The radius in horizontal direction of the ellipse (horizontal refers to when angle = 0)...
Definition: Structs.h:147
ImageType type
The type of the image.
Definition: ByteImage.h:292
Vec2d p2
Definition: Structs.h:74
GLdouble GLdouble GLdouble r
Definition: glext.h:3227
Vec2d center
The center of the circle.
Definition: Structs.h:123
float c
The negative scalar product of normalVector and point.
Definition: Structs.h:252
GLuint GLsizei GLsizei * length
Definition: glext.h:3509
GLenum GLint GLint y
Definition: glext.h:3125
Data structure for the representation of a 2D vector.
Definition: Math2d.h:82
GLfloat GLfloat v1
Definition: glext.h:3531
void DrawLineNormal(CByteImage *pImage, float nx, float ny, float c, int r, int g, int b, int thickness=1)
Draws a line into a CByteImage, given its parameters in normal form.
void DrawRegion(CByteImage *pImage, const MyRegion &region, int r=255, int g=255, int b=255, int thickness=1)
Draws a rectangle into a CByteImage.
void SetVec(Vec2d &vec, float x, float y)
Definition: Math2d.cpp:68
GLfloat ny
Definition: glext.h:5172
static void FillScan(CByteImage *pImage, int y, Edge *pActiveEdge, int r, int g, int b)
static void InsertEdge(Edge *ppEdgeList, Edge *pEdge)
void DrawPoints(CByteImage *pImage, const CVec2dArray &points, int r=255, int g=255, int b=255)
Draws a list of points of type CVec2dArray into a CByteImage.
GLfloat GLfloat p
Definition: glext.h:5178
int max_y
Definition: Structs.h:336
static void BuildEdgeList(const Vec2dInt *pPoints, int nPoints, Edge **ppResultEdges, int height)


asr_ivt
Author(s): Allgeyer Tobias, Hutmacher Robin, Kleinert Daniel, Meißner Pascal, Scholz Jonas, Stöckle Patrick
autogenerated on Mon Dec 2 2019 03:47:28