Computational Geometry¶

The Nature of Mathematical Modeling (draft)¶

$ \def\%#1{\mathbf{#1}} \def\mat#1{\mathbf{#1}} \def\*#1{\vec{#1}} \def\ve#1{\vec{#1}} \def\ds#1#2{\cfrac{d #1}{d #2}} \def\dd#1#2{\cfrac{d^2 #1}{d #2^2}} \def\ps#1#2{\cfrac{\partial #1}{\partial #2}} \def\pp#1#2{\cfrac{\p^2 #1}{\p #2^2}} \def\p{\partial} \def\ba{\begin{eqnarray*}} \def\ea{\end{eqnarray*}} \def\eps{\epsilon} \def\del{\nabla} \def\disp{\displaystyle} \def\la{\langle} \def\ra{\rangle} \def\unit#1{~({\rm #1)}} \def\units#1#2{~\left(\frac{\rm #1}{\rm #2}\right)} \def\argmax#1{\mathrel{\mathop{\mathrm {argmax}}\limits_{#1}}} $

CGAL
Gaussian splats
line drawing

Meshes¶

triangulation FEM, STL, GL

Delaunay, Boris Nikolajewitsch. "Neue darstellung der geometrischen kristallographie." Z. Kristallograph 84 (1932): 109-149.

maximize minimum angle

Voronoi, G. "New applications, from continuous parameter to quadratic shape theory." Journal für die Reine und Angewandte Mathematik 133 (1907): 97-178.

closest points voting, ecology, networking dual simplices with no vertex in circumsphere

Watson, David F. "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes." The computer journal 24.2 (1981): 167-172.

start arbitrary bounding simplex add point, delete intersecting circumspheres, create simplices from polytope faces not unique, perturb construct tree from subdivisions

Guibas, Leonidas J., Donald E. Knuth, and Micha Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica 7.1-6 (1992): 381-413.

randomized incremental N log N

polygon

Meisters, Gary H. "Polygons have ears." American Mathematical Monthly (1975): 648-651.

ear-clipping, diagonal contained

volume CT, sim, frep marchine cubes

Lorensen, William E., and Harvey E. Cline. "Marching cubes: A high resolution 3D surface construction algorithm." ACM Siggraph Computer Graphics. Vol. 21. No. 4. ACM, 1987.

decimation

Ramer, Urs. "An iterative procedure for the polygonal approximation of plane curves." Computer Graphics and Image Processing 1.3 (1972): 244- 256.

Douglas, David H., and Thomas K. Peucker. "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature." Cartographica: The International Journal for Geographic Information and Geovisualization 10.2 (1973): 112-122.

Schroeder, William J., Jonathan A. Zarge, and William E. Lorensen. "Decimation of triangle meshes." ACM Siggraph Computer Graphics. Vol.

No. 2. ACM, 1992.

Shapes¶

mesh NURB brep CSG frep

Pasko, Alexander, et al. "Function representation in geometric modeling: concepts, implementation and applications." The Visual Computer 11.8 (1995): 429-446.

Boolean distance metric interval arithmetic octree

Duff, Tom. "Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry." ACM SIGGRAPH Computer Graphics. Vol. 26. No. 2. ACM, 1992.

Pion, Sylvain. "Interval arithmetic: An efficient implementation and an application to computational geometry." Workshop on Applications of Interval Analysis to systems and Control (MISC). 1999.

Hu, Chun-Yi, Nicholas M. Patrikalakis, and Xiuzi Ye. "Robust interval solid modelling part I: representations." Computer-Aided Design 28.10 (1996): 807-817.

Hu, Chun-Yi, Nicholas M. Patrikalakis, and Xiuzi Ye. "Robust interval solid modelling part II: boundary evaluation." Computer-Aided Design 28. 10 (1996): 819-830.

ASDF

Frisken, Sarah F., et al. "Adaptively sampled distance fields: a general representation of shape for computer graphics." Proceedings of the 27th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 2000.

Hierarchical Volumetric Object Representations for Digital Fabrication Workflows, Matthew Keeter (May 2013)

folding

Cheung, Kenneth C., et al. "Programmable assembly with universally foldable strings (moteins)." Robotics, IEEE Transactions on 27.4 (2011): 718-729.

Demaine, Erik D., and Joseph O’Rourke. Geometric folding algorithms. Cambridge: Cambridge University Press, 2007.

Distances¶

offset

biarc

Bolton, K. M. "Biarc curves." Computer-Aided Design 7.2 (1975): 89-92.

discretize thicken, thin, fill distance transform

naive $N^2$

Rosenfeld, Azriel, and John L. Pfaltz. "Distance functions on digital pictures." Pattern recognition 1.1 (1968): 33-61.

Saito, Toyofumi, and Jun-Ichiro Toriwaki. "New algorithms for euclidean distance transformation of an< i> n</i>-dimensional digitized picture with applications." Pattern recognition 27.11 (1994): 1551-1565.

Xu, Dong, and Hua Li. "Euclidean distance transform of digital images in arbitrary dimensions." Advances in Multimedia Information Processing- PCM 2006. Springer Berlin Heidelberg, 2006. 72-79.

pixel $p_{ij}$ zero interior nonzero exterior

$$ f_{ij} = \min_{x \in {\rm interior}} (i-x)^2 $$

sweep left, right

every point assigned

$$ g_{ij} = \min_{y \in {\rm interior}} f_{iy} + (j-y)^2 $$

sweep up, down

$$ \ba g_{ij} &=& \min_{y \in {\rm interior}} f_{iy} + (j-y)^2\\ &=& \min_{y \in {\rm interior}} \min_{x \in {\rm interior}} (i-x)^2 + (j-y)^2 = 0 \ea $$

bound distance by $f$

higher dimensions

skeletonization

photogrammetry triangulation structured light Gray code

Lanman, Douglas, and Gabriel Taubin. "Build your own 3D scanner: 3D photography for beginners." ACM SIGGRAPH 2009 Courses. ACM, 2009.

Rotations¶

quaternions

Hamilton, William Rowan, and William Edwin Hamilton. Elements of quaternions. London: Longmans, Green, & Company, 1866.

Kuipers, Jack B. Quaternions and rotation sequences. Vol. 66. Princeton: Princeton university press, 1999.

Lie groups

Arthur Tresse (1893). "Sur les invariants différentiels des groupes continus de transformations". Acta Mathematica 18: 1–88.

Berry's phase

Berry, Michael V. "Quantal phase factors accompanying adiabatic changes. " Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 392.1802 (1984): 45-57.

Zwanziger, Josef W., Marianne Koenig, and Alexander Pines. "Berry's phase." Annual Review of Physical Chemistry 41.1 (1990): 601-646.

Graphs¶

types linked lists

routing shortest path

Dijkstra's algorithm

Dijkstra, Edsger W. "A note on two problems in connexion with graphs." Numerische mathematik 1.1 (1959): 269-271.

Fredman, Michael L., and Robert Endre Tarjan. "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM (JACM) 34.3 (1987): 596-615.

dynamic programing mathematical programing

Bellman-Ford

Bellman, Richard. On a routing problem. No. RAND-P-1000. RAND CORP SANTA MONICA CA, 1956.

Ford, Lester R., and Delbert R. Fulkerson. "Maximal flow through a network." Canadian Journal of Mathematics 8.3 (1956): 399-404.

Hamiltonian path, TSP NP complete relaxations

References¶

Preparata, Franco P., & Shamos, Michael Ian. (1985). Computational Geometry: An Introduction. New York: Springer-Verlag.

de Berg, Mark, Cheong, Otfried, van Kreveld, Marc, & Overmars, Mark. (2010). Computational Geometry: Algorithms and Applications. 3rd edn.

Old and new classics.

Problems¶

FRep
720 rotation
mesh routing