home *** CD-ROM | disk | FTP | other *** search
/ Mega Top 1 / os2_top1.zip / os2_top1 / APPS / RAYTRACE / POV22F / SOURCE / HFIELD.C < prev    next >
C/C++ Source or Header  |  1994-01-28  |  48KB  |  1,834 lines
  1. /****************************************************************************
  2. *                   hfield.c
  3. *
  4. *    This file implements the height field shape primitive.  The shape is
  5. *    implemented as a collection of triangles which are calculated as
  6. *    needed.  The basic intersection routine first computes the rays
  7. *    intersection with the box marking the limits of the shape, then
  8. *    follows the line from one intersection point to the other, testing the
  9. *    two triangles which form the pixel for an intersection with the ray at
  10. *    each step.
  11. *        height field added by Doug Muir
  12. *        with lots of advice and support from David Buck 
  13. *            and Drew Wells.
  14. *
  15. *  from Persistence of Vision Raytracer
  16. *  Copyright 1993 Persistence of Vision Team
  17. *---------------------------------------------------------------------------
  18. *  NOTICE: This source code file is provided so that users may experiment
  19. *  with enhancements to POV-Ray and to port the software to platforms other 
  20. *  than those supported by the POV-Ray Team.  There are strict rules under
  21. *  which you are permitted to use this file.  The rules are in the file
  22. *  named POVLEGAL.DOC which should be distributed with this file. If 
  23. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  24. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  25. *  Forum.  The latest version of POV-Ray may be found there as well.
  26. *
  27. * This program is based on the popular DKB raytracer version 2.12.
  28. * DKBTrace was originally written by David K. Buck.
  29. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  30. *
  31. *****************************************************************************/
  32.  
  33. #include "frame.h"
  34. #include "vector.h"
  35. #include "povproto.h"
  36.  
  37. #define sign(x) (((x) > 0.0) ? 1: (((x) < 0.0) ? -1: 0))
  38.  
  39. #ifndef min_value
  40. #define min_value(x,y) ((x) > (y) ? (y) : (x))
  41. #endif
  42. #ifndef max_value
  43. #define max_value(x,y) ((x) < (y) ? (y) : (x))
  44. #endif
  45.  
  46. METHODS Height_Field_Methods = 
  47.   {
  48.   All_HeightFld_Intersections,
  49.   Inside_HeightFld, HeightFld_Normal,
  50.   Copy_HeightFld,    Translate_HeightFld, Rotate_HeightFld,
  51.   Scale_HeightFld, Transform_HeightFld, Invert_HeightFld,Destroy_HeightFld
  52. };
  53.  
  54. METHODS Csg_Height_Field_Methods = 
  55.   {
  56.   All_Csg_HeightFld_Intersections,
  57.   Inside_HeightFld, HeightFld_Normal,
  58.   Copy_HeightFld,
  59.   Translate_HeightFld, Rotate_HeightFld,
  60.   Scale_HeightFld, Transform_HeightFld, Invert_HeightFld,Destroy_HeightFld
  61. };
  62.  
  63. extern long Ray_Ht_Field_Tests, Ray_Ht_Field_Tests_Succeeded;
  64. extern long Ray_Ht_Field_Box_Tests, Ray_HField_Box_Tests_Succeeded;
  65. extern int Options;
  66.  
  67. int isdx, isdz, X_Dom;
  68. DBL Gdx, Gdy, Gdz, Block_Size, Inv_Blk_Size;
  69. DBL Myx, Mxz, Mzx, Myz;
  70. ISTACK *Hf_Stack;
  71. RAY *RRay;
  72. DBL mindist, maxdist;
  73.  
  74. #define Get_Height(x, z, H_Field) ((DBL)(H_Field)->Map[(z)][(x)])
  75.  
  76. static DBL Normalize PARAMS(( VECTOR *A, VECTOR *B ));
  77. static DBL stretch PARAMS((DBL x));
  78. static int Intersect_Csg_Sub_Block PARAMS((HF_BLOCK *Block, RAY *Ray,
  79. HEIGHT_FIELD *H_Field, VECTOR *start, VECTOR *end));
  80. static int Intersect_Csg_Hf_Node PARAMS((RAY *Ray, HEIGHT_FIELD *H_Field,
  81. VECTOR *start, VECTOR *end));
  82. static DBL Normalize PARAMS(( VECTOR *A, VECTOR *B ));
  83. static int add_single_normal PARAMS((HF_val **data, int xsize, int zsize,
  84. int x0, int z0,int x1, int z1,int x2, int z2,VECTOR *N));
  85. static void smooth_height_field PARAMS((HEIGHT_FIELD *hf, int xsize, int zsize));
  86.  
  87. static DBL
  88. Normalize(A, B)
  89. VECTOR *A, *B;
  90.   {
  91.   DBL VTemp = sqrt(B->x * B->x + B->y * B->y + B->z * B->z);
  92.   if (fabs(VTemp) > EPSILON) 
  93.     {
  94.     A->x = B->x / VTemp;
  95.     A->y = B->y / VTemp;
  96.     A->z = B->z / VTemp;
  97.     }
  98.   else 
  99.     {
  100.     A->x = 0.0;
  101.     A->y = 1.0;
  102.     A->z = 0.0;
  103.     }
  104.   return VTemp;
  105.   }
  106.  
  107.   int Intersect_Pixel(x, z, Ray, H_Field, height1, height2)
  108.     int x;
  109. int z;
  110. RAY *Ray;
  111. HEIGHT_FIELD *H_Field;
  112. DBL height1;
  113. DBL height2;
  114.   {
  115.   VECTOR T1V1,T1V2,T1V3,T2V1,T2V2,T2V3,Local_Normal,N1;
  116.   DBL pos1,pos2,dot,depth1,depth2,s,t,y1,y2,y3,y4;
  117.   DBL max_height, min_height;
  118.   int Found = FALSE;
  119.  
  120.   y1 = Get_Height(x,z,H_Field);
  121.   y2 = Get_Height(x+1,z,H_Field);
  122.   y3 = Get_Height(x,z+1,H_Field);
  123.   y4 = Get_Height(x+1,z+1,H_Field);
  124.  
  125.   Make_Vector(&T1V1,(DBL)x,y1,(DBL)z);
  126.   Make_Vector(&T1V2,1.0,y2-y1,0.0);
  127.   Make_Vector(&T1V3,0.0,y3-y1,1.0);
  128.   Make_Vector(&T2V1,(DBL)(x+1),y4,(DBL)(z+1));
  129.   Make_Vector(&T2V2,-1.0,y3-y4,0.0);
  130.   Make_Vector(&T2V3,0.0,y2-y4,-1.0);
  131.  
  132.   /*
  133.      * first, we check to see if it is even possible for the ray to
  134.      * intersect the triangle.
  135.      */
  136.  
  137.   max_height = max_value(y1,max_value(y2,y3));
  138.   min_height = min_value(y1,min_value(y2,y3));
  139.   if((max_height >= height1) && (min_height <= height2))
  140.     {
  141.     VCross(Local_Normal,T1V3,T1V2);
  142.     VDot(dot,Local_Normal,Ray->Direction);
  143.  
  144.     if((dot > EPSILON) || (dot < -EPSILON))
  145.       {
  146.       VDot(pos1,Local_Normal,T1V1);
  147.       VDot(pos2,Local_Normal,Ray->Initial);
  148.  
  149.       pos1 -= pos2;
  150.  
  151.       depth1 = pos1 / dot;
  152.  
  153.       if((depth1 >= mindist) && (depth1 <= maxdist)) 
  154.         {
  155.         s = Ray->Initial.x+(depth1*Ray->Direction.x)-(DBL)x;
  156.         t = Ray->Initial.z+(depth1*Ray->Direction.z)-(DBL)z;
  157.  
  158.         if((s>=-0.0001) && (t>=-0.0001) && ((s+t)<=1.0001)) 
  159.           {
  160.           if (!H_Field->Smoothed) 
  161.             {
  162.             N1 = Local_Normal;
  163.             if (H_Field->cache_pos < HF_CACHE_SIZE) 
  164.               {
  165.               H_Field->Normal_Vector[H_Field->cache_pos].normal = N1;
  166.               H_Field->Normal_Vector[H_Field->cache_pos].x = x + s;
  167.               H_Field->Normal_Vector[H_Field->cache_pos].z = z + t;
  168.               H_Field->cache_pos += 1;
  169.               }
  170.             }
  171.  
  172.           VScale (T1V1, RRay -> Direction, depth1);
  173.           VAddEq (T1V1, RRay -> Initial);
  174.           if (Point_In_Clip (&T1V1, H_Field->Clip))
  175.             {
  176.             push_entry(depth1,T1V1,(OBJECT *)H_Field,Hf_Stack);
  177.             Found = TRUE;
  178.             Ray_Ht_Field_Tests_Succeeded++;
  179.             }
  180.           }
  181.         }
  182.       }
  183.     }
  184.  
  185.   /*
  186.      * first, we check to see if it is even possible for the ray to
  187.      * intersect the triangle.
  188.        Rewritten to get around Code Builder FP stack problem.
  189.        Original code:
  190.               if((max_value(y4,max_value(y2,y3)) >= height1) && 
  191.           (min_value(y4,min_value(y2,y3)) <= height2))            */
  192.  
  193.   max_height = max_value(y4,max_value(y2,y3));
  194.   min_height = min_value(y4,min_value(y2,y3));
  195.   if((max_height >= height1) && (min_height <= height2))
  196.     {
  197.     VCross(Local_Normal,T2V3,T2V2);
  198.     VDot(dot,Local_Normal,Ray->Direction);
  199.  
  200.     if((dot > EPSILON) || (dot < -EPSILON))
  201.       {
  202.       VDot(pos1,Local_Normal,T2V1);
  203.  
  204.       VDot(pos2,Local_Normal,Ray->Initial);
  205.       pos1 -= pos2;
  206.  
  207.       depth2 = pos1 / dot;
  208.  
  209.       if((depth2 >=mindist) && (depth2 <=maxdist))
  210.         {
  211.         s = Ray->Initial.x+(depth2*Ray->Direction.x)-(DBL)x;
  212.         t = Ray->Initial.z+(depth2*Ray->Direction.z)-(DBL)z;
  213.  
  214.         if((s<=1.0001) && (t<=1.0001) && ((s+t)>0.9999)) 
  215.           {
  216.           if (!H_Field->Smoothed) 
  217.             {
  218.             N1 = Local_Normal;
  219.             if (H_Field->cache_pos < HF_CACHE_SIZE) 
  220.               {
  221.               H_Field->Normal_Vector[H_Field->cache_pos].normal = N1;
  222.               H_Field->Normal_Vector[H_Field->cache_pos].x = x + s;
  223.               H_Field->Normal_Vector[H_Field->cache_pos].z = z + t;
  224.               H_Field->cache_pos += 1;
  225.               }
  226.             }
  227.  
  228.           VScale (T1V1, RRay -> Direction, depth2);
  229.           VAddEq (T1V1, RRay -> Initial);
  230.           if (Point_In_Clip (&T1V1, H_Field->Clip))
  231.             {
  232.             push_entry(depth2,T1V1,(OBJECT *)H_Field,Hf_Stack);
  233.             Found = TRUE;
  234.             Ray_Ht_Field_Tests_Succeeded++;
  235.             }
  236.           }
  237.         }
  238.       }
  239.     }
  240.  
  241.   return(Found);
  242.   }
  243.  
  244. int Intersect_Sub_Block(Block, Ray, H_Field, start, end)
  245. HF_BLOCK *Block;
  246. RAY *Ray;
  247. HEIGHT_FIELD *H_Field;
  248. VECTOR *start, *end;
  249.   {
  250.   DBL y1, y2;
  251.   DBL sx, sy, sz, ex, ez, f, tx, tz;
  252.   int ix, iz, length, i;
  253.  
  254.   if(min_value(start->y,end->y) > (DBL)Block->max_y)
  255.     return(FALSE);
  256.  
  257.   if(max_value(start->y,end->y) < (DBL)Block->min_y)
  258.     return(FALSE);
  259.  
  260.   sx = start->x;
  261.   ex = end->x;
  262.   sz = start->z;
  263.   ez = end->z;
  264.   sy = start->y;
  265.  
  266.   if(X_Dom) 
  267.     {
  268.     if(isdx >= 0) 
  269.       {
  270.       f = floor(sx) - sx;
  271.       sx = floor(sx);
  272.       sy += Myx * f;
  273.       sz += Mzx * f;
  274.       ex = ceil(ex) - 1.0;
  275.       ix = (int)sx;
  276.       }
  277.     else 
  278.       {
  279.       f = ceil(sx) - sx;
  280.       sx = ceil(sx) - 1.0;
  281.       sy += Myx * f;
  282.       sz += Mzx * f;
  283.       ex = floor(ex);
  284.       ix = (int)sx;
  285.       }
  286.  
  287.       length = (int)abs((int)ex - (int)sx);
  288.  
  289.     if (isdz >= 0) 
  290.       {
  291.       tz = floor(start->z) + 1.0;
  292.       iz = (int)start->z;
  293.       f = sz - tz;
  294.       }
  295.     else 
  296.       {
  297.       tz = ceil(start->z) - 1.0;
  298.       iz = (int)tz;
  299.       f = tz - sz;
  300.       }
  301.  
  302.       if(Gdy >= 0.0) 
  303.       {
  304.       y1 = sy;
  305.       y2 = sy + Gdy;
  306.       }
  307.       else 
  308.       {
  309.       y1 = sy + Gdy;
  310.       y2 = sy;
  311.       }
  312.  
  313.       for(i=0;i<=length;i++) 
  314.       {
  315.       if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  316.         return(TRUE);
  317.       f += Gdz;
  318.       if(f>0.0) 
  319.         {
  320.         iz += isdz;
  321.         if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  322.           return(TRUE);
  323.         f -= 1.0;
  324.         }
  325.       ix += isdx;
  326.       y1 += Gdy;
  327.       y2 += Gdy;
  328.       }
  329.     }
  330.   else 
  331.     {
  332.     if(isdz >= 0) 
  333.       {
  334.       f = floor(sz) - sz;
  335.       sz = floor(sz);
  336.       sy += Myz * f;
  337.       sx += Mxz * f;
  338.       ez = ceil(ez) - 1.0;
  339.       iz = (int)sz;
  340.       }
  341.     else 
  342.       {
  343.       f = ceil(sz) - sz;
  344.       sz = ceil(sz) - 1.0;
  345.       sy += Myz * f;
  346.       sx += Mxz * f;
  347.       ez = floor(ez);
  348.       iz = (int)sz;
  349.       }             
  350.  
  351.       length = (int)abs((int)ez - (int)sz);
  352.  
  353.     if (isdx >= 0) 
  354.       {
  355.       tx = floor(start->x) + 1.0;
  356.       ix = (int)start->x;
  357.       f = sx - tx;
  358.       }
  359.     else 
  360.       {
  361.       tx = ceil(start->x) - 1.0;
  362.       ix = (int)tx;
  363.       f = tx - sx;
  364.       }
  365.  
  366.       if(Gdy >= 0.0) 
  367.       {
  368.       y1 = sy;
  369.       y2 = sy + Gdy;
  370.       }
  371.       else 
  372.       {
  373.       y1 = sy + Gdy;
  374.       y2 = sy;
  375.       }
  376.  
  377.       for(i=0;i<=length;i++) 
  378.       {
  379.       if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  380.         return(TRUE);
  381.       f += Gdx;
  382.       if(f>0.0) 
  383.         {
  384.         ix += isdx;
  385.         if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  386.           return(TRUE);
  387.         f -= 1.0;
  388.         }
  389.       iz += isdz;
  390.       y1 += Gdy;
  391.       y2 += Gdy;
  392.       }
  393.     }
  394.   return (FALSE);
  395.   }
  396.  
  397. static int Intersect_Csg_Sub_Block(Block, Ray, H_Field, start, end)
  398. HF_BLOCK *Block;
  399. RAY *Ray;
  400. HEIGHT_FIELD *H_Field;
  401. VECTOR *start, *end;
  402.   {
  403.   DBL y1, y2;
  404.   DBL sx, sy, sz, ex, ez, f, tx, tz;
  405.   int ix, iz, length, i, retval;
  406.  
  407.   if(min_value(start->y,end->y) > (DBL)Block->max_y)
  408.     return(FALSE);
  409.  
  410.   if(max_value(start->y,end->y) < (DBL)Block->min_y)
  411.     return(FALSE);
  412.  
  413.   retval = FALSE;
  414.   sx = start->x;
  415.   ex = end->x;
  416.   sz = start->z;
  417.   ez = end->z;
  418.   sy = start->y;
  419.  
  420.   if(X_Dom) 
  421.     {
  422.     if(isdx >= 0) 
  423.       {
  424.       f = floor(sx) - sx;
  425.       sx = floor(sx);
  426.       sy += Myx * f;
  427.       sz += Mzx * f;
  428.       ex = ceil(ex) - 1.0;
  429.       ix = (int)sx;
  430.       }
  431.     else 
  432.       {
  433.       f = ceil(sx) - sx;
  434.       sx = ceil(sx) - 1.0;
  435.       sy += Myx * f;
  436.       sz += Mzx * f;
  437.       ex = floor(ex);
  438.       ix = (int)sx;
  439.       }
  440.  
  441.       length = (int) abs((int)ex - (int)sx);
  442.  
  443.     if (isdz >= 0) 
  444.       {
  445.       tz = floor(start->z) + 1.0;
  446.       iz = (int)start->z;
  447.       f = sz - tz;
  448.       }
  449.     else 
  450.       {
  451.       tz = ceil(start->z) - 1.0;
  452.       iz = (int)tz;
  453.       f = tz - sz;
  454.       }
  455.  
  456.       if(Gdy >= 0.0) 
  457.       {
  458.       y1 = sy;
  459.       y2 = sy + Gdy;
  460.       }
  461.       else 
  462.       {
  463.       y1 = sy + Gdy;
  464.       y2 = sy;
  465.       }
  466.  
  467.       for(i=0;i<=length;i++) 
  468.       {
  469.       if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  470.         retval = TRUE;
  471.       f += Gdz;
  472.       if(f>0.0) 
  473.         {
  474.         iz += isdz;
  475.         if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  476.           retval = TRUE;
  477.         f -= 1.0;
  478.         }
  479.       ix += isdx;
  480.       y1 += Gdy;
  481.       y2 += Gdy;
  482.       }
  483.     }
  484.   else 
  485.     {
  486.     if(isdz >= 0) 
  487.       {
  488.       f = floor(sz) - sz;
  489.       sz = floor(sz);
  490.       sy += Myz * f;
  491.       sx += Mxz * f;
  492.       ez = ceil(ez) - 1.0;
  493.       iz = (int)sz;
  494.       }
  495.     else 
  496.       {
  497.       f = ceil(sz) - sz;
  498.       sz = ceil(sz) - 1.0;
  499.       sy += Myz * f;
  500.       sx += Mxz * f;
  501.       ez = floor(ez);
  502.       iz = (int)sz;
  503.       }             
  504.  
  505.       length = (int)abs((int)ez - (int)sz);
  506.  
  507.     if (isdx >= 0) 
  508.       {
  509.       tx = floor(start->x) + 1.0;
  510.       ix = (int)start->x;
  511.       f = sx - tx;
  512.       }
  513.     else 
  514.       {
  515.       tx = ceil(start->x) - 1.0;
  516.       ix = (int)tx;
  517.       f = tx - sx;
  518.       }
  519.  
  520.       if(Gdy >= 0.0) 
  521.       {
  522.       y1 = sy;
  523.       y2 = sy + Gdy;
  524.       }
  525.       else 
  526.       {
  527.       y1 = sy + Gdy;
  528.       y2 = sy;
  529.       }
  530.  
  531.       for(i=0;i<=length;i++) 
  532.       {
  533.       if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  534.         retval = TRUE;
  535.       f += Gdx;
  536.       if(f>0.0) 
  537.         {
  538.         ix += isdx;
  539.         if(Intersect_Pixel(ix,iz,Ray,H_Field,y1,y2))
  540.           retval = TRUE;
  541.         f -= 1.0;
  542.         }
  543.       iz += isdz;
  544.       y1 += Gdy;
  545.       y2 += Gdy;
  546.       }
  547.     }
  548.   return (retval);
  549.   }
  550.  
  551. int Intersect_Hf_Node(Ray, H_Field, start, end)
  552. RAY *Ray;
  553. HEIGHT_FIELD *H_Field;
  554. VECTOR *start, *end;
  555.   {
  556.   VECTOR *curr, *next, *temp, temp1, temp2;
  557.   DBL sx, sy, sz, ex, ey, ez, x, y, z;
  558.   DBL tnear, tfar, t, bsx, bsz, bex, bez;
  559.   int ix, iz, x_size, z_size, length, i;
  560.  
  561.   x = sx = start->x;
  562.   y = sy = start->y;
  563.   z = sz = start->z;
  564.   ex = end->x;
  565.   ey = end->y;
  566.   ez = end->z;
  567.  
  568.   bsx = sx * Inv_Blk_Size;
  569.   bsz = sz * Inv_Blk_Size;
  570.   bex = ex * Inv_Blk_Size;
  571.   bez = ez * Inv_Blk_Size;
  572.  
  573.   if (isdx >= 0) 
  574.     {
  575.     bsx = floor(bsx);
  576.     bex = ceil(bex) - 1.0;
  577.     }
  578.   else 
  579.     {
  580.     bsx = ceil(bsx) - 1.0;
  581.     bex = floor(bex);
  582.     }
  583.  
  584.     if (isdz >= 0) 
  585.     {
  586.     bsz = floor(bsz);
  587.     bez = ceil(bez) - 1.0;
  588.     }
  589.     else 
  590.     {
  591.     bsz = ceil(bsz) - 1.0;
  592.     bez = floor(bez);
  593.     }
  594.  
  595.     x_size = abs((int)bex - (int)bsx);
  596.   z_size = abs((int)bez - (int)bsz);
  597.  
  598.   length = x_size + z_size;
  599.  
  600.   curr = &temp1;
  601.   next = &temp2;
  602.   Make_Vector(curr, x, y, z);
  603.   t = 0.0;
  604.  
  605.   if(X_Dom) 
  606.     {
  607.     if(isdx >= 0) 
  608.       {
  609.       ix = (int)floor(sx*Inv_Blk_Size);
  610.       tnear = Block_Size*(ix+1) - sx;
  611.  
  612.       if (isdz >= 0) 
  613.         {
  614.         iz = (int)floor(sz*Inv_Blk_Size);
  615.         tfar = Gdx * (Block_Size*(iz+1) - sz);
  616.         }
  617.       else 
  618.         {
  619.         iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  620.         tfar = Gdx * (sz - Block_Size*(iz));
  621.         }                        
  622.       for (i = 0; i < length; i++) 
  623.         {
  624.         if(tfar < tnear) 
  625.           {
  626.           t = tfar;
  627.           x = sx + t;
  628.           y = sy + Myx * t;
  629.           z = sz + Mzx * t;
  630.           Make_Vector(next, x, y, z);
  631.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  632.             return(TRUE);
  633.           temp = curr;
  634.           curr = next;
  635.           next = temp;
  636.           iz += isdz;
  637.           if (isdz >= 0) 
  638.             tfar = Gdx * (Block_Size*(iz+1) - sz);
  639.           else 
  640.             tfar = Gdx * (sz - Block_Size*(iz));
  641.           }
  642.         else 
  643.           {
  644.           t = tnear;
  645.           x = sx + t;
  646.           y = sy + Myx * t;
  647.           z = sz + Mzx * t;
  648.           Make_Vector(next, x, y, z);
  649.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  650.             return(TRUE);
  651.           temp = curr;
  652.           curr = next;
  653.           next = temp;
  654.           ix++;
  655.           tnear = Block_Size*(ix+1) - sx;
  656.           }
  657.         }
  658.       }
  659.     else 
  660.       {                          
  661.       ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  662.       tnear = sx - Block_Size*(ix);
  663.  
  664.         if (isdz >= 0) 
  665.         {
  666.         iz = (int)floor(sz*Inv_Blk_Size);
  667.         tfar = Gdx * (Block_Size*(iz+1) - sz);
  668.         }
  669.         else 
  670.         {
  671.         iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  672.         tfar = Gdx * (sz - Block_Size*(iz));
  673.         }
  674.  
  675.         for (i = 0; i < length; i++) 
  676.         {
  677.         if(tfar < tnear) 
  678.           {
  679.           t = tfar;
  680.           x = sx - t;
  681.           y = sy - Myx * t;
  682.           z = sz - Mzx * t;
  683.           Make_Vector(next, x, y, z);
  684.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  685.             return(TRUE);
  686.           temp = curr;
  687.           curr = next;
  688.           next = temp;
  689.           iz += isdz;
  690.           if (isdz >= 0) 
  691.             tfar = Gdx * (Block_Size*(iz+1) - sz);
  692.           else 
  693.             tfar = Gdx * (sz - Block_Size*(iz));
  694.           }
  695.         else 
  696.           {
  697.           t = tnear;
  698.           x = sx - t;
  699.           y = sy - Myx * t;
  700.           z = sz - Mzx * t;
  701.           Make_Vector(next, x, y, z);
  702.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  703.             return(TRUE);
  704.           temp = curr;
  705.           curr = next;
  706.           next = temp;
  707.           ix--;
  708.           tnear = sx - Block_Size*(ix);
  709.           }
  710.         }
  711.       }                             
  712.     }
  713.   else 
  714.     {
  715.     if(isdz >= 0) 
  716.       {
  717.       iz = (int)floor(sz*Inv_Blk_Size);
  718.       tnear = Block_Size*(iz+1) - sz;
  719.  
  720.       if (isdx >= 0) 
  721.         {
  722.         ix = (int)floor(sx*Inv_Blk_Size);       
  723.         tfar = Gdz * (Block_Size*(ix+1) - sx);
  724.         }
  725.       else 
  726.         {
  727.         ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  728.         tfar = Gdz * (sx - Block_Size*(ix));
  729.         }
  730.       for (i = 0; i < length; i++) 
  731.         {
  732.         if(tfar < tnear) 
  733.           {
  734.           t = tfar;
  735.           z = sz + t;
  736.           y = sy + Myz * t;
  737.           x = sx + Mxz * t;
  738.           Make_Vector(next, x, y, z);
  739.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  740.             return(TRUE);
  741.           temp = curr;
  742.           curr = next;
  743.           next = temp;
  744.           ix += isdx;
  745.           if (isdx >= 0) 
  746.             tfar = Gdz * (Block_Size*(ix+1) - sx);
  747.           else 
  748.             tfar = Gdz * (sx - Block_Size*(ix));
  749.           }
  750.         else 
  751.           {
  752.           t = tnear;
  753.           z = sz + t;
  754.           y = sy + Myz * t;
  755.           x = sx + Mxz * t;
  756.           Make_Vector(next, x, y, z);
  757.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  758.             return(TRUE);
  759.           temp = curr;
  760.           curr = next;
  761.           next = temp;
  762.           iz++;
  763.           tnear = Block_Size*(iz+1) - sz;
  764.           }
  765.         }
  766.       }
  767.     else 
  768.       {                          
  769.       iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  770.       tnear = sz - Block_Size*(iz);
  771.  
  772.         if (isdx >= 0) 
  773.         {
  774.         ix = (int)floor(sx*Inv_Blk_Size);
  775.         tfar = Gdz * (Block_Size*(ix+1) - sx);
  776.         }
  777.         else 
  778.         {
  779.         ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  780.         tfar = Gdz * (sx - Block_Size*(ix));
  781.         }                                   
  782.       for (i = 0; i < length; i++) 
  783.         {
  784.         if(tfar < tnear) 
  785.           {
  786.           t = tfar;
  787.           z = sz - t;
  788.           y = sy - Myz * t;
  789.           x = sx - Mxz * t;
  790.           Make_Vector(next, x, y, z);
  791.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  792.             return(TRUE);
  793.           temp = curr;
  794.           curr = next;
  795.           next = temp;
  796.           ix += isdx;
  797.           if (isdx >= 0) 
  798.             tfar = Gdz * (Block_Size*(ix+1) - sx);
  799.           else
  800.             tfar = Gdz * (sx - Block_Size*(ix));
  801.           }
  802.         else 
  803.           {
  804.           t = tnear;
  805.           z = sz - t;
  806.           y = sy - Myz * t;
  807.           x = sx - Mxz * t;
  808.           Make_Vector(next, x, y, z);
  809.           if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  810.             return(TRUE);
  811.           temp = curr;
  812.           curr = next;
  813.           next = temp;
  814.           iz--;
  815.           tnear = sz - Block_Size*iz;
  816.           }
  817.         }
  818.       }                                     
  819.     }
  820.   Make_Vector(next,ex,ey,ez);
  821.   if(isdx >= 0)
  822.     ix = (int)ceil(ex*Inv_Blk_Size) - 1;
  823.   else
  824.     ix = (int)floor(ex*Inv_Blk_Size);
  825.   if(isdz >= 0)
  826.     iz = (int)ceil(ez*Inv_Blk_Size) - 1;
  827.   else
  828.     iz = (int)floor(ez*Inv_Blk_Size);
  829.   if(Intersect_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  830.     return(TRUE);
  831.   return (FALSE);
  832.   }
  833.  
  834. static int Intersect_Csg_Hf_Node(Ray, H_Field, start, end)
  835. RAY *Ray;
  836. HEIGHT_FIELD *H_Field;
  837. VECTOR *start, *end;
  838.   {
  839.   VECTOR *curr, *next, *temp, temp1, temp2;
  840.   DBL sx, sy, sz, ex, ey, ez, x, y, z;
  841.   DBL tnear, tfar, t, bsx, bsz, bex, bez;
  842.   int ix, iz, x_size, z_size, length, i, retval;
  843.  
  844.   retval = FALSE;
  845.   x = sx = start->x;
  846.   y = sy = start->y;
  847.   z = sz = start->z;
  848.   ex = end->x;
  849.   ey = end->y;
  850.   ez = end->z;
  851.  
  852.   bsx = sx * Inv_Blk_Size;
  853.   bsz = sz * Inv_Blk_Size;
  854.   bex = ex * Inv_Blk_Size;
  855.   bez = ez * Inv_Blk_Size;
  856.  
  857.   if (isdx >= 0) 
  858.     {
  859.     bsx = floor(bsx);
  860.     bex = ceil(bex) - 1.0;
  861.     }
  862.   else 
  863.     {
  864.     bsx = ceil(bsx) - 1.0;
  865.     bex = floor(bex);
  866.     }
  867.  
  868.     if (isdz >= 0) 
  869.     {
  870.     bsz = floor(bsz);
  871.     bez = ceil(bez) - 1.0;
  872.     }
  873.     else 
  874.     {
  875.     bsz = ceil(bsz) - 1.0;
  876.     bez = floor(bez);
  877.     }
  878.  
  879.     x_size = abs((int)bex - (int)bsx);
  880.   z_size = abs((int)bez - (int)bsz);
  881.  
  882.   length = x_size + z_size;
  883.  
  884.   curr = &temp1;
  885.   next = &temp2;
  886.   Make_Vector(curr, x, y, z);
  887.   t = 0.0;
  888.  
  889.   if(X_Dom) 
  890.     {
  891.     if(isdx >= 0) 
  892.       {
  893.       ix = (int)floor(sx*Inv_Blk_Size);
  894.       tnear = Block_Size*(ix+1) - sx;
  895.  
  896.       if (isdz >= 0) 
  897.         {
  898.         iz = (int)floor(sz*Inv_Blk_Size);
  899.         tfar = Gdx * (Block_Size*(iz+1) - sz);
  900.         }
  901.       else 
  902.         {
  903.         iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  904.         tfar = Gdx * (sz - Block_Size*(iz));
  905.         }                        
  906.       for (i = 0; i < length; i++) 
  907.         {
  908.         if(tfar < tnear) 
  909.           {
  910.           t = tfar;
  911.           x = sx + t;
  912.           y = sy + Myx * t;
  913.           z = sz + Mzx * t;
  914.           Make_Vector(next, x, y, z);
  915.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  916.             retval = TRUE;
  917.           temp = curr;
  918.           curr = next;
  919.           next = temp;
  920.           iz += isdz;
  921.           if (isdz >= 0) 
  922.             tfar = Gdx * (Block_Size*(iz+1) - sz);
  923.           else 
  924.             tfar = Gdx * (sz - Block_Size*(iz));
  925.           }
  926.         else 
  927.           {
  928.           t = tnear;
  929.           x = sx + t;
  930.           y = sy + Myx * t;
  931.           z = sz + Mzx * t;
  932.           Make_Vector(next, x, y, z);
  933.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  934.             retval = TRUE;
  935.           temp = curr;
  936.           curr = next;
  937.           next = temp;
  938.           ix++;
  939.           tnear = Block_Size*(ix+1) - sx;
  940.           }
  941.         }
  942.       }
  943.     else 
  944.       {                          
  945.       ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  946.       tnear = sx - Block_Size*(ix);
  947.  
  948.         if (isdz >= 0) 
  949.         {
  950.         iz = (int)floor(sz*Inv_Blk_Size);
  951.         tfar = Gdx * (Block_Size*(iz+1) - sz);
  952.         }
  953.         else 
  954.         {
  955.         iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  956.         tfar = Gdx * (sz - Block_Size*(iz));
  957.         }
  958.  
  959.         for (i = 0; i < length; i++) 
  960.         {
  961.         if(tfar < tnear) 
  962.           {
  963.           t = tfar;
  964.           x = sx - t;
  965.           y = sy - Myx * t;
  966.           z = sz - Mzx * t;
  967.           Make_Vector(next, x, y, z);
  968.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  969.             retval = TRUE;
  970.           temp = curr;
  971.           curr = next;
  972.           next = temp;
  973.           iz += isdz;
  974.           if (isdz >= 0) 
  975.             tfar = Gdx * (Block_Size*(iz+1) - sz);
  976.           else 
  977.             tfar = Gdx * (sz - Block_Size*(iz));
  978.           }
  979.         else 
  980.           {
  981.           t = tnear;
  982.           x = sx - t;
  983.           y = sy - Myx * t;
  984.           z = sz - Mzx * t;
  985.           Make_Vector(next, x, y, z);
  986.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  987.             retval = TRUE;
  988.           temp = curr;
  989.           curr = next;
  990.           next = temp;
  991.           ix--;
  992.           tnear = sx - Block_Size*(ix);
  993.           }
  994.         }
  995.       }                             
  996.     }
  997.   else 
  998.     {
  999.     if(isdz >= 0) 
  1000.       {
  1001.       iz = (int)floor(sz*Inv_Blk_Size);
  1002.       tnear = Block_Size*(iz+1) - sz;
  1003.  
  1004.       if (isdx >= 0) 
  1005.         {
  1006.         ix = (int)floor(sx*Inv_Blk_Size);       
  1007.         tfar = Gdz * (Block_Size*(ix+1) - sx);
  1008.         }
  1009.       else 
  1010.         {
  1011.         ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  1012.         tfar = Gdz * (sx - Block_Size*(ix));
  1013.         }
  1014.       for (i = 0; i < length; i++) 
  1015.         {
  1016.         if(tfar < tnear) 
  1017.           {
  1018.           t = tfar;
  1019.           z = sz + t;
  1020.           y = sy + Myz * t;
  1021.           x = sx + Mxz * t;
  1022.           Make_Vector(next, x, y, z);
  1023.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  1024.             retval = TRUE;
  1025.           temp = curr;
  1026.           curr = next;
  1027.           next = temp;
  1028.           ix += isdx;
  1029.           if (isdx >= 0) 
  1030.             tfar = Gdz * (Block_Size*(ix+1) - sx);
  1031.           else 
  1032.             tfar = Gdz * (sx - Block_Size*(ix));
  1033.           }
  1034.         else 
  1035.           {
  1036.           t = tnear;
  1037.           z = sz + t;
  1038.           y = sy + Myz * t;
  1039.           x = sx + Mxz * t;
  1040.           Make_Vector(next, x, y, z);
  1041.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  1042.             retval = TRUE;
  1043.           temp = curr;
  1044.           curr = next;
  1045.           next = temp;
  1046.           iz++;
  1047.           tnear = Block_Size*(iz+1) - sz;
  1048.           }
  1049.         }
  1050.       }
  1051.     else 
  1052.       {                          
  1053.       iz = (int)ceil(sz*Inv_Blk_Size) - 1;
  1054.       tnear = sz - Block_Size*(iz);
  1055.  
  1056.         if (isdx >= 0) 
  1057.         {
  1058.         ix = (int)floor(sx*Inv_Blk_Size);
  1059.         tfar = Gdz * (Block_Size*(ix+1) - sx);
  1060.         }
  1061.         else 
  1062.         {
  1063.         ix = (int)ceil(sx*Inv_Blk_Size) - 1;
  1064.         tfar = Gdz * (sx - Block_Size*(ix));
  1065.         }                                   
  1066.       for (i = 0; i < length; i++) 
  1067.         {
  1068.         if(tfar < tnear) 
  1069.           {
  1070.           t = tfar;
  1071.           z = sz - t;
  1072.           y = sy - Myz * t;
  1073.           x = sx - Mxz * t;
  1074.           Make_Vector(next, x, y, z);
  1075.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  1076.             retval = TRUE;
  1077.           temp = curr;
  1078.           curr = next;
  1079.           next = temp;
  1080.           ix += isdx;
  1081.           if (isdx >= 0) 
  1082.             tfar = Gdz * (Block_Size*(ix+1) - sx);
  1083.           else 
  1084.             tfar = Gdz * (sx - Block_Size*(ix));
  1085.           }
  1086.         else 
  1087.           {
  1088.           t = tnear;
  1089.           z = sz - t;
  1090.           y = sy - Myz * t;
  1091.           x = sx - Mxz * t;
  1092.           Make_Vector(next, x, y, z);
  1093.           if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  1094.             retval = TRUE;
  1095.           temp = curr;
  1096.           curr = next;
  1097.           next = temp;
  1098.           iz--;
  1099.           tnear = sz - Block_Size*iz;
  1100.           }
  1101.         }
  1102.       }                                     
  1103.     }
  1104.   Make_Vector(next,ex,ey,ez);
  1105.   if(isdx >= 0)
  1106.     ix = (int)ceil(ex*Inv_Blk_Size) - 1;
  1107.   else
  1108.     ix = (int)floor(ex*Inv_Blk_Size);
  1109.   if(isdz >= 0)
  1110.     iz = (int)ceil(ez*Inv_Blk_Size) - 1;
  1111.   else
  1112.     iz = (int)floor(ez*Inv_Blk_Size);
  1113.   if(Intersect_Csg_Sub_Block(&(H_Field->Block[ix][iz]),Ray,H_Field,curr,next))
  1114.     retval = TRUE;
  1115.   return (retval);
  1116.   }
  1117.  
  1118. static int
  1119. add_single_normal(data, xsize, zsize, x0, z0, x1, z1, x2, z2, N)
  1120.   HF_val **data;
  1121.   int xsize,zsize,x0,z0,x1,z1,x2,z2;
  1122.   VECTOR *N;
  1123.   {
  1124.   VECTOR v0, v1, v2, t0, t1, Nt;
  1125.  
  1126.   if (x0 < 0 || z0 < 0 ||
  1127.     x1 < 0 || z1 < 0 ||
  1128.     x2 < 0 || z2 < 0 ||
  1129.     x0 > xsize || z0 > zsize ||
  1130.     x1 > xsize || z1 > zsize ||
  1131.     x2 > xsize || z2 > zsize) 
  1132.     {
  1133.     return 0;
  1134.     }
  1135.   else 
  1136.     {
  1137.     Make_Vector(&v0, x0, (DBL)data[z0][x0], z0);
  1138.     Make_Vector(&v1, x1, (DBL)data[z1][x1], z1);
  1139.     Make_Vector(&v2, x2, (DBL)data[z2][x2], z2);
  1140.     VSub(t0, v2, v0);
  1141.     VSub(t1, v1, v0);
  1142.     VCross(Nt, t0, t1);
  1143.     Normalize(&Nt, &Nt);
  1144.     if(Nt.y < 0.0) 
  1145.       {
  1146.       VScale(Nt,Nt,-1.0);
  1147.       }
  1148.     VAdd(*N, *N, Nt);
  1149.     return 1;
  1150.     }
  1151.   }
  1152.  
  1153. /* Given a height field that only contains an elevation grid, this
  1154.    routine will walk through the data and produce averaged normals
  1155.    for all points on the grid. */
  1156. static void
  1157. smooth_height_field(hf, xsize, zsize)
  1158.   HEIGHT_FIELD *hf;
  1159.   int xsize;
  1160.   int zsize;
  1161.   {
  1162.   int i, j, k;
  1163.   VECTOR N;
  1164.   HF_val **map = hf->Map;
  1165.  
  1166.   /* First off, allocate all the memory needed to store the
  1167.       normal information */
  1168.   hf->Normals = (HF_Normals **)malloc((zsize+1) * sizeof(HF_Normals *));
  1169.   if (hf->Normals == NULL) 
  1170.     {
  1171.     fprintf(stderr, "Failed to allocate hf->norm\n");
  1172.     exit(1);
  1173.     }
  1174.   for (i=0; i<=zsize; i++) 
  1175.     {
  1176.     hf->Normals[i] = (HF_Normals *)malloc((xsize+1) * sizeof(HF_Normals));
  1177.     if (hf->Normals[i] == NULL) 
  1178.       {
  1179.       fprintf(stderr, "Failed to allocate hf->norm[%d]\n", i);
  1180.       exit(1);
  1181.       }
  1182.     }
  1183.  
  1184.   /* For now we will do it the hard way - by generating the normals
  1185.       individually for each elevation point */
  1186.   for (i=0;i<=zsize;i++) 
  1187.     {
  1188.     COOPERATE 
  1189.     if((i%(int)Block_Size) == 0) fprintf(stderr,".");
  1190.     for (j=0;j<=xsize;j++) 
  1191.       {
  1192.       Make_Vector(&N, 0.0, 0.0, 0.0);
  1193.       k = 0;
  1194.       /*
  1195.          k += add_single_normal(map, xsize, zsize, j, i, j+1, i, j, i+1, &N);
  1196.          k += add_single_normal(map, xsize, zsize, j+1, i+1, j, i+1, j+1, i, &N);
  1197.          k += add_single_normal(map, xsize, zsize, j, i+1, j-1, i+1, j, i, &N);
  1198.          k += add_single_normal(map, xsize, zsize, j-1, i, j, i, j-1, i+1, &N);
  1199.          k += add_single_normal(map, xsize, zsize, j, i, j-1, i, j, i-1, &N);
  1200.          k += add_single_normal(map, xsize, zsize, j-1, i-1, j, i-1, j-1, i, &N);
  1201.          k += add_single_normal(map, xsize, zsize, j, i-1, j+1, i-1, j, i, &N);
  1202.          k += add_single_normal(map, xsize, zsize, j+1, i, j, i, j+1, i-1, &N);
  1203. */
  1204.       k += add_single_normal(map, xsize, zsize, j, i, j+1, i, j, i+1, &N);
  1205.       k += add_single_normal(map, xsize, zsize, j, i, j, i+1, j-1, i, &N);
  1206.       k += add_single_normal(map, xsize, zsize, j, i, j-1, i, j, i-1, &N);
  1207.       k += add_single_normal(map, xsize, zsize, j, i, j, i-1, j+1, i, &N);
  1208.  
  1209.       if (k == 0) 
  1210.         {
  1211.         fprintf(stderr, "Failed to find any normals at: (%d, %d)\n", i, j);
  1212.         exit(1);
  1213.         }
  1214.       Normalize(&N, &N);
  1215.       hf->Normals[i][j][0] = (short)(32767 * N.x);
  1216.       hf->Normals[i][j][1] = (short)(32767 * N.y);
  1217.       hf->Normals[i][j][2] = (short)(32767 * N.z);
  1218.       /* printf("n[%d,%d]: <%g %g %g>\n", j, i, N.x, N.y, N.z); */
  1219.       }
  1220.     }
  1221.   }   
  1222.  
  1223. void Find_Hf_Min_Max(H_Field, Image)
  1224. HEIGHT_FIELD *H_Field;
  1225. IMAGE *Image;
  1226.   {
  1227.   int n, i, i2, j, j2, x, z, w, h, max_x, max_z, temp1, temp2;
  1228.   DBL size;
  1229.   HF_val temp_y;
  1230.  
  1231.   max_x = Image->iwidth;
  1232.   if(Image->File_Type == POT_FILE) max_x = max_x/2;
  1233.   max_z = Image->iheight;
  1234.  
  1235.   size = (DBL)max_value(max_x, max_z);
  1236.   H_Field->Block_Size  = Block_Size = ceil(sqrt(size+1.0));
  1237.   H_Field->Inv_Blk_Size = Inv_Blk_Size = 1.0/Block_Size;
  1238.   n = (int)Block_Size;
  1239.  
  1240.   w = (int)ceil((max_x+1.0)*Inv_Blk_Size);
  1241.   h = (int)ceil((max_z+1.0)*Inv_Blk_Size);
  1242.  
  1243.   H_Field->Map = (HF_val **)calloc(max_z+1, sizeof(HF_val *));
  1244.   if (H_Field->Map == NULL)
  1245.     fprintf(stderr,"Cannot allocate memory for height field\n");
  1246.  
  1247.   H_Field->Block = (HF_BLOCK **)calloc(w,sizeof(HF_BLOCK *));
  1248.   if(H_Field->Block == NULL)
  1249.     fprintf(stderr, "Cannot allocate memory for height field buffer\n");
  1250.   for(i=0; i<w; i++) 
  1251.     {
  1252.     H_Field->Block[i] = (HF_BLOCK *)calloc(h,sizeof(HF_BLOCK));
  1253.     if (H_Field->Block[i] == NULL)
  1254.       fprintf(stderr, "Cannot allocate memory for height field buffer line\n"
  1255.         );
  1256.     for(j=0; j<h; j++) 
  1257.       {
  1258.       H_Field->Block[i][j].min_y = 65535;
  1259.       H_Field->Block[i][j].max_y = 0;
  1260.       }
  1261.     }
  1262.  
  1263.   H_Field->Map[0] = (HF_val *)calloc(max_x+1,sizeof(HF_val));
  1264.   if (H_Field->Map[0] == NULL)
  1265.     fprintf(stderr,"Cannot allocate memory for height field\n");
  1266.  
  1267.   for(j=0; j < h; j++)
  1268.     {
  1269.     for(j2=0;(j2 <= n) && (j*n+j2 <= max_z);j2++)
  1270.       {
  1271.       z = j*n+j2;
  1272.       if(j2!=0)
  1273.         {
  1274.         H_Field->Map[z] = (HF_val *)calloc(max_x+1,sizeof(HF_val));
  1275.         if (H_Field->Map[z] == NULL)
  1276.           fprintf(stderr, "Cannot allocate memory for height field\n");
  1277.         }
  1278.  
  1279.       COOPERATE 
  1280.       for(i=0; i < w; i++)
  1281.         {
  1282.         for(i2=0;(i2 <= n)&&(i*n+i2 <= max_x);i2++)
  1283.           {
  1284.           x = i*n+i2;
  1285.           if((x >= 0) && (x < max_x) && (z >= 0) && (z < max_z)) 
  1286.             {
  1287.             switch(Image->File_Type) 
  1288.             {
  1289.             case GIF_FILE:
  1290.               temp1 = Image->data.map_lines[max_z - z - 1][x];
  1291.               temp_y = (HF_val)(256*temp1);
  1292.               break;
  1293.             case POT_FILE:
  1294.               temp1 = Image->data.map_lines[max_z - z - 1][x];
  1295.               temp2 = Image->data.map_lines[max_z - z - 1][x + max_x];
  1296.               temp_y = (HF_val)(256*temp1 + temp2);
  1297.               break;
  1298.             case TGA_FILE:
  1299.               if (Image->Colour_Map == NULL) 
  1300.                 {
  1301.                 temp1 = Image->data.rgb_lines[max_z - z - 1].red[x];
  1302.                 temp2 = Image->data.rgb_lines[max_z - z - 1].green[x];
  1303.                 }
  1304.               else 
  1305.                 {
  1306.                 temp1 = Image->data.map_lines[max_z - z - 1][x];
  1307.                 temp2 = 0;
  1308.                 }
  1309.               temp_y = (HF_val)(256*temp1 + temp2);
  1310.               break;
  1311.             }
  1312.             H_Field->Map[z][x] = temp_y;
  1313.             }
  1314.           else 
  1315.             {
  1316.             if (z == max_z) 
  1317.               {
  1318.               H_Field->Map[z][x] = H_Field->Map[z-1][x];
  1319.               }
  1320.             if (x == max_x) 
  1321.               {
  1322.               H_Field->Map[z][x] = H_Field->Map[z][x-1];
  1323.               }
  1324.             temp_y = H_Field->Map[z][x];
  1325.             }
  1326.  
  1327.           if(temp_y < H_Field->Block[i][j].min_y)
  1328.             H_Field->Block[i][j].min_y = temp_y;
  1329.           if(temp_y > H_Field->Block[i][j].max_y)
  1330.             H_Field->Block[i][j].max_y = temp_y;
  1331.           }
  1332.         }
  1333.       if((z >= 0) && (z < max_z) && (j2!=n)) 
  1334.         {
  1335.         switch (Image->File_Type) 
  1336.         {
  1337.         case GIF_FILE: 
  1338.           free(Image->data.map_lines[max_z - z - 1]); break;
  1339.         case POT_FILE: 
  1340.           free(Image->data.map_lines[max_z - z - 1]); break;
  1341.         case TGA_FILE:
  1342.           if (Image->Colour_Map == NULL) 
  1343.             {
  1344.             free(Image->data.rgb_lines[max_z - z - 1].blue);
  1345.             free(Image->data.rgb_lines[max_z - z - 1].green);
  1346.             free(Image->data.rgb_lines[max_z - z - 1].red);
  1347.             }
  1348.           else 
  1349.             {
  1350.             free(Image->data.map_lines[max_z - z - 1]);
  1351.             }
  1352.           break;
  1353.         }
  1354.         }
  1355.       }
  1356.     }
  1357.  
  1358.     /* If this is a smoothed height field, then allocate storage for
  1359.       the normals & compute them */
  1360.     if (H_Field->Smoothed)
  1361.       smooth_height_field(H_Field, max_x, max_z);
  1362.  
  1363.   }
  1364.  
  1365. int All_HeightFld_Intersections(Object, Ray, Depth_Stack)
  1366. OBJECT *Object;
  1367. RAY *Ray;
  1368. ISTACK *Depth_Stack;
  1369.   {
  1370.   VECTOR Temp1, Temp2;
  1371.   RAY Temp_Ray;
  1372.   DBL depth1, depth2;
  1373.   int ret_val = FALSE;
  1374.   HEIGHT_FIELD *H_Field = (HEIGHT_FIELD *) Object;
  1375.  
  1376.   Ray_Ht_Field_Tests++;
  1377.  
  1378.   MInvTransPoint(&(Temp_Ray.Initial),&(Ray->Initial),H_Field->Trans);
  1379.   MInvTransDirection(&(Temp_Ray.Direction),&(Ray->Direction),H_Field->Trans);
  1380.  
  1381.   if(!Intersect_Boxx(&Temp_Ray,H_Field->bounding_box,&depth1,&depth2))
  1382.     return(FALSE);     
  1383.  
  1384.   H_Field->cache_pos = 0;
  1385.   Block_Size = H_Field->Block_Size;
  1386.   Inv_Blk_Size = H_Field->Inv_Blk_Size;
  1387.  
  1388.   if( depth1 == depth2) 
  1389.     {
  1390.     depth1 = Small_Tolerance;
  1391.     VScale(Temp1,Temp_Ray.Direction,depth1);
  1392.     VAddEq(Temp1,Temp_Ray.Initial);
  1393.     VScale(Temp2,Temp_Ray.Direction,depth2);
  1394.     VAddEq(Temp2,Temp_Ray.Initial);
  1395.     }
  1396.   else 
  1397.     {
  1398.     VScale(Temp1,Temp_Ray.Direction,depth1);
  1399.     VAddEq(Temp1,Temp_Ray.Initial);
  1400.     VScale(Temp2,Temp_Ray.Direction,depth2);
  1401.     VAddEq(Temp2,Temp_Ray.Initial);        
  1402.     }
  1403.  
  1404.   mindist = depth1;
  1405.   maxdist = depth2;
  1406.  
  1407.   if(fabs(Temp_Ray.Direction.x) > EPSILON) 
  1408.     {
  1409.     Mzx = Temp_Ray.Direction.z/Temp_Ray.Direction.x;
  1410.     Myx = Temp_Ray.Direction.y/Temp_Ray.Direction.x;
  1411.     }
  1412.   else 
  1413.     {
  1414.     Mzx = Temp_Ray.Direction.z/EPSILON;
  1415.     Myx = Temp_Ray.Direction.y/EPSILON;
  1416.     }
  1417.   if(fabs(Temp_Ray.Direction.z) > EPSILON) 
  1418.     {
  1419.     Mxz = Temp_Ray.Direction.x/Temp_Ray.Direction.z;
  1420.     Myz = Temp_Ray.Direction.y/Temp_Ray.Direction.z;
  1421.     }
  1422.   else 
  1423.     {
  1424.     Mxz = Temp_Ray.Direction.x/EPSILON;
  1425.     Myz = Temp_Ray.Direction.y/EPSILON;
  1426.     }
  1427.  
  1428.   Hf_Stack = Depth_Stack;
  1429.   RRay = Ray;
  1430.  
  1431.   isdx = sign(Temp_Ray.Direction.x);
  1432.   isdz = sign(Temp_Ray.Direction.z);
  1433.  
  1434.   X_Dom = FALSE;
  1435.   if(fabs(Temp_Ray.Direction.x) >= fabs(Temp_Ray.Direction.z))
  1436.     X_Dom = TRUE;
  1437.  
  1438.   Gdx = fabs(Mxz);
  1439.   Gdz = fabs(Mzx);
  1440.   if(X_Dom) 
  1441.     {
  1442.     Gdy = Myx * (DBL)isdx;
  1443.     }
  1444.   else 
  1445.     {
  1446.     Gdy = Myz * (DBL)isdz;
  1447.     }
  1448.  
  1449.   if(Intersect_Hf_Node(&Temp_Ray, H_Field, &Temp1, &Temp2))
  1450.     ret_val = TRUE;
  1451.   return(ret_val);
  1452.   }
  1453.  
  1454. int All_Csg_HeightFld_Intersections(Object, Ray, Depth_Stack)
  1455. OBJECT *Object;
  1456. RAY *Ray;  
  1457. ISTACK *Depth_Stack;
  1458.   {
  1459.   VECTOR Temp1, Temp2;
  1460.   RAY Temp_Ray;
  1461.   DBL depth1, depth2;
  1462.   int ret_val = FALSE;
  1463.   HEIGHT_FIELD *H_Field = (HEIGHT_FIELD *) Object;
  1464.  
  1465.   Ray_Ht_Field_Tests++;
  1466.  
  1467.   MInvTransPoint(&(Temp_Ray.Initial),&(Ray->Initial),H_Field->Trans);
  1468.   MInvTransDirection(&(Temp_Ray.Direction),&(Ray->Direction),H_Field->Trans);
  1469.  
  1470.   if(!Intersect_Boxx(&Temp_Ray,H_Field->bounding_box,&depth1,&depth2))
  1471.     return(FALSE);     
  1472.  
  1473.   H_Field->cache_pos = 0;          
  1474.   Block_Size = H_Field->Block_Size;
  1475.   Inv_Blk_Size = H_Field->Inv_Blk_Size;
  1476.  
  1477.   if( depth1 == depth2) 
  1478.     {
  1479.     depth1 = Small_Tolerance;
  1480.     VScale(Temp1,Temp_Ray.Direction,depth1);
  1481.     VAddEq(Temp1,Temp_Ray.Initial);
  1482.     VScale(Temp2,Temp_Ray.Direction,depth2);
  1483.     VAddEq(Temp2,Temp_Ray.Initial);
  1484.     }
  1485.   else 
  1486.     {
  1487.     VScale(Temp1,Temp_Ray.Direction,depth1);
  1488.     VAddEq(Temp1,Temp_Ray.Initial);
  1489.     VScale(Temp2,Temp_Ray.Direction,depth2);
  1490.     VAddEq(Temp2,Temp_Ray.Initial);             
  1491.     }
  1492.  
  1493.     mindist = depth1;
  1494.   maxdist = depth2;
  1495.  
  1496.   if(fabs(Temp_Ray.Direction.x) > EPSILON) 
  1497.     {
  1498.     Mzx = Temp_Ray.Direction.z/Temp_Ray.Direction.x;
  1499.     Myx = Temp_Ray.Direction.y/Temp_Ray.Direction.x;
  1500.     }
  1501.   else 
  1502.     {
  1503.     Mzx = Temp_Ray.Direction.z/EPSILON;
  1504.     Myx = Temp_Ray.Direction.y/EPSILON;
  1505.     }
  1506.   if(fabs(Temp_Ray.Direction.z) > EPSILON) 
  1507.     {
  1508.     Mxz = Temp_Ray.Direction.x/Temp_Ray.Direction.z;
  1509.     Myz = Temp_Ray.Direction.y/Temp_Ray.Direction.z;
  1510.     }
  1511.   else 
  1512.     {
  1513.     Mxz = Temp_Ray.Direction.x/EPSILON;
  1514.     Myz = Temp_Ray.Direction.y/EPSILON;
  1515.     }
  1516.  
  1517.     Hf_Stack = Depth_Stack;
  1518.   RRay = Ray;
  1519.  
  1520.   isdx = sign(Temp_Ray.Direction.x);
  1521.   isdz = sign(Temp_Ray.Direction.z);
  1522.  
  1523.   X_Dom = FALSE;
  1524.   if(fabs(Temp_Ray.Direction.x) >= fabs(Temp_Ray.Direction.z))
  1525.     X_Dom = TRUE;
  1526.  
  1527.   Gdx = fabs(Mxz);
  1528.   Gdz = fabs(Mzx);
  1529.   if(X_Dom) 
  1530.     {
  1531.     Gdy = Myx * (DBL)isdx;
  1532.     }
  1533.   else 
  1534.     {
  1535.     Gdy = Myz * (DBL)isdz;
  1536.     }
  1537.  
  1538.     if(Intersect_Csg_Hf_Node(&Temp_Ray, H_Field, &Temp1, &Temp2))
  1539.       ret_val = TRUE;
  1540.   return(ret_val);
  1541.   }
  1542.  
  1543. int Inside_HeightFld (IPoint, Object)
  1544. VECTOR *IPoint;
  1545. OBJECT *Object;
  1546.   {
  1547.   HEIGHT_FIELD *H_Field = (HEIGHT_FIELD *) Object;
  1548.   int px, pz;
  1549.   DBL x,z,y1,y2,y3,water, dot1, dot2;
  1550.   VECTOR Local_Origin, Temp1, Temp2, Local_Normal, Test;
  1551.  
  1552.   MInvTransPoint(&Test, IPoint, H_Field->Trans);
  1553.  
  1554.   water = H_Field->bounding_box->bounds[0].y;
  1555.   if ((Test.x < 0.0) || (Test.x >= H_Field->bounding_box->bounds[1].x) || (Test.z < 0.0) || (Test.z >= H_Field->bounding_box->bounds[1].z))
  1556.     return (H_Field->Inverted);
  1557.  
  1558.   if (Test.y >= H_Field->bounding_box->bounds[1].y)
  1559.     return (H_Field->Inverted);
  1560.  
  1561.   if (Test.y < water)
  1562.     return (H_Field->Inverted ^ TRUE);
  1563.  
  1564.   px = (int)Test.x;
  1565.   pz = (int)Test.z;
  1566.   x = Test.x - (DBL)px;
  1567.   z = Test.z - (DBL)pz;
  1568.  
  1569.   if((x+z)<1.0) 
  1570.     {
  1571.     y1 = max_value(Get_Height(px,pz,H_Field),water);
  1572.     y2 = max_value(Get_Height(px+1,pz,H_Field),water);
  1573.     y3 = max_value(Get_Height(px,pz+1,H_Field),water);
  1574.     Make_Vector(&Local_Origin,(DBL)px,y1,(DBL)pz);
  1575.     Temp1.x = 1.0;
  1576.     Temp1.z = 0.0;
  1577.     Temp1.y = y2 - y1;
  1578.     Temp2.x = 0.0;
  1579.     Temp2.z = 1.0;
  1580.     Temp2.y = y3 - y1;
  1581.     }
  1582.   else 
  1583.     {
  1584.     px = (int)ceil(Test.x);
  1585.     pz = (int)ceil(Test.z);
  1586.     y1 = max_value(Get_Height(px,pz,H_Field),water);
  1587.     y2 = max_value(Get_Height(px-1,pz,H_Field),water);
  1588.     y3 = max_value(Get_Height(px,pz-1,H_Field),water);
  1589.     Make_Vector(&Local_Origin,(DBL)px,y1,(DBL)pz);
  1590.     Temp1.x = -1.0;
  1591.     Temp1.z = 0.0;
  1592.     Temp1.y = y2 - y1;
  1593.     Temp2.x = 0.0;
  1594.     Temp2.z = -1.0;
  1595.     Temp2.y = y3 - y1;
  1596.     }
  1597.   VCross(Local_Normal,Temp2,Temp1);
  1598.   VDot(dot1,Test,Local_Normal);
  1599.   VDot(dot2,Local_Origin,Local_Normal);
  1600.   if(dot1 < dot2)
  1601.     return(TRUE^H_Field->Inverted);
  1602.   return(FALSE^H_Field->Inverted);
  1603.   }
  1604.  
  1605. static
  1606. DBL stretch (x)
  1607. DBL x;
  1608.   {
  1609.   if(x<=0.5) 
  1610.     {
  1611.     x = 2 * x*x;
  1612.     }
  1613.   else 
  1614.     {
  1615.     x = 1.0 - (2 * (1.0-x)*(1.0-x));
  1616.     }
  1617.   return x;
  1618.   }
  1619.  
  1620.   void HeightFld_Normal (Result, Object, IPoint)
  1621.     OBJECT *Object;
  1622. VECTOR *Result, *IPoint;
  1623.   {
  1624.   HEIGHT_FIELD *H_Field = (HEIGHT_FIELD *) Object;
  1625.   int px,pz, i, code;
  1626.   DBL x,z,y1,y2,y3,u,v;
  1627.   VECTOR Local_Origin, Temp1, Temp2;
  1628.   VECTOR n[5];
  1629.  
  1630.   MInvTransPoint(&Local_Origin, IPoint, H_Field->Trans);
  1631.  
  1632.   for(i=0;i<H_Field->cache_pos;i++) 
  1633.     {
  1634.     if(((float)Local_Origin.x == H_Field->Normal_Vector[i].x) &&
  1635.       ((float)Local_Origin.z == H_Field->Normal_Vector[i].z)) 
  1636.       {
  1637.       *Result = H_Field->Normal_Vector[i].normal;
  1638.       MTransNormal(Result,Result,H_Field->Trans);
  1639.       VNormalize(*Result,*Result);
  1640.       return;
  1641.       }
  1642.     }
  1643.  
  1644.   px = (int)Local_Origin.x;
  1645.   pz = (int)Local_Origin.z;
  1646.   x = Local_Origin.x - (DBL)px;
  1647.   z = Local_Origin.z - (DBL)pz;
  1648.  
  1649.   px = (int)Local_Origin.x;
  1650.   pz = (int)Local_Origin.z;
  1651.   x = Local_Origin.x - (DBL)px;
  1652.   z = Local_Origin.z - (DBL)pz;
  1653.   if ((x+z) <= 1.0)
  1654.     code = LOWER_TRI;
  1655.   else 
  1656.     code = UPPER_TRI;
  1657.  
  1658.   if (H_Field->Smoothed) 
  1659.     {
  1660.     n[0].x = H_Field->Normals[pz][px][0];
  1661.     n[0].y = H_Field->Normals[pz][px][1];
  1662.     n[0].z = H_Field->Normals[pz][px][2];
  1663.     n[1].x = H_Field->Normals[pz][px+1][0];
  1664.     n[1].y = H_Field->Normals[pz][px+1][1];
  1665.     n[1].z = H_Field->Normals[pz][px+1][2];
  1666.     n[2].x = H_Field->Normals[pz+1][px][0];
  1667.     n[2].y = H_Field->Normals[pz+1][px][1];
  1668.     n[2].z = H_Field->Normals[pz+1][px][2];
  1669.     n[3].x = H_Field->Normals[pz+1][px+1][0];
  1670.     n[3].y = H_Field->Normals[pz+1][px+1][1];
  1671.     n[3].z = H_Field->Normals[pz+1][px+1][2];
  1672.     x = stretch(x);
  1673.     z = stretch(z);
  1674.     u = (1.0 - x);
  1675.     v = (1.0 - z);
  1676.  
  1677.     /*      n[4].x = u*n[0].x + x*n[1].x;
  1678.      n[4].y = u*n[0].y + x*n[1].y;
  1679.      n[4].z = u*n[0].z + x*n[1].z;
  1680.  
  1681.      n[5].x = u*n[2].x + x*n[3].x;
  1682.      n[5].y = u*n[2].y + x*n[3].y;
  1683.      n[5].z = u*n[2].z + x*n[3].z;
  1684.  
  1685.      n[6].x = v*n[0].x + z*n[2].x;
  1686.      n[6].y = v*n[0].y + z*n[2].y;
  1687.      n[6].z = v*n[0].z + z*n[2].z;
  1688.  
  1689.      n[7].x = v*n[1].x + z*n[3].x;
  1690.      n[7].y = v*n[1].y + z*n[3].y;
  1691.      n[7].z = v*n[1].z + z*n[3].z;
  1692.  
  1693.      Result->x = u*n[6].x + x*n[7].x + v*n[4].x + z*n[5].x;
  1694.      Result->y = u*n[6].y + x*n[7].y + v*n[4].y + z*n[5].y;
  1695.      Result->z = u*n[6].z + x*n[7].z + z*n[4].z + v*n[5].z;
  1696. */
  1697.     Result->x = u*v*n[0].x + x*v*n[1].x + u*z*n[2].x + x*z*n[3].x;     
  1698.     Result->y = u*v*n[0].y + x*v*n[1].y + u*z*n[2].y + x*z*n[3].y;     
  1699.     Result->z = u*v*n[0].z + x*v*n[1].z + u*z*n[2].z + x*z*n[3].z;     
  1700.     }
  1701.   else if (code == LOWER_TRI) 
  1702.     {
  1703.     y1 = Get_Height(px,pz,H_Field);
  1704.     y2 = Get_Height(px+1,pz,H_Field);
  1705.     y3 = Get_Height(px,pz+1,H_Field);
  1706.     Temp1.x = 1.0;
  1707.     Temp1.z = 0.0;
  1708.     Temp1.y = y2 - y1;
  1709.     Temp2.x = 0.0;
  1710.     Temp2.z = 1.0;
  1711.     Temp2.y = y3 - y1;
  1712.     VCross(*Result,Temp2,Temp1);
  1713.     }
  1714.   else 
  1715.     {
  1716.     y1 = Get_Height(px+1,pz+1,H_Field);
  1717.     y2 = Get_Height(px,pz+1,H_Field);
  1718.     y3 = Get_Height(px+1,pz,H_Field);
  1719.     Temp1.x = -1.0;
  1720.     Temp1.z = 0.0;
  1721.     Temp1.y = y2 - y1;
  1722.     Temp2.x = 0.0;
  1723.     Temp2.z = -1.0;
  1724.     Temp2.y = y3 - y1;
  1725.     VCross(*Result,Temp2,Temp1);
  1726.     }
  1727.   MTransNormal(Result,Result,H_Field->Trans);
  1728.   VNormalize(*Result,*Result);
  1729.   return;
  1730.   }
  1731.  
  1732.   void *Copy_HeightFld (Object)
  1733.     OBJECT *Object;
  1734.   {
  1735.   HEIGHT_FIELD *New;
  1736.  
  1737.   New = Create_Height_Field ();
  1738.  
  1739.   /*  Create_Height_Field creates a transform and a box as 
  1740.     does Copy_Transform and Copy_Box so destroy these.
  1741. */
  1742.  
  1743.   Destroy_Transform(New->Trans);
  1744.   Destroy_Box((OBJECT *)(New->bounding_box));
  1745.  
  1746.   *New = *((HEIGHT_FIELD *)Object);
  1747.  
  1748.   New->Trans        = Copy_Transform (((HEIGHT_FIELD *)Object)->Trans);
  1749.   New->bounding_box = Copy_Box ((OBJECT *)(((HEIGHT_FIELD *)Object)->bounding_box));
  1750.  
  1751.   /* Note: For the time being we will not support copying the Block and Map
  1752.    arrays.  We will only copy the pointers.  This means Destroy_HeightFld
  1753.    must not destroy these arrays.  Actually it cannot because we don't
  1754.    really know how big they are!  
  1755. */
  1756.  
  1757.   return (New);
  1758.   }
  1759.  
  1760. void Translate_HeightFld (Object, Vector)
  1761. OBJECT *Object;
  1762. VECTOR *Vector;
  1763.   {
  1764.   TRANSFORM Trans;
  1765.  
  1766.   Compute_Translation_Transform(&Trans,Vector);
  1767.   Compose_Transforms(((HEIGHT_FIELD *) Object)->Trans,&Trans);
  1768.   }
  1769.  
  1770. void Rotate_HeightFld (Object, Vector)
  1771. OBJECT *Object;
  1772. VECTOR *Vector;
  1773.   {
  1774.   TRANSFORM Trans;
  1775.  
  1776.   Compute_Rotation_Transform(&Trans,Vector);
  1777.   Compose_Transforms(((HEIGHT_FIELD *) Object)->Trans,&Trans);
  1778.   }
  1779.  
  1780. void Scale_HeightFld (Object, Vector)
  1781. OBJECT *Object;
  1782. VECTOR *Vector;
  1783.   {
  1784.   TRANSFORM Trans;
  1785.  
  1786.   Compute_Scaling_Transform(&Trans,Vector);
  1787.   Compose_Transforms(((HEIGHT_FIELD *)Object)->Trans,&Trans);
  1788.   }
  1789.  
  1790. void Invert_HeightFld (Object)
  1791. OBJECT *Object;
  1792.   {
  1793.   ((HEIGHT_FIELD *)Object)->Inverted ^= TRUE;
  1794.   }
  1795.  
  1796. void Transform_HeightFld (Object, Trans)
  1797. OBJECT *Object;
  1798. TRANSFORM *Trans;
  1799.   {
  1800.   Compose_Transforms(((HEIGHT_FIELD *)Object)->Trans, Trans);
  1801.   }
  1802.  
  1803. /* Allocate and intialize a Height Field */
  1804. HEIGHT_FIELD *Create_Height_Field()
  1805.   {
  1806.   HEIGHT_FIELD *New;
  1807.  
  1808.   if((New = (HEIGHT_FIELD *) malloc (sizeof(HEIGHT_FIELD))) == NULL)
  1809.     MAError ("height field");
  1810.  
  1811.   INIT_OBJECT_FIELDS(New, HEIGHT_FIELD_OBJECT, &Height_Field_Methods)
  1812.  
  1813.     /* Always uses Trans so always create one. */  
  1814.     New->Trans = Create_Transform (); 
  1815.   New->bounding_box = Create_Box (); 
  1816.   New->Block_Size   = 1.0;
  1817.   New->Inv_Blk_Size = 1.0;
  1818.   New->Block = NULL;
  1819.   New->Map   = NULL;
  1820.   New->Inverted = FALSE;
  1821.   New->cache_pos = 0;
  1822.   New->Smoothed = FALSE;
  1823.   New->Normals  = NULL;
  1824.   return(New);
  1825.   }
  1826.  
  1827. void Destroy_HeightFld (Object)
  1828. OBJECT *Object;
  1829.   {
  1830.   Destroy_Transform (((HEIGHT_FIELD *)Object)->Trans);
  1831.   Destroy_Box ((OBJECT *)((HEIGHT_FIELD *)Object)->bounding_box);
  1832.   free (Object);
  1833.   }
  1834.