DOI: 10.1145/321466.321468. A Procedure for Detecting Intersections of Three-Dimensional Objects

A Procedure for Detecting Intersections of Three-Dimensional Objects

10.1145/321466.321468

Crossref journal-article

Association for Computing Machinery (ACM)

Journal of the ACM (320)

Abstract

As a step toward the solution of the placement problem in engineering design, a procedure has been developed for detecting intersections of convex regions in 3-space by means of a pseudocharacteristic function. The mathematical techniques underlying the procedure are discussed, and a system of programs embodying these techniques is described. As a special case a solution is given for the hidden-line problem in graphic display.

Bibliography

Comba, P. G. (1968). A Procedure for Detecting Intersections of Three-Dimensional Objects. Journal of the ACM, 15(3), 354â366.

Authors 1

Paul G. Comba (first)

References 16 Referenced 39

Three-dimensional placement and routing. Form E20-0119 , IBM Corp. , 1963 . Three-dimensional placement and routing. Form E20-0119, IBM Corp., 1963. / IBM Corp. (1963)
10.1145/321328.321330
MERTZ R.T. Private communication. MERTZ R.T. Private communication.
CARROLL , CHARL ES W . The created response surface technique for optimizing nonlinear, restrained systems . Oper. Res. 9 ( 1961 ), 169 - 184 . CARROLL, CHARLES W. The created response surface technique for optimizing nonlinear, restrained systems. Oper. Res. 9 (1961), 169-184. (10.1287/opre.9.2.169) / Oper. Res. / The created response surface technique for optimizing nonlinear, restrained systems by CARROLL ES W (1961)
COLVILLE A. R. JR. Process optimization program POP. 7040-H9 IBM0007. COLVILLE A. R. JR. Process optimization program POP. 7040-H9 IBM0007.
FLETCHER , R. , AND POWELL , M. J. D . A rapidly convergent descent method for minimization . Comput. J. 6 ( 1963 ), 163 - 168 . FLETCHER, R., AND POWELL, M. J.D. A rapidly convergent descent method for minimization. Comput. J. 6 (1963), 163-168. (10.1093/comjnl/6.2.163) / Comput. J. / A rapidly convergent descent method for minimization by FLETCHER R. (1963)
DAVIDON W. C. Variable metric method for minimization. A.E.C. Res. and Develop. Rep. ANL-5990 (Rev.). (Cited in {6}.) DAVIDON W. C. Variable metric method for minimization. A.E.C. Res. and Develop. Rep. ANL-5990 (Rev.). (Cited in {6}.)
Box, M.J . A comparison of several current optimization methods, and the use of transformations in constrained problems . Comput. J. 9 ( 1966 ), 67 - 77 . Box, M.J. A comparison of several current optimization methods, and the use of transformations in constrained problems. Comput. J. 9 (1966), 67-77. (10.1093/comjnl/9.1.67) / Comput. J. / A comparison of several current optimization methods, and the use of transformations in constrained problems (1966)
WILDE , DOUGLA SS J ., AND BEIGHTLER , CHARL ES S . Foundation8 of OpTimizalion . Prentice- Hall , Englewood Cliffs, N. J. , 1967 . WILDE, DOUGLASS J., AND BEIGHTLER, CHARLES S. Foundation8 of OpTimizalion. Prentice- Hall, Englewood Cliffs, N. J., 1967. / Foundation8 of OpTimizalion by WILDE SS J (1967)
ROSEN , EDWA RD M . A review of quasi-Newton methods in nonlinear equation solving and unconstrained optimization . Proe. ACM 21st Nat. Conf., ACM Pub. P-66 , Thompson Book Co., Washington, D. C. , 1966 , pp. 37 - 41 . 10.1145/800256.810678 ROSEN, EDWARD M. A review of quasi-Newton methods in nonlinear equation solving and unconstrained optimization. Proe. ACM 21st Nat. Conf., ACM Pub. P-66, Thompson Book Co., Washington, D. C., 1966, pp. 37-41. 10.1145/800256.810678 / Proe. ACM 21st Nat. Conf., ACM Pub. P-66 by ROSEN RD M (1966)
10.1145/363744.363788
LOUTREL , PHIL IPPE . A solution to the "hidden-line" problem for computer-drawn polyhedra. Doctoral Diss ., Dep. Elec. Eng. , New York U., New York , N. Y. , 1967 . LOUTREL, PHILIPPE. A solution to the "hidden-line" problem for computer-drawn polyhedra. Doctoral Diss., Dep. Elec. Eng., New York U., New York, N. Y., 1967. / Dep. Elec. Eng. by LOUTREL IPPE (1967)
WYLIE , C ,, ROMNEY , G. , EVANS , D. , AND ERDA t IL, A . IIalf-tone perspective drawings by computer . Proc. AFIPS 1967 Fall Joint Comput. Conf. , Vol. 31 , pp. 49 - 58 (Thompson Book Co., Washington, D. C.). WYLIE, C,, ROMNEY, G., EVANS, D., AND ERDAtIL, A. IIalf-tone perspective drawings by computer. Proc. AFIPS 1967 Fall Joint Comput. Conf., Vol. 31, pp. 49-58 (Thompson Book Co., Washington, D. C.). / Proc. AFIPS 1967 Fall Joint Comput. Conf. by WYLIE C
10.1145/363958.363993
APPEL , A. The notion of quantitative invisibility and the machine rendering of solids . Proc. ACM 22nd Nat. Conf., ACM Pub. P-67 , Thompson Book Co., Washington, D. C. , 1967 , pp. 387 - 393 . 10.1145/800196.806007 APPEL, A. The notion of quantitative invisibility and the machine rendering of solids. Proc. ACM 22nd Nat. Conf., ACM Pub. P-67, Thompson Book Co., Washington, D. C., 1967, pp. 387-393. 10.1145/800196.806007 / Proc. ACM 22nd Nat. Conf., ACM Pub. P-67 by APPEL A. (1967)
OXAYA , Y . Graphic display of crystal structures: An example of man-machine interaction . IBM Res. Rep. RC 1706 , 1966 . OXAYA, Y. Graphic display of crystal structures: An example of man-machine interaction. IBM Res. Rep. RC 1706, 1966. / IBM Res. Rep. RC / Graphic display of crystal structures: An example of man-machine interaction by OXAYA Y (1966)

Dates

Type	When
Created	23 years ago (July 27, 2002, 7:26 a.m.)
Deposited	2 months ago (June 18, 2025, 6:54 p.m.)
Indexed	2 months ago (June 18, 2025, 7:10 p.m.)
Issued	57 years, 1 month ago (July 1, 1968)
Published	57 years, 1 month ago (July 1, 1968)
Published Online	57 years, 1 month ago (July 1, 1968)
Published Print	57 years, 1 month ago (July 1, 1968)

Funders 0

None

BibTeX

@article{Comba_1968, title={A Procedure for Detecting Intersections of Three-Dimensional Objects}, volume={15}, ISSN={1557-735X}, url={http://dx.doi.org/10.1145/321466.321468}, DOI={10.1145/321466.321468}, number={3}, journal={Journal of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Comba, Paul G.}, year={1968}, month=jul, pages={354–366} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T23:10:01Z",
    "timestamp": 1750288201670,
    "version": "3.41.0"
  },
  "reference-count": 16,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1968,
            7,
            1
          ]
        ],
        "date-time": "1968-07-01T00:00:00Z",
        "timestamp": -47433600000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1968,
        7
      ]
    ]
  },
  "abstract": "<jats:p>As a step toward the solution of the placement problem in engineering design, a procedure has been developed for detecting intersections of convex regions in 3-space by means of a pseudocharacteristic function. The mathematical techniques underlying the procedure are discussed, and a system of programs embodying these techniques is described. As a special case a solution is given for the hidden-line problem in graphic display.</jats:p>",
  "DOI": "10.1145/321466.321468",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:26:10Z",
    "timestamp": 1027769170000
  },
  "page": "354-366",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 39,
  "title": "A Procedure for Detecting Intersections of Three-Dimensional Objects",
  "prefix": "10.1145",
  "volume": "15",
  "author": [
    {
      "given": "Paul G.",
      "family": "Comba",
      "sequence": "first",
      "affiliation": [
        {
          "name": "IBM New York Scientific Center, New York, New York"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1968,
        7
      ]
    ]
  },
  "reference": [
    {
      "volume-title": "IBM Corp.",
      "year": "1963",
      "key": "e_1_2_1_1_2",
      "unstructured": "Three-dimensional placement and routing. Form E20-0119 , IBM Corp. , 1963 . Three-dimensional placement and routing. Form E20-0119, IBM Corp., 1963."
    },
    {
      "key": "e_1_2_1_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/321328.321330"
    },
    {
      "key": "e_1_2_1_3_2",
      "unstructured": "MERTZ R.T. Private communication.  MERTZ R.T. Private communication."
    },
    {
      "key": "e_1_2_1_4_2",
      "doi-asserted-by": "crossref",
      "first-page": "169",
      "DOI": "10.1287/opre.9.2.169",
      "article-title": "The created response surface technique for optimizing nonlinear, restrained systems",
      "volume": "9",
      "author": "CARROLL ES W",
      "year": "1961",
      "unstructured": "CARROLL , CHARL ES W . The created response surface technique for optimizing nonlinear, restrained systems . Oper. Res. 9 ( 1961 ), 169 - 184 . CARROLL, CHARLES W. The created response surface technique for optimizing nonlinear, restrained systems. Oper. Res. 9 (1961), 169-184.",
      "journal-title": "Oper. Res."
    },
    {
      "key": "e_1_2_1_5_2",
      "unstructured": "COLVILLE A. R. JR. Process optimization program POP. 7040-H9 IBM0007.  COLVILLE A. R. JR. Process optimization program POP. 7040-H9 IBM0007."
    },
    {
      "key": "e_1_2_1_6_2",
      "doi-asserted-by": "crossref",
      "first-page": "163",
      "DOI": "10.1093/comjnl/6.2.163",
      "article-title": "A rapidly convergent descent method for minimization",
      "volume": "6",
      "author": "FLETCHER R.",
      "year": "1963",
      "unstructured": "FLETCHER , R. , AND POWELL , M. J. D . A rapidly convergent descent method for minimization . Comput. J. 6 ( 1963 ), 163 - 168 . FLETCHER, R., AND POWELL, M. J.D. A rapidly convergent descent method for minimization. Comput. J. 6 (1963), 163-168.",
      "journal-title": "Comput. J."
    },
    {
      "key": "e_1_2_1_7_2",
      "unstructured": "DAVIDON W. C. Variable metric method for minimization. A.E.C. Res. and Develop. Rep. ANL-5990 (Rev.). (Cited in {6}.)  DAVIDON W. C. Variable metric method for minimization. A.E.C. Res. and Develop. Rep. ANL-5990 (Rev.). (Cited in {6}.)"
    },
    {
      "key": "e_1_2_1_8_2",
      "doi-asserted-by": "crossref",
      "first-page": "67",
      "DOI": "10.1093/comjnl/9.1.67",
      "article-title": "A comparison of several current optimization methods, and the use of transformations in constrained problems",
      "volume": "9",
      "year": "1966",
      "unstructured": "Box, M.J . A comparison of several current optimization methods, and the use of transformations in constrained problems . Comput. J. 9 ( 1966 ), 67 - 77 . Box, M.J. A comparison of several current optimization methods, and the use of transformations in constrained problems. Comput. J. 9 (1966), 67-77.",
      "journal-title": "Comput. J."
    },
    {
      "key": "e_1_2_1_9_2",
      "volume-title": "Foundation8 of OpTimizalion",
      "author": "WILDE SS J",
      "year": "1967",
      "unstructured": "WILDE , DOUGLA SS J ., AND BEIGHTLER , CHARL ES S . Foundation8 of OpTimizalion . Prentice- Hall , Englewood Cliffs, N. J. , 1967 . WILDE, DOUGLASS J., AND BEIGHTLER, CHARLES S. Foundation8 of OpTimizalion. Prentice- Hall, Englewood Cliffs, N. J., 1967."
    },
    {
      "key": "e_1_2_1_10_2",
      "first-page": "37",
      "volume-title": "Proe. ACM 21st Nat. Conf., ACM Pub. P-66",
      "author": "ROSEN RD M",
      "year": "1966",
      "unstructured": "ROSEN , EDWA RD M . A review of quasi-Newton methods in nonlinear equation solving and unconstrained optimization . Proe. ACM 21st Nat. Conf., ACM Pub. P-66 , Thompson Book Co., Washington, D. C. , 1966 , pp. 37 - 41 . 10.1145/800256.810678 ROSEN, EDWARD M. A review of quasi-Newton methods in nonlinear equation solving and unconstrained optimization. Proe. ACM 21st Nat. Conf., ACM Pub. P-66, Thompson Book Co., Washington, D. C., 1966, pp. 37-41. 10.1145/800256.810678"
    },
    {
      "key": "e_1_2_1_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/363744.363788"
    },
    {
      "key": "e_1_2_1_12_2",
      "volume-title": "Dep. Elec. Eng.",
      "author": "LOUTREL IPPE",
      "year": "1967",
      "unstructured": "LOUTREL , PHIL IPPE . A solution to the \"hidden-line\" problem for computer-drawn polyhedra. Doctoral Diss ., Dep. Elec. Eng. , New York U., New York , N. Y. , 1967 . LOUTREL, PHILIPPE. A solution to the \"hidden-line\" problem for computer-drawn polyhedra. Doctoral Diss., Dep. Elec. Eng., New York U., New York, N. Y., 1967."
    },
    {
      "key": "e_1_2_1_13_2",
      "first-page": "49",
      "volume-title": "Proc. AFIPS 1967 Fall Joint Comput. Conf.",
      "volume": "31",
      "author": "WYLIE C",
      "unstructured": "WYLIE , C ,, ROMNEY , G. , EVANS , D. , AND ERDA t IL, A . IIalf-tone perspective drawings by computer . Proc. AFIPS 1967 Fall Joint Comput. Conf. , Vol. 31 , pp. 49 - 58 (Thompson Book Co., Washington, D. C.). WYLIE, C,, ROMNEY, G., EVANS, D., AND ERDAtIL, A. IIalf-tone perspective drawings by computer. Proc. AFIPS 1967 Fall Joint Comput. Conf., Vol. 31, pp. 49-58 (Thompson Book Co., Washington, D. C.)."
    },
    {
      "key": "e_1_2_1_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/363958.363993"
    },
    {
      "key": "e_1_2_1_16_2",
      "first-page": "387",
      "volume-title": "Proc. ACM 22nd Nat. Conf., ACM Pub. P-67",
      "author": "APPEL A.",
      "year": "1967",
      "unstructured": "APPEL , A. The notion of quantitative invisibility and the machine rendering of solids . Proc. ACM 22nd Nat. Conf., ACM Pub. P-67 , Thompson Book Co., Washington, D. C. , 1967 , pp. 387 - 393 . 10.1145/800196.806007 APPEL, A. The notion of quantitative invisibility and the machine rendering of solids. Proc. ACM 22nd Nat. Conf., ACM Pub. P-67, Thompson Book Co., Washington, D. C., 1967, pp. 387-393. 10.1145/800196.806007"
    },
    {
      "key": "e_1_2_1_17_2",
      "first-page": "1706",
      "article-title": "Graphic display of crystal structures: An example of man-machine interaction",
      "author": "OXAYA Y",
      "year": "1966",
      "unstructured": "OXAYA , Y . Graphic display of crystal structures: An example of man-machine interaction . IBM Res. Rep. RC 1706 , 1966 . OXAYA, Y. Graphic display of crystal structures: An example of man-machine interaction. IBM Res. Rep. RC 1706, 1966.",
      "journal-title": "IBM Res. Rep. RC"
    }
  ],
  "container-title": "Journal of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/321466.321468",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/321466.321468",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T22:54:19Z",
    "timestamp": 1750287259000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/321466.321468"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1968,
        7
      ]
    ]
  },
  "references-count": 16,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          1968,
          7
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/321466.321468"
  ],
  "URL": "http://dx.doi.org/10.1145/321466.321468",
  "relation": {},
  "ISSN": [
    "0004-5411",
    "1557-735X"
  ],
  "subject": [],
  "container-title-short": "J. ACM",
  "published": {
    "date-parts": [
      [
        1968,
        7
      ]
    ]
  },
  "assertion": [
    {
      "value": "1968-07-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}