From: orourke@cs.smith.edu (Joseph O'Rourke)
Newsgroups: comp.graphics.algorithms,news.answers,comp.answers
Subject: comp.graphics.algorithms Frequently Asked Questions
Date: 15 Jun 1996 06:44:45 GMT
Organization: Smith College, Dept. of Computer Science
Welcome to the FAQ for comp.graphics.algorithms!
Thanks to all who have contributed. Corrections and contributions
(to orourke@cs.smith.edu) always welcome.
| Changed items this posting: 2.03
+ New items this posting: 5.16
----------------------------------------------------------------------
Table of Contents
----------------------------------------------------------------------
0. General Information
0.01: Charter of comp.graphics.algorithms
0.02: Are the postings to comp.graphics.algorithms archived?
0.03: How can I get this FAQ?
0.04: What are some must have books on graphics algorithms?
0.05: Are there any online references?
0.06: Are there other graphics related FAQs?
0.07: Where is all the source?
1. 2D Computations: Points, Segments, Circles, Etc.
1.01: How do I rotate a 2D point?
1.02: How do I find the distance from a point to a line?
1.03: How do I find intersections of 2 2D line segments?
1.04: How do I generate a circle through three points?
1.05: Where can I find graph layout algorithms?
2. 2D Polygon Computations
2.01: How do I find the area of a polygon?
2.02: How can the centroid of a polygon be computed?
| 2.03: How do I find if a point lies within a polygon?
2.04: How do I find the intersection of two convex polygons?
2.05: How do I do a hidden surface test (backface culling) with 2d points?
2.06: How do I find a single point inside a simple polygon?
2.07: How do I find the orientation of a simple polygon?
3. 2D Image/Pixel Computations
3.01: How do I rotate a bitmap?
3.02: How do I display a 24 bit image in 8 bits?
3.03: How do I fill the area of an arbitrary shape?
3.04: How do I find the 'edges' in a bitmap?
3.05: How do I enlarge/sharpen/fuzz a bitmap?
3.06: How do I map a texture on to a shape?
3.07: How do I detect a 'corner' in a collection of points?
3.08: Where do I get source to display (raster font format)?
3.09: What is morphing/how is it done?
3.10: How do I quickly draw a filled triangle?
3.11: D Noise functions and turbulence in Solid texturing.
3.12: How do I generate realistic sythetic textures?
3.13: How do I convert between color models (RGB, HLS, CMYK, CIE etc)?
4. Curve Computations
4.01: How do I generate a bezier curve that is parallel to another bezier?
4.02: How do I split a bezier at a specific value for t?
4.03: How do I find a t value at a specific point on a bezier?
4.04: How do I fit a bezier curve to a circle?
5. 3D computations
5.01: How do I rotate a 3D point?
5.02: What is ARCBALL and where is the source?
5.03: How do I clip a polygon against a rectangle?
5.04: How do I clip a polygon against another polygon?
5.05: How do I find the intersection of a line and a plane?
5.06: How do I determine the intersection between a ray and a polygon?
5.07: How do I determine the intersection between a ray and a sphere?
5.08: How do I find the intersection of a ray and a bezier surface?
5.09: How do I ray trace caustics?
5.10: What is the marching cubes algorithm?
5.11: What is the status of the patent on the "marching cubes" algorithm?
5.12: How do I do a hidden surface test (backface culling) with 3d points?
5.13: Where can I find algorithms for 3D collision detection?
5.14: How do I perform basic viewing in 3d?
5.15: How do I optimize a 3D polygon mesh?
+ 5.16 How can I perform volume rendering?
6. Geometric Structures and Mathematics
6.01: Where can I get source for Voronoi/Delaunay triangulation?
6.02: Where do I get source for convex hull?
6.03: Where do I get source for halfspace intersection?
6.04: What are barycentric coordinates?
6.05: How do I generate a random point inside a triangle?
6.06: How do I evenly distribute N points on (tesselate) a sphere?
6.07: What are coordinates for the vertices of an icosohedron?
6.08: How do I generate random points on the surface of a sphere?
7. Contributors
7.01: How can you contribute to this FAQ?
7.02: Contributors. Who made this all possible.
Search e.g. for "Section 6" to find that section.
Search e.g. for "Subject 6.04" to find that item.
----------------------------------------------------------------------
Section 0. General Information
----------------------------------------------------------------------
Subject 0.01: Charter of comp.graphics.algorithms
comp.graphics.algorithms is an unmoderated newsgroup intended as a forum
for the discussion of the algorithms used in the process of generating
computer graphics. These algorithms may be recently proposed in
published journals or papers, old or previously known algorithms, or
hacks used incidental to the process of computer graphics. The scope of
these algorithms may range from an efficient way to multiply matrices,
all the way to a global illumination method incorporating raytracing,
radiosity, infinite spectrum modeling, and perhaps even mirrored balls
and lime jello.
It is hoped that this group will serve as a forum for programmers and
researchers to exchange ideas and ask questions on recent papers or
current research related to computer graphics.
comp.graphics.algorithms is not:
- for requests for gifs, or other pictures
- for requests for image translator or processing software; see
alt.binaries.pictures* FAQ
alt.binaries.pictures.utilities (picture source code)
alt.graphics.pixutils (image format translation)
comp.sources.misc (image viewing source code)
sci.image.processing
comp.graphics.apps.softimage
fj.comp.image
- for requests for compression software; for these try:
alt.comp.compression
comp.compression
comp.compression.research
----------------------------------------------------------------------
Subject 0.02: Are the postings to comp.graphics.algorithms archived?
Archives may be found at:
ftp://wuarchive.wustl.edu/graphics/graphics/mail-lists/comp.graphics.algorithms
It is archived in the same manner that all other newsgroups are
being archived there, namely there is an Index file with all the
subjects, and all the articles are being kept in a hierarchy based
on the year and month they are posted.
----------------------------------------------------------------------
Subject 0.03: How can I get this FAQ?
Here are a few locations that have the FAQ:
http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html
ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/graphics/algorithms-faq
ftp://ftp.seas.gwu.edu/pub/rtfm/comp/graphics/algorithms/comp.graphics.algorithms_Frequently_Asked_Questions
The (busy) rtfm.mit.edu site lists many alternative "mirror" sites.
Also can reach the FAQ from http://www.geom.umn.edu/software/cglist/,
which is worth visiting in its own right.
----------------------------------------------------------------------
Subject 0.04: What are some must have books on graphics algorithms?
The keywords in brackets are used to refer to the books in later
questions. They generally refer to the first author except where
it is necessary to resolve ambiguity or in the case of the Gems.
Basic computer graphics, rendering algorithms,
----------------------------------------------
[Foley]
Computer Graphics: Principles and Practice (2nd Ed.),
J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley
1990, ISBN 0-201-12110-7
[Rogers:Procedural]
Procedural Elements for Computer Graphics,
David F. Rogers, McGraw Hill 1985, ISBN 0-07-053534-5
[Rogers:Mathematical]
Mathematical Elements for Computer Graphics 2nd Ed.,
David F. Rogers and J. Alan Adams, McGraw Hill 1990, ISBN
0-07-053530-2
[Watt:3D]
_3D Computer Graphics, 2nd Edition_,
Alan Watt, Addison-Wesley 1993, ISBN 0-201-63186-5
[Glassner:RayTracing]
An Introduction to Ray Tracing,
Andrew Glassner (ed.), Academic Press 1989, ISBN 0-12-286160-4
[Gems I]
Graphics Gems,
Andrew Glassner (ed.), Academic Press 1990, ISBN 0-12-286165-5
[Gems II]
Graphics Gems II,
James Arvo (ed.), Academic Press 1991, ISBN 0-12-64480-0
[Gems III]
Graphics Gems III,
David Kirk (ed.), Academic Press 1992, ISBN 0-12-409670-0 (with
IBM disk) or 0-12-409671-9 (with Mac disk)
[Gems IV]
Graphics Gems IV,
Paul S. Heckbert (ed.), Academic Press 1994, ISBN 0-12-336155-9
(with IBM disk) or 0-12-336156-7 (with Mac disk)
[Gems V]
Graphic Gems V,
Alan W. Paeth (ed.), Academic Press 1995, ISBN 0-12-543455-3
(with IBM disk)
[Watt:Animation]
Advanced Animation and Rendering Techniques,
Alan Watt, Mark Watt, Addison-Wesley 1992, ISBN 0-201-54412-1
[Bartels]
An Introduction to Splines for Use in Computer Graphics and
Geometric Modeling,
Richard H. Bartels, John C. Beatty, Brian A. Barsky, 1987, ISBN
0-934613-27-3
[Farin]
Curves and Surfaces for Computer Aided Geometric Design:
A Practical Guide, 3rd Edition, Gerald E. Farin, Academic Press
1993. ISBN 0-12-249052-5
[Prusinkiewicz]
The Algorithmic Beauty of Plants,
Przemyslaw W. Prusinkiewicz, Aristid Lindenmayer, Springer-Verlag,
1990, ISBN 0-387-97297-8, ISBN 3-540-97297-8
[Oliver]
Tricks of the Graphics Gurus,
Dick Oliver, et al. (2) 3.5 PC disks included, $39.95 SAMS Publishing
[Hearn]
Introduction to computer graphics,
Hearn & Baker
[Cohen]
Radiosity and Realistic Imange Sythesis,
Michael F. Cohen, John R. Wallace, Academic Press Professional
1993, ISBN 0-12-178270-0
[Ebert]
Texturing and Modeling - A Procedural Approach
David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin,
Setven Worley, Academic Press 1994, ISBN 0-12-228760-6,
ISBN 0-12-2278761-4 (IBM disk)
[Schroeder]
Visualization Toolkit, The: An Object-Oriented Approach to 3-D
Graphics (Bk/CD) (Professional Description)
William J. Schroeder, Kenneth Martin and Bill Lorensen,
Prentice-Hall 1996, ISBN: 0-13-199837-4 (Published: 02/02/96)
[Anderson]
PC Graphics Unleashed
Scott Anderson. SAMS Publishing, ISBN 0-672-30570-4
For image processing,
---------------------
[Barnsley]
Fractal Image Compression,
Michael F. Barnsley and Lyman P. Hurd, AK Peters, Ltd, 1993 ISBN
1-56881-000-8
[Jain]
Fundamentals of Image Processing,
Anil K. Jain, Prentice-Hall 1989, ISBN 0-13-336165-9
[Castleman]
Digital Image Processing,
Kenneth R. Castleman, Prentice-Hall 1996, ISBN(Cloth): 0-13-211467-4
(Description and errata at: "http://www.phoenix.net/~castlman")
[Pratt]
Digital Image Processing, Second Edition,
William K. Pratt, Wiley-Interscience 1991, ISBN 0-471-85766-1
[Gonzalez]
Digital Image Processing (3rd Ed.),
Rafael C. Gonzalez, Paul Wintz, Addison-Wesley 1992, ISBN
0-201-50803-6
[Russ]
The Image Processing Handbook,
John C. Russ, CRC Press 1992, ISBN 0-8493-4233-3
[Wolberg]
Digital Image Warping,
George Wolberg, IEEE Computer Society Press Monograph 1990, ISBN
0-8186-8944-7
Computational geometry,
----------------------
[Bowyer]
A Programmer's Geometry,
Adrian Bowyer, John Woodwark, Butterworths 1983,
ISBN 0-408-01242-0 Pbk
[O' Rourke]
Computational Geometry in C,
Joseph O'Rourke, Cambridge University Press 1994,
ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk
[Samet:Application]
Applications of Spatial Data Structures: Computer Graphics,
Image Processing, and GIS,
Hanan Samet, Addison-Wesley, Reading, MA, 1990.
ISBN 0-201-50300-0.
[Samet:Design & Analysis]
The Design and Analysis of Spatial Data Structures,
Hanan Samet, Addison-Wesley, Reading, MA, 1990.
ISBN 0-201-50255-0.
[Mortenson]
Geometric Modeling,
Michael E. Mortenson, Wiley 1985, ISBN 0-471-88279-8
[Preparata]
Computational Geometry: An Introduction,
Franco P. Preparata, Michael Ian Shamos, Springer-Verlag 1985,
ISBN 0-387-96131-3
[Okabe]
Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,
A. Okabe and B. Boots and K. Sugihara,
John Wiley, Chichester, England, 1992.
Solid Modelling
---------------
[Mantyla]
Introduction to Solid Modeling
Martti Mantyla, Computer Science Press 1988,
ISBN 07167-8015-1
----------------------------------------------------------------------
Subject 0.05: Are there any online references?
The computational geometry community maintains its own
bibliography of publications in or closely related to that
subject. Every four months, additions and corrections are
solicited from users, after which the database is updated and
released anew. As of February 1996, it contained 7,154 bib-tex
entries. It can be retrieved from
ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.Z - bibliography proper
ftp://ftp.cs.usask.ca/pub/geometry/geom.ps.Z - PostScript format
ftp://ftp.cs.usask.ca/pub/geometry/o-cgc19.ps.Z - overview published
in '93 in SIGACT News and the Internat. J. Comput. Geom. Appl.
ftp://ftp.cs.usask.ca/pub/geometry/ftp-hints - detailed retrieval info
Announcing the ACM SIGGRAPH Online Bibliography Project, by
Stephen Spencer (biblio@siggraph.org)
The database is available for anonymous FTP from the
ftp://siggraph.org/publications/bibliography directory. Please
download and examine the file READ_ME in that directory for more
specific information concerning the database.
'netlib' is a useful source for algorithms, member inquiries for
SIAM, and bibliographic searches. For information, send mail to
netlib@ornl.gov, with "send index" in the body of the mail
message.
You can also find free sources for numerical computation in C via
ftp://usc.edu/pub/C-numanal. In particular, grab
numcomp-free-c.gz in that directory.
Check out Nick Fotis's computer graphics resources FAQ -- it's
packed with pointers to all sorts of great computer graphics
stuff. This FAQ is posted biweekly to comp.graphics.
This WWW page contains links to a large number
of computer graphic related pages:
http://www.dataspace.com:84/vlib/comp-graphics.html
There's a Computer Science Bibliography Server at:
http://glimpse.cs.arizona.edu:1994/bib/
with Computer Graphics, Vision and Radiosity sections
A comprehensive bibliography of color quantization papers and articles is
available at ftp://hobbes.lbl.gov/pub/doc/cquant95.txt
Modelling physically based systems for animation:
http://www.cc.gatech.edu/gvu/animation/Animation.html
The University of Manchester NURBS Library:
ftp://unix.hensa.ac.uk/pub/misc/unix/nurbs/
For an implementation of Seidel's algorithm for fast trapezoidation
and triangulation of polygons. You can get the code from:
ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz
Ray tracing bibliography:
ftp://ftp.eye.com/pub/graphics/papers/rtbib95.tar.Z
ftp://ftp.eye.com/pub/graphics/papers/rtbib95.zip
Quaternions and other comp sci curiosities:
ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/hakmem.html
Directory of Computational Geometry Software,
collected by Nina Amenta (nina@geom.umn.edu)
Nina Amenta is maintaining a WWW directory to computational
geometry software. The directory lives at The Geometry Center.
It has pointers to lots of convex hull and voronoi diagram programs,
triangulations, collision detection, polygon intersection, smallest
enclosing ball of a point set and other stuff.
http://www.geom.umn.edu/software/cglist/lowdvod.html
----------------------------------------------------------------------
Subject 0.06: Are there other graphics related FAQs?
BSP Tree FAQ by Bretton Wade
http://www.qualia.com/bspfaq/
Gamma and Color FAQs by Charles A. Poynton has
ftp://ftp.inforamp.net/pub/users/poynton/doc/colour/
http://www.inforamp.net/~poynton/
The documents are mirrored to space provided by Fraunhofer Computer
Graphics in Rhode Island, U.S.A. at
ftp://elaine.crcg.edu/pub/doc/colour/
in Darmstadt, Germany at
ftp://ftp.igd.fhg.de/pub/doc/colour/
----------------------------------------------------------------------
Subject 0.07: Where is all the source?
Graphics Gems source code.
ftp://princeton.edu:pub/Graphics/GraphicsGems
http://grafi.elte.hu/mix/ggems/
General 'stuff'
ftp://wuarchive.wustl.edu/graphics/graphics
There are a number of interesting items in
http://theory.lcs.mit.edu/~seth including:
- Code for 2D Voronoi, Delaunay, and Convex hull
- Mike Hoymeyer's implementation of Raimund Seidel's
O( d! n ) time linear programming algorithm for
n constraints in d dimensions
- geometric models of UC Berkeley's new computer science
building
You can find useful overviews of a number of computer graphic
topics in http://archpropplan.auckland.ac.nz/People/Paul/Paul.html
including:
- area/orientation of polygons
- finding if a point lies within a polygon
- generating a circle through 3 points
- description and psuedo-code for Delaunay triangulation
- basic viewing in 3D
etc.
Sources to Computational Geometry in C", by J. O'Rourke
can be found at ftp://grendel.csc.smith.edu/pub/compgeom
Greg Ferrar has uploaded his heavily commented C++ 3D rendering
library at ftp://ftp.math.ohio-state.edu/pub/users/gregt
TAGL is a portable and extensible library that provides a subset
of Open-GL functionalities.
ftp://sunsite.unc.edu/pub/packages/programming/graphics/tagl21.tgz
Try ftp://x2ftp.oulu.fi for /pub/msdos/programming/docs/graphpro.lzh by
Michael Abrash. His XSharp package has an implementation of Xiaoulin
Wu's anti-aliasing algorithm (in C).
Example sources for BSP tree algorithms can be found in
ftp://ftp.qualia.com/pub/bspfaq/
Mel Slater (mel@dcs.qmw.ac.uk) also made some implementations of
BSP trees and shadows for static scenes using shadow volumes
code available
http://www.dcs.qmw.ac.uk/~mel/BSP.html
ftp://ftp.dcs.qmw.ac.uk/people/mel/BSP
----------------------------------------------------------------------
Section 1. 2D Computations: Points, Segments, Circles, Etc.
----------------------------------------------------------------------
Subject 1.01: How do I rotate a 2D point?
In 2-D, the 2x2 matrix is very simple. If you want to rotate a
column vector v by t degrees using matrix M, use
M = {{cos t, -sin t}, {sin t, cos t}} in M*v.
If you have a row vector, use the transpose of M (turn rows into
columns and vice versa). If you want to combine rotations, in 2-D
you can just add their angles, but in higher dimensions you must
multiply their matrices.
----------------------------------------------------------------------
Subject 1.02: How do I find the distance from a point to a line?
Let the point be C (XC,YC) and the line be AB (XA,YA) to (XB,YB).
The length of the line segment AB is L:
L=((XB-XA)**2+(YB-YA)**2)**0.5
and
(YA-YC)(YA-YB)-(XA-XC)(XB-XA)
r = -----------------------------
L**2
(YA-YC)(XB-XA)-(XA-XC)(YB-YA)
s = -----------------------------
L**2
Let I be the point of perpendicular projection of C onto AB, the
XI=XA+r(XB-XA)
YI=YA+r(YB-YA)
Distance from A to I = r*L
Distance from C to I = s*L
If r<0 I is on backward extension of AB
If r>1 I is on ahead extension of AB
If 0<=r<=1 I is on AB
If s<0 C is left of AB (you can just check the numerator)
If s>0 C is right of AB
If s=0 C is on AB
----------------------------------------------------------------------
Subject 1.03: How do I find intersections of 2 2D line segments?
This problem can be extremely easy or extremely difficult depends
on your applications. If all you want is the intersection point,
the following should work:
Let A,B,C,D be 2-space position vectors. Then the directed line
segments AB & CD are given by:
AB=A+r(B-A), r in [0,1]
CD=C+s(D-C), s in [0,1]
If AB & CD intersect, then
A+r(B-A)=C+s(D-C), or
XA+r(XB-XA)=XC+s(XD-XC)
YA+r(YB-YA)=YC+s(YD-YC) for some r,s in [0,1]
Solving the above for r and s yields
(YA-YC)(XD-XC)-(XA-XC)(YD-YC)
r = ----------------------------- (eqn 1)
(XB-XA)(YD-YC)-(YB-YA)(XD-XC)
(YA-YC)(XB-XA)-(XA-XC)(YB-YA)
s = ----------------------------- (eqn 2)
(XB-XA)(YD-YC)-(YB-YA)(XD-XC)
Let I be the position vector of the intersection point, then
I=A+r(B-A) or
XI=XA+r(XB-XA)
YI=YA+r(YB-YA)
By examining the values of r & s, you can also determine some
other limiting conditions:
If 0<=r<=1 & 0<=s<=1, intersection exists
r<0 or r>1 or s<0 or s>1 line segments do not intersect
If the denominator in eqn 1 is zero, AB & CD are parallel
If the numerator in eqn 1 is also zero, AB & CD are coincident
If the intersection point of the 2 lines are needed (lines in this
context mean infinite lines) regardless whether the two line
segments intersect, then
If r>1, I is located on extension of AB
If r<0, I is located on extension of BA
If s>1, I is located on extension of CD
If s<0, I is located on extension of DC
Also note that the denominators of eqn 1 & 2 are identical.
References:
[O'Rourke] pp. 249-51
[Gems III] pp. 199-202 "Faster Line Segment Intersection,"
----------------------------------------------------------------------
Subject 1.04: How do I generate a circle through three points?
Let the three given points be a, b, c. Use _0 and _1 to represent
x and y coordinates. The coordinates of the center p=(p_0,p_1) of
the circle determined by a, b, and c are:
A = b_0 - a_0;
B = b_1 - a_1;
C = c_0 - a_0;
D = c_1 - a_1;
E = A*(a_0 + b_0) + B*(a_1 + b_1);
F = C*(a_0 + c_0) + D*(a_1 + c_1);
G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0));
p_0 = (D*E - B*F) / G;
p_1 = (A*F - C*E) / G;
If G is zero then the three points are collinear and no finite-radius
circle through them exists. Otherwise, the radius of the circle is:
r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2
Reference:
[O' Rourke] p. 201. Simplified by Jim Ward.
----------------------------------------------------------------------
Subject 1.05: Where can I find graph layout algorithms?
See the paper by Eades and Tamassia, "Algorithms for Drawing
Graphs: An Annotated Bibliography," Tech Rep CS-89-09, Dept. of
CS, Brown Univ, Feb. 1989.
A revised version of the annotated bibliography on graph drawing
algorithms by Giuseppe Di Battista, Peter Eades, and Roberto
Tamassia is now available from
ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.tex.Z and
ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.ps.Z
----------------------------------------------------------------------
Section 2. 2D Polygon Computations
----------------------------------------------------------------------
Subject 2.01: How do I find the area of a polygon?
The signed area can be computed in linear time by a simple sum.
The key formula is this:
If the coordinates of vertex v_i are x_i and y_i,
twice the area of a polygon is given by
2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).
Reference: [O' Rourke] pp. 18-27; [Gems I] Rokne, pp. 5-6.
To find the area of a planar polygon not in the x-y plane, use:
2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))
where N is a unit vector normal to the plane. The `.' represents the
dot product operator, the `x' represents the cross product operator,
and abs() is the absolute value function.
[Gems II] pp. 170-171.
----------------------------------------------------------------------
Subject 2.02: How can the centroid of a polygon be computed?
The centroid (a.k.a. the center of mass, or center of gravity)
of a polygon can be computed as the weighted sum of the centroids
of a partition of the polygon into triangles. The centroid of a
triangle is simply the average of its three vertices, i.e., it
has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3. This
suggests first triangulating the polygon, then forming a sum
of the centroids of each triangle, weighted by the area of
each triangle, the whole sum normalized by the total polygon area.
This indeed works, but there is a simpler method: the triangulation
need not be a partition, but rather can use positively and
negatively oriented triangles (with positive and negative areas),
as is used when computing the area of a polygon. This leads to
a very simple algorithm for computing the centroid, based on a
sum of triangle centroids weighted with their signed area.
The triangles can be taken to be those formed by one fixed vertex
v0 of the polygon, and the two endpoints of consecutive edges of
the polygon: (v1,v2), (v2,v3), etc. The area of a triangle with
vertices a, b, c is half of this expression:
(b[X] - a[X]) * (c[Y] - a[Y]) -
(c[X] - a[X]) * (b[Y] - a[Y]);
Code available at ftp://grendel.csc.smith.edu/pub/code/centroid.c (3K).
Reference: [Gems IV] pp.3-6; also includes code.
----------------------------------------------------------------------
Subject 2.03: How do I find if a point lies within a polygon?
The definitive reference is "Point in Polyon Strategies" by
Eric Haines [Gems IV] pp. 24-46.
| The code in the Sedgewick book Algorithms (2nd Edition, p.354) is
| incorrect.
The code below is from Wm. Randolph Franklin
with some minor modifications for speed.
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y
(x-vx,y-vy,z-vz). This includes the viewpoint and the viewplane.
Now we need to rotate so that the z axis points straight at the
viewplane, then scale so it is 1 unit away.
After all this, we may find ourselves looking out upside- down. It
is traditional to specify some direction in the world or viewplane
as "up", and rotate so the positive y axis points that way (as
nearly as possible if it's a world vector). Finally, we have acted
so far as if the window was the entire plane instead of a limited
portal. A final shift and scale transforms coordinates in the
plane to coordinates on the screen, so that a rectangular region
of interest (our "window") in the plane fills a rectangular region
of the screen (our "canvas" if you like).
I have left out details of how you define and perform the rotation
of the viewplane, but I'm sure someone else will be happy to
supply those if there is demand. It requires knowing how to
describe a plane, and how to rotate vectors to line up. Neither is
difficult, but this is already using a lot of net space. One
further practical difficulty is the need to clip away parts of the
world behind us, so -(x,y,z) doesn't pop up at (x/z,y/z,1).
(Notice the mathematics of projection alone would allow that!) But
all the viewing transformations can be done using translation,
rotation, scale, and a final perspective divide. If a 4x4
homogeneous matrix is used, it can represent everything needed,
which saves a lot of work.
----------------------------------------------------------------------
Subject 5.15: How Do I optimize a 3D polygon mesh
References:
"Mesh Optimization" Hoppe, DeRose Duchamp, McDonald, Stuetzle,
ACM COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993.
"Re-Tiling Polygonal Surfaces",
Greg Turk, ACM Computer Graphics, 26, 2, July 1992
"Decimation of Triangle Meshes", Schroeder, Zarge, Lorensen,
ACM Computer Graphics, 26, 2 July 1992
"Simplification of ObjectsRendered by Polygonal Approximations",
Michael J. DeHaemer, Jr. and Michael J. Zyda, Computer & Graphics,
Vol. 15, No. 2, 1991, Great Britain: Pergamon Press, pp. 175-184.
----------------------------------------------------------------------
Subject 5.16: How can I perform volume rendering?
+ Two principal methods can be used:
+ - Ray casting or front-to-back, where the volume is behind the
+ projection plane. A ray is projected from each point in the projection
+ plane through the volume. The ray accumulates the properties of each
+ voxel it passes through.
+ - Object order or back-to-front, where the projection plane is behind
+ the volume. Each slice of the volume is projected on the projection
+ plane, from the farest plane to the nearest plane.
+ You can also use the marching-cubes algorithm, if the extraction of
+ surfaces from the data set is easy to do (see Subject 5.10).
+ Here is one algorithm to do front-to-back volume rendering:
+ Set up a projection plane as a plane tangent to a sphere that encloses
+ the volume. From each pixel of the projection plane, cast a ray
+ through the volume by using a Bresenham 3D algorithm.
+ The ray accumulates properties from each voxel intersected, stopping
+ when the ray exits the volume. The pixel value on
+ the projection plane determines the final color of the ray.
+ For unshaded images (i.e., without gradient and light computations),
+ if C is the ray color t the ray transparency
+ C' the new ray color t' the new ray transparency
+ Cv the voxel color tv the voxel transparency
+ then:
+ C' = C + t*Cv and t' = t * tv
+ with initial values: C = 0.0 and t = 1.0
+ An alternate version: instead of C' = C + t*Cv , use :
+ C' = C + t*Cv*(1-tv)^p with p a float variable.
+ Sometimes this gives the best results.
+ When the ray has accumulated transparency, if it becomes negligible
+ (e.g., t<0.1), the process can stop and proceed to the next ray.
+ References:
+ Bresenham 3D:
+ - http://www.sct.gu.edu.au/~anthony/info/graphics/bresenham.procs
+ - [Gems IV] p. 366
+ Volume rendering:
+ - [Watt:Animation] pp. 297-321
+ - IEEE Computer Graphics and application
+ Vol. 10, Nb. 2, March 1990 - pp. 24-53
+ - "Volume Visualization"
+ Arie Kaufman - Ed. IEEE Computer Society Press Tutorial
+ - "Efficient Ray Tracing of Volume Data"
+ Marc Levoy - ACM Transactions on Graphics, Vol. 9, Nb 3, July 1990
----------------------------------------------------------------------
Section 6. Geometric Structures and Mathematics
----------------------------------------------------------------------
Subject 6.01: Where can I get source for Voronoi/Delaunay triangulation?
For 2-d Delaunay triangulation, try Shewchuk's triangle program. It
includes options for constrained triangulation and quality mesh
generation. It uses exact arithmetic.
The Delaunay triangulation is equivalent to computing the convex hull
of the points lifted to a paraboloid. For n-d Delaunay triangulation
try Clarkson's hull program (exact arithmetic) or Barber and Huhdanpaa's
Qhull program (floating point arithmetic). The hull program also
computes Voronoi volumes and alpha shapes. The Qhull program also
computes 2-d Voronoi diagrams and n-d Voronoi vertices. The output of
both programs may be visualized with Geomview.
There are many other codes for Delaunay triangulation and Voronoi
diagrams. See Amenta's list of computational geometry software.
The Delaunay triangulation satisfies the following property: the
circumcircle of each triangle is empty. The Voronoi diagram is the
closest-point map, i.e., each Voronoi cell identifies the points that
are closest to an input site. The Voronoi diagram is the dual of
the Delaunay triangulation. Both structures are defined for general
dimension. Delaunay triangulation is an important part of mesh
generation.
References:
Amenta: http://www.geom.umn.edu/software/cglist
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
Clarkson: http://netlib.att.com/netlib/voronoi/hull.html
ftp://netlib.att.com/netlib/voronoi/hull.shar.Z
Geomview: http://www.geom.umn.edu/locate/geomview
ftp://geom.umn.edu/pub/software/geomview/
Shewchuk: http://www.cs.cmu.edu/~quake/triangle.html
ftp://netlib.att.com/netlib/voronoi/triangle.shar.Z
[O' Rourke] pp. 168-204
[Preparata & Shamos] pp. 204-225
Chew, L. P. 1987. "Constrained Delaunay Triangulations," Proc. Third
Annual ACM Symposium on Computational Geometry.
Chew, L. P. 1989. "Constrained Delaunay Triangulations," Algorithmica
4:97-108. (UPDATED VERSION OF CHEW 1987.)
Fang, T-P. and L. A. Piegl. 1994. "Algorithm for Constrained Delaunay
Triangulation," The Visual Computer 10:255-265. (RECOMMENDED!)
Frey, W. H. 1987. "Selective Refinement: A New Strategy for Automatic
Node Placement in Graded Triangular Meshes," International Journal for
Numerical Methods in Engineering 24:2183-2200.
Guibas, L. and J. Stolfi. 1985. "Primitives for the Manipulation of
General Subdivisions and the Computation of Voronoi Diagrams," ACM
Transactions on Graphics 4(2):74-123.
Karasick, M., D. Lieber, and L. R. Nackman. 1991. "Efficient Delaunay
Triangulation Using Rational Arithmetic," ACM Transactions on Graphics
10(1):71-91.
Lischinski, D. 1994. "Incremental Delaunay Triangulation," Graphics
Gems IV, P. S. Heckbert, Ed. Cambridge, MA: Academic Press Professional.
(INCLUDES C++ SOURCE CODE -- THANK YOU, DANI!)
[Okabe]
Schuierer, S. 1989. "Delaunay Triangulation and the Radiosity
Approach," Proc. Eurographics '89, W. Hansmann, F. R. A. Hopgood, and
W. Strasser, Eds. Elsevier Science Publishers, 345-353.
Subramanian, G., V. V. S. Raveendra, and M. G. Kamath. 1994. "Robust
Boundary Triangulation and Delaunay Triangulation of Arbitrary
Triangular Domains," International Journal for Numerical Methods in
Engineering 37(10):1779-1789.
Watson, D. F. and G. M. Philip. 1984. "Survey: Systematic
Triangulations," Computer Vision, Graphics, and Image Processing
26:217-223.
----------------------------------------------------------------------
Subject 6.02: Where do I get source for convex hull?
For n-d convex hulls, try Clarkson's hull program (exact arithmetic)
or Barber and Huhdanpaa's Qhull program (floating point arithmetic).
Qhull handles numeric precision problems by merging facets. The output
of both programs may be visualized with Geomview.
In higher dimensions, the number of facets may be much smaller than
the number of lower-dimensional features. When this is the case,
Fukuda's cdd program is much faster than Qhull or hull.
There are many other codes for convex hulls. See Amenta's list of
computational geometry software.
References:
Amenta: http://www.geom.umn.edu/software/cglist/
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
Clarkson: http://netlib.att.com/netlib/voronoi/hull.html
ftp://netlib.att.com/netlib/voronoi/hull.shar.Z
Geomview: http://www.geom.umn.edu/locate/geomview
ftp://geom.umn.edu/pub/software/geomview/
Fukuda: ftp://ifor13.ethz.ch/pub/fukuda/cdd/
[O' Rourke] pp. 70-167
C code for Graham's algorithm on p.80-96.
Three-dimensional convex hull discussed in Chapter 4 (p.113-67).
C code for the incremental algorithm on p.130-60.
[Preparata & Shamos] pp. 95-184
----------------------------------------------------------------------
Subject 6.03: Where do I get source for halfspace intersection?
For n-d halfspace intersection, try Fukuda's cdd program or Barber
and Huhdanpaa's Qhull program. Both use floating point arithmetic.
Fukuda includes code for exact arithmetic. Qhull handles numeric
precision problems by merging facets.
Qhull computes halfspace intersection by computing a convex hull.
The intersection of halfspaces about the origin is equivalent to the
convex hull of the halfspace coefficients divided by their offsets.
References:
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa ftp://geom.umn.edu/pub/software/qhull.tar.Z
Fukuda: ftp://ifor13.ethz.ch/pub/fukuda/cdd/
[Preparata & Shamos] pp. 315-320
----------------------------------------------------------------------
Subject 6.04: What are barycentric coordinates?
Let p1, p2, p3 be the three vertices (corners) of a closed
triangle T (in 2D or 3D or any dimension). Let t1, t2, t3 be real
numbers that sum to 1, with each between 0 and 1: t1 + t2 + t3 = 1,
0 <= ti <= 1. Then the point p = t1*p1 + t2*p2 + t3*p3 lies in
the plane of T and is inside T. The numbers (t1,t2,t3) are called the
barycentric coordinates of p with respect to T. They uniquely identify
p. They can be viewed as masses placed at the vertices whose
center of gravity is p.
For example, let p1=(0,0), p2=(1,0), p3=(3,2). The
barycentric coordinates (1/2,0,1/2) specify the point
p = (0,0)/2 + 0*(1,0) + (3,2)/2 = (3/2,1), the midpoint of the p1-p3
edge.
If p is joined to the three vertices, T is partitioned
into three triangles. Call them T1, T2, T3, with Ti not incident
to pi. The areas of these triangles Ti are proportional to the
barycentric coordinates ti of p.
Reference:
[Coxeter, Intro. to Geometry, p.217].
----------------------------------------------------------------------
Subject 6.05: How can I generate a random point inside a triangle?
Use barycentric coordinates (see item 53) . Let A, B, C be the
three vertices of your triangle. Any point P inside can be expressed
uniquely as P = aA + bB + cC, where a+b+c=1 and a,b,c are each >= 0.
Knowing a and b permits you to calculate c=1-a-b. So if you can
generate two random numbers a and b, each in [0,1], such that
their sum <=1, you've got a random point in your triangle.
Generate random a and b independently and uniformly in [0,1]
(just divide the standard C rand() by its max value to get such a
random number.) If a+b>1, replace a by 1-a, b by 1-b. Let c=1-a-b.
Then aA + bB + cC is uniformly distributed in triangle ABC: the reflection
step a=1-a; b=1-b gives a point (a,b) uniformly distributed in the triangle
(0,0)(1,0)(0,1), which is then mapped affinely to ABC.
Now you have barycentric coordinates a,b,c. Compute your point
P = aA + bB + cC.
Reference: [Gems I], Turk, pp. 24-28.
----------------------------------------------------------------------
Subject 6.06: How do I evenly distribute N points on (tesselate) a sphere?
"Evenly distributed" doesn't have a single definition. Under the
most strict criteria, only the five Platonic solids have their vertices
evenly distributed. Going beyond these distributions requires
loosening the requirements, and leads into moderately complex
mathematics. This topic happens to be a FAQ on sci.math as well
as on comp.graphics.algorithms; a much more extensive and rigorous
discussion written by Dave Rusin can be found at:
http://www.math.niu.edu/~rusin/papers/known-math/spheres/sphere.faq
One frequently used definition is a distribution that minimizes a 1/r
potential energy function of all the points, so that in a global sense
points are as "far away" from each other as possible. Starting from an
arbitrary distribution, we can either use numerical minimization algorithms
or point repulsion, in which all the points are considered to repel each
other according to a 1/r^2 force law and dynamics are simulated. The
algorithm is run until some convergence criterion is satisfied, and the
resulting distribution is our approximation.
Jon Leech developed code to do just this. It is available at
ftp://ftp.cs.unc.edu/pub/users/leech/points.tar.gz.
See his README file for more information.
----------------------------------------------------------------------
Subject 6.07: What are coordinates for the vertices of an icosohedron?
Data on various polyhedra is available at
http://netlib.att.com/netlib/polyhedra/index.html
For the icosahedron, the twelve vertices are:
(+- 1, 0, +-t), (0, +-t, +-1), and (+-t, +-1, 0)
where t = (sqrt(5)-1)/2, the golden ratio.
Reference: "Beyond the Third Dimension" by Banchoff, p.168.
----------------------------------------------------------------------
Subject 6.08: How do I generate random points on the surface of a sphere?
The trig method. This method works only in 3-space, but it is
very fast. It depends on the slightly counterintuitive fact (see
proof below) that each of the three coordinates is uniformly
distributed on [-1,1] (but the three are not independent,
obviously). Therefore, it suffices to choose one axis (Z, say)
and generate a uniformly distributed value on that axis. This
constrains the chosen point to lie on a circle parallel to the
X-Y plane, and the obvious trig method may be used to obtain the
remaining coordinates.
(a) Choose z uniformly distributed in [-1,1].
(b) Choose t uniformly distributed on [0, 2*pi).
(c) Let r = sqrt(1-z^2).
(d) Let x = r * cos(t).
(e) Let y = r * sin(t).
This method uses uniform deviates (faster to generate than normal
deviates), and no set of coordinates is ever rejected.
Here is a proof of correctness for the fact that the z-coordinate is
uniformly distributed. The proof also works for the x- and y-
coordinates, but note that this works only in 3-space.
The area of a surface of revolution in 3-space is given by
A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
Consider a zone of a sphere of radius R. Since we are integrating in
the z direction, we have
f(z) = sqrt(R^2 - z^2)
f'(z) = -z / sqrt(R^2-z^2)
1 + [f'(z)]^2 = r^2 / (R^2-z^2)
A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
= 2 * pi * R int_a^b dz
= 2 * pi * R * (b-a)
= 2 * pi * R * h,
where h = b-a is the vertical height of the zone. Notice how the integrand
reduces to a constant. The density is therefore uniform.
----------------------------------------------------------------------
Section 7. Contributors
----------------------------------------------------------------------
Subject 7.01: How can you contribute to this FAQ?
Send email to orourke@cs.smith.edu with your suggestions, possible
topics, corrections, or pointers to information.
----------------------------------------------------------------------
Subject 7.02: Contributors. Who made this all possible.
Jens Alfke
Scott Anguish
Brad Barber
Paul Bourke
Andrew Bromage
Brent Burley
Ken Clarkson
Martin Dillon
Dave Eberly
John Eickemeyer
Ata Etemadi
Luiz Henrique de Figueiredo
Andrew Fitzgibbon
David N. Fogel
Steve Hollasch
Craig Kolb
Steve Lamont
Jon Leech
Sum Lin
Fritz Lott
Marc Christopher Martin
Samuel Murphy
Joseph O'Rourke
Samuel S. Paik
| Christian von Roques
Dave Seaman
Klamer Schutte
Ken Shoemake
Jon Stone
Seth Teller
Yael "YoeL" Touboul
Anson Tsao
Jim Ward
Jason Weiler
Karsten Weiss
Previous Editors:
Jon Stone
Anson Tsao