{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T05:25:13Z","timestamp":1672377913601},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[1995,1]]},"abstract":"Solid modeling underlies many technologies that are key to modern manufacturing. These range from CAD systems to robot simulators, from finite-element analysis to integrated circuit process modeling. The accuracy, and hence the utility, of these models is often constrained by the amount of computer time required to perform the desired operations. In this paper we present, in detail, an efficient algorithm for parallel intersections of solids using the Connection Machine, a massively parallel SIMD processor. We describe the data structure for representing the solid models and detail the intersection algorithm, giving special attention to implementation issues. We provide performance results, comparing the parallel algorithm to a serial intersection algorithm.<\/jats:p>","DOI":"10.1145\/200972.200976","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"21-57","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Intersecting solids on a massively parallel processor"],"prefix":"10.1145","volume":"14","author":[{"given":"Michael","family":"Karasick","sequence":"first","affiliation":[{"name":"IBM Research Div., Yorktown Heights, NY"}]},{"given":"David","family":"Strip","sequence":"additional","affiliation":[{"name":"Sandia National Labs, Albuquerque, NM"}]}],"member":"320","published-online":{"date-parts":[[1995,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 1985 International Conference on Parallel Processing (State College, Pa.), 411-417","author":"ATT~AH M. J.","year":"1985","unstructured":"ATT~AH , M. J. AND GOODRICH , M.T. 1985 . Efficient parallel solutions to geometric problems . In Proceedings of the 1985 International Conference on Parallel Processing (State College, Pa.), 411-417 . ATT~AH, M. J. AND GOODRICH, M.T. 1985. Efficient parallel solutions to geometric problems. In Proceedings of the 1985 International Conference on Parallel Processing (State College, Pa.), 411-417."},{"key":"e_1_2_1_2_1","first-page":"774","article-title":"Computational geometry on a systolic chip","author":"C~L~ZELLE B.","year":"1984","unstructured":"C~L~ZELLE , B. 1984 . Computational geometry on a systolic chip . IEEE Trans. Comput. ( Sept. ), 774 - 785 . C~L~ZELLE, B. 1984. Computational geometry on a systolic chip. IEEE Trans. Comput. (Sept.), 774-785.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/74334.74341"},{"key":"e_1_2_1_4_1","first-page":"127","volume-title":"Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures (Santa Fe, N.M.) ACM","author":"GOODRICH M.T.","year":"1989","unstructured":"GOODRICH , M.T. 1989 . Intersecting line segments in parallel with an output-sensitive number of processors . In Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures (Santa Fe, N.M.) ACM , New York , 127 - 136 . 10.1145\/72935.72950 GOODRICH, M.T. 1989. Intersecting line segments in parallel with an output-sensitive number of processors. In Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures (Santa Fe, N.M.) ACM, New York, 127-136. 10.1145\/72935.72950"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.16223"},{"key":"e_1_2_1_7_1","unstructured":"McGill Univ. Montreal Quebec Canada. (Also Rep. 89-976 Dept. of Computer Science Ceruell Univ. Ithaca N.Y.) McGill Univ. Montreal Quebec Canada. (Also Rep. 89-976 Dept. of Computer Science Ceruell Univ. Ithaca N.Y.)"},{"key":"e_1_2_1_8_1","first-page":"533","volume-title":"ICCD '84, (Oct.)","author":"KEDEM G.","year":"1984","unstructured":"KEDEM , G. , AND ELLIS , J. 1984. The raycasting machine . In ICCD '84, (Oct.) , 533 - 538 . KNUTH, D.E. 1984 . The TEXbook. Addison-Wesley , New York. KEDEM, G., AND ELLIS, J. 1984. The raycasting machine. In ICCD '84, (Oct.), 533-538. KNUTH, D.E. 1984. The TEXbook. Addison-Wesley, New York."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/15886.15904"},{"key":"e_1_2_1_10_1","first-page":"10","article-title":"A parallel processing technique for set operations using three-dimensional solid modelling","volume":"30","author":"NAK MA, Y","year":"1989","unstructured":"NAK aSH~ MA, Y ., Nl IM g, H., SH m^~~ta, IC , AND HAGIW Ar~ , H. 1989 . A parallel processing technique for set operations using three-dimensional solid modelling . Trans. Inf. Proc. Soc. Japan 30 , 10 (Oct.), 1298-1308. (Translated from the Japanese.) NAKaSH~MA, Y., NlIMg, H., SHm^~~ta, IC, AND HAGIWAr~, H. 1989. A parallel processing technique for set operations using three-dimensional solid modelling. Trans. Inf. Proc. Soc. Japan 30, 10 (Oct.), 1298-1308. (Translated from the Japanese.)","journal-title":"Trans. Inf. Proc. Soc. Japan"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356833"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1109\/MCG.1982.1674149","article-title":"Solid modeling: A historical summary and contemporary assessment","author":"REQUICHA A.","year":"1982","unstructured":"REQUICHA , A. , ANI ) VOEL(' KER , H. 1982 . Solid modeling: A historical summary and contemporary assessment . IEEE Comput. Graph. Appl. (Mar.) , 9 - 24 . REQUICHA, A., ANI) VOEL('KER, H. 1982. Solid modeling: A historical summary and contemporary assessment. IEEE Comput. Graph. Appl. (Mar.), 9-24.","journal-title":"IEEE Comput. Graph. Appl. (Mar.)"},{"key":"e_1_2_1_16_1","volume-title":"Proc. IEEE (Jan.), 30-44","author":"REQUICHA A., .","year":"1985","unstructured":"REQUICHA , A., . ~N 1) VOEL CKER , H. 1985 . Boolean operations in solid modeling: Boundary evaluation and merging algorithms . Proc. IEEE (Jan.), 30-44 . REQUICHA, A., .~N1) VOELCKER, H. 1985. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proc. IEEE (Jan.), 30-44."},{"key":"e_1_2_1_17_1","volume-title":"SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering","author":"ROSSIGNAC J.","year":"1990","unstructured":"ROSSIGNAC , J. , AND O'CONNOR , M. 1990 . SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering , M. J. Wozny, J. U. Turner, and K. Preiss, Eds., Elsevier Science , New York , 145 180. ROSSIGNAC, J., AND O'CONNOR, M. 1990. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering, M. J. Wozny, J. U. Turner, and K. Preiss, Eds., Elsevier Science, New York, 145 180."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.490"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"STRIP D. R. AND KARASICK M.S. 1992. Solid modeling on a massively parallel processor. Int. J. $upercomputer Appl. To be published. STRIP D. R. AND KARASICK M.S. 1992. Solid modeling on a massively parallel processor. Int. J. $upercomputer Appl. To be published.","DOI":"10.1177\/109434209200600205"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/200972.200976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T18:39:42Z","timestamp":1672339182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/200972.200976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["10.1145\/200972.200976"],"URL":"http:\/\/dx.doi.org\/10.1145\/200972.200976","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,1]]},"assertion":[{"value":"1995-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}