home *** CD-ROM | disk | FTP | other *** search
/ Fish 'n' More 2 / fishmore-publicdomainlibraryvol.ii1991xetec.iso / dirs / dkbtrace_397.lzh / DKBTrace / DKBSource.LZH / quadrics.c < prev    next >
C/C++ Source or Header  |  1990-08-26  |  11KB  |  342 lines
  1. /*****************************************************************************
  2. *
  3. *                                   quadrics.c
  4. *
  5. *   from DKBTrace (c) 1990  David Buck
  6. *
  7. *  This module implements the code for the quadric shape primitive.
  8. *
  9. * This software is freely distributable. The source and/or object code may be
  10. * copied or uploaded to communications services so long as this notice remains
  11. * at the top of each file.  If any changes are made to the program, you must
  12. * clearly indicate in the documentation and in the programs startup message
  13. * who it was who made the changes. The documentation should also describe what
  14. * those changes were. This software may not be included in whole or in
  15. * part into any commercial package without the express written consent of the
  16. * author.  It may, however, be included in other public domain or freely
  17. * distributed software so long as the proper credit for the software is given.
  18. *
  19. * This software is provided as is without any guarantees or warranty. Although
  20. * the author has attempted to find and correct any bugs in the software, he
  21. * is not responsible for any damage caused by the use of the software.  The
  22. * author is under no obligation to provide service, corrections, or upgrades
  23. * to this package.
  24. *
  25. * Despite all the legal stuff above, if you do find bugs, I would like to hear
  26. * about them.  Also, if you have any comments or questions, you may contact me
  27. * at the following address:
  28. *
  29. *     David Buck
  30. *     22C Sonnet Cres.
  31. *     Nepean Ontario
  32. *     Canada, K2H 8W7
  33. *
  34. *  I can also be reached on the following bulleton boards:
  35. *
  36. *     ATX              (613) 526-4141
  37. *     OMX              (613) 731-3419
  38. *     Mystic           (613) 731-0088 or (613) 731-6698
  39. *
  40. *  Fidonet:   1:163/109.9
  41. *  Internet:  David_Buck@Carleton.CA
  42. *
  43. *  IBM Port by Aaron A. Collins. Aaron may be reached on the following BBS'es:
  44. *
  45. *     Lattice BBS                      (708) 916-1200
  46. *     The Information Exchange BBS     (708) 945-5575
  47. *     Stillwaters BBS                  (708) 403-2826
  48. *
  49. *****************************************************************************/
  50.  
  51.  
  52. #include "frame.h"
  53. #include "vector.h"
  54. #include "dkbproto.h"
  55.  
  56. METHODS Quadric_Methods =
  57.    { Object_Intersect, All_Quadric_Intersections,
  58.      Inside_Quadric, Quadric_Normal,
  59.      Copy_Quadric,
  60.      Translate_Quadric, Rotate_Quadric,
  61.      Scale_Quadric, Invert_Quadric};
  62.  
  63. extern RAY *VP_Ray;
  64. extern long Ray_Quadric_Tests, Ray_Quadric_Tests_Succeeded;
  65.  
  66. int All_Quadric_Intersections (Object, Ray, Depth_Queue)
  67.    OBJECT *Object;
  68.    RAY *Ray;
  69.    PRIOQ *Depth_Queue;
  70.    {
  71.    QUADRIC *Shape = (QUADRIC *) Object;
  72.    DBL Depth1, Depth2;
  73.    VECTOR Intersection_Point;
  74.    INTERSECTION Local_Element;
  75.    register int Intersection_Found;
  76.  
  77.    Intersection_Found = FALSE;
  78.    if (Intersect_Quadric (Ray, Shape, &Depth1, &Depth2))
  79.       {
  80.       Local_Element.Depth = Depth1;
  81.       Local_Element.Object = Shape -> Parent_Object;
  82.       VScale (Intersection_Point, Ray -> Direction, Depth1);
  83.       VAdd (Intersection_Point, Intersection_Point, Ray -> Initial);
  84.       Local_Element.Point = Intersection_Point;
  85.       Local_Element.Shape = (SHAPE *)Shape;
  86.       pq_add (Depth_Queue, &Local_Element);
  87.       Intersection_Found = TRUE;
  88.  
  89.       if (Depth2 != Depth1)
  90.          {
  91.          Local_Element.Depth = Depth2;
  92.          Local_Element.Object = Shape -> Parent_Object;
  93.          VScale (Intersection_Point, Ray -> Direction, Depth2);
  94.          VAdd (Intersection_Point, Intersection_Point, Ray -> Initial);
  95.          Local_Element.Point = Intersection_Point;
  96.          Local_Element.Shape = (SHAPE *) Shape;
  97.          pq_add (Depth_Queue, &Local_Element);
  98.          Intersection_Found = TRUE;
  99.          }
  100.       }
  101.    return (Intersection_Found);
  102.    }
  103.  
  104. int Intersect_Quadric (Ray, Shape, Depth1, Depth2)
  105.    RAY *Ray;
  106.    QUADRIC *Shape;
  107.    DBL *Depth1, *Depth2;
  108.    {
  109.    register DBL Square_Term, Linear_Term, Constant_Term, Temp_Term;
  110.    register DBL Determinant, Determinant_2, A2, BMinus;
  111.  
  112.    Ray_Quadric_Tests++;
  113.    if (!Ray->Quadric_Constants_Cached)
  114.       Make_Ray(Ray);
  115.  
  116.    if (Shape -> Non_Zero_Square_Term)
  117.       {
  118.       VDot (Square_Term, Shape -> Object_2_Terms, Ray -> Direction_2);
  119.       VDot (Temp_Term, Shape -> Object_Mixed_Terms, Ray -> Mixed_Dir_Dir);
  120.       Square_Term += Temp_Term;
  121.       }
  122.    else
  123.       Square_Term = 0.0;
  124.  
  125.    VDot (Linear_Term, Shape -> Object_2_Terms, Ray -> Initial_Direction);
  126.    Linear_Term *= 2.0;
  127.    VDot (Temp_Term, Shape -> Object_Terms, Ray -> Direction);
  128.    Linear_Term += Temp_Term;
  129.    VDot (Temp_Term, Shape -> Object_Mixed_Terms, Ray -> Mixed_Init_Dir);
  130.    Linear_Term += Temp_Term;
  131.  
  132.    if (Ray == VP_Ray)
  133.       if (!Shape -> Constant_Cached)
  134.          {
  135.          VDot (Constant_Term, Shape -> Object_2_Terms, Ray -> Initial_2);
  136.          VDot (Temp_Term, Shape -> Object_Terms, Ray -> Initial);
  137.          Constant_Term +=  Temp_Term + Shape -> Object_Constant;
  138.          Shape -> Object_VP_Constant = Constant_Term;
  139.          Shape -> Constant_Cached = TRUE;
  140.          }
  141.       else
  142.          Constant_Term = Shape -> Object_VP_Constant;
  143.    else
  144.       {
  145.       VDot (Constant_Term, Shape -> Object_2_Terms, Ray -> Initial_2);
  146.       VDot (Temp_Term, Shape -> Object_Terms, Ray -> Initial);
  147.       Constant_Term += Temp_Term + Shape -> Object_Constant;
  148.       }
  149.  
  150.    VDot (Temp_Term, Shape -> Object_Mixed_Terms, 
  151.          Ray -> Mixed_Initial_Initial);
  152.    Constant_Term += Temp_Term;
  153.  
  154.    if (Square_Term != 0.0)
  155.       {
  156.   /* The equation is quadratic - find its roots */
  157.  
  158.       Determinant_2 = Linear_Term * Linear_Term - 4.0 * Square_Term * Constant_Term;
  159.  
  160.       if (Determinant_2 < 0.0)
  161.          return (FALSE);
  162.  
  163.       Determinant = sqrt (Determinant_2);
  164.       A2 = Square_Term * 2.0;
  165.       BMinus = Linear_Term * -1.0;
  166.  
  167.       *Depth1 = (BMinus + Determinant) / A2;
  168.       *Depth2 = (BMinus - Determinant) / A2;
  169.       }
  170.    else
  171.       {
  172.     /* There are no quadratic terms.  Solve the linear equation instead. */
  173.       if (Linear_Term == 0.0)
  174.          return (FALSE);
  175.  
  176.       *Depth1 = Constant_Term * -1.0 / Linear_Term;
  177.       *Depth2 = *Depth1;
  178.       }
  179.  
  180.    if ((*Depth1 < Small_Tolerance) || (*Depth1 > Max_Distance))
  181.       if ((*Depth2 < Small_Tolerance) || (*Depth2 > Max_Distance))
  182.          return (FALSE);
  183.       else
  184.          *Depth1 = *Depth2;
  185.    else
  186.       if ((*Depth2 < Small_Tolerance) || (*Depth2 > Max_Distance))
  187.         *Depth2 = *Depth1;
  188.  
  189.    Ray_Quadric_Tests_Succeeded++;
  190.    return (TRUE);
  191.    }
  192.  
  193. int Inside_Quadric (Point, Object)
  194.    VECTOR *Point;
  195.    OBJECT *Object;
  196.    {
  197.    QUADRIC *Shape = (QUADRIC *) Object;
  198.    VECTOR New_Point;
  199.    register DBL Result, Linear_Term, Square_Term;
  200.  
  201.    VDot (Linear_Term, *Point, Shape -> Object_Terms);
  202.    Result = Linear_Term + Shape -> Object_Constant;
  203.    VSquareTerms (New_Point, *Point);
  204.    VDot (Square_Term, New_Point, Shape -> Object_2_Terms);
  205.    Result += Square_Term;
  206.    Result += Shape -> Object_Mixed_Terms.x * (Point -> x) * (Point -> y)
  207.             + Shape -> Object_Mixed_Terms.y * (Point -> x) * (Point -> z)
  208.             + Shape -> Object_Mixed_Terms.z * (Point -> y) * (Point -> z);
  209.  
  210.    if (Result < Small_Tolerance)
  211.       return (TRUE);
  212.  
  213.    return (FALSE);
  214.    }
  215.  
  216. void Quadric_Normal (Result, Object, Intersection_Point)
  217.    VECTOR *Result, *Intersection_Point;
  218.    OBJECT *Object;
  219.    {
  220.    QUADRIC *Intersection_Shape = (QUADRIC *) Object;
  221.    VECTOR Derivative_Linear;
  222.  
  223.    VScale (Derivative_Linear, Intersection_Shape -> Object_2_Terms, 2.0);
  224.    VEvaluate (*Result, Derivative_Linear, *Intersection_Point);
  225.    VAdd (*Result, *Result, Intersection_Shape -> Object_Terms);
  226.  
  227.    Result -> x += 
  228.          Intersection_Shape -> Object_Mixed_Terms.x * Intersection_Point -> y +
  229.          Intersection_Shape -> Object_Mixed_Terms.y * Intersection_Point -> z;
  230.  
  231.  
  232.    Result -> y +=
  233.          Intersection_Shape -> Object_Mixed_Terms.x * Intersection_Point -> x +
  234.          Intersection_Shape -> Object_Mixed_Terms.z * Intersection_Point -> z;
  235.  
  236.    Result -> z +=
  237.          Intersection_Shape -> Object_Mixed_Terms.y * Intersection_Point -> x +
  238.          Intersection_Shape -> Object_Mixed_Terms.z * Intersection_Point -> y;
  239.  
  240.    VNormalize (*Result, *Result);
  241.    Perturb_Normal (Result, Intersection_Shape -> Parent_Object,
  242.                    Intersection_Point, Result);
  243.    }
  244.  
  245. void *Copy_Quadric (Object)
  246.    OBJECT *Object;
  247.    {
  248.    QUADRIC *New_Shape;
  249.  
  250.    New_Shape = Get_Quadric_Shape ();
  251.    *New_Shape = *((QUADRIC *) Object);
  252.    New_Shape -> Next_Object = NULL;
  253.    return (New_Shape);
  254.    }
  255.  
  256. void Transform_Quadric (Shape, Transformation)
  257.    QUADRIC *Shape;
  258.    TRANSFORMATION *Transformation;
  259.    {
  260.    MATRIX Quadric_Matrix, Transform_Transposed;
  261.  
  262.    Quadric_To_Matrix (Shape, (MATRIX *) &Quadric_Matrix[0][0]);
  263.    MTimes ((MATRIX *) &Quadric_Matrix[0][0], (MATRIX *) &(Transformation -> inverse[0][0]), (MATRIX *) &Quadric_Matrix[0][0]);
  264.    MTranspose ((MATRIX *) &Transform_Transposed[0][0], (MATRIX *) &(Transformation -> inverse[0][0]));
  265.    MTimes ((MATRIX *) &Quadric_Matrix[0][0], (MATRIX *) &Quadric_Matrix[0][0], (MATRIX *) &Transform_Transposed[0][0]);
  266.    Matrix_To_Quadric ((MATRIX *) &Quadric_Matrix[0][0], Shape);
  267.    }
  268.  
  269. void Quadric_To_Matrix (Quadric, Matrix)
  270.    QUADRIC *Quadric;
  271.    MATRIX *Matrix;
  272.    {
  273.    MZero (Matrix);
  274.    (*Matrix)[0][0] = Quadric -> Object_2_Terms.x;
  275.    (*Matrix)[1][1] = Quadric -> Object_2_Terms.y;
  276.    (*Matrix)[2][2] = Quadric -> Object_2_Terms.z;
  277.    (*Matrix)[0][1] = Quadric -> Object_Mixed_Terms.x;
  278.    (*Matrix)[0][2] = Quadric -> Object_Mixed_Terms.y;
  279.    (*Matrix)[0][3] = Quadric -> Object_Terms.x;
  280.    (*Matrix)[1][2] = Quadric -> Object_Mixed_Terms.z;
  281.    (*Matrix)[1][3] = Quadric -> Object_Terms.y;
  282.    (*Matrix)[2][3] = Quadric -> Object_Terms.z;
  283.    (*Matrix)[3][3] = Quadric -> Object_Constant;
  284.    }
  285.  
  286. void Matrix_To_Quadric (Matrix, Quadric)
  287.    MATRIX *Matrix;
  288.    QUADRIC *Quadric;
  289.    {
  290.    Quadric -> Object_2_Terms.x = (*Matrix)[0][0];
  291.    Quadric -> Object_2_Terms.y = (*Matrix)[1][1];
  292.    Quadric -> Object_2_Terms.z = (*Matrix)[2][2];
  293.    Quadric -> Object_Mixed_Terms.x = (*Matrix)[0][1] + (*Matrix)[1][0];
  294.    Quadric -> Object_Mixed_Terms.y = (*Matrix)[0][2] + (*Matrix)[2][0];
  295.    Quadric -> Object_Terms.x = (*Matrix)[0][3] + (*Matrix)[3][0];
  296.    Quadric -> Object_Mixed_Terms.z = (*Matrix)[1][2] + (*Matrix)[2][1];
  297.    Quadric -> Object_Terms.y = (*Matrix)[1][3] + (*Matrix)[3][1];
  298.    Quadric -> Object_Terms.z = (*Matrix)[2][3] + (*Matrix)[3][2];
  299.    Quadric -> Object_Constant = (*Matrix)[3][3];
  300.    }
  301.  
  302. void Translate_Quadric (Object, Vector)
  303.    OBJECT *Object;
  304.    VECTOR *Vector;
  305.    {
  306.    TRANSFORMATION Transformation;
  307.  
  308.    Get_Translation_Transformation (&Transformation, Vector);
  309.    Transform_Quadric ((QUADRIC *) Object, &Transformation);
  310.    }
  311.  
  312. void Rotate_Quadric (Object, Vector)
  313.    OBJECT *Object;
  314.    VECTOR *Vector;
  315.    {
  316.    TRANSFORMATION Transformation;
  317.  
  318.    Get_Rotation_Transformation (&Transformation, Vector);
  319.    Transform_Quadric ((QUADRIC *) Object, &Transformation);
  320.    }
  321.  
  322. void Scale_Quadric (Object, Vector)
  323.    OBJECT *Object;
  324.    VECTOR *Vector;
  325.    {
  326.    TRANSFORMATION Transformation;
  327.  
  328.    Get_Scaling_Transformation (&Transformation, Vector);
  329.    Transform_Quadric ((QUADRIC *) Object, &Transformation);
  330.    }
  331.  
  332. void Invert_Quadric (Object)
  333.    OBJECT *Object;
  334.    {
  335.    QUADRIC *Shape = (QUADRIC *) Object;
  336.  
  337.    VScale (Shape -> Object_2_Terms, Shape -> Object_2_Terms, -1.0);
  338.    VScale (Shape -> Object_Mixed_Terms, Shape -> Object_Mixed_Terms, -1.0);
  339.    VScale (Shape -> Object_Terms, Shape -> Object_Terms, -1.0);
  340.    Shape -> Object_Constant *= -1.0;
  341.    }
  342.