API tools faq
paste
Guest User

cr.c

a guest
Feb 6th, 2021
318
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 18.59 KB | None | 0 0
raw download clone embed print report
  1.  
  2.  
  3.  
  4. /*************************************************************************/
  5. /* */
  6. /* Copyright (c) 1994 Stanford University */
  7. /* */
  8. /* All rights reserved. */
  9. /* */
  10. /* Permission is given to use, copy, and modify this software for any */
  11. /* non-commercial purpose as long as this copyright notice is not */
  12. /* removed. All other uses, including redistribution in whole or in */
  13. /* part, are forbidden without prior written permission. */
  14. /* */
  15. /* This software is provided with absolutely no warranty and no */
  16. /* support. */
  17. /* */
  18. /*************************************************************************/
  19.  
  20.  
  21. /*
  22. * NAME
  23. * cr.c
  24. *
  25. * DESCRIPTION
  26. * This file contains routines that manage the creation of the HU grid
  27. * structures.
  28. *
  29. */
  30.  
  31.  
  32. #include <stdio.h>
  33. #include <math.h>
  34. #include "rt.h"
  35.  
  36.  
  37.  
  38. GRID *gridlist = NULL;
  39.  
  40. /*
  41. Note: gridlist doesn't need to be an array since it is only used when
  42. building HUG, which is done before child process creation
  43. */
  44.  
  45.  
  46.  
  47. /*
  48. * NAME
  49. * prn_gridlist - print HU grid to stdout
  50. *
  51. * SYNOPSIS
  52. * VOID prn_gridlist()
  53. *
  54. * RETURNS
  55. * Nothing.
  56. */
  57.  
  58. VOID prn_gridlist()
  59. {
  60. GRID *g;
  61.  
  62. fprintf(stderr, " Print Gridlist \n");
  63. g = gridlist;
  64.  
  65. while (g != NULL)
  66. {
  67. prn_grid(g);
  68. g = g->next;
  69. }
  70.  
  71. fprintf(stderr, " End Gridlist \n");
  72. }
  73.  
  74.  
  75.  
  76. /*
  77. * NAME
  78. * prn_ds_stats - print HU grid data structure statistics to stdout
  79. *
  80. * SYNOPSIS
  81. * VOID prn_ds_stats()
  82. *
  83. * RETURNS
  84. * Nothing.
  85. */
  86.  
  87. VOID prn_ds_stats()
  88. {
  89. INT leafs;
  90. INT voxels;
  91.  
  92. printf("\n");
  93. printf("****** Hierarchical uniform grid data structure statistics ******\n\n");
  94.  
  95. printf(" Data structure evaluated as a preprocess.\n");
  96.  
  97. printf(" gridsize %3ld \n", hu_gridsize);
  98. printf(" hashtable buckets %3ld \n", hu_numbuckets);
  99. printf(" maximum subdivision level %3ld \n", hu_max_subdiv_level);
  100. printf(" maximum primitives / cell %3ld \n", hu_max_prims_cell);
  101. printf(" grids %3ld \n", grids);
  102.  
  103. voxels = empty_voxels + nonempty_voxels;
  104. leafs = empty_voxels + nonempty_leafs;
  105.  
  106. printf(" empty voxels %8ld %3ld %% \n", empty_voxels, 100*empty_voxels/voxels);
  107. printf(" nonempty voxels %8ld %3ld %% \n", nonempty_voxels, 100*nonempty_voxels/voxels);
  108. printf(" empty leafs %8ld %3ld %% \n", empty_voxels, 100*empty_voxels/leafs);
  109. printf(" nonempty leafs %8ld %3ld %% \n", nonempty_leafs, 100*nonempty_leafs/leafs);
  110. printf(" primitives / leaf %6.1lf \n", (double)prims_in_leafs/leafs);
  111. printf("\n");
  112. }
  113.  
  114.  
  115.  
  116. /*
  117. * NAME
  118. * init_masks - initialize empty and nonempty mask arrays
  119. *
  120. * SYNOPSIS
  121. * VOID init_masks()
  122. *
  123. * RETURNS
  124. * Nothing.
  125. */
  126.  
  127. VOID init_masks()
  128. {
  129. INT n, i;
  130.  
  131. n = sizeof(UINT)*8;
  132.  
  133. for (i = 0; i < n; i++)
  134. {
  135. empty_masks[i] = (MSB >> i);
  136. nonempty_masks[i] = ~empty_masks[i];
  137. }
  138.  
  139. }
  140.  
  141.  
  142. /*
  143. * NAME
  144. * init_world_grid -
  145. *
  146. * SYNOPSIS
  147. * GRID *init_world_grid(v, pepa, num_pe)
  148. * VOXEL *v;
  149. * ELEMENT **pepa; // Prim elements in voxel containing grid.
  150. * INT num_pe; // # of prim elements in voxel containing grid.
  151. *
  152. * RETURNS
  153. * A pointer to the grid.
  154. *
  155. */
  156.  
  157. GRID *init_world_grid(v, pepa, num_pe)
  158. VOXEL *v;
  159. ELEMENT **pepa;
  160. INT num_pe;
  161. {
  162. UINT *ec;
  163. UINT *pc;
  164. BBOX wbox;
  165. GRID *g;
  166. VOXEL **ht;
  167.  
  168. g = ObjectMalloc(OT_GRID, 1);
  169. g->id = grids++;
  170.  
  171. ht = ObjectMalloc(OT_HASHTABLE, 1);
  172.  
  173. g->hashtable = ht;
  174. g->hashtable[0] = v;
  175.  
  176. ec = ObjectMalloc(OT_EMPTYCELLS, 1);
  177.  
  178. g->emptycells = ec;
  179. g->emptycells[0] = 0; /* nonempty */
  180.  
  181. g->indx_inc[0] = 1;
  182. g->indx_inc[1] = 1;
  183. g->indx_inc[2] = 1;
  184. g->num_buckets = 1;
  185.  
  186. wbox.dnear[0] = 0.0;
  187. wbox.dnear[1] = 0.0;
  188. wbox.dnear[2] = 0.0;
  189. wbox.dfar[0] = 1.0;
  190. wbox.dfar[1] = 1.0;
  191. wbox.dfar[2] = 1.0;
  192.  
  193. g->min[0] = wbox.dnear[0];
  194. g->min[1] = wbox.dnear[1];
  195. g->min[2] = wbox.dnear[2];
  196.  
  197. g->cellsize[0] = wbox.dfar[0] - wbox.dnear[0];
  198. g->cellsize[1] = wbox.dfar[1] - wbox.dnear[1];
  199. g->cellsize[2] = wbox.dfar[2] - wbox.dnear[2];
  200.  
  201. g->subdiv_level = - 1;
  202. g->num_prims = num_pe;
  203. g->pepa = pepa;
  204. g->next = NULL;
  205.  
  206. gridlist = g;
  207. return (g);
  208. }
  209.  
  210.  
  211.  
  212. /*
  213. * NAME
  214. * init_world_voxel -
  215. *
  216. * SYNOPSIS
  217. * VOXEL *init_world_voxel(pepa, numelements)
  218. * ELEMENT **pepa;
  219. * INT numelements;
  220. *
  221. * RETURNS
  222. * A pointer to the voxel.
  223. *
  224. */
  225.  
  226. VOXEL *init_world_voxel(pepa, numelements)
  227. ELEMENT **pepa;
  228. INT numelements;
  229. {
  230. VOXEL *v;
  231.  
  232. v = ObjectMalloc(OT_VOXEL, 1);
  233.  
  234. nonempty_voxels++;
  235.  
  236. v->id = 0;
  237. v->cell = (CHAR *)pepa;
  238. v->numelements = numelements;
  239. v->celltype = GSM_VOXEL;
  240. v->next = NULL;
  241.  
  242. return (v);
  243. }
  244.  
  245.  
  246.  
  247. /*
  248. * NAME
  249. * mark_empty - mark grid as being empty
  250. *
  251. * SYNOPSIS
  252. * VOID mark_empty(index1D, g)
  253. * INT index1D;
  254. * GRID *g;
  255. *
  256. * RETURNS
  257. * Nothing.
  258. */
  259.  
  260. VOID mark_empty(index1D, g)
  261. INT index1D;
  262. GRID *g;
  263. {
  264. INT i, r;
  265. UINT w;
  266.  
  267. i = index1D/(sizeof(UINT)*8);
  268. r = index1D - i*sizeof(UINT)*8;
  269.  
  270. w = g->emptycells[i];
  271. w = w | empty_masks[r];
  272. g->emptycells[i] = w;
  273. }
  274.  
  275.  
  276.  
  277. /*
  278. * NAME
  279. * mark_nonempty - mark grid as being nonempty
  280. *
  281. * SYNOPSIS
  282. * VOID mark_nonempty(index1D, g)
  283. * INT index1D;
  284. * GRID *g;
  285. *
  286. * RETURNS
  287. * Nothing.
  288. */
  289.  
  290. VOID mark_nonempty(index1D, g)
  291. INT index1D;
  292. GRID *g;
  293. {
  294. INT i, r;
  295. UINT w;
  296.  
  297. i = index1D/(sizeof(UINT)*8);
  298. r = index1D - i*sizeof(UINT)*8;
  299.  
  300. w = g->emptycells[i];
  301. w = w & nonempty_masks[r];
  302. g->emptycells[i] = w;
  303. }
  304.  
  305.  
  306.  
  307. /*
  308. * NAME
  309. * insert_in_hashtable - insert voxel from grid into hashtable
  310. *
  311. * SYNOPSIS
  312. * VOID insert_in_hashtable(v, g)
  313. * VOXEL *v;
  314. * GRID *g;
  315. *
  316. * RETURNS
  317. * Nothing.
  318. */
  319.  
  320. VOID insert_in_hashtable(v, g)
  321. VOXEL *v;
  322. GRID *g;
  323. {
  324. INT i, r;
  325. VOXEL *vht;
  326.  
  327. i = v->id/hu_numbuckets;
  328. r = v->id - i*hu_numbuckets;
  329.  
  330. vht = g->hashtable[r];
  331. v->next = vht;
  332. g->hashtable[r] = v;
  333. }
  334.  
  335.  
  336. /*
  337. * NAME
  338. * **prims_in_box2 -
  339. *
  340. * SYNOPSIS
  341. * ELEMENT **prims_in_box2(pepa, n_in, b, n)
  342. * ELEMENT **pepa; // Array of element ptrs to check.
  343. * INT n_in; // Number of elements in array.
  344. * BBOX b; // Bounding box to check.
  345. * INT *n; // Number of elements in the box.
  346. *
  347. * RETURNS
  348. * An array of PrimElement pointers for those primitive elements in the
  349. * bounding box.
  350. */
  351.  
  352. ELEMENT **prims_in_box2(pepa, n_in, b, n)
  353. ELEMENT **pepa;
  354. INT n_in;
  355. BBOX b;
  356. INT *n;
  357. {
  358. INT ovlap, i, j, k;
  359. ELEMENT *pe;
  360. ELEMENT **npepa;
  361. BBOX bb;
  362. REAL max, side, eps;
  363.  
  364. max = b.dfar[0] - b.dnear[0];
  365. side = b.dfar[1] - b.dnear[1];
  366.  
  367. max = max > side ? max : side;
  368. side = b.dfar[2] - b.dnear[2];
  369.  
  370. max = max > side ? max : side;
  371. eps = max * 1.0E-6;
  372.  
  373. if (n_in > 0)
  374. npepa = ObjectMalloc(OT_PEPARRAY, n_in);
  375. else
  376. {
  377. npepa == NULL;
  378. *n = 0;
  379. return (npepa);
  380. }
  381.  
  382. *n = 0;
  383. k = 0;
  384.  
  385. for (j = 0; j < n_in; j++)
  386. {
  387. pe = pepa[j];
  388. bb = pe->bv;
  389. ovlap = 1;
  390.  
  391. for (i = 0; i < 1; i++)
  392. {
  393. if (b.dnear[0] > bb.dfar[0] + eps)
  394. {
  395. ovlap = 0;
  396. break;
  397. }
  398.  
  399. if (b.dnear[1] > bb.dfar[1] + eps)
  400. {
  401. ovlap = 0;
  402. break;
  403. }
  404.  
  405. if (b.dnear[2] > bb.dfar[2] + eps)
  406. {
  407. ovlap = 0;
  408. break;
  409. }
  410.  
  411. if (b.dfar[0] < bb.dnear[0] - eps)
  412. {
  413. ovlap = 0;
  414. break;
  415. }
  416.  
  417. if (b.dfar[1] < bb.dnear[1] - eps)
  418. {
  419. ovlap = 0;
  420. break;
  421. }
  422.  
  423. if (b.dfar[2] < bb.dnear[2] - eps)
  424. {
  425. ovlap = 0;
  426. break;
  427. }
  428. }
  429.  
  430. if (ovlap == 1)
  431. {
  432. npepa[k++] = pepa[j];
  433. (*n)++;
  434. }
  435. }
  436.  
  437. return (npepa);
  438. }
  439.  
  440.  
  441.  
  442. /*
  443. * NAME
  444. * init_bintree - initialize (create) rootnode of bintree
  445. *
  446. * SYNOPSIS
  447. * BTNODE *init_bintree(ng)
  448. * GRID *ng;
  449. *
  450. * RETURNS
  451. * A pointer to the newly created bintree root.
  452. *
  453. */
  454.  
  455. BTNODE *init_bintree(ng)
  456. GRID *ng;
  457. {
  458. BTNODE *btn;
  459. ELEMENT **pepa;
  460.  
  461. btn = ObjectMalloc(OT_BINTREE, 1);
  462.  
  463. btn->btn[0] = NULL;
  464. btn->btn[1] = NULL;
  465. btn->axis = -1;
  466.  
  467. btn->p[0] = ng->min[0];
  468. btn->p[1] = ng->min[1];
  469. btn->p[2] = ng->min[2];
  470.  
  471. btn->n[0] = ng->indx_inc[1];
  472. btn->n[1] = ng->indx_inc[1];
  473. btn->n[2] = ng->indx_inc[1];
  474.  
  475. btn->i[0] = 0;
  476. btn->i[1] = 0;
  477. btn->i[2] = 0;
  478.  
  479. btn->nprims = ng->num_prims;
  480. btn->totalPrimsAllocated = btn->nprims;
  481.  
  482. if (ng->num_prims > 0)
  483. btn->pe = ng->pepa;
  484. else
  485. btn->pe = NULL;
  486.  
  487. return (btn);
  488. }
  489.  
  490.  
  491. /*
  492. * NAME
  493. * subdiv_bintree
  494. *
  495. * SYNOPSIS
  496. * VOID subdiv_bintree(btn, g)
  497. * BTNODE *btn; // Current bintree node.
  498. * GRID *g; // Grid being created.
  499. *
  500. * DESCRIPTION
  501. * The bintree node is subdivided at the largest dimension and the
  502. * primitive element list is pruned to the two new nodes.
  503. *
  504. * RETURNS
  505. * Nothing.
  506. *
  507. */
  508.  
  509. VOID subdiv_bintree(btn, g)
  510. BTNODE *btn;
  511. GRID *g;
  512. {
  513. BTNODE *btn1, *btn2;
  514. INT n1, n2, imax, dmax;
  515. BBOX b1, b2;
  516.  
  517. /* Find largest dimension. */
  518.  
  519. imax = 0;
  520. dmax = btn->n[0];
  521.  
  522. if (dmax < btn->n[1])
  523. {
  524. imax = 1;
  525. dmax = btn->n[1];
  526. }
  527.  
  528. if (dmax < btn->n[2])
  529. {
  530. imax = 2;
  531. dmax = btn->n[2];
  532. }
  533.  
  534. /* Subdiv largest dimension. */
  535.  
  536. btn->axis = imax;
  537. btn->btn[0] = NULL;
  538. btn->btn[1] = NULL;
  539.  
  540. if (btn->n[imax] > 1)
  541. {
  542. n1 = btn->n[imax] / 2;
  543. n2 = btn->n[imax] - n1;
  544.  
  545. btn1 = ObjectMalloc(OT_BINTREE, 1);
  546. btn2 = ObjectMalloc(OT_BINTREE, 1);
  547.  
  548. btn->btn[0] = btn1;
  549. btn->btn[1] = btn2;
  550.  
  551. btn1->btn[0] = NULL;
  552. btn1->btn[1] = NULL;
  553. btn1->axis = -1;
  554.  
  555. btn2->btn[0] = NULL;
  556. btn2->btn[1] = NULL;
  557. btn2->axis = -1;
  558.  
  559. btn1->i[0] = btn->i[0];
  560. btn1->i[1] = btn->i[1];
  561. btn1->i[2] = btn->i[2];
  562.  
  563. btn2->i[0] = btn->i[0];
  564. btn2->i[1] = btn->i[1];
  565. btn2->i[2] = btn->i[2];
  566. btn2->i[imax] += n1;
  567.  
  568. btn1->n[0] = btn->n[0];
  569. btn1->n[1] = btn->n[1];
  570. btn1->n[2] = btn->n[2];
  571. btn1->n[imax] = n1;
  572.  
  573. btn2->n[0] = btn->n[0];
  574. btn2->n[1] = btn->n[1];
  575. btn2->n[2] = btn->n[2];
  576. btn2->n[imax] = n2;
  577.  
  578. btn1->p[0] = btn->p[0];
  579. btn1->p[1] = btn->p[1];
  580. btn1->p[2] = btn->p[2];
  581.  
  582. btn2->p[0] = btn->p[0];
  583. btn2->p[1] = btn->p[1];
  584. btn2->p[2] = btn->p[2];
  585. btn2->p[imax] = btn->p[imax] + n1 * g->cellsize[imax];
  586.  
  587. b1.dnear[0] = btn1->p[0];
  588. b1.dnear[1] = btn1->p[1];
  589. b1.dnear[2] = btn1->p[2];
  590. b1.dfar[0] = btn1->p[0] + btn1->n[0] * g->cellsize[0];
  591. b1.dfar[1] = btn1->p[1] + btn1->n[1] * g->cellsize[1];
  592. b1.dfar[2] = btn1->p[2] + btn1->n[2] * g->cellsize[2];
  593.  
  594. btn1->pe = prims_in_box2(btn->pe, btn->nprims, b1, &(btn1->nprims));
  595. btn1->totalPrimsAllocated = btn->nprims;
  596.  
  597. b2.dnear[0] = btn2->p[0];
  598. b2.dnear[1] = btn2->p[1];
  599. b2.dnear[2] = btn2->p[2];
  600. b2.dfar[0] = btn2->p[0] + btn2->n[0] * g->cellsize[0];
  601. b2.dfar[1] = btn2->p[1] + btn2->n[1] * g->cellsize[1];
  602. b2.dfar[2] = btn2->p[2] + btn2->n[2] * g->cellsize[2];
  603.  
  604. btn2->pe = prims_in_box2(btn->pe, btn->nprims, b2, &(btn2->nprims));
  605. btn2->totalPrimsAllocated = btn->nprims;
  606.  
  607. }
  608.  
  609. if (btn1->n[0] == 1 && btn1->n[1] == 1 && btn1->n[2] == 1)
  610. {
  611. /* further optimize the pe so no space is wasted !! */
  612. }
  613.  
  614. if (btn2->n[0] == 1 && btn2->n[1] == 1 && btn2->n[2] == 1)
  615. {
  616. /* further optimize the pe so no space is wasted !! */
  617. }
  618. }
  619.  
  620.  
  621.  
  622. /*
  623. * NAME
  624. * create_bintree - subdivide tree until all leaf nodes have gridsizes of
  625. * (1, 1, 1).
  626. *
  627. * SYNOPSIS
  628. * VOID create_bintree(root , g)
  629. * BTNODE *root; // Root of bintree.
  630. * GRID *g; // Grid being created.
  631. *
  632. * RETURNS
  633. * Nothing.
  634. */
  635.  
  636. VOID create_bintree(root , g)
  637. BTNODE *root;
  638. GRID *g;
  639. {
  640. BTNODE *btn;
  641.  
  642. /* It is assumed that root's children are NULL on entry. */
  643.  
  644. btn = root;
  645. if (btn->n[0] != 1 || btn->n[1] != 1 || btn->n[2] != 1)
  646. {
  647. subdiv_bintree(btn, g);
  648. create_bintree(btn->btn[0], g);
  649. create_bintree(btn->btn[1], g);
  650.  
  651. if ((btn->nprims) > 0)
  652. {
  653. /* ObjectFree(OT_PEPARRAY, btn->totalPrimsAllocated, btn->pe);
  654. btn->pe = NULL; */
  655. }
  656. }
  657. }
  658.  
  659.  
  660.  
  661. /*
  662. * NAME
  663. * bintree_lookup -
  664. *
  665. * SYNOPSIS
  666. * ELEMENT **bintree_lookup(root, i, j, k, g, n)
  667. * BTNODE *root; // Root of bintree.
  668. * INT i, j, k; // 3D indecies of cell in grid.
  669. * GRID *g; // Grid for this bintree.
  670. * INT *n; // # prims.
  671. *
  672. * DESCRIPTION
  673. * Receive the 3D indices of the cell in the grid and return a pointer to
  674. * an array of elments and the number of elements on the list.
  675. *
  676. * RETURNS
  677. * An array of elements associated with the voxel
  678. *
  679. */
  680.  
  681. ELEMENT **bintree_lookup(root, i, j, k, g, n)
  682. BTNODE *root;
  683. INT i, j, k;
  684. GRID *g;
  685. INT *n;
  686. {
  687. INT l,x;
  688. INT ijk[3];
  689. INT child;
  690. INT idiv;
  691. ELEMENT **pepa;
  692. BTNODE *btn;
  693.  
  694. ijk[0] = i;
  695. ijk[1] = j;
  696. ijk[2] = k;
  697.  
  698. btn = root;
  699.  
  700. if (btn == NULL)
  701. {
  702. *n = 0;
  703. return (NULL);
  704. }
  705.  
  706. while (btn->n[0] != 1 || btn->n[1] != 1 || btn->n[2] != 1)
  707. {
  708. if (btn->axis == - 1)
  709. {
  710. /* Not a leaf & not subdivided but should be subdivided. */
  711.  
  712. fprintf(stderr, "bintree_lookup: gridsizes (%ld, %ld, %ld), axis %ld & nprims %ld\n",
  713. btn->n[0], btn->n[1], btn->n[2], btn->axis, btn->nprims);
  714.  
  715. exit(-1);
  716. }
  717.  
  718. /* Descend the tree: find which branch. */
  719.  
  720. child = 0;
  721. idiv = (btn->n[btn->axis]/2);
  722.  
  723. if (ijk[btn->axis] + 1 > idiv)
  724. {
  725. child = 1;
  726. ijk[btn->axis] -= idiv;
  727. }
  728.  
  729. /* Child is now the correct branch. */
  730.  
  731. btn = btn->btn[child];
  732. if (btn == NULL)
  733. {
  734. *n = 0;
  735. return (NULL);
  736. }
  737. }
  738.  
  739. /* Now at a leaf. */
  740.  
  741. *n = btn->nprims;
  742. pepa = btn->pe;
  743.  
  744. /* if (btn->nprims == btn->totalPrimsAllocated)
  745. pepa = btn->pe;
  746. else
  747. {
  748. if (btn->pe)
  749. pepa = GlobalRealloc(btn->pe, btn->nprims*sizeof(ELEMENT *));
  750. else
  751. pepa = NULL;
  752.  
  753.  
  754. pepa = ObjectMalloc(OT_PEPARRAY, btn->nprims);
  755. for (x = 0; x < btn->nprims; x++)
  756. pepa[x] = btn->pe[x];
  757.  
  758. ObjectFree(OT_PEPARRAY, btn->totalPrimsAllocated, btn->pe);
  759. btn->pe = NULL;
  760. }
  761. */
  762. return (pepa);
  763. }
  764.  
  765.  
  766.  
  767. /*
  768. * NAME
  769. * deleteBinTree - delete the entire bintree and free its memory
  770. *
  771. * SYNOPSIS
  772. * VOID deleteBinTree(binTree)
  773. * BTNODE *binTree;
  774. *
  775. * DESCRIPTION
  776. * Delete the entire bintree by recursively calling this procedure.
  777. *
  778. * RETURNS
  779. * Nothing.
  780. */
  781.  
  782. VOID deleteBinTree(binTree)
  783. BTNODE *binTree;
  784. {
  785. BTNODE *left, *right;
  786.  
  787. if (binTree != NULL)
  788. {
  789. left = binTree->btn[0];
  790. right = binTree->btn[1];
  791.  
  792. deleteBinTree(left);
  793. deleteBinTree(right);
  794. /* ObjectFree(OT_BINTREE, 1, binTree); */
  795. }
  796. }
  797.  
  798.  
  799.  
  800. /*
  801. * NAME
  802. * create_grid -
  803. *
  804. * SYNOPSIS
  805. * GRID *create_grid(v, g, num_prims)
  806. * VOXEL *v;
  807. * GRID *g;
  808. * INT num_prims; // # of prim elem in voxel to be subdivided.
  809. *
  810. * DESCRIPTION
  811. *
  812. * Accept a voxel with an ELEMENT array and a grid and recursively
  813. * uniformly subdivide the voxel to produce a new grid. Create a
  814. * new list of prim elements pruned to each new voxel. If the
  815. * list is non NULL create a voxel for it.
  816. *
  817. * In all cases:
  818. *
  819. * Place a pointer to the new grid in the input voxel and mark
  820. * the celltype as GSM_GRID. Return a pointer to the new grid.
  821. * Link all new grids on to the list gridlist for debug purposes.
  822. *
  823. * RETURNS
  824. * A pointer to the grid.
  825. */
  826.  
  827. GRID *create_grid(v, g, num_prims)
  828. VOXEL *v;
  829. GRID *g;
  830. INT num_prims;
  831. {
  832. INT n;
  833. INT i, j, k, r;
  834. INT nprims;
  835. INT index1D;
  836. UINT *ec;
  837. UINT *pc;
  838. R64 nec, unsgn, ncells;
  839. GRID *ng, *nng; /* New grid. */
  840. BBOX b;
  841. VOXEL *nv;
  842. VOXEL **ht;
  843. BTNODE *bintree;
  844. ELEMENT **pepa;
  845.  
  846. ng = ObjectMalloc(OT_GRID, 1);
  847. ng->id = grids++;
  848.  
  849. ht = ObjectMalloc(OT_HASHTABLE, hu_numbuckets);
  850. ng->hashtable = ht;
  851.  
  852. ncells = (R64)(hu_gridsize * hu_gridsize * hu_gridsize);
  853. total_cells += ncells;
  854.  
  855. ec = ObjectMalloc(OT_EMPTYCELLS, (INT)ncells);
  856. ng->emptycells = ec;
  857.  
  858. ng->num_prims = num_prims;
  859. ng->pepa = (ELEMENT**)v->cell;
  860. ng->indx_inc[0] = 1;
  861. ng->indx_inc[1] = hu_gridsize;
  862. ng->indx_inc[2] = hu_gridsize * hu_gridsize;
  863. ng->num_buckets = hu_numbuckets;
  864.  
  865. k = v->id/g->indx_inc[2];
  866. r = v->id - k*g->indx_inc[2];
  867. j = r/g->indx_inc[1];
  868. i = r - j*g->indx_inc[1];
  869.  
  870. ng->min[0] = g->min[0] + i * g->cellsize[0];
  871. ng->min[1] = g->min[1] + j * g->cellsize[1];
  872. ng->min[2] = g->min[2] + k * g->cellsize[2];
  873.  
  874. ng->cellsize[0] = g->cellsize[0]/ng->indx_inc[1];
  875. ng->cellsize[1] = g->cellsize[1]/ng->indx_inc[1];
  876. ng->cellsize[2] = g->cellsize[2]/ng->indx_inc[1];
  877. ng->subdiv_level = g->subdiv_level + 1;
  878. ng->next = gridlist;
  879.  
  880. gridlist = ng;
  881.  
  882. /* Calculate hierarchical grid */
  883.  
  884. /* First create bintree. */
  885.  
  886. bintree = init_bintree(ng);
  887. create_bintree(bintree, ng);
  888.  
  889. index1D = 0;
  890. n = hu_gridsize;
  891.  
  892. /*
  893. * For each cell in new grid, create an ELEMENT array for the
  894. * cell; if non empty create a voxel for it. If nonempty
  895. * cell has more than MAX_PRIMS_PER_CELL (hu_max_prims_cell) primitives and
  896. * MAX_SUBDIV_LEVEL (hu_max_subdiv_level) has not been reached, create a
  897. * new grid (i.e. subdivide) and insert it in the hashtable. If nonempty
  898. * cell has less than MAX_PRIMS_PER_CELL insert it in the
  899. * hashtable. In any case make the appropriate entry in
  900. * emptycells.
  901. */
  902.  
  903. for (k = 0; k < n; k++)
  904. {
  905. for (j = 0; j < n; j++)
  906. {
  907. for (i = 0; i < n; i++)
  908. {
  909. pepa = bintree_lookup(bintree, i, j, k, ng, &nprims);
  910.  
  911. if (pepa != NULL)
  912. {
  913. nonempty_voxels++;
  914. mark_nonempty(index1D, ng);
  915.  
  916. nv = ObjectMalloc(OT_VOXEL, 1);
  917.  
  918. nv->id = index1D;
  919. nv->celltype = GSM_VOXEL;
  920. nv->cell = (CHAR*)pepa;
  921. nv->numelements = nprims;
  922.  
  923. if (nprims > hu_max_prims_cell && ng->subdiv_level < hu_max_subdiv_level)
  924. nng = create_grid(nv, ng, nprims);
  925. else
  926. {
  927. /* Leaf cell. */
  928.  
  929. nonempty_leafs++;
  930. prims_in_leafs += nprims;
  931. }
  932.  
  933. insert_in_hashtable(nv, ng);
  934. }
  935. else
  936. {
  937. /* Empty cell. */
  938.  
  939. empty_voxels++;
  940. mark_empty(index1D, ng);
  941. }
  942.  
  943. index1D++;
  944. }
  945. }
  946. }
  947.  
  948. /* Store new grid ptr in input voxel. */
  949.  
  950. v->cell = (CHAR *)ng;
  951. v->numelements = -1; /* this field doesn't make sence if cell is a GRID */
  952. v->celltype = GSM_GRID;
  953.  
  954. deleteBinTree(bintree);
  955.  
  956. return (ng);
  957. }
  958.  
  959.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!