123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328 |
- /*
- ucg_polygon.c
- Universal uC Color Graphics Library
-
- Copyright (c) 2014, olikraus@gmail.com
- All rights reserved.
- Redistribution and use in source and binary forms, with or without modification,
- are permitted provided that the following conditions are met:
- * Redistributions of source code must retain the above copyright notice, this list
- of conditions and the following disclaimer.
-
- * Redistributions in binary form must reproduce the above copyright notice, this
- list of conditions and the following disclaimer in the documentation and/or other
- materials provided with the distribution.
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
- CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
- INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
- */
- #include "ucg.h"
- /*===========================================*/
- /* procedures, which should not be inlined (save as much flash ROM as possible) */
- static uint8_t pge_Next(struct pg_edge_struct *pge) PG_NOINLINE;
- static uint8_t pg_inc(pg_struct *pg, uint8_t i) PG_NOINLINE;
- static uint8_t pg_dec(pg_struct *pg, uint8_t i) PG_NOINLINE;
- static void pg_expand_min_y(pg_struct *pg, pg_word_t min_y, uint8_t pge_idx) PG_NOINLINE;
- static void pg_line_init(pg_struct * const pg, uint8_t pge_index) PG_NOINLINE;
- /*===========================================*/
- /* line draw algorithm */
- static uint8_t pge_Next(struct pg_edge_struct *pge)
- {
- if ( pge->current_y >= pge->max_y )
- return 0;
-
- pge->current_x += pge->current_x_offset;
- pge->error += pge->error_offset;
- if ( pge->error > 0 )
- {
- pge->current_x += pge->x_direction;
- pge->error -= pge->height;
- }
-
- pge->current_y++;
- return 1;
- }
- /* assumes y2 > y1 */
- static void pge_Init(struct pg_edge_struct *pge, pg_word_t x1, pg_word_t y1, pg_word_t x2, pg_word_t y2)
- {
- pg_word_t dx = x2 - x1;
- pg_word_t width;
- pge->height = y2 - y1;
- pge->max_y = y2;
- pge->current_y = y1;
- pge->current_x = x1;
- if ( dx >= 0 )
- {
- pge->x_direction = 1;
- width = dx;
- pge->error = 0;
- }
- else
- {
- pge->x_direction = -1;
- width = -dx;
- pge->error = 1 - pge->height;
- }
-
- pge->current_x_offset = dx / pge->height;
- pge->error_offset = width % pge->height;
- }
- /*===========================================*/
- /* convex polygon algorithm */
- static uint8_t pg_inc(pg_struct *pg, uint8_t i)
- {
- i++;
- if ( i >= pg->cnt )
- i = 0;
- return i;
- }
- static uint8_t pg_dec(pg_struct *pg, uint8_t i)
- {
- i--;
- if ( i >= pg->cnt )
- i = pg->cnt-1;
- return i;
- }
- static void pg_expand_min_y(pg_struct *pg, pg_word_t min_y, uint8_t pge_idx)
- {
- uint8_t i = pg->pge[pge_idx].curr_idx;
- for(;;)
- {
- i = pg->pge[pge_idx].next_idx_fn(pg, i);
- if ( pg->list[i].y != min_y )
- break;
- pg->pge[pge_idx].curr_idx = i;
- }
- }
- static uint8_t pg_prepare(pg_struct *pg)
- {
- pg_word_t max_y;
- pg_word_t min_y;
- uint8_t i;
- /* setup the next index procedures */
- pg->pge[PG_RIGHT].next_idx_fn = pg_inc;
- pg->pge[PG_LEFT].next_idx_fn = pg_dec;
-
- /* search for highest and lowest point */
- max_y = pg->list[0].y;
- min_y = pg->list[0].y;
- pg->pge[PG_LEFT].curr_idx = 0;
- for( i = 1; i < pg->cnt; i++ )
- {
- if ( max_y < pg->list[i].y )
- {
- max_y = pg->list[i].y;
- }
- if ( min_y > pg->list[i].y )
- {
- pg->pge[PG_LEFT].curr_idx = i;
- min_y = pg->list[i].y;
- }
- }
- /* calculate total number of scan lines */
- pg->total_scan_line_cnt = max_y;
- pg->total_scan_line_cnt -= min_y;
-
- /* exit if polygon height is zero */
- if ( pg->total_scan_line_cnt == 0 )
- return 0;
-
- /* if the minimum y side is flat, try to find the lowest and highest x points */
- pg->pge[PG_RIGHT].curr_idx = pg->pge[PG_LEFT].curr_idx;
- pg_expand_min_y(pg, min_y, PG_RIGHT);
- pg_expand_min_y(pg, min_y, PG_LEFT);
-
- /* check if the min side is really flat (depends on the x values) */
- pg->is_min_y_not_flat = 1;
- if ( pg->list[pg->pge[PG_LEFT].curr_idx].x != pg->list[pg->pge[PG_RIGHT].curr_idx].x )
- {
- pg->is_min_y_not_flat = 0;
- }
- else
- {
- pg->total_scan_line_cnt--;
- if ( pg->total_scan_line_cnt == 0 )
- return 0;
- }
- return 1;
- }
- static void pg_hline(pg_struct *pg, ucg_t *ucg)
- {
- pg_word_t x1, x2, y;
- x1 = pg->pge[PG_LEFT].current_x;
- x2 = pg->pge[PG_RIGHT].current_x;
- y = pg->pge[PG_RIGHT].current_y;
-
- if ( y < 0 )
- return;
- if ( y >= ucg_GetHeight(ucg) )
- return;
- if ( x1 < x2 )
- {
- if ( x2 < 0 )
- return;
- if ( x1 >= ucg_GetWidth(ucg) )
- return;
- if ( x1 < 0 )
- x1 = 0;
- if ( x2 >= ucg_GetWidth(ucg) )
- x2 = ucg_GetWidth(ucg);
- ucg_DrawHLine(ucg, x1, y, x2 - x1);
- }
- else
- {
- if ( x1 < 0 )
- return;
- if ( x2 >= ucg_GetWidth(ucg) )
- return;
- if ( x2 < 0 )
- x1 = 0;
- if ( x1 >= ucg_GetWidth(ucg) )
- x1 = ucg_GetWidth(ucg);
- ucg_DrawHLine(ucg, x2, y, x1 - x2);
- }
- }
- static void pg_line_init(pg_struct * pg, uint8_t pge_index)
- {
- struct pg_edge_struct *pge = pg->pge+pge_index;
- uint8_t idx;
- pg_word_t x1;
- pg_word_t y1;
- pg_word_t x2;
- pg_word_t y2;
- idx = pge->curr_idx;
- y1 = pg->list[idx].y;
- x1 = pg->list[idx].x;
- idx = pge->next_idx_fn(pg, idx);
- y2 = pg->list[idx].y;
- x2 = pg->list[idx].x;
- pge->curr_idx = idx;
-
- pge_Init(pge, x1, y1, x2, y2);
- }
- static void pg_exec(pg_struct *pg, ucg_t *ucg)
- {
- pg_word_t i = pg->total_scan_line_cnt;
- /* first line is skipped if the min y line is not flat */
- pg_line_init(pg, PG_LEFT);
- pg_line_init(pg, PG_RIGHT);
-
- if ( pg->is_min_y_not_flat != 0 )
- {
- pge_Next(&(pg->pge[PG_LEFT]));
- pge_Next(&(pg->pge[PG_RIGHT]));
- }
- do
- {
- pg_hline(pg, ucg);
- while ( pge_Next(&(pg->pge[PG_LEFT])) == 0 )
- {
- pg_line_init(pg, PG_LEFT);
- }
- while ( pge_Next(&(pg->pge[PG_RIGHT])) == 0 )
- {
- pg_line_init(pg, PG_RIGHT);
- }
- i--;
- } while( i > 0 );
- }
- /*===========================================*/
- /* API procedures */
- void ucg_pg_ClearPolygonXY(pg_struct *pg)
- {
- pg->cnt = 0;
- }
- void ucg_pg_AddPolygonXY(pg_struct *pg, ucg_t *ucg, int16_t x, int16_t y)
- {
- if ( pg->cnt < PG_MAX_POINTS )
- {
- pg->list[pg->cnt].x = x;
- pg->list[pg->cnt].y = y;
- pg->cnt++;
- }
- }
- void ucg_pg_DrawPolygon(pg_struct *pg, ucg_t *ucg)
- {
- if ( pg_prepare(pg) == 0 )
- return;
- pg_exec(pg, ucg);
- }
- pg_struct ucg_pg;
- void ucg_ClearPolygonXY(void)
- {
- ucg_pg_ClearPolygonXY(&ucg_pg);
- }
- void ucg_AddPolygonXY(ucg_t *ucg, int16_t x, int16_t y)
- {
- ucg_pg_AddPolygonXY(&ucg_pg, ucg, x, y);
- }
- void ucg_DrawPolygon(ucg_t *ucg)
- {
- ucg_pg_DrawPolygon(&ucg_pg, ucg);
- }
- void ucg_DrawTriangle(ucg_t *ucg, int16_t x0, int16_t y0, int16_t x1, int16_t y1, int16_t x2, int16_t y2)
- {
- ucg_ClearPolygonXY();
- ucg_AddPolygonXY(ucg, x0, y0);
- ucg_AddPolygonXY(ucg, x1, y1);
- ucg_AddPolygonXY(ucg, x2, y2);
- ucg_DrawPolygon(ucg);
- }
- void ucg_DrawTetragon(ucg_t *ucg, int16_t x0, int16_t y0, int16_t x1, int16_t y1, int16_t x2, int16_t y2, int16_t x3, int16_t y3)
- {
- ucg_ClearPolygonXY();
- ucg_AddPolygonXY(ucg, x0, y0);
- ucg_AddPolygonXY(ucg, x1, y1);
- ucg_AddPolygonXY(ucg, x2, y2);
- ucg_AddPolygonXY(ucg, x3, y3);
- ucg_DrawPolygon(ucg);
- }
|