home *** CD-ROM | disk | FTP | other *** search
/ Peanuts NeXT Software Archives / Peanuts-Update.iso / CDROM / Contents / READMEs / Peanuts-3 / Tools / screen / backspace / old / Voronoi.README < prev    next >
Encoding:
Text File  |  1996-11-09  |  3.8 KB  |  83 lines
  1. This directory contains the source and binaries for the VoronoiView
  2. BackSpace module.  When invoked, VoronoiView scatters a random
  3. number of dots (`sites') on the screen, builds the Voronoi tessellation
  4. of that point set, and displays the points and Voronoi polygons in
  5. vibrant color (unless your screen is monochrome).  After remaining
  6. idle for some time period, it then clears the display and repeats
  7. the process with a new batch of sites.
  8.  
  9. On my NextDimension, VoronoiView consumes very little CPU time when running,
  10. which gives it some advantages over some other BackSpace modules that have
  11. floated across the Net recently.  It also (hopefully) should not cause burn-in.
  12.  
  13. How to install VoronoiView:
  14. ---------------------------
  15. 1. Set INSTALLDIR in the Makefile.  I always put my Views in the app wrapper.
  16. 2. Change the parameters in VoronoiViewPart.m if desired (see below)
  17. 3. make install
  18.  
  19. Three user-settable parameters at the top of VoronoiViewPart.m
  20. --------------------------------------------------------------
  21. The width (in pixels) of the polygon edges and site dots is WIDTH.
  22. Its default value is 2.0.
  23.  
  24. The maximum number of sites is BS_MAXSITES (default 100).
  25. ******* DANGER *****************************************************
  26. * The voronoi code (see below) uses a parameter called MAXSITES    *
  27. * (#defined in voronoi,h, default value 4096).  BS_MAXSITES SHOULD *
  28. * BE NO LARGER THAN MAXSITES.  Why you would want more than 4096   *
  29. * sites is beyond me.  256 is plenty.                              *
  30. ******* REGNAD *****************************************************
  31.  
  32. The number of idle seconds between generations is IDLESECONDS (default 30).
  33.  
  34. What's atan2.o doing in there?
  35. ------------------------------
  36. Well, I had to extract atan2.o from the math library in order to
  37. get VoronoiView to work.  atan2() is used by the Voronoi code in
  38. VoronoiViewPart.m.  It is apparently NOT linked into BackSpace as
  39. compiled under the defaults.  So we need to supply it to BackSpace
  40. in our view class .o file.
  41.  
  42. Voronoi code
  43. ------------
  44. The actual code for the 2D voronoi tessellation was written by Seth
  45. Teller (of SGI, I think); I ripped it out of 2DLab (available at
  46. your fave archive site) and wrote the View glue to make it run
  47. within BackSpace.  As originally distributed (it is available from
  48. many archive sites), the code was in a bunch of .c and .h files.
  49. To make this module simple, I took all the C code and mashed it
  50. into VoronoiViewPart.m . Yeah, I know that's ugly.  misc.h, voronoi.h,
  51. headers.s, and vector.h are needed by that code, so don't delete
  52. them.
  53.  
  54. Possible additions/changes that I'm too lazy to implement
  55. ---------------------------------------------------------
  56. 1. Delaunay triangulation (or Gabriel graph, or Relative neighborhood graph)
  57.    instead of Voronoi diagram.  This is probably about 6 lines of code.
  58.    I suppose you could do the MST as well, or a convex hull.
  59.  
  60. 2. Detect what kind of screen we're running under. (Feh. Why bother? The window
  61.    is unbuffered).
  62.  
  63. 3. Fill in the polygons instead of outlining them.  Or outline the sites instead
  64.    of filling them.  Be my guest.  Beware of burn-in!
  65.  
  66. 4. Replace the 2% shrinking-polygon hack with something a little more
  67.    sophisticated.  The whole idea of shrining the polygons was to have edges
  68.    appear in multiple colors.  Unfortunately, sparse site distributions produce
  69.    disconnected Voronoi polygons.
  70.  
  71. 5. Incorporate some pre-specified, structured site distributions (e.g. samples
  72.    from a circle, or an ellipse, etc.) instead of the current random (uniform)
  73.    2D distribution.  Or perhaps samples from a bivariate Gaussian
  74.    (or some other) distribution. Such ideas should be easy to implement.
  75.  
  76. Author
  77. ------
  78. Patrick J. Flynn
  79. School of Electrical Engineering and Computer Science
  80. Washington State University
  81. Pullman, WA 99164-2752
  82. flynn@eecs.wsu.edu
  83.