[95] | 1 | /* |
---|
[672] | 2 | * libcucul Canvas for ultrafast compositing of Unicode letters |
---|
[527] | 3 | * Copyright (c) 2002-2006 Sam Hocevar <sam@zoy.org> |
---|
[268] | 4 | * All Rights Reserved |
---|
[95] | 5 | * |
---|
[769] | 6 | * $Id: line.c 1947 2007-11-13 12:41:33Z pterjan $ |
---|
| 7 | * |
---|
[1462] | 8 | * This library is free software. It comes without any warranty, to |
---|
[1452] | 9 | * the extent permitted by applicable law. You can redistribute it |
---|
| 10 | * and/or modify it under the terms of the Do What The Fuck You Want |
---|
| 11 | * To Public License, Version 2, as published by Sam Hocevar. See |
---|
[522] | 12 | * http://sam.zoy.org/wtfpl/COPYING for more details. |
---|
[95] | 13 | */ |
---|
| 14 | |
---|
[769] | 15 | /* |
---|
[268] | 16 | * This file contains line and polyline drawing functions, with both thin |
---|
| 17 | * and thick styles. |
---|
[205] | 18 | */ |
---|
| 19 | |
---|
[95] | 20 | #include "config.h" |
---|
[859] | 21 | #include "common.h" |
---|
[95] | 22 | |
---|
[568] | 23 | #if !defined(__KERNEL__) |
---|
| 24 | # include <stdlib.h> |
---|
| 25 | #endif |
---|
[95] | 26 | |
---|
[524] | 27 | #include "cucul.h" |
---|
| 28 | #include "cucul_internals.h" |
---|
[95] | 29 | |
---|
[322] | 30 | #if !defined(_DOXYGEN_SKIP_ME) |
---|
[101] | 31 | struct line |
---|
| 32 | { |
---|
| 33 | int x1, y1; |
---|
| 34 | int x2, y2; |
---|
[810] | 35 | uint32_t ch; |
---|
| 36 | void (*draw) (cucul_canvas_t *, struct line*); |
---|
[101] | 37 | }; |
---|
[322] | 38 | #endif |
---|
[101] | 39 | |
---|
[810] | 40 | static void clip_line(cucul_canvas_t*, struct line*); |
---|
| 41 | static uint8_t clip_bits(cucul_canvas_t*, int, int); |
---|
| 42 | static void draw_solid_line(cucul_canvas_t*, struct line*); |
---|
| 43 | static void draw_thin_line(cucul_canvas_t*, struct line*); |
---|
[95] | 44 | |
---|
[773] | 45 | /** \brief Draw a line on the canvas using the given character. |
---|
[127] | 46 | * |
---|
[870] | 47 | * This function never fails. |
---|
| 48 | * |
---|
[811] | 49 | * \param cv The handle to the libcucul canvas. |
---|
[773] | 50 | * \param x1 X coordinate of the first point. |
---|
| 51 | * \param y1 Y coordinate of the first point. |
---|
| 52 | * \param x2 X coordinate of the second point. |
---|
| 53 | * \param y2 Y coordinate of the second point. |
---|
[1330] | 54 | * \param ch UTF-32 character to be used to draw the line. |
---|
[870] | 55 | * \return This function always returns 0. |
---|
[127] | 56 | */ |
---|
[870] | 57 | int cucul_draw_line(cucul_canvas_t *cv, int x1, int y1, int x2, int y2, |
---|
[1330] | 58 | unsigned long int ch) |
---|
[95] | 59 | { |
---|
[101] | 60 | struct line s; |
---|
| 61 | s.x1 = x1; |
---|
| 62 | s.y1 = y1; |
---|
| 63 | s.x2 = x2; |
---|
| 64 | s.y2 = y2; |
---|
[1330] | 65 | s.ch = ch; |
---|
[101] | 66 | s.draw = draw_solid_line; |
---|
[811] | 67 | clip_line(cv, &s); |
---|
[870] | 68 | |
---|
| 69 | return 0; |
---|
[101] | 70 | } |
---|
| 71 | |
---|
[773] | 72 | /** \brief Draw a polyline. |
---|
[257] | 73 | * |
---|
[1947] | 74 | * Draw a polyline on the canvas using the given character and coordinate |
---|
[773] | 75 | * arrays. The first and last points are not connected, hence in order to |
---|
| 76 | * draw a polygon you need to specify the starting point at the end of the |
---|
| 77 | * list as well. |
---|
| 78 | * |
---|
[870] | 79 | * This function never fails. |
---|
| 80 | * |
---|
[811] | 81 | * \param cv The handle to the libcucul canvas. |
---|
[773] | 82 | * \param x Array of X coordinates. Must have \p n + 1 elements. |
---|
| 83 | * \param y Array of Y coordinates. Must have \p n + 1 elements. |
---|
| 84 | * \param n Number of lines to draw. |
---|
[1330] | 85 | * \param ch UTF-32 character to be used to draw the lines. |
---|
[870] | 86 | * \return This function always returns 0. |
---|
[257] | 87 | */ |
---|
[870] | 88 | int cucul_draw_polyline(cucul_canvas_t *cv, int const x[], int const y[], |
---|
[1330] | 89 | int n, unsigned long int ch) |
---|
[153] | 90 | { |
---|
| 91 | int i; |
---|
| 92 | struct line s; |
---|
[1330] | 93 | s.ch = ch; |
---|
[153] | 94 | s.draw = draw_solid_line; |
---|
| 95 | |
---|
| 96 | for(i = 0; i < n; i++) |
---|
| 97 | { |
---|
| 98 | s.x1 = x[i]; |
---|
| 99 | s.y1 = y[i]; |
---|
| 100 | s.x2 = x[i+1]; |
---|
| 101 | s.y2 = y[i+1]; |
---|
[811] | 102 | clip_line(cv, &s); |
---|
[153] | 103 | } |
---|
[870] | 104 | |
---|
| 105 | return 0; |
---|
[153] | 106 | } |
---|
| 107 | |
---|
[773] | 108 | /** \brief Draw a thin line on the canvas, using ASCII art. |
---|
[127] | 109 | * |
---|
[870] | 110 | * This function never fails. |
---|
| 111 | * |
---|
[811] | 112 | * \param cv The handle to the libcucul canvas. |
---|
[773] | 113 | * \param x1 X coordinate of the first point. |
---|
| 114 | * \param y1 Y coordinate of the first point. |
---|
| 115 | * \param x2 X coordinate of the second point. |
---|
| 116 | * \param y2 Y coordinate of the second point. |
---|
[870] | 117 | * \return This function always returns 0. |
---|
[127] | 118 | */ |
---|
[870] | 119 | int cucul_draw_thin_line(cucul_canvas_t *cv, int x1, int y1, int x2, int y2) |
---|
[103] | 120 | { |
---|
| 121 | struct line s; |
---|
| 122 | s.x1 = x1; |
---|
| 123 | s.y1 = y1; |
---|
| 124 | s.x2 = x2; |
---|
| 125 | s.y2 = y2; |
---|
| 126 | s.draw = draw_thin_line; |
---|
[811] | 127 | clip_line(cv, &s); |
---|
[870] | 128 | |
---|
| 129 | return 0; |
---|
[103] | 130 | } |
---|
| 131 | |
---|
[773] | 132 | /** \brief Draw an ASCII art thin polyline. |
---|
[257] | 133 | * |
---|
[773] | 134 | * Draw a thin polyline on the canvas using the given coordinate arrays and |
---|
| 135 | * with ASCII art. The first and last points are not connected, so in order |
---|
| 136 | * to draw a polygon you need to specify the starting point at the end of |
---|
| 137 | * the list as well. |
---|
| 138 | * |
---|
[870] | 139 | * This function never fails. |
---|
| 140 | * |
---|
[811] | 141 | * \param cv The handle to the libcucul canvas. |
---|
[773] | 142 | * \param x Array of X coordinates. Must have \p n + 1 elements. |
---|
| 143 | * \param y Array of Y coordinates. Must have \p n + 1 elements. |
---|
| 144 | * \param n Number of lines to draw. |
---|
[870] | 145 | * \return This function always returns 0. |
---|
[257] | 146 | */ |
---|
[870] | 147 | int cucul_draw_thin_polyline(cucul_canvas_t *cv, int const x[], int const y[], |
---|
| 148 | int n) |
---|
[153] | 149 | { |
---|
| 150 | int i; |
---|
| 151 | struct line s; |
---|
| 152 | s.draw = draw_thin_line; |
---|
| 153 | |
---|
| 154 | for(i = 0; i < n; i++) |
---|
| 155 | { |
---|
| 156 | s.x1 = x[i]; |
---|
| 157 | s.y1 = y[i]; |
---|
| 158 | s.x2 = x[i+1]; |
---|
| 159 | s.y2 = y[i+1]; |
---|
[811] | 160 | clip_line(cv, &s); |
---|
[153] | 161 | } |
---|
[870] | 162 | |
---|
| 163 | return 0; |
---|
[153] | 164 | } |
---|
| 165 | |
---|
[129] | 166 | /* |
---|
| 167 | * XXX: The following functions are local. |
---|
| 168 | */ |
---|
| 169 | |
---|
[773] | 170 | /* Generic Cohen-Sutherland line clipping function. */ |
---|
[811] | 171 | static void clip_line(cucul_canvas_t *cv, struct line* s) |
---|
[101] | 172 | { |
---|
[95] | 173 | uint8_t bits1, bits2; |
---|
| 174 | |
---|
[811] | 175 | bits1 = clip_bits(cv, s->x1, s->y1); |
---|
| 176 | bits2 = clip_bits(cv, s->x2, s->y2); |
---|
[95] | 177 | |
---|
| 178 | if(bits1 & bits2) |
---|
| 179 | return; |
---|
| 180 | |
---|
| 181 | if(bits1 == 0) |
---|
| 182 | { |
---|
| 183 | if(bits2 == 0) |
---|
[811] | 184 | s->draw(cv, s); |
---|
[95] | 185 | else |
---|
[101] | 186 | { |
---|
| 187 | int tmp; |
---|
| 188 | tmp = s->x1; s->x1 = s->x2; s->x2 = tmp; |
---|
| 189 | tmp = s->y1; s->y1 = s->y2; s->y2 = tmp; |
---|
[811] | 190 | clip_line(cv, s); |
---|
[101] | 191 | } |
---|
[95] | 192 | |
---|
| 193 | return; |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | if(bits1 & (1<<0)) |
---|
| 197 | { |
---|
[101] | 198 | s->y1 = s->y2 - (s->x2 - 0) * (s->y2 - s->y1) / (s->x2 - s->x1); |
---|
| 199 | s->x1 = 0; |
---|
[95] | 200 | } |
---|
[165] | 201 | else if(bits1 & (1<<1)) |
---|
[95] | 202 | { |
---|
[811] | 203 | int xmax = cv->width - 1; |
---|
[101] | 204 | s->y1 = s->y2 - (s->x2 - xmax) * (s->y2 - s->y1) / (s->x2 - s->x1); |
---|
| 205 | s->x1 = xmax; |
---|
[95] | 206 | } |
---|
[165] | 207 | else if(bits1 & (1<<2)) |
---|
[95] | 208 | { |
---|
[101] | 209 | s->x1 = s->x2 - (s->y2 - 0) * (s->x2 - s->x1) / (s->y2 - s->y1); |
---|
| 210 | s->y1 = 0; |
---|
[95] | 211 | } |
---|
[165] | 212 | else if(bits1 & (1<<3)) |
---|
[95] | 213 | { |
---|
[811] | 214 | int ymax = cv->height - 1; |
---|
[101] | 215 | s->x1 = s->x2 - (s->y2 - ymax) * (s->x2 - s->x1) / (s->y2 - s->y1); |
---|
| 216 | s->y1 = ymax; |
---|
[95] | 217 | } |
---|
| 218 | |
---|
[811] | 219 | clip_line(cv, s); |
---|
[95] | 220 | } |
---|
| 221 | |
---|
[773] | 222 | /* Helper function for clip_line(). */ |
---|
[811] | 223 | static uint8_t clip_bits(cucul_canvas_t *cv, int x, int y) |
---|
[95] | 224 | { |
---|
[101] | 225 | uint8_t b = 0; |
---|
| 226 | |
---|
| 227 | if(x < 0) |
---|
| 228 | b |= (1<<0); |
---|
[811] | 229 | else if(x >= (int)cv->width) |
---|
[101] | 230 | b |= (1<<1); |
---|
| 231 | |
---|
| 232 | if(y < 0) |
---|
| 233 | b |= (1<<2); |
---|
[811] | 234 | else if(y >= (int)cv->height) |
---|
[101] | 235 | b |= (1<<3); |
---|
| 236 | |
---|
| 237 | return b; |
---|
| 238 | } |
---|
| 239 | |
---|
[773] | 240 | /* Solid line drawing function, using Bresenham's mid-point line |
---|
| 241 | * scan-conversion algorithm. */ |
---|
[811] | 242 | static void draw_solid_line(cucul_canvas_t *cv, struct line* s) |
---|
[101] | 243 | { |
---|
[103] | 244 | int x1, y1, x2, y2; |
---|
| 245 | int dx, dy; |
---|
| 246 | int xinc, yinc; |
---|
[101] | 247 | |
---|
[103] | 248 | x1 = s->x1; y1 = s->y1; x2 = s->x2; y2 = s->y2; |
---|
[95] | 249 | |
---|
[103] | 250 | dx = abs(x2 - x1); |
---|
| 251 | dy = abs(y2 - y1); |
---|
[95] | 252 | |
---|
| 253 | xinc = (x1 > x2) ? -1 : 1; |
---|
| 254 | yinc = (y1 > y2) ? -1 : 1; |
---|
| 255 | |
---|
| 256 | if(dx >= dy) |
---|
| 257 | { |
---|
| 258 | int dpr = dy << 1; |
---|
| 259 | int dpru = dpr - (dx << 1); |
---|
| 260 | int delta = dpr - dx; |
---|
| 261 | |
---|
| 262 | for(; dx>=0; dx--) |
---|
| 263 | { |
---|
[1347] | 264 | cucul_put_char(cv, x1, y1, s->ch); |
---|
[95] | 265 | if(delta > 0) |
---|
| 266 | { |
---|
| 267 | x1 += xinc; |
---|
| 268 | y1 += yinc; |
---|
| 269 | delta += dpru; |
---|
| 270 | } |
---|
| 271 | else |
---|
| 272 | { |
---|
| 273 | x1 += xinc; |
---|
| 274 | delta += dpr; |
---|
| 275 | } |
---|
| 276 | } |
---|
| 277 | } |
---|
| 278 | else |
---|
| 279 | { |
---|
| 280 | int dpr = dx << 1; |
---|
| 281 | int dpru = dpr - (dy << 1); |
---|
| 282 | int delta = dpr - dy; |
---|
| 283 | |
---|
| 284 | for(; dy >= 0; dy--) |
---|
| 285 | { |
---|
[1347] | 286 | cucul_put_char(cv, x1, y1, s->ch); |
---|
[95] | 287 | if(delta > 0) |
---|
| 288 | { |
---|
| 289 | x1 += xinc; |
---|
| 290 | y1 += yinc; |
---|
| 291 | delta += dpru; |
---|
| 292 | } |
---|
| 293 | else |
---|
| 294 | { |
---|
| 295 | y1 += yinc; |
---|
| 296 | delta += dpr; |
---|
| 297 | } |
---|
| 298 | } |
---|
| 299 | } |
---|
| 300 | } |
---|
| 301 | |
---|
[773] | 302 | /* Thin line drawing function, using Bresenham's mid-point line |
---|
| 303 | * scan-conversion algorithm and ASCII art graphics. */ |
---|
[811] | 304 | static void draw_thin_line(cucul_canvas_t *cv, struct line* s) |
---|
[103] | 305 | { |
---|
[678] | 306 | uint32_t charmapx[2], charmapy[2]; |
---|
[103] | 307 | int x1, y1, x2, y2; |
---|
| 308 | int dx, dy; |
---|
| 309 | int yinc; |
---|
| 310 | |
---|
| 311 | if(s->x2 >= s->x1) |
---|
| 312 | { |
---|
[958] | 313 | charmapx[0] = (s->y1 > s->y2) ? ',' : '`'; |
---|
| 314 | charmapx[1] = (s->y1 > s->y2) ? '\'' : '.'; |
---|
[103] | 315 | x1 = s->x1; y1 = s->y1; x2 = s->x2; y2 = s->y2; |
---|
| 316 | } |
---|
| 317 | else |
---|
| 318 | { |
---|
[958] | 319 | charmapx[0] = (s->y1 > s->y2) ? '`' : '.'; |
---|
| 320 | charmapx[1] = (s->y1 > s->y2) ? ',' : '\''; |
---|
[103] | 321 | x2 = s->x1; y2 = s->y1; x1 = s->x2; y1 = s->y2; |
---|
| 322 | } |
---|
| 323 | |
---|
| 324 | dx = abs(x2 - x1); |
---|
| 325 | dy = abs(y2 - y1); |
---|
| 326 | |
---|
| 327 | if(y1 > y2) |
---|
| 328 | { |
---|
[958] | 329 | charmapy[0] = ','; |
---|
| 330 | charmapy[1] = '\''; |
---|
[103] | 331 | yinc = -1; |
---|
| 332 | } |
---|
| 333 | else |
---|
| 334 | { |
---|
| 335 | yinc = 1; |
---|
[958] | 336 | charmapy[0] = '`'; |
---|
| 337 | charmapy[1] = '.'; |
---|
[103] | 338 | } |
---|
| 339 | |
---|
| 340 | if(dx >= dy) |
---|
| 341 | { |
---|
| 342 | int dpr = dy << 1; |
---|
| 343 | int dpru = dpr - (dx << 1); |
---|
| 344 | int delta = dpr - dx; |
---|
| 345 | int prev = 0; |
---|
| 346 | |
---|
| 347 | for(; dx>=0; dx--) |
---|
| 348 | { |
---|
| 349 | if(delta > 0) |
---|
| 350 | { |
---|
[1347] | 351 | cucul_put_char(cv, x1, y1, charmapy[1]); |
---|
[103] | 352 | x1++; |
---|
| 353 | y1 += yinc; |
---|
| 354 | delta += dpru; |
---|
| 355 | prev = 1; |
---|
| 356 | } |
---|
| 357 | else |
---|
| 358 | { |
---|
| 359 | if(prev) |
---|
[1347] | 360 | cucul_put_char(cv, x1, y1, charmapy[0]); |
---|
[103] | 361 | else |
---|
[1347] | 362 | cucul_put_char(cv, x1, y1, '-'); |
---|
[103] | 363 | x1++; |
---|
| 364 | delta += dpr; |
---|
| 365 | prev = 0; |
---|
| 366 | } |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | else |
---|
| 370 | { |
---|
| 371 | int dpr = dx << 1; |
---|
| 372 | int dpru = dpr - (dy << 1); |
---|
| 373 | int delta = dpr - dy; |
---|
| 374 | |
---|
| 375 | for(; dy >= 0; dy--) |
---|
| 376 | { |
---|
| 377 | if(delta > 0) |
---|
| 378 | { |
---|
[1347] | 379 | cucul_put_char(cv, x1, y1, charmapx[0]); |
---|
| 380 | cucul_put_char(cv, x1 + 1, y1, charmapx[1]); |
---|
[103] | 381 | x1++; |
---|
| 382 | y1 += yinc; |
---|
| 383 | delta += dpru; |
---|
| 384 | } |
---|
| 385 | else |
---|
| 386 | { |
---|
[1347] | 387 | cucul_put_char(cv, x1, y1, '|'); |
---|
[103] | 388 | y1 += yinc; |
---|
| 389 | delta += dpr; |
---|
| 390 | } |
---|
| 391 | } |
---|
| 392 | } |
---|
| 393 | } |
---|
| 394 | |
---|