MIRA
Bresenham.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2012 by
3  * MetraLabs GmbH (MLAB), GERMANY
4  * and
5  * Neuroinformatics and Cognitive Robotics Labs (NICR) at TU Ilmenau, GERMANY
6  * All rights reserved.
7  *
8  * Contact: info@mira-project.org
9  *
10  * Commercial Usage:
11  * Licensees holding valid commercial licenses may use this file in
12  * accordance with the commercial license agreement provided with the
13  * software or, alternatively, in accordance with the terms contained in
14  * a written agreement between you and MLAB or NICR.
15  *
16  * GNU General Public License Usage:
17  * Alternatively, this file may be used under the terms of the GNU
18  * General Public License version 3.0 as published by the Free Software
19  * Foundation and appearing in the file LICENSE.GPL3 included in the
20  * packaging of this file. Please review the following information to
21  * ensure the GNU General Public License version 3.0 requirements will be
22  * met: http://www.gnu.org/copyleft/gpl.html.
23  * Alternatively you may (at your option) use any later version of the GNU
24  * General Public License if such license has been publicly approved by
25  * MLAB and NICR (or its successors, if any).
26  *
27  * IN NO EVENT SHALL "MLAB" OR "NICR" BE LIABLE TO ANY PARTY FOR DIRECT,
28  * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
29  * THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF "MLAB" OR
30  * "NICR" HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  *
32  * "MLAB" AND "NICR" SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
33  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
34  * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
35  * ON AN "AS IS" BASIS, AND "MLAB" AND "NICR" HAVE NO OBLIGATION TO
36  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS OR MODIFICATIONS.
37  */
38 
49 #ifndef _MIRA_BRESENHAM_H_
50 #define _MIRA_BRESENHAM_H_
51 
52 #include <cstdlib>
53 #include <algorithm>
54 #include <geometry/Point.h>
55 
56 namespace mira {
57 
59 
87 template<typename Visitor>
88 void bresenham(int x0, int y0, int x1, int y1, Visitor&& visitor);
89 
91 
102 template<typename Visitor>
103 void bresenham(Point2i p0, Point2i p1, Visitor&& visitor)
104 {
105  bresenham(p0[0], p0[1], p1[0], p1[1], visitor);
106 }
107 
109 
161 template<typename Visitor>
162 void bresenhamRunSlice(int x0, int y0, int x1, int y1, Visitor&& visitor);
163 
165 
175 template<typename Visitor>
176 void bresenhamRunSlice(Point2i p0, Point2i p1, Visitor&& visitor)
177 {
178  bresenhamRunSlice(p0[0], p0[1], p1[0], p1[1], visitor);
179 }
180 
182 // implementation section: BresenhamLineIterator class definition
183 
200 {
201 public:
212  BresenhamLineIterator(int x0, int y0, int x1, int y1,
213  int xInc=1, int yInc=1);
214 
216  bool hasNext() const;
217 
220 
223 
225  int x() const { return mX; }
226 
228  int y() const { return mY; }
229 
231  bool isMajorX() const { return (mDeltaX >= mDeltaY); }
232 
234  bool isMajorY() const { return !isMajorX(); }
235 
237  int pos() const { return mI; }
238 
240  int length() const { return mDen; }
241 
247 
248 private:
249  BresenhamLineIterator(int mx, int my,
250  int xInc1, int xInc2, int yInc1, int yInc2,
251  int num, int den, int numInc,
252  int deltaX, int deltaY);
253 
254 private:
255  int mI;
256  int mX,mY;
257  int mXInc1, mXInc2, mYInc1, mYInc2, mNum, mDen, mNumInc;
258  int mDeltaX, mDeltaY;
259 };
260 
262 // implementation section: GeneralBresenhamLineIterator class definition
263 
265 {
266 protected:
271  struct AxisBase
272  {
273  int current;
274  int step;
275  int end;
276  int64_t distance;
277  int64_t error;
278  };
279 };
280 
287 template <int Drive, bool DrivenByLongestAxis = (Drive < 0)>
288 class GeneralBresenhamLineIteratorBase : public GeneralBresenhamLineIteratorCommonBase
289 {
290 protected:
291  inline void checkForDrivingAxis(int index, const int64_t& dist, int64_t& maxd)
292  {
293  if (dist > maxd)
294  {
295  maxd = dist;
296  mDrivingAxis = index;
297  }
298  }
299 
300  inline void step(AxisBase& axis, const AxisBase& drive)
301  {
302  if (axis.error >= 0)
303  {
304  axis.current += axis.step;
305  axis.error += axis.distance - drive.distance;
306  }
307  else
308  axis.error += axis.distance;
309  }
310 
311 public:
313  inline int drivingAxis() const { return mDrivingAxis; }
314 
315 protected:
317 };
318 
323 template <int Drive>
325 {
326 protected:
327  inline void checkForDrivingAxis(int index, const int64_t& dist, int64_t& maxd) {} // do nothing
328 
329  inline void step(AxisBase& axis, const AxisBase& drive)
330  {
331  if (axis.error >= 0)
332  {
333  int steps = axis.error / drive.distance + 1;
334  axis.current += steps * axis.step;
335  axis.error -= steps * drive.distance;
336  }
337  axis.error += axis.distance;
338  }
339 
340 public:
342  inline int drivingAxis() const { return Drive; }
343 };
344 
346 
372 template <int D, typename T = float, int Drive = -1, int Res = 1000>
374 {
375  static_assert(Drive < D, "Driving axis Drive must not be >= number of dimensions D in GeneralBresenhamLineIterator instantiation!");
376 public:
380  struct Axis : public GeneralBresenhamLineIteratorCommonBase::AxisBase
381  {
382  T startExact, endExact;
383  };
384 
385 public:
392  GeneralBresenhamLineIterator(Point<T, D> start = Point<T, D>(),
393  Point<T, D> end = Point<T, D>());
394 
395 public:
401  void init(Point<T, D> start = Point<T, D>(),
402  Point<T, D> end = Point<T, D>());
403 
405  inline bool hasNext() const
406  { return mAxes[this->drivingAxis()].current != mAxes[this->drivingAxis()].end; }
407 
409  const GeneralBresenhamLineIterator& operator++();
410 
418  Point<int, D> pos() const;
419 
424  inline const Axis& axis(uint32 d) const { return mAxes[d]; }
425 
426 protected:
427 
428  Axis mAxes[D]; ///< the axes variables
429 };
430 
432 // implementation section: BresenhamLineIterator class implementation
434 
435 inline BresenhamLineIterator::BresenhamLineIterator(int x0, int y0,
436  int x1, int y1,
437  int xInc, int yInc)
438 {
439  // prepare the bresenham algo
440  mDeltaX = std::abs(x1 - x0);
441  mDeltaY = std::abs(y1 - y0);
442 
443  mX = x0;
444  mY = y0;
445 
446  if (x1 >= x0) {mXInc1 = xInc; mXInc2 = xInc; }
447  else {mXInc1 = -xInc; mXInc2 = -xInc; }
448 
449  if (y1 >= y0) {mYInc1 = yInc; mYInc2 = yInc; }
450  else {mYInc1 = -yInc; mYInc2 = -yInc; }
451 
452  if (mDeltaX >= mDeltaY) {
453  mXInc1 = 0;
454  mYInc2 = 0;
455  mDen = mDeltaX;
456  mNumInc = mDeltaY;
457  }
458  else {
459  mXInc2 = 0;
460  mYInc1 = 0;
461  mDen = mDeltaY;
462  mNumInc = mDeltaX;
463  }
464 
465  mNum = mDen >> 1;
466  mI=0;
467 }
468 
470 
471 inline BresenhamLineIterator::BresenhamLineIterator(int mx, int my,
472  int xInc1, int xInc2,
473  int yInc1, int yInc2,
474  int num, int den, int numInc,
475  int deltaX, int deltaY) :
476  mI(0),
477  mX(mx), mY(my),
478  mXInc1(xInc1), mXInc2(xInc2), mYInc1(yInc1), mYInc2(yInc2),
479  mNum(num), mDen(den), mNumInc(numInc),
480  mDeltaX(deltaX), mDeltaY(deltaY)
481 {
482  // this constructor is for internal use only
483 }
484 
486 
487 inline const BresenhamLineIterator& BresenhamLineIterator::operator++()
488 {
489  mNum += mNumInc;
490  if (mNum >= mDen)
491  {
492  mNum -= mDen;
493  mX += mXInc1;
494  mY += mYInc1;
495  }
496  mX += mXInc2;
497  mY += mYInc2;
498 
499  ++mI;
500 
501  return *this;
502 }
503 
505 
506 inline const BresenhamLineIterator& BresenhamLineIterator::operator--()
507 {
508  mNum -= mNumInc;
509  if (mNum < 0)
510  {
511  mNum += mDen;
512  mX -= mXInc1;
513  mY -= mYInc1;
514  }
515  mX -= mXInc2;
516  mY -= mYInc2;
517 
518  --mI;
519 
520  return *this;
521 }
522 
524 
525 inline bool BresenhamLineIterator::hasNext() const
526 {
527  if(mI<=mDen)
528  return true;
529  else
530  return false;
531 }
532 
534 
535 // normal line has tangent of dY/dX -> orthogonal line has tangent of -dX/dY.
536 // So we have to switch and negate the increments and switch the deltas. The
537 // line itself still starts at (mX,mY).
538 inline BresenhamLineIterator BresenhamLineIterator::orthogonal()
539 {
540  return BresenhamLineIterator(mX, mY, mYInc1, mYInc2, -mXInc1, -mXInc2,
541  mNum, mDen, mNumInc, mDeltaY, mDeltaX);
542 }
543 
545 // interface implementation
546 
547 template<typename Visitor>
548 inline void bresenham(int x0, int y0, int x1, int y1, Visitor&& visitor)
549 {
550  for(BresenhamLineIterator l(x0,y0,x1,y1); l.hasNext(); ++l)
551  visitor(l.x(), l.y());
552 
553 }
554 
556 
569 
571 template<typename Visitor>
572 inline void bresenhamRunSlice(int x0, int y0, int x1, int y1, Visitor&& visitor)
573 {
574  // make sure we always go from top to bottom
575  if (y1 < y0) {
576  std::swap(y0,y1);
577  std::swap(x0,x1);
578  }
579 
580  int dx = x1 - x0;
581  int dy = y1 - y0;
582 
583  int x, y;
584  x = x0;
585  y = y0;
586 
587  int adjUp, adjDown, error;
588  int wholeStep, initialLength, finalLength, runLength;
589 
590  // are we going from right to left ?
591  if (dx < 0)
592  dx = -dx;
593 
594  // special case: horizontal line
595  if(dy==0) {
596  if(x0<=x1)
597  visitor(x0, y0, dx+1);
598  else
599  visitor(x1, y0, dx+1);
600  return;
601  }
602 
603  // use normal bresenham for lines with major y-axis
604  if(dx<=dy) {
605  for(BresenhamLineIterator l(x0,y0,x1,y1); l.hasNext(); ++l)
606  visitor(l.x(), l.y(), 1);
607  return;
608  }
609 
610  // use run-slice algorithm for lines with major x-axis:
611 
612  // minimum number of pixels in a run in this line
613  wholeStep = dx / dy;
614 
615  // Error term adjust each time Y steps by 1; used to tell when one
616  // extra pixel should be drawn as part of a run, to account for
617  // fractional steps along the X axis per 1-pixel steps along Y
618  adjUp = (dx % dy) * 2;
619 
620  // Error term adjust when the error term turns over, used to factor
621  // out the X step made at that time
622  adjDown = dy * 2;
623 
624  // Initial error term; reflects an initial step of 0.5 along the Y
625  // axis
626  error = (dx % dy) - (dy * 2);
627 
628  // The initial and last runs are partial, because Y advances only 0.5
629  // for these runs, rather than 1. Divide one full run, plus the
630  // initial pixel, between the initial and last runs
631  initialLength = (wholeStep / 2) + 1;
632  finalLength = initialLength;
633 
634  // If the basic run length is even and there's no fractional
635  // advance, we have one pixel that could go to either the initial
636  // or last partial run, which we'll arbitrarily allocate to the
637  // last run
638  if ((adjUp == 0) && ((wholeStep & 0x01) == 0)) {
639  initialLength--;
640  }
641 
642  // If there're an odd number of pixels per run, we have 1 pixel that can't
643  // be allocated to either the initial or last partial run, so we'll add 0.5
644  // to error term so this pixel will be handled by the normal full-run loop
645  if ((wholeStep & 0x01) != 0) {
646  error += dy;
647  }
648 
649  if (x1 >= x0) {
650  // Draw the first, partial run of pixels
651  visitor(x, y, initialLength);
652  x += initialLength;
653  ++y;
655 
656  // process full runs
657  for (int i = 0; i < (dy - 1); i++) {
658  runLength = wholeStep; // run is at least this long
659  // advance the error term and add an extra pixel if the error
660  // term so indicates
661  if ((error += adjUp) > 0) {
662  runLength++;
663  error -= adjDown;
664  }
665 
666  // call the visitor
667  visitor(x, y, runLength);
668  x += runLength;
669  ++y;
670  }
671 
672  // the final run of pixels
673  visitor(x, y, finalLength);
674  } else {
675  ++x;
676 
677  // Draw the first, partial run of pixels
678  x -= initialLength;
679  visitor(x, y, initialLength);
680  ++y;
681 
683 
684  // process full runs
685  for (int i = 0; i < (dy - 1); i++) {
686  runLength = wholeStep; // run is at least this long
687  // advance the error term and add an extra pixel if the error
688  // term so indicates
689  if ((error += adjUp) > 0) {
690  runLength++;
691  error -= adjDown;
692  }
693 
694  // call the visitor
695  x -= runLength;
696  visitor(x, y, runLength);
697  ++y;
698  }
699 
700  // the final run of pixels
701  x -= finalLength;
702  visitor(x, y, finalLength);
703  }
704 }
705 
707 // implementation section: GeneralBresenhamLineIterator class implementation
709 template <int D, typename T, int Drive, int Res>
710 inline GeneralBresenhamLineIterator<D, T, Drive, Res>::
711 GeneralBresenhamLineIterator(Point<T, D> start,
712  Point<T, D> end)
713 {
714  init(start, end);
715 }
716 
717 template <int D, typename T, int Drive, int Res>
718 inline void GeneralBresenhamLineIterator<D, T, Drive, Res>::
719 init(Point<T, D> start, Point<T, D> end)
720 {
721  int64_t maxd = -1;
722 
723  for (int n = 0; n < D; ++n)
724  {
725  Axis& axis = mAxes[n];
726  axis.startExact = start(n);
727  axis.endExact = end(n);
728  axis.distance = std::abs(Res * (axis.endExact - axis.startExact));
729  axis.current = floor(axis.startExact);
730  axis.end = floor(axis.endExact);
731  axis.step = (axis.endExact >= axis.startExact) ? 1 : -1;
732 
733  this->checkForDrivingAxis(n, axis.distance, maxd);
734  }
735 
736  Axis& drive = mAxes[this->drivingAxis()];
737  drive.distance = std::ceil(std::abs(Res * (drive.endExact - drive.startExact)));
738 
739  T driveOffset = drive.startExact - drive.current;
740  if (drive.step < 0)
741  driveOffset = 1 - driveOffset;
742 
743  for (int n = 0; n < D; ++n)
744  {
745  Axis& axis = mAxes[n];
746 
747  if (n == this->drivingAxis())
748  {
749  axis.error = 0;
750  continue;
751  }
752 
753  T axisOffset = axis.startExact - axis.current;
754  if (axis.step < 0)
755  axisOffset = 1 - axisOffset;
756 
757  axis.error = floor( axis.distance * (1 - driveOffset)
758  -drive.distance * (1 - axisOffset) );
759  }
760 }
761 
762 template <int D, typename T, int Drive, int Res>
763 inline const GeneralBresenhamLineIterator<D, T, Drive, Res>&
764 GeneralBresenhamLineIterator<D, T, Drive, Res>::operator++()
765 {
766  for (int n = 0; n < D; ++n)
767  {
768  Axis& axis = mAxes[n];
769 
770  if (n == this->drivingAxis())
771  axis.current += axis.step;
772  else
773  this->step(axis, mAxes[this->drivingAxis()]);
774  }
775 
776  return *this;
777 }
778 
779 template <int D, typename T, int Drive, int Res>
780 inline Point<int, D>
781 GeneralBresenhamLineIterator<D, T, Drive, Res>::pos() const
782 {
783  Point<int, D> p;
784  for (int n = 0; n < D; ++n)
785  p(n) = mAxes[n].current;
786 
787  return p;
788 }
789 
791 }
792 
793 #endif
const BresenhamLineIterator & operator--()
Moves iterator backward to the previous point/pixel.
Definition: Bresenham.h:506
BresenhamLineIterator orthogonal()
Creates a new bresenham line iterator that is orthogonal to this line and starts in the current point...
Definition: Bresenham.h:538
Guaranteeing longest axis as drive axis allows some simplification/optimization in step...
Definition: Bresenham.h:288
void bresenham(int x0, int y0, int x1, int y1, Visitor &&visitor)
Rasterizes a Bresenham line point by point starting at coordinate (x0,y0) and ending in (x1...
Definition: Bresenham.h:548
int length() const
Returns the length of the line in points/pixels.
Definition: Bresenham.h:240
General point class template.
Definition: Point.h:135
specialize cv::DataType for our ImgPixel and inherit from cv::DataType<Vec>
Definition: IOService.h:67
int mDrivingAxis
driving axis dimension index
Definition: Bresenham.h:316
Class for 2D, 3D and N-dimensional points.
int y() const
Returns current y-coordinate.
Definition: Bresenham.h:228
int drivingAxis() const
Returns dimension index of the driving axis.
Definition: Bresenham.h:342
void bresenhamRunSlice(int x0, int y0, int x1, int y1, Visitor &&visitor)
Rasterizes a Bresenham line starting at coordinate (x0,y0) and ending in (x1,y1). ...
Definition: Bresenham.h:572
int drivingAxis() const
Returns dimension index of the driving axis.
Definition: Bresenham.h:313
Data structure containing the numtype-independent relevant variables for one axis (dimension) of the ...
Definition: Bresenham.h:271
bool isMajorX() const
Returns true if the line mainly moves along the x-axis.
Definition: Bresenham.h:231
void step(AxisBase &axis, const AxisBase &drive)
Definition: Bresenham.h:300
void step(AxisBase &axis, const AxisBase &drive)
Definition: Bresenham.h:329
BresenhamLineIterator(int x0, int y0, int x1, int y1, int xInc=1, int yInc=1)
Creates a new bresenham iterator that iterates over a line starting at coordinate (x0...
Definition: Bresenham.h:435
Implements an iterator that is able to iterate over a Bresenham line point by point using the prefix ...
Definition: Bresenham.h:199
This more general iterator basically follows the design of BresenhamLineIterator, but works on an arb...
Definition: Bresenham.h:373
const BresenhamLineIterator & operator++()
Advances the iterator to the next point/pixel.
Definition: Bresenham.h:487
int64_t distance
Definition: Bresenham.h:276
bool isMajorY() const
Returns true if the line mainly moves along the y-axis.
Definition: Bresenham.h:234
void checkForDrivingAxis(int index, const int64_t &dist, int64_t &maxd)
Definition: Bresenham.h:327
bool hasNext() const
Returns true, if there are more points/pixels to go.
Definition: Bresenham.h:525
int x() const
Returns current x-coordinate.
Definition: Bresenham.h:225
int pos() const
Returns the current position on the line.
Definition: Bresenham.h:237