Another G'MIC challenge: Random Subdivision

In discord/generative chatroom, a person has asked how can one generate shapes found in this picture:

As you can see, it is a bunch of subdivided rectangle. Quadtree is not the answer because it isn’t in common denominator form.

Here’s some of the roadblocks.

  1. G’MIC has no methods to have arrays within array akin to Python. That means it becomes very difficult to subdivide within subdivision.
  2. One has to factor into the size of border to fill the entire image with border around it and inside the rectangles.
  3. See the Quadtree commentary. So, with built-in commands out, one has to figure out a recursive method.

Personally, I think the goal involves a recursive subdivision with a merge command doing the subdivision. I don’t know how, but it involves that. Maybe even generating string to do that.

The goal:

Create a random subdivision art with borders as option, and palette in it.

Computing a recursive subdivision of something does not require arrays of arrays.
Even better : it’s rarely good to actually implement that with recursive functions.
Just maintain a list of your different objects (e.g. as an image of coordinates), and loop over it to subdivise some of them when needed (see example below).

subdivide_example :

  # Create a list of randomly subdivided rectangles.
  1,1,1,4
  eval ${-math_lib}"
    dar_insert(#-1,[0,0,511,511]);
    repeat(10,r,
      N = dar_size(#-1);
      repeat(N,k,
        P = I[#-1,k];
        size = P[2,2] - P[0,2] + 1;
        (N<8 || u<0.75) && min(size)>10?(
          C = round(lerp(P[0,2],P[2,2],u));
          dar_insert(#-1,[ P[0],P[1],C[0] - 1,C[1] - 1 ]);
          dar_insert(#-1,[ C[0],P[1],P[2],C[1] - 1 ]);
          dar_insert(#-1,[ P[0],C[1],C[0] - 1,P[3] ]);
          copy(I[#-1,k],[ C[0],C[1],P[2],P[3] ]);
        );
      );
    );
    resize(#-1,1,dar_size(#-1),1,4,0)"

  # Draw rectangles.
  512,512,1,3
  eval.. "
    P = I;
    coords = [ P[0],P[1],P[2],P[1],P[2],P[3],P[0],P[3] ];
    color = u([20,20,20],[255,255,255]);
    polygon(#-1,4,coords,1,color);
    polygon(#-1,-4,coords,1,0xFFFFFFFF,0);
  "
  rm..

gives :

subdivide

2 Likes

Matt Pearson Generative Art?

Here is a 3D version :

subdivide3d :

  # Create a list of randomly subdivided 3D rectangles.
  1,1,1,9
  eval ${-math_lib}"
    dar_insert(#-1,[ -256,-256,128, 512,0,0, 0,512,0 ] );
    dar_insert(#-1,[ -256,-256,0, 0,0,128, 0,512,0 ] );
    dar_insert(#-1,[ 256,-256,0, 0,0,128, 0,512,0 ] );
    dar_insert(#-1,[ -256,-256,0, 512,0,0, 0,0,128 ] );
    dar_insert(#-1,[ -256,256,0, 512,0,0, 0,0,128 ] );
    repeat(6,r,
      N = dar_size(#-1);
      repeat(N,k,
        F = I[#-1,k];
        P0 = F[0,3];
        U0 = F[3,3];
        U1 = F[6,3];
        (N<8 || u<0.75) && norm(U0 + U1)>10?(
          V0 = u*U0;
          W0 = U0 - V0;
          V1 = u*U1;
          W1 = U1 - V1;
          dar_insert(#-1,[ P0,V0,V1 ]);
          dar_insert(#-1,[ P0 + V0,W0,V1 ]);
          dar_insert(#-1,[ P0 + V1,V0,W1 ]);
          copy(I[#-1,k],[ P0 + V0 + V1,W0,W1 ]);
        );
      );
    );
    resize(#-1,1,dar_size(#-1),1,9,0)"

  # Draw 3D rectangles.
  512,512,1,3
  eval.. "
    const focale = 64;
    proj2d(P) = [ focale*P[0]/P[2] + w#-1/2, focale*P[1]/P[2] + h#-1/2 ];
    F = I;
    U0 = F[3,3];
    U1 = F[6,3];
    P0 = F[0,3] +  [0,0,focale ];
    P1 = P0 + U0;
    P2 = P1 + U1;
    P3 = P0 + U1;
    coords = [ proj2d(P0),proj2d(P1),proj2d(P2),proj2d(P3) ];
    color = u([20,20,20],[255,255,255]);
    polygon(#-1,4,coords,1,color);
    polygon(#-1,-4,coords,1,0xFFFFFFFF,0);
  "
  rm..

subdivide3d

2 Likes

Absolutely impressive, @David_Tschumperle . I might make my own version, but only thing that holds me back is the fear of my solution being very time-consuming, and this one will consume more time than I’d like.

1 Like

Adding Z-shading, and playing a little bit with the parameters:

subdivide3d_2

3 Likes

Last attempt, playing with the position of the 3D planes, as well as applying a color LUT at the end.
Now, back to work :slight_smile:

subdivide3d_4

subdivide3d_3

2 Likes

@David_Tschumperle How are you able to use dar_insert into the same image?

C:\Windows\System32>gmic 512,512 rep_random_subdivide
[gmic]-0./ Start G'MIC interpreter.
[gmic]-0./ Input black image at position 0 (1 image 512x512x1x1).
[gmic] *** Error in ./rep_random_subdivide/ *** Command 'eval': gmic<float>: Function 'resize()': Cannot both fill and resize image (1,1,1,6) to new dimensions (1,2,1,6).
[gmic] Command 'eval' has the following description:

[gmic] No help available for command 'eval'.
       Try 'gmic -h' for global help.
rep_random_subdivide:
1,1,1,6,[0,w#-1-1,0,h#-1-1,0,0]

eval. ${-math_lib}"
dar_insert(#-1,[0,255,0,255,1,1]);
"

As the error message tells you, it is not possible to use fill or eval on an image that is used as a dynamic array.
Because by definition a dynamic array has a dynamic size, and so using dar_insert() or dar_remove() may indeed change the size of the image.

And of course, if the size of the image changes during a fill or eval execution, it would be a complete mess.
Note that this constraint does not apply if you use eval without a selection, because in that case, the evaluation is done once and not for all pixels of an image.

2 Likes

pfffffffff
The speed with which you write things like this is frightening!
Incredible

1 Like

I have made a different approach though WIP:

init_subdivision() generates subdivision.

EDIT: More work done, but still buggy. :/. Only if I can manage to subdivide properly beyond the first iteration.

rep_random_subdivide:
skip ${3=4},${4=500}
1,1,1,5,[0,w#-1-1,0,h#-1-1,0]
1,1,1,1,0

#Last two values for array above#
#-2==iteration#
#-1==skip#

eval ${-math_lib}"
 const ww=w#-3-1;
 const hh=h#-3-1;
 const border_size=$2;
 const max_division=$1;
 const max_iter=$3;
 const arr_limit=$4;
 
 find_orientation(a,b)=a<border_size?1:b<border_size?0:u(0,1)<.5?1;
 find_diff_w(a)=a[1]-a[0];
 find_diff_h(a)=a[3]-a[2];
 
 init_subdivision(a,c_iter,insertion_point)=(
  ri=int(u(0,max_division))+1;
  nw=find_diff_w(a);
  nh=find_diff_h(a);
  orientation=find_orientation(nw,hh);
  end_pos_x=a[1];
  end_pos_y=a[3];
  if(orientation,
   step_size=nh/ri;
   pos=a[2];
   repeat(ri,iter,
    (iter==(ri-1))?(
     min_pos=pos+border_size;
     max_pos=end_pos_y-border_size;
     new_dim_pos=round(u(min_pos,max_pos));
     dar_insert(#-2,[a[0],end_pos_x,pos,new_dim_pos,c_iter],insertion_point);
     dar_insert(#-2,[a[0],end_pos_x,new_dim_pos+1,end_pos_y,c_iter],insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
    ):(
     min_pos=pos+border_size;
     max_pos=step_size*(iter+1);
     new_dim_pos=round(u(min_pos,max_pos));
     dar_insert(#-2,[a[0],end_pos_x,pos,new_dim_pos,c_iter],insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
     pos=new_dim_pos+1;
     if(pos>=(end_pos_y-border_size),break(););
    );
   );
  ,
   step_size=nw/ri;
   pos=a[0];
   repeat(ri,iter,
    (iter==(ri-1))?(
     min_pos=pos+border_size;
     max_pos=end_pos_x-border_size;
     new_dim_pos=round(u(min_pos,max_pos));
     dar_insert(#-2,[pos,new_dim_pos,a[2],end_pos_y,c_iter],insertion_point);
     dar_insert(#-2,[new_dim_pos+1,end_pos_x,a[2],end_pos_y,c_iter],insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
    ):(
     min_pos=pos+border_size;
     max_pos=step_size*(iter+1);
     new_dim_pos=round(u(min_pos,max_pos));
     dar_insert(#-2,[pos,new_dim_pos,a[2],end_pos_y,c_iter],insertion_point);
     dar_insert(#-1,u(0,1)<.5,insertion_point);
     pos=new_dim_pos+1;
     if(pos>=(end_pos_x-border_size),break(););
    );
   );
  );   
 );
 
 m=0;
 
 add_subdivision(insertion_point)=(
  ci=I(#-2,0,insertion_point);
  iter_lvl=ci[4];
  if(iter_lvl<max_iter,
   dar_remove(#-2,insertion_point);
   dar_remove(#-1,insertion_point);
   init_subdivision(ci,iter_lvl+1,insertion_point);
  ,
  i(#-1,0,insertion_point)=1;
  );
 );
 
 add_subdivision(a,c_iter,insertion_point)=(
  nw=find_diff_w(a);
  nh=find_diff_h(a);
  if(nw<border_size&&nh<border_size,
   m++;
   i(#-1,0,insertion_point);
  ,
   init_subdivision(a,c_iter,insertion_point);
  );
 );
 
 (ww<border_size)&&(hh<border_size)?run('error inv_dim');
 
 initial_pixel=I(#-2,0,0,0);
 
 find_pos(p)=int(u(p));
 
 init_subdivision(initial_pixel,1,0);
 add_subdivision(find_pos(dar_size(#-1)));
 
 
 resize(#-2,1,dar_size(#-2),1,4,0);
 resize(#-1,1,dar_size(#-1),1,1,0);"

r[-3] 100%,100%,1,4

eval.. "
begin(
 convert2coords(c)=(
  tl=[c[0],c[2]];
  tr=[c[1],c[2]];
  bl=[c[0],c[3]];
  br=[c[1],c[3]];
  [tl,tr,br,bl];
 );
);
polygon(#-3,4,convert2coords(vector(#s,I)),1,I);"

@garagecoder We know by now that @David_Tschumperle codes in his dreams. Even when he says he is on vacation or super busy, and he may not respond to requests, he seems to be doing something CImg or G’MIC concurrently.

1 Like

if only it were true, I would have better nights… :sleepy:

1 Like

I got my attempt to work better:

image

Irrelevant code deleted

It still quite not there yet. I don’t know how to fix the bugs there. I wish I could. Oh well.


EDIT: Really, really close to getting it. Some pixels spaz out 1 px away. They either spaz out below or to the right. I know it has to do with the end, but I just don’t know how to fix that spaz out error. You can see in the code that I attempted to fix the spaz out.

rand_img

rep_wip:
r. 100%,100%,1,3
1,1,1,6
eval ${-math_lib}"
 const ww=w#-2-1;
 const hh=h#-2-1;
 const md=$1;
 const border_size=$2?($2+1);
 const test_boundary=$2?(border_size+1);
 const max_iter=$3;
 const arr_limit=$4;
 const test=1;
 
 convert2coords(c)=(
  tl=[c[0],c[2]];
  tr=[c[1],c[2]];
  bl=[c[0],c[3]];
  br=[c[1],c[3]];
  [tl,tr,br,bl];
 );
 
 diff_check(a)=(
  mri=md;
  ds=a/mri;
  if(mri>1&&ds<1,
   while(mri>1&&ds<1,
    mri--;
    ds=a/mri;
   );
  );
  ds>1;
 );
 
 width_check=diff_check(ww-border_size*2);
 height_check=diff_check(hh-border_size*2);
 
 !(width_check||height_check)?run('error inv_dim');
 
 m=0;
 dar_insert(#-1,[0,ww,0,hh,0,0]);
 
 sub_column(v,point)=(
  ri=int(u(1,md))+1;
  mri=ri-1;
  sx=v[0]+border_size;
  ex=v[1]-border_size;
  bound_check=(v[1]-v[0])>test_boundary;
  if(bound_check, 
   diff=(ex-sx);
   ds=diff/mri;
   if(mri>1&&ds<1,
    while(mri>1&&ds<1,
     ri--;
     mri--;
     ds=diff/mri;
    );
   );   
   if(ds>1,   
    py=[v[2],v[3]];
    iter=v[4]+1;
    dar_remove(#-1,point);
    p=v[0];   
    repeat(ri,ri_ind,   
     rb=u(0,1)<.25;   
     ri_ind==mri?(
      dar_insert(#-1,[p,v[1],py,iter,rb]);
      if(rb||(iter==max_iter),m++;);
     ):
     !ri_ind?(
      mx=sx+ds;
      np=max(sx,round(u(p,mx)));
      vp=[p,np];
      dar_insert(#-1,[vp,py,iter,rb]);
      p=np+1;
      if(rb||(iter==max_iter),m++;);
     ):(
      mx+=ds;
      np=min(max(p+border_size,round(u(p,mx))),v[1]);
      vp=[p,np];
      dar_insert(#-1,[vp,py,iter,rb]);
      p=np+1;
      if(rb||(iter==max_iter),m++;);
     );
    );   
   ,
    tv=v;
    tv[5]=1;
    I[#-1,point]=tv;
    m++;
   );
  ,
   tv=v;
   tv[5]=1;
   I[#-1,point]=tv;
   m++;
  );
 );
 
 sub_row(v,point)=(
  ri=int(u(1,md))+1;
  mri=ri-1;
  sy=v[2]+border_size;
  ey=v[3]-border_size;
  bound_check=(v[3]-v[2])>test_boundary;
  if(bound_check, 
   diff=(ey-sy);
   ds=diff/mri;
   if(mri>1&&ds<1,
    while(mri>1&&ds<1,
     ri--;
     mri--;
     ds=diff/mri;
    );
   );   
   if(ds>1,   
    px=[v[0],v[1]];
    iter=v[4]+1;
    dar_remove(#-1,point);
    p=v[2];   
    repeat(ri,ri_ind,   
     rb=u(0,1)<.25;   
     ri_ind==mri?(
      dar_insert(#-1,[px,p,v[3],iter,rb]);
      if(rb||(iter==max_iter),m++;);
     ):
     !ri_ind?(
      my=sy+ds;
      np=max(sy,round(u(p,my)));
      vp=[p,np];
      dar_insert(#-1,[px,vp,iter,rb]);
      p=np+1;
      if(rb||(iter==max_iter),m++;);
     ):(
      my+=ds;
      np=min(max(p+border_size,round(u(p,my))),v[3]);
      vp=[p,np];
      dar_insert(#-1,[px,vp,iter,rb]);
      p=np+1;
      if(rb||(iter==max_iter),m++;);
     );
    );   
   ,
    tv=v;
    tv[5]=1;
    I[#-1,point]=tv;
    m++;
   );
  ,
   tv=v;
   tv[5]=1;
   I[#-1,point]=tv;
   m++;
  );
 );
 
 
 v=I[#-1,0];
 
 width_check&&height_check?(
  u(0,1)<=.5?(
   sub_row(v,0);
  ):(
   sub_column(v,0);
  );
 ):
 width_check?(
  sub_column(v,0);
 ):
 height_check?(
  sub_row(v,0);
 );
 
 if(test,
 
 arr_point=0;
 
 while(m<dar_size(#-1),
  if(m==dar_size(#-1),break());
  p_ind=int(u(dar_size(#-1)));
  cv=I[#-1,p_ind];
  if((cv[4]==max_iter)||cv[5],
   while((cv[4]==max_iter)||cv[5],
    p_ind++;
    p_ind=p_ind%dar_size(#-1);
    cv=I[#-1,p_ind];
   );
  );
  u(0,1)<.5?(
   sub_row(cv,p_ind);
  ):(
   sub_column(cv,p_ind);
  );
  arr_point++;
  if(arr_point==arr_limit,break());
 );
 
 );
 
 repeat(dar_size(#-1),k,
  cv=I[#-1,k];
  nv=resize(cv,4,-1);
  coords=convert2coords(nv);
  polygon(#-2,4,coords,1,[u(255),u(255),u(255)]);
 );
"
rm.

Ha ha, looks like you are defragging.

2 Likes

Here’s another picture. Now, I’m doing the GUI thing.

image