home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsi / tripnts.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-15  |  2.7 KB  |  104 lines
  1. /* 
  2. Generating Random Points in Triangles
  3. by Greg Turk
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include <math.h>
  8. #include "GraphicsGems.h"
  9.  
  10. /*****************************************************************
  11. Compute relative areas of sub-triangles that form a convex polygon.
  12. There are vcount-2 sub-triangles, each defined by the first point
  13. in the polygon and two other adjacent points.
  14.  
  15. This procedure should be called once before using 
  16. square_to_polygon().
  17.  
  18. Entry:
  19.   vertices - list of the vertices of a convex polygon
  20.   vcount   - number of vertices of polygon
  21. Exit:
  22.   areas - relative areas of sub-triangles of polygon
  23. *******************************************************************/
  24.  
  25. triangle_areas (vertices, vcount, areas)
  26.       Point3 vertices[];
  27.     int vcount;
  28.       float areas[];
  29. {
  30.       int i;
  31.       float area_sum = 0;
  32.       Vector3 v1,v2,v3;
  33.  
  34.   /* compute relative areas of the sub-triangles of polygon */
  35.  
  36.       for (i = 0; i < vcount - 2; i++) {
  37.          V3Sub(&vertices[i+1], &vertices[0], &v1);
  38.          V3Sub(&vertices[i+2], &vertices[0], &v2);
  39.          V3Cross(&v1, &v2, &v3);
  40.          areas[i] = V3Length(&v3);
  41.          area_sum += areas[i];
  42.   }
  43.  
  44.   /* normalize areas so that the sum of all sub-triangles is one */
  45.  
  46.       for (i = 0; i < vcount - 2; i++)
  47.         areas[i] /= area_sum;
  48. }
  49.  
  50.  
  51. /******************************************************************
  52. Map a point from the square [0,1] x [0,1] into a convex polygon.
  53. Uniform random points in the square will generate uniform random 
  54. points in the polygon.
  55.  
  56. The procedure triangle_areas() must be called once to compute 
  57. 'areas', and then this procedure can be called repeatedly.
  58.  
  59. Entry:
  60.   vertices - list of the vertices of a convex polygon
  61.   vcount   - number of vertices of polygon
  62.   areas    - relative areas of sub-triangles of polygon
  63.   s,t      - position in the square [0,1] x [0,1]
  64. Exit:
  65.   p - position in polygon
  66. *********************************************************************/
  67.  
  68. square_to_polygon (vertices, vcount, areas, s, t, p)
  69.      Point3 vertices[];
  70.       int vcount;
  71.       float areas[];
  72.       float s,t;
  73.       Point3 *p;
  74. { 
  75.     int i;
  76.     float area_sum = 0;
  77.       float a,b,c;
  78.  
  79.   /* use 's' to pick one sub-triangle, weighted by relative */
  80.   /* area of triangles */
  81.  
  82.       for (i = 0; i < vcount - 2; i++) {
  83.         area_sum += areas[i];
  84.         if (area_sum >= s)
  85.               break;
  86.   }
  87.  
  88.   /* map 's' into the interval [0,1] */
  89.  
  90.   s = (s - area_sum + areas[i]) / areas[i];
  91.  
  92.   /* map (s,t) to a point in that sub-triangle */
  93.  
  94.   t = sqrt(t);
  95.  
  96.   a = 1 - t;
  97.   b = (1 - s) * t;
  98.   c = s * t;
  99.  
  100.   p->x = a * vertices[0].x + b * vertices[i+1].x + c * vertices[i+2].x;
  101.   p->y = a * vertices[0].y + b * vertices[i+1].y + c * vertices[i+2].y;
  102.   p->z = a * vertices[0].z + b * vertices[i+1].z + c * vertices[i+2].z;
  103. }
  104.