{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:06:36Z","timestamp":1777716396504,"version":"3.51.4"},"reference-count":21,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[1989,2,1]],"date-time":"1989-02-01T00:00:00Z","timestamp":602294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1989,2]]},"abstract":"<jats:p>Testing for the existence of intersections is an important part of algorithms for interference detection, collision detection, and the like. We describe three techniques that can be used to implement an efficient intersection detection routine when entities are described constructively, that is, as set combina tions of primitive entities. All three techniques are described in a domain where constructive solid geometry is the princi pal entity description used, although their use in boundary representation schemes is also discussed. The first technique, called S-bounds, is a method of reasoning about where inter sections may be taking place; in practice it is fast and often sufficient. S-bounds can also be used as a general constraint manipulation method over Boolean algebras. The second technique is based on spatial subdivision, and is used mainly to improve the speed of the intersection test. The third tech nique is employed only on regions of space left by the first two techniques; it is a specialization of the \"classical\" tech nique of generate and test. The combination of these tech niques has been implemented as an intersection detection routine which shows a speedup over the \"classical\" algorithm of about two orders of magnitude.<\/jats:p>","DOI":"10.1177\/027836498900800101","type":"journal-article","created":{"date-parts":[[2007,3,11]],"date-time":"2007-03-11T03:05:13Z","timestamp":1173582313000},"page":"3-25","source":"Crossref","is-referenced-by-count":48,"title":["Efficient Intersection Tests for Objects Defined Constructively"],"prefix":"10.1177","volume":"8","author":[{"given":"Stephen","family":"Cameron","sequence":"first","affiliation":[{"name":"Robotics Group, Department of Engineering Science University of Oxford, Oxford OX1 3PJ, England U.K."}]}],"member":"179","published-online":{"date-parts":[[1989,2,1]]},"reference":[{"key":"atypb1","unstructured":"Ambler, A.P., Cameron, S.A., and Comer, D.F. 1986 (Sept. 1-5). Augmenting the RAPT robot language. In Languages for sensor-based control in robotics, eds. U. Rembold and K. Hormann , pp. 305-316. New York: Springer-Verlag . Ref. F29 (1987), Castelvecchio Pascoli. Also as University of Edinburgh DAI Research Paper 330."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(75)90007-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1982.1674167"},{"key":"atypb4","volume-title":"Modelling solids in motion. Ph.D. thesis, Department of Artificial Intelligence","author":"Cameron, S.A.","year":"1984"},{"key":"atypb5","volume-title":"IEEE Int. Conf. Robotics and Automation","author":"Cameron, S.A."},{"key":"atypb6","volume-title":"Efficient intersection tests for objects defined constructively","author":"Cameron, S.A.","year":"1987"},{"key":"atypb7","volume-title":"A geometric database for the Oxford autonomous guide vehicle","author":"Cameron, S.A.","year":"1988"},{"key":"atypb8","volume-title":"IEEE Int. Conf. Robotics and Automation","author":"Cameron, S.A."},{"key":"atypb9","volume-title":"The use of bounds in geometric processing","author":"Cameron, S.A."},{"issue":"4","key":"atypb10","volume":"12","author":"Requicha, A.A.G.","year":"1980","journal-title":"Computing Surveys"},{"issue":"2","key":"atypb11","volume":"2","author":"Requicha, A.A.G.","year":"1982","journal-title":"IEEE Computer Graphics and Applications"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1983.263271"},{"key":"atypb13","author":"Rossignac, J.R.","year":"1986","journal-title":"ACM Trans. on Graphics"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/358826.358836"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356930"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675470"},{"key":"atypb17","author":"Tilove, R.B.","year":"1981","journal-title":"Applied Science"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/358105.358195"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1049\/cae.1986.0005"},{"key":"atypb20","first-page":"335","volume":"80","author":"Woodwark, J.R.","year":"1980","journal-title":"Computer Graphics"},{"issue":"2","key":"atypb21","volume":"14","author":"Woodwark, J.R.","year":"1984","journal-title":"CAD J."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836498900800101","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836498900800101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:18:14Z","timestamp":1777457894000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836498900800101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,2]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,2]]}},"alternative-id":["10.1177\/027836498900800101"],"URL":"https:\/\/doi.org\/10.1177\/027836498900800101","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,2]]}}}