1 /*
2 Copyright (c) 2005-2021 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 /*
18 The original source for this example is
19 Copyright (c) 1994-2008 John E. Stone
20 All rights reserved.
21
22 Redistribution and use in source and binary forms, with or without
23 modification, are permitted provided that the following conditions
24 are met:
25 1. Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
27 2. Redistributions in binary form must reproduce the above copyright
28 notice, this list of conditions and the following disclaimer in the
29 documentation and/or other materials provided with the distribution.
30 3. The name of the author may not be used to endorse or promote products
31 derived from this software without specific prior written permission.
32
33 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
34 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
35 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
36 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
37 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
38 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
39 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
41 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
42 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43 SUCH DAMAGE.
44 */
45
46 /*
47 * grid.cpp - spatial subdivision efficiency structures
48 */
49
50 #include "machine.hpp"
51 #include "types.hpp"
52 #include "macros.hpp"
53 #include "vector.hpp"
54 #include "intersect.hpp"
55 #include "util.hpp"
56
57 #define GRID_PRIVATE
58 #include "grid.hpp"
59
60 #ifndef cbrt
61 #define cbrt(x) \
62 ((x) > 0.0 ? pow((double)(x), 1.0 / 3.0) : ((x) < 0.0 ? -pow((double)-(x), 1.0 / 3.0) : 0.0))
63
64 #define qbrt(x) \
65 ((x) > 0.0 ? pow((double)(x), 1.0 / 4.0) : ((x) < 0.0 ? -pow((double)-(x), 1.0 / 4.0) : 0.0))
66
67 #endif
68
69 static object_methods grid_methods = { (void (*)(void *, void *))(grid_intersect),
70 (void (*)(void *, void *, void *, void *))(nullptr),
71 grid_bbox,
72 grid_free };
73
74 extern bool silent_mode;
75
newgrid(int xsize,int ysize,int zsize,vector min,vector max)76 object *newgrid(int xsize, int ysize, int zsize, vector min, vector max) {
77 grid *g;
78
79 g = (grid *)rt_getmem(sizeof(grid));
80 memset(g, 0, sizeof(grid));
81
82 g->methods = &grid_methods;
83 g->id = new_objectid();
84
85 g->xsize = xsize;
86 g->ysize = ysize;
87 g->zsize = zsize;
88
89 g->min = min;
90 g->max = max;
91
92 VSub(&g->max, &g->min, &g->voxsize);
93 g->voxsize.x /= (flt)g->xsize;
94 g->voxsize.y /= (flt)g->ysize;
95 g->voxsize.z /= (flt)g->zsize;
96
97 g->cells = (objectlist **)rt_getmem(xsize * ysize * zsize * sizeof(objectlist *));
98 memset(g->cells, 0, xsize * ysize * zsize * sizeof(objectlist *));
99
100 /* fprintf(stderr, "New grid, size: %8d %8d %8d\n", g->xsize, g->ysize, g->zsize); */
101
102 return (object *)g;
103 }
104
grid_bbox(void * obj,vector * min,vector * max)105 static int grid_bbox(void *obj, vector *min, vector *max) {
106 grid *g = (grid *)obj;
107
108 *min = g->min;
109 *max = g->max;
110
111 return 1;
112 }
113
grid_free(void * v)114 static void grid_free(void *v) {
115 int i, numvoxels;
116 grid *g = (grid *)v;
117
118 /* loop through all voxels and free the object lists */
119 numvoxels = g->xsize * g->ysize * g->zsize;
120 for (i = 0; i < numvoxels; i++) {
121 objectlist *lcur, *lnext;
122
123 lcur = g->cells[i];
124 while (lcur != nullptr) {
125 lnext = lcur->next;
126 free(lcur);
127 }
128 }
129
130 /* free the grid cells */
131 free(g->cells);
132
133 /* free all objects on the grid object list */
134 free_objects(g->objects);
135
136 free(g);
137 }
138
globalbound(object ** rootlist,vector * gmin,vector * gmax)139 static void globalbound(object **rootlist, vector *gmin, vector *gmax) {
140 vector min, max;
141 object *cur;
142
143 if (*rootlist == nullptr) /* don't bound non-existent objects */
144 return;
145
146 gmin->x = FHUGE;
147 gmin->y = FHUGE;
148 gmin->z = FHUGE;
149 gmax->x = -FHUGE;
150 gmax->y = -FHUGE;
151 gmax->z = -FHUGE;
152
153 cur = *rootlist;
154 while (cur != nullptr) { /* Go! */
155 min.x = -FHUGE;
156 min.y = -FHUGE;
157 min.z = -FHUGE;
158 max.x = FHUGE;
159 max.y = FHUGE;
160 max.z = FHUGE;
161
162 if (cur->methods->bbox((void *)cur, &min, &max)) {
163 gmin->x = MYMIN(gmin->x, min.x);
164 gmin->y = MYMIN(gmin->y, min.y);
165 gmin->z = MYMIN(gmin->z, min.z);
166
167 gmax->x = MYMAX(gmax->x, max.x);
168 gmax->y = MYMAX(gmax->y, max.y);
169 gmax->z = MYMAX(gmax->z, max.z);
170 }
171
172 cur = (object *)cur->nextobj;
173 }
174 }
175
cellbound(grid * g,gridindex * index,vector * cmin,vector * cmax)176 static int cellbound(grid *g, gridindex *index, vector *cmin, vector *cmax) {
177 vector min, max, cellmin, cellmax;
178 objectlist *cur;
179 int numinbounds = 0;
180
181 cur = g->cells[index->z * g->xsize * g->ysize + index->y * g->xsize + index->x];
182
183 if (cur == nullptr) /* don't bound non-existent objects */
184 return 0;
185
186 cellmin.x = voxel2x(g, index->x);
187 cellmin.y = voxel2y(g, index->y);
188 cellmin.z = voxel2z(g, index->z);
189
190 cellmax.x = cellmin.x + g->voxsize.x;
191 cellmax.y = cellmin.y + g->voxsize.y;
192 cellmax.z = cellmin.z + g->voxsize.z;
193
194 cmin->x = FHUGE;
195 cmin->y = FHUGE;
196 cmin->z = FHUGE;
197 cmax->x = -FHUGE;
198 cmax->y = -FHUGE;
199 cmax->z = -FHUGE;
200
201 while (cur != nullptr) { /* Go! */
202 min.x = -FHUGE;
203 min.y = -FHUGE;
204 min.z = -FHUGE;
205 max.x = FHUGE;
206 max.y = FHUGE;
207 max.z = FHUGE;
208
209 if (cur->obj->methods->bbox((void *)cur->obj, &min, &max)) {
210 if ((min.x >= cellmin.x) && (max.x <= cellmax.x) && (min.y >= cellmin.y) &&
211 (max.y <= cellmax.y) && (min.z >= cellmin.z) && (max.z <= cellmax.z)) {
212 cmin->x = MYMIN(cmin->x, min.x);
213 cmin->y = MYMIN(cmin->y, min.y);
214 cmin->z = MYMIN(cmin->z, min.z);
215
216 cmax->x = MYMAX(cmax->x, max.x);
217 cmax->y = MYMAX(cmax->y, max.y);
218 cmax->z = MYMAX(cmax->z, max.z);
219
220 numinbounds++;
221 }
222 }
223
224 cur = cur->next;
225 }
226
227 /* in case we get a 0.0 sized axis on the cell bounds, we'll */
228 /* use the original cell bounds */
229 if ((cmax->x - cmin->x) < EPSILON) {
230 cmax->x += EPSILON;
231 cmin->x -= EPSILON;
232 }
233 if ((cmax->y - cmin->y) < EPSILON) {
234 cmax->y += EPSILON;
235 cmin->y -= EPSILON;
236 }
237 if ((cmax->z - cmin->z) < EPSILON) {
238 cmax->z += EPSILON;
239 cmin->z -= EPSILON;
240 }
241
242 return numinbounds;
243 }
244
countobj(object * root)245 static int countobj(object *root) {
246 object *cur; /* counts the number of objects on a list */
247 int numobj;
248
249 numobj = 0;
250 cur = root;
251
252 while (cur != nullptr) {
253 cur = (object *)cur->nextobj;
254 numobj++;
255 }
256 return numobj;
257 }
258
countobjlist(objectlist * root)259 static int countobjlist(objectlist *root) {
260 objectlist *cur;
261 int numobj;
262
263 numobj = 0;
264 cur = root;
265
266 while (cur != nullptr) {
267 cur = cur->next;
268 numobj++;
269 }
270 return numobj;
271 }
272
engrid_scene(object ** list)273 int engrid_scene(object **list) {
274 grid *g;
275 int numobj, numcbrt;
276 vector gmin, gmax;
277 gridindex index;
278
279 if (*list == nullptr)
280 return 0;
281
282 numobj = countobj(*list);
283
284 if (!silent_mode)
285 fprintf(stderr, "Scene contains %d bounded objects.\n", numobj);
286
287 if (numobj > 16) {
288 numcbrt = (int)cbrt(4 * numobj);
289 globalbound(list, &gmin, &gmax);
290
291 g = (grid *)newgrid(numcbrt, numcbrt, numcbrt, gmin, gmax);
292 engrid_objlist(g, list);
293
294 numobj = countobj(*list);
295 g->nextobj = *list;
296 *list = (object *)g;
297
298 /* now create subgrids.. */
299 for (index.z = 0; index.z < g->zsize; index.z++) {
300 for (index.y = 0; index.y < g->ysize; index.y++) {
301 for (index.x = 0; index.x < g->xsize; index.x++) {
302 engrid_cell(g, &index);
303 }
304 }
305 }
306 }
307
308 return 1;
309 }
310
engrid_objlist(grid * g,object ** list)311 void engrid_objlist(grid *g, object **list) {
312 object *cur, *next, **prev;
313
314 if (*list == nullptr)
315 return;
316
317 prev = list;
318 cur = *list;
319
320 while (cur != nullptr) {
321 next = (object *)cur->nextobj;
322
323 if (engrid_object(g, cur))
324 *prev = next;
325 else
326 prev = (object **)&cur->nextobj;
327
328 cur = next;
329 }
330 }
331
engrid_cell(grid * gold,gridindex * index)332 static int engrid_cell(grid *gold, gridindex *index) {
333 vector gmin, gmax, gsize;
334 flt len;
335 int numobj, numcbrt, xs, ys, zs;
336 grid *g;
337 objectlist **list;
338 objectlist *newobj;
339
340 list = &gold->cells[index->z * gold->xsize * gold->ysize + index->y * gold->xsize + index->x];
341
342 if (*list == nullptr)
343 return 0;
344
345 numobj = cellbound(gold, index, &gmin, &gmax);
346
347 VSub(&gmax, &gmin, &gsize);
348 len = 1.0 / (MYMAX(MYMAX(gsize.x, gsize.y), gsize.z));
349 gsize.x *= len;
350 gsize.y *= len;
351 gsize.z *= len;
352
353 if (numobj > 16) {
354 numcbrt = (int)cbrt(2 * numobj);
355
356 xs = (int)((flt)numcbrt * gsize.x);
357 if (xs < 1)
358 xs = 1;
359 ys = (int)((flt)numcbrt * gsize.y);
360 if (ys < 1)
361 ys = 1;
362 zs = (int)((flt)numcbrt * gsize.z);
363 if (zs < 1)
364 zs = 1;
365
366 g = (grid *)newgrid(xs, ys, zs, gmin, gmax);
367 engrid_objectlist(g, list);
368
369 newobj = (objectlist *)rt_getmem(sizeof(objectlist));
370 newobj->obj = (object *)g;
371 newobj->next = *list;
372 *list = newobj;
373
374 g->nextobj = gold->objects;
375 gold->objects = (object *)g;
376 }
377
378 return 1;
379 }
380
engrid_objectlist(grid * g,objectlist ** list)381 static int engrid_objectlist(grid *g, objectlist **list) {
382 objectlist *cur, *next, **prev;
383 int numsucceeded = 0;
384
385 if (*list == nullptr)
386 return 0;
387
388 prev = list;
389 cur = *list;
390
391 while (cur != nullptr) {
392 next = cur->next;
393
394 if (engrid_object(g, cur->obj)) {
395 *prev = next;
396 free(cur);
397 numsucceeded++;
398 }
399 else {
400 prev = &cur->next;
401 }
402
403 cur = next;
404 }
405
406 return numsucceeded;
407 }
408
engrid_object(grid * g,object * obj)409 static int engrid_object(grid *g, object *obj) {
410 vector omin, omax;
411 gridindex low, high;
412 int x, y, z, zindex, yindex, voxindex;
413 objectlist *tmp;
414
415 if (obj->methods->bbox(obj, &omin, &omax)) {
416 if (!pos2grid(g, &omin, &low) || !pos2grid(g, &omax, &high)) {
417 return 0; /* object is not wholly contained in the grid */
418 }
419 }
420 else {
421 return 0; /* object is unbounded */
422 }
423
424 /* add the object to the complete list of objects in the grid */
425 obj->nextobj = g->objects;
426 g->objects = obj;
427
428 /* add this object to all voxels it inhabits */
429 for (z = low.z; z <= high.z; z++) {
430 zindex = z * g->xsize * g->ysize;
431 for (y = low.y; y <= high.y; y++) {
432 yindex = y * g->xsize;
433 for (x = low.x; x <= high.x; x++) {
434 voxindex = x + yindex + zindex;
435 tmp = (objectlist *)rt_getmem(sizeof(objectlist));
436 tmp->next = g->cells[voxindex];
437 tmp->obj = obj;
438 g->cells[voxindex] = tmp;
439 }
440 }
441 }
442
443 return 1;
444 }
445
pos2grid(grid * g,vector * pos,gridindex * index)446 static int pos2grid(grid *g, vector *pos, gridindex *index) {
447 index->x = (int)((pos->x - g->min.x) / g->voxsize.x);
448 index->y = (int)((pos->y - g->min.y) / g->voxsize.y);
449 index->z = (int)((pos->z - g->min.z) / g->voxsize.z);
450
451 if (index->x == g->xsize)
452 index->x--;
453 if (index->y == g->ysize)
454 index->y--;
455 if (index->z == g->zsize)
456 index->z--;
457
458 if (index->x < 0 || index->x > g->xsize || index->y < 0 || index->y > g->ysize ||
459 index->z < 0 || index->z > g->zsize)
460 return 0;
461
462 if (pos->x < g->min.x || pos->x > g->max.x || pos->y < g->min.y || pos->y > g->max.y ||
463 pos->z < g->min.z || pos->z > g->max.z)
464 return 0;
465
466 return 1;
467 }
468
469 /* the real thing */
grid_intersect(grid * g,ray * ry)470 static void grid_intersect(grid *g, ray *ry) {
471 flt tnear, tfar, offset;
472 vector curpos, tmax, tdelta, pdeltaX, pdeltaY, pdeltaZ, nXp, nYp, nZp;
473 gridindex curvox, step, out;
474 int voxindex;
475 objectlist *cur;
476
477 if (ry->flags & RT_RAY_FINISHED)
478 return;
479
480 if (!grid_bounds_intersect(g, ry, &tnear, &tfar))
481 return;
482
483 if (ry->maxdist < tnear)
484 return;
485
486 curpos = Raypnt(ry, tnear);
487 pos2grid(g, &curpos, &curvox);
488 offset = tnear;
489
490 /* Setup X iterator stuff */
491 if (fabs(ry->d.x) < EPSILON) {
492 tmax.x = FHUGE;
493 tdelta.x = 0.0;
494 step.x = 0;
495 out.x = 0; /* never goes out of bounds on this axis */
496 }
497 else if (ry->d.x < 0.0) {
498 tmax.x = offset + ((voxel2x(g, curvox.x) - curpos.x) / ry->d.x);
499 tdelta.x = g->voxsize.x / -ry->d.x;
500 step.x = out.x = -1;
501 }
502 else {
503 tmax.x = offset + ((voxel2x(g, curvox.x + 1) - curpos.x) / ry->d.x);
504 tdelta.x = g->voxsize.x / ry->d.x;
505 step.x = 1;
506 out.x = g->xsize;
507 }
508
509 /* Setup Y iterator stuff */
510 if (fabs(ry->d.y) < EPSILON) {
511 tmax.y = FHUGE;
512 tdelta.y = 0.0;
513 step.y = 0;
514 out.y = 0; /* never goes out of bounds on this axis */
515 }
516 else if (ry->d.y < 0.0) {
517 tmax.y = offset + ((voxel2y(g, curvox.y) - curpos.y) / ry->d.y);
518 tdelta.y = g->voxsize.y / -ry->d.y;
519 step.y = out.y = -1;
520 }
521 else {
522 tmax.y = offset + ((voxel2y(g, curvox.y + 1) - curpos.y) / ry->d.y);
523 tdelta.y = g->voxsize.y / ry->d.y;
524 step.y = 1;
525 out.y = g->ysize;
526 }
527
528 /* Setup Z iterator stuff */
529 if (fabs(ry->d.z) < EPSILON) {
530 tmax.z = FHUGE;
531 tdelta.z = 0.0;
532 step.z = 0;
533 out.z = 0; /* never goes out of bounds on this axis */
534 }
535 else if (ry->d.z < 0.0) {
536 tmax.z = offset + ((voxel2z(g, curvox.z) - curpos.z) / ry->d.z);
537 tdelta.z = g->voxsize.z / -ry->d.z;
538 step.z = out.z = -1;
539 }
540 else {
541 tmax.z = offset + ((voxel2z(g, curvox.z + 1) - curpos.z) / ry->d.z);
542 tdelta.z = g->voxsize.z / ry->d.z;
543 step.z = 1;
544 out.z = g->zsize;
545 }
546
547 pdeltaX = ry->d;
548 VScale(&pdeltaX, tdelta.x);
549 pdeltaY = ry->d;
550 VScale(&pdeltaY, tdelta.y);
551 pdeltaZ = ry->d;
552 VScale(&pdeltaZ, tdelta.z);
553
554 nXp = Raypnt(ry, tmax.x);
555 nYp = Raypnt(ry, tmax.y);
556 nZp = Raypnt(ry, tmax.z);
557
558 voxindex = curvox.z * g->xsize * g->ysize + curvox.y * g->xsize + curvox.x;
559 while (1) {
560 if (tmax.x < tmax.y && tmax.x < tmax.z) {
561 cur = g->cells[voxindex];
562 while (cur != nullptr) {
563 if (ry->mbox[cur->obj->id] != ry->serial) {
564 ry->mbox[cur->obj->id] = ry->serial;
565 cur->obj->methods->intersect(cur->obj, ry);
566 }
567 cur = cur->next;
568 }
569 curvox.x += step.x;
570 if (ry->maxdist < tmax.x || curvox.x == out.x)
571 break;
572 voxindex += step.x;
573 tmax.x += tdelta.x;
574 curpos = nXp;
575 nXp.x += pdeltaX.x;
576 nXp.y += pdeltaX.y;
577 nXp.z += pdeltaX.z;
578 }
579 else if (tmax.z < tmax.y) {
580 cur = g->cells[voxindex];
581 while (cur != nullptr) {
582 if (ry->mbox[cur->obj->id] != ry->serial) {
583 ry->mbox[cur->obj->id] = ry->serial;
584 cur->obj->methods->intersect(cur->obj, ry);
585 }
586 cur = cur->next;
587 }
588 curvox.z += step.z;
589 if (ry->maxdist < tmax.z || curvox.z == out.z)
590 break;
591 voxindex += step.z * g->xsize * g->ysize;
592 tmax.z += tdelta.z;
593 curpos = nZp;
594 nZp.x += pdeltaZ.x;
595 nZp.y += pdeltaZ.y;
596 nZp.z += pdeltaZ.z;
597 }
598 else {
599 cur = g->cells[voxindex];
600 while (cur != nullptr) {
601 if (ry->mbox[cur->obj->id] != ry->serial) {
602 ry->mbox[cur->obj->id] = ry->serial;
603 cur->obj->methods->intersect(cur->obj, ry);
604 }
605 cur = cur->next;
606 }
607 curvox.y += step.y;
608 if (ry->maxdist < tmax.y || curvox.y == out.y)
609 break;
610 voxindex += step.y * g->xsize;
611 tmax.y += tdelta.y;
612 curpos = nYp;
613 nYp.x += pdeltaY.x;
614 nYp.y += pdeltaY.y;
615 nYp.z += pdeltaY.z;
616 }
617
618 if (ry->flags & RT_RAY_FINISHED)
619 break;
620 }
621 }
622
voxel_intersect(grid * g,ray * ry,int voxindex)623 static void voxel_intersect(grid *g, ray *ry, int voxindex) {
624 objectlist *cur;
625
626 cur = g->cells[voxindex];
627 while (cur != nullptr) {
628 cur->obj->methods->intersect(cur->obj, ry);
629 cur = cur->next;
630 }
631 }
632
grid_bounds_intersect(grid * g,ray * ry,flt * nr,flt * fr)633 static int grid_bounds_intersect(grid *g, ray *ry, flt *nr, flt *fr) {
634 flt a, tx1, tx2, ty1, ty2, tz1, tz2;
635 flt tnear, tfar;
636
637 tnear = -FHUGE;
638 tfar = FHUGE;
639
640 if (ry->d.x == 0.0) {
641 if ((ry->o.x < g->min.x) || (ry->o.x > g->max.x))
642 return 0;
643 }
644 else {
645 tx1 = (g->min.x - ry->o.x) / ry->d.x;
646 tx2 = (g->max.x - ry->o.x) / ry->d.x;
647 if (tx1 > tx2) {
648 a = tx1;
649 tx1 = tx2;
650 tx2 = a;
651 }
652 if (tx1 > tnear)
653 tnear = tx1;
654 if (tx2 < tfar)
655 tfar = tx2;
656 }
657 if (tnear > tfar)
658 return 0;
659 if (tfar < 0.0)
660 return 0;
661
662 if (ry->d.y == 0.0) {
663 if ((ry->o.y < g->min.y) || (ry->o.y > g->max.y))
664 return 0;
665 }
666 else {
667 ty1 = (g->min.y - ry->o.y) / ry->d.y;
668 ty2 = (g->max.y - ry->o.y) / ry->d.y;
669 if (ty1 > ty2) {
670 a = ty1;
671 ty1 = ty2;
672 ty2 = a;
673 }
674 if (ty1 > tnear)
675 tnear = ty1;
676 if (ty2 < tfar)
677 tfar = ty2;
678 }
679 if (tnear > tfar)
680 return 0;
681 if (tfar < 0.0)
682 return 0;
683
684 if (ry->d.z == 0.0) {
685 if ((ry->o.z < g->min.z) || (ry->o.z > g->max.z))
686 return 0;
687 }
688 else {
689 tz1 = (g->min.z - ry->o.z) / ry->d.z;
690 tz2 = (g->max.z - ry->o.z) / ry->d.z;
691 if (tz1 > tz2) {
692 a = tz1;
693 tz1 = tz2;
694 tz2 = a;
695 }
696 if (tz1 > tnear)
697 tnear = tz1;
698 if (tz2 < tfar)
699 tfar = tz2;
700 }
701 if (tnear > tfar)
702 return 0;
703 if (tfar < 0.0)
704 return 0;
705
706 *nr = tnear;
707 *fr = tfar;
708 return 1;
709 }
710