1 //----------------------------------------------------------------------------
2 // Anti-Grain Geometry - Version 2.4
3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4 //
5 // Permission to copy, use, modify, sell and distribute this software
6 // is granted provided this copyright notice appears in all copies.
7 // This software is provided "as is" without express or implied
8 // warranty, and with no claim as to its suitability for any purpose.
9 //
10 //----------------------------------------------------------------------------
11 // Contact: mcseem@antigrain.com
12 // mcseemagg@yahoo.com
13 // http://www.antigrain.com
14 //----------------------------------------------------------------------------
15
16 #ifndef AGG_BASICS_INCLUDED
17 #define AGG_BASICS_INCLUDED
18
19 #include <cmath>
20 #include "agg_config.h"
21
22 //---------------------------------------------------------AGG_CUSTOM_ALLOCATOR
23 #ifdef AGG_CUSTOM_ALLOCATOR
24 #include "agg_allocator.h"
25 #else
26 namespace agg
27 {
28 // The policy of all AGG containers and memory allocation strategy
29 // in general is that no allocated data requires explicit construction.
30 // It means that the allocator can be really simple; you can even
31 // replace new/delete to malloc/free. The constructors and destructors
32 // won't be called in this case, however everything will remain working.
33 // The second argument of deallocate() is the size of the allocated
34 // block. You can use this information if you wish.
35 //------------------------------------------------------------pod_allocator
36 template<class T> struct pod_allocator
37 {
38 static T* allocate(unsigned num) { return new T [num]; }
39 static void deallocate(T* ptr, unsigned) { delete [] ptr; }
40 };
41
42 // Single object allocator. It's also can be replaced with your custom
43 // allocator. The difference is that it can only allocate a single
44 // object and the constructor and destructor must be called.
45 // In AGG there is no need to allocate an array of objects with
46 // calling their constructors (only single ones). So that, if you
47 // replace these new/delete to malloc/free make sure that the in-place
48 // new is called and take care of calling the destructor too.
49 //------------------------------------------------------------obj_allocator
50 template<class T> struct obj_allocator
51 {
52 static T* allocate() { return new T; }
53 static void deallocate(T* ptr) { delete ptr; }
54 };
fls(int mask)55 }
56 #endif
57
58
59 //-------------------------------------------------------- Default basic types
60 //
61 // If the compiler has different capacity of the basic types you can redefine
62 // them via the compiler command line or by generating agg_config.h that is
63 // empty by default.
64 //
65 #ifndef AGG_INT8
66 #define AGG_INT8 signed char
67 #endif
68
69 #ifndef AGG_INT8U
70 #define AGG_INT8U unsigned char
71 #endif
72
73 #ifndef AGG_INT16
74 #define AGG_INT16 short
75 #endif
76
77 #ifndef AGG_INT16U
78 #define AGG_INT16U unsigned short
79 #endif
80
81 #ifndef AGG_INT32
82 #define AGG_INT32 int
83 #endif
84
85 #ifndef AGG_INT32U
86 #define AGG_INT32U unsigned
87 #endif
88
89 #ifndef AGG_INT64
90 #if defined(_MSC_VER) || defined(__BORLANDC__)
91 #define AGG_INT64 signed __int64
92 #else
93 #define AGG_INT64 signed long long
94 #endif
95 #endif
96
97 #ifndef AGG_INT64U
98 #if defined(_MSC_VER) || defined(__BORLANDC__)
99 #define AGG_INT64U unsigned __int64
100 #else
101 #define AGG_INT64U unsigned long long
102 #endif
103 #endif
104
105 //------------------------------------------------ Some fixes for MS Visual C++
106 #if defined(_MSC_VER)
107 #pragma warning(disable:4786) // Identifier was truncated...
108 #endif
109
110 #if defined(_MSC_VER)
111 #define AGG_INLINE __forceinline
112 #else
113 #define AGG_INLINE inline
114 #endif
115
116 namespace agg
117 {
118 //-------------------------------------------------------------------------
119 typedef AGG_INT8 int8; //----int8
120 typedef AGG_INT8U int8u; //----int8u
121 typedef AGG_INT16 int16; //----int16
122 typedef AGG_INT16U int16u; //----int16u
123 typedef AGG_INT32 int32; //----int32
124 typedef AGG_INT32U int32u; //----int32u
125 typedef AGG_INT64 int64; //----int64
126 typedef AGG_INT64U int64u; //----int64u
127
128 #if defined(AGG_FISTP)
129 #pragma warning(push)
130 #pragma warning(disable : 4035) //Disable warning "no return value"
131 AGG_INLINE int iround(double v) //-------iround
132 {
133 int t;
134 __asm fld qword ptr [v]
135 __asm fistp dword ptr [t]
136 __asm mov eax, dword ptr [t]
137 }
138 AGG_INLINE unsigned uround(double v) //-------uround
139 {
140 unsigned t;
141 __asm fld qword ptr [v]
142 __asm fistp dword ptr [t]
143 __asm mov eax, dword ptr [t]
144 }
145 #pragma warning(pop)
146 AGG_INLINE int ifloor(double v)
147 {
148 return int(floor(v));
149 }
150 AGG_INLINE unsigned ufloor(double v) //-------ufloor
151 {
152 return unsigned(floor(v));
153 }
154 AGG_INLINE int iceil(double v)
155 {
156 return int(ceil(v));
157 }
158 AGG_INLINE unsigned uceil(double v) //--------uceil
159 {
160 return unsigned(ceil(v));
161 }
162 #elif defined(AGG_QIFIST)
163 AGG_INLINE int iround(double v)
164 {
165 return int(v);
166 }
167 AGG_INLINE int uround(double v)
168 {
169 return unsigned(v);
170 }
171 AGG_INLINE int ifloor(double v)
172 {
173 return int(std::floor(v));
174 }
175 AGG_INLINE unsigned ufloor(double v)
176 {
177 return unsigned(std::floor(v));
178 }
179 AGG_INLINE int iceil(double v)
180 {
181 return int(std::ceil(v));
182 }
183 AGG_INLINE unsigned uceil(double v)
184 {
185 return unsigned(std::ceil(v));
186 }
187 #else
188 AGG_INLINE int iround(double v)
189 {
190 return int((v < 0.0) ? v - 0.5 : v + 0.5);
191 }
192 AGG_INLINE int uround(double v)
193 {
194 return unsigned(v + 0.5);
195 }
196 AGG_INLINE int ifloor(double v)
197 {
198 int i = int(v);
199 return i - (i > v);
200 }
201 AGG_INLINE unsigned ufloor(double v)
202 {
203 return unsigned(v);
204 }
205 AGG_INLINE int iceil(double v)
206 {
207 return int(std::ceil(v));
208 }
209 AGG_INLINE unsigned uceil(double v)
210 {
211 return unsigned(std::ceil(v));
212 }
213 #endif
214
215 //---------------------------------------------------------------saturation
216 template<int Limit> struct saturation
217 {
218 AGG_INLINE static int iround(double v)
219 {
220 if(v < double(-Limit)) return -Limit;
221 if(v > double( Limit)) return Limit;
222 return agg::iround(v);
223 }
224 };
225
226 //------------------------------------------------------------------mul_one
227 template<unsigned Shift> struct mul_one
228 {
229 AGG_INLINE static unsigned mul(unsigned a, unsigned b)
230 {
231 unsigned q = a * b + (1 << (Shift-1));
232 return (q + (q >> Shift)) >> Shift;
233 }
234 };
235
236 //-------------------------------------------------------------------------
237 typedef unsigned char cover_type; //----cover_type
238 enum cover_scale_e
239 {
240 cover_shift = 8, //----cover_shift
241 cover_size = 1 << cover_shift, //----cover_size
242 cover_mask = cover_size - 1, //----cover_mask
243 cover_none = 0, //----cover_none
244 cover_full = cover_mask //----cover_full
245 };
246
247 //----------------------------------------------------poly_subpixel_scale_e
248 // These constants determine the subpixel accuracy, to be more precise,
249 // the number of bits of the fractional part of the coordinates.
250 // The possible coordinate capacity in bits can be calculated by formula:
251 // sizeof(int) * 8 - poly_subpixel_shift, i.e, for 32-bit integers and
252 // 8-bits fractional part the capacity is 24 bits.
253 enum poly_subpixel_scale_e
254 {
255 poly_subpixel_shift = 8, //----poly_subpixel_shift
256 poly_subpixel_scale = 1<<poly_subpixel_shift, //----poly_subpixel_scale
257 poly_subpixel_mask = poly_subpixel_scale-1 //----poly_subpixel_mask
258 };
259
260 //----------------------------------------------------------filling_rule_e
261 enum filling_rule_e
262 {
263 fill_non_zero,
264 fill_even_odd
265 };
266
267 //-----------------------------------------------------------------------pi
268 const double pi = 3.14159265358979323846;
269
270 //------------------------------------------------------------------deg2rad
271 inline double deg2rad(double deg)
272 {
273 return deg * pi / 180.0;
274 }
275
276 //------------------------------------------------------------------rad2deg
277 inline double rad2deg(double rad)
278 {
279 return rad * 180.0 / pi;
280 }
281
282 //----------------------------------------------------------------rect_base
283 template<class T> struct rect_base
284 {
285 typedef T value_type;
286 typedef rect_base<T> self_type;
287 T x1, y1, x2, y2;
288
289 rect_base() {}
290 rect_base(T x1_, T y1_, T x2_, T y2_) :
291 x1(x1_), y1(y1_), x2(x2_), y2(y2_) {}
292
293 void init(T x1_, T y1_, T x2_, T y2_)
294 {
295 x1 = x1_; y1 = y1_; x2 = x2_; y2 = y2_;
296 }
297
298 const self_type& normalize()
299 {
300 T t;
301 if(x1 > x2) { t = x1; x1 = x2; x2 = t; }
302 if(y1 > y2) { t = y1; y1 = y2; y2 = t; }
303 return *this;
304 }
305
306 bool clip(const self_type& r)
307 {
308 if(x2 > r.x2) x2 = r.x2;
309 if(y2 > r.y2) y2 = r.y2;
310 if(x1 < r.x1) x1 = r.x1;
311 if(y1 < r.y1) y1 = r.y1;
312 return x1 <= x2 && y1 <= y2;
313 }
314
315 bool is_valid() const
316 {
317 return x1 <= x2 && y1 <= y2;
318 }
319
320 bool hit_test(T x, T y) const
321 {
322 return (x >= x1 && x <= x2 && y >= y1 && y <= y2);
323 }
324
325 bool overlaps(const self_type& r) const
326 {
327 return !(r.x1 > x2 || r.x2 < x1
328 || r.y1 > y2 || r.y2 < y1);
329 }
330 };
331
332 //-----------------------------------------------------intersect_rectangles
333 template<class Rect>
334 inline Rect intersect_rectangles(const Rect& r1, const Rect& r2)
335 {
336 Rect r = r1;
337
338 // First process x2,y2 because the other order
339 // results in Internal Compiler Error under
340 // Microsoft Visual C++ .NET 2003 69462-335-0000007-18038 in
341 // case of "Maximize Speed" optimization option.
342 //-----------------
343 if(r.x2 > r2.x2) r.x2 = r2.x2;
344 if(r.y2 > r2.y2) r.y2 = r2.y2;
345 if(r.x1 < r2.x1) r.x1 = r2.x1;
346 if(r.y1 < r2.y1) r.y1 = r2.y1;
347 return r;
348 }
349
350
351 //---------------------------------------------------------unite_rectangles
352 template<class Rect>
353 inline Rect unite_rectangles(const Rect& r1, const Rect& r2)
354 {
355 Rect r = r1;
356 if(r.x2 < r2.x2) r.x2 = r2.x2;
357 if(r.y2 < r2.y2) r.y2 = r2.y2;
358 if(r.x1 > r2.x1) r.x1 = r2.x1;
359 if(r.y1 > r2.y1) r.y1 = r2.y1;
360 return r;
361 }
362
363 typedef rect_base<int> rect_i; //----rect_i
364 typedef rect_base<float> rect_f; //----rect_f
365 typedef rect_base<double> rect_d; //----rect_d
366
367 //---------------------------------------------------------path_commands_e
368 enum path_commands_e
369 {
370 path_cmd_stop = 0, //----path_cmd_stop
371 path_cmd_move_to = 1, //----path_cmd_move_to
372 path_cmd_line_to = 2, //----path_cmd_line_to
373 path_cmd_curve3 = 3, //----path_cmd_curve3
374 path_cmd_curve4 = 4, //----path_cmd_curve4
375 path_cmd_curveN = 5, //----path_cmd_curveN
376 path_cmd_catrom = 6, //----path_cmd_catrom
377 path_cmd_ubspline = 7, //----path_cmd_ubspline
378 path_cmd_end_poly = 0x0F, //----path_cmd_end_poly
379 path_cmd_mask = 0x0F //----path_cmd_mask
380 };
381
382 //------------------------------------------------------------path_flags_e
383 enum path_flags_e
384 {
385 path_flags_none = 0, //----path_flags_none
386 path_flags_ccw = 0x10, //----path_flags_ccw
387 path_flags_cw = 0x20, //----path_flags_cw
388 path_flags_close = 0x40, //----path_flags_close
389 path_flags_mask = 0xF0 //----path_flags_mask
390 };
391
392 //---------------------------------------------------------------is_vertex
393 inline bool is_vertex(unsigned c)
394 {
395 return c >= path_cmd_move_to && c < path_cmd_end_poly;
396 }
397
398 //--------------------------------------------------------------is_drawing
399 inline bool is_drawing(unsigned c)
400 {
401 return c >= path_cmd_line_to && c < path_cmd_end_poly;
402 }
403
404 //-----------------------------------------------------------------is_stop
405 inline bool is_stop(unsigned c)
406 {
407 return c == path_cmd_stop;
408 }
409
410 //--------------------------------------------------------------is_move_to
411 inline bool is_move_to(unsigned c)
412 {
413 return c == path_cmd_move_to;
414 }
415
416 //--------------------------------------------------------------is_line_to
417 inline bool is_line_to(unsigned c)
418 {
419 return c == path_cmd_line_to;
420 }
421
422 //----------------------------------------------------------------is_curve
423 inline bool is_curve(unsigned c)
424 {
425 return c == path_cmd_curve3 || c == path_cmd_curve4;
426 }
427
428 //---------------------------------------------------------------is_curve3
429 inline bool is_curve3(unsigned c)
430 {
431 return c == path_cmd_curve3;
432 }
433
434 //---------------------------------------------------------------is_curve4
435 inline bool is_curve4(unsigned c)
436 {
437 return c == path_cmd_curve4;
438 }
439
440 //-------------------------------------------------------------is_end_poly
441 inline bool is_end_poly(unsigned c)
442 {
443 return (c & path_cmd_mask) == path_cmd_end_poly;
444 }
445
446 //----------------------------------------------------------------is_close
447 inline bool is_close(unsigned c)
448 {
449 return (c & ~(path_flags_cw | path_flags_ccw)) ==
450 (path_cmd_end_poly | path_flags_close);
451 }
452
453 //------------------------------------------------------------is_next_poly
454 inline bool is_next_poly(unsigned c)
455 {
456 return is_stop(c) || is_move_to(c) || is_end_poly(c);
457 }
458
459 //-------------------------------------------------------------------is_cw
460 inline bool is_cw(unsigned c)
461 {
462 return (c & path_flags_cw) != 0;
463 }
464
465 //------------------------------------------------------------------is_ccw
466 inline bool is_ccw(unsigned c)
467 {
468 return (c & path_flags_ccw) != 0;
469 }
470
471 //-------------------------------------------------------------is_oriented
472 inline bool is_oriented(unsigned c)
473 {
474 return (c & (path_flags_cw | path_flags_ccw)) != 0;
475 }
476
477 //---------------------------------------------------------------is_closed
478 inline bool is_closed(unsigned c)
479 {
480 return (c & path_flags_close) != 0;
481 }
482
483 //----------------------------------------------------------get_close_flag
484 inline unsigned get_close_flag(unsigned c)
485 {
486 return c & path_flags_close;
487 }
488
489 //-------------------------------------------------------clear_orientation
490 inline unsigned clear_orientation(unsigned c)
491 {
492 return c & ~(path_flags_cw | path_flags_ccw);
493 }
494
495 //---------------------------------------------------------get_orientation
496 inline unsigned get_orientation(unsigned c)
497 {
498 return c & (path_flags_cw | path_flags_ccw);
499 }
500
501 //---------------------------------------------------------set_orientation
502 inline unsigned set_orientation(unsigned c, unsigned o)
503 {
504 return clear_orientation(c) | o;
505 }
506
507 //--------------------------------------------------------------point_base
508 template<class T> struct point_base
509 {
510 typedef T value_type;
511 T x,y;
512 point_base() {}
513 point_base(T x_, T y_) : x(x_), y(y_) {}
514 };
515 typedef point_base<int> point_i; //-----point_i
516 typedef point_base<float> point_f; //-----point_f
517 typedef point_base<double> point_d; //-----point_d
518
519 //-------------------------------------------------------------vertex_base
520 template<class T> struct vertex_base
521 {
522 typedef T value_type;
523 T x,y;
524 unsigned cmd;
525 vertex_base() {}
526 vertex_base(T x_, T y_, unsigned cmd_) : x(x_), y(y_), cmd(cmd_) {}
527 };
528 typedef vertex_base<int> vertex_i; //-----vertex_i
529 typedef vertex_base<float> vertex_f; //-----vertex_f
530 typedef vertex_base<double> vertex_d; //-----vertex_d
531
532 //----------------------------------------------------------------row_info
533 template<class T> struct row_info
534 {
535 int x1, x2;
536 T* ptr;
537 row_info() {}
538 row_info(int x1_, int x2_, T* ptr_) : x1(x1_), x2(x2_), ptr(ptr_) {}
539 };
540
541 //----------------------------------------------------------const_row_info
542 template<class T> struct const_row_info
543 {
544 int x1, x2;
545 const T* ptr;
546 const_row_info() {}
547 const_row_info(int x1_, int x2_, const T* ptr_) :
548 x1(x1_), x2(x2_), ptr(ptr_) {}
549 };
550
551 //------------------------------------------------------------is_equal_eps
552 template<class T> inline bool is_equal_eps(T v1, T v2, T epsilon)
553 {
554 bool neg1 = v1 < 0.0;
555 bool neg2 = v2 < 0.0;
556
557 if (neg1 != neg2)
558 return std::fabs(v1) < epsilon && std::fabs(v2) < epsilon;
559
560 int int1, int2;
561 std::frexp(v1, &int1);
562 std::frexp(v2, &int2);
563 int min12 = int1 < int2 ? int1 : int2;
564
565 v1 = std::ldexp(v1, -min12);
566 v2 = std::ldexp(v2, -min12);
567
568 return std::fabs(v1 - v2) < epsilon;
569 }
570 }
571
572
573 #endif
574
575