git.sesse.net Git - vlc/blob - modules/video_filter/puzzle_pce.c

   1 /*****************************************************************************
   2  * puzzle_pce.c : Puzzle game filter - pieces functions
   3  *****************************************************************************
   4  * Copyright (C) 2013 Vianney Boyer
   5  * $Id$
   6  *
   7  * Author:  Vianney Boyer <vlcvboyer -at- gmail -dot- com>
   8  *
   9  * This program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  17  * GNU Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with this program; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  22  *****************************************************************************/
  23
  24 /*****************************************************************************
  25  * Preamble
  26  *****************************************************************************/
  27
  28 #ifdef HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31 #include <math.h>
  32
  33 #include <vlc_common.h>
  34 #include <vlc_plugin.h>
  35 #include <vlc_filter.h>
  36 #include <vlc_rand.h>
  37
  38 #include "filter_picture.h"
  39
  40 #include "puzzle_bezier.h"
  41 #include "puzzle_lib.h"
  42 #include "puzzle_pce.h"
  43
  44 #define SHAPES_QTY 20
  45 #define PIECE_TYPE_NBR (4*2*(1+SHAPES_QTY))
  46
  47 /*****************************************************************************
  48  * puzzle_bake_pieces_shapes: allocate and compute shapes
  49  *****************************************************************************/
  50 int puzzle_bake_pieces_shapes( filter_t *p_filter)
  51 {
  52 /* note:
  53  *   piece_shape_t **ps_pieces_shapes;  * array [each piece type (PCE_TYPE_NBR  * 4 ( * negative ): top, left,right,btm)][each plane] of piece definition
  54  *   0 => left border
  55  *   1 => left border (negative, never used)
  56  *   2 => top border
  57  *   .....
  58  *   8 => bezier left
  59  *   9 => bezier left negative
  60  *  10 => bezier top
  61  *  11 => bezier top negative
  62  *  12 => bezier btm
  63  *  13 => bezier btm negative
  64  *  14 => bezier right
  65  *  15 => bezier right negative
  66  *  .....
  67  */
  68
  69     filter_sys_t *p_sys = p_filter->p_sys;
  70
  71     puzzle_free_ps_pieces_shapes(p_filter);
  72     p_sys->ps_pieces_shapes = malloc( sizeof( piece_shape_t *) * PIECE_TYPE_NBR );
  73     if( !p_sys->ps_pieces_shapes )
  74         return VLC_ENOMEM;
  75
  76     for (int32_t i_piece = 0; i_piece < PIECE_TYPE_NBR; i_piece++) {
  77         p_sys->ps_pieces_shapes[i_piece] = malloc( sizeof( piece_shape_t) * p_sys->s_allocated.i_planes );
  78         if( !p_sys->ps_pieces_shapes[i_piece] )
  79             return VLC_ENOMEM;
  80         for (uint8_t i_plane = 0; i_plane < p_filter->p_sys->s_allocated.i_planes; i_plane++) {
  81             p_sys->ps_pieces_shapes[i_piece][i_plane].i_row_nbr = 0;
  82             p_sys->ps_pieces_shapes[i_piece][i_plane].ps_piece_shape_row = NULL;
  83         }
  84     }
  85
  86     int32_t i_currect_shape = 0;
  87
  88     for (uint8_t i_plane = 0; i_plane < p_filter->p_sys->s_allocated.i_planes; i_plane++) {
  89         int i_ret;
  90         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+0][i_plane], i_plane, puzzle_SHAPE_LEFT);
  91         if (i_ret != VLC_SUCCESS) return i_ret;
  92         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+1][i_plane], i_plane, puzzle_SHAPE_LEFT);
  93         if (i_ret != VLC_SUCCESS) return i_ret;
  94         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+2][i_plane], i_plane, puzzle_SHAPE_TOP);
  95         if (i_ret != VLC_SUCCESS) return i_ret;
  96         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+3][i_plane], i_plane, puzzle_SHAPE_TOP);
  97         if (i_ret != VLC_SUCCESS) return i_ret;
  98         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+4][i_plane], i_plane, puzzle_SHAPE_BTM);
  99         if (i_ret != VLC_SUCCESS) return i_ret;
 100         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+5][i_plane], i_plane, puzzle_SHAPE_BTM);
 101         if (i_ret != VLC_SUCCESS) return i_ret;
 102         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+6][i_plane], i_plane, puzzle_SHAPE_RIGHT);
 103         if (i_ret != VLC_SUCCESS) return i_ret;
 104         i_ret = puzzle_generate_sect_border( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+7][i_plane], i_plane, puzzle_SHAPE_RIGHT);
 105         if (i_ret != VLC_SUCCESS) return i_ret;
 106     }
 107
 108     i_currect_shape += 8;
 109
 110     int32_t i_width = p_sys->ps_desk_planes[0].i_pce_max_width;
 111     int32_t i_lines = p_sys->ps_desk_planes[0].i_pce_max_lines;
 112
 113     for (int32_t i_shape = 0; i_shape<SHAPES_QTY; i_shape++) {
 114
 115         point_t *ps_scale_pts_H = puzzle_scale_curve_H(i_width, i_lines,     7, p_sys->ps_bezier_pts_H[i_shape], p_sys->s_allocated.i_shape_size);
 116         point_t *ps_scale_pts_V = puzzle_H_2_scale_curve_V(i_width, i_lines, 7, p_sys->ps_bezier_pts_H[i_shape], p_sys->s_allocated.i_shape_size);
 117         point_t *ps_neg_pts_H =   puzzle_curve_H_2_negative(7, ps_scale_pts_H);
 118         point_t *ps_neg_pts_V =   puzzle_curve_V_2_negative(7, ps_scale_pts_V);
 119
 120         if (!ps_scale_pts_H || !ps_scale_pts_V || !ps_neg_pts_H || !ps_neg_pts_V) {
 121             free(ps_scale_pts_H);
 122             free(ps_scale_pts_V);
 123             free(ps_neg_pts_H);
 124             free(ps_neg_pts_V);
 125             return VLC_EGENERIC;
 126         }
 127
 128         int i_ret;
 129         for (uint8_t i_plane = 0; i_plane < p_filter->p_sys->s_allocated.i_planes; i_plane++) {
 130             i_ret = puzzle_generate_sect_bezier( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape][i_plane],   7, ps_scale_pts_V, i_plane, puzzle_SHAPE_LEFT);
 131             if (i_ret != VLC_SUCCESS) break;
 132             i_ret = puzzle_generate_sect_bezier( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+1][i_plane], 7, ps_neg_pts_V,   i_plane, puzzle_SHAPE_LEFT);
 133             if (i_ret != VLC_SUCCESS) break;
 134             i_ret = puzzle_generate_sect_bezier(  p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+2][i_plane], 7, ps_scale_pts_H, i_plane, puzzle_SHAPE_TOP);
 135             if (i_ret != VLC_SUCCESS) break;
 136             i_ret = puzzle_generate_sect_bezier(  p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+3][i_plane], 7, ps_neg_pts_H,   i_plane, puzzle_SHAPE_TOP);
 137             if (i_ret != VLC_SUCCESS) break;
 138
 139             i_ret = puzzle_generate_sectTop2Btm( p_filter,    &p_sys->ps_pieces_shapes[i_currect_shape+4][i_plane], &p_sys->ps_pieces_shapes[i_currect_shape+2][i_plane], i_plane);
 140             if (i_ret != VLC_SUCCESS) break;
 141             i_ret = puzzle_generate_sectTop2Btm( p_filter,    &p_sys->ps_pieces_shapes[i_currect_shape+5][i_plane], &p_sys->ps_pieces_shapes[i_currect_shape+3][i_plane], i_plane);
 142             if (i_ret != VLC_SUCCESS) break;
 143             i_ret = puzzle_generate_sectLeft2Right( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+6][i_plane], &p_sys->ps_pieces_shapes[i_currect_shape][i_plane],   i_plane);
 144             if (i_ret != VLC_SUCCESS) break;
 145             i_ret = puzzle_generate_sectLeft2Right( p_filter, &p_sys->ps_pieces_shapes[i_currect_shape+7][i_plane], &p_sys->ps_pieces_shapes[i_currect_shape+1][i_plane], i_plane);
 146             if (i_ret != VLC_SUCCESS) break;
 147         }
 148
 149         free(ps_scale_pts_H);
 150         free(ps_scale_pts_V);
 151         free(ps_neg_pts_H);
 152         free(ps_neg_pts_V);
 153
 154         if (i_ret != VLC_SUCCESS) return i_ret;
 155
 156         i_currect_shape += 8;
 157     }
 158
 159     p_sys->b_shape_init = true;
 160
 161     return VLC_SUCCESS;
 162 }
 163
 164 /* free allocated shapes data */
 165 void puzzle_free_ps_pieces_shapes( filter_t *p_filter)
 166 {
 167     filter_sys_t *p_sys = p_filter->p_sys;
 168
 169     if (p_sys->ps_pieces_shapes == NULL)
 170         return;
 171
 172     for (int32_t p = 0; p < p_sys->s_allocated.i_piece_types; p++) {
 173         for (uint8_t i_plane = 0; i_plane < p_sys->s_allocated.i_planes; i_plane++) {
 174             for (int32_t r = 0; r < p_sys->ps_pieces_shapes[p][i_plane].i_row_nbr; r++)
 175                 free( p_sys->ps_pieces_shapes[p][i_plane].ps_piece_shape_row[r].ps_row_section );
 176             free( p_sys->ps_pieces_shapes[p][i_plane].ps_piece_shape_row );
 177         }
 178         free( p_sys->ps_pieces_shapes[p] );
 179     }
 180     free( p_sys->ps_pieces_shapes );
 181     p_sys->ps_pieces_shapes = NULL;
 182 }
 183
 184 /*****************************************************************************
 185  * puzzle_find_piece: use piece corners to find the piece selected
 186  *                    by mouse cursor
 187  *****************************************************************************/
 188 int puzzle_find_piece( filter_t *p_filter, int32_t i_x, int32_t i_y, int32_t i_except) {
 189     filter_sys_t *p_sys = p_filter->p_sys;
 190
 191     for (uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++) {
 192         piece_t *ps_current_piece = &p_sys->ps_pieces[i];
 193         if (( ps_current_piece->i_min_x <= i_x ) &&
 194             ( ps_current_piece->i_max_x >= i_x ) &&
 195             ( ps_current_piece->i_min_y <= i_y ) &&
 196             ( ps_current_piece->i_max_y  >= i_y ) &&
 197             ( (int32_t)i != i_except ) )
 198         {
 199             return i;
 200         }
 201     }
 202     return -1;
 203 }
 204
 205 /*****************************************************************************
 206  * puzzle_calculate_corners: calculate corners location & regen geometry data
 207  *****************************************************************************/
 208 void puzzle_calculate_corners( filter_t *p_filter,  int32_t i_piece )
 209 {
 210     filter_sys_t *p_sys = p_filter->p_sys;
 211     piece_t *ps_piece = &p_sys->ps_pieces[i_piece];
 212
 213     switch ( ps_piece->i_actual_angle)
 214     {
 215       case 0:
 216         ps_piece->i_step_x_x = ps_piece->i_actual_mirror;
 217         ps_piece->i_step_x_y = 0;
 218         ps_piece->i_step_y_y = 1;
 219         ps_piece->i_step_y_x = 0;
 220         break;
 221       case 1:
 222         ps_piece->i_step_x_x = 0;
 223         ps_piece->i_step_x_y = -ps_piece->i_actual_mirror; /* x offset on original pict creates negative y offset on desk */
 224         ps_piece->i_step_y_y = 0;
 225         ps_piece->i_step_y_x = 1;
 226         break;
 227       case 2:
 228         ps_piece->i_step_x_x = -ps_piece->i_actual_mirror;
 229         ps_piece->i_step_x_y = 0;
 230         ps_piece->i_step_y_y = -1;
 231         ps_piece->i_step_y_x = 0;
 232         break;
 233       case 3:
 234         ps_piece->i_step_x_x = 0;
 235         ps_piece->i_step_x_y = ps_piece->i_actual_mirror;
 236         ps_piece->i_step_y_y = 0;
 237         ps_piece->i_step_y_x = -1;
 238         break;
 239     }
 240
 241     /* regen geometry */
 242     for (uint8_t i_plane = 1; i_plane < p_sys->s_allocated.i_planes; i_plane++) {
 243         ps_piece->ps_piece_in_plane[i_plane].i_actual_x =
 244             ps_piece->ps_piece_in_plane[0].i_actual_x * p_sys->ps_desk_planes[i_plane].i_width / p_sys->ps_desk_planes[0].i_width;
 245         ps_piece->ps_piece_in_plane[i_plane].i_actual_y =
 246             ps_piece->ps_piece_in_plane[0].i_actual_y * p_sys->ps_desk_planes[i_plane].i_lines / p_sys->ps_desk_planes[0].i_lines;
 247     }
 248
 249     /* regen location of grabed piece's corners */
 250     int32_t i_width = ps_piece->ps_piece_in_plane[0].i_width;
 251     int32_t i_lines = ps_piece->ps_piece_in_plane[0].i_lines;
 252
 253     ps_piece->i_TLx = ps_piece->ps_piece_in_plane[0].i_actual_x;
 254     ps_piece->i_TLy = ps_piece->ps_piece_in_plane[0].i_actual_y;
 255     ps_piece->i_TRx = ps_piece->i_TLx + ( i_width - 1 ) * ps_piece->i_step_x_x;
 256     ps_piece->i_TRy = ps_piece->i_TLy + ( i_width - 1 ) * ps_piece->i_step_x_y;
 257     ps_piece->i_BRx = ps_piece->i_TLx + ( i_width - 1 ) * ps_piece->i_step_x_x + ( i_lines - 1 ) * ps_piece->i_step_y_x;
 258     ps_piece->i_BRy = ps_piece->i_TLy + ( i_width - 1 ) * ps_piece->i_step_x_y + ( i_lines - 1 ) * ps_piece->i_step_y_y;
 259     ps_piece->i_BLx = ps_piece->i_TLx + ( i_lines - 1 ) * ps_piece->i_step_y_x;
 260     ps_piece->i_BLy = ps_piece->i_TLy + ( i_lines - 1 ) * ps_piece->i_step_y_y;
 261
 262     ps_piece->i_max_x = __MAX( __MAX( ps_piece->i_TLx, ps_piece->i_TRx ), __MAX( ps_piece->i_BLx, ps_piece->i_BRx ) );
 263     ps_piece->i_min_x = __MIN( __MIN( ps_piece->i_TLx, ps_piece->i_TRx ), __MIN( ps_piece->i_BLx, ps_piece->i_BRx ) );
 264     ps_piece->i_max_y = __MAX( __MAX( ps_piece->i_TLy, ps_piece->i_TRy ), __MAX( ps_piece->i_BLy, ps_piece->i_BRy ) );
 265     ps_piece->i_min_y = __MIN( __MIN( ps_piece->i_TLy, ps_piece->i_TRy ), __MIN( ps_piece->i_BLy, ps_piece->i_BRy ) );
 266
 267     ps_piece->i_center_x = ( ps_piece->i_max_x + ps_piece->i_min_x ) / 2;
 268     ps_piece->i_center_y = ( ps_piece->i_max_y + ps_piece->i_min_y ) / 2;
 269
 270     int32_t pce_overlap = puzzle_find_piece( p_filter, ps_piece->i_center_x, ps_piece->i_center_y, i_piece);
 271
 272     if ( ( pce_overlap != NO_PCE ) && ( p_sys->pi_group_qty[ps_piece->i_group_ID] == 1 ) )
 273         ps_piece->b_overlap = true;
 274 }
 275
 276 /*****************************************************************************
 277  * rotate piece when user click on mouse
 278  *****************************************************************************/
 279 void puzzle_rotate_pce( filter_t *p_filter, int32_t i_piece, int8_t i_rotate_mirror, int32_t i_center_x, int32_t i_center_y, bool b_avoid_mirror )
 280 {
 281     filter_sys_t *p_sys = p_filter->p_sys;
 282     piece_t *ps_piece = &p_sys->ps_pieces[i_piece];
 283
 284     if ( p_sys->s_current_param.i_rotate == 0 )
 285         return;
 286
 287     if ( p_sys->s_current_param.i_rotate == 1 && (i_rotate_mirror != 2) )
 288         return;
 289
 290     for ( uint8_t i=0; i < abs( i_rotate_mirror ); i++) {
 291         int32_t i_tempx, i_tempy;
 292
 293         /* piece has to be rotated by 90° */
 294         if ( i_rotate_mirror > 0 ) {
 295             ps_piece->i_actual_angle++;
 296             ps_piece->i_actual_angle &= 0x03;
 297
 298             i_tempx = -( i_center_y - ps_piece->ps_piece_in_plane[0].i_actual_y ) + i_center_x;
 299             i_tempy = +( i_center_x - ps_piece->ps_piece_in_plane[0].i_actual_x ) + i_center_y;
 300         }
 301         else {
 302             ps_piece->i_actual_angle--;
 303             ps_piece->i_actual_angle &= 0x03;
 304
 305             i_tempx = +( i_center_y - ps_piece->ps_piece_in_plane[0].i_actual_y ) + i_center_x;
 306             i_tempy = -( i_center_x - ps_piece->ps_piece_in_plane[0].i_actual_x ) + i_center_y;
 307         }
 308
 309         ps_piece->ps_piece_in_plane[0].i_actual_x = i_tempx;
 310         ps_piece->ps_piece_in_plane[0].i_actual_y = i_tempy;
 311
 312         if ( ps_piece->i_actual_angle == 0 && p_sys->s_current_param.i_rotate == 3 && !b_avoid_mirror ) {
 313             ps_piece->ps_piece_in_plane[0].i_actual_x = 2 * i_center_x - ps_piece->ps_piece_in_plane[0].i_actual_x;
 314             ps_piece->i_actual_mirror *= -1;
 315         }
 316         puzzle_calculate_corners( p_filter, i_piece );
 317     }
 318 }
 319
 320 /*****************************************************************************
 321  * move group of joined pieces when user drag'n drop it with mouse
 322  *****************************************************************************/
 323 void puzzle_move_group( filter_t *p_filter, int32_t i_piece, int32_t i_dx, int32_t i_dy)
 324 {
 325     filter_sys_t *p_sys = p_filter->p_sys;
 326     uint32_t i_group_ID = p_sys->ps_pieces[i_piece].i_group_ID;
 327     for (uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++) {
 328         piece_t *ps_piece = &p_sys->ps_pieces[i];
 329         if (ps_piece->i_group_ID == i_group_ID) {
 330             ps_piece->b_finished = false;
 331             ps_piece->ps_piece_in_plane[0].i_actual_x += i_dx;
 332             ps_piece->ps_piece_in_plane[0].i_actual_y += i_dy;
 333
 334             puzzle_calculate_corners( p_filter, i );
 335         }
 336     }
 337 }
 338
 339 /*****************************************************************************
 340  * draw straight rectangular piece in the specified plane
 341  *****************************************************************************/
 342 void puzzle_drw_basic_pce_in_plane( filter_t *p_filter, picture_t *p_pic_in, picture_t *p_pic_out, uint8_t i_plane, piece_t *ps_piece)
 343 {
 344     /* basic version rectangular & angle = 0 */
 345     filter_sys_t *p_sys = p_filter->p_sys;
 346
 347     if ((p_sys->ps_puzzle_array == NULL) || (p_sys->ps_pieces == NULL) || (ps_piece == NULL))
 348         return;
 349
 350     const int32_t i_src_pitch    = p_pic_in->p[i_plane].i_pitch;
 351     const int32_t i_dst_pitch    = p_pic_out->p[i_plane].i_pitch;
 352     const int32_t i_src_width    = p_pic_in->p[i_plane].i_pitch / p_pic_in->p[i_plane].i_pixel_pitch;
 353     const int32_t i_dst_width    = p_pic_out->p[i_plane].i_pitch / p_pic_out->p[i_plane].i_pixel_pitch;
 354     const int32_t i_pixel_pitch  = p_pic_out->p[i_plane].i_pixel_pitch;
 355     const int32_t i_src_visible_lines    = p_pic_in->p[i_plane].i_visible_lines;
 356     const int32_t i_dst_visible_lines    = p_pic_out->p[i_plane].i_visible_lines;
 357     uint8_t *p_src = p_pic_in->p[i_plane].p_pixels;
 358     uint8_t *p_dst = p_pic_out->p[i_plane].p_pixels;
 359
 360     const int32_t i_desk_start_x = ps_piece->ps_piece_in_plane[i_plane].i_actual_x;
 361     const int32_t i_desk_start_y = ps_piece->ps_piece_in_plane[i_plane].i_actual_y;
 362     const int32_t i_pic_start_x = ps_piece->ps_piece_in_plane[i_plane].i_original_x;
 363     const int32_t i_pic_start_y = ps_piece->ps_piece_in_plane[i_plane].i_original_y;
 364     const int32_t i_width = ps_piece->ps_piece_in_plane[i_plane].i_width;
 365     const int32_t i_lines = ps_piece->ps_piece_in_plane[i_plane].i_lines;
 366
 367     const int32_t i_ofs_x   =           __MAX(0, __MAX(-i_desk_start_x,-i_pic_start_x));
 368     const int32_t i_count_x = i_width - __MAX(0, __MAX(i_desk_start_x + i_width - i_dst_width, i_pic_start_x + i_width - i_src_width ));
 369     const int32_t i_ofs_y   =           __MAX(0, __MAX(-i_desk_start_y,-i_pic_start_y));
 370     const int32_t i_count_y = i_lines - __MAX(0, __MAX(i_desk_start_y + i_lines - i_dst_visible_lines, i_pic_start_y + i_lines - i_src_visible_lines ));
 371
 372     for (int32_t i_y = i_ofs_y; i_y < i_count_y; i_y++) {
 373         memcpy( p_dst + (i_desk_start_y + i_y) * i_dst_pitch + ( i_desk_start_x + i_ofs_x ) * i_pixel_pitch,
 374             p_src + (i_pic_start_y + i_y) * i_src_pitch + ( i_pic_start_x + i_ofs_x ) * i_pixel_pitch,
 375             ( i_count_x - i_ofs_x ) * i_pixel_pitch );
 376     }
 377
 378     return;
 379 }
 380
 381 /*****************************************************************************
 382  * draw oriented rectangular piece in the specified plane
 383  *****************************************************************************/
 384 void puzzle_drw_adv_pce_in_plane( filter_t *p_filter, picture_t *p_pic_in, picture_t *p_pic_out, uint8_t i_plane, piece_t *ps_piece)
 385 {
 386     /* here we still have rectangular shape but angle is not 0 */
 387     filter_sys_t *p_sys = p_filter->p_sys;
 388
 389     if ((p_sys->ps_puzzle_array == NULL) || (p_sys->ps_pieces == NULL) || (ps_piece == NULL))
 390         return;
 391
 392     const int32_t i_src_pitch    = p_pic_in->p[i_plane].i_pitch;
 393     const int32_t i_dst_pitch    = p_pic_out->p[i_plane].i_pitch;
 394     const int32_t i_src_width    = p_pic_in->p[i_plane].i_pitch / p_pic_in->p[i_plane].i_pixel_pitch;
 395     const int32_t i_dst_width    = p_pic_out->p[i_plane].i_pitch / p_pic_out->p[i_plane].i_pixel_pitch;
 396     const int32_t i_pixel_pitch  = p_pic_out->p[i_plane].i_pixel_pitch;
 397     const int32_t i_src_visible_lines    = p_pic_in->p[i_plane].i_visible_lines;
 398     const int32_t i_dst_visible_lines    = p_pic_out->p[i_plane].i_visible_lines;
 399     uint8_t *p_src = p_pic_in->p[i_plane].p_pixels;
 400     uint8_t *p_dst = p_pic_out->p[i_plane].p_pixels;
 401
 402     const int32_t i_desk_start_x = ps_piece->ps_piece_in_plane[i_plane].i_actual_x;
 403     const int32_t i_desk_start_y = ps_piece->ps_piece_in_plane[i_plane].i_actual_y;
 404     const int32_t i_pic_start_x = ps_piece->ps_piece_in_plane[i_plane].i_original_x;
 405     const int32_t i_pic_start_y = ps_piece->ps_piece_in_plane[i_plane].i_original_y;
 406     const int32_t i_width = ps_piece->ps_piece_in_plane[i_plane].i_width;
 407     const int32_t i_lines = ps_piece->ps_piece_in_plane[i_plane].i_lines;
 408
 409     for (int32_t i_y = 0; i_y < i_lines; i_y++) {
 410         int32_t i_current_src_y = i_pic_start_y + i_y;
 411
 412         if ( ( i_current_src_y >= 0 ) && ( i_current_src_y < i_src_visible_lines ) ) {
 413             for (int32_t i_x = 0; i_x < i_width; i_x++) {
 414                 int32_t i_current_dst_x = i_desk_start_x + i_x * ps_piece->i_step_x_x + i_y * ps_piece->i_step_y_x;
 415                 int32_t i_current_dst_y = i_desk_start_y + i_x * ps_piece->i_step_x_y + i_y * ps_piece->i_step_y_y;
 416                 int32_t i_current_src_x = i_pic_start_x + i_x;
 417
 418                 if ( ( i_current_dst_x  >= 0 ) && ( i_current_src_x >= 0 )
 419                         && ( i_current_dst_x  < i_dst_width ) && ( i_current_src_x < i_src_width )
 420                         && ( i_current_dst_y >= 0 ) && ( i_current_dst_y < i_dst_visible_lines ) )
 421                 {
 422                     memcpy( p_dst + i_current_dst_y * i_dst_pitch + i_current_dst_x * i_pixel_pitch,
 423                             p_src + i_current_src_y * i_src_pitch + i_current_src_x * i_pixel_pitch,
 424                            i_pixel_pitch );
 425                 }
 426             }
 427         }
 428     }
 429
 430     return;
 431 }
 432
 433 /*****************************************************************************
 434  * draw complex shape in the specified plane
 435  *****************************************************************************/
 436 void puzzle_drw_complex_pce_in_plane( filter_t *p_filter, picture_t *p_pic_in, picture_t *p_pic_out, uint8_t i_plane, piece_t *ps_piece, uint32_t i_pce)
 437 {
 438     /* "puzzle" shape and maybe angle != 0 */
 439     filter_sys_t *p_sys = p_filter->p_sys;
 440
 441     if ((p_sys->ps_puzzle_array == NULL) || (p_sys->ps_pieces == NULL) || (ps_piece == NULL))
 442         return;
 443
 444     const int32_t i_src_pitch    = p_pic_in->p[i_plane].i_pitch;
 445     const int32_t i_dst_pitch    = p_pic_out->p[i_plane].i_pitch;
 446     const int32_t i_src_width    = p_pic_in->p[i_plane].i_pitch / p_pic_in->p[i_plane].i_pixel_pitch;
 447     const int32_t i_dst_width    = p_pic_out->p[i_plane].i_pitch / p_pic_out->p[i_plane].i_pixel_pitch;
 448     const int32_t i_pixel_pitch  = p_pic_out->p[i_plane].i_pixel_pitch;
 449     const int32_t i_src_visible_lines    = p_pic_in->p[i_plane].i_visible_lines;
 450     const int32_t i_dst_visible_lines    = p_pic_out->p[i_plane].i_visible_lines;
 451     uint8_t *p_src = p_pic_in->p[i_plane].p_pixels;
 452     uint8_t *p_dst = p_pic_out->p[i_plane].p_pixels;
 453
 454     const int32_t i_desk_start_x = ps_piece->ps_piece_in_plane[i_plane].i_actual_x;
 455     const int32_t i_desk_start_y = ps_piece->ps_piece_in_plane[i_plane].i_actual_y;
 456     const int32_t i_pic_start_x = ps_piece->ps_piece_in_plane[i_plane].i_original_x;
 457     const int32_t i_pic_start_y = ps_piece->ps_piece_in_plane[i_plane].i_original_y;
 458
 459     piece_shape_t *ps_top_shape =   &p_sys->ps_pieces_shapes[ps_piece->i_top_shape][i_plane];
 460     piece_shape_t *ps_btm_shape =   &p_sys->ps_pieces_shapes[ps_piece->i_btm_shape][i_plane];
 461     piece_shape_t *ps_right_shape = &p_sys->ps_pieces_shapes[ps_piece->i_right_shape][i_plane];
 462     piece_shape_t *ps_left_shape =  &p_sys->ps_pieces_shapes[ps_piece->i_left_shape][i_plane];
 463     piece_shape_t *ps_shape;
 464
 465     int32_t i_min_y = ps_top_shape->i_first_row_offset;
 466     int32_t i_max_y = ps_btm_shape->i_first_row_offset + ps_btm_shape->i_row_nbr - 1;
 467
 468     for (int32_t i_y = i_min_y; i_y <= i_max_y; i_y++) {
 469         int32_t i_current_src_y = i_pic_start_y + i_y;
 470
 471         if ( ( i_current_src_y >= 0 ) && ( i_current_src_y < i_src_visible_lines ) ) {
 472             int32_t i_sect_start_x = 0;
 473
 474             /* process each sub shape (each quarter) */
 475             for (int8_t i_shape=0; i_shape < 4; i_shape++) {
 476                 switch ( i_shape )
 477                 {
 478                   case 0:
 479                     ps_shape = ps_left_shape;
 480                     break;
 481                   case 1:
 482                     ps_shape = ps_top_shape;
 483                     break;
 484                   case 2:
 485                     ps_shape = ps_btm_shape;
 486                     break;
 487                   case 3:
 488                     ps_shape = ps_right_shape;
 489                     break;
 490                 }
 491
 492                 int32_t i_r = i_y - ps_shape->i_first_row_offset;
 493
 494                 if (i_r <0 || i_r >= ps_shape->i_row_nbr)
 495                     continue;
 496
 497                 piece_shape_row_t *ps_piece_shape_row = &ps_shape->ps_piece_shape_row[i_r];
 498
 499                 for (int32_t i_s = 0; i_s < ps_piece_shape_row->i_section_nbr; i_s++) {
 500                     uint8_t i_type = ps_piece_shape_row->ps_row_section[i_s].i_type;
 501                     int32_t i_width = ps_piece_shape_row->ps_row_section[i_s].i_width;
 502                     if (i_type == 0) {
 503                         /* copy pixel line from input image to puzzle desk */
 504                         for (int32_t i_x = 0; i_x < i_width; i_x++) {
 505                             int32_t i_current_dst_x = i_desk_start_x + (i_sect_start_x + i_x) * ps_piece->i_step_x_x + i_y * ps_piece->i_step_y_x;
 506                             int32_t i_current_dst_y = i_desk_start_y + (i_sect_start_x + i_x) * ps_piece->i_step_x_y + i_y * ps_piece->i_step_y_y;
 507                             int32_t i_current_src_x = i_pic_start_x + (i_sect_start_x + i_x);
 508
 509                             if (    i_current_dst_x < 0 || i_current_dst_x >= i_dst_width
 510                                  || i_current_src_x < 0 || i_current_src_x >= i_src_width
 511                                  || i_current_dst_y < 0 || i_current_dst_y >= i_dst_visible_lines )
 512                                 continue;
 513
 514                             memcpy( p_dst + i_current_dst_y * i_dst_pitch + i_current_dst_x * i_pixel_pitch,
 515                                     p_src + i_current_src_y * i_src_pitch + i_current_src_x * i_pixel_pitch,
 516                                     i_pixel_pitch );
 517
 518                             /* Check if mouse pointer is over this pixel
 519                              * Yes: set i_pointed_pce = current drawn piece
 520                              */
 521                             if ((i_plane == 0)  && (p_sys->i_mouse_x == i_current_dst_x )
 522                                                 && (p_sys->i_mouse_y == i_current_dst_y ))
 523                                 p_sys->i_pointed_pce = i_pce;
 524                         }
 525                     }
 526                     i_sect_start_x += i_width;
 527                 }
 528             }
 529         }
 530     }
 531
 532     return;
 533 }
 534
 535 /*****************************************************************************
 536  * draw all puzzle pieces on the desk
 537  *****************************************************************************/
 538 void puzzle_draw_pieces( filter_t *p_filter, picture_t *p_pic_in, picture_t *p_pic_out)
 539 {
 540     filter_sys_t *p_sys = p_filter->p_sys;
 541
 542     if ((p_sys->ps_puzzle_array == NULL) || (p_sys->ps_pieces == NULL))
 543         return;
 544
 545     for( uint8_t i_plane = 0; i_plane < p_pic_out->i_planes; i_plane++ ) {
 546         for ( int32_t i = p_sys->s_allocated.i_pieces_nbr-1; i >= 0 ; i-- ) {
 547             piece_t *ps_piece = &p_sys->ps_pieces[i];
 548
 549             if (!p_sys->s_current_param.b_advanced
 550                     || (ps_piece->i_actual_mirror == 1 && ps_piece->i_actual_angle == 0
 551                     && p_sys->s_current_param.i_shape_size == 0))
 552             {
 553                 puzzle_drw_basic_pce_in_plane(p_filter, p_pic_in, p_pic_out, i_plane, ps_piece);
 554             }
 555             else if ( ( p_sys->s_current_param.i_shape_size == 0)  || !p_sys->b_shape_init
 556                     || (p_sys->ps_pieces_shapes == NULL) || (!p_sys->b_shape_init) )
 557             {
 558                 puzzle_drw_adv_pce_in_plane(p_filter, p_pic_in, p_pic_out, i_plane, ps_piece);
 559             }
 560             else {
 561                 puzzle_drw_complex_pce_in_plane(p_filter, p_pic_in, p_pic_out, i_plane, ps_piece, i);
 562             }
 563         }
 564     }
 565
 566     return;
 567 }
 568
 569 /*****************************************************************************
 570  * when generating shape data: determine limit between sectors to be drawn
 571  *****************************************************************************/
 572 int32_t puzzle_diagonal_limit( filter_t *p_filter, int32_t i_y, bool b_left, uint8_t i_plane )
 573 {
 574     filter_sys_t *p_sys = p_filter->p_sys;
 575
 576     if (b_left ^ (i_y >= p_sys->ps_desk_planes[i_plane].i_pce_max_lines / 2))
 577         return ( i_y * p_sys->ps_desk_planes[i_plane].i_pce_max_width) / p_sys->ps_desk_planes[i_plane].i_pce_max_lines;
 578     else
 579         return p_sys->ps_desk_planes[i_plane].i_pce_max_width - ( ( i_y * p_sys->ps_desk_planes[i_plane].i_pce_max_width) / p_sys->ps_desk_planes[i_plane].i_pce_max_lines);
 580 }
 581
 582 #define MAX_SECT 10
 583
 584 /*****************************************************************************
 585  * generate data which will be used to draw each line of a piece sector with
 586  *       flat border
 587  *****************************************************************************/
 588 int puzzle_generate_sect_border( filter_t *p_filter, piece_shape_t *ps_piece_shape, uint8_t i_plane, uint8_t i_border)
 589 {
 590     /* generate data required to draw a sector of border puzzle piece */
 591     if (!ps_piece_shape)
 592         return VLC_EGENERIC;
 593
 594     filter_sys_t *p_sys = p_filter->p_sys;
 595
 596     int32_t i_width = p_sys->ps_desk_planes[i_plane].i_pce_max_width;
 597     int32_t i_lines = p_sys->ps_desk_planes[i_plane].i_pce_max_lines;
 598
 599     /* process each horizontal pixel lines */
 600     int32_t i_min_y = (i_border != puzzle_SHAPE_BTM) ? 0 : floor( i_lines / 2 );
 601
 602     int32_t i_nb_y = (i_border != puzzle_SHAPE_TOP)?
 603                         (i_lines - i_min_y) : (i_lines /2 - i_min_y);
 604
 605     /* allocate memory */
 606     ps_piece_shape->i_row_nbr = i_nb_y;
 607     ps_piece_shape->i_first_row_offset = i_min_y;
 608     ps_piece_shape->ps_piece_shape_row = malloc( sizeof( piece_shape_row_t ) * i_nb_y );
 609     if (!ps_piece_shape->ps_piece_shape_row)
 610         return VLC_ENOMEM;
 611
 612     for (int32_t i_y = i_min_y; i_y < i_nb_y + i_min_y; i_y++) {
 613         uint8_t i_sect = 0;
 614         int32_t pi_sects[MAX_SECT];
 615         int32_t i_row = i_y - i_min_y;
 616
 617         /* ...fill from border to next junction */
 618         switch (i_border)
 619         {
 620           case puzzle_SHAPE_TOP:
 621           case puzzle_SHAPE_BTM:
 622             pi_sects[i_sect] = puzzle_diagonal_limit( p_filter, i_y, false, i_plane ) - 1
 623                             - (puzzle_diagonal_limit( p_filter, i_y, true, i_plane ) - 1);
 624             break;
 625           case puzzle_SHAPE_RIGHT:
 626             pi_sects[i_sect] = i_width - puzzle_diagonal_limit( p_filter, i_y, false, i_plane );
 627             break;
 628           case puzzle_SHAPE_LEFT:
 629           default:
 630             pi_sects[i_sect] = puzzle_diagonal_limit( p_filter, i_y, true, i_plane );
 631         }
 632         i_sect++;
 633
 634         /* ...allocate memory and copy final values */
 635         ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_sect;
 636         ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc ( sizeof(row_section_t) * i_sect);
 637         if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 638             for (uint8_t i=0; i<i_row;i++)
 639                 free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 640             free(ps_piece_shape->ps_piece_shape_row);
 641             ps_piece_shape->ps_piece_shape_row = NULL;
 642             return VLC_ENOMEM;
 643         }
 644
 645         for (uint8_t i=0; i < i_sect; i++) {
 646             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_type = i % 2; /* 0 = fill ; 1 = offset */
 647             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_width = pi_sects[i];
 648         }
 649     }
 650     return VLC_SUCCESS;
 651 }
 652
 653 /*****************************************************************************
 654  * generate data which will be used to draw each line of a piece sector based
 655  *       on bezier curve
 656  *****************************************************************************/
 657 int puzzle_generate_sect_bezier( filter_t *p_filter, piece_shape_t *ps_piece_shape, uint8_t i_pts_nbr, point_t *ps_pt, uint8_t i_plane, uint8_t i_border)
 658 {
 659     /* generate data required to draw a sector of puzzle piece using bezier shape */
 660     if ((!ps_pt) || (!ps_piece_shape))
 661         return VLC_EGENERIC;
 662
 663     filter_sys_t *p_sys = p_filter->p_sys;
 664
 665     int32_t i_width = p_sys->ps_desk_planes[i_plane].i_pce_max_width;
 666     int32_t i_lines = p_sys->ps_desk_planes[i_plane].i_pce_max_lines;
 667     int32_t i_size_x_0 = p_sys->ps_desk_planes[0].i_pce_max_width;
 668     int32_t i_size_y_0 = p_sys->ps_desk_planes[0].i_pce_max_lines;
 669
 670     float f_x_ratio =  ((float) i_width) / ((float) i_size_x_0);
 671     float f_y_ratio = ((float) i_lines) / ((float) i_size_y_0);
 672
 673     /* first: get min x and min y */
 674     float f_min_curve_x, f_min_curve_y;
 675     puzzle_get_min_bezier(&f_min_curve_x, &f_min_curve_y, f_x_ratio, f_y_ratio, ps_pt, i_pts_nbr);
 676
 677     f_min_curve_y = __MIN(0,floor(f_min_curve_y));
 678     f_min_curve_x = __MIN(0,floor(f_min_curve_x));
 679
 680     /* next: process each horizontal pixel lines */
 681     int32_t i_min_y = (i_border==puzzle_SHAPE_TOP)?floor(f_min_curve_y):0;
 682     int32_t i_nb_y = (i_border==puzzle_SHAPE_TOP)?(i_lines / 2 - i_min_y):i_lines;
 683
 684     /* allocate memory */
 685     ps_piece_shape->i_row_nbr = i_nb_y;
 686     ps_piece_shape->i_first_row_offset = i_min_y;
 687     ps_piece_shape->ps_piece_shape_row = malloc( sizeof( piece_shape_row_t ) * ps_piece_shape->i_row_nbr );
 688     if (!ps_piece_shape->ps_piece_shape_row)
 689         return VLC_ENOMEM;
 690
 691     return puzzle_generate_shape_lines(p_filter, ps_piece_shape, i_min_y, i_nb_y, f_x_ratio, f_y_ratio, ps_pt, i_pts_nbr, i_border, i_plane);
 692 }
 693
 694 /*****************************************************************************
 695  * when generating shape data: determine minimum bezier value
 696  *****************************************************************************/
 697 void puzzle_get_min_bezier(float *f_min_curve_x, float *f_min_curve_y, float f_x_ratio, float f_y_ratio, point_t *ps_pt, uint8_t i_pts_nbr)
 698 {
 699     *f_min_curve_y = ps_pt[0].f_y * f_y_ratio;
 700     *f_min_curve_x = ps_pt[0].f_x * f_x_ratio;
 701
 702     for (float f_t = 0; f_t <= i_pts_nbr - 1; f_t += 0.1 ) {
 703         int8_t i_main_t = floor(f_t);
 704         if ( i_main_t == i_pts_nbr - 1 )
 705             i_main_t = i_pts_nbr - 2;
 706         float f_sub_t = f_t - i_main_t;
 707
 708         *f_min_curve_x = __MIN(*f_min_curve_x,bezier_val(ps_pt,f_sub_t,i_main_t,x) * f_x_ratio);
 709         *f_min_curve_y = __MIN(*f_min_curve_y,bezier_val(ps_pt,f_sub_t,i_main_t,y) * f_y_ratio);
 710     }
 711 }
 712
 713 /*****************************************************************************
 714  * proceed with each line in order to generate data which will be used
 715  *     to draw each line of a piece sector
 716  *****************************************************************************/
 717 int puzzle_generate_shape_lines( filter_t *p_filter, piece_shape_t *ps_piece_shape, int32_t i_min_y, int32_t i_nb_y, float f_x_ratio, float f_y_ratio, point_t *ps_pt, uint8_t i_pts_nbr, uint8_t i_border, uint8_t i_plane)
 718 {
 719     /* generate data required to draw a line of a piece sector */
 720     for (int32_t i_y = i_min_y; i_y < i_nb_y + i_min_y; i_y++) {
 721         int32_t i_row = i_y - i_min_y;
 722
 723         int32_t pi_sects[MAX_SECT];
 724
 725         uint8_t i_sect = puzzle_detect_curve( p_filter, i_y, f_x_ratio, f_y_ratio, ps_pt, i_pts_nbr, i_border, i_plane, pi_sects);
 726
 727         /* ...we have to convert absolute values to offsets and take into account min_curve_x */
 728         int8_t i_s = 0;
 729         int32_t i_last_x = (i_border==puzzle_SHAPE_TOP && (i_y>=0))?puzzle_diagonal_limit( p_filter, i_y, true, i_plane ):0;
 730
 731         for (i_s = 0; i_s<i_sect; i_s++) {
 732             int32_t i_current_x = pi_sects[i_s];
 733             int32_t i_delta = i_current_x - i_last_x;
 734             pi_sects[i_s] = i_delta;
 735
 736             i_last_x = i_current_x;
 737         }
 738
 739         switch (i_border)
 740         {
 741           case puzzle_SHAPE_TOP:
 742             /* ...allocate memory and copy final values */
 743             /* note for y > 0 we have to ignore the first offset as it is included in "Left" piece shape */
 744             if ( i_y >= 0 ) {
 745                 ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_sect;
 746                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * i_sect);
 747                 if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 748                     for (uint8_t i=0; i<i_row;i++)
 749                         free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 750                     free(ps_piece_shape->ps_piece_shape_row);
 751                     ps_piece_shape->ps_piece_shape_row = NULL;
 752                     return VLC_ENOMEM;
 753                 }
 754                 for (uint8_t i=0; i < i_sect; i++) {
 755                     ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_type = i % 2; /* 0 = fill ; 1 = offset */
 756                     ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_width = pi_sects[i];
 757                 }
 758             }
 759             else {
 760                 ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_sect;
 761                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * i_sect);
 762                 if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 763                     for (uint8_t i=0; i<i_row;i++)
 764                         free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 765                     free(ps_piece_shape->ps_piece_shape_row);
 766                     ps_piece_shape->ps_piece_shape_row = NULL;
 767                     return VLC_ENOMEM;
 768                 }
 769                 for (uint8_t i=0; i < i_sect; i++) {
 770                     ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_type = (i + 1) % 2; /* 0 = fill ; 1 = offset */
 771                     ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_width = pi_sects[i];
 772                 }
 773             }
 774             break;
 775           case puzzle_SHAPE_LEFT:
 776             /* ...allocate memory and copy final values */
 777             /* note for y > 0 we have to ignore the first offset as it is included in "Left" piece shape */
 778             ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_sect;
 779             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * i_sect);
 780             if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 781                 for (uint8_t i=0; i<i_row;i++)
 782                     free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 783                 free(ps_piece_shape->ps_piece_shape_row);
 784                 ps_piece_shape->ps_piece_shape_row = NULL;
 785                 return VLC_ENOMEM;
 786             }
 787             for (uint8_t i=0; i < i_sect; i++) {
 788                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_type = (i+1) % 2; /* 0 = fill ; 1 = offset */
 789                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i].i_width = pi_sects[i];
 790             }
 791         }
 792     }
 793     return VLC_SUCCESS;
 794 }
 795
 796 /*****************************************************************************
 797  * when generating shape data: detect all bezier curve intersections with
 798  * current line
 799  *****************************************************************************/
 800 int puzzle_detect_curve( filter_t *p_filter, int32_t i_y, float f_x_ratio, float f_y_ratio, point_t *ps_pt, uint8_t i_pts_nbr, uint8_t i_border, uint8_t i_plane, int32_t *pi_sects)
 801 {
 802     int8_t i_main_t = 0;
 803     float f_xd, f_yd;
 804     float f_xo = ps_pt[0].f_x * f_x_ratio;
 805     float f_yo = ps_pt[0].f_y * f_y_ratio;
 806     int8_t i_sect = 0;
 807
 808     for (float f_t = 0; f_t <= i_pts_nbr - 1; f_t += 0.1 ) {
 809         i_main_t = floor(f_t);
 810         if ( i_main_t == i_pts_nbr - 1 )
 811             i_main_t = i_pts_nbr - 2;
 812         float f_sub_t = f_t - i_main_t;
 813
 814         f_xd = bezier_val(ps_pt,f_sub_t,i_main_t,x) * f_x_ratio;
 815         f_yd = bezier_val(ps_pt,f_sub_t,i_main_t,y) * f_y_ratio;
 816
 817         if ((f_yo < (float)i_y+0.5 && f_yd >= (float)i_y+0.5) || (f_yo > (float)i_y+0.5 && f_yd <= (float)i_y+0.5)) {
 818             pi_sects[i_sect] = floor(((float)i_y+0.5 - f_yo) * (f_xd - f_xo) / (f_yd - f_yo) + f_xo);
 819             if (i_sect < MAX_SECT - 1)
 820                 i_sect++;
 821         }
 822
 823         f_xo = f_xd;
 824         f_yo = f_yd;
 825     }
 826     f_xd = ps_pt[i_pts_nbr - 1].f_x * f_x_ratio;
 827     f_yd = ps_pt[i_pts_nbr - 1].f_y * f_y_ratio;
 828
 829     /* ...fill from this junction to next junction */
 830     if ( i_y >= 0 ) {
 831         /* last diagonal intersection */
 832         pi_sects[i_sect] = (i_border==puzzle_SHAPE_TOP)?puzzle_diagonal_limit( p_filter, i_y, false, i_plane )
 833                                                        :puzzle_diagonal_limit( p_filter, i_y, true,  i_plane );
 834         if (i_sect < MAX_SECT - 1)
 835             i_sect++;
 836     }
 837
 838     /* ...reorder the list of intersection */
 839     int32_t i_s = 0;
 840
 841     while (i_s < (i_sect - 1)) {
 842         if (pi_sects[i_s] > pi_sects[i_s+1]) {
 843             uint32_t i_temp = pi_sects[i_s];
 844             pi_sects[i_s] = pi_sects[i_s+1];
 845             pi_sects[i_s+1] = i_temp;
 846             i_s = 0;
 847         }
 848         else {
 849             i_s++;
 850         }
 851     }
 852
 853     return i_sect;
 854 }
 855
 856 /*****************************************************************************
 857  * generate Right shape data from Left shape data
 858  *****************************************************************************/
 859 int puzzle_generate_sectLeft2Right( filter_t *p_filter, piece_shape_t *ps_piece_shape, piece_shape_t *ps_left_piece_shape, uint8_t i_plane)
 860 {
 861     if ((!ps_piece_shape) || (!ps_left_piece_shape))
 862         return VLC_EGENERIC;
 863
 864     filter_sys_t *p_sys = p_filter->p_sys;
 865
 866     int32_t i_min_y = ps_left_piece_shape->i_first_row_offset;
 867     int32_t i_nb_y = ps_left_piece_shape->i_row_nbr;
 868
 869     /* allocate memory */
 870     ps_piece_shape->i_row_nbr = i_nb_y;
 871     ps_piece_shape->i_first_row_offset = i_min_y;
 872     ps_piece_shape->ps_piece_shape_row = malloc( sizeof( piece_shape_row_t ) * i_nb_y );
 873     if (!ps_piece_shape->ps_piece_shape_row)
 874         return VLC_ENOMEM;
 875
 876     for (int32_t i_y = i_min_y; i_y < i_nb_y + i_min_y; i_y++) {
 877         int32_t i_row = i_y - i_min_y;
 878
 879         int32_t i_width = p_sys->ps_desk_planes[i_plane].i_pce_max_width;
 880         int32_t i_left_width = puzzle_diagonal_limit( p_filter, i_y, true, i_plane  );
 881         int32_t i_right_width = i_width - puzzle_diagonal_limit( p_filter, i_y, false, i_plane );
 882         int16_t i_section_nbr = ps_left_piece_shape->ps_piece_shape_row[i_row].i_section_nbr;
 883
 884         ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_section_nbr;
 885         ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * i_section_nbr);
 886         if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 887             for (uint8_t i=0; i<i_row;i++)
 888                 free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 889             free(ps_piece_shape->ps_piece_shape_row);
 890             ps_piece_shape->ps_piece_shape_row = NULL;
 891             return VLC_ENOMEM;
 892         }
 893
 894         ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_type =
 895                 ps_left_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_type;
 896         ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_width =
 897                 ps_left_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_width + i_right_width - i_left_width;
 898
 899         for (int8_t i_s=0; i_s<i_section_nbr;i_s++) {
 900             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_s].i_type =
 901                     ps_left_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_section_nbr - 1 - i_s].i_type;
 902             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_s].i_width =
 903                     ps_left_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_section_nbr - 1 - i_s].i_width
 904                     + (i_s == 0 ? i_right_width - i_left_width : 0);
 905         }
 906     }
 907     return VLC_SUCCESS;
 908 }
 909
 910 /*****************************************************************************
 911  * generates Bottom shape data from Top shape data
 912  *****************************************************************************/
 913 int puzzle_generate_sectTop2Btm( filter_t *p_filter, piece_shape_t *ps_piece_shape, piece_shape_t *ps_top_piece_shape, uint8_t i_plane)
 914 {
 915     if ((!ps_piece_shape) || (!ps_top_piece_shape))
 916         return VLC_EGENERIC;
 917
 918     filter_sys_t *p_sys = p_filter->p_sys;
 919
 920     int32_t i_top_min_y = ps_top_piece_shape->i_first_row_offset;
 921     int32_t i_top_nb_y = ps_top_piece_shape->i_row_nbr;
 922     int32_t i_lines = p_sys->ps_desk_planes[i_plane].i_pce_max_lines;
 923     int32_t i_max_y = p_sys->ps_desk_planes[i_plane].i_pce_max_lines - i_top_min_y;
 924
 925     int32_t i_min_y = i_lines / 2;
 926     int32_t i_nb_y = i_max_y - i_min_y;
 927
 928     /* allocate memory */
 929     ps_piece_shape->i_row_nbr = i_nb_y;
 930     ps_piece_shape->i_first_row_offset = i_min_y;
 931     ps_piece_shape->ps_piece_shape_row = malloc( sizeof( piece_shape_row_t ) * i_nb_y );
 932     if (!ps_piece_shape->ps_piece_shape_row)
 933         return VLC_ENOMEM;
 934
 935     for (int32_t i_y = i_min_y; i_y < i_nb_y + i_min_y; i_y++) {
 936         int32_t i_top_y = 2 * i_min_y - i_y + (i_nb_y - i_top_nb_y);
 937         int32_t i_row = i_y - i_min_y;
 938         int32_t i_top_row = i_top_y - i_top_min_y;
 939
 940         if ( i_top_row < 0 || i_top_row >= i_top_nb_y ) { /* the line does not exist in top */
 941             ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = 1;
 942             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * 1);
 943             if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 944                 for (uint8_t i=0; i<i_row;i++)
 945                     free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 946                 free(ps_piece_shape->ps_piece_shape_row);
 947                 ps_piece_shape->ps_piece_shape_row = NULL;
 948                 return VLC_ENOMEM;
 949             }
 950             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_type = 0;
 951             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[0].i_width =
 952                 puzzle_diagonal_limit( p_filter, i_y, false, i_plane ) - 1 - (puzzle_diagonal_limit( p_filter, i_y, true, i_plane ) - 1);
 953         }
 954         else { /* copy the line from TopShape */
 955             int32_t i_top_width =
 956                 puzzle_diagonal_limit( p_filter, i_top_y, false, i_plane ) - 1 - (puzzle_diagonal_limit( p_filter, i_top_y, true, i_plane ) - 1);
 957             int32_t i_width =
 958                 puzzle_diagonal_limit( p_filter, i_y, false, i_plane ) - 1 - (puzzle_diagonal_limit( p_filter, i_y, true, i_plane ) - 1);
 959             int32_t i_left_adjust = ( i_width - i_top_width ) / 2;
 960             int32_t i_right_adjust = ( i_width - i_top_width ) - i_left_adjust;
 961
 962             int8_t i_section_nbr = ps_top_piece_shape->ps_piece_shape_row[i_top_row].i_section_nbr;
 963             ps_piece_shape->ps_piece_shape_row[i_row].i_section_nbr = i_section_nbr;
 964             ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section = malloc (  sizeof(row_section_t) * i_section_nbr);
 965             if (!ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section) {
 966                 for (uint8_t i=0; i<i_row;i++)
 967                     free(ps_piece_shape->ps_piece_shape_row[i].ps_row_section);
 968                 free(ps_piece_shape->ps_piece_shape_row);
 969                 ps_piece_shape->ps_piece_shape_row = NULL;
 970                 return VLC_ENOMEM;
 971             }
 972
 973             for (int8_t i_s=0; i_s<i_section_nbr; i_s++) {
 974                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_s].i_type =
 975                         ps_top_piece_shape->ps_piece_shape_row[i_top_row].ps_row_section[i_s].i_type;
 976                 ps_piece_shape->ps_piece_shape_row[i_row].ps_row_section[i_s].i_width =
 977                         ps_top_piece_shape->ps_piece_shape_row[i_top_row].ps_row_section[i_s].i_width
 978                         + (i_s == 0 ? i_left_adjust : (i_s == i_section_nbr-1 ? i_right_adjust : 0));
 979             }
 980         }
 981     }
 982     return VLC_SUCCESS;
 983 }