11.14 Basic Algorithms for Three-Dimensional Computations

Chapter Contents (Back)
Three Dimensional Computations. The section is for methods that are not really vision, but are algorithms that are used by vision people.

Udupa, K.J., and Murthy, I.S.N.,
New Concepts for Three-Dimensional Shape Analysis,
TC(26), No. 10, October 1977, pp. 1043-1049. See also Some new concepts for encoding line patterns. BibRef 7710

Udupa, K.J., and Murthy, I.S.N.,
Machine Visualization of Three-Dimensional Objects via Skeletal Transformations,
SMC(7), 1977, pp. 424-434. BibRef 7700

Sinha, S.S., Jain, R.,
Range Image Analysis,
HPRIP-CV94(185-237). BibRef 9400

Lee, Y.T., Requicha, A.A.G.,
Algorithms for Computing the Volume and Other Integral Properties of Solids,
CACM(25), 1982, pp. 635-650. BibRef 8200

Mantyla, M., Tamminen, M.,
Localized Set Operations for Solid Modeling,
Computer Graphics(17), No. 3, 1983, pp. 279-288. BibRef 8300

Gordon, W.J.,
An Operator Calculus for Surface and Volume Modeling,
IEEE_CGA(3), No. 7, October 1983, pp. 18-22. BibRef 8310

Langridge, D.J.,
Detection of Discontinuities in the First Derivatives of Surfaces,
CVGIP(27), No. 3, September 1984, pp. 291-308.
Elsevier DOI Derived from curves: See also Curve Encoding and the Detection of Discontinuities. BibRef 8409

Ritter, G.X.[Gerhard X.], Tou, J.T.[Julius T.],
The Encoding of Arbitrary Surfaces in 3-Dimensional Space,
PR(17), No. 6, 1984, pp. 593-606.
Elsevier DOI Surface triangulation provides a chain code. BibRef 8400

Koparkar, P.A., Mudur, S.P.,
Computational Techniques for Processing Parametric Surfaces,
CVGIP(28), No. 3, December 1984, pp. 303-322.
Elsevier DOI rendering, intersection detection, silhouette detection. BibRef 8412

Sederberg, T.W., Anderson, D.C., Goldman, R.N.,
Implicit Representation of Parametric Curves and Surfaces,
CVGIP(28), No. 1, October 1984, pp. 72-84.
Elsevier DOI Closed form solutions for parametric curves and surfaces. BibRef 8410

Bajaj, C.L., Hoffmann, C.M., Lynch, R.E., and Hopcroft, J.E.H.,
Tracing surface intersections,
CAGD(5), No. 4, November 1988, pp. 285-307. BibRef 8811

Kriezis, G.A., Patrikalakis, N.M., and Wolter, F.E.,
Topological and differentialequation methods for surface intersections,
CAD(24), No. 1, January 1992, pp. 41-55. BibRef 9201

Abdel-Malek, K., and Yeh, H.,
Determining intersection curves between surfaces of two solids,
CAD(28), No. 6-7, June-July 1996, pp. 539-549. BibRef 9606

Barnhill, R.E., Farin, G., Jordan, M., and Piper, B.R.,
Surface/Surface Intersection,
CAGD(4), No. 1-2, July 1987, pp. 3-16. BibRef 8707

Barnhill, R.E., and Kersey, S.N.,
A marching method for parametric surface/surface intersection,
CAGD(7), No. 1-4, June 1990, pp. 257.280. BibRef 9006

Jain, R.C.[Ramesh C.], and Jain, A.K.[Anil K.],
Report on Range Image Understanding Workshop,
East Lansing, Michigan, March 21-23, 1988, MVA(2), No. 1, 1989, pp. 45-60. BibRef 8900

Chattopadhyay, S., Das, P.P.,
Parameter Estimation and Reconstruction of Digital Conics in Normal Positions,
GMIP(54), No. 5, September 1992, pp. 385-395. BibRef 9209

Bhandarkar, S.M., Siebert, A.,
INTEGRA: An Integrated System For Range Image Understanding,
PRAI(6), No. 5, 1992, pp. 913-953. BibRef 9200
Earlier: ICPR92(I:624-627).

Corby, N.R., and Mundy, J.L.,
Applications of Range Image Sensing and Processing,
AIRI90(255-272). BibRef 9000

Herman, G.T.[Gabor T.],
Discrete Multidimensional Jordan Surfaces,
GMIP(54), No. 6, November 1992, pp. 507-515. BibRef 9211

Herman, G.T.[Gabor T.],
Finitary 1-Simply Connected Digital Spaces,
GMIP(60), No. 1, January 1998, pp. 46-56. BibRef 9801

Herman, G.T.[Gabor T.], Zhao, E.P.,
Jordan Surfaces in Simply Connected Digital Spaces,
JMIV(6), No. 2-3, June 1996, pp. 121-138. 9608

Latecki, L.J., Ma, C.M.,
An Algorithm for a 3D Simplicity Test,
CVIU(63), No. 2, March 1996, pp. 388-393.
DOI Link BibRef 9603

Barth, E.[Erhardt], Caelli, T.M.[Terry M.], Zetzsche, C.[Christoph],
Image Encoding, Labeling and Reconstruction from Differential Geometry,
GMIP(55), 1993, pp. 428-446. BibRef 9300

Barth, E.[Erhardt], Caelli, T.M.[Terry M.], Zetzsche, C.[Christoph],
Efficient Visual Representation and Reconstruction from Generalized Curvature Measures,
SPIE(1570), 1991, pp. 86-95 BibRef 9100

Loop, C.,
Smooth Spline Surfaces over Irregular Meshes,
Computer Graphics(28), 1994, pp. 303-310. BibRef 9400

Chionh, E.W.[Eng-Wee], Goldman, R.N.[Ronald N.],
On the Existence and the Coefficients of the Implicit Equation of Rational Surfaces,
GMIP(56), No. 1, January 1994, pp. 19-yy. BibRef 9401

Francon, J.,
Discrete Combinatorial Surfaces,
GMIP(57), No. 1, January 1995, pp. 20-26. BibRef 9501

Thurfjell, L., Bengtsson, E., Nordin, B.,
A Boundary Approach for Fast Neighborhood Operations on 3-Dimensional Binary Data,
GMIP(57), No. 1, January 1995, pp. 13-19. BibRef 9501

Thirion, J.P.,
The Extremal Mesh and the Understanding of 3D Surfaces,
IJCV(19), No. 2, August 1996, pp. 115-128.
Springer DOI 9609

Thirion, J.P., Gourdon, A.,
Computing the Differential Characteristics of Isointensity Surfaces,
CVIU(61), No. 2, March 1995, pp. 190-202.
DOI Link BibRef 9503

Saha, P.K., Chaudhuri, B.B.,
3D Digital Topology under Binary Transformation with Applications,
CVIU(63), No. 3, May 1996, pp. 418-429.
DOI Link 9606

Chaudhuri, B.B.,
A New Definition of Neighborhood of a Point in Multidimensional Space,
PRL(17), No. 1, January 10 1996, pp. 11-17. BibRef 9601

Bhansali, S., Kramer, G.A., and Hoar, T.J.,
A Principled Approach Towards Symbolic Geometric Constraint Satisfaction,
JAIR(4), 1996, pp. 419-443. 9606
Find the configuration of a collection of geometric bodies so as to satisfy a set of given constraints. Uses degree of freedom analysis, and plan fragments.
HTML Version. BibRef

Evako, A.V.[Alexander V.], Kopperman, R., Mukhin, Y.V.,
Dimensional Properties of Graphs and Digital Spaces,
JMIV(6), No. 2-3, June 1996, pp. 109-119. 9608

Evako, A.V.[Alexander V.],
Topological properties of closed digital spaces: One method of constructing digital models of closed continuous surfaces by using covers,
CVIU(102), No. 2, May 2006, pp. 134-144.
Elsevier DOI Computer graphics 0605

Kiryati, N.[Nahum], Székely, G.[Gabor],
Estimating Shortest Paths and Minimal Distances on Digitized Three-Dimensional Surfaces,
PR(26), No. 11, November 1993, pp. 1623-1637.
Elsevier DOI combine length estimators and shortest paths in graphs. BibRef 9311

Tolimieri, R., An, M.,
Algebra Of Multidimensional Multirate Structures,
IJIST(7), No. 4, Winter 1996, pp. 421-425. 9612

Ching, W.S.,
A Fast and Effective Occlusion Detection Algorithm,
PRAI(9), 1995, pp. 565-578. BibRef 9500

Komen, E.R.,
View Angle Transformations,
PRL(12), 1991, pp. 273-278. BibRef 9100

Toffoli, T., Quick, J.,
3-Dimensional Rotations by 3 Shears,
GMIP(59), No. 2, March 1997, pp. 89-95. 9704

Cameron, S.,
A Comparison of 2 Fast Algorithms for Computing the Distance Between Convex Polyhedra,
RA(13), No. 6, December 1997, pp. 915-920. 9801

Kitamura, Y., Smith, A., Takemura, H., Kishino, F.,
A Real-Time Algorithm for Accurate Collision Detection for Deformable Polyhedral Objects,
PTVE(7), No. 1, February 1998, pp. 36-52. 9803

Malgouyres, R.[Rémy], Bertrand, G.[Gilles],
A new local property of strong n-surfaces,
PRL(20), No. 4, April 1999, pp. 417-428. BibRef 9904

Kaufman, A., Dachille, F., Chen, B., Bitter, I., Kreeger, K., Zhang, N., Tang, Q.,
Real-time volume rendering,
IJIST(11), No. 1, 2000, pp. 44-52. 0005

Max, N.L.[Nelson L.], Williams, P.[Peter], Silva, C.[Claudio],
Approximate volume rendering for curvilinear and unstructured grids by hardware-assisted polyhedron projection,
IJIST(11), No. 1, 2000, pp. 53-61. 0005

Malgouyres, R., Bertrand, G.,
Complete Local Characterization of Strong 26-Surfaces: Continuous Analogs for Strong 26-Surfaces,
PRAI(13), No. 4, June 1999, pp. 465. 0005

Lee, R.K.[Rae Kyoung], Ihm, I.[Insung],
On Enhancing the Speed of Splatting Using Both Object- and Image-Space Coherence,
GM(62), No. 4, July 2000, pp. 263-282. Volume Rendering 0006

Chen, B.Q.[Bao-Quan], Kaufman, A.[Arie],
3D Volume Rotation Using Shear Transformations,
GM(62), No. 4, July 2000, pp. 308-322. 0006

Kim, M.S.[Myung-Soo], Seidel, H.P.[Hans-Peter],
Special Issue on Pacific Graphics '99 in Graphical Models,
GM(62), No. 6, November 2000, pp. 389-389. 0102
Some of the papers are included as relevant to vision. BibRef

Berthilsson, R.[Rikard], Ĺström, K.[Kalle], Heyden, A.[Anders],
Reconstruction of General Curves, Using Factorization and Bundle Adjustment,
IJCV(41), No. 3, February-March 2001, pp. 171-182.
DOI Link 0105
Reconstruction of Curves in R3, using Factorization and Bundle Adjustment,
IEEE DOI Extend affine shape from point sets to curves. See also Simplifications of Multilinear Forms for Sequences of Images. BibRef

Berthilsson, R.[Rikard], Astrom, K.[Kalle], and Heyden, A.[Anders],
Projective Reconstruction of 3D-Curves from Its 2D-Images Using Error Models and Bundle Adjustments,
HTML Version. 9705

Turlington, J.Z., Higgins, W.E.,
New techniques for efficient sliding thin-slab volume visualization,
MedImg(20), No. 8, August 2001, pp. 823-835.
IEEE Top Reference. 0110

Wolf, L.[Lior], Shashua, A.[Amnon],
On Projection Matrices P^k, -> P^2, k=,3..., 6, and their Applications in Computer Vision,
IJCV(48), No. 1, June 2002, pp. 53-67.
DOI Link 0204
Earlier: ICCV01(I: 412-419).
Award, Marr Prize, HM. Honorable mention. BibRef

Gagvani, N.[Nikhil], Silver, D.[Deborah],
Animating Volumetric Models,
GM(63), No. 6, November 2001, pp. 443-458.
DOI Link 0208

Zoeter, O.[Onno], Heskes, T.[Tom],
Hierarchical visualization of time-series data using switching linear dynamical systems,
PAMI(25), No. 10, October 2003, pp. 1202-1214.
IEEE Abstract. 0310
Visualize high dimensional data. BibRef

Allen, P.K.[Peter K.], Troccoli, A.[Alejandro], Smith, B.[Benjamin], Murray, S.[Stephen], Stamos, I.[Ioannis], Leordeanu, M.[Marius],
New Methods for Digital Modeling of Historic Sites,
IEEE_CGA(23), No. 6, November/December, 2003, pp. 32-41.
HTML Version. BibRef 0311

Allen, P.K., Feiner, S., Troccoli, A., Benko, H., Ishak, E., Smith, B.,
Seeing into the Past: Creating a 3D Modeling Pipeline for Archaeological Visualization,

Troccoli, A.[Alejandro], Allen, P.K.[Peter K.],
Shadow based texture registration for 3D modeling of outdoor scenes,
MVA(18), No. 2, April 2007, pp. 65-72.
Springer DOI 0704
Relighting acquired models of outdoor scenes,

Troccoli, A.[Alejandro], Allen, P.K.[Peter K.],
Building Illumination Coherent 3D Models of Large-Scale Outdoor Scenes,
IJCV(78), No. 2-3, July 2008, pp. 261-280.
Springer DOI 0803

Kaminski, J.Y.[Jeremy Yermiyahou], Shashua, A.[Amnon],
Multiple View Geometry of General Algebraic Curves,
IJCV(56), No. 3, February-March 2004, pp. 195-219.
DOI Link 0402
On Calibration and Reconstruction from Planar Curves,
ECCV00(I: 678-694).
Springer DOI 0003

Kaminski, J.Y.[Jeremy Yermiyahou], Fryers, M.[Michael], Shashua, A.[Amnon], Teicher, M.[Mina],
Multiple View Geometry of Non-planar Algebraic Curves,
ICCV01(II: 181-186).
Curves and lines in 3-D BibRef

Park, S.[Sangmin], Bajaj, C.[Chandrajit],
Feature selection of 3D volume data through multi-dimensional transfer functions,
PRL(28), No. 3, 1 February 2007, pp. 367-374.
Elsevier DOI 0701
Volume rendering; Transfer functions BibRef

Wang, T.[Taehyung], Sheu, P.C.Y.[Phillip C. Y.],
An Object-oriented Bsp Tree Algorithm For Hidden Surface Removal,
IJIG(2), No. 3, July 2002, pp. 395-411. 0207

Faudot, D.[Dominique], Gesquiere, G.[Gilles],
Study of Volume Variation of Implicit Objects,
IJIG(6), No. 4, October 2006, pp. 551-568. 0610

Dorst, L.[Leo], Lasenby, J.[Joan], (Eds.)
Guide to Geometric Algebra in Practice,
Springer2011. ISBN: 978-0-85729-810-2.
WWW Link. 1109

Lai, R.J.[Rong-Jie], Chan, T.F.[Tony F.],
A framework for intrinsic image processing on surfaces,
CVIU(115), No. 12, December 2011, pp. 1647-1661.
Elsevier DOI 1111
Computational differential geometry; Imaging on surfaces; Total variation; Image denoising; Image segmentation generalize Rudin-Osher-Fatemi (ROF) denoising model ( See also Nonlinear total variation based noise removal algorithms. ) and convexified Chan-Vese (CV) segmentation model ( See also Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model, A. ) on surfaces BibRef

Saracchini, R.F.V.[Rafael F. V.], Stolfi, J.[Jorge], da Gama Leităo, H.C.[Helena C.], Atkinson, G.A.[Gary A.], Smith, M.L.[Melvyn L.],
A robust multi-scale integration method to obtain the depth from gradient maps,
CVIU(116), No. 8, August 2012, pp. 882-895.
Elsevier DOI 1205
Multi-scale Integration of Slope Data on an Irregular Mesh,
PSIVT11(I: 109-120).
Springer DOI 1111
Multi-scale Depth from Slope with Weights,
HTML Version. 1009
Computer vision; Multi-scale methods; Gradient map integration; Surface reconstruction Integration of the slope map. See also Uniform Grid Structure to Speed Up Example-Based Photometric Stereo, A. BibRef

Lin, Y.H.[Yu-Hsun], Tsai, M.H.[Ming-Hung], Wu, J.L.[Ja-Ling],
Depth sculpturing for 2D paintings: A progressive depth map completion framework,
JVCIR(25), No. 4, 2014, pp. 670-678.
Elsevier DOI 1403
Interactive 3D. 2D painting Interactive depth. BibRef

Yao, B.[Bin], Wu, H.[Hua], Yang, Y.[Yun], Chao, Y.[Yuyan], Ohta, A.[Atsushi], Kawanaka, H.[Haruki], He, L.F.[Li-Feng],
An Efficient Strategy for Bit-Quad-Based Euler Number Computing Algorithm,
IEICE(E97-D), No. 5, May 2014, pp. 1374-1378.
WWW Link. 1405

Yao, B.[Bin], He, L.F.[Li-Feng], Kang, S.Y.[Shi-Ying], Zhao, X.[Xiao], Chao, Y.[Yuyan],
A Further Improvement on Bit-Quad-Based Euler Number Computing Algorithm,
IEICE(E99-D), No. 2, February 2016, pp. 545-549.
WWW Link. 1604

Yao, B.[Bin], He, L.F.[Li-Feng], Kang, S.Y.[Shi-Ying], Zhao, X.[Xiao], Chao, Y.[Yuyan],
Bit-Quad-Based Euler Number Computing,
IEICE(E100-D), No. 9, September 2017, pp. 2197-2204.
WWW Link. 1709

He, L.F.[Li-Feng], Zhao, X.[Xiao], Yao, B.[Bin], Yang, Y.[Yun], Chao, Y.[Yuyan],
An Efficient Two-Scan Labeling Algorithm for Binary Hexagonal Images,
IEICE(E97-D), No. 12, December 2014, pp. 3244-3247.
WWW Link. 1503

Krotzsch, G.[Guillermo], Uriostegui, K.[Kenan], Wolf, K.B.[Kurt Bernardo],
Unitary rotations in two-, three-, and D-dimensional Cartesian data arrays,
JOSA-A(31), No. 7, July 2014, pp. 1531-1535.
DOI Link 1407
Three-dimensional image processing BibRef

Xu, J.Q.[Jian-Qiu], Güting, R.H.[Ralf Hartmut],
Querying visible points in large obstructed space,
GeoInfo(19), No. 3, July 2015, pp. 435-461.
Springer DOI 1505
Spatial database, nearest neighhbors. BibRef

Xu, J.Q.[Jian-Qiu], Güting, R.H.[Ralf Hartmut], Zheng, Y.[Yu],
The TM-RTree: an index on generic moving objects for range queries,
GeoInfo(19), No. 3, July 2015, pp. 487-524.
Springer DOI 1505

Huska, M.[Martin], Morigi, S.[Serena],
A meshless strategy for shape diameter analysis,
VC(33), No. 3, March 2017, pp. 303-315.
WWW Link. 1702

Szirmay-Kalos, L.[László], Magdics, M.[Milán], Tóth, B.[Balázs],
Volume enhancement with externally controlled anisotropic diffusion,
VC(33), No. 3, March 2017, pp. 331-342.
WWW Link. 1702

Kukelova, Z.[Zuzana], Heller, J.[Jan], Fitzgibbon, A.[Andrew],
Efficient Intersection of Three Quadrics and Applications in Computer Vision,

Domenjoud, E.[Eric], Provençal, X.[Xavier], Vuillon, L.[Laurent],
Facet Connectedness of Discrete Hyperplanes with Zero Intercept: The General Case,
Springer DOI 1410

Morsdorf, F., Frey, O., Koetz, B., Meier, E.,
Ray Tracing for Modeling of Small Footprint Airborne Laser Scanning Returns,
PDF File. 0709

Weise, T.[Thibaut], Leibe, B.[Bastian], Van Gool, L.J.[Luc J.],
Accurate and robust registration for in-hand modeling,

Van Gool, L.J.[Luc J.], Leibe, B.[Bastian], Muller, P.[Pascal], Vergauwen, M.[Maarten], Weise, T.[Thibaut],
3D Challenges and a Non-In-Depth Overview of Recent Progress,

Quan, W.[Wu], Huang, M.L.[Mao Lin],
Dynamic Visualization of Spatially Referenced Information,
Springer DOI 0512

Drewes, H.[Heiko], Schmidt, A.[Albrecht],
WYSIWYG-Tool Tips: Enhancing Tool Tips with Translucent Preview Bitmaps,
Springer DOI 0512

Liu, D.C.[Dong C.], Hou, L.L.[Long-Long], Liu, P.S.[Paul S.],
Motion Visualization of Ultrasound Imaging,
Springer DOI 0512

Silva, F.G.M.[Frutuoso G.M.], Gomes, A.J.P.[Abel J.P.],
Oversimplified Euler Operators for a Non-oriented, Non-manifold B-Rep Data Structure,
Springer DOI 0512

Budiu, M.[Mihai],
Spatial Computation,
CMU-CS-TR-03-217. 2003. BibRef 0300 Ph.D.Thesis.
HTML Version. 0501

Chai, J.X.[Jin-Xiang], Shum, H.Y.[Heung-Yeung],
Parallel Projections for Stereo Reconstruction,
CVPR00(II: 493-500).

Pervin, E.[Edward], and Webb, J.A.[Jon A.],
Quaternions in Computer Vision and Robotics,
CVPR83(383-383). BibRef 8300
And: CMU-CS-TR-82-150, CMU CS Dept., Fall 1982. Discusses some of the problems with using vectors for robotics and vision and proposes quaternions, 4 vectors with certain properties which allow division of vectors. Primarily it shows that you can do the usual things in computer vision with them. BibRef

Buesching, D.,
Efficiently Finding Bitangents,
ICPR96(I: 428-432).
(Technical Univ. of Muenich, D) BibRef

Koivunen, V.[Visa], Bajcsy, R.[Ruzena],
Spline representations in 3-D vision,
Springer DOI 9412
Geometric Methods for Building CAD Models from Range Data,
SPIE(2031), 1993, pp. 205-216. BibRef

Koivunen, V.[Visa], Kuosmanen, P., Astola, J.T.,
Orthogonal Spline Fitting in Range Data,
ICIP96(II: 385-388).
IEEE DOI BibRef 9600

Chakrabarti, C., Lucke, L.,
Efficient architectures for hidden surface removal,
ICIP94(I: 661-665).

Gudmundsson, B.[Björn], Tegenfeldt, C.[Clas],
Fast shadowing of volume data,
Springer DOI 9309

Chen, S.W.[Sei-Wang], Stockman, G.C.[George C.], and Shrikhande, N.[Neelima],
Constructing Constraint Tables for Model-Based Recognition and Localization,
MSU-ENGR-85-34, Mich. State Univ., 1985. Recognition, Model Based. Model Based Recognition. Compute the distances between 3-D geometric entities. BibRef 8500

Kasvand, T.,
The K1K2 Space in Range Image Analysis,
ICPR88(II: 923-926).
IEEE DOI BibRef 8800

Kasvand, T.,
Surface Curvatures in 3D Range Images,
ICPR86(842-845). BibRef 8600

Sethi, I.K., Jayaramamurthy, S.N.,
Surface Classification Using Characteristic Contours,
ICPR84(438-440). BibRef 8400

Bajcsy, R.,
Three-Dimensional Scene Analysis,
ICPR80(1064-1074). BibRef 8000

Chapter on 3-D Object Description and Computation Techniques, Surfaces, Deformable, View Generation, Video Conferencing continues in
Surface, Volume Intersections .

Last update:Feb 26, 2018 at 13:41:56