Schneider P., Eberly D.H. Geometric Tools for Computer Graphics

Подождите немного. Документ загружается.

964 References

Farouki, R. T. 1986. The characterization of parametric surface sections. Computer

Vision, Graphics, and Image Processing, 33:209–236.

Field, D. A. 1986. Implementing Watson’s algorithm in three dimensions. Proceedings

of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational

Geometry, pages 246–259.

Finney, Ross L., and George B. Thomas. 1996. Calculus and Analytic Geometry, 9th

edition. Addison-Wesley Publishing Company, Reading, MA.

Foley, James D., Andries van Dam, Steven K. Feiner, and John F. Hughes. 1996. Com-

puter Graphics: Principles and Practices. Addison-Wesley Publishing Company,

Reading, MA.

Fournier, Alain, and John Buchanan. 1984. Chebyshev polynomials for boxing and

intersections of parametric curves and surfaces. Computer Graphics Forum: Pro-

ceedings of Eurographics ’94, volume 13(3), pages 127–142.

Fournier, A., and D. Y. Montuno. 1984. Triangulating simple polygons and equivalent

problems. ACM Transactions on Graphics, 3:153–174.

Fuchs, Henry, Zvi Kedem, and Bruce Naylor. 1979. Predetermining visibility priority

in 3-d scenes. Proceedings of SIGGRAPH, pages 175–181.

Fuchs, Henry, Zvi Kedem, and Bruce Naylor. 1980. On visible surface generation by

aprioritreestructures.Proceedings of SIGGRAPH, pages 124–133.

Gaertner, Bernd, and Sven Schoenherr. 1998. Exact primitives for smallest enclosing

ellipses. Information Processing Letters, 68:33–38.

Gaertner, Bernd, and Sven Schoenherr. 2000. An efﬁcient, exact, and generic qua-

dratic programming solver for geometric optimization. Proc. 16th Annual ACM

Symposium on Computational Geometry (SCG), pages 110–118.

Georgiades, Pr

ıamos. 1992. Signed distance from point to plane. In David Kirk,

editor, Graphics Gems III, Academic Press, New York, pages 223–224.

Gilbert, E. G., and C.-P. Foo. 1990. Computing the distance between general convex

objects in three-dimensional space. IEEE Transactions on Robotics and Automa-

tion, 6(1):53–61.

Gilbert, E. G., D. W. Johnson, and S. S. Keerthi. 1988. A fast procedure for computing

the distance between complex objects in three-dimensional space. IEEE Journal of

Robotics and Automation, 4(2):193–203.

Glaeser, Georg. 1994. Fast Algorithms for 3D-Graphics. Springer-Verlag, New York.

Glassner, Andrew S., editor. 1989. An Introduction to Ray Tracing. Academic Press,

Berkeley.

Glassner, Andrew S., editor. 1990. Graphics Gems. Academic Press, San Diego.

Goldman, Ronald N. 1985. Illicit expressions in vector algebra. ACM Transactions on

Graphics, 4(3):223–243, July.

References 965

Goldman, Ronald N. 1987. Vector geometry: A coordinate-free approach. Geometry

for Computer Graphics and Computer Aided Design: Course Notes 19, SIGGRAPH

’87, pages 1–172, June.

Goldman, Ronald N. 1990a. Intersection of three planes. In Andrew Glassner, editor,

Graphics Gems, Academic Press, San Diego, page 305.

Goldman, Ronald N. 1990b. Matrices and transformations. In Andrew Glassner,

editor, Graphics Gems, Academic Press, San Diego, pages 472–475.

Goldman, Ronald N. 1990c. Triangles. In Andrew Glassner, editor, Graphics Gems,

Academic Press, San Diego, pages 20–23.

Goldman, Ronald N. 1991. More matrices and transformations: Shear and pseudo-

perspective. In James Arvo, editor, Graphics Gems II, Academic Press, San Diego,

pages 338–341.

Goldman, Ronald N., and Tom Lyche, editors. 1993. Knot Insertion and Deletion

Algorithms for B–Spline Curves and Surfaces. Society for Industrial and Applied

Mathematics, Philadelphia.

Golub, Gene H., and Charles F. Van Loan. 1993. Matrix Computations, 2nd edition.

The Johns Hopkins University Press, Baltimore, MD.

Gottschalk, Stefan, Ming Lin, and Dinesh Manocha. 1996. OBBTree: A hierarchical

structure for rapid interference detection. Computer Graphics (SIGGRAPH ’96

Proceedings), pages 171–180, August.

Haines, Eric. 1987. Abnormal normals. Ray Tracing News,0,September.

Haines, Eric. 1989. Essential ray tracing algorithms. In Andrew Glassner, editor, An

Introduction to Ray Tracing, Academic Press, San Diego, pages 33–77.

Haines, Eric. 1991. Fast ray–convex polyhedron intersection. In James Arvo, editor,

Graphics Gems II, Academic Press, San Diego, pages 247–250.

Haines, Eric. 1994. Point in polygon strategies. In Paul S. Heckbert, editor, Graphics

Gems IV , Academic Press, San Diego, pages 24–46.

Hanrahan, Pat. 1983. Ray tracing algebraic surfaces. Computer Graphics (SIGGRAPH

’83 Proceedings), ACM, July, pages 83–90.

Hart, John. 1994. Distance to an ellipsoid. In Paul S. Heckbert, editor, Graphics Gems

IV , Academic Press, New York, pages 113–119.

Heckbert, Paul S., editor. 1994. Graphics Gems IV . Academic Press, San Diego.

Hecker, Chris. 1997. Physics, part 4: The third dimension. Game Developer, pages

15–26, June.

Hershberger, John E., and Jack S. Snoeyink. 1988. Erased decompositions of lines

and convex decompositions of polyhedra. Computational Geometry, Theory and

Applications, 9(3):129–143.

966 References

Hertel, S., and K. Mehlhorn. 1983. Fast triangulation of simple polygons. Proc. 4th

Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes in Computer

Science, pages 207–218.

Hill, F. S., Jr. 1994. The pleasures of ‘perp dot’ products. In Paul S. Heckbert, editor,

Graphics Gems IV , Academic Press, New York, pages 139–148.

Hoffman, C. M. 1989. Geometric and Solid Modeling. Morgan Kaufmann, San Fran-

cisco.

Holwerda, Klaas. 2000. Boolean, version 6. www.xs4all.nl/ kholwerd/bool.html.

Horn, Roger A., and Charles R. Johnson. 1985. Matrix Analysis. Cambridge Univer-

sity Press, Cambridge, England.

Huber, Ernst H. 1998. Intersecting general parametric surfaces using bounding vol-

umes. In Mike Soss, editor, Proceedings of the 10th Canadian Conference on Com-

putational Geometry,Montr

eal, Qu

ebec, School of Computer Science, McGill

University, pages 52–53.

Joe, Barry. 1991. Delaunay versus max-min solid angle triangulations for three-

dimensional mesh generation. International Journal for Numerical Methods in

Engineering, 31:987–997.

Johnson, L., and R. Riess. 1982. Numerical Analysis. Addison-Wesley Publishing

Company, Reading, MA.

Kajiya, James T. 1982. Ray tracing parametric surfaces. Computer Graphics (SIG-

GRAPH ’82 Proceedings), ACM, volume 16(3), pages 245–254 .

Kay, D. D. 1988. Schaum’s Outline of Theory and Problems of Tensor Calculus.

McGraw-Hill, New York.

Kay, Timothy L., and James T. Kajiya. 1986. Ray tracing complex scenes. Computer

Graphics (SIGGRAPH ’86 Proceedings), ACM, pages 269–278.

Keil, J. M. 1985. Decomposing a polygon into simpler components. SIAM J. Comput.,

14:799–817.

Keil, J. M., and J. Snoeyink. 1998. On the time bound for convex decomposition of

simple polygons. Proceedings of the 10th Canadian Conference on Computational

Geometry, pages 54–55.

Kirk, David, editor. 1992. Graphics Gems III. Academic Press, San Diego.

Kirkpatrick, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comp.,

12:28–35.

Klee, V. 1980. On the complexity of d-dimensional Voronoi diagrams. Archiv.

Mathem., 34:75–80.

Krishnan, Shankar, and Dinesh Manocha. 1997. An efﬁcient surface intersection al-

gorithm based on lower dimensional formulation. ACM Transactions on Graphics,

16(1).

References 967

Lam, T. 1973. The Algebraic Theory of Quadratic Forms. W.A. Benjamin, Reading, MA.

Lane, Jeffrey, and Robert F. Riesenfeld. 1980. A theoretical development for the com-

puter generation and display of piecewise polynomial surfaces. IEEE Transactions

on Pattern Analysis and Machine Intelligence, 2(1):150–159.

Lasser, D. 1986. Intersection of parametric surfaces in the Bernstein-B

ezier represen-

tation. Computer-Aided Design, 18(4):186–192.

Lee, Randy B., and David A. Fredricks. 1984. Special feature: Intersection of paramet-

ric surfaces and a plane. IEEE Computer Graphics and Applications, 4(8):48–51,

August.

Leonov, Michael. 1997. poly_boolean. woland.it.nsc.ru/ leonov/clipdoc.html.

Levin, Joshua. 1976. A parametric algorithm for drawing pictures of solid objects

composed of quadric surfaces. Communications of the ACM, 19(11):553–563,

October.

Levin, Joshua. 1979. Mathematical models for determining the intersection of

quadric surfaces. Computer Graphics and Image Processing, 11(1):73–87.

Levin, Joshua. 1980. QUISP: A Computer Processor for the Design and Display of

Quadric-Surface Bodies. Ph.D. dissertation, Rensselaer Polytechnic Institute, Troy,

NY.

Levine, Ron. 2000. Collisions of moving objects. GD algorithms list at sourceforge.net,

November.

Lin, M. C., and J. F. Canny. 1991. A fast algorithm for incremental distance compu-

tation. Proc. IEEE Int. Conf. on Robotics and Automation, pages 1008–1014.

Martin, William, Elaine Cohen, Russell Fish, and Peter Shirley. 2000. Practical ray

tracing of trimmed NURBS surfaces. Journal of Graphics Tools, 5(1):27–52.

Maynard, Hugh, and Lucio Tavernini. 1984. Boolean operations on polysolids. Un-

published work. (See a summary of the work in [Eberly 1997].)

Meister, G. H. 1975. Polygons have ears. Amer. Math. Monthly, 82:648–651.

Miller, James R. 1987. Geometric approaches to nonplanar quadric surface intersec-

tion curves. ACM Transactions on Graphics, 6(4), October.

Miller, James R. 1999a. Applications of vector geometry for robustness and speed.

IEEE Computer Graphics and Applications, 19(4):68–73, July.

Miller, James R. 1999b. Vector geometry for computer graphics. IEEE Computer

Graphics and Applications, 19(3):66–73, May.

Miller, James R., and Ronald N. Goldman. 1992. Using tangent balls to ﬁnd plane

sections of natural quadrics. IEEE Computer Graphics and Applications, 16(2):68–

82, March.

Miller, James R., and Ronald N. Goldman. 1993a. Detecting and calculating conic

sections in the intersection of two natural quadric surfaces, Part I: Theoretical

968 References

analysis. Technical Report TR-93-1, Department of Computer Science, University

of Kansas.

Miller, James R., and Ronald N. Goldman. 1993b. Detecting and calculating conic

sections in the intersection of two natural quadric surfaces, Part II: Geometric

constructions for detection and calculation. Technical Report TR-93-2, Depart-

ment of Computer Science, University of Kansas.

Miller, James R., and Ronald Goldman. 1995. Geometric algorithms for detecting

and calculating all conic sections in the intersection of any two natural quadric

surfaces. Computer Vision, Graphics, and Image Processing, 57(1):55–66, January.

Mirtich, B. 1997. V-clip: Fast and robust polyhedral collision detection. ACM Trans-

actions on Graphics, 17(3):177–208.

oller, Tomas. 1997. A fast triangle-triangle intersection test. Journal of Graphics

Tools , 2(2):25–30.

oller, Tomas, and Eric Haines. 1999. Real-Time Rendering. A.K. Peters, Ltd., Natick,

MA.

oller, Tomas, and Ben Trumbore. 1997. Fast, minimum storage ray-triangle inter-

section. Journal of Graphics Tools, 2(1):21–28.

Murtha, Alan. 2000. gpc (general polygon clipper library), version 2.31. www.cs.man.

ac.uk/aig/staff/alan/software/index.html.

Naylor, B. 1990. SCULPT: An interactive solid modeling tool. Proceedings of Graphics

Interface ’90, pages 138–148, May.

Naylor, B. 1992. Interactive solid geometry via partitioning trees. Proceedings of

Graphics Interface ’92, pages 11–18, May.

Naylor, B., J. Amanatides, and W. Thibault. 1990. Merging BSP trees yields polyhedral

set operations. Proceedings of SIGGRAPH, pages 115–124.

Newman, W., and R. Sproull. 1979. Principles of Interactive Computer Graphics, 2nd

edition. McGraw-Hill, New York.

Nishita, Tomoyuki, Thomas W. Sederberg, and Masanori Kakimoto. 1990. Ray trac-

ing trimmed rational surface patches. Computer Graphics (SIGGRAPH ’90 Pro-

ceedings), ACM, volume 24 (4), pages 337–345.

O’Rourke, J. 1985. Finding minimal enclosing boxes. Internat. J. Comput. Inform. Sci.,

14:183–199, June.

O’Rourke, Joseph. 1998. Computational Geometry in C, 2nd edition. Cambridge Uni-

versity Press, Cambridge, England.

Paeth, Alan W., editor. 1995. Graphics Gems V . Academic Press, San Diego.

Patrikalakis, N. M. 1993. Surface-to-surface intersections. IEEE Computer Graphics

and Applications, 13(1):89–95.

References 969

Piegl, Les. 1989. Geometric method of intersecting natural quadrics represented in

trimmed surface form. Computer-Aided Design, 13(1):89–95.

Piegl, Les, and Wayne Tiller. 1995. The NURBS Book. Springer-Verlag, Berlin.

Pierre, Donald A. 1986. Optimization Theory with Applications. Dover Publications,

New York.

Pirzadeh, Hormoz. 1999. Rotating calipers home page. www.cs.mcgill.ca/˜orm/rotcal.

html.

Pratt, M. J., and A. D. Geisow. 1986. Surface/surface intersection problems. In J. A.

Gregory, editor, The Mathematics of Surfaces, volume 6, Clarendon Press, Oxford,

pages 117–142.

Preparata, Franco P., and Michael Ian Shamos. 1985. Computational Geometry: An

Introduction. Springer-Verlag, New York.

Press, W. H., B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. 1988. Numerical

Recipes in C: The Art of Scientiﬁc Computing. Cambridge University Press, Cam-

bridge, England.

Rade, Lennart, and Bertil Westergren. 1995. Mathematics Handbook for Science and

Engineering. Birkhauser, Boston.

Rogers, David F. 2001. An Introduction to NURBS with Historical Perspective.Morgan

Kaufmann Publishers, San Francisco.

Rogers, David F., and J. A. Adams. 1990. Mathematical Elements for Computer Graph-

ics, 2nd edition. McGraw-Hill, New York.

Rossignac, J. R., and A. A. G. Requicha. 1987. Piecewise-circular curves for geometric

modeling. IBM Journal on Research and Development, 31(3):39–45.

Roth, Scott. 1981. Ray casting for modeling solids. Computer Graphics and Image

Processing, 18(2):109–144.

Rusin, Dave. 1995. General formula for the area of a polygon. www.math.niu.edu/˜

rusin/known-math/95/greens.

Salomon, David. 1999. Computer Graphics and Geometric Modeling. Springer-Verlag,

New York.

Sarraga, R. F. 1983. Algebraic methods for intersection of quadric surfaces in GM-

SOLID. Computer Vision, Graphics, and Image Processing, 22(2):222–238, May.

Schneider, Philip J. 1990. A B

ezier curve-based root ﬁnder. In Andrew Glassner,

editor, Graphics Gems, Academic Press, San Diego, pages 408–415.

Schutte, Klamer. 1995. An edge labeling approach to concave polygon clipping.

www.ph.tn.tudelft.nl/People/klamer/clip.ps.gz.

Sechrest, S., and D. Greenberg. 1981. A visible polygon reconstruction algorithm.

Comput. Graph., 15(3):17–26.

970 References

Sederberg, Thomas W. 1983. Implicit and Parametric Curves and Surfaces. Ph.D. the-

sis, Purdue University.

Sederberg, Thomas W. 1984. Ray tracing of Steiner patches. Computer Graphics (SIG-

GRAPH ’84 Proceedings), ACM, volume 18 (3), pages 159–164.

Sederberg, Thomas W., and Tomoyuki Nishita. 1991. Geometric Hermite approxi-

mation of surface patch intersection curves. Computer Aided Geometric Design,

8:97–114.

Seidel, R. 1991. A simple and fast incremental randomized algorithm for comput-

ing trapezoidal decompositions and for triangulating polygons. Computational

Geometry: Theory and Applications, 1(1):51–64.

Shamos, Michael I. 1978. Computational Geometry. Ph.D. dissertation, Yale Uni-

versity.

Shewchuk, Jonathan Richard. 2000. Stabbing Delaunay tetrahedralizations. www.cs

.cmu.edu/ jrs/papers/stab.ps.

Shoemake, Ken. 1987. Animating rotation with quaternion calculus. ACM SIG-

GRAPH Course Notes 10: Computer Animation: 3-D Motion, Speciﬁcation, and

Control.

Sunday, Dan. 2001a. Area of triangles and polygons (2d and 3d). www.softsurfer.com.

Sunday, Dan. 2001b. Distance between lines, segments, and the closest point of ap-

proach. www.softsurfer.com.

Sunday, Dan. 2001c. Intersection of line, segment, and plane in 2d and 3d.

www.softsurfer.com.

Sweeney, Michael A. J., and Richard H. Bartels. 1986. Ray tracing free-form B-spline

surfaces. IEEE Computer Graphics and Applications, 6(2):41–49, February.

Tampieri, Filippo. 1992. Newell’s method for computing the plane equation of a

polygon. In David Kirk, editor, Graphics Gems III, Academic Press, San Diego,

pages 231–232.

ter Haar Romeny, B. M., editor. 1994. Geometry-Driven Diffusion in Computer Vision.

Computational Imaging and Vision Series. Kluwer Academic Publishers, Dor-

drecht, the Netherlands.

Thibault, William C., and Bruce F. Naylor. 1987. Set operations on polyhedra us-

ing binary space partitioning trees. Proceedings of the 14th Annual Conference on

Computer Graphics, pages 153–162.

Toth, Daniel L. 1995. On ray tracing parametric surfaces. Computer Graphics (SIG-

GRAPH ’85 Proceedings), ACM, volume 19 (3), pages 171–179.

van den Bergen, Gino. 1997. Efﬁcient collision detection of complex deformable

models using AABB trees. Journal of Graphics Tools, 2(4):1–13.

van den Bergen, Gino. 1999. A fast and robust GJK implementation for collision

detectionofconvexobjects.Journal of Graphics Tools, 4(2):7–25.

References 971

van den Bergen, Gino. 2001a. Proximity queries and penetration depth computation

on 3d game objects. Game Developers Conference Proceedings, pages 821–837.

van den Bergen, Gino. 2001b. SOLID: Software library for interference detection.

www.win.tue.nl/ gino/solid/.

Vatti, B. R. 1992. A generic solution to polygon clipping. Communications of the

ACM , 35(7):56–63.

Watson, D. 1981. Computing the n–dimensional Delaunay tessellation with applica-

tions to Voronoi polytopes. The Computer Journal, 24(2):167–172.

Wee, Chionh Eng, and Ronald N. Goldman. 1995a. Elimination and resultants part

1: Elimination and bivariate resultants. IEEE Computer Graphics and Applications,

January, pages 69–77.

Wee, Chionh Eng, and Ronald N. Goldman. 1995b. Elimination and resultants part 2:

Multivariate resultants. IEEE Computer Graphics and Applications, March, pages

60–69.

Weiler, K., and P. Atherton. 1977. Hidden surface removal using polygon area sorting.

Proceedings of SIGGRAPH, volume 11, pages 214–222.

Weisstein, Eric. 1999. Torus. mathworld.wolfram.com/Torus.html.

Welzl, Emo. 1991. Smallest enclosing disks (balls and ellipsoids). Lecture Notes in

Computer Science, New Results and New Trends in Computer Science, 555:359–370.

Wikipedia. 2002. Field. www.wikipedia.com/wiki/Field.

Yamaguchi, Fujio. 1988. Curves and Surfaces in Computer Aided Geometric Design.

Springer-Verlag, Berlin.

Index

binary space-partitioning (BSP)

trees, 673–687

convex hulls, 729–744

Delaunay triangulation, 757–761

distance in, 189–239

geometric primitives in, 171–188

intersection in, 241–284

linear components, 171–174

method of separating axes,

265–284

mirror image, 153

miscellaneous problems,

285–324

points, transforming, 10

reﬂection, 150, 151

shearing, 155, 158

triangulation, 766

2D objects

embedded, 331

methods for representing,

332–333

in plane, 331–333

2D polygon area, 816–820

as algebraic quantity, 817–819

as analytic quantity, 819–820

as geometric quantity, 819

as inductive formula, 817