Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes

Arie Kaufman

doi:10.1145/37401.37423

Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes

Arie Kaufman

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

30 Scopus citations

Abstract

Three-dimensional (3D) scan-conversion algorithms,. that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements. The algorithms introduced here employ third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the CUBE Architecture, which is a voxelbased system for 3D graphics.

Original language	English
Title of host publication	Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987
Editors	Maureen C. Stone
Publisher	Association for Computing Machinery, Inc
Pages	171-179
Number of pages	9
ISBN (Electronic)	0897912276, 9780897912273
DOIs	https://doi.org/10.1145/37401.37423
State	Published - Aug 1 1987
Event	14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987 - Anaheim, United States Duration: Jul 27 1987 → Jul 31 1987

Publication series

Name	Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987

Conference

Conference	14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987
Country/Territory	United States
City	Anaheim
Period	07/27/87 → 07/31/87

Keywords

Bezier curves
Bezier surfaces
Bezier volumes
Cubic Frame Buffer
Three-dimensional scan conversion
Voxel

Access to Document

10.1145/37401.37423

Cite this

Kaufman, A. (1987). Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. In M. C. Stone (Ed.), Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987 (pp. 171-179). (Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987). Association for Computing Machinery, Inc. https://doi.org/10.1145/37401.37423

Kaufman, Arie. / Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987. editor / Maureen C. Stone. Association for Computing Machinery, Inc, 1987. pp. 171-179 (Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987).

@inproceedings{04a4369f9fce45248575fa9a1ae236d0,

title = "Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes",

abstract = "Three-dimensional (3D) scan-conversion algorithms,. that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements. The algorithms introduced here employ third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the CUBE Architecture, which is a voxelbased system for 3D graphics.",

keywords = "Bezier curves, Bezier surfaces, Bezier volumes, Cubic Frame Buffer, Three-dimensional scan conversion, Voxel",

author = "Arie Kaufman",

year = "1987",

month = aug,

day = "1",

doi = "10.1145/37401.37423",

language = "English",

series = "Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987",

publisher = "Association for Computing Machinery, Inc",

pages = "171--179",

editor = "Stone, \{Maureen C.\}",

booktitle = "Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987",

note = "14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987 ; Conference date: 27-07-1987 Through 31-07-1987",

}

Kaufman, A 1987, Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. in MC Stone (ed.), Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987. Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987, Association for Computing Machinery, Inc, pp. 171-179, 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987, Anaheim, United States, 07/27/87. https://doi.org/10.1145/37401.37423

Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. / Kaufman, Arie.
Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987. ed. / Maureen C. Stone. Association for Computing Machinery, Inc, 1987. p. 171-179 (Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes

AU - Kaufman, Arie

PY - 1987/8/1

Y1 - 1987/8/1

N2 - Three-dimensional (3D) scan-conversion algorithms,. that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements. The algorithms introduced here employ third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the CUBE Architecture, which is a voxelbased system for 3D graphics.

AB - Three-dimensional (3D) scan-conversion algorithms,. that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements. The algorithms introduced here employ third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the CUBE Architecture, which is a voxelbased system for 3D graphics.

KW - Bezier curves

KW - Bezier surfaces

KW - Bezier volumes

KW - Cubic Frame Buffer

KW - Three-dimensional scan conversion

KW - Voxel

UR - https://www.scopus.com/pages/publications/84971476654

U2 - 10.1145/37401.37423

DO - 10.1145/37401.37423

M3 - Conference contribution

AN - SCOPUS:84971476654

T3 - Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987

SP - 171

EP - 179

BT - Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987

A2 - Stone, Maureen C.

PB - Association for Computing Machinery, Inc

T2 - 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987

Y2 - 27 July 1987 through 31 July 1987

ER -

Kaufman A. Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes. In Stone MC, editor, Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987. Association for Computing Machinery, Inc. 1987. p. 171-179. (Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1987). doi: 10.1145/37401.37423

Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this