Point containment algorithms for constructive solid geometry with unbounded primitives

Paul K. Romano; Patrick A. Myers; Seth R. Johnson; Aljaz̆ Kols̆ek; Patrick C. Shriwise

doi:10.1016/j.cad.2024.103803

Point containment algorithms for constructive solid geometry with unbounded primitives

Paul K. Romano, Patrick A. Myers, Seth R. Johnson, Aljaz̆ Kols̆ek, Patrick C. Shriwise

Scalable Engineering Applications

Research output: Contribution to journal › Article › peer-review

Abstract

We present several algorithms for evaluating point containment in constructive solid geometry (CSG) trees with unbounded primitives. Three algorithms are presented based on postfix, prefix, and infix notations of the CSG binary expression tree. We show that prefix and infix notations enable short-circuiting logic, which reduces the number of primitives that must be checked during point containment. To evaluate the performance of the algorithms, each algorithm was implemented in the OpenMC Monte Carlo particle transport code, which relies on CSG to represent solid bodies through which subatomic particles travel. Two sets of tests were carried out. First, the execution time to generate a rasterized image of a 2D slice of three CSG models of varying complexity was measured. Use of both prefix and infix notations offered significant speedup over the postfix notation that has traditionally been used in particle transport codes, with infix resulting in a 6× reduction in execution time relative to postfix for a model of a tokamak fusion device. We then measured the execution time of neutron transport simulations of the same three models using each of the algorithms. The results and performance improvements reveal the same trends as for the rasterization test, with a 5.52× overall speedup using the infix notation relative to the original postfix notation in OpenMC for the tokamak model.

Original language	English
Article number	103803
Journal	CAD Computer Aided Design
Volume	178
DOIs	https://doi.org/10.1016/j.cad.2024.103803
State	Published - Jan 2025

Funding

This work is supported by the U.S. Department of Energy Office of Fusion Energy Sciences under award number DE-SC0022033. We gratefully acknowledge the computing resources provided on Improv, a high-performance computing cluster operated by the Laboratory Computing Resource Center at Argonne National Laboratory. This work was carried out using an adaption of the E-lite model which was developed as a collaborative effort between: AMEC Co (International), CCFE (UK), ENEA Frascati (Italy), FDS Team of INEST (PRC), ITER Organization (France), QST (Japan), KIT (Germany), UNED (Spain), University of Wisconsin-Madison (USA), F4E (Europe). The views and opinions expressed herein do not necessarily relect those of the ITER Organization.

Funders	Funder number
FDS Team of INEST
University of Wisconsin-Madison
Agenzia nazionale per le nuove tecnologie, l'energia e lo sviluppo economico sostenibile
Instituto Tecnológico y de Energías Renovables
Karlsruhe Institute of Technology
Argonne National Laboratory
National Institutes for Quantum and Radiological Science and Technology
Culham Centre for Fusion Energy
AMEC Co
Universidad Nacional de Educación a Distancia
Laboratory Computing Resource Center
Fusion Energy Sciences	DE-SC0022033
Fusion Energy Sciences

Keywords

Constructive solid geometry
Monte Carlo
Particle transport
Point containment

Access to Document

10.1016/j.cad.2024.103803

Cite this

@article{513c1fab19024d7aa663a303cea7dc96,

title = "Point containment algorithms for constructive solid geometry with unbounded primitives",

abstract = "We present several algorithms for evaluating point containment in constructive solid geometry (CSG) trees with unbounded primitives. Three algorithms are presented based on postfix, prefix, and infix notations of the CSG binary expression tree. We show that prefix and infix notations enable short-circuiting logic, which reduces the number of primitives that must be checked during point containment. To evaluate the performance of the algorithms, each algorithm was implemented in the OpenMC Monte Carlo particle transport code, which relies on CSG to represent solid bodies through which subatomic particles travel. Two sets of tests were carried out. First, the execution time to generate a rasterized image of a 2D slice of three CSG models of varying complexity was measured. Use of both prefix and infix notations offered significant speedup over the postfix notation that has traditionally been used in particle transport codes, with infix resulting in a 6× reduction in execution time relative to postfix for a model of a tokamak fusion device. We then measured the execution time of neutron transport simulations of the same three models using each of the algorithms. The results and performance improvements reveal the same trends as for the rasterization test, with a 5.52× overall speedup using the infix notation relative to the original postfix notation in OpenMC for the tokamak model.",

keywords = "Constructive solid geometry, Monte Carlo, Particle transport, Point containment",

author = "Romano, {Paul K.} and Myers, {Patrick A.} and Johnson, {Seth R.} and Alja{\u z} Kol{\u s}ek and Shriwise, {Patrick C.}",

note = "Publisher Copyright: {\textcopyright} 2024",

year = "2025",

month = jan,

doi = "10.1016/j.cad.2024.103803",

language = "English",

volume = "178",

journal = "CAD Computer Aided Design",

issn = "0010-4485",

publisher = "Elsevier",

}

TY - JOUR

T1 - Point containment algorithms for constructive solid geometry with unbounded primitives

AU - Romano, Paul K.

AU - Myers, Patrick A.

AU - Johnson, Seth R.

AU - Kols̆ek, Aljaz̆

AU - Shriwise, Patrick C.

PY - 2025/1

Y1 - 2025/1

N2 - We present several algorithms for evaluating point containment in constructive solid geometry (CSG) trees with unbounded primitives. Three algorithms are presented based on postfix, prefix, and infix notations of the CSG binary expression tree. We show that prefix and infix notations enable short-circuiting logic, which reduces the number of primitives that must be checked during point containment. To evaluate the performance of the algorithms, each algorithm was implemented in the OpenMC Monte Carlo particle transport code, which relies on CSG to represent solid bodies through which subatomic particles travel. Two sets of tests were carried out. First, the execution time to generate a rasterized image of a 2D slice of three CSG models of varying complexity was measured. Use of both prefix and infix notations offered significant speedup over the postfix notation that has traditionally been used in particle transport codes, with infix resulting in a 6× reduction in execution time relative to postfix for a model of a tokamak fusion device. We then measured the execution time of neutron transport simulations of the same three models using each of the algorithms. The results and performance improvements reveal the same trends as for the rasterization test, with a 5.52× overall speedup using the infix notation relative to the original postfix notation in OpenMC for the tokamak model.

AB - We present several algorithms for evaluating point containment in constructive solid geometry (CSG) trees with unbounded primitives. Three algorithms are presented based on postfix, prefix, and infix notations of the CSG binary expression tree. We show that prefix and infix notations enable short-circuiting logic, which reduces the number of primitives that must be checked during point containment. To evaluate the performance of the algorithms, each algorithm was implemented in the OpenMC Monte Carlo particle transport code, which relies on CSG to represent solid bodies through which subatomic particles travel. Two sets of tests were carried out. First, the execution time to generate a rasterized image of a 2D slice of three CSG models of varying complexity was measured. Use of both prefix and infix notations offered significant speedup over the postfix notation that has traditionally been used in particle transport codes, with infix resulting in a 6× reduction in execution time relative to postfix for a model of a tokamak fusion device. We then measured the execution time of neutron transport simulations of the same three models using each of the algorithms. The results and performance improvements reveal the same trends as for the rasterization test, with a 5.52× overall speedup using the infix notation relative to the original postfix notation in OpenMC for the tokamak model.

KW - Constructive solid geometry

KW - Monte Carlo

KW - Particle transport

KW - Point containment

UR - http://www.scopus.com/inward/record.url?scp=85203636782&partnerID=8YFLogxK

U2 - 10.1016/j.cad.2024.103803

DO - 10.1016/j.cad.2024.103803

M3 - Article

AN - SCOPUS:85203636782

SN - 0010-4485

VL - 178

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

M1 - 103803

ER -

Point containment algorithms for constructive solid geometry with unbounded primitives

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this