Comp.Graphics.Algorithms
Frequently Asked Questions

Introduction and Contents

Welcome to the FAQ for comp.graphics.algorithms!

Thanks to all who have contributed. Corrections and contributions (to orourke@cs.smith.edu) always welcome.
This article is Copyright 1998 by Joseph O'Rourke. It may be freely redistributed in its entirety provided that this copyright notice is not removed.

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: How can the smallest circle enclosing a set of points be found?
1.06: 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)?
3.14: How is "GIF" pronounced?

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?
5.17: Where can I get the spline description of the famous teapot etc.?
5.18: How can the distance between two lines in space be computed?
5.19: How can I compute the volume of a polyhedron?
5.20: How can I decompose a polyhedron into convex pieces?
5.21: How can the circumsphere of a tetrahedron be computed?
5.22: How do I determine if two triangles in 3D intersect?

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?
6.09: What are Plücker coordinates?

7. Contributors

7.01: How can you contribute to this FAQ?
7.02: Contributors. Who made this all possible.

Note

This Html version is maintained and updated from the ASCII version by James Sharman. If whilst reading this document you spot any inconstancies with the ASCII version please email James@exaflop.org.

Note: The full ascii version of this FAQ is posted every 2 weeks to comp.graphics.algorithums.