Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
954 Appendix C Basic Formulas for Geometric Primitives
C.3 Quadrilaterals
C.3.1 Square
e
a
A = a
2
=
e
2
2
R =
a
√
2
e = a
√
2
r =
a
2
C.3.2 Rectangle
e
b
a
A = ab
R =
e
2
e =
a
2
+ b
2
C.3.3 Parallelogram
e
h
f
bb
a
a
A = ah
= a
2
sin α
h = b sin α
e
2
+ f
2
= 2(a
2
+ b
2
)
e =
a
2
+ b
2
+ 2ab cos α
e =
a
2
+ b
2
− 2ab cos α
C.3 Quadrilaterals 955
C.3.4 Rhombus
e
h
f
a
a
a
a
A = ah
= a
2
sin α
h =
1
2
ef
e
2
+ f
2
= 4a
2
e = 2a cos
α
2
f = 2a sin
α
2
C.3.5 Trapezoid
e
h
f
d
a
c
b
A =
(a +c)h
2
h = d sin α
= b sin β
e =
a
2
+ b
2
− 2ab cos β
f =
a
2
+ d
2
− 2ad cos α
C.3.6 General Quadrilateral
e
f
d
a
c
b
α + β + δ +γ = 360
◦
θ = 90 ⇔a
2
+ c
2
= b
2
+ d
2
A =
1
2
ef sin θ
=
1
4
(b
2
+ d
2
− a
2
− c
2
) tan θ
=
1
4
4e
2
f
2
− (b
2
+ d
2
− a
2
− c
2
)
2
956 Appendix C Basic Formulas for Geometric Primitives
C.4 Circles
C.4.1 Symbols
r:radius
d: diameter
c: circumference
s: length of arc
C.4.2 Full Circle
r
A
c
c = 2πr
= πd
A = πr
2
=
πd
2
4
C.4.3 Sector of a Circle
r
s
A
s =αr
A =
sr
2
=
αr
2
2
C.5 Polyhedra 957
C.4.4 Segment of a Circle
r
s
A
x
h
b
x =2r sin
α
2
h = r(1 − cos
α
2
)
h(2r − h) = (
x
2
)
2
=
αr
2
2
A =
r
2
2
(α − sin α)
=
1
2
(rx − bx)
C.5 Polyhedra
C.5.1 Symbols
a, b, c: edges
d: diagonal
B: area of base
S: surface area
V : volume
C.5.2 Box
a
b
c
d
d =
a
2
+ b
2
+ c
2
S =2(ab + bc + ac)
V = abc
958 Appendix C Basic Formulas for Geometric Primitives
C.5.3 Prism
h
B
V = Bh
C.5.4 Pyramid
h
h
1
h
2
V
1
V
2
B
1
B
2
V =
1
3
Bh
V
1
V
=
B
1
B
3
2
=
h
1
h
3
V
1
=
h
3
1
B
3h
2
V
2
=
h
2
3
B +
BB
1
+ B
1
C.6 Cylinder
h
r
B = πr
2
A = 2πrh
S =2πr(r + h)
V = πr
2
h
C.8 Spheres 959
C.7 Cone
r
h
s
B
s =
r
2
+ h
2
A = πrs
S =πr(r + s)
V =
1
3
πr
2
h
C.8 Spheres
r
S =4πr
2
V =
4
3
πr
3
C.8.1 Segments
One Base
r
h
a
S
a =r sin α
a
2
= h(2r − h)
h = r(1 − cos α)
S =2πrh
V =
π
3
h
2
(3r − h)
=
π
6
h(3a
2
+ h
2
)
960 Appendix C Basic Formulas for Geometric Primitives
Two Bases
r
a
b
S
h
S =2πrh
V =
π
6
h(3a
2
+ 3b
2
+ h
2
)
C.8.2 Sector
r
h
V =
2πr
2
h
3
=
πr
3
3
2 −3cos
θ
2
+ cos
3
θ
2
C.9 Torus
r
1
r
2
S =4π
2
r
1
r
2
V = 2π
2
r
1
r
2
2
References
Agnew, Jeanne, and Robert C. Knapp. 1978. Linear Algebra with Applications. Brooks/
Cole Publishing Company, Monterey, CA.
Anton, Howard. 1980. Calculus with Analytic Geometry. John Wiley and Sons, New
Yo r k .
Arvo, James. 1990. A simple method for box-sphere intersection testing. In Andrew
Glassner, editor, Graphics Gems, Academic Press, New York, pages 335–339.
Arvo, James, editor. 1991. Graphics Gems II. Academic Press, San Diego.
Bajaj, C. L., C. M. Hoffman, J. E. H. Hopcroft, and R. E. Lynch. 1989. Tracing surface
intersections. Computer Aided Geometric Design, 5:285–307.
Barequet, Gill, and Sariel Har-Peled. 1999. Efficiently approximating the minimum-
volume bounding box of a point set in three dimensions. Proc. 10th ACM-SIAM
Sympos. Discrete Algorithms, pages 82–91.
Barnhill, Robert E., and S. N. Kersey. 1990. A marching method for parametric
surface/surface intersection. Computer Aided Geometric Design, 7:257–280.
Bartels, Richard H., John C. Beatty, and Brian A. Barsky. 1987. An Introduction to
Splines for Use in Computer Graphics and Geometric Modeling. Morgan Kaufmann
Publishers, San Francisco.
Bellman, R. E. 1987. Dynamic Programming. Princeton University Press, Princeton,
NJ.
Blumenthal, Leonard M. 1970. Theory and Applications of Distance Geometry.
Chelsea House Publishers, Broomall, PA.
Boeing Information & Support Services. 1997. DT_NURBS spline geometry subpro-
gram library: Theory document, version 3.5. Carderock Division, Naval Surface
Warfare Center.
Bourke, Paul. 1992. Intersection of a line and a sphere (or circle). astronomy.swin.edu
.au/pbourke/geometry/sphereline.
Bowyer. A. 1981. Computing dirichlet tessellations. The Computer Journal, 24(2):
162–166.
Bowyer, Adrian, and John Woodwark. 1983. A Programmer’s Geometry.Butter-
worth’s, London.
961
962 References
Busboom, Axel, and Robert J. Schalkoff. 1996. Active stereo vision and direct sur-
face parameter estimation: Curve-to-curve image plane mappings. IEEE Pro-
ceedings on Vision, Image, and Signal Processing, 143(2), April. Web version:
ece.clemson.edu/iaal/vsip1rw/vsip1rw.htm.
Bykat, A. 1978. Convex hull of a finite set of points in two dimensions. Information
Processing Letters, 7:296–298.
Cameron, S. 1997. Enhancing GJK: Computing minimum and penetration distances
between convex polyhedra. Proc. IEEE Int. Conf. on Robotics and Automation,
pages 3112–3117.
Cameron, S., and R. K. Culley. 1986. Determining the minimum translational dis-
tance between convex polyhedra. Proc. IEEE Int. Conf. on Robotics and Automa-
tion, pages 591–596.
Campagna, Swen, Philipp Slusallek, and Hans-Peter Seidel. 1997. Ray tracing of
spline surfaces: B
´
ezier clipping, Chebyshev boxing, and bounding volume
hierarchy—a critical comparison with new results. The Visual Computer, 13.
Casselman, Bill. 2001. Mathematics 309—conic sections and their applications.
www.math.ubc.ca/people/faculty/cass/courses/m309-01a/text/ch4.pdf.
Chasen, Sylvan H. 1978. Geometric Principles and Procedures for Computer Graphics
Applications. Prentice Hall, Englewood Cliffs, NJ.
Chazelle, B. 1991. Triangulating a simple polygon in linear time. Disc. Comp. Geom.,
6:485–524.
Chazelle, B., and J. Incerpi. 1984. Triangulation and shape complexity. ACM Transac-
tions on Graphics, 3:135–152.
Chazelle, B., and L. Palios. 1990. Triangulating a nonconvex polyhedron. Discrete and
Computational Geometry, 5:505–526.
Cheng, S.-W., T. K. Dey, H. Edelsbrunner, M. A. Facello, and S.-H. Teng. 2000. Sliver
exudation. Journal of the ACM, 47(5):883–904.
Clarkson, K., R. E. Tarjan, and C. J. Van Wyk. 1989. A fast Las Vegas algorithm for
triangulating a simple polygon. Disc. Comp. Geom., 4:387–421.
Cohen, Elaine, Tom Lyche, and Richard Riesenfeld. 1980. Discrete B-splines and sub-
division techniques in computer-aided geometric design and computer graphics.
Computer Graphics and Image Processing, 14:87–111.
Cohen, Elaine, Richard F. Riesenfeld, and Gershon Elber. 2001. Geometric Modeling
with Splines: An Introduction.A.K.Peters,Natick,MA.
Cohen, J. D., M. C. Lin, D. Manocha, and M. K. Ponamgi. 1995. I–Collide: An in-
teractive and exact collision detection system for large-scale environments. Proc.
ACM Symposium on Interactive 3D Graphics, pages 189–196.
References 963
Collins, G. E., and A. G. Akritas. 1976. Polynomial real root isolation using Descartes’
rule of signs. ACM Symposium on Symbolic and Algebraic Computation, pages
272–276.
Collins, G. E., and R. Loos. 1982. Real zeros of polynomials. Computing, Suppl., 4:83–
94.
Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction
to Algorithms. The MIT Press, Cambridge, MA.
Crawford, Diane, editor. 2002. Game engines in scientific research (seven articles).
Communications of the ACM, 45(1), January.
Dahmen, W., C. A. Micchelli, and H.-P. Seidel. 1992. Blossoming begets B-spline
bases built better by B-patches. Mathematics of Computation, 1(1):97–115, July.
de Berg, Mark (editor), Marc van Kreveld, Mark Overmars, and O. Schwarzkopf.
2000. Computational Geometry: Algorithms and Applications (2nd edition).
Springer, Berlin.
DeRose, Tony D. 1989. A coordinate-free approach to geometric programming. Math
for SIGGRAPH: Course Notes 23, SIGGRAPH ’89, pages 55–115, July.
DeRose, Tony D. 1992. Three-Dimensional Computer Graphics: A Coordinate-Free
Approach. Unpublished manuscript, University of Washington.
Dey, Tamal K., Chandrajit L. Bajaj, and Kokicki Sugihara. 1991. On good triangula-
tions in three dimensions. Proceedings of the First Symposium on Solid Modeling
Foundations and CAD/CAM Applications, pages 431–441.
Dobkin, D. P., and D. G. Kirkpatrick. 1990. Determining the separation of pre-
processed polyhedra—A unified approach. Proc. 17th Internat. Colloq. Automata
Lang. Program, Lecture Notes in Computer Science, volume 443, pages 400–413.
Springer-Verlag.
Dupont, Laurent, Sylvain Lazard, and Sylvain Petitjean. 2001. Towards the robust
intersection of implicit quadrics. In Workshop on Uncertainty in Geometric Com-
putations, The University of Scheffield (England).Kluwer.
Eberly, David H. 1999. Polysolids and boolean operations. www.magic-software
.com/Documentation/psolid.pdf .
Eberly, David H. 2000. 3D Game Engine Design. Morgan Kaufmann, San Francisco.
Eberly, David H. 2001. Polysolid and BSP-based Boolean polygon operations.
www.magic-software.com/ConstructivePlanarGeometry.html.
Edelsbrunner, H., and R. Seidel. 1986. Voronoi diagrams and arrangements. Disc.
Comp. Geom., 1:25–44.
Farin, Gerald. 1990. Curves and Surfaces in Computer Aided Geometric Design: A
Practical Guide. Academic Press, Boston.
Farin, Gerald. 1995. NURB Curves and Surfaces, From Projective Geometry to Practical
Use. A. K. Peters, Wellesley, MA.