}0~RECT.BCKYRECT.BCKRBACKUP README.TXT;,CONTENTS.TXT;,BUILD.COM;,*.C;,*.H;,*.UIL; RECT.BCK/SAVE_SET/LOG JMSYNGE  WV5.3 _HELTER::  _$22$DUA261: V5.3 ~  *[RECT]README.TXT;1+,Y. / 4E -%e 0123KPWO 56@"W7 ˀW89G HJA I've been working on some tools which I think will be useful for@ doing certain kinds of graphic simulations. I hope that others might find them useful too.D These tools are embodied in the program RECT, which allows the userD to create rectangles in a world coordinate system, to specify their< movement and rotation, and to display portions of the worldA coordinate system in multiple viewports. The scaling from world< coordinates to viewport coordinates can be set by the user.D -------------------------------------------------------------------< Each viewport (toplevel window) has the following elements:+ A window which shows a view on the world;4 Scroll bars for sliding the view around the world;9 A menu bar offering New View and Quit options (New View8 creates a new toplevel window, Quit deletes a toplevel window);< A command window in which commands can be entered with the< keyboard. Click in the command window with MB1 to give it input focus.D -------------------------------------------------------------------@ RECT supports the creation of of rectangles of integral size atE integer coordinates. The world coordinates range from -1000 to 1000B on both the X and Y axes. Internally, rectangles are represented 100 times more accurately.A Angles are represented as integer degrees (0 to 359 for absoluteA values, -359 to 359 for relative values). Specifying angle zero@ points the rectangle up (e.g. in the increasing y direction, or? north). Specifying angle 90 points the rectangle to the rightB (although, since the rectangles are symmetric, right and left are visually indistinguishable).D -------------------------------------------------------------------C The command line language is very terse. Each command is a singleC letter, and each of the command parameters is an integer. Objects@ are identified by a number, from 0 to 127. No check is made toA ensure that object numbers are within this range, so be careful. Commands: A = Sets the angle of the object whose number is to9 be (0 to 359). It stops any rotation which the object was doing.= C : Creates an object whose center will be at and< , whose size will be by , tilted> at degrees (0 to 359). This object will be assigned= the number . The object's initial altitude will< be set to its , and there is no initial motion. D - Deletes the object whose id is . H > Sets the altitude for the object whose number is 3 to . When two objects overlap in world> coordinates (X and Y), this value is used to determine which8 is displayed so that it appears to be above the other.: This is the very early support being developed for three dimensional objects. I 7 When objects are moving, this determines the interval7 between updates. The default is 1000 milliseconds (11 second). The minimum value is 10 milliseconds. M > Sets the distance that an object is moved at every interval.> The absolute direction in which it is moved depends upon its# angle and the sign of . P 5 Prints internal status information about the object. to stdout, usually the terminal. R : Sets the angle in degrees by which object is< rotated every interval. The initial value is 0. This can be an angle from -359 to 359. S < Each viewport can have its own scale-factor, the amount by= which objects are scaled down when drawn on the screen. The; initial viewport has a scale factor of 100. Thus, if the< world area is represented in units of meters, an rectangle4 on the screen would be drawn in the same number of centimeters.$ T > Translate the object whose number is so that its7 center is at , . Any forward (or< backward) motion the object had is stopped. This does not affect rotation.ha~RECT.BCKLu%e [RECT]CONTENTS.TXT;1E{*[RECT]CONTENTS.TXT;1+,Lu./ 4E-%e 0123KPWO56@L W7`W89G HJBBOX.H2 Bounding box data structures, and static routines BUILD.COM- Command file for compiling and linking RECT. CONTENTS.TXT This file.DATA.C2 A table of sine and cosine values, and of slopes.DRAW.C, Routines for drawing rectangles using Xlib.EXPOSE.CD Exposure handling routines, both for X events, and exposures caused by the movement of objects.LINES_AND_POINTS.HE Structures for representing lines and points in the world coordinate system. MISC_MATH.H Constants and macros for math.O.CE Object (rectangle) manipulation routines. This includes the parsing! of commands and performing them.O.H Object data structures. PRINTEVENT.C* Useful for dumping XAnyEvent information. QUADTREE.C7 Create quadtrees, insert and remove objects from them. QUADTREE.H. External interface definition for QUADTREE.C.QUADTREE_INT.H? Internal data structures for QUADTREE.C and QUADTREE_SEARCH.C.QUADTREE_SEARCH.C" Routines for searching quadtrees. README.TXT Overview of RECT.RECT.C Main routine.RECT.UIL" UIL description of the interface. RECTANGLE.C& Routines for manipulating rectangles. RECTANGLE.H- Data structures for representing rectangles. VIEWPORT.C3 Xlib routines for creating and handling viewports.X.H3 Xlib level structures for representing a viewport.XT.H7 Xtoolkit level structures for representing a viewport.XTVIEW.C? Xtoolkit level routines for creating and supporting viewports.uC~RECT.BCKw %e [RECT]BUILD.COM;1  *[RECT]BUILD.COM;1+,w ./ 4 -%e 0123KPWO56fV7bW89G HJ $ cc data $ cc draw $ cc expose$ cc o$ cc printevent $ cc quadtree$ cc quadtree_search $ cc rect$ cc rectangle $ cc viewport $ cc xtview$ link rect,sys$input:/optdata.objdraw.obj expose.objo.objprintevent.obj quadtree.objquadtree_search.obj rectangle.obj viewport.obj xtview.objsys$library:vaxcrtl/share sys$library:decw$dwtlibshr/sharesys$library:decw$xlibshr/share $ uil rect$ exity~RECT.BCKx %e [RECT]DATA.C;1!$-*[RECT]DATA.C;1+,x .$/ 4!$$-%e 0123KPWO%56 ?pM7\W89G HJH/* data.c */ #define _DATA_C #include "misc_math.h" globaldef T_FLOAT sin_cos_table[360+90] = { /* 0 */ 0.00000000, /* 1 */ 0.01745241, /* 2 */ 0.03489950, /* 3 */ 0.05233596, /* 4 */ 0.06975647, /* 5 */ 0.08715574, /* 6 */ 0.10452846, /* 7 */ 0.12186934, /* 8 */ 0.13917310, /* 9 */ 0.15643447, /* 10 */ 0.17364818, /* 11 */ 0.19080900, /* 12 */ 0.20791169, /* 13 */ 0.22495105, /* 14 */ 0.24192190, /* 15 */ 0.25881905, /* 16 */ 0.27563736, /* 17 */ 0.29237170, /* 18 */ 0.30901699, /* 19 */ 0.32556815, /* 20 */ 0.34202014, /* 21 */ 0.35836795, /* 22 */ 0.37460659, /* 23 */ 0.39073113, /* 24 */ 0.40673664, /* 25 */ 0.42261826, /* 26 */ 0.43837115, /* 27 */ 0.45399050, /* 28 */ 0.46947156, /* 29 */ 0.48480962, /* 30 */ 0.50000000, /* 31 */ 0.51503807, /* 32 */ 0.52991926, /* 33 */ 0.54463904, /* 34 */ 0.55919290, /* 35 */ 0.57357644, /* 36 */ 0.58778525, /* 37 */ 0.60181502, /* 38 */ 0.61566148, /* 39 */ 0.62932039, /* 40 */ 0.64278761, /* 41 */ 0.65605903, /* 42 */ 0.66913061, /* 43 */ 0.68199836, /* 44 */ 0.69465837, /* 45 */ 0.70710678, /* 46 */ 0.71933980, /* 47 */ 0.73135370, /* 48 */ 0.74314483, /* 49 */ 0.75470958, /* 50 */ 0.76604444, /* 51 */ 0.77714596, /* 52 */ 0.78801075, /* 53 */ 0.79863551, /* 54 */ 0.80901699, /* 55 */ 0.81915204, /* 56 */ 0.82903757, /* 57 */ 0.83867057, /* 58 */ 0.84804810, /* 59 */ 0.85716730, /* 60 */ 0.86602540, /* 61 */ 0.87461971, /* 62 */ 0.88294759, /* 63 */ 0.89100652, /* 64 */ 0.89879405, /* 65 */ 0.90630779, /* 66 */ 0.91354546, /* 67 */ 0.92050485, /* 68 */ 0.92718385, /* 69 */ 0.93358043, /* 70 */ 0.93969262, /* 71 */ 0.94551858, /* 72 */ 0.95105652, /* 73 */ 0.95630476, /* 74 */ 0.96126170, /* 75 */ 0.96592583, /* 76 */ 0.97029573, /* 77 */ 0.97437006, /* 78 */ 0.97814760, /* 79 */ 0.98162718, /* 80 */ 0.98480775, /* 81 */ 0.98768834, /* 82 */ 0.99026807, /* 83 */ 0.99254615, /* 84 */ 0.99452190, /* 85 */ 0.99619470, /* 86 */ 0.99756405, /* 87 */ 0.99862953, /* 88 */ 0.99939083, /* 89 */ 0.99984770, /* 90 */ 1.00000000, /* 91 */ 0.99984770, /* 92 */ 0.99939083, /* 93 */ 0.99862953, /* 94 */ 0.99756405, /* 95 */ 0.99619470, /* 96 */ 0.99452190, /* 97 */ 0.99254615, /* 98 */ 0.99026807, /* 99 */ 0.98768834, /* 100 */ 0.98480775, /* 101 */ 0.98162718, /* 102 */ 0.97814760, /* 103 */ 0.97437006, /* 104 */ 0.97029573, /* 105 */ 0.96592583, /* 106 */ 0.96126170, /* 107 */ 0.95630476, /* 108 */ 0.95105652, /* 109 */ 0.94551858, /* 110 */ 0.93969262, /* 111 */ 0.93358043, /* 112 */ 0.92718385, /* 113 */ 0.92050485, /* 114 */ 0.91354546, /* 115 */ 0.90630779, /* 116 */ 0.89879405, /* 117 */ 0.89100652, /* 118 */ 0.88294759, /* 119 */ 0.87461971, /* 120 */ 0.86602540, /* 121 */ 0.85716730, /* 122 */ 0.84804810, /* 123 */ 0.83867057, /* 124 */ 0.82903757, /* 125 */ 0.81915204, /* 126 */ 0.80901699, /* 127 */ 0.79863551, /* 128 */ 0.78801075, /* 129 */ 0.77714596, /* 130 */ 0.76604444, /* 131 */ 0.75470958, /* 132 */ 0.74314483, /* 133 */ 0.73135370, /* 134 */ 0.71933980, /* 135 */ 0.70710678, /* 136 */ 0.69465837, /* 137 */ 0.68199836, /* 138 */ 0.66913061, /* 139 */ 0.65605903, /* 140 */ 0.64278761, /* 141 */ 0.62932039, /* 142 */ 0.61566148, /* 143 */ 0.60181502, /* 144 */ 0.58778525, /* 145 */ 0.57357644, /* 146 */ 0.55919290, /* 147 */ 0.54463904, /* 148 */ 0.52991926, /* 149 */ 0.51503807, /* 150 */ 0.50000000, /* 151 */ 0.48480962, /* 152 */ 0.46947156, /* 153 */ 0.45399050, /* 154 */ 0.43837115, /* 155 */ 0.42261826, /* 156 */ 0.40673664, /* 157 */ 0.39073113, /* 158 */ 0.37460659, /* 159 */ 0.35836795, /* 160 */ 0.34202014, /* 161 */ 0.32556815, /* 162 */ 0.30901699, /* 163 */ 0.29237170, /* 164 */ 0.27563736, /* 165 */ 0.25881905, /* 166 */ 0.24192190, /* 167 */ 0.22495105, /* 168 */ 0.20791169, /* 169 */ 0.19080900, /* 170 */ 0.17364818, /* 171 */ 0.15643447, /* 172 */ 0.13917310, /* 173 */ 0.12186934, /* 174 */ 0.10452846, /* 175 */ 0.08715574, /* 176 */ 0.06975647, /* 177 */ 0.05233596, /* 178 */ 0.03489950, /* 179 */ 0.01745241, /* 180 */ 0.00000000, /* 181 */ -0.01745241, /* 182 */ -0.03489950, /* 183 */ -0.05233596, /* 184 */ -0.06975647, /* 185 */ -0.08715574, /* 186 */ -0.10452846, /* 187 */ -0.12186934, /* 188 */ -0.13917310, /* 189 */ -0.15643447, /* 190 */ -0.17364818, /* 191 */ -0.19080900, /* 192 */ -0.20791169, /* 193 */ -0.22495105, /* 194 */ -0.24192190, /* 195 */ -0.25881905, /* 196 */ -0.27563736, /* 197 */ -0.29237170, /* 198 */ -0.30901699, /* 199 */ -0.32556815, /* 200 */ -0.34202014, /* 201 */ -0.35836795, /* 202 */ -0.37460659, /* 203 */ -0.39073113, /* 204 */ -0.40673664, /* 205 */ -0.42261826, /* 206 */ -0.43837115, /* 207 */ -0.45399050, /* 208 */ -0.46947156, /* 209 */ -0.48480962, /* 210 */ -0.50000000, /* 211 */ -0.51503807, /* 212 */ -0.52991926, /* 213 */ -0.54463904, /* 214 */ -0.55919290, /* 215 */ -0.57357644, /* 216 */ -0.58778525, /* 217 */ -0.60181502, /* 218 */ -0.61566148, /* 219 */ -0.62932039, /* 220 */ -0.64278761, /* 221 */ -0.65605903, /* 222 */ -0.66913061, /* 223 */ -0.68199836, /* 224 */ -0.69465837, /* 225 */ -0.70710678, /* 226 */ -0.71933980, /* 227 */ -0.73135370, /* 228 */ -0.74314483, /* 229 */ -0.75470958, /* 230 */ -0.76604444, /* 231 */ -0.77714596, /* 232 */ -0.78801075, /* 233 */ -0.79863551, /* 234 */ -0.80901699, /* 235 */ -0.81915204, /* 236 */ -0.82903757, /* 237 */ -0.83867057, /* 238 */ -0.84804810, /* 239 */ -0.85716730, /* 240 */ -0.86602540, /* 241 */ -0.87461971, /* 242 */ -0.88294759, /* 243 */ -0.89100652, /* 244 */ -0.89879405, /* 245 */ -0.90630779, /* 246 */ -0.91354546, /* 247 */ -0.92050485, /* 248 */ -0.92718385, /* 249 */ -0.93358043, /* 250 */ -0.93969262, /* 251 */ -0.94551858, /* 252 */ -0.95105652, /* 253 */ -0.95630476, /* 254 */ -0.96126170, /* 255 */ -0.96592583, /* 256 */ -0.97029573, /* 257 */ -0.97437006, /* 258 */ -0.97814760, /* 259 */ -0.98162718, /* 260 */ -0.98480775, /* 261 */ -0.98768834, /* 262 */ -0.99026807, /* 263 */ -0.99254615, /* 264 */ -0.99452190, /* 265 */ -0.99619470, /* 266 */ -0.99756405, /* 267 */ -0.99862953, /* 268 */ -0.99939083, /* 269 */ -0.99984770, /* 270 */ -1.00000000, /* 271 */ -0.99984770, /* 272 */ -0.99939083, /* 273 */ -0.99862953, /* 274 */ -0.99756405, /* 275 */ -0.99619470, /* 276 */ -0.99452190, /* 277 */ -0.99254615, /* 278 */ -0.99026807, /* 279 */ -0.98768834, /* 280 */ -0.98480775, /* 281 */ -0.98162718, /* 282 */ -0.97814760, /* 283 */ -0.97437006, /* 284 */ -0.97029573, /* 285 */ -0.96592583, /* 286 */ -0.96126170, /* 287 */ -0.95630476, /* 288 */ -0.95105652, /* 289 */ -0.94551858, /* 290 */ -0.93969262, /* 291 */ -0.93358043, /* 292 */ -0.92718385, /* 293 */ -0.92050485, /* 294 */ -0.91354546, /* 295 */ -0.90630779, /* 296 */ -0.89879405, /* 297 */ -0.89100652, /* 298 */ -0.88294759, /* 299 */ -0.87461971, /* 300 */ -0.86602540, /* 301 */ -0.85716730, /* 302 */ -0.84804810, /* 303 */ -0.83867057, /* 304 */ -0.82903757, /* 305 */ -0.81915204, /* 306 */ -0.80901699, /* 307 */ -0.79863551, /* 308 */ -0.78801075, /* 309 */ -0.77714596, /* 310 */ -0.76604444, /* 311 */ -0.75470958, /* 312 */ -0.74314483, /* 313 */ -0.73135370, /* 314 */ -0.71933980, /* 315 */ -0.70710678, /* 316 */ -0.69465837, /* 317 */ -0.68199836, /* 318 */ -0.66913061, /* 319 */ -0.65605903, /* 320 */ -0.64278761, /* 321 */ -0.62932039, /* 322 */ -0.61566148, /* 323 */ -0.60181502, /* 324 */ -0.58778525, /* 325 */ -0.57357644, /* 326 */ -0.55919290, /* 327 */ -0.54463904, /* 328 */ -0.52991926, /* 329 */ -0.51503807, /* 330 */ -0.50000000, /* 331 */ -0.48480962, /* 332 */ -0.46947156, /* 333 */ -0.45399050, /* 334 */ -0.43837115, /* 335 */ -0.42261826, /* 336 */ -0.40673664, /* 337 */ -0.39073113, /* 338 */ -0.37460659, /* 339 */ -0.35836795, /* 340 */ -0.34202014, /* 341 */ -0.32556815, /* 342 */ -0.30901699, /* 343 */ -0.29237170, /* 344 */ -0.27563736, /* 345 */ -0.25881905, /* 346 */ -0.24192190, /* 347 */ -0.22495105, /* 348 */ -0.20791169, /* 349 */ -0.19080900, /* 350 */ -0.17364818, /* 351 */ -0.15643447, /* 352 */ -0.13917310, /* 353 */ -0.12186934, /* 354 */ -0.10452846, /* 355 */ -0.08715574, /* 356 */ -0.06975647, /* 357 */ -0.05233596, /* 358 */ -0.03489950, /* 359 */ -0.01745241, /* 360 */ 0.00000000, /* 361 */ 0.01745241, /* 362 */ 0.03489950, /* 363 */ 0.05233596, /* 364 */ 0.06975647, /* 365 */ 0.08715574, /* 366 */ 0.10452846, /* 367 */ 0.12186934, /* 368 */ 0.13917310, /* 369 */ 0.15643447, /* 370 */ 0.17364818, /* 371 */ 0.19080900, /* 372 */ 0.20791169, /* 373 */ 0.22495105, /* 374 */ 0.24192190, /* 375 */ 0.25881905, /* 376 */ 0.27563736, /* 377 */ 0.29237170, /* 378 */ 0.30901699, /* 379 */ 0.32556815, /* 380 */ 0.34202014, /* 381 */ 0.35836795, /* 382 */ 0.37460659, /* 383 */ 0.39073113, /* 384 */ 0.40673664, /* 385 */ 0.42261826, /* 386 */ 0.43837115, /* 387 */ 0.45399050, /* 388 */ 0.46947156, /* 389 */ 0.48480962, /* 390 */ 0.50000000, /* 391 */ 0.51503807, /* 392 */ 0.52991926, /* 393 */ 0.54463904, /* 394 */ 0.55919290, /* 395 */ 0.57357644, /* 396 */ 0.58778525, /* 397 */ 0.60181502, /* 398 */ 0.61566148, /* 399 */ 0.62932039, /* 400 */ 0.64278761, /* 401 */ 0.65605903, /* 402 */ 0.66913061, /* 403 */ 0.68199836, /* 404 */ 0.69465837, /* 405 */ 0.70710678, /* 406 */ 0.71933980, /* 407 */ 0.73135370, /* 408 */ 0.74314483, /* 409 */ 0.75470958, /* 410 */ 0.76604444, /* 411 */ 0.77714596, /* 412 */ 0.78801075, /* 413 */ 0.79863551, /* 414 */ 0.80901699, /* 415 */ 0.81915204, /* 416 */ 0.82903757, /* 417 */ 0.83867057, /* 418 */ 0.84804810, /* 419 */ 0.85716730, /* 420 */ 0.86602540, /* 421 */ 0.87461971, /* 422 */ 0.88294759, /* 423 */ 0.89100652, /* 424 */ 0.89879405, /* 425 */ 0.90630779, /* 426 */ 0.91354546, /* 427 */ 0.92050485, /* 428 */ 0.92718385, /* 429 */ 0.93358043, /* 430 */ 0.93969262, /* 431 */ 0.94551858, /* 432 */ 0.95105652, /* 433 */ 0.95630476, /* 434 */ 0.96126170, /* 435 */ 0.96592583, /* 436 */ 0.97029573, /* 437 */ 0.97437006, /* 438 */ 0.97814760, /* 439 */ 0.98162718, /* 440 */ 0.98480775, /* 441 */ 0.98768834, /* 442 */ 0.99026807, /* 443 */ 0.99254615, /* 444 */ 0.99452190, /* 445 */ 0.99619470, /* 446 */ 0.99756405, /* 447 */ 0.99862953, /* 448 */ 0.99939083, /* 449 */ 0.99984770, }; globaldef T_FLOAT slope_table[360] = { /* 0 */ INFINITE, /* 1 */ 57.28996163, /* 2 */ 28.63625328, /* 3 */ 19.08113669, /* 4 */ 14.30066626, /* 5 */ 11.43005230, /* 6 */ 9.51436445, /* 7 */ 8.14434643, /* 8 */ 7.11536972, /* 9 */ 6.31375151, /* 10 */ 5.67128182, /* 11 */ 5.14455402, /* 12 */ 4.70463011, /* 13 */ 4.33147587, /* 14 */ 4.01078093, /* 15 */ 3.73205081, /* 16 */ 3.48741444, /* 17 */ 3.27085262, /* 18 */ 3.07768354, /* 19 */ 2.90421088, /* 20 */ 2.74747742, /* 21 */ 2.60508906, /* 22 */ 2.47508685, /* 23 */ 2.35585237, /* 24 */ 2.24603677, /* 25 */ 2.14450692, /* 26 */ 2.05030384, /* 27 */ 1.96261051, /* 28 */ 1.88072647, /* 29 */ 1.80404776, /* 30 */ 1.73205081, /* 31 */ 1.66427948, /* 32 */ 1.60033453, /* 33 */ 1.53986496, /* 34 */ 1.48256097, /* 35 */ 1.42814801, /* 36 */ 1.37638192, /* 37 */ 1.32704482, /* 38 */ 1.27994163, /* 39 */ 1.23489716, /* 40 */ 1.19175359, /* 41 */ 1.15036841, /* 42 */ 1.11061251, /* 43 */ 1.07236871, /* 44 */ 1.03553031, /* 45 */ 1.00000000, /* 46 */ 0.96568877, /* 47 */ 0.93251509, /* 48 */ 0.90040404, /* 49 */ 0.86928674, /* 50 */ 0.83909963, /* 51 */ 0.80978403, /* 52 */ 0.78128563, /* 53 */ 0.75355405, /* 54 */ 0.72654253, /* 55 */ 0.70020754, /* 56 */ 0.67450852, /* 57 */ 0.64940759, /* 58 */ 0.62486935, /* 59 */ 0.60086062, /* 60 */ 0.57735027, /* 61 */ 0.55430905, /* 62 */ 0.53170943, /* 63 */ 0.50952545, /* 64 */ 0.48773259, /* 65 */ 0.46630766, /* 66 */ 0.44522869, /* 67 */ 0.42447482, /* 68 */ 0.40402623, /* 69 */ 0.38386404, /* 70 */ 0.36397023, /* 71 */ 0.34432761, /* 72 */ 0.32491970, /* 73 */ 0.30573068, /* 74 */ 0.28674539, /* 75 */ 0.26794919, /* 76 */ 0.24932800, /* 77 */ 0.23086819, /* 78 */ 0.21255656, /* 79 */ 0.19438031, /* 80 */ 0.17632698, /* 81 */ 0.15838444, /* 82 */ 0.14054083, /* 83 */ 0.12278456, /* 84 */ 0.10510424, /* 85 */ 0.08748866, /* 86 */ 0.06992681, /* 87 */ 0.05240778, /* 88 */ 0.03492077, /* 89 */ 0.01745506, /* 90 */ 0.00000000, /* 91 */ -0.01745506, /* 92 */ -0.03492077, /* 93 */ -0.05240778, /* 94 */ -0.06992681, /* 95 */ -0.08748866, /* 96 */ -0.10510424, /* 97 */ -0.12278456, /* 98 */ -0.14054083, /* 99 */ -0.15838444, /* 100 */ -0.17632698, /* 101 */ -0.19438031, /* 102 */ -0.21255656, /* 103 */ -0.23086819, /* 104 */ -0.24932800, /* 105 */ -0.26794919, /* 106 */ -0.28674539, /* 107 */ -0.30573068, /* 108 */ -0.32491970, /* 109 */ -0.34432761, /* 110 */ -0.36397023, /* 111 */ -0.38386404, /* 112 */ -0.40402623, /* 113 */ -0.42447482, /* 114 */ -0.44522869, /* 115 */ -0.46630766, /* 116 */ -0.48773259, /* 117 */ -0.50952545, /* 118 */ -0.53170943, /* 119 */ -0.55430905, /* 120 */ -0.57735027, /* 121 */ -0.60086062, /* 122 */ -0.62486935, /* 123 */ -0.64940759, /* 124 */ -0.67450852, /* 125 */ -0.70020754, /* 126 */ -0.72654253, /* 127 */ -0.75355405, /* 128 */ -0.78128563, /* 129 */ -0.80978403, /* 130 */ -0.83909963, /* 131 */ -0.86928674, /* 132 */ -0.90040404, /* 133 */ -0.93251509, /* 134 */ -0.96568877, /* 135 */ -1.00000000, /* 136 */ -1.03553031, /* 137 */ -1.07236871, /* 138 */ -1.11061251, /* 139 */ -1.15036841, /* 140 */ -1.19175359, /* 141 */ -1.23489716, /* 142 */ -1.27994163, /* 143 */ -1.32704482, /* 144 */ -1.37638192, /* 145 */ -1.42814801, /* 146 */ -1.48256097, /* 147 */ -1.53986496, /* 148 */ -1.60033453, /* 149 */ -1.66427948, /* 150 */ -1.73205081, /* 151 */ -1.80404776, /* 152 */ -1.88072647, /* 153 */ -1.96261051, /* 154 */ -2.05030384, /* 155 */ -2.14450692, /* 156 */ -2.24603677, /* 157 */ -2.35585237, /* 158 */ -2.47508685, /* 159 */ -2.60508906, /* 160 */ -2.74747742, /* 161 */ -2.90421088, /* 162 */ -3.07768354, /* 163 */ -3.27085262, /* 164 */ -3.48741444, /* 165 */ -3.73205081, /* 166 */ -4.01078093, /* 167 */ -4.33147587, /* 168 */ -4.70463011, /* 169 */ -5.14455402, /* 170 */ -5.67128182, /* 171 */ -6.31375151, /* 172 */ -7.11536972, /* 173 */ -8.14434643, /* 174 */ -9.51436445, /* 175 */ -11.43005230, /* 176 */ -14.30066626, /* 177 */ -19.08113669, /* 178 */ -28.63625328, /* 179 */ -57.28996163, /* 180 */ INFINITE, /* 181 */ 57.28996163, /* 182 */ 28.63625328, /* 183 */ 19.08113669, /* 184 */ 14.30066626, /* 185 */ 11.43005230, /* 186 */ 9.51436445, /* 187 */ 8.14434643, /* 188 */ 7.11536972, /* 189 */ 6.31375151, /* 190 */ 5.67128182, /* 191 */ 5.14455402, /* 192 */ 4.70463011, /* 193 */ 4.33147587, /* 194 */ 4.01078093, /* 195 */ 3.73205081, /* 196 */ 3.48741444, /* 197 */ 3.27085262, /* 198 */ 3.07768354, /* 199 */ 2.90421088, /* 200 */ 2.74747742, /* 201 */ 2.60508906, /* 202 */ 2.47508685, /* 203 */ 2.35585237, /* 204 */ 2.24603677, /* 205 */ 2.14450692, /* 206 */ 2.05030384, /* 207 */ 1.96261051, /* 208 */ 1.88072647, /* 209 */ 1.80404776, /* 210 */ 1.73205081, /* 211 */ 1.66427948, /* 212 */ 1.60033453, /* 213 */ 1.53986496, /* 214 */ 1.48256097, /* 215 */ 1.42814801, /* 216 */ 1.37638192, /* 217 */ 1.32704482, /* 218 */ 1.27994163, /* 219 */ 1.23489716, /* 220 */ 1.19175359, /* 221 */ 1.15036841, /* 222 */ 1.11061251, /* 223 */ 1.07236871, /* 224 */ 1.03553031, /* 225 */ 1.00000000, /* 226 */ 0.96568877, /* 227 */ 0.93251509, /* 228 */ 0.90040404, /* 229 */ 0.86928674, /* 230 */ 0.83909963, /* 231 */ 0.80978403, /* 232 */ 0.78128563, /* 233 */ 0.75355405, /* 234 */ 0.72654253, /* 235 */ 0.70020754, /* 236 */ 0.67450852, /* 237 */ 0.64940759, /* 238 */ 0.62486935, /* 239 */ 0.60086062, /* 240 */ 0.57735027, /* 241 */ 0.55430905, /* 242 */ 0.53170943, /* 243 */ 0.50952545, /* 244 */ 0.48773259, /* 245 */ 0.46630766, /* 246 */ 0.44522869, /* 247 */ 0.42447482, /* 248 */ 0.40402623, /* 249 */ 0.38386404, /* 250 */ 0.36397023, /* 251 */ 0.34432761, /* 252 */ 0.32491970, /* 253 */ 0.30573068, /* 254 */ 0.28674539, /* 255 */ 0.26794919, /* 256 */ 0.24932800, /* 257 */ 0.23086819, /* 258 */ 0.21255656, /* 259 */ 0.19438031, /* 260 */ 0.17632698, /* 261 */ 0.15838444, /* 262 */ 0.14054083, /* 263 */ 0.12278456, /* 264 */ 0.10510424, /* 265 */ 0.08748866, /* 266 */ 0.06992681, /* 267 */ 0.05240778, /* 268 */ 0.03492077, /* 269 */ 0.01745506, /* 270 */ 0.00000000, /* 271 */ -0.01745506, /* 272 */ -0.03492077, /* 273 */ -0.05240778, /* 274 */ -0.06992681, /* 275 */ -0.08748866, /* 276 */ -0.10510424, /* 277 */ -0.12278456, /* 278 */ -0.14054083, /* 279 */ -0.15838444, /* 280 */ -0.17632698, /* 281 */ -0.19438031, /* 282 */ -0.21255656, /* 283 */ -0.23086819, /* 284 */ -0.24932800, /* 285 */ -0.26794919, /* 286 */ -0.28674539, /* 287 */ -0.30573068, /* 288 */ -0.32491970, /* 289 */ -0.34432761, /* 290 */ -0.36397023, /* 291 */ -0.38386404, /* 292 */ -0.40402623, /* 293 */ -0.42447482, /* 294 */ -0.44522869, /* 295 */ -0.46630766, /* 296 */ -0.48773259, /* 297 */ -0.50952545, /* 298 */ -0.53170943, /* 299 */ -0.55430905, /* 300 */ -0.57735027, /* 301 */ -0.60086062, /* 302 */ -0.62486935, /* 303 */ -0.64940759, /* 304 */ -0.67450852, /* 305 */ -0.70020754, /* 306 */ -0.72654253, /* 307 */ -0.75355405, /* 308 */ -0.78128563, /* 309 */ -0.80978403, /* 310 */ -0.83909963, /* 311 */ -0.86928674, /* 312 */ -0.90040404, /* 313 */ -0.93251509, /* 314 */ -0.96568877, /* 315 */ -1.00000000, /* 316 */ -1.03553031, /* 317 */ -1.07236871, /* 318 */ -1.11061251, /* 319 */ -1.15036841, /* 320 */ -1.19175359, /* 321 */ -1.23489716, /* 322 */ -1.27994163, /* 323 */ -1.32704482, /* 324 */ -1.37638192, /* 325 */ -1.42814801, /* 326 */ -1.48256097, /* 327 */ -1.53986496, /* 328 */ -1.60033453, /* 329 */ -1.66427948, /* 330 */ -1.73205081, /* 331 */ -1.80404776, /* 332 */ -1.88072647, /* 333 */ -1.96261051, /* 334 */ -2.05030384, /* 335 */ -2.14450692, /* 336 */ -2.24603677, /* 337 */ -2.35585237, /* 338 */ -2.47508685, /* 339 */ -2.60508906, /* 340 */ -2.74747742, /* 341 */ -2.90421088, /* 342 */ -3.07768354, /* 343 */ -3.27085262, /* 344 */ -3.48741444, /* 345 */ -3.73205081, /* 346 */ -4.01078093, /* 347 */ -4.33147587, /* 348 */ -4.70463011, /* 349 */ -5.14455402, /* 350 */ -5.67128182, /* 351 */ -6.31375151, /* 352 */ -7.11536972, /* 353 */ -8.14434643, /* 354 */ -9.51436445, /* 355 */ -11.43005230, /* 356 */ -14.30066626, /* 357 */ -19.08113669, /* 358 */ -28.63625328, /* 359 */ -57.28996163, }; *[RECT]DRAW.C;1+,x. / 4S P-%e 0123KPWO 56SV7`cjW89G HJ /* draw.c */#include "o.h"#include "x.h"voidCreateGC(Viewport v);staticXColor screen_colors[16];staticvoid-QueryColors(Display *display, Screen *screen) { int i; for (i = 0; i < 16; i++) screen_colors[i].pixel = i; i = XQueryColors( display,# XDefaultColormapOfScreen(screen), &screen_colors[0], 16); for (i = 0; i < 16; i++) {7 printf("Color %d: red = %d, green = %d, blue = %d\n", screen_colors[i].pixel, screen_colors[i].red, screen_colors[i].green, screen_colors[i].blue); } }staticstruct _color_choices { char *name;, int fallback; /* A previous colors index */ } color_choices[] = {* /*0*/ { "black", 0 }, /* Must be first */+ /*1*/ { "white", 1 }, /* Must be second */ /*2*/ { "red", 1 }, /*3*/ { "blue", 1 }, /*4*/ { "green", 1 }, /*5*/ { "steel blue", 3 }, /*5*/ { "wheat", 1 }, }; #define COLOR_CHOICES_ELEMENTS \< ((sizeof color_choices) / (sizeof (struct _color_choices)))!#define NUMBER_OF_COLOR_CHOICES \J (COLOR_CHOICES_ELEMENTS < MAXCOLORS ? COLOR_CHOICES_ELEMENTS : MAXCOLORS)voidDefineColors(Viewport v){. int pixel, i, color_screen, query_colors = 0; Display *display = v->display; Screen *screen = v->screen;! XColor exact_color,screen_color;, v->colors[0] = XBlackPixelOfScreen(screen);, v->colors[1] = XWhitePixelOfScreen(screen); color_screen = (= ((XDefaultVisualOfScreen(screen))->class == PseudoColor) ||= ((XDefaultVisualOfScreen(screen))->class == DirectColor) );. for (i = 2; i < NUMBER_OF_COLOR_CHOICES; i++) { if (color_screen == 1) { if (XAllocNamedColor( display,% XDefaultColormapOfScreen(screen), color_choices[i].name, &screen_color, &exact_color)) {& v->colors[i] = screen_color.pixel;Mprintf("Color %s is index %d.\n", color_choices[i].name, screen_color.pixel); } else {C printf("Could not allocate the color %s. Using %s instead.\n", color_choices[i].name,4 color_choices[color_choices[i].fallback].name);8 v->colors[i] = v->colors[color_choices[i].fallback]; query_colors = 1; } } else {7 v->colors[i] = v->colors[color_choices[i].fallback]; } } v->background_color = 0; v->foreground_color = 1; if (query_colors)% QueryColors(v->display, v->screen); return; } voidInitialize_Draw() { return; }voidCreateGC(Viewport v) { XGCValues xgcv;2 xgcv.foreground = v->colors[v->foreground_color];2 xgcv.background = v->colors[v->background_color]; v->gc = XCreateGC( v->display, v->window, GCForeground | GCBackground, &xgcv); v->clipping = 0; XSetWindowBackground( v->display, v->window, xgcv.background); XClearWindow( v->display, v->window); }voidCancelClipping(Viewport v) {% RectangleList rl = v->exposed_areas; if (v->gc == 0) { /* Can't be clipping. */ v->clipping = 0; return; } if (rl != 0) rl->in_use = 0; if (v->clipping == 0) return; XSetClipMask( v->display, v->gc, None); v->clipping = 0; return; }voidSetClipRectangles(Viewport v) {% RectangleList rl = v->exposed_areas; if (rl->in_use == 0) { CancelClipping(v); return; } if (v->gc == 0) CreateGC(v); XSetClipRectangles( v->display, v->gc, 0, 0, rl->rectangles, rl->in_use, Unsorted); v->clipping = 1; }void8SetClipRectangle(Viewport v, int x, int y, int w, int h) { XRectangle rectangle; rectangle.x = x; rectangle.y = y; rectangle.width = w; rectangle.height= h; if (v->gc == 0) CreateGC(v);#ifdef VERBOSE-printf("SetClipRectangle(,%d, %d, %d, %d)\n",=rectangle.x, rectangle.y, rectangle.width, rectangle.height);#endif XSetClipRectangles( v->display, v->gc, 0, 0, &rectangle, 1, YXBanded); v->clipping = 1; } -#define CONVERT_POINTREC_TO_XPOINT(v, a, b) \2 (b.x) = ((a.x) - (v->bbox.minx)) * (v->hscale); \0 (b.y) = ((v->bbox.maxy) - (a.y)) * (v->vscale);void*DrawGameObject(Viewport v, GameObject obj) { Rectangle r = obj->rect; XPoint corners[4];A int color_index = (obj->id % (NUMBER_OF_COLOR_CHOICES - 1)) + 1; if (v->gc == 0) {$ v->foreground_color = color_index; CreateGC(v); }- else if (v->foreground_color != color_index) {$ v->foreground_color = color_index;< XSetForeground(v->display, v->gc, v->colors[color_index]); }; CONVERT_POINTREC_TO_XPOINT(v, r->vertices[0], corners[0]);; CONVERT_POINTREC_TO_XPOINT(v, r->vertices[1], corners[1]);; CONVERT_POINTREC_TO_XPOINT(v, r->vertices[2], corners[2]);; CONVERT_POINTREC_TO_XPOINT(v, r->vertices[3], corners[3]);#ifdef VERBOSESprintf("XFillPolygon(,,,{{%d, %d}, {%d, %d}, {%d, %d}, {%d, %d}}, 4,Nonconvex,)\n",corners[0].x, corners[0].y,corners[1].x, corners[1].y,corners[2].x, corners[2].y,corners[3].x, corners[3].y);#endif XFillPolygon( v->display, v->window, v->gc, &corners[0], 4, Nonconvex, CoordModeOrigin); }*[RECT]EXPOSE.C;1+,x ./ 4Z R-%e 0123KPWO56`Q T7ŴW89G HJ/* Expose.c */#include "o.h"#include "x.h"staticGameObject exposed_objects = 0;#define MAXOBJECTS 1024#define MAXVIEWERS 32#define MAXEXPOSURES 32void?PrependExposedRectangle(Viewport v, int x, int y, int w, int h) {% RectangleList rl = v->exposed_areas;#ifdef VERBOSEZprintf("PrependExposedRectangle(v=%x, x=%d, y=%d, width=%d, height=%d)\n", v, x, y, w, h);#endif VERBOSE+ /* Save the exposed area for later use. */ if (rl == 0) {$ v->exposed_areas = (RectangleList)# malloc(sizeof(RectangeListRec) +3 sizeof(XRectangle) * (_X_RECTANGLE_COUNT - 1)); rl = v->exposed_areas; rl->total = 10; rl->in_use = 0; }" else if (rl->total == rl->in_use) {1 int new_total = rl->total + _X_RECTANGLE_COUNT; /* Need more room! */$ v->exposed_areas = (RectangleList)( realloc(rl, sizeof(RectangeListRec) +* sizeof(XRectangle) * (new_total - 1)); rl = v->exposed_areas; rl->total = new_total; }# rl->rectangles[rl->in_use].x = x;# rl->rectangles[rl->in_use].y = y;& rl->rectangles[rl->in_use].width = w;' rl->rectangles[rl->in_use].height = h; rl->in_use++; } staticvoid.ExposeObject(ObjectList *head, GameObject obj) {/ ObjectList *prev = head, current = *head, new;> /* Find where obj belongs in the list (ordered by height). */ while (current) {+ if (obj == (GameObject)(current->object))% return; /* Already in the list. */< if (((GameObject)(current->object))->height > obj->height) break; /* Insert here. */ prev = &(current->next); current = current->next; } new = AllocateObjectList(); new->next = current; new->object = (void *)obj; *prev = new; return; } void/ExposedViewingArea(Viewport v, XExposeEvent *e) { int count, i, r; GameObject obj; BoundingBoxRec world_exposed; GameObject overlap[MAXOBJECTS]; RectangleList rl = 0; ObjectList ol = 0;+ /* Save the exposed area for later use. */= PrependExposedRectangle(v, e->x, e->y, e->width, e->height);) /* Paint the background in this area. */L /* If more exposures are expected, wait for them before doing more work. */ if (e->count > 0) return;G /* For each exposed rectangle in the viewport, determine which objects * were exposed. */ v->exposed_objects = 0; rl = v->exposed_areas;! for (r = 0; r < rl->in_use; r++) {H /* Determine which part of the world coordinate system was exposed. */& world_exposed.minx = v->bbox.minx + # rl->rectangles[r].x / v->hscale;& world_exposed.maxx = v->bbox.minx + 2 (rl->rectangles[r].x + rl->rectangles[r].width) / v->hscale;% world_exposed.maxy = v->bbox.maxy -# rl->rectangles[r].y / v->vscale;% world_exposed.miny = v->bbox.maxy -4 (rl->rectangles[r].y + rl->rectangles[r].height)  / v->vscale;#ifdef VERBOSE:printf("Exposed world area: X = [%d, %d], Y = [%d, %d]\n",Pworld_exposed.minx, world_exposed.maxx, world_exposed.miny, world_exposed.maxy);#endif VERBOSE- /* Determine which objects were exposed. */ count = QT_SimpleSearch: (ObjectsQuadtree, overlap, MAXOBJECTS, &world_exposed);@ /* Add these objects to the ORDERED SET of exposed objects. */ for (i = 0; i < count; i++)1 ExposeObject(&v->exposed_objects, overlap[i]); }4 /* Set the GC to clip to the exposed rectangles. */ SetClipRectangles(v); /* Draw the exposed objects. */ ol = v->exposed_objects; v->exposed_objects = 0; while(ol != 0) { ObjectList next = ol->next;. DrawGameObject(v, (GameObject)(ol->object)); DeallocateObjectList(ol); ol = next; } return; } 5/* All of a viewport has been exposed. Redraw it. */voidExposedViewport(Viewport v) { int count, i; GameObject overlap[MAXOBJECTS]; /* Cancel any clipping. */ CancelClipping(v); /* Paint the background. */% XClearWindow(v->display, v->window);, /* Determine which objects were exposed. */ count = QT_SimpleSearch3 (ObjectsQuadtree, overlap, MAXOBJECTS, &v->bbox); /* Draw the exposed objects. */ for(i = 0; i < count; i++) DrawGameObject(v, overlap[i]); return; } ExposeArea(BoundingBox b) { int vcount, ecount, i, j; Viewport viewers[MAXVIEWERS]; GameObject exposed[MAXOBJECTS]; ObjectList sorted_set = 0, ol;4 /* Find out which viewports are watching area b. */ vcount = QT_SimpleSearch. (ViewportsQuadtree, viewers, MAXVIEWERS, b);#ifdef VERBOSEEprintf("ExposeArea(X=[%d,%d], Y=[%d,%d]) visible to %d viewports.\n",,b->minx, b->maxx, b->miny, b->maxy, vcount);#endif VERBOSE if (vcount == 0) return;4 /* And find out which objects are in the area b. */ ecount = QT_SimpleSearch, (ObjectsQuadtree, exposed, MAXOBJECTS, b);? /* Add these objects to the ORDERED SET of exposed objects. */F /* DOING THIS BECAUSE IT SORTS THEM BY HEIGHT, SO I DON'T HAVE TO. */ for (i = 0; i < ecount; i++)( ExposeObject(&sorted_set, exposed[i]);> /* For each viewport, redraw the background, then the exposed * objects. */ for (i = 0; i < vcount; i++) { int x, y, x1, y1; unsigned int width, height; Viewport v; v = viewers[i];( /* Translate to viewer coordinates. */+ x = (b->minx - v->bbox.minx) * v->hscale;+ y = (v->bbox.maxy - b->maxy) * v->vscale;+ x1= (b->maxx - v->bbox.minx) * v->hscale;+ y1= (v->bbox.maxy - b->miny) * v->vscale; width = x1 - x + 1; height = y1 - y + 1;+ SetClipRectangle(v, x, y, width, height);) /* Draw the background in this area. */#ifdef VERBOSE?printf("XClearArea(,,%d, %d, %d, %d,)\n", x, y, width, height);#endif XClearArea( v->display, v->window, x, y, width, height, 0);# /* Redraw each exposed object. */ ol = sorted_set; while(ol) {/ DrawGameObject(v, (GameObject)(ol->object)); ol = ol->next; } }2 /* Now deallocate the list of exposed objects. */ ol = sorted_set; while(ol) { ObjectList next = ol->next; DeallocateObjectList(ol); ol = next; } return; } *[RECT]O.C;1+,x ./ 4P-%e 0123KPWO56|V7juW89G HJw;~RECT.BCKx %e  [RECT]O.C;1P90 /* o.c */ #include #define _O_C#include "o.h"#define MAXOBJECTS 128+static GameObject object_index[MAXOBJECTS];2static GameObject overlapping_objects[MAXOBJECTS];!static int update_interval = 500;BoundingBoxRec the_world_area;Initialize_Objects() { int i;' the_world_area.minx = KM_TO_UNITS(-1);& the_world_area.maxx = KM_TO_UNITS(1);' the_world_area.miny = KM_TO_UNITS(-1);& the_world_area.maxy = KM_TO_UNITS(1); ObjectsQuadtree = QT_Create(, METERS_TO_UNITS(10) * METERS_TO_UNITS(10), the_world_area.minx, the_world_area.maxx, the_world_area.miny, the_world_area.maxy); ViewportsQuadtree = QT_Create(, METERS_TO_UNITS(10) * METERS_TO_UNITS(10), the_world_area.minx, the_world_area.maxx, the_world_area.miny, the_world_area.maxy); for (i=0; i < MAXOBJECTS; i++) object_index[i] = 0; },/*extern int the_viewport;*/ /* Temporary */InsertObject(GameObject obj) {+ /* Insert the object into the quadtree. */G obj->object_qt_id = QT_Insert(ObjectsQuadtree, obj, &obj->rect->bbox);@ /* Generate exposure events in the appropriate viewports. This( * causes the rectangle to be drawn. */ ExposeArea(&obj->rect->bbox); }RemoveObject(GameObject obj) {3 /* Remove the object from the objects quadtree. *// QT_Remove(ObjectsQuadtree, obj->object_qt_id); obj->object_qt_id = 0;= /* Generate exposure events in the appropriate viewports. */ ExposeArea(&obj->rect->bbox); }intPIntersectingObjects(GameObject obj, GameObject overlapping_objects[], int count) { int count2, i, j;, /* Determine which objects obj overlaps. */? count2 = QT_SimpleSearch(ObjectsQuadtree, overlapping_objects, count, &obj->rect->bbox);( if ((count2 == count) || (count2 == 0)) return count2; j = 0; for (i = 0; i < count2; i ++) {( if ((obj != overlapping_objects[i]) &&$ RectanglesIntersect(obj->rect,# overlapping_objects[i]->rect)) { overlapping_objects[j++] = overlapping_objects[i]; } } return j; }void ReportCollisions(GameObject obj) { int count = 0, i;3 /* Determine which objects it will now overlap. */G/* count = IntersectingObjects(obj, overlapping_objects, MAXOBJECTS);*/ if (count) {#ifdef VERBOSEprintf(="Found the following %d objects which object %d overlaps:\n",count, obj->id);#endif VERBOSE#ifdef VERBOSE for(i = 0; i < count; i++)-printf("\t%d\n", overlapping_objects[i]->id);#endif VERBOSE } }void)SetObjectAngle(GameObject obj, int angle) {/ BoundingBoxRec bbox1 = obj->rect->bbox, bbox2; RectangleRec covered; Rectangle new; if (obj->rect->angle == angle) return;3 /* Remove the object from the objects quadtree. *// QT_Remove(ObjectsQuadtree, obj->object_qt_id); obj->object_qt_id = 0; /* Set the new angle. */ obj->rect->angle = angle; RotateRectangle(obj->rect, 0);3 /* Determine which objects it will now overlap. */ ReportCollisions(obj);* /* Replace the object in the quadtree. */G obj->object_qt_id = QT_Insert(ObjectsQuadtree, obj, &obj->rect->bbox);! /* Redraw areas as necessary. */, BoxesBox(&bbox2, &bbox1, &obj->rect->bbox); ExposeArea(&bbox2); return; }voidASetObjectPosition(GameObject obj, T_COORDINATE x, T_COORDINATE y) {/ BoundingBoxRec bbox1 = obj->rect->bbox, bbox2; RectangleRec covered; Rectangle new;> if ((obj->rect->center.x == x) && (obj->rect->center.y == y)) return;3 /* Remove the object from the objects quadtree. *// QT_Remove(ObjectsQuadtree, obj->object_qt_id); obj->object_qt_id = 0; /* Set the new position. */ TranslateRectangle(obj->rect, x - obj->rect->center.x, y - obj->rect->center.y);3 /* Determine which objects it will now overlap. */ ReportCollisions(obj);* /* Replace the object in the quadtree. */G obj->object_qt_id = QT_Insert(ObjectsQuadtree, obj, &obj->rect->bbox);! /* Redraw areas as necessary. */, if (BoxesOverlap(&bbox1, &obj->rect->bbox)) {- BoxesBox(&bbox2, &bbox1, &obj->rect->bbox); ExposeArea(&bbox2); } else { ExposeArea(&bbox1); ExposeArea(&obj->rect->bbox); } return; }void$UpdateObjectPosition(GameObject obj) {/ BoundingBoxRec bbox1 = obj->rect->bbox, bbox2;- BoundingBox exposed1 = &bbox1, exposed2 = 0; RectangleRec covered; Rectangle new;3 /* Remove the object from the objects quadtree. *// QT_Remove(ObjectsQuadtree, obj->object_qt_id); obj->object_qt_id = 0;: /* If the object is rotating, rotate before moving it. */# if (obj->rotational_velocity != 0) {7 RotateRectangle(obj->rect, obj->rotational_velocity); } /* Move the object. */ if (obj->velocity != 0) { new = AllocateRectangle();> RectangleTraversed(obj->rect, obj->velocity, &covered, new);6 /* Determine which objects have been intersected. */% /* Get rid of the old rectangle. */! DeallocateRectangle(obj->rect); obj->rect = new; } 3 /* Determine which objects it will now overlap. */ ReportCollisions(obj);* /* Replace the object in the quadtree. */G obj->object_qt_id = QT_Insert(ObjectsQuadtree, obj, &obj->rect->bbox);! /* Redraw areas as necessary. */, if (BoxesOverlap(&bbox1, &obj->rect->bbox)) {- BoxesBox(&bbox2, &bbox1, &obj->rect->bbox); ExposeArea(&bbox2); } else { ExposeArea(&bbox1); ExposeArea(&obj->rect->bbox); } return; }intUpdateAllObjectPositions() { GameObject obj = game_objects;/*#ifdef VERBOSE 'printf("UpdateAllObjectPositions()\n"); #endif*/ while (obj) { if (obj->moving) UpdateObjectPosition(obj); obj = obj->next; } return update_interval; }+ProcessObjectCommand(char *tag, char *line) {D T_COORDINATE cx, cy, h, w, angle, dx, dy, rx, lx, by, ty, velocity; QUADTREE_OBJECTID id; int items, count, i; BoundingBoxRec bbox; GameObject obj; switch (line[0]) { case 'a': case 'A':1 items = sscanf(line+1, "%d %d\n", &id, &angle); if (items != 2) { printf(4 "Error! Format is \"A \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; } obj->rotational_velocity = 0;% obj->moving = (obj->velocity != 0); SetObjectAngle(obj, angle); break; case 'c': case 'C': items = sscanf(line+1,9 "%d %d %d %d %d %d\n", &id, &cx, &cy, &h, &w, &angle); if (items != 6) { printf(F "Error! Format is \"C \".\n"); break; } if (object_index[id] != 0) {1 printf("Error. That object id is in use.\n"); break; }* object_index[id] = AllocateGameObject(); obj = object_index[id]; obj->id = id; obj->height = id; InitRectangle( obj->rect, METERS_TO_UNITS(cx), METERS_TO_UNITS(cy), METERS_TO_UNITS(h), METERS_TO_UNITS(w), angle);, /* Determine which objects it overlaps. */D count = IntersectingObjects(obj, overlapping_objects, MAXOBJECTS); if (count) { printf(? "Found the following %d objects which object %d overlaps:\n", count, id); for(i = 0; i < count; i++)1 printf("\t%d\n", overlapping_objects[i]->id); }0 /* Now insert the object into the quadtree. */ InsertObject(obj);P printf("Inserted object %d. Bounding box covers X = [%d,%d], Y = [%d,%d].\n", id, obj->rect->bbox.minx, obj->rect->bbox.maxx, obj->rect->bbox.miny, obj->rect->bbox.maxy); break; case 'd': case 'D':& items = sscanf(line+1, "%d\n", &id); if (items != 1) { printf(, "Error! Format is \"D \".\n"); break; } if (object_index[id] == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; }! RemoveObject(object_index[id]);) DeallocateGameObject(object_index[id]); object_index[id] = 0;% printf("Deleted object %d.\n", id); break; case 'h': case 'H':- items = sscanf(line+1, "%d %d\n", &id, &i); if (items != 2) { printf(8 "Error! Format is \"H \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; } obj->height = i; break; case 'i': case 'I': items = sscanf(line+1, "%d\n", &i); if (items != 1) { printf(? "Error! Format is \"I \".\n"); break; } if (i < 10)L printf("Error! Argument must be a positive integer greater than 10.\n"); else update_interval = i; break; case 'm': case 'M': items = sscanf(line+1, "%d %d\n", &id, &velocity); if (items != 2) { printf(7 "Error! Format is \"M \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; }, obj->velocity = METERS_TO_UNITS(velocity); obj->moving == ((obj->rotational_velocity != 0) || (obj->velocity != 0));/ printf("Velocity for object %d set to %d.\n", id, velocity); break; case 'p': case 'P':& items = sscanf(line+1, "%d\n", &id); if (items != 1) { printf(, "Error! Format is \"P \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; }P printf("Object %d: center @ (%d, %d), height = %d, width = %d, angle = %d,\n", id, obj->rect->center.x, obj->rect->center.y, obj->rect->height, obj->rect->width, obj->rect->angle); for (i = 0; i < 4; i++)% printf("\tVertex %d @ (%d, %d)\n", i, obj->rect->vertices[i].x, obj->rect->vertices[i].y); if (obj->rect->aligned)& printf("\tRectangle is aligned\n"); else for (i = 0; i < 4; i++)) printf("\tEdge %d: a = %f, b = %d\n", i, obj->rect->edges[i].slope,& obj->rect->edges[i].y_intercept);9 printf("\tBounding box is X = [%d,%d], Y = [%d,%d].\n", obj->rect->bbox.minx, obj->rect->bbox.maxx, obj->rect->bbox.miny, obj->rect->bbox.maxy); break; case 'r': case 'R': items = sscanf(line+1, "%d %d\n", &id, &angle); if (items != 2) { printf(B "Error! Format is \"R \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; }# obj->rotational_velocity = angle; obj->moving == ((obj->rotational_velocity != 0) || (obj->velocity != 0));: printf("Rotational velocity for object %d set to %d.\n", id, angle); break; case 's': case 'S':% items = sscanf(line+1, "%d\n", &i); if (items != 1) { printf(0 "Error! Format is \"S \".\n"); break; } if (i <= 0) {D printf("The scale factor must be greater than or equal to 1.\n"); break; } SetXtViewportScale(tag, i); break; case 't': case 'T': items = sscanf(line+1, "%d %d %d\n", &id, &cx, &cy); if (items != 3) { printf(6 "Error! Format is \"T \".\n"); break; }$ if ((obj = object_index[id]) == 0) {4 printf("Error. Object %d doesn't exist.\n", id); break; } obj->velocity = 0;0 obj->moving = (obj->rotational_velocity != 0);C SetObjectPosition(obj, METERS_TO_UNITS(cx), METERS_TO_UNITS(cy)); break; default:1 printf("Command \"%c\" not known.\n", line[0]);B printf("Try C, D, M, or R (Create, Delete, Move, or Rotate)\n"); break; }/* End switch */ }*[RECT]PRINTEVENT.C;1+,x./ 4F-%e 0123KPWO565RՒ7`8W89G HJ#include char *types[] = { "Error", "Reply", "KeyPress", "KeyRelease", "ButtonPress", "ButtonRelease", "MotionNotify", "EnterNotify", "LeaveNotify", "FocusIn", "FocusOut", "KeymapNotify", "Expose", "GraphicsExpose", "NoExpose", "VisibilityNotify", "CreateNotify", "DestroyNotify", "UnmapNotify", "MapNotify", "MapRequest", "ReparentNotify", "ConfigureNotify", "ConfigureRequest", "GravityNotify", "ResizeRequest", "CirculateNotify", "CirculateRequest", "PropertyNotify", "SelectionClear", "SelectionRequest", "SelectionNotify", "ColormapNotify", "ClientMessage", "MappingNotify"};void PrintEvent(eventP) XEvent *eventP;{- printf("\nType: %s\n", types[eventP->type]); switch (eventP->type) { case 0: case 1: break; case KeyPress: case KeyRelease: case ButtonPress: case ButtonRelease: case MotionNotify: case EnterNotify: case LeaveNotify: case FocusIn: case FocusOut: case KeymapNotify: case Expose: case GraphicsExpose: case NoExpose: case VisibilityNotify: case CreateNotify: case DestroyNotify: case UnmapNotify: case MapNotify: case MapRequest: case ReparentNotify: case ConfigureNotify: case ConfigureRequest: case GravityNotify: case ResizeRequest: case CirculateNotify: case CirculateRequest: case PropertyNotify: case SelectionClear: case SelectionRequest: case SelectionNotify: case ColormapNotify: case ClientMessage: case MappingNotify:F printf("serial = %d, send_event = %d, display = %x, window = %x\n", eventP->xany.serial, eventP->xany.send_event, eventP->xany.display, eventP->xany.window); break; }}*[RECT]QUADTREE.C;1+,x ./ 4R-%e 0123KPWO56`(]-H7"nW89G HJ/* Quadtree.c James M Synge *F * A quadtree is a two-dimensional data structure, like a binary tree,H * expect that each node has four children, one for each quadrant of the * rectangle it represents. *I * This particular instance is used to 'store' aligned rectangles. TheseK * rectangles may overlap. A rectangle is stored in a linked list attachedK * to the lowest node which completely contains it. If a rectangle crossesC * the axes of a node, then it can not be stored lower in the tree. *J * I've embellished this version by allowing those rectangles which touch,L * but don't cross, an axis to be pushed lower in the tree. This can reduce * searching time. * * The coordinate system is: * * y>0 * ^ * NW | NE * |# *x<0 <----------+------------> x>0 * | * SW | SE * | * V * y<0 */#include "quadtree_int.h"Quadtree QT_Create(T_COORDINATE min_area,& T_COORDINATE minx, T_COORDINATE maxx,& T_COORDINATE miny, T_COORDINATE maxy) { Quadtree q; T_COORDINATE area; int levels;& if ((minx >= maxx) || (miny >= maxy)) {4 printf("QT_Create: specified area is invalid!\n"); return 0; } if (min_area <= 0) {# printf("QT_Create: min_area!\n"); return 0; }7 /* Compute the number of levels, based on min_area. */& area = (maxx - minx) * (maxy - miny);- for (levels = 0; area > min_area; levels ++) area = area / 4; if (levels) levels --; /* Create the quadtree node. */+ q = (Quadtree)malloc(sizeof(QuadtreeRec)); #ifdef DEBUGAprintf("Allocated root of quadtree @ %x, level = %d", q, levels);#endif q->rect.minx = minx; q->rect.maxx = maxx;! q->center.x = (minx + maxx) / 2; q->rect.miny = miny; q->rect.maxy = maxy;! q->center.y = (miny + maxy) / 2; q->quadrants[NE_Quad] = 0; q->quadrants[NW_Quad] = 0; q->quadrants[SW_Quad] = 0; q->quadrants[SE_Quad] = 0; q->objects = 0; q->parent = 0; q->level = levels; return q; }staticQuadtree-CreateQuadrant(Quadtree q, QUADRANT quadrant) {8 Quadtree child = (Quadtree)malloc(sizeof(QuadtreeRec)); q->quadrants[quadrant] = child; child->quadrants[NE_Quad] = 0; child->quadrants[NW_Quad] = 0; child->quadrants[SW_Quad] = 0; child->quadrants[SE_Quad] = 0; child->objects = 0; child->parent = q; child->level = q->level - 1; #ifdef DEBUGRprintf("Allocated quadtree @ %x for quadrant %d of quadtree @ %x. level = %d\n", "child, quadrant, q, child->level);#endif switch (quadrant) { case NE_Quad:! child->rect.minx = q->center.x;" child->rect.maxx = q->rect.maxx;! child->rect.miny = q->center.y;" child->rect.maxy = q->rect.maxy; break; case NW_Quad:" child->rect.minx = q->rect.minx;! child->rect.maxx = q->center.x;! child->rect.miny = q->center.y;" child->rect.maxy = q->rect.maxy; break; case SW_Quad:" child->rect.minx = q->rect.minx;! child->rect.maxx = q->center.x;" child->rect.miny = q->rect.miny;! child->rect.maxy = q->center.y; break; case SE_Quad:! child->rect.minx = q->center.x;" child->rect.maxx = q->rect.maxx;" child->rect.miny = q->rect.miny;! child->rect.maxy = q->center.y; break; }/* end switch */= child->center.x = (child->rect.minx + child->rect.maxx) / 2;= child->center.y = (child->rect.miny + child->rect.maxy) / 2; return child; }staticQUADRANT<BoxQuadrant(BoundingBox box, T_COORDINATE x, T_COORDINATE y) { if (box->maxx <= x) { /* Westerly */ if (box->miny >= y) return NW_Quad; else if (box->maxy <= y) return SW_Quad; else return Multiple_Quadrants; } else if (box->minx >= x) { /* Easterly */ if (box->miny >= y) return NE_Quad; else if (box->maxy <= y) return SE_Quad; else return Multiple_Quadrants; } else return Multiple_Quadrants; } ?QT_Object QT_Insert(Quadtree rootq, QUADTREE_OBJECTID objectid, BoundingBox objectrange) { QT_Object r; Quadtree q = rootq; QUADRANT quadrant; int dx, dy; if (q == 0) {1 printf("QT_Insert: quadtree not specified!\n"); return 0; } if (objectrange == 0) {< printf("QT_Insert: rectangle to insert not specified!\n"); return 0; }, if (!BoxesOverlap(&(q->rect), objectrange)) { printf(? "QT_Insert: rectangle not contained in quadtree area!\n"); return 0; }- r = (QT_Object)malloc(sizeof(QT_ObjectRec)); #ifdef DEBUGAprintf("Allocate QT_Object @ %x for objectid %d\n", r, objectid);#endif" r->rect.minx = objectrange->minx;" r->rect.maxx = objectrange->maxx;" r->rect.miny = objectrange->miny;" r->rect.maxy = objectrange->maxy; r->id = objectid; r->next_object = 0; r->container = 0;, /* As long as r doesn't intersect the lines * * X == q -> center.x, and * * Y == q -> center.y, * * keep subdividing the tree. */ while (1) { if (q->level == 0) break;0 /* Which quadrant encloses the rectangle r? */? quadrant = BoxQuadrant(&(r->rect), q->center.x, q->center.y);% if (quadrant == Multiple_Quadrants) break;6 /* Get the address of that quadrant's quadtree node.0 * If the node hasn't yet been created, do so. */" if (q->quadrants[quadrant] == 0)# q = CreateQuadrant(q, quadrant); else q = q->quadrants[quadrant]; }+ /* We've subdivided as far as possible. */ r->container = q; r->next_object = q->objects; q->objects = r; #ifdef DEBUG=printf("Attaching object %d to quadtree @ %x. level = %d\n",objectid, q, q->level);#endif return r; } int"QT_Remove(Quadtree q, QT_Object o) { QT_Object prev; if ((q == 0) || (o == 0)) {3 printf("QT_Remove: invalid pointer argument!\n"); return 0; } if (o->container == 0) {3 printf("QT_Remove: invalid object container!\n"); return 0; } q = o->container; if (q->objects == o) { q->objects = o->next_object; #ifdef DEBUG;printf("Detaching object @ %x from quadtree @ %x\n", o, q);#endif free(o);/ while ((q->objects == 0) && (q->parent != 0)) {& if ((q->quadrants[NE_Quad] == 0) &&& (q->quadrants[NW_Quad] == 0) &&& (q->quadrants[SW_Quad] == 0) &&$ (q->quadrants[SE_Quad] == 0)) { int i = 0; Quadtree p = q->parent;7 /* There are no objects enclosed by this rectangle.' * Find out which quadrant this is. */ for (i = 0; i < 4; i++) { if (p->quadrants[i] == q) { p->quadrants[i] = 0; break; } } #ifdef DEBUG*printf("Deallocating quadtree @ %x\n", q);#endif free(q); q = p; } else return 1; } return 1; }# /* Find the object on the list. */ prev = q->objects;0 while ((prev != 0) && (prev->next_object != o)) prev = prev->next_object; if (prev == 0) {B printf("QT_Remove: object is not on containers object list!\n"); return 0; }$ prev->next_object = o->next_object; #ifdef DEBUG;printf("Detaching object @ %x from quadtree @ %x\n", o, q);#endif free(o); return 1; }*[RECT]QUADTREE_SEARCH.C;1+,x./ 4T-%e 0123KPWO56-ۊM7`0"W89G HJ"#/* Quadtree_Search.c James M Synge *F * A quadtree is a two-dimensional data structure, like a binary tree,H * expect that each node has four children, one for each quadrant of the * rectangle it represents. *I * This particular instance is used to 'store' aligned rectangles. TheseK * rectangles may overlap. A rectangle is stored in a linked list attachedK * to the lowest node which completely contains it. If a rectangle crossesC * the axes of a node, then it can not be stored lower in the tree. *J * I've embellished this version by allowing those rectangles which touch,L * but don't cross, an axis to be pushed lower in the tree. This can reduce * searching time. * * The coordinate system is: * * y>0 * ^ * NW | NE * |# *x<0 <----------+------------> x>0 * | * SW | SE * | * V * y<0 *@ * This module provides a number of quadtree searching routines. */#include "quadtree_int.h" B/* Append all objects attached to this quadtree, and its children, * to the list objectids. */staticintLDegenerateSimpleSearch(Quadtree q, QUADTREE_OBJECTID objectids[], int count) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child;C /* All entries in this quadrant are in the specified rectangle. */ while (obj) { objectids[i++] = obj->id; if (i == count) return i; obj = obj->next_object; }D /* Recurse to append all objects at lower levels on to the list. */. for (quadrant = 0; quadrant < 4; quadrant ++) {, if (0 == (child = q->quadrants[quadrant])) continue;? i += DegenerateSimpleSearch(child, &objectids[i], count - i); if (i == count) return i; } return i; }7/* Find all entries in the quadtree which intersect the4 * specified rectangle, and return their object ids. */intTQT_SimpleSearch(Quadtree q, QUADTREE_OBJECTID objectids[], int count, BoundingBox r) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child;5 /* Compare against all the entries at this level. */ while (obj) {$ if (BoxesOverlap(&(obj->rect), r)) { objectids[i++] = obj->id; if (i == count) return i; } obj = obj->next_object; }= /* If the rectangle r overlaps with a quadrant, then recurse) * to examine the objects at that level. */. for (quadrant = 0; quadrant < 4; quadrant ++) {, if (0 == (child = q->quadrants[quadrant])) continue;& if (BoxContained(&(child->rect), r)) {@ i += DegenerateSimpleSearch(child, &objectids[i], count - i); if (i == count) return i; }+ else if (BoxesOverlap(&(child->rect), r)) {< i += QT_SimpleSearch(child, &objectids[i], count - i, r); if (i == count) return i; } } return i; } 6/* For each entry in the quadtree which intersects the3 * specified rectangle call the supplied procedure. */staticvoid *DDegenerateSearch(Quadtree q, QT_ObjectProc objectproc, int user_arg) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child; void *retval;C /* All entries in this quadrant are in the specified rectangle. */ while (obj) {, retval = (*objectproc)(obj->id, user_arg); if (retval != 0) return retval; obj = obj->next_object; }D /* Recurse to append all objects at lower levels on to the list. */. for (quadrant = 0; quadrant < 4; quadrant ++) {, if (0 == (child = q->quadrants[quadrant])) continue;9 retval = DegenerateSearch(child, objectproc, user_arg); if (retval != 0) return retval; } return i; } void *QT_Search(Quadtree q, QT_ObjectProc objectproc, QT_OverlapProc overlapproc, void *user_context) { int i = 0, quadrant, tmp; QT_Object obj = q->objects; Quadtree child; void *retval;5 /* Compare against all the entries at this level. */ while (obj) {3 tmp = (*overlapproc)(&(obj->rect), user_context); if (tmp != 0) {( retval = (*objectproc)(obj->id, tmp); if (retval != 0) return retval; } obj = obj->next_object; }= /* If the rectangle r overlaps with a quadrant, then recurse) * to examine the objects at that level. */. for (quadrant = 0; quadrant < 4; quadrant ++) {, if (0 == (child = q->quadrants[quadrant])) continue;5 tmp = (*overlapproc)(&(child->rect), user_context); if (tmp == 0) continue; else if (tmp < 0) {5 retval = DegenerateSearch(child, objectproc, tmp); if (retval != 0) return retval; } else { retval = QT_Search(child, objectproc, overlapproc, user_context); if (retval != 0) return retval; } } return i; } )/* Find all entries in the quadtree which* * intersect the specified unaligned line. */staticintKIntersectLine(Quadtree q, QUADTREE_OBJECTID objectids[], int count, Line l) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child;5 /* Compare against all the entries at this level. */ while (obj) {) if (BoxAndLineIntersect(&obj->rect, l)) { objectids[i++] = obj->id; if (i == count) return i; } obj = obj->next_object; }5 /* If the line l intersects a quadrant, then recurse) * to examine the objects at that level. */. for (quadrant = 0; quadrant < 4; quadrant ++) {0 if ((0 != (child = q->quadrants[quadrant])) &&- (BoxAndLineIntersect(&child->rect, l))) {: i += IntersectLine(child, &objectids[i], count - i, l); if (i == count) return i; } } return i; })/* Find all entries in the quadtree which) * intersect the specified vertical line. */int QT_IntersectVertical(Quadtree q," QUADTREE_OBJECTID objectids[], int count, T_COORDINATE x) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child;5 /* Compare against all the entries at this level. */ while (obj) {1 if (BETWEEN(x, obj->rect.minx, obj->rect.maxx)) { objectids[i++] = obj->id; if (i == count) return i; } obj = obj->next_object; }5 /* If the line l intersects a quadrant, then recurse) * to examine the objects at that level. */ if (q->level <= 0) return i; if (x <= q->center.x) {+ if (0 != (child = q->quadrants[NW_Quad])) {A i += QT_IntersectVertical(child, &objectids[i], count - i, x); if (i == count) return i; }+ if (0 != (child = q->quadrants[SW_Quad])) {A i += QT_IntersectVertical(child, &objectids[i], count - i, x); if (i == count) return i; } } if (x >= q->center.x) {+ if (0 != (child = q->quadrants[NE_Quad])) {A i += QT_IntersectVertical(child, &objectids[i], count - i, x); if (i == count) return i; }+ if (0 != (child = q->quadrants[SE_Quad])) {A i += QT_IntersectVertical(child, &objectids[i], count - i, x); if (i == count) return i; } } return i; })/* Find all entries in the quadtree which+ * intersect the specified horizontal line. */staticintIntersectHorizontal(Quadtree q," QUADTREE_OBJECTID objectids[], int count, T_COORDINATE y) { int i = 0, quadrant; QT_Object obj = q->objects; Quadtree child;5 /* Compare against all the entries at this level. */ while (obj) {1 if (BETWEEN(y, obj->rect.miny, obj->rect.maxy)) { objectids[i++] = obj->id; if (i == count) return i; } obj = obj->next_object; }6 /* If the horizontal line intersects a quadrant, then1 * recurse to examine the objects at that level. */ if (q->level <= 0) return i; if (y <= q->center.y) {+ if (0 != (child = q->quadrants[SW_Quad])) {@ i += IntersectHorizontal(child, &objectids[i], count - i, y); if (i == count) return i; }+ if (0 != (child = q->quadrants[SE_Quad])) {@ i += IntersectHorizontal(child, &objectids[i], count - i, y); if (i == count) return i; } } if (y >= q->center.y) {+ if (0 != (child = q->quadrants[NW_Quad])) {@ i += IntersectHorizontal(child, &objectids[i], count - i, y); if (i == count) return i; }+ if (0 != (child = q->quadrants[NE_Quad])) {@ i += IntersectHorizontal(child, &objectids[i], count - i, y); if (i == count) return i; } } return i; }=7~RECT.BCKx%e [RECT]QUADTREE_SEARCH.C;1TlintNQT_IntersectLine(Quadtree q, QUADTREE_OBJECTID objectids[], int count, Line l) { if (l->slope == 0.0)B return IntersectHorizontal(q, objectids, count, l->y_intercept);. return IntersectLine(q, objectids, count, l); }*[RECT]RECT.C;1+,>| ./ 4EJ-%e 0123KPWO56@1xnV7#зW89G HJ /* rect.c" * Author: James Millington Synge * Creation Date: April 7, 1990 */!#include #include "xt.h"!extern void Initialize_Objects();)extern void ProcessObjectCommand(char *);'extern int UpdateAllObjectPositions();%extern BoundingBoxRec the_world_area;extern int Initialize_Draw(); static void Update();>static char *db_filename_vec[] = /* DRM heirachy file list. */5 {"rect.uid" /* There is only one UID file for */ }; /* this application. */Estatic DRMHierarchy drmHierarchy; /* DRM database hierarchy ID */static Widget godW;static Xt_Viewport xt_viewport; main(argc, argv) char **argv; int argc;{ DwtCallback callback; DRMType class_return;* DwtInitializeDRM(); /* Initialize DRM */? /* Open the display and create a main window widget for it. */; godW = XtInitialize("rect", "rect", NULL, 0, &argc, argv);& /*XSynchronize(XtDisplay(godW), 1);*/& /* Initialize the various modules. */ Initialize_Objects(); Initialize_Draw();0 /* Open the UID file[s] for the application. */2 if (DwtOpenHierarchy ( XtNumber(db_filename_vec), db_filename_vec, 0, &drmHierarchy) != DRMSuccess) {> printf ("Failure - Can't open %s file", db_filename_vec[0]); exit(0); };! /* Create the first viewport. */ xt_viewport = CreateXtViewport( drmHierarchy,2 (the_world_area.minx + the_world_area.maxx) / 2,2 (the_world_area.miny + the_world_area.maxy) / 2,& 300, 300, /* Window size, pixels. */A 100); /* Scale: 1 inch on screen equal to 100 in the world. */ /* Display the windows. */ XtAddTimeOut(2000, Update, 0); XtMainLoop();} static void Update(Opaque data) {8 XtAddTimeOut(UpdateAllObjectPositions(), Update, data); XFlush( XtDisplay(godW) ); }*[RECT]RECTANGLE.C;1+,?|.'/ 4P'%-%e 0123KPWO&56 T7`W89G HJJ/* rectangles.c * * Functional Description: * * * Regions around a rectangle 0: * * | | * 4 | 3 | 2 * | | * -------+-------+------ * | | * 5 | 0 | 1 * | | * -------+-------+------ * | | * 6 | 7 | 8 * | | * * * * Author: James M Synge */#define _RECTANGLE_C#include "rectangle.h" /* c r */ static char region_table[3][3] =$ { {2, 1, 8}, {3, 0, 7}, {4, 5, 6}};K/* Entries in the the segment_intersection table indicate whether a segmentI * going from region i to region j intersects region 0. If equal 0, thenJ * the intersection may occur. If equal 1, then there is no intersection.; * And if equal 2, then there is certainly an intersection. * * -2 Can not intersect * -1 Must intersectH *>=0 May intersect. The value indicates which edge or edges to compare * * 0 Compare against edge 0 * 1 Compare against edge 1 * 2 Compare against edge 2 * 3 Compare against edge 3. * 4 Compare against the pair of edges 0 and 1. * 5 Compare against the pair of edges 1 and 2 */*static char segment_intersection[9][9] = {&/* 0 1 2 3 4 5 6 7 8 */#/*0*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1},#/*1*/ {-1,-2,-2, 3, 3,-1, 3, 3,-2},#/*2*/ {-1,-2,-2,-2,-2, 1, 5, 2,-2},#/*3*/ {-1, 0,-2,-2,-2, 0, 0,-1, 0},#/*4*/ {-1, 3,-2,-2,-2,-2,-2, 2, 4},#/*5*/ {-1,-1, 1, 1,-2,-2,-2, 1, 1},#/*6*/ {-1, 3, 5, 0,-2,-2,-2,-2,-2},#/*7*/ {-1, 2, 2,-1, 2, 2,-2,-2,-2},$/*8*/ {-1,-2,-2, 0, 4, 1,-2,-2,-2}}; void-RotateRectangle(Rectangle r, int delta_angle) { T_FLOAT P0_x, P0_y, P1_x, P1_y;2 T_FLOAT sine_angle, cosine_angle, slope1, slope2; int i, angle; r->angle += delta_angle; if (r->angle < 0) r->angle += 360; else if (r->angle >= 360) r->angle -= 360; angle = r->angle;= /* Based on the angle, determine which quadrant contains theA * leading edge of the object, the slopes the lines representing? * its edges, which vertices will contain the x and y extrema,) * and the sine and cosine of the angle. */ cosine_angle = COSINE(angle); sine_angle = SINE(angle); slope1 = SLOPE(angle);" r->forward_quadrant = angle / 90;4 r->aligned = ((r->forward_quadrant * 90) == angle); switch(r->forward_quadrant) { case 0: slope2 = SLOPE(angle + 90); break; case 1: slope2 = SLOPE(angle + 90); break; case 2: slope2 = SLOPE(angle + 90); break; case 3: slope2 = SLOPE(angle - 270); break; }2 /* Compute P0, the midpoint of the edge V0,V1. */% P0_x = r->height * sine_angle / 2.0;' P0_y = r->height * cosine_angle / 2.0;- 2 /* Compute P1, the midpoint of the edge V3,V0. */& P1_x = r->width * cosine_angle / 2.0;& P1_y = - r->width * sine_angle / 2.0; /* V0 = P0 + P1 */ r->vertices[0].x = P0_x + P1_x; r->vertices[0].y = P0_y + P1_y; /* V1 = P0 - P1 */ r->vertices[1].x = P0_x - P1_x; r->vertices[1].y = P0_y - P1_y; /* V2 = - P0 - P1 = - V0 */' r->vertices[2].x = - r->vertices[0].x;' r->vertices[2].y = - r->vertices[0].y; /* V3 = - P0 + P1 = - V1 */' r->vertices[3].x = - r->vertices[1].x;' r->vertices[3].y = - r->vertices[1].y;F /* The vertices have been determined based on a center at the origin.6 * Now account for the fact that it may not be there. */3 r->vertices[0].x = r->vertices[0].x + r->center.x;3 r->vertices[0].y = r->vertices[0].y + r->center.y;3 r->vertices[1].x = r->vertices[1].x + r->center.x;3 r->vertices[1].y = r->vertices[1].y + r->center.y;3 r->vertices[2].x = r->vertices[2].x + r->center.x;3 r->vertices[2].y = r->vertices[2].y + r->center.y;3 r->vertices[3].x = r->vertices[3].x + r->center.x;3 r->vertices[3].y = r->vertices[3].y + r->center.y;8 /* For computational efficiency, duplicate V0 as V4. */% r->vertices[4].x = r->vertices[0].x;% r->vertices[4].y = r->vertices[0].y;$ /* Now compute the bounding box. */ ResetRectangleBox(r);A /* Compute the lines representing the edges of the rectangle. */ r->edges[0].slope = slope2; r->edges[1].slope = slope1; r->edges[2].slope = slope2; r->edges[3].slope = slope1; ResetRectangleEdges(r); } /* Line 1 Line 2 * / / * / / * / / * / / *Column 2/Column 1/Column 0 * / / * / / * / / * / / * * * Line 2 Line 1 * \ \ * \ \& * Column 0 \Column 1\ Column 2 * \ \ * \ \ * \ \ * \ \ */staticint&WhichColumn(Line l1, Line l2, Point p) {3 T_COORDINATE ax_minus_y = l1->slope * p->x - p->y; T_COORDINATE tmp;$ tmp = ax_minus_y + l1->y_intercept; if (tmp < 0) return 2; else if (tmp == 0) return 1;$ tmp = ax_minus_y + l2->y_intercept; if (tmp > 0) return 0; return 1; } int!WhichRegion(Rectangle a, Point p) { int column, row, v; if (a->aligned != 0) { int x, y;# column = (p->x < a->bbox.minx) + (p->x <= a->bbox.maxx); row = (p->y < a->bbox.miny) + (p->y <= a->bbox.maxy);# return region_table[column][row]; } switch(a->forward_quadrant) { case 0: /* Facing Northeast */( column = WhichColumn(&a->edges[1], &a->edges[3], p);( row = 2 - WhichColumn(&a->edges[0], &a->edges[2], p);# return region_table[column][row]; break; case 1: /* Facing Southeast */$ column = WhichColumn(&a->edges[1], &a->edges[3], p);$ row = WhichColumn(&a->edges[2], &a->edges[0], p);# return region_table[column][row]; break; case 2: /* Facing Southwest */( column = 2 - WhichColumn(&a->edges[3], &a->edges[1], p);( row = WhichColumn(&a->edges[2], &a->edges[0], p);# return region_table[column][row]; break; case 3: /* Facing Northwest */( column = 2 - WhichColumn(&a->edges[3], &a->edges[1], p);( row = 2 - WhichColumn(&a->edges[0], &a->edges[2], p);# return region_table[column][row]; break; } /* end of switch */ return 0; } GComputeRegions(Rectangle a, Point vertices[], int count, int regions[]) { int column, row, v;A /* Classify each of the vertices in terms of the region around a= * which it occupies. If it is in A, then our work is done. */ switch(a->forward_quadrant) { case 0: /* Facing Northeast */ for(v = 0; v < count; v++) {) column = WhichColumn(&a->edges[1], &a->edges[3], &vertices[v]);) row = 2 - WhichColumn(&a->edges[0], &a->edges[2], &vertices[v]);* regions[v] = region_table[column][row]; if (regions[v] == 0) return 1; } break; case 1: /* Facing Southeast */ for(v = 0; v < count; v++) {% column = WhichColumn(&a->edges[1], &a->edges[3], &vertices[v]);% row = WhichColumn(&a->edges[2], &a->edges[0], &vertices[v]);* regions[v] = region_table[column][row]; if (regions[v] == 0) return 1; } break; case 2: /* Facing Southwest */ for(v = 0; v < count; v++) {) column = 2 - WhichColumn(&a->edges[3], &a->edges[1], &vertices[v]);) row = WhichColumn(&a->edges[2], &a->edges[0], &vertices[v]);* regions[v] = region_table[column][row]; if (regions[v] == 0) return 1; } break; case 3: /* Facing Northwest */ for(v = 0; v < count; v++) {) column = 2 - WhichColumn(&a->edges[3], &a->edges[1], &vertices[v]);) row = 2 - WhichColumn(&a->edges[0], &a->edges[2], &vertices[v]);* regions[v] = region_table[column][row]; if (regions[v] == 0) return 1; } break; } /* end of switch */ return 0; } /* URectIntersect(a, b) *E * Detect whether two rectangles, which are known to be unaligned andA * whose bounding boxes are known to overlap, themselves overlap.@ * The area of a must be greater than or equal to the area of b. */(URectIntersect(Rectangle a, Rectangle b) {# int column, row, regions[5], e, v;= /* Classify each of the vertices of b in terms of the region= * around a which it occupies. Of course, if it occupies A, * then our work is done. */8 if (ComputeRegions(a, &(b->vertices), 4, regions) == 1) return 1; regions[4] = regions[0];> /* We now know where each vertex of b lies with respect to a.; * Determine if any of the edges connecting these vertices * intesect a. *D * There may at first appear to be a special case when a and b are@ * aligned relative to one another (their edges are parallel to? * those of the other rectangle). Since parallel lines either? * intersect nowhere or everywhere, IntersectLines() would getB * mighty confused (i.e. it would do a divide by zero). BUT, twoA * such rectangles can only intersect at right angles. Thus theC * segment_intersection table will never indicate that an edge MAY. * intersect. Either it does, or it doesn't. */ for (e = 0; e < 4; e++) {) /* Does the edge e of b intersect a? */: int si = segment_intersection[regions[e]][regions[e+1]]; PointRec intercept; switch(si) {- case -2:/* The edge can not intersect a. */ break;' case -1:/* The edge must intersect a. * Thus b and a intersect. */ return 1; case 0: case 1: case 2: case 3:. /* The edge may intersect the edge si of a.4 * Determine whether the point at which the lines" * intersect is within edge si. */# IntersectLines( &(a->edges[si]), &(b->edges[e]), &intercept); if (BETWEEN(intercept.x, a->vertices[si].x, a->vertices[si+1].x))* /* The intercept point is within the x' * range of edge si, and thus b and * a intersect. */ return 1;1 /* The edge e of b didn't intersect with a. */ break; case 4:& /* Edge e of b may intersect either * edge 1 or 2 of a. */" IntersectLines( &(a->edges[0]), &(b->edges[e]), &intercept); if (BETWEEN(intercept.x, a->vertices[0].x, a->vertices[1].x)) return 1;" IntersectLines( &(a->edges[1]), &(b->edges[e]), &intercept); if (BETWEEN(intercept.x, a->vertices[1].x, a->vertices[2].x)) return 1;1 /* The edge e of b didn't intersect with a. */ break; case 5:& /* Edge e of b may intersect either * edge 1 or 2 of a. */" IntersectLines( &(a->edges[1]), &(b->edges[e]), &intercept); if (BETWEEN(intercept.x, a->vertices[1].x, a->vertices[2].x)) return 1;" IntersectLines( &(a->edges[2]), &(b->edges[e]), &intercept); if (BETWEEN(intercept.x, a->vertices[2].x, a->vertices[3].x)) return 1;1 /* The edge e of b didn't intersect with a. */ break; } /* End of switch */ } /* End of for */B /* No edges of b are in a, and since a is at least as large as b,3 * b can not contain a, so they do not overlap. */ return 0; } /* VerticalIntercept *? * Determine the Y value for the interception between a segment9 * which crosses a vertical line, and that vertical line. * * (y1 - y0) * (x - x0) * = -------------------- + y0 * x1 - x0 */static T_COORDINATE5VerticalIntercept(Point p0, Point p1, T_COORDINATE x) { T_COORDINATE tmp; tmp = p1->x - p0->x;- tmp = ((p1->y - p0->y) * (x - p0->x)) / tmp; tmp = tmp + p0->y; return tmp; }/* HorizontalIntercept *? * Determine the X value for the interception between a segment= * which crosses a horizontal line, and that horizontal line. * * (y1 - y0) * (x - x0) * = -------------------- + y0 * x1 - x0 */static T_COORDINATE7HorizontalIntercept(Point p0, Point p1, T_COORDINATE y) { T_COORDINATE tmp; tmp = p1->y - p0->y;- tmp = ((y - p0->y) * (p1->x - p0->x)) / tmp; tmp = tmp + p0->x; return tmp; } /* RectanglesIntersect *E * Determine whether or not two rectangles intersect. We assume that@ * their bounding boxes have already been compared, and found toB * intersect. We now do the more complex calculations required toC * determine whether the unaligned rectangles themselves intersect. * */int-RectanglesIntersect(Rectangle a, Rectangle b) { int regions[5], i, e;= /* Choose which rectangle to consider the primary rectangle.: * If one is already aligned, then choose it. Otherwise, * choose the larger. */ if (a->aligned) { if (b->aligned) {5 /* Since their bounding boxes intersect, and their5 * bounding boxes are equivalent to the rectangles2 * they contain, the rectangles themselves must * intersect. */ return 1; } } else if (b->aligned) { Rectangle tmp; tmp = b; b = a; a = tmp; } else {; /* Neither rectangle is aligned. Choose the larger as the * primary rectangle. */ if ((a->height * a->width) < (b->height * b->width)) { Rectangle tmp; tmp = b; b = a; a = tmp; }> /* Delegate the rest of the work on unaligned rectangles. */ return URectIntersect(a, b); }A /* At this point, a is known to be aligned, and b is known to beD * unaligned. Determine which region around a each of b's vertices * occupy. */ for (i = 0; i < 4; i++) { int x, y;* x = (b->vertices[i].x < a->bbox.minx) +) (b->vertices[i].x <= a->bbox.maxx);* y = (b->vertices[i].y < a->bbox.miny) +) (b->vertices[i].y <= a->bbox.maxy);" regions[i] = region_table[x][y]; if (regions[i] == 0)9 /* Vertex i of b is within a, so b and a intersect. */ return 1; } regions[4] = regions[0];> /* We now know where each vertex of b lies with respect to a.G * Determine if any of the edges connecting these vertices intesect a. */ for (e = 0; e < 4; e++) {% /* Does edge e of b intersect a? */: int si = segment_intersection[regions[e]][regions[e+1]]; T_COORDINATE intercept; switch(si) {- case -2:/* The edge can not intersect a. */ break;' case -1:/* The edge must intersect a. * Thus b and a intersect. */ return 1; case 0:/ /* Edge e of b may intersect edge 0 of a. */7 intercept = (a->bbox.maxy - b->edges[e].y_intercept) / b->edges[e].slope; if (BETWEEN(intercept, a->bbox.minx, a->bbox.maxx)) return 1;1 /* The edge e of b didn't intersect with a. */ break; case 1:/ /* Edge e of b may intersect edge 1 of a. */2 intercept = (a->bbox.minx * b->edges[e].slope)  + b->edges[e].y_intercept; if (BETWEEN(intercept, a->bbox.miny, a->bbox.maxy)) return 1;1 /* The edge e of b didn't intersect with a. */ break; case 2:/ /* Edge e of b may intersect edge 2 of a. */7 intercept = (a->bbox.miny - b->edges[e].y_intercept) / b->edges[e].slope; if (BETWEEN(intercept, a->bbox.minx, a->bbox.maxx)) return 1;1 /* The edge e of b didn't intersect with a. */ break; case 3:/ /* Edge e of b may intersect edge 3 of a. */2 intercept = (a->bbox.maxy * b->edges[e].slope)  + b->edges[e].y_intercept; if (BETWEEN(intercept, a->bbox.miny, a->bbox.maxy)) return 1;1 /* The edge e of b didn't intersect with a. */ break; case 4:' /* Edge e of by may intersect either# * edge 0 or 1 of a, or neither. */7 intercept = (a->bbox.maxy - b->edges[e].y_intercept)* /o b->edges[e].slope; if (BETWEEN(intercept, a->bbox.minx, a->bbox.maxx)) return 1; ) /* Now compare against edge 1 of a. */ 2 intercept = (a->bbox.minx * b->edges[e].slope)  + b->edges[e].y_intercept; if (BETWEEN(intercept,  a->bbox.miny, a->bbox.maxy)) return 1;1 /* The edge e of b didn't intersect with a. */R break; case 5:t8 /* The edge may intersect either edge 1 or 2 of a. */2 intercept = (a->bbox.minx * b->edges[e].slope)  + b->edges[e].y_intercept; if (BETWEEN(intercept,  a->bbox.miny, a->bbox.maxy))i return 1; 7 intercept = (a->bbox.miny - b->edges[e].y_intercept). /l b->edges[e].slope;r if (BETWEEN(intercept,t a->bbox.minx, a->bbox.maxx)) return 1;o1 /* The edge e of b didn't intersect with a. */c break;  } /* End of switch */d } /* End of for */E /* No edges of b are in a. Perhaps a is entirely contained in b? */a4 return ComputeRegions(b, &(a->center), 1, regions); } t%/* RectangleTraversed(a,distance,b,c)e *: * a is a rectangle which we would like to move forward or< * backward by distance units. b is filled in with the area= * which will be traversed by this move. It extends from the,; * leading edge's current position, to its new position. c-< * is filled in with the final position of a after the move. * * distance must be non-zero.1" * a must be completely filled in. */}PRectangleTraversed(Rectangle a, T_COORDINATE distance, Rectangle b, Rectangle c) {& CopyAndMoveRectangle(a, distance, c); b->height = a->height;_ b->width = a->width; b->area = a->area;n b->forward_quadrant = a->forward_quadrant; b->angle = a->angle;  if (distance > 0) {+" b->vertices[0] = c->vertices[0];" b->vertices[1] = c->vertices[1];" b->vertices[2] = a->vertices[1];" b->vertices[3] = a->vertices[0]; }d elsee {h" b->vertices[0] = c->vertices[3];" b->vertices[1] = c->vertices[2];" b->vertices[2] = a->vertices[2];" b->vertices[3] = a->vertices[3]; }e! b->vertices[4] = b->vertices[0];g ResetRectangleBox(b);' b->edges[0].slope = a->edges[0].slope;r' b->edges[1].slope = a->edges[1].slope;g' b->edges[2].slope = a->edges[2].slope;e' b->edges[3].slope = a->edges[3].slope;s ResetRectangleEdges(b); }*[RECT]VIEWPORT.C;1+,|./ 4N -%e 0123KPWO56 >R7`SW89G HJ/* viewport.c */#include "o.h"#include "x.h"3/* Determine the vertical and horizontal scales for; * converting from world coordinates to screen coordinates. */voidComputeScales(Screen *screen, int scale, float *hscale, float *vscale) { float hpixels_per_mm => ((float)XWidthOfScreen(screen)) / XWidthMMOfScreen(screen); float vpixels_per_mm =? ((float)XHeightOfScreen(screen)) / XHeightMMOfScreen(screen);; *hscale = (MM_PER_UNIT_DISTANCE * hpixels_per_mm) / scale;; *vscale = (MM_PER_UNIT_DISTANCE * vpixels_per_mm) / scale;#ifdef VERBOSEBprintf("ComputeScales() %d => %f, %f\n", scale, *hscale, *vscale);#endif }voidComputeBoxSize(BoundingBox b, float hscale, float vscale, int *width, int *height) {( *width = (b->maxx - b->minx) * hscale;( *height = (b->maxy - b->miny) * vscale; } Viewport ViewportCreate(Display *display, Screen *screen, Window window, int window_width, int window_height, int scale, T_COORDINATE centerx, T_COORDINATE centery) { T_COORDINATE width, height;7 Viewport v = (Viewport) malloc( sizeof(ViewportRec) ); v->display = display; v->screen = screen; v->window = window; v->window_width = window_width;" v->window_height = window_height; v->qt_id = 0; v->exposed_areas = 0; v->exposed_objects = 0; DefineColors(v); CreateGC(v);: /* Compute the size of the area which this window can see# * in the world coordinate system. */6 ComputeScales(screen, scale, &v->hscale, &v->vscale);$ width = window_width / v->hscale;$ height = window_height / v->vscale;$ v->bbox.minx = centerx - width / 2;) v->bbox.maxx = v->bbox.minx + width - 1;$ v->bbox.miny = centery - height/ 2;* v->bbox.maxy = v->bbox.miny + height - 1;A /* Due to the fact that the viewport's world area may not extendA * all the way to the right or bottom of the window, lets extend> * the world bbox by one in those directions so that the bbox' * goes beyond the edge of the window. */ v->bbox.maxx++; v->bbox.miny--;1 /* Now insert the viewport into the quadtree. */6 v->qt_id = QT_Insert(ViewportsQuadtree, v, &v->bbox); return v; } voidDestroyViewport(Viewport v) { if (v->qt_id != 0)) QT_Remove(ViewportsQuadtree, v->qt_id); if (v->gc != 0) XFreeGC(v->display, v->gc); if (v->exposed_objects != 0) {% ObjectList ol = v->exposed_objects; while(ol) { ObjectList next = ol->next; DeallocateObjectList(ol); ol = next; } } if (v->exposed_areas) free(v->exposed_areas); return; } voidTranslateViewport(Viewport v, T_COORDINATE deltax, T_COORDINATE deltay) { T_COORDINATE width, height;#ifdef VERBOSE=printf("TranslateViewport(%x, %d, %d)\n", v, deltax, deltay);#endif$ if ((deltax == 0) && (deltay == 0)) return;@ /* Start by removing the viewport from the set of viewports. */( QT_Remove(ViewportsQuadtree, v->qt_id);> /* FOR THE MOMENT, JUST MOVE THE VIEWPORT, AND INVALIDATE THE * WHOLE AREA. */ v->bbox.minx += deltax; v->bbox.maxx += deltax; v->bbox.miny += deltay; v->bbox.maxy += deltay;5 /* Insert the viewport into the set of viewports. */6 v->qt_id = QT_Insert(ViewportsQuadtree, v, &v->bbox); /* Redraw the whole area. */ ExposedViewport(v); return; } void!ViewportWindowResized(Viewport v, int window_width, int window_height) {. T_COORDINATE centerx, centery, width, height;#ifdef VERBOSENprintf("ViewportWindowResized(%x, %d, %d)\n", v, window_width, window_height);#endif+ if ((window_width == v->window_width) && ) (window_height == v->window_height)) return; v->window_width = window_width;" v->window_height = window_height;@ /* Start by removing the viewport from the set of viewports. */( QT_Remove(ViewportsQuadtree, v->qt_id); v->qt_id = 0;- /* FOR THE MOMENT, JUST RESIZE THE VIEWPORT," * AND INVALIDATE THE WHOLE AREA. */A /* Compute the old center of the window, which we shall maintain$ * as the center of the new window. */- centerx = (v->bbox.minx + v->bbox.maxx) / 2;- centery = (v->bbox.miny + v->bbox.maxy) / 2;A /* Now compute the size of world area visible to this window. */$ width = window_width / v->hscale;$ height = window_height / v->vscale;( /* And compute the new bounding box. */$ v->bbox.minx = centerx - width / 2;) v->bbox.maxx = v->bbox.minx + width - 1;$ v->bbox.miny = centery - height/ 2;* v->bbox.maxy = v->bbox.miny + height - 1;A /* Due to the fact that the viewport's world area may not extendA * all the way to the right or bottom of the window, lets extend> * the world bbox by one in those directions so that the bbox' * goes beyond the edge of the window. */ v->bbox.maxx++; v->bbox.miny--;5 /* Insert the viewport into the set of viewports. */6 v->qt_id = QT_Insert(ViewportsQuadtree, v, &v->bbox); /* Redraw the whole area. */ ExposedViewport(v); return; } void'SetViewportScale(Viewport v, int scale) {. T_COORDINATE centerx, centery, width, height;#ifdef VERBOSE/printf("SetViewportScale(%x, %d)\n", v, scale);#endif@ /* Start by removing the viewport from the set of viewports. */( QT_Remove(ViewportsQuadtree, v->qt_id); v->qt_id = 0;A /* Compute the old center of the window, which we shall maintain$ * as the center of the new window. */- centerx = (v->bbox.minx + v->bbox.maxx) / 2;- centery = (v->bbox.miny + v->bbox.maxy) / 2;: /* Compute the size of the area which this window can see# * in the world coordinate system. */9 ComputeScales(v->screen, scale, &v->hscale, &v->vscale);' width = v->window_width / v->hscale;' height = v->window_height / v->vscale;$ v->bbox.minx = centerx - width / 2;) v->bbox.maxx = v->bbox.minx + width - 1;$ v->bbox.miny = centery - height/ 2;* v->bbox.maxy = v->bbox.miny + height - 1;A /* Due to the fact that the viewport's world area may not extendA * all the way to the right or bottom of the window, lets extend> * the world bbox by one in those directions so that the bbox' * goes beyond the edge of the window. */ v->bbox.maxx++; v->bbox.miny--;5 /* Insert the viewport into the set of viewports. */6 v->qt_id = QT_Insert(ViewportsQuadtree, v, &v->bbox); /* Redraw the whole area. */ ExposedViewport(v); return; }*[RECT]XTVIEW.C;15+,Eu./ 4Rv-%e 0123KPWO56]q9W7 gW89G HJ  /* XtView.c" * Author: James Millington Synge * Creation Date: April 11, 1990 */#include ##include #include "xt.h"%extern BoundingBoxRec the_world_area;"static void xt_viewport_created();static void ExposeCallback();#static void WindowResizedHandler();'static void HbarValueChangedCallback();'static void VbarValueChangedCallback();static void CommandCallback();static void NewViewCallback();static void QuitCallback();.static Xt_Viewport viewport_being_created = 0;6static int xt_viewports = 0; /* Number of viewports */'static DRMHierarchy saved_drmHierarchy;*#define MIN(a,b) (((a) < (b)) ? (a) : (b))*#define MAX(a,b) (((a) > (b)) ? (a) : (b)) 1static DRMResourceContextPtr resourceContext = 0;char *7GetLiteralString(DRMHierarchy drmHierarchy, char *name) { char *valueP; if (!resourceContext)> if (!DwtDrmGetResourceContext (0, 0, 256, &resourceContext)) return (0);E if (!DwtDrmHGetIndexedLiteral (drmHierarchy, name, resourceContext)) return (0);8 valueP = XtMalloc (DwtDrmRCSize (resourceContext) + 1);3 strcpy (valueP, DwtDrmRCBuffer (resourceContext)); return (valueP); }int4GetLiteralInt(DRMHierarchy drmHierarchy, char *name) { if (!resourceContext)> if (!DwtDrmGetResourceContext (0, 0, 256, &resourceContext)) return (0);E if (!DwtDrmHGetIndexedLiteral (drmHierarchy, name, resourceContext)) return (0);2 return ((int) *DwtDrmRCBuffer (resourceContext)); } #static DRMRegisterArg reglist[] = {8 {"ViewportCreated", (caddr_t) xt_viewport_created},};staticint initialized = 0;staticint window_index, hbar_index, vbar_index, command_index, quit_index, newview_index;staticvoid%Initialize(DRMHierarchy drmHierarchy) { if (initialized != 0) return; initialized = 1;# saved_drmHierarchy = drmHierarchy;# /* Register the create callback */1 DwtRegisterDRMNames(reglist, XtNumber(reglist));I /* Get the widget indexes which will be used in the create callbacks. */H window_index = GetLiteralInt(drmHierarchy, "Xt_Viewport_window_index");D hbar_index = GetLiteralInt(drmHierarchy, "Xt_Viewport_hbar_index");D vbar_index = GetLiteralInt(drmHierarchy, "Xt_Viewport_vbar_index");J command_index = GetLiteralInt(drmHierarchy, "Xt_Viewport_command_index");J newview_index = GetLiteralInt(drmHierarchy, "Xt_Viewport_newview_index");D quit_index = GetLiteralInt(drmHierarchy, "Xt_Vi[n"~RECT.BCKEu%e [RECT]XTVIEW.C;15R{ewport_quit_index"); return; } Xt_Viewport CloneXtViewport(Xt_Viewport src, DRMHierarchy drmHierarchy) { return CreateXtViewport( drmHierarchy,. (src->v->bbox.minx + src->v->bbox.maxx) / 2,. (src->v->bbox.miny + src->v->bbox.maxy) / 2, src->v->window_width, src->v->window_height, src->scale); } Xt_Viewport+CreateXtViewport(DRMHierarchy drmHierarchy, T_COORDINATE centerx, T_COORDINATE centery, int width_pixels, int height_pixels, int scale) { DRMType class_return;( Widget main_window, window, vbar, hbar; DwtCallback cb1, cb2, cb3; Xt_Viewport xt_viewport; Initialize(drmHierarchy);* /* Allocate the Xt_Viewport structure. */; xt_viewport = (Xt_Viewport)malloc(sizeof(Xt_ViewportRec));& viewport_being_created = xt_viewport; xt_viewport->scale = scale; xt_viewport->centerx = centerx; xt_viewport->centery = centery; xt_viewport->v = 0; /* Create the shell widget. */ xt_viewport->shell =C XtCreateApplicationShell("Rect", topLevelShellWidgetClass, 0, 0);5 /* Fetch the widgets which make up the interface. */ xt_viewport->main = 0; xt_viewport->window = 0; xt_viewport->hbar = 0; xt_viewport->vbar = 0; xt_viewport->command = 0; DwtFetchWidget( drmHierarchy, "Xt_Viewport", xt_viewport->shell, &main_window, &class_return );! xt_viewport->main = main_window; xt_viewports += 1;> /* Set the size and expose callback for the window widget. */ { Arg args[] = {' {XtNwidth, MAX(width_pixels, 50)},' {XtNheight, MAX(height_pixels, 50)}, };8 XtSetValues(xt_viewport->window, args, XtNumber(args)); } XtAddCallback( xt_viewport->window, DwtNexposeCallback, ExposeCallback, (int)xt_viewport);2 /* Set the horizontal scroll bar's attributes. */: /* NOTE THAT THE SCROLL BAR ASSUMES THAT THE REAL MAXIMUM: * VALUE IS IS ONE LESS THAN THE SPECIFIED MAXIMUM VALUE. */ { Arg args[] = {$ {DwtNvalue, the_world_area.minx},' {DwtNminValue, the_world_area.minx},+ {DwtNmaxValue, the_world_area.maxx + 1},> {DwtNshown, the_world_area.maxx - the_world_area.minx + 1}, };6 XtSetValues(xt_viewport->hbar, args, XtNumber(args)); }0 /* Set the vertical scroll bar's attributes. */ { Arg args[] = {$ {DwtNvalue, the_world_area.miny},' {DwtNminValue, the_world_area.miny},+ {DwtNmaxValue, the_world_area.maxy + 1},> {DwtNshown, the_world_area.maxy - the_world_area.miny + 1}, };6 XtSetValues(xt_viewport->vbar, args, XtNumber(args)); }? /* Set the command entered callback for the command widget. */$ XtAddCallback(xt_viewport->command,A DwtNcommandEnteredCallback, CommandCallback, (int)xt_viewport);6 /* Display the windows when the shell is realized. */ XtManageChild( main_window );#ifdef VERBOSE%printf("Managed the main_window.\n");#endif' XtRealizeWidget( xt_viewport->shell ); return xt_viewport;} staticvoidLxt_viewport_created(Widget w, int *widget_index, DwtAnyCallbackStruct *data) {# if (*widget_index == window_index)% viewport_being_created->window = w;& else if (*widget_index == hbar_index)# viewport_being_created->hbar = w;& else if (*widget_index == vbar_index)# viewport_being_created->vbar = w;) else if (*widget_index == command_index)& viewport_being_created->command = w;) else if (*widget_index == newview_index) {/ /* Set the quit callback for the menu bar. */ XtAddCallback( w, DwtNactivateCallback, NewViewCallback, (int)viewport_being_created); }& else if (*widget_index == quit_index) {/ /* Set the quit callback for the menu bar. */ XtAddCallback( w, DwtNactivateCallback, QuitCallback, (int)viewport_being_created); } return; } staticvoid+AdjustXtViewportScrollBars(Xt_Viewport xtv) { BoundingBox b = &xtv->v->bbox;- T_COORDINATE hrange = b->maxx - b->minx + 1,& vrange = b->maxy - b->miny + 1;@ /* Set the attributes of the scroll bars to reflect the current( * area being 'viewed' by the viewport. */ { Arg args[] = { {DwtNvalue, (int)b->minx}, {DwtNshown, (int)hrange},& {DwtNpageInc, (int)(hrange * .95)}," {DwtNinc, (int)(hrange * .05)}, };. XtSetValues(xtv->hbar, args, XtNumber(args)); } {7 T_COORDINATE distance = the_world_area.maxy - b->maxy; Arg args[] = {6 {DwtNvalue, (int)(the_world_area.miny + distance)}, {DwtNshown, (int)vrange},& {DwtNpageInc, (int)(vrange * .95)}," {DwtNinc, (int)(vrange * .05)}, };. XtSetValues(xtv->vbar, args, XtNumber(args)); } return; }staticvoidEExposeCallback(Widget w, Xt_Viewport xtv, DwtAnyCallbackStruct *data){ PrintEvent(data->event); if (xtv->v == 0) { int hscale, vscale; T_COORDINATE width, height;8 /* The window has never been displayed before. Create6 * a viewport for it, centered and scaled as we were * instructed. */ xtv->v = ViewportCreate( XtDisplay(w), XtScreen(w), XtWindow(w), w->core.width, w->core.height, xtv->scale, xtv->centerx, xtv->centery); XtAddEventHandler( xtv->window, StructureNotifyMask, 0, WindowResizedHandler, (int)xtv);" AdjustXtViewportScrollBars(xtv); XtAddCallback( xtv->hbar, DwtNvalueChangedCallback, HbarValueChangedCallback, (int)xtv); XtAddCallback( xtv->vbar, DwtNvalueChangedCallback, VbarValueChangedCallback, (int)xtv); ExposedViewport(xtv->v); } else* ExposedViewingArea(xtv->v, data->event); return;}staticvoidWindowResizedHandler(Widget w, Xt_Viewport xtv, XConfigureEvent *e) {#ifdef VERBOSEPrintEvent(e);#endif: if ((e->type != ConfigureNotify) || (e->send_event == 1)) return;5 /* Tell the viewport that its window was resized. */4 ViewportWindowResized(xtv->v, e->width, e->height); /* Adjust the scroll bars. */! AdjustXtViewportScrollBars(xtv); return; } staticvoid"HbarValueChangedCallback(Widget w, Xt_Viewport xtv,% DwtScrollBarCallbackStruct *data) {! T_COORDINATE minx = data->value; /* Re-position the viewport. */8 TranslateViewport(xtv->v, minx - xtv->v->bbox.minx, 0);,  return; }staticvoid"VbarValueChangedCallback(Widget w, Xt_Viewport xtv,% DwtScrollBarCallbackStruct *data) {6 T_COORDINATE maxy, value = (T_COORDINATE)data->value;E /* Adjust for the fact that the scroll bar widget thinks the minimum8 * value is represented by the slider being at the top. */B maxy = the_world_area.maxy - (data->value - the_world_area.miny); # /* Now reposition the viewport. */8 TranslateViewport(xtv->v, 0, maxy - xtv->v->bbox.maxy); return; }staticvoidPCommandCallback(Widget w, Xt_Viewport xtv, DwtCommandWindowCallbackStruct *data){3 printf("Command callback: \"%s\"\n", data->value);( ProcessObjectCommand(xtv, data->value);}Rstatic void NewViewCallback(Widget w, Xt_Viewport xtv, DwtAnyCallbackStruct *data){ /* Clone this view port. */* CloneXtViewport(xtv, saved_drmHierarchy);}Ostatic void QuitCallback(Widget w, Xt_Viewport xtv, DwtAnyCallbackStruct *data){ xt_viewports -= 1; if (xt_viewports <= 0) {" XtCloseDisplay(xtv->v->display); exit(1); } else { /* Unrealize the widgets. */ XtUnrealizeWidget(xtv->shell); /* Deallocate the viewport. */ DestroyViewport(xtv->v); } return;} void.SetXtViewportScale(Xt_Viewport xtv, int scale) { if (xtv->scale == scale) return; xtv->scale = scale;9 /* Tell the viewport that the scale has been changed. */! SetViewportScale(xtv->v, scale); /* Adjust the scroll bars. */! AdjustXtViewportScrollBars(xtv); return; }\)F ~RECT.BCK}%e [RECT]BBOX.H;1EX*[RECT]BBOX.H;1+,}./ 4E-%e 0123KPWO56UUO7W89G HJ  /* bbox.h *E * Bounding box structure. Used both in quadtree.c and rectangles.c.B * This sharing allows arguments to be passed as addresses of thisA * common structure, rather than as seperate arguments which must * be pushed. */#ifndef _BBOX_H#define _BBOX_H#include "misc_math.h"#include "lines_and_points.h"typedefstruct _BoundingBoxRec { T_COORDINATE- minx, maxx, /* Left and Right x values. */- miny, maxy; /* Bottom and Top y values. */ } BoundingBoxRec, *BoundingBox;7/* Compute the box a containing two others, b and c. */0#define _BOX_H_MIN(i, j) ((i) < (j) ? (i) : (j))0#define _BOX_H_MAX(i, j) ((i) > (j) ? (i) : (j))staticintBoxesBox(a, b, c)BoundingBox a, b, c; {( a->minx = _BOX_H_MIN(b->minx, c->minx);( a->maxx = _BOX_H_MAX(b->maxx, c->maxx);( a->miny = _BOX_H_MIN(b->miny, c->miny);( a->maxy = _BOX_H_MAX(b->maxy, c->maxy); }*/* Is any point in A also a point in B? */staticint*BoxesOverlap(BoundingBox a, BoundingBox b) { if ((a->maxx >= b->minx) && (a->minx <= b->maxx) && (a->maxy >= b->miny) && (a->miny <= b->maxy)) return 1; return 0; },/* Is every point in a also a point in b? */staticint*BoxContained(BoundingBox a, BoundingBox b) { if ((a->maxx <= b->maxx) && (a->minx >= b->minx) && (a->maxy <= b->maxy) && (a->miny >= b->miny)) return 1; return 0; }staticint+Box_CompareX(BoundingBox r, T_COORDINATE x) { if (x <= r->minx) return -1; if (r->maxx <= x) return 1; return 0; }staticint+Box_CompareY(BoundingBox r, T_COORDINATE y) { if (y <= r->miny) return -1; if (r->maxy <= y) return 1; return 0; }</* Do the box and line touch? Assume that l->slope != 0. */staticint*BoxAndLineIntersect(BoundingBox b, Line l) { T_COORDINATE x,y; y = LineSolveForY(l, b->minx);" if (BETWEEN(y, b->miny, b->maxy)) return 1; y = LineSolveForY(l, b->maxx);" if (BETWEEN(y, b->miny, b->maxy)) return 1; x = LineSolveForX(l, b->miny); % return BETWEEN(x, b->minx, b->maxx); }#endif*[RECT]LINES_AND_POINTS.H;1+,}./ 4CV-%e 0123KPWO56@ޛF7W89G HJ/* lines_and_points.h */#ifndef _LINES_AND_POINTS_H#define _LINES_AND_POINTS_H#include "misc_math.h"typedefstruct _PointRec { T_COORDINATE x,y; } PointRec, *Point;typedefstruct _LineRec { T_FLOAT slope; T_COORDINATE y_intercept; } LineRec, *Line;/* IntersectLines *4 * Determine the point of intersection of two lines. * * Line 1: ax + b = y * Line 2: cx + d = y * * Solving for x: * * ax + b = cx + d * * ax - cx = d - b * * x (a - c) = d - b * * d - b * x = ----- * a - c * * Then solving for y: * * y = ax + b */staticvoid)IntersectLines(Line l1, Line l2, Point p) { T_COORDINATE x, y;C x = (l2->y_intercept - l1->y_intercept) / (l1->slope - l2->slope);% y = l1->slope * x + l1->y_intercept; p->x = x; p->y = y; return; }static T_COORDINATE%LineSolveForY(Line l, T_COORDINATE x) {& return l->slope * x + l->y_intercept; }static T_COORDINATE%LineSolveForX(Line l, T_COORDINATE y) {( return (y - l->y_intercept) / l->slope; }#endif*[RECT]MISC_MATH.H;1+,}./ 47-%e 0123KPWO56 rM7*IW89G HJ/* misc_math.h */#ifndef _MISC_MATH_H#define _MISC_MATH_H#define T_COORDINATE int#define T_FLOAT float#define INFINITE 999999.0#ifndef _DATA_C globalrefT_FLOAT sin_cos_table[360+90], slope_table[360];#endif*#define SINE(angle) (sin_cos_table[angle])/#define COSINE(angle) (sin_cos_table[angle+90]))#define SLOPE(angle) (slope_table[angle])7/* Is c between a and b, inclusive of the endpoints? */3#define BETWEEN(c, a, b) (0 >= ((c - a) * (c - b)))#endif *[RECT]O.H;1+,}. / 4E |-%e 0123KPWO 56vER7@$W89G HJ /* o.h */ #ifndef _O_H #define _O_H#include "quadtree.h"#include "rectangle.h"#define MM_PER_UNIT_DISTANCE 10A#define UNIT_DISTANCE_PER_METER (1000 / MM_PER_UNIT_DISTANCE)A#define UNIT_DISTANCE_PER_KM (1000 * 1000 / MM_PER_UNIT_DISTANCE)5#define KM_TO_UNITS(km) ((km) * UNIT_DISTANCE_PER_KM)<#define METERS_TO_UNITS(km) ((km) * UNIT_DISTANCE_PER_METER)typedefstruct _GameObject {! struct _GameObject *next, *prev; Rectangle rect; int height; QUADTREE_OBJECT object_qt_id; int id;E int rotational_velocity; /* Degrees per unit time. (0 <= x < 360) */< T_COORDINATE velocity; /* Distance units per unit time. */ int moving : 1; int reserved_flags : 31; int color_index; } GameObjectRec, *GameObject;typedefstruct _AreaObject { struct _AreaObject *next; BoundingBoxRec bbox; QUADTREE_OBJECT obj; } AreaObjectRec, *AreaObject;typedefstruct _ObjectList { struct _ObjectList *next; void *object; } ObjectListRec, *ObjectList; #ifdef _O_C%#define _GLOBAL(d,i) globaldef d = i;#else!#define _GLOBAL(d,i) globalref d;#endif%_GLOBAL(QUADTREE ObjectsQuadtree, 0);'_GLOBAL(QUADTREE ViewportsQuadtree, 0);$_GLOBAL(GameObject game_objects, 0);)_GLOBAL(GameObject free_game_objects, 0);$_GLOBAL(AreaObject area_objects, 0);)_GLOBAL(AreaObject free_area_objects, 0);-_GLOBAL(ObjectList free_object_list_recs, 0);#undef _GLOBALstatic GameObjectAllocateGameObject() {( GameObject new_obj = free_game_objects; if (new_obj != 0) {& free_game_objects = new_obj -> next; if (new_obj->next != 0) new_obj->next->prev = 0; } else {6 new_obj = (GameObject)malloc(sizeof(GameObjectRec)); }4 /* Add to global list of allocated game objects. */ new_obj->next = game_objects; game_objects = new_obj; new_obj->prev = 0;  if (new_obj->next != 0) new_obj->next->prev = new_obj; /* Initialize fields. */% new_obj->rect = AllocateRectangle(); new_obj->height = 0; new_obj->id = 0; new_obj->object_qt_id = 0;" new_obj->rotational_velocity = 0; new_obj->velocity = 0; new_obj->moving = 0; new_obj->color_index = 1; return new_obj; }staticvoid$DeallocateGameObject(GameObject obj) {* /* Remove any allocated sub-resources. */ if (obj->rect != 0)! DeallocateRectangle(obj->rect); if (obj->object_qt_id != 0)0 QT_Remove(ObjectsQuadtree, obj->object_qt_id);+ /* Remove from the active objects list. */ if (obj->next != 0) obj->next->prev = obj->prev; if (obj->prev != 0) obj->prev->next = obj->next; else game_objects = obj->next;3 /* Insert at the head of the free objects list. */ obj->next = free_game_objects; free_game_objects = obj; obj->prev = 0; if (obj->next != 0) obj->next->prev = obj; }static AreaObjectAllocateAreaObject() {( AreaObject new_obj = free_area_objects; if (new_obj != 0) {$ free_area_objects = new_obj->next; return new_obj; } else {3 return (AreaObject)malloc(sizeof(AreaObjectRec)); } }staticvoid)DeallocateAreaObject(AreaObject free_obj) {& free_obj -> next = free_area_objects; free_area_objects = free_obj; }static ObjectListAllocateObjectList() {, ObjectList new_obj = free_object_list_recs; if (new_obj != 0) {( free_object_list_recs = new_obj->next; return new_obj; } else {3 return (ObjectList)malloc(sizeof(ObjectListRec)); } }staticvoid)DeallocateObjectList(ObjectList free_obj) {( free_obj->next = free_object_list_recs;" free_object_list_recs = free_obj; }#endif*[RECT]QUADTREE.H;1+,}./ 4IB-%e 0123KPWO56j^8H7bW89G HJ#ifndef _QUADTREE_H#define _QUADTREE_H#include "misc_math.h"#include "bbox.h"#ifndef _QUADTREE_INT_Htypedef int QUADTREE_OBJECTID;typedef void *QUADTREE;typedef void *QUADTREE_OBJECT;#else#define QUADTREE Quadtree!#define QUADTREE_OBJECT QT_Object#endif3typedef int (*QT_OverlapProc)(BoundingBox, void *);7typedef void* (*QT_ObjectProc)(QUADTREE_OBJECTID, int);)QUADTREE QT_Create(T_COORDINATE min_area," T_COORDINATE lx, T_COORDINATE rx,# T_COORDINATE by, T_COORDINATE ty);6QUADTREE_OBJECT QT_Insert(QUADTREE, QUADTREE_OBJECTID, BoundingBox objectrange);)int QT_Remove(QUADTREE, QUADTREE_OBJECT);Iint QT_SimpleSearch(QUADTREE q, QUADTREE_OBJECTID objectids[], int count, BoundingBox range);Bvoid * QT_Search(QUADTREE, QT_ObjectProc, QT_OverlapProc, void *);#endif*[RECT]QUADTREE_INT.H;1+,}./ 4G-%e 0123KPWO56@TsF7@W89G HJ/* quadtree_int.h */4/* Quadtree data structures. Private to quadtree.c.. * QUADTREE_OBJECTID is defined in quadtree.h. */#ifndef _QUADTREE_INT_H#define _QUADTREE_INT_H#include "bbox.h"#include "lines_and_points.h"typedefGenum {NE_Quad, NW_Quad, SW_Quad, SE_Quad, Multiple_Quadrants} QUADRANT;typedef int QUADTREE_OBJECTID;typedefstruct _QT_ObjectRec { BoundingBoxRec rect; QUADTREE_OBJECTID id;# struct _QT_ObjectRec *next_object; struct _QuadtreeRec *container; } QT_ObjectRec, *QT_Object;typedefstruct _QuadtreeRec { BoundingBoxRec rect; PointRec center;# struct _QuadtreeRec *quadrants[4]; QT_Object objects; struct _QuadtreeRec *parent; int level; } QuadtreeRec, *Quadtree;#include "quadtree.h"#endif*[RECT]RECTANGLE.H;1+,}./ 4N b-%e 0123KPWO56`Hs^O7 W89G HJ/* Rectangles.h *@ * Data structures for representing unaligned rectangles. TheseA * are rectangles (4 sides, 90 degree angles between sides) which< * are not aligned with the axes of their coordinate system. * *Vertex 1 Edge 0B * +-------------------+ Vertex 0 (And repeated as vertex 4) * | ^ | * | | | * | | | * E| | |C * d|<--Width---------->| This is the angle == 0 arrangement.C * g| | | angle increases as the rectangle is3 * e| | |E rotated clockwise. * | H |d * 1| e |g * | i |e * | g | * | h |3 * | t | * | | | * | V |' * +-------------------+ Vertex 3 *Vertex 2 Edge 2 */#ifndef _RECTANGLE_H#define _RECTANGLE_H#include "misc_math.h"#include "bbox.h"#include "lines_and_points.h"typedefstruct _RectangleRec { BoundingBoxRec bbox; PointRec center;" T_COORDINATE height, width, area; PointRec vertices[5]; LineRec edges[4];* short angle; /* Angle is in degrees. */E char forward_quadrant; /* In which quadrant is the leading edge. */ char aligned; void *id; } RectangleRec, *Rectangle;extern float cos_sin_table[91];void(RotateRectangle(Rectangle r, int angle);int.RectanglesIntersect(Rectangle a, Rectangle b);N/****************************************************************************/N/****************************************************************************/N/** **/N/** Functions which will be commonly used, therefore they are included **/N/** here in the hope that fancy compilers can 'inline' them. **/N/** **/N/****************************************************************************/N/****************************************************************************/#ifdef _RECTANGLE_C%#define _GLOBAL(d,i) globaldef d = i;#else!#define _GLOBAL(d,i) globalref d;#endif&_GLOBAL(Rectangle free_rectangles, 0);#undef _GLOBALstruct _FreeRectangle { struct _FreeRectangle *next; };static RectangleAllocateRectangle() {& Rectangle new_rect = free_rectangles; if (new_rect != 0) { free_rectangles = (Rectangle)/ (((struct _FreeRectangle *)new_rect)->next); } else {5 new_rect = (Rectangle)malloc(sizeof(RectangleRec)); } return new_rect; }staticvoid5DeallocateRectangle(struct _FreeRectangle *free_rect) {< free_rect->next = (struct _FreeRectangle *)free_rectangles;( free_rectangles = (Rectangle)free_rect; }staticvoidInitRectangle(Rectangle r,% T_COORDINATE cx, T_COORDINATE cy,# T_COORDINATE h, T_COORDINATE w, int angle) { double sqrt(double); r->center.x = cx; r->center.y = cy; r->height = h; r->width = w; r->area = h * w; r->angle = 0; RotateRectangle(r, angle); }staticvoidResetRectangleBox(Rectangle a) { switch (a->forward_quadrant) { case 0:" a->bbox.minx = a->vertices[2].x;" a->bbox.maxx = a->vertices[0].x;" a->bbox.miny = a->vertices[3].y;" a->bbox.maxy = a->vertices[1].y; break; case 1:" a->bbox.minx = a->vertices[3].x;" a->bbox.maxx = a->vertices[1].x;" a->bbox.miny = a->vertices[0].y;" a->bbox.maxy = a->vertices[2].y; break; case 2:" a->bbox.minx = a->vertices[0].x;" a->bbox.maxx = a->vertices[2].x;" a->bbox.miny = a->vertices[1].y;" a->bbox.maxy = a->vertices[3].y; break; case 3:" a->bbox.minx = a->vertices[1].x;" a->bbox.maxx = a->vertices[3].x;" a->bbox.miny = a->vertices[2].y;" a->bbox.maxy = a->vertices[0].y; break; } /* End of switch */ }>/* ReCompute the y intercepts of those lines. I.E., solve the? * equation ax + b = y for b. The equation becomes b = y - ax. */staticvoid ResetRectangleEdges(Rectangle r) {* if ((r->angle == 0) || (r->angle == 180)) return; r->edges[0].y_intercept =< r->vertices[0].y - (r->edges[0].slope * r->vertices[0].x); r->edges[1].y_intercept =< r->vertices[1].y - (r->edges[1].slope * r->vertices[1].x); r->edges[2].y_intercept =< r->vertices[2].y - (r->edges[2].slope * r->vertices[2].x); r->edges[3].y_intercept =< r->vertices[3].y - (r->edges[3].slope * r->vertices[3].x); }staticvoidATranslateRectangle(Rectangle r, T_COORDINATE dx, T_COORDINATE dy) { int i; T_FLOAT slope_times_dx; r->bbox.minx += dx; r->bbox.maxx += dx; r->bbox.miny += dy; r->bbox.maxy += dy; r->center.x += dx; r->center.y += dy; for (i = 0; i < 4; i++) { r->vertices[i].x += dx; r->vertices[i].y += dy; }% r->vertices[4].x = r->vertices[0].x;% r->vertices[4].y = r->vertices[0].y; ResetRectangleEdges(r); }staticvoidECopyAndMoveRectangle(Rectangle a, T_COORDINATE distance, Rectangle b) { int i, angle, dx, dy; T_FLOAT slope_times_dx; b->height = a->height; b->width = a->width; b->area = a->area; b->forward_quadrant = a->forward_quadrant; b->angle = a->angle; angle = a->angle; dx = distance * SINE(angle); dy = distance * COSINE(angle);" b->bbox.minx = a->bbox.minx + dx;" b->bbox.maxx = a->bbox.maxx + dx;" b->bbox.miny = a->bbox.miny + dy;" b->bbox.maxy = a->bbox.maxy + dy; b->center.x = a->center.x + dx; b->center.y = a->center.y + dy; #define __COPYANDMOVEVERTEX(i) \+ b->vertices[i].x = a->vertices[i].x + dx;\* b->vertices[i].y = a->vertices[i].y + dy; __COPYANDMOVEVERTEX(0) __COPYANDMOVEVERTEX(1) __COPYANDMOVEVERTEX(2) __COPYANDMOVEVERTEX(3) __COPYANDMOVEVERTEX(4)#undef __COPYANDMOVEVERTEX' b->edges[0].slope = a->edges[0].slope;' b->edges[1].slope = a->edges[1].slope;' b->edges[2].slope = a->edges[2].slope;' b->edges[3].slope = a->edges[3].slope; ResetRectangleEdges(b); }#endif *[RECT]X.H;1+,}./ 4#B-%e 0123KPWO56)R7 QW89G HJ #ifndef _X_H #define _X_H#include #include "o.h"typedefstruct _RectangleList { int total; int in_use; XRectangle rectangles[1];# } RectangeListRec, *RectangleList;typedefstruct _GCModifier { unsigned long value_mask; XGCValues values; } GCModifierRec, *GCModifier;#define MAXCOLORS 8typedefstruct _Viewport { BoundingBoxRec bbox; float hscale, vscale; Display *display; Screen *screen; Window window; GC gc; int background_color; int foreground_color; int window_width; int window_height;! unsigned long colors[MAXCOLORS]; QUADTREE_OBJECT qt_id; RectangleList *exposed_areas; ObjectList *exposed_objects; int clipping : 1; int reserved : 31; } ViewportRec, *Viewport;typedefstruct _ExposedArea { struct _ExposedArea *next; BoundingBoxRec bbox; };typedefstruct _ExposedView { struct _ExposedView *next; int x, y; unsigned int width, height; Viewport *v; };#define _X_RECTANGLE_COUNT 10 #endif *[RECT]XT.H;1+,}./ 4J-%e 0123KPWO56HV7@޹W89G HJ #ifndef _XT_H #define _XT_H#include "x.h"typedefstruct _XT_Viewport { Viewport v;1 Widget shell, main, window, hbar, vbar, command; T_COORDINATE centerx, centery; int scale; } Xt_ViewportRec, *Xt_Viewport;extern Xt_Viewport+CloneXtViewport(Xt_Viewport, DRMHierarchy);extern Xt_ViewportJCreateXtViewport(DRMHierarchy, T_COORDINATE, T_COORDINATE, int, int, int);#endif' sV~RECT.BCK}%e [RECT]RECT.UIL;1C[*[RECT]RECT.UIL;1+,}./ 4C@-%e 0123KPWO56sQ7>W89G HJ 0module rect /* UIL file for the rect program */ names = case_sensitive(include file 'decw$include:dwtappl.uil';value' Xt_Viewport_window_index : exported 1;% Xt_Viewport_hbar_index : exported 2;% Xt_Viewport_vbar_index : exported 3;( Xt_Viewport_command_index : exported 4;( Xt_Viewport_newview_index : exported 5;% Xt_Viewport_quit_index : exported 6;#procedure ViewportCreated(integer);C/* Define the application main window. It contains the dialog box. */"object Xt_Viewport : main_window { arguments { x = 300; y = 300; width = 0; height = 0; }; controls { menu_bar rect_menu_bar; window rect_window; scroll_bar rect_hori; scroll_bar rect_vert; command_window rect_command; };};object rect_window : window { arguments { width = 600; height = 500; }; callbacks {A create = procedure ViewportCreated( Xt_Viewport_window_index ); };};object rect_vert : scroll_bar { arguments {' orientation = DwtOrientationVertical; }; callbacks {? create = procedure ViewportCreated( Xt_Viewport_vbar_index ); };};object rect_hori : scroll_bar { arguments {) orientation = DwtOrientationHorizontal; }; callbacks {? create = procedure ViewportCreated( Xt_Viewport_hbar_index ); };};&object rect_command : command_window { arguments { lines = 3; }; callbacks {B create = procedure ViewportCreated( Xt_Viewport_command_index ); };};!object rect_menu_bar : menu_bar { arguments {) orientation = DwtOrientationHorizontal; }; controls { pulldown_entry { arguments { label_label = 'Control'; }; controls {$ pulldown_menu rect_control_menu; }; };/* pulldown_entry {** arguments {** label_label = 'Edit';** };** controls {#** pulldown_menu rect_edit_menu;** };** };*/ };};*object rect_control_menu : pulldown_menu { controls { push_button { arguments { label_label = 'New View'; }; callbacks {& create = procedure ViewportCreated! (Xt_Viewport_newview_index); }; }; push_button { arguments { label_label = 'Quit'; }; callbacks {& create = procedure ViewportCreated (Xt_Viewport_quit_index); }; }; };};/*procedure PasteCallback;**)**object rect_edit_menu : pulldown_menu { ** controls {** push_button {** arguments {** label_label = 'Paste';** };** callbacks {)** activate = procedure PasteCallback;** };** };** };**};*/ end module;o j~RECT.BCKs c;5V<<irH.C;1;0ow++ 6~  ,bYv~w\xcku>.*.T\3yby.Xg'y{eE&j*j>\_= i8b!3^9PwnU_fJ8~Cm# g 6C&a.< dm10=I&a>U`)1;ak`%)xE5UXIz: UPd|#2h ^BJ*W~sY(de| E4zht&\>iN%AqRK nma'c?FOMͼojk9"BD)NL^"b_> PUG1@ "K@!@RV&DTFs,cEKSDu+.teU@.N3ea{xpzyB/mhOSiWe1KA]aE%L$-_t 'eS.EP#%k_#w|edz deuc+JoIlN@oza)uL ia0J{:+S-;>Zq}pl90J v<<"sK0EX'OxR B3&;Y1@s&}P,(Zv%<# zOu>8 ur1^IdM 2J^]tR#vuDsLJXx@e}b+\MNthu;B-u98\;a,S=oFQ<;Ae mcO=>0OJ{@':'. R948@Mrx~YARc{7v(SK)E&efd@@W D1zVw0wlVHL1OB"?d5m_ F$% %TZPW3L[ %&!P^sT9W j~oV~aKu h.=XFq}`XDT4I-9;/`1leyi0c&%y+OG2=v+fgbF5\xMt**d}iCmj8&1S1WUtJGr2/ > _tHPQ_;E aFLy "83m1`\O:F OV hQoE7: :=O|iDa]&> 1A0JOKAHaH@R +q8O0HeWM\O2wA3<T)I{Y)d [Q<7QA/`a?"3|lj[O(uzps?m>p}xpAobqVkE7j)gu6h@:; Ixo!@@>W _['2= DTr/>#J~ 1GX/E9E/_|$*8B<|zH2DCkac(}6! UlB"V^\Fu_A>mcyy""Op/MAg0gl"1F{%Ob9 x!"b w]VRj ;|%KE Dzy\."0?{+TMsZ&K_na/GM@]DP0mVC>;o}6MOPAnUJ;05`?C1[t:p/FXEg"Nnth\$rV<'xI!I.`nmu#\i]{Ti@&xa:gIdnR{dV o &\~k_mK Nf`o2ik=iRB9{7.9*nH}|Ogb fKx2# aye8$fYi'z&oX6$);bn.#||^ !< U )2p'8W6R  dvPh\Nia uH-&*o0Y=pR`f`~Soysrvk =fSTLiS\6v=JoOo1\4w#&k Z _5!xy9J P!S:hWMlr`gxv/UV }F[ ??dea@4A o9~ Jpw}@6T|9$}zN]ozkJ:;c@sH:FF55 =6M%HCK@\x6K76@Kx%|UkD6,! F$N5L-?  ihf@G;2~]/3oE8 J]au_ k7I'8`.3[&8w\os!yV;x>a [3QG[ _2 :&JDyG0=5$Tpn3?=7 V&VWeJlPx}=.wN|xtlS^oQ@ D!s{ S(YFY={E DPO\((c7N[K =}Z.^Ww"{RB#bo|61[3b QF?uP+Kl~U}+O;<>oh)bl$|J*S #ilKyUMkF5#*Bp^[Y.#av,[*I{V%f"Xh>M l\_Z;arT1Yfj#cEmj 5e03`"hr7h(=BdEO*%IKUA|)j<$![=.te2 XE$q6iM ujx`7l-xf <=*tPtfOj \|T*{*cju/w dh4 D1TB t6>%u0*x+/'/|qJ2xVc.TNKBm=zwQv`imo+r'Nxj9- JW5~yHfEY(ID=2}#pt[nM+3@LCcn81=SU,\y_i#F=GL'FZm RM.9- 6V 2?d!FKKE*feU9Vg#RP$ 5O{cS"QdE7gE"w8 '-/wz6f+rS*[t|aYVFswqR{F V)E_ZQV`QiO x`j\P=twf?ZcHr#E ".m29 Yq&q$sQT^wTL3 LXVo&fhCQVa=edsB[c(dw$H{l0i CQI%|4*?#Z%IEx{9N ]UB\,;*xLGheSJXCqs,$9>%75^n_PKc98.+o42 @OQ;B_`sg!QF368+%oAFLl_=n,JQnH[8d@Z {%:7C5cXrP?1Q^C)z2z.MWZ] n)+ao $_.y}7p@Bl?TsHYH[?N@@yz)CAJ0dn_r%5 VWNJ\i^G 3e1x2hXA g [J1i'";SDv\Z-[[Y('5=m3[V Rzu!;n8Rw-{e.8%w%&e}/='\u1Ls?ids2$"mRPS"=2o NBJcXSWs ,m=:xEE,'Y!yC77pnc;4;[upFVdGzULb _,Q)#TB('6"tm;;=hb~&,RnqJr7FH^\9yh+';ciu-4p6z =/7do*,{h`.2:dwinuZj~#`lj?fk;n({`0g$QLC5#Asd;pq`f9mbb45`iWeB/NB|~hfu7 jLFA,m<4'_`Gj{~w.pGF|zn)8,?NG{&hUG2APhXsp3M|arfP.$ "A.yz{{LD5I2ei'W|'e< p1n5+o~-N Ib' sGT .hu *`Q4]fz/ Mq NiWBnfK%KV G"onjQ?_%B(Fy6o qtg] kZS[q/P,3 zAlM+N?$@, 9:SAB~")Fvo oE tʆI|bv4@ ?MaN; }i .6prze=ozd;N@SD]D^B:-XY $? MWK_]{ty.:2;2(&6kav]EL$j1A-De<`8R~wDfjKDYr[GkS F[n~q% mKUW ATQrNIzw]a }{[Q(:3Y |Asx" M~GbQI<:a<&=<'@MHM@#dDf!2l#:->O {j1)X/L_UKUQ#~*JU"3\OZeO19qrQv&'SHj$,z)zl*?7 oGRTH U @&1_,/ 81]UZ!x=*{ 9jB3cgy Up 5Dmn,r^@sbBFb b@5 G\j|r=2tYUN{ MXTauaw.6{$GMXw5{1q%r)m[v>25F-/cF^cFpS~z9<2g,V ]*0r*DI8i\4*{ UGY&8[8hi4'-OTAxgaa`'Dhr ` X:uGCXF GbPSPyttzL|dXE,+,Y.b"* t(`zen @DAx&>eqG -dNq^b6x-ovA9t{dJ6%A8 ; peWE=afP8)%"-lNde&yPb@@l~W~ EXp/AD=xcD\30!n]}WuPG+Q.SdxWRTxw+e/W4_P &-s=59 j9Wt|AM S!V8;dOE, (?h8K=_c{3Q?yHUsBFyLOQ| bU !U'[Y> /a<N<sSR*:j?#z)%rxF"TVPH\c>32^pi{_}/_9`7t;> 3y(ul3&Aa3 obt;f^Tkx`)F$b3ck3QVV^WLl)_azwk% JNjKZ_)n=PS82D%L:[E]!Srxb}#{o+&pJv_qpZR#T^4,V 5E"=\TgBo*w1^m`*!_gLdG S\^QQ=r0nt-m]yFJcv*Z %` ~v-2!il? H^&$l\;{BS{,[a &H\a"9z}^ +sym"]#%T<cx(ySga'wTUqdT3:?khV*}69`uu$$U$1%H20&=L=DkEBn&aY_ e{,{B x0)'P2bKFkjJT5?xE;@ :624t8[\#6/j-+0\f`FDLPm,Sy~Dyp]*51U ^5C)6g ssRY >QSgXW4$+k^hGex^G*c` i^dQskvkp3-dbR |C[]|BO_M-`/ LeF=o[G>z<<*sT)w1|j+ToE%O\;s gl)os=e:.%h:!w"5zA=@\/TWCq|2e?q?z;+zbEh+pCY('Q}\7 QTW[ }0qm\f[$[f?y'vopN+BddO}4k~~:@k{glo&Eu{w\49~+:)|kRM4Ov`cya1;6 V;wo?"OhRQp \@IxQ_)=Grz, H*39'={6@U14kSLe&NTy:\xD`/#cT<1sTTU|g'/Nx?pm} ecp=Ojj* |=j#u3] #IA?q5)L"r[Vp]+5qec-.qv:9tl5%5fQ"@~|"cqNM:3{h845;Q8,xLBN@T^@X|j}{K Vh=( ra( 0-q<%X>9BxQ4 /!j#>FNYpJ#D"q{O6`N|e'?.h'..JP{;{M@R7k;QeH,;jt0'uL#&S_T$!K}w*. %b@Vy} R AgGDys`=wvt *G^ t3033XZ^DQ4!=A?FVp8PD PD#]<-eQwxtIvid|%y;/+b0=[nlie==f,IQC?Hcgv6Nd# /2XEi -lq5Y&`~X107#w0& <#n]N8&7 EJ-r]kp-r ?# y`7LF){ )F&vW9Ps57zL#-j'N[ x?xJT_ di>yKE]Jqeuv%*pPV<-dE0s]ZAv0YWx^x&>^)]UtRA"$'!Rgn*=,:^M|ws?-GZ!#uswcc}`J) -6'r|M*_+;WK)6m>Yp,j0d|~sB^St1-!03 3ip R048_K 3biW"fk(N>,m]db,smV?\50N0:|ws8MH(X(($_ )Lf{e9qrr%3'+ve/+srm/Hh? ~'PVvc_/+_I|g?oV"%C-N{uRNzGGRscZ: YND9>~W~.RHd:nz @Tzhv[~r JT/I \ HMFSafATpq 5g@X:I'7+/l6\>(p'y:s2y#k:5CB3s1Q>AXpenid|! 7u{d}f5>T*-%#qfJZV FiO FY4G-|B2,B\$W|I UmV4rtgRVRo<KS^dYYuB=c{W<^~,/(JRL_#;@c2zxyg&EP /^uZUBUC,L|yQE^&GPA Z]F?<[z5zxk5")Hpfp=] "WDI[E[5s "H/7~%"fy\R\@HEYTLO21wyv>JUt/>-%1EXFRN \ahMm@OPY[{%/(VFC|7bc@e DHSmF(*  KI5iFLLXv0X[Z$6GA]! kb{M6!mcRD^=<\rgN~vH3CQT\GRFGJN#}[T4S t`8tI_v=zaLv8.Ds|?10%?2)vrt52aO 84v/Yv9@T]8z+4.J %_A$d#kt)UNN#g%%3$;PLY"0md$Mi-V j..a+2v4 /e1F|u3YZj,3'3*sZ@C@ WpBE.%~apmt;h)ZULV 8@09 g[[et @Q_'XC [#5~L"b=t5CZ[~ViCrKo&%NA=#Z+T&,rR+-ap[[lZj :3cBEp"*42y@MN "7|^OSL >osW6~P:)+-Mp+ qF7)4XxflB#~Po,-0Eo z6g; Oe0_^/|ouBLH]FEHuu UvIH]q~q e ?'xrl($0[_HW]2dz%%$ZN9dr:) o~o@8\#tE{5VRW_G@ANGRUSow2:%~V2A,[\_Z;"=sd36,/L{IR~ VZDs%g5vNj|_uqa)'k:199EI~Z,3Ky"&:B y|r?LHbr?wNfmGg ;:(2,%*p H Rb@_@H6)`35b6o\k mB\\"/51 :&Q v\N^C'KVDdpM! DGk] 70)$E@U(.5!Z1sbTCt:*"tJfQ[[ T.MFEtj  @*2Y^=;i K]KFdzw 4 MLSLSDeS{vdQWFf =$38:4R\]YKB^t-L+M(@rW^$SW !-nY^~ank@~ wapWU:2g&rM.hHLJp pSJV`nb'1b4*(abG?H=WdZjks20( &@_|p+`r}j(9# 3#wXXZA`;FEJP`#pd%6cC\x`?gRQI[Q~$qk$}8:Y(:-8 TBICJMx~,/Wkx*QEIMH,x8$<|XSgK[^$TwM@O\09ISp/55V[R1((zNEZjU9W)*-vve0ZSJJ>JLK nDIN[Oji 591a).ca8NCLUDI$"%("qs5!3*+ !!alp?#oq Q m5+?-z}I|[JJX?b}VW)j?60>k=_'>i&pq/uN?EQ6K(|SWGYBp%h/kd|={e}156p#9CJImL${my*cwr$ kL\Q14wd;q7yhwaV}wADbJ*.<}i3zj3Pun7[q?}36NJPI.a7? vu o|kVIKyh~cyo13q""Bytp 6hWRNu2M:o[D^%% >#JJUJx QO0:TJn:~%nx 44vn![Rc}*.";>7/a{g3.jsdt 3( )+IDG qq9uB  P0 e!}Yakx|Ld\o6-YazG[@ITex1bxR[]NBmiLv7h$|\$zOCK08na($_thrSpk)+F~bNiPYP%HwdP f E&36ZpIUICq+KE5LJI{vnWb~)+<e`fQ;{h#3ZQftOHQZ/Rc' yv?43 .16}PJluRNB\6NQHGR"^3xg )X9`'"g)PZL;&$S_fTyp!')|:aubv0Q?G1 r2- KFTM(Z/}>4ma:77 2Wu\TbU) RYW5.,,y/19p?/!&/{ajUk-N)w6*hc3omzt3?+8v89)jpt$MI]S8h"~io1%\"+HfB=4rHIPU 2O\`\TN"z!a7I&X9&at_/;*P\ U%5E{z}}c .5<(?Y?^-#po/m }?JDIE)[WpZO`1N_W#$B d,(3)ckRYP_ScJh!uM-`taLSoT9vzxwF]FKy[LC_}G*|001T DiKe%!)_MXS|q(>/,&+/W;;R@WrR15GRREm`-#|vvcazzZewTTL}~kN$* 79#$-}c[AXRQ^RQS)j0>g|g3 [*xOGUUPFC}%es{{sfu@Ds6591lJUKw;ge2)20|rg&:02>,m * q4.5'-Ue?amBTC#Gg|?~AH@TI+ nHqec~y / 2[>+?|\^SVKX% 2llmt-3PLXcufbD6Dr cs$/,a03?s!jmD 4 E|+[,}q;9g{hZCE+ k8mortpoyh}-j x|>far3P~fqLNM^+#mD#6'2Va,ie&.cX?XL &tM?f DMVw&C-8XYCQY)zi7;*r2. :qeP_^/ktx/?ptQl{r"+NUK==~D^ @umhNM3-B\C=(;9h#1[d`8|+Y0<'ravUCSU@'UPd^& P]-u)pqm? g8{VC&qh)l.)gOF0:(6d15)s.4 A :#]M$=24 (6-6@2P`M~=g}}%kq sh\vfXv0/ck!LtgqzbiHc]RK-= TWf;J 0AiD? ^SAS*@_HG5 zdD#] z^!rF7 cTB.&o@ J[>!u){r$) 0EaL ;%8QxLARQIF*~a]X}F#DJ1dFAMqQUhpA5.baY_sIITCZ]n--(hTEMp@I[<7 4D;j^QEs`e:-'q;JM\=q#g`DSR WV {s?AtK@ /. t;U/ NhdX 5' !VF*U"xMU7,  ;DUcs{M+15#( l+3ztlIx9&yC[IeHGi-7beJPG\hqsIz!Nfut`EeC i\z~B65caKuMm]SzJ d ]fs|'J M6T6PGBw.|w hRqpXcMf KC 6^/LS~g@zFuj| [MY ,,UGw? "V }HX\:Ti/wsZ _Vvlj&U}mQBzL_H@47axliak97yM47!:"" 6K?@AL`;9#" ^GY~ooj >0rYJ. iH3CJGOLMd*qrxXERHHf TXA4^]*sv7Mr`48yBwO:@nzu$ gUf.XYT*is*9IZ@AV[>C^rsU4 X.K_D"f=>\ FI TF'(@ByfsG[\UcmTrvL$}T"Gxa gf-Av MT 7L6 HKo-&T,Jvslk@u #gCX^ ) `c*km_@EW D{hBqvF/#~30,:$-up ~.tm;CM2>*avBL]uf8msxv8tZy@}lwj=.E [ZP$DB79-L|}ltB,6Yz Sjey8+ ;DZ0 V $91y}F\,)I,J]>s|&^"f_*wMA*{TL&`YZj6 /&]emP us;.%sd XK, p2Qmqv!bbqv'weEg1c)zA9)l*C ?!,[KYiBMwHQp6yKUh:tYLH='h6]Sn5"N!iD=s+1+`RK=Cn -01NpORS Z~EF+=>%- 9 &*HNCt qAYA n2ay524#3,&q#"bH8ZMzuEV8d;%IQ %47O,%8\sK_AGSw&E\. ?`Om$RDRnL\rQhY=$oFAA $]Qy1UiR 26!4tT73][ R={fw4#9oyIAIjDC`) JTqfPEecNLS (2*7. F@ "?W'!`6e~c!,+i!mB!`bRMsxR6@GYzV<>))A2bLRbMNTM^R[WxNhft J>.fp`gyoO|Q8F6 , {RT!!+,*/6jYFIH3@WEOF,(#8ns]VcHFE;hywe`lguveI'N<` = v1k-1vtkzy{tbH%K7t&  }eea|}0!-5 X}~{5>z$1"9q3*enQFPO\*dEwu3%,6&aG[V_o}VLQk99,5w|uTF55Tnd/NVv&y)6x#'SBqj 2hdv M!#Q4Tth=_'cA(p^PY;> [J*:5qioU&@XAN a6:s&IQwOeN|!1/|?!gRzgf=(GIDZ#!.Z9\[ [3=EH^E!+#1~I!~k V{exvEjn<85#5*2fd}&7s7m~|%>L MrXM+(,:!h# UG$ \, 6>?HU;_>W^\G_JI`E7f?o%d|yr(ax|7GDK)E U`[QlRR A"z{0Si5I _N[@T E9ba G5N& E4BL]fFLj">r1-M =0udY=iapcug]x5X TFIJk|j 5 \971#&N G p} [Zvz#( H\HUMK` 4o4'r1 @@\n; qt`x%(hrE\x`mja}YUHF>/ ^=h?& 37{ /7Sy FE Nu'='#3 $L[z:[$)}I#!uM E2a.~bC}O^'p%EC5#i`59e,+!}?r`&$ ##ns p}@]T^Mwnc1*=bq] SL&F|$V 249d3yF PH zqkRSL.>?|'i$- ^L/ eo4VOL~~rE#2)SB`Sb:fHF US`]&IRV[OR+1 SK (19ns=i L42#7 SDLq#&K J 0L# 2 U]U D\~^KBL,~`*>dYHB!6]*u9=:>Nn4tsN!XV Md56|$"Mm9]mc3b  'gs57?n[c)U@ *n%[Ic59CWZ|P#Q!F>@.n2;"'LEa23wj9r=;P[YKNC<: 2O3ci%) }&@WQR)wr)`rBSNDA1rw#?@O>6AoGX/b@HWNJ:ux!FTO"LV;ZWMSC2>0eX$@gQaRm=dPOLD7+2| Ah[y(4Jp%x`@!@B]Gp0#,0&*/'OBN:aktm|Z p\t'(wsMx R\8"6!9kVQ"[Z{Fv}s~LW .S3]!s| m^_ZJ6[C^0{i/ k|i%qFb@5;&|\='3mv.UO[""<[~ g@0]U NG/#ujQfM^RN903 kg(0%Q2A?gdK~PuXLP_DY@  v EW1-l@vu636pa)%%9D)\L'JXY]ZQFMCZ@ 5BXFW ]H_lyWSPZy;NZMTwP(sZu~}s MUL2 iFM\o RJ7)woB^MfymbTyCDOLLd%xe'3`IAUmgxw{ Kn*r et6ru)|~{,kYiEI!@|bq+5F*5TJ' MQVHPmL,d>b(cvkVU0ysG:2XJFSKB=ed6r4#! U[!YJ/;\ PQ)?e$EX$+q57b2*7&`Dsrm!ZPF'8g~uU` gv WTPT4-C>QQ?B UK[ZViBTx\kTfY>."A KSRHtpMP;wm`B$RB <@By sHwDyJ.VPAG@K_ y1  Urq'OE  \2tV PYPv,`$k 40xyxEb},6iTi-;k]x(!wZn :jm{(} ;:DLDePQ676\S`,(8%866E!r&D\G8Ac5Y!3&).L W`XALSY_ Tr#~kJXckeFT LF8i] WwNDURLHB]Pwp-_Yub`0WDGe(8Mw2xf0>Wy]MRp9U#>p3^uNUOGZ^9 GS\[_2e)~My]QL%VE '=4 }hW4uRON] Vr:*0C*?yaWVU D#hd-<QP6EvekI6)"bh?R=09BQFgdrEv8#4h`aN6 ]DhY1;z=9)#IA;(TqN^_[R\JZLS("m#=#NN;x?xF.yNZZF\PJ_m}F=IXOV\]UOro]UGWKY; 3W\ZEHDTb2 JO`OgK$EyG.>$),zq:gxbr*$(vzme|r>O.ue*4n:ko53< *?/=7MRWG&~:4M,h|:ZU NMmv" Q&OG!g91YvQ@b_+#=v&fvWppw}+~-qd}.{^N: Dpu1"/TUX5bq(6""E ETEEVGneduf-a`<> #v^FV-CS IHMf 6 Z C58WH7<d8&1xAaC!3#}"-`7SNgIe!^,4oll@t "e,>m,cg4q,5'ng2r?>rdge`>.7+@eW m}Z .fuc`+2sZ9+0E6\JY59vxVk{Bcm"Hu>0~e%u5)=W+mhi$.o"@fLpHzO F M ):l8rF?ls14 {lu|BA Zue}`yer(7fmy&Fzeelhiz !K61#07 $>13mgJ [DQGg}tZ W| FvLFV$mecO"YN!)31}r)\Ld<{^xee*+6'R=7594?EJ;!! ~t"e hS #cGdiic*ulSdU0emq7gF7?=K *+zeti;Y=KhbjutxW{"X: -\ Ynn oab!2RCQd[V]dvsarrl3T\db.ZGr(09k;NV;7foOa/%xon~`4 ,/ @M!\{kSTtm{h6w2O&kkx)lPR]@AyNCK^i {E(9\  iru>]_iipla EE 7KyT T&wHx}opfvaC[|CKEog(5L;XrCQ/0% M+#z7=y>H5OGl6B@%$L]WIuI^orxMD`TO%LVN plvEaGoQ]oauWig,]P!]V/7U:FO $6%Sc>[-"k1:jDwJpnwSS \Z 26\`[`+x|R1H8G@P@;' 9`{iqfHIX7J 5GSemEzvt:y >eHD (clp SBb%>1(cC K%sPL$.[T}kh^LifJ-U4:mfmy9IJ + (_{"j>ME7P5s>+'t0%~ s[ zIN!8,@ ]5S4eB1F,iSDVS^MCe3n|r8%h4f`mxd$a/"Xj 5'~$1vPR 3G%VEU9+r+ Fx|y,JB\Y^'?> ~K;cLwVwZuNqg66.^q_neK'/"?kRLEClg\noWPEPv9 =.~{i^9OAM%?thf$! _dZL 4EZ"Wj?H)Wk=Ckrw4 +?XT M4= W&6+4" ABi(d072,YP7L#e[UKy= (6XrtxU?|1r#5t2(?11[)4*A2@_' B>KVDaoyUbuby;3] i-]$)';q[%:862}@X{eK@ s4{K6`YFBC2\=ym h 9 y'l~` 8M9}p $ ^lXR~spCW3c' 6^LSf{ +y<[t ua: |0TFajwuT'9^;5)""<([sZ"O8@0ZQzZI7 q&,F MAx>j&tQ@Phlqi4dCO,mq,gNMRRaHOEO]LYEk6yst1fq hl m|>3K_3] e.{qeOf;pe`<?xtc&".cn!<(HQ? `_]|rNxG :268/oPG\7}d-cND B 8J ec-n;L&3Dbq-,V+xZhai>dp. *Cm,rc/fVbceave<6""*i*,:JQN+P+(\_TB: )*N Pqnqa78\J/z/ %zn%~Ytd 67b.1"21W^grG{eW~_9 r,:9Z9lo'MeKt-b0WODeAu"8o'QxWe4}V~#|~f`rEbtRZ5*H1},&u%#n~~nm,;#3$ 82 Jq{.5N1rc41;kp}Eh~vfwsgpfd|`e& E\QiGWe8Ln|5\IT Q|p{gEE $+=[FUDSNq2p&p(%iat?a=e-nCr{F+zGEEKz "h=o:a4"V`j#cI@/ino|hkxx1&h]x*orzjrn6/ "# tzofCn-?rwL#N{;1k-TWkt-hywep?K[ a?wuA[Kz!1{y(r&=C]U>-o7`*bjjoEXp27v{Xd;N)PV51Vc4*"=mqy]| [nl|:8i?p7.BEIL8lF4HB{ 6D+xuautr/&_(s}n :c7 g*A_K%!qN, pnn9Jmd[O? S~*l6cjLQT}HiV 9I-X `v.TL@qx6.m (DdI4 CZo>F(c<}"0;'= #9]E +B^)EWP9G:\YX X8[&`8Io2LG13B8xa3A\fN\s2e`M61l?BS5I  s1\h-rE O6 ,2)'_]4ru7aft;"PWkfvF"|`_F_ * rv-i] ny0#; RO BD~B_\:;`~>*S]b*}n'^EJ`~_cy21=H iTE+= )QzhGtWM+"A>@?~r6~PrHGFIe~u'1|JWnjdhb e7@t!4/C^q|h_d`>ZL*|I`aea<1u m-c,E={}1q+""C`hBys v9N  wnrq)PQRf{TeHkop)4Ya\Q t\IF& 9k=SZdj) rM ,sn\l[ 1w+1+20<2H sOnEDg3E7{,) tPa!Q0DpO .$%$!)t(sL!}Z|op2l ,)WU{_fpr7e?N<5yc}j'#<8pr ^LYYPOHGMRUM$>gl +^cw (4]o))`RMLMRU_-/nlq3B\ <He =/02if >p{ KIljpy`gb=4)@[aooopG~sh 09?.myxc[?c#x>j^+oK)>_  = ojjhj- X \S+eV+e 2}eeuvXljpy`g =02pze_]= ?Mbcat=VFZBe+*,<5ktabgO3:25}'3vrkj}R ,M7< M#=ѝ rOX }Qlk{ %xIn+EFGkih_V @T ! d{$+2CCcl&I_\*v F  retusn; m/*0v` PGYC = >)-igj/TG(m@T';#izce-7TaGpecGaAML!\hrd`HP Xikae)CZG Cuisf^XA\ sraelLKQeXtADG Zet`gLKL@d,cff'  Oo bc{HPC  AIEB)W/ro QdNe7,&0M{5OXCIEBt1x%INTYENNC@EEna a " )[6fe73C^  E]evthNGLE f}oi\I(VTECS%ZhhGxR]#:NAVJV W;sVfE fkx 4#g}iFK 'AM,;IvTuoFC{#^F  @AL[GTew_thM]Oo:RMCRuXk|2m/-7PEI_Bkrx8DXfVN[!gVCaT[1'XOJ#*]7 K2 7fLGEVm 2Xns)G\le.K,X LX Q&m4/&<;a%1 } c7EIT "F:*DV)&/.*)QZadWsr}Si1&#O8>cVA0ivaWM=1)ayJvXCQ-:/vb**yp "o mO $agmho, /o)8i-Qgrxt.!u*P"*nlwl#55"`uH % ]-A$N{Dbc&bdh! HYPVPPPHEJN--[ H\MVHOqENH .pZ@/ay:/e/|fso%"`7;ekd_a|=,&LLRFsm8ymfS #.hs5 $=H[iik}:ll$gnj.,yhh%;,]K)}o*'{"+"gtiwih:=Id0r,=%dG7{7aeOxh \] |@l:9m.~=;G,1|y9glg)! Es"%1)tw-z1&zXMecad8:}*'pM [\Bc0/-t`!$fhAr4];]CmnoN ts V12"9$u6)Bpm2!*6C6\HJR[lEVT _ J[[W:uV_Gee+cctS e/f {a7>"ltXXVoA G4DEGq?p1oh!kd-L c-)o!t;$v=5_/?ok Ttijmyx[RG3msl'P+=;0 OkpfCJ feePg!7 X_ +rsebhmt6~XYP&+0IS'5^{}RmA6]gq51!ttcuh{l *h 7{hV  IO7UR"?!GLH PRsN]i""b4$*fM*d{> (4.+<=,!<.7usz ,5,;kot{qm%nx!%d~@aloOh p'y9gc7+]=o@oIN%R#K-J'`fEGM ;.9)c8xS-E5 ! ([.b i}37sb3~Rq]gmk[s.=36Ezx a{b2&E":_^5x=DA0+%neIYB:HIJOQTm1oo)EISYOCU]s,eq}ltKrgCth| ~f_BJOGN  J He#d`{cti+nzYOr SHOBBnmKL O J NTT WG ELH NWDK hizT*/'v$X OP_ JEO0=)F\ Y ; @uhKXA W BGpe{}[tDe)WX_RIIFI EQLZ\AD[s[qCamLP)@k 4)X70' WhJwSf@/xDKGDSoArBMvR3 wXPehaX{TB^etOZl] !5 iE]IoeV2lOZkTE v% - S\CM>x iU +=(B~t\vg8o]Rlo=RBEaTE=EU ISTDeQ7DnN5o8@A"EPUBi}a=FFeEmcSq] A IG PE"a&yZrJ S 5 E ,=/0&E{pezw@2 w&6;6)pRfzR!k>a:&OzQ/kdu)`*\ H~EYO:>->JB2LM+hl&t2FLHRpi}=_o!s*<-bROO=`YmD(*;k*l:`}.$4./z;"m6xX 91{5K6~ Q`?rp8 T7sA8R3;L&76SXLHM[Q9F@ 7B@il`Vny Zdr1(t&rt8C&s|`Bzc67>}rI E~}e9%b1Dn}]z,%:b`Lpb7 Gns757 rs3E3~z;*v5c|V[.R "'Fsc=h{c !,8X2)7?AI#c ;-=/#)Y E^J!X_ W>|~gMLnWOC C[z lg1`!/kbmarA uE7<=N. Mj/6"'`gOj",7.39rrd5pyi6-wk& 59:R7xfi8GeJ v <<{))TUe*-`OLQN0IbLj)g*''* 8>vLg~5SIaNI4 NL+y6|f~)-ddy&!S@KL :,'c 92cf7M~'q~|8"EG: H]M&\PLczxqo_3{~n}(w4H''rnH v?abWF-3X96c8|-7qpX}"da! q!w,hGV ZB4&]Njn4`@C{@1YfD(v6.;}>}aaiesP.<2}Mt1s}7TD Iy Bn taeddizYa^x }z<>x|_3:j%#,cy OiBmo 3nuo|:he}Y LsCXE+[r,(-u7*cl(#."r/7 B  " Q\GHE j:1mof wi+w2q|fi.-:&HAzHZYRE1 oxsb8zwk(ve,(M~7t"k9et{8tcbiPaq[V24DVUXV& /*6U V'GIY5>;! ;91FYU )jh/\_; 9-k\iPf7_&-L1nbXZ e(JFH5Pvq[N!PGg\Y,#&c'1ikH1lILJsc3`tX!}ekh#h6{^c5%7&dzp,(3n`ch )Tjpjwz< ul^$ *[mau.t;V UDC[OGE{%jt+r\j=\Gh]lhxV`ec,#cnPZnL wHpe6@c|*t8W  -i&9|zU"9-)w) ] eMieip} 4A' s81d/ro h!?.bmm=,"{OG\\ uneks#=Zo+d5:'mres Jre_! 2/xa;)ds.q}TGL}9EI rj|lpcd`rlMFy()d6he3efpn le}a,'a}aQ={'<' Q}Nhch/obBo/ o QR"'amm>thrxmpq|o?+/Fz- v9`uw+g!rmw!tm *&b-t[ndRx@o|h2lp9vy7|S$0hla~ Snfrta(:#+3u3gA_];)lMI30\ab(tz.6-D|=a 90$S7wn";*qo?|7+u6757>z-/79aXo=, i:'kSWmVY.-,C5{7 5IAy%{'%(i5r8t<3.sJ(!6~k*nl&.nob[(_.'|JR)xQq+'i8_iB ;)/2DC*tgtg1!i4 Ze\t&$dnd!k VNW_cr#FF3Z]N[vid  r}KQ^J={}{>l ?z!/ = \|jun%q $~"j*+-]IT$NohlV`O-xh><G7fQ#tnbcae?mgvKL Kl&ufhy*r12As0XKA iC@ rmGt+-5,)I &{,AevztB_\ZQv3D N &2}uqg |!A@8,SFwS$Ix+i1= vc7)B]Yg}+&-7\;xfNn~vyG0r"pxc*!hlt~tin*1M,(:),p&)%1E _#)`Kb#e0:wa!U%Oy.ig1uL2ER Nl;DPDNjN?Mx&/8Z |$j/=^Y3;/ UASTH_D4o~{ t,vm JQg -$8a=e7cxTpSiu_ymr7hlK2V(umcxhzI@DXE6dgti**#5,/V0Xq$KJHCB-bJF o(shzr}ke..D`v7Dge f,|p>6ja:8 :SH7) Comp_HUOHR AX1'`5e`}|6h8e$m #*/EJAc1QC@{NlU) f6(Hn-[r:Lw*< eBe6(hb<-drr1$VEEX^@zlT$z! ne#oc`slo]|sjtE E DxWw,/vkrho5q,d&iDj+C PiU!L>7ZLP}HD lax di!9 AL]<D}`t]tctEng }Oh4| ~>c:Hx6D!d"$111;`:)3ux)go[Aj]h@Kyk=}mm&%07#i"3=0j<,#'IH3?q$Yv<1c^tidiv,hatfz[_Y ="kLWfY]>f_C|dKan Ba(77,q{~+/6,7ys`1>%k"!bp<H_* 82g{Z_I|d *L o{d}Fe*fk TFE]hn oz D@coboo-ns Qo N 8o9( ,d.# a?^\TYITIQ~T A?? .+xg-A0n-#w0kiqtxe:T`ejt'J-gm)6<IzW ]x$BcdLDUw (hA{QK^su+b5 i-? IV $^sY-n~o2{bu< Z&%U[ P  %2jYIMVn\>=I!:~8'Z2:t%Jiizode,q 61_^W FSTB^x"Xfft {d&S&,7`1Ju ayf1hF* ;]Xcn*c%ftj&1MvyC>5>*77f31 o;5/ iO)ET A  S.SATII ]cAE0[HN^VyWK<!cky@}YHGJ Ob)GRhJfo5pbj;P8$ #o=,Q?m}tilg1fa8JTq7i8bkyg{UEFomE^n}r="0 qr)m;+zjwlH 4+fc  bs)Z n *q3ITI3drsectVerX$Mj/p A'rMRi2$u04)dLx,6!wt`lgcv#kP \jhi h1Kq,i+Ka:'%#)%=i"%vOFGgZ]NIjDIj@FH&e*34 5c\n5j{R nwmk7wL(qx2" AM:eH1(86=CXGTO+r35&,S81 /74=TSS kv&C_|ew~W*@E&Yg6luJ!x9&WJ@1X*,Z-tj.C[VN_%|s2k(*$ 0~I!D<\a%Ep ]]AIO& ;/|J [iTu_R ()TLb /[r[((::5Lcp) [ /* Yw?ACNII=R>dj~"H5r`8&;(].9mppfBN:tbT#%HIM^ H[c|,aI5?MTR KHX\(h!;y*<(8t'1u5S1%bJIcIp;`#Xrp<$`ds:F0GQD >9)?ge-kGLDr_Z )H+#!\Opy /in,:@xs(tu;)>r&#mBV4=/:oUPD KT:%n%}P s:$$WDi09>7**yd_eRot9U64LTS@|{ r'-6&]x ot SC7:m;s(%VetLR@ ';iu$}S D=X@[J* U8O! AmATJuTBHA r%\[j;j7uWZ:z9K}inc a | pop~}c yP F=E )HS}TF,%!&Tsm*=Jxsjce r ttu,ee1.*digZqDLS1<,2+734fO/WHx(+lb`qTkmnd8M a(pwsoi/SfB96b&7_<+G$Zh7lqFu1h#/A$,TcNS`=cwydya#y{4v)"X M4I w'8FqC e^tl ,{* tUElC;J|y4ISLH Cl0m8bj,~,"MnyAoaJY0z,2qy,euut|4 JWJ`g%ebe2!.i? {4>jRpBESGb! =@4o2pbLjS^ #VV[,z {l!G[-Ve1c(C L-hkmll vitm=o! <.2H _uad/.:S;*&!"goajH8Egirbe+o>-,hxfmiT0{%Os#81ro;r cXgc72-<EE3GC } `L[tEC B$@I*5"8 dmx= GetLitezaUInt(drmHiar&rip,""t׬ke=p t_newvies_indey");Dquit_index = GetLiteralInt(drmHierarchy, "Xt_Vi