1
2 /********************************************************************\
3 * *
4 * Code to do window placement by searching fo a good position. It *
5 * evaluates positions by looking at their weighted intersection *
6 * with other windows. *
7 * *
8 * In all of the following code, variables with names ending in two *
9 * digits are used to signify values atthe corner of rectangles as *
10 * follows... *
11 * *
12 * x00-------------x10 *
13 * | | *
14 * x01-------------x11 *
15 * *
16 \********************************************************************/
17
18 #include <stdio.h>
19 #include "twm.h"
20 #include "screen.h"
21 #include "icons.h"
22 #include "list.h"
23 #include "parse.h"
24
25 /* #define DEBUG_PLACEMENT */
26
27 /* some interpolation macros, doing this with macros isn't nice
28 because it causes lots of repeated expressions, but looks clean.
29 Good compilers will spot this.
30 Maybe I should rewrite these. Of course inline functions would be best.
31 */
32
33 /* interpolate weight on a line */
34 #define interpolate_line(d, dmax, w0, w1) \
35 (((double)d)/(dmax) * ((w1)-(w0)) + (w0))
36
37 /* interpolate weight on a plane */
38 #define interpolate_plane(x,y,xmax,ymax,w00,w10,w01,w11) \
39 interpolate_line((x), (xmax), \
40 interpolate_line((y), (ymax), (w00), (w01)), \
41 interpolate_line((y), (ymax), (w10), (w11)))
42
43 /* I think this is the integral. */
44
45 #define integrate_weights(xmin, ymin, xmax, ymax, w00, w10, w01, w11) \
46 (((xmax)-(xmin))*((ymax)-(ymin))*((w00)+(w01)+(w10)+(w11))/4.0)
47
48 #define min(x,y) ((x)<(y)?(x):(y))
49 #define max(x,y) ((x)>(y)?(x):(y))
50
51 typedef struct
52 {
53 int x, y, width, height;
54 } Rectangle;
55
56 /********************************************************************\
57 * *
58 * Procedure OverlapWeight *
59 * *
60 * Inputs: *
61 * lower - the lower rectangle *
62 * lw?? - weights on corners of lower *
63 * upper - the upper rectangle *
64 * *
65 * Returns: *
66 * The integral of the weight on the intersection of the *
67 * two rectangles using the above interpolation *
68 * function. *
69 * *
70 \********************************************************************/
71
72
73 static double
OverlapWeight(lower,lw00,lw10,lw01,lw11,upper)74 OverlapWeight(lower, lw00, lw10, lw01, lw11, upper)
75
76 Rectangle lower;
77 double lw00, lw01, lw10, lw11; /* weights for the corners of lower */
78 Rectangle upper;
79
80 {
81 int xmin, xmax, ymin, ymax;
82 double cw00, cw01, cw10, cw11;
83
84 /* Calculate clip rectangle */
85
86 xmin = min(max(lower.x, upper.x),lower.x + lower.width);
87 xmax = max(min(lower.x+lower.width, upper.x+upper.width), lower.x);
88 ymin = min(max(lower.y, upper.y),lower.y + lower.height);
89 ymax = max(min(lower.y+lower.height, upper.y+upper.height), lower.y);
90
91 #if DEBUG_POSITIONING > 1
92 printf("lower=%d, %d, %d, %d\n", lower.x, lower.x+lower.width, lower.y, lower.y+lower.height);
93 printf("upper=%d, %d, %d, %d\n", upper.x, upper.x+upper.width, upper.y, upper.y+upper.height);
94 printf("inter=%d, %d, %d, %d\n", xmin, xmax, ymin, ymax);
95 #endif
96
97 if (xmin==xmax || ymin==ymax)
98 return 0.0;
99
100 /* Calculate clip rectangle corner weights,
101 this could be enormously optimised by using interpolate_line
102 for the cases where a point is on an edge of `lower'*/
103
104 cw00=interpolate_plane(xmin-lower.x, ymin-lower.y,
105 lower.width, lower.height,
106 lw00, lw10, lw01, lw11);
107 cw10=interpolate_plane(xmax-lower.x, ymin-lower.y,
108 lower.width, lower.height,
109 lw00, lw10, lw01, lw11);
110 cw01=interpolate_plane(xmin-lower.x, ymax-lower.y,
111 lower.width, lower.height,
112 lw00, lw10, lw01, lw11);
113 cw11=interpolate_plane(xmax-lower.x, ymax-lower.y,
114 lower.width, lower.height,
115 lw00, lw10, lw01, lw11);
116
117 /* Finally do the integration over the surface.
118 I think I have the calculus right. */
119
120 return integrate_weights(xmin, ymin, xmax, ymax, cw00, cw10, cw01, cw11);
121 }
122
123 /********************************************************************\
124 * *
125 * Procedure EvaluatePosition - See how good a position is. *
126 * *
127 * Inputs: *
128 * x, y, w, h - the suggested position (screen *
129 * coordiantes) *
130 * *
131 * Returns: *
132 * A total weight for that position. *
133 * *
134 * This should really only count the currently visable parts of the *
135 * windows etc. *
136 * *
137 \********************************************************************/
138
139 static double
EvaluatePosition(x,y,width,height,weighting)140 EvaluatePosition(x, y, width, height, weighting)
141
142
143 int x, y, width, height;
144 WindowWeighting *weighting;
145
146 {
147 double weight;
148 Rectangle rect, window_rect;
149 TwmWindow *w;
150 IconRegion *ir;
151 name_list *p;
152 int i, j, ii, jj, istep, jstep;
153 WindowWeighting *ww;
154
155 weight= 0.0;
156
157 /* The major part of the weight is to sum the weighted intersections
158 for all of the open windows. */
159
160 for (w = Scr->TwmRoot.next; w != NULL; w=w->next)
161 if (w->mapped) /* New window is not mapped yet */
162 {
163 #ifdef DEBUG_PLACEMENT
164 printf("\t%s(0x%x) mapped", w->name, w->w);
165 #endif
166 if ( w->sticky && Scr->StickyAbove)
167 {
168 /* Sticky above windows will obscure new window, so clip
169 new window's weights against sticky window */
170
171 rect.x=w->frame_x;
172 rect.y=w->frame_y;
173 rect.width=w->frame_width;
174 rect.height=w->frame_height;
175
176 if ( w->root == Scr->VirtualDesktop)
177 {
178 rect.x -= Scr->vdtPositionX;
179 rect.y -= Scr->vdtPositionY;
180 }
181
182 for(i=0;i<3;i++)
183 for(j=0;j<3;j++)
184 {
185 window_rect.x=x+i*width/3.0;
186 window_rect.y=y+j*height/3.0;
187 window_rect.width=width/3.0;
188 window_rect.height=height/3.0;
189
190 weight += OverlapWeight(window_rect,
191 weighting->weights[i][j],
192 weighting->weights[i+1][j],
193 weighting->weights[i][j+1],
194 weighting->weights[i+1][j+1],
195 rect);
196 }
197 }
198 else
199 {
200 /* Other windows will be (at first at least) obscured by
201 the new one, so clip their weights against it */
202
203 if (w->sticky)
204 ww= w->StickyWeighting;
205 else
206 ww= w->Weighting;
207
208 window_rect.x=x;
209 window_rect.y=y;
210 window_rect.width=width;
211 window_rect.height=height;
212
213 for(i=0;i<3;i++)
214 for(j=0;j<3;j++)
215 {
216 rect.x=w->frame_x + i*w->frame_width/3.0;
217 rect.y=w->frame_y + j*w->frame_height/3.0;
218 rect.width=w->frame_width/3.0;
219 rect.height=w->frame_height/3.0;
220
221 if ( w->root == Scr->VirtualDesktop)
222 {
223 rect.x -= Scr->vdtPositionX;
224 rect.y -= Scr->vdtPositionY;
225 }
226
227 weight += OverlapWeight(rect,
228 ww->weights[i][j],
229 ww->weights[i+1][j],
230 ww->weights[i][j+1],
231 ww->weights[i+1][j+1],
232 window_rect);
233 }
234 }
235 #ifdef DEBUG_PLACEMENT
236 printf(" weight=%f\n", weight);
237 #endif
238 }
239
240 /* Icon Regions obscured. the weights for icon regions are rotated accordin
241 to the gravity */
242
243 window_rect.x=x;
244 window_rect.y=y;
245 window_rect.width=width;
246 window_rect.height=height;
247
248 for(p=Scr->IconRegions; p!=NULL; p=next_entry(p))
249 {
250 ir=(IconRegion *)contents_of_entry(p);
251 #ifdef DEBUG_PLACEMENT
252 printf("\tRegion %s ", ir->name);
253 #endif
254 if (ir->grav1==D_EAST || ir->grav2==D_EAST)
255 {
256 ii=3;
257 istep=-1;
258 }
259 else
260 {
261 ii=0;
262 istep=1;
263 }
264
265 for(i=0;i<3;i++)
266 {
267
268 if (ir->grav1==D_SOUTH || ir->grav2==D_SOUTH)
269 {
270 jj=3;
271 jstep=-1;
272 }
273 else
274 {
275 jj=0;
276 jstep=1;
277 }
278
279 for(j=0;j<3;j++)
280 {
281 rect.x=ir->x+i*ir->w/3.0;
282 rect.y=ir->y+j*ir->h/3.0;
283 rect.width=ir->w/3.0;
284 rect.height=ir->h/3.0;
285
286 if ( Scr->VirtualDesktop != None)
287 {
288 rect.x -= Scr->vdtPositionX;
289 rect.y -= Scr->vdtPositionY;
290 }
291
292 weight += OverlapWeight(rect,
293 Scr->IconRegionWindowWeighting.weights[ii][jj],
294 Scr->IconRegionWindowWeighting.weights[ii+istep][jj],
295 Scr->IconRegionWindowWeighting.weights[ii][jj+jstep],
296 Scr->IconRegionWindowWeighting.weights[ii+istep][jj+jstep],
297 window_rect);
298 jj += jstep;
299 }
300 ii+=istep;
301 }
302 #ifdef DEBUG_PLACEMENT
303 printf(" weight=%f\n", weight);
304 #endif
305 }
306
307 /* now add in a factor for the screen area consumed */
308
309 for(i=0;i<3;i++)
310 for(j=0;j<3;j++)
311 {
312 rect.x= i*Scr->MyDisplayWidth/3.0;
313 rect.y= j*Scr->MyDisplayHeight/3.0;
314 rect.width=Scr->MyDisplayWidth/3.0;
315 rect.height=Scr->MyDisplayHeight/3.0;
316
317 weight += OverlapWeight(rect,
318 Scr->ScreenWindowWeighting.weights[i][j],
319 Scr->ScreenWindowWeighting.weights[i+1][j],
320 Scr->ScreenWindowWeighting.weights[i][j+1],
321 Scr->ScreenWindowWeighting.weights[i+1][j+1],
322 window_rect);
323 }
324
325 /* finally a factor for how much of the new window would be off screen.
326 This is calculated as the weight for the entire window minus the weight
327 for the bit on screen. */
328
329 rect.x=rect.y=0;
330 rect.width=Scr->MyDisplayWidth;
331 rect.height=Scr->MyDisplayHeight;
332
333 for(i=0;i<3;i++)
334 for(j=0;j<3;j++)
335 {
336 window_rect.x=x+i*width/3.0;
337 window_rect.y=y+j*height/3.0;
338 window_rect.width=width/3.0;
339 window_rect.height=height/3.0;
340
341 weight += integrate_weights(window_rect.x,window_rect.y,
342 window_rect.x+window_rect.width,
343 window_rect.y+window_rect.height,
344 weighting->weights[i][j],
345 weighting->weights[i+1][j],
346 weighting->weights[i][j+1],
347 weighting->weights[i+1][j+1])
348 - OverlapWeight(window_rect,
349 weighting->weights[i][j],
350 weighting->weights[i+1][j],
351 weighting->weights[i][j+1],
352 weighting->weights[i+1][j+1],
353 rect);
354 }
355
356 /* that's all folks */
357
358 return weight;
359 }
360
361 /********************************************************************\
362 * *
363 * Procedure: *
364 * FindPlace - Find a place for the window which will *
365 * minimalise overlap. *
366 * *
367 * Inputs: *
368 * tmp_win - Window structure *
369 * *
370 * Results: *
371 * xp, yp - returned screen coordinates for top left *
372 * hand corner. *
373 * *
374 * This uses a simple 8-direction hill climbing algorithm. *
375 * *
376 \********************************************************************/
377
378 void
FindPlace(tmp_win,xp,yp)379 FindPlace(tmp_win, xp, yp)
380
381 TwmWindow *tmp_win;
382 int *xp, *yp;
383
384 {
385 int x, y, xstep, ystep, width, height;
386 int best_x, best_y, tx, ty;
387 double best_weight, last_best, weight;
388 WindowWeighting *ww;
389
390 if (tmp_win->sticky)
391 ww=tmp_win->StickyWeighting;
392 else
393 ww=tmp_win->Weighting;
394
395 width=tmp_win->frame_width;
396 height=tmp_win->frame_height;
397
398 /* start in the middle of the screen */
399
400 x= Scr->MyDisplayWidth/2;
401 y= Scr->MyDisplayHeight/2;
402 xstep = x/2;
403 ystep = y/2;
404
405 last_best=best_weight=EvaluatePosition(x-width/2, y-height/2, width, height, ww);
406 best_x=x;
407 best_y=y;
408
409 if (Scr->WatchPlacement)
410 {
411 MoveOutline(Scr->Root, x-width/2, y-height/2, width, height, 1,1);
412 XFlush(dpy);
413 }
414
415 while(xstep >0 || ystep >0)
416 {
417 for(ty=y-ystep; ty<=y+ystep; ty+=ystep)
418 {
419 for(tx=x-xstep; tx<=x+xstep; tx+=xstep)
420 {
421 #ifdef DEBUG_PLACEMENT
422 printf("(%d, %d) ->", tx, ty);
423 #endif
424 if (tx!=x || ty!=y)
425 {
426 if (Scr->WatchPlacement)
427 {
428 MoveOutline(Scr->Root, tx-width/2, ty-height/2, width, height, 1,1);
429 XFlush(dpy);
430 }
431 weight=EvaluatePosition(tx-width/2, ty-height/2, width, height, ww);
432 #ifdef DEBUG_PLACEMENT
433 printf("= %5.2f", weight);
434 #endif
435 if (weight<best_weight)
436 {
437 best_x=tx;
438 best_y=ty;
439 best_weight=weight;
440 }
441 }
442 else
443 {
444 #ifdef DEBUG_PLACEMENT
445 printf("still = %5.2f", last_best);
446 #endif
447 }
448 if ( xstep == 0 )
449 break;
450 }
451 #ifdef DEBUG_PLACEMENT
452 putchar('\n');
453 #endif
454 if ( ystep == 0 )
455 break;
456 }
457
458 #ifdef DEBUG_PLACEMENT
459 printf("\nbest=%5.2f @ %d, %d\n\n", best_weight, best_x, best_y);
460 getchar();
461 #endif
462 x=best_x;
463 y=best_y;
464 last_best=best_weight;
465 xstep /=2;
466 ystep /=2;
467 }
468
469 if (Scr->WatchPlacement)
470 {
471 MoveOutline(Scr->Root, 0,0,0,0,0,0);
472 XFlush(dpy);
473 }
474
475 *xp=x-width/2;
476 *yp=y-height/2+tmp_win->title_height;
477 }
478
479