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