chrisp@bilby.cs.uwa.oz.au (Chris Pudney) (04/09/91)
[sorry for the delay - our news dirs have been full] G'day, As promised here are the responses I received to my posting concerning surface contouring: From: gillam@aerospace.aero.org I would also be interested in what you find out. There is a book which has some papers on contour plotting, but I don't have the time to implement them. I haven't read them, just noticed they were on the topic. They're in FUNDAMENTAL ALGORITHMS for COMPUTER GRAPHICS edited by R.A. Earnshaw Springer Verlag - April Gillam The Aerospace Corp. gillam@aerospace.aero.org ------------------------------------------------------------------------------- From: sundar@ai.mit.edu (Sundar Narasimhan) Look at ftp.ai.mit.edu:/com/ftp/pub/users/sundar/graph.tar.Z This contains a contour plotting algorithm. [I obtained and compiled this for a Sparc 1. Is a library of X graphing functions including contouring] ------------------------------------------------------------------------------- From: gershon%gr@cs.utah.edu (Elber Gershon) Anonymous ftp gnuplot2.02 from cs.duke.edu and gnuplot3d.shar.Z from cs.utah.edu directory. The later includes patches for the former to do what you want with all the power of gnuplot. Gershon -- Elber Gershon gershon@cs.utah.edu 918 University village Salt Lake City 84108-1180 Tel: (801) 582-1807 (Home) Utah Tel: (801) 581-7888 (Work) [I obtained and compiled this for a Sparc 1. Big (in comparison with graph) but is very useful for graphing analytic functions as well as sampled data.] ------------------------------------------------------------------------------ From: pdbourke@ccu1.aukuni.ac.nz A few years ago I wrote an article for BYTE magazine on just such an algorithm, in fact from memory the example I used was of a potential field. I don't have the article here (it's at home somewhere along with the source code) but it appeared I think in the June/July issue in either 1987 or 1988. It was titled CONREC - A Contouring Algorithm. Briefly - it contoured any rectangular grid of points. To contour a surface described by a function one would first evaluate the function on a rectangular mesh (not necessarily a regular spaced mesh) and pass that data onto the contouring program. One of the main features of the program was that it was very efficient, ie: even version in BASIC were quite fast. Have a look in past issues of BYTE, if you can't find it I can send the code in BASIC or FORTRAN (maybe C). ------------------------------------------------------------------------------ From: alice@athena.mit.edu I've got several; you can get back to me for detailed explanations. All work with rectangular grids. 1) divide each grid square into four triangles (average the four corners for the middle point. For a given value, store a segment for each crossing of that value on two edges of a triangle. Draw the segments. This handles ravines/ridges nicely. 2) go through the entire grid for each contour, tracing a particular value from where it starts until you return to the original square. This method is more complicated, but is necessary if you want your contours to be closed polygons (shading/discrete coloring) or if you want to label the contours, both of which are important for clarity. I wrote an application which uses the second method. If you want a copy, (it's written for X11, R3 or later, with athena widgets) email me and I can give you the ftp address (the machine is down right now but should be up within the week). Given a data file in simple grid format, it draws shaded or unshaded contours, provides a legend, and produces PostScript output. It also tracks the value under the cursor. We use it for similar purposes, viewing geological data, contamination plumes, etc. Let me know if I can help further. Timothy Wall alice@athena.mit.edu Parsons Water Resources Lab, MIT alice@maya.mit.edu 4 Ames Street Cambridge, MA 02139 Phone: 617-225-6607 ------------------------------------------------------------------------------ [A while D. Moore sent me the following list of responses to his enquiries about contour references] From: "Dwight D. Moore" <DWIGHT@geo785.gcn.uoknor.edu> G'day Chris, These are the responses I have recieved thus far. I haven't had a chance yet to look up any of these resources yet, but I would appreciate any progress you make, also. The last guy (Shane Miller) even called me up on the phone to see if he could help; he seemed rather eager.. Dwight D. Moore Geosciences Computing Network University of Oklahoma work address: dwight@geohub.gcn.uoknor.edu other: dwight@uokmax.ecn.uoknor.edu ------------------------------------------------------------------------------- >>From ted@aps1.spa.umn.edu Wed Oct 10 12:13:20 1990 > >One source is "Pattern Classification adn Scene Analysis" by >Duda and Hart. p. 290-293 >John Wiley and Sons, 1973 > >-- >Ted Stockwell U of MN, Dept. of Astronomy >ted@aps1.spa.umn.edu Automated Plate Scanner Project >------------------------------------------------------------------------------- >>From thomson@cs.utah.edu Wed Oct 10 19:45:32 1990 > >I remember seeing an algorithm for contouring data sets in ACM >Transactions on Mathematical Software (or something like that) in the >Summer of 1988. It was a recent issue at that time. It probably only >comes out quarterly, so it shouldn't be hard to find if you're >browsing through the issues. > > -- Rich >-- >Rich Thomson thomson@cs.utah.edu {bellcore,hplabs,uunet}!utah-cs!thomson >------------------------------------------------------------------------------- >>From chooft@fys.ruu.nl Thu Oct 11 02:42:17 1990 > >Do you need 2d or 3d algorithms? 2d is quite simple. Take a grid. Make a >linear interpolation on all grid-lines that pass your "value". Connect all >points found (this can be done by drawing straight lines, splines, or circle- >segments, whatever you want). The only problem that can arise using this >algorithm is that all four sides of a gridsquare have a point, then you don't >know which ones to connect. > >-- >Rob Hooft, Chemistry department University of Utrecht. >hooft@hutruu54.bitnet hooft@chem.ruu.nl chooft@fys.ruu.nl >------------------------------------------------------------------------------- >>From uselton@wk207.nas.nasa.gov Thu Oct 11 12:14:48 1990 > >Your question is not specific enough to be sure a particular >response describes what you are after. > >Do you want algorithm(s) to find contours? In what context? from what input? > >Best bet: Check Image Processing books, eg Pavlidis, _Computer_Graphics_&_ >Image_Processing - a reasonable survey with lots of code to crib from. > >Do you want algorithm(s) that perform some operations ON contours? >what operations? display? surface tiling? comparison? .... > >Display is pretty trivial. Any graphics program should display contours >as polygons as long as the linit on number of vertices per polygon is >large enough. > >Surface tiling - My favorite is Fuchs, Kedem, Uselton "Optimal Surface >Reconstruction from Planar Contours", CACM Oct. 1977. (But I'm biased...) >There are several strategies published in research literature, and work >continues... > >Comparison - back to the image processing community,... > >Hope this helps. Or you could ask the question with more details. > >Sam Uselton uselton@nas.nasa.gov >employed by CSC working for NASA speaking for myself >------------------------------------------------------------------------------- >>From @cca.ucsf.EDU:smiller@wet.UUCP Mon Oct 15 19:57:57 1990 > >It is funny you should post that question. I've just finished one for >iso-rectangles. Look at the Shamos/Preparata computational geometry >book for sure. Second, obtain the Lipski/Preparata original article >on the subject from the J. of Algorithms 1980. Be sure to get the >corrections of the original article from J. of Algorithms 1982. > >Again, I've implemented their algorithm per info from above. They use >a sweep line with segment tree (via Bentely). > >What are you trying to find a contour of? SMT, analog, digital? For >what application. I would be interested in seeing what your doing. > >Regards, > >-- >-- >G. Shane Miller [ smiller@wet.UUCP ] Von Neumann eat your heart out! > >------------------------------------------------------------------------------- -- -------------------------------------------------------------------------------- Chris Pudney Department of Computer Science, PHONE: (local: 09) (int'l: +61 9) 380 3455