No Access

PARALLEL SOLID MODELING USING BSP DATAFLOW

GIORGIO SCORZELLI

PLM Lab, Dipartimento Informatica e Automazione, Università Roma Tre, Via della Vasca navale, 79, Rome, I-00146, Italy

Search for more papers by this author

ALBERTO PAOLUZZI

PLM Lab, Dipartimento Informatica e Automazione, Università Roma Tre, Via della Vasca navale, 79, Rome, I-00146, Italy

Search for more papers by this author

, and

VALERIO PASCUCCI

Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Box 808, L-560, Livermore, CA 94551, USA

Search for more papers by this author

https://doi.org/10.1142/S0218195908002714Cited by:6 (Source: Crossref)

Abstract

We introduce a parallel approach to geometric modeling of complex objects and scenes, combining a dataflow streaming of BSP trees with a partition of the object space into independent portions, to be evaluated in parallel with minimal interprocess communication. Binary Space Partition (BSP) is a space index used in graphics for hidden-surface removal and animation. We use BSP trees with fuzzy leaves as a progressive representation of solid meshes. Our approach is implemented as a dataflow with processes that progress concurrently, where each refinement of the input to a process is mapped instantly to a refinement of the output, so that the result is also a stream of progressive refinements. This framework allows for progressive generation of complex geometric parts and large-scale assemblies. We have adapted several graphics techniques, including BSP, boundary polygons, CSG, splines and subdivision methods, to fit into our dataflow graph, where four types of processes produce, transform, combineor consume mesh cells. This approach is scalable over different kinds of HPC hardware and different number of computing nodes, by way of the decomposition of the object space and of the distribution of computational processes. Compiling a generative geometric expression into a dataflow graph is well suited to SMP machines, whereas a space decomposition into independent portions fits well with computing clusters and grids.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

B. Adams and P. Dutrø, ACM Trans. Graph. (TOG) 22(3), 651 (2003), DOI: 10.1145/882262.882320. Crossref, Web of Science, Google Scholar
Arvind and D. E. Culler, Ann. Rev. Comput. Sci. 1, 225 (1986), DOI: 10.1146/annurev.cs.01.060186.001301. Crossref, Web of Science, Google Scholar
C. L. Bajaj and T. K. Dey, SIAM J. Comput. 21(2), 339 (1992), DOI: 10.1137/0221025. Crossref, Web of Science, Google Scholar
C. L. Bajaj and V. Pascucci, Splitting a complex of convex polytopes in any dimension, SCG '96: Proc. Twelfth Ann. Symp. Computational Geometry (ACM Press, 1996) pp. 88–97. Google Scholar
R. H. Bartels , J. C. Beatty and B. A. Barsky (eds.) , An Introduction to Splines for Use in Computer Graphics and Geometric Modeling ( Morgan Kaufmann , San Mateo, CA , 1987 ) . Google Scholar
F. Bernardiniet al., A product operator on cell complexes, Proc. 2nd ACM/IEEE Symp. Solid Modeling and Applications, eds. J. Rossignac, J. Turner and G. Allen (ACM Press, 1993) pp. 43–52. Google Scholar
F. Bernardini, Comput. Aided Des. 23(1), 51 (1991). Web of Science, Google Scholar
H. Biermann, D. Kristjansson and D. Zorin, Approximate boolean operations on free-form solids, SIGGRAPH '01: Proc. 28th Ann. Conf. Computer Graphics and Interactive Techniques (ACM Press, 2001) pp. 185–194. Google Scholar
D. Brodsky and B. Watson, Graphics Interface 221 (2000). Google Scholar
P. Brunet and I. Navazo, ACM Trans. Graph. 9(2), 170 (1990), DOI: 10.1145/78956.78959. Crossref, Web of Science, Google Scholar
H. Chen and S. Fang, Proc. Fifth ACM Symp. Solid Modeling and Applications (ACM Press, 1999) pp. 318–319. Google Scholar
A. Edalat and A. Lieutier, Foundation of a computable solid modeling, SMA '99: Proc. Fifth ACM Symp. Solid Modeling and Applications (ACM Press, 1999) pp. 278–284. Google Scholar
G. Vanĕcek Jr., Brep-index: A multidimensional space partitioning tree, SMA '91: Proc. First ACM Symp. Solid Modeling Foundations and CAD/CAM Applications (ACM Press, New York, NY, USA, 1991) pp. 35–44. Google Scholar
J. Hable and J. Rossignac, ACM Trans. Graph. 24(3), 1024 (2005), DOI: 10.1145/1073204.1073306. Crossref, Web of Science, Google Scholar
C. M. Hoffmann and N. F. Stewart, Graphical Models (2004). Google Scholar
W. M. Johnston, J. R. Paul Hanna and R. J. Millar, ACM Comput. Surv. 36(1), 1 (2004), DOI: 10.1145/1013208.1013209. Crossref, Web of Science, Google Scholar
C. Jorgensen et al. , Development and performance of a PVM based parallel geometric modeler for MEMS , Proc. 2002 Int. Conf. Modeling and Simulation of Microsystems (Nanotech 2002) ( 2002 ) . Google Scholar
M. Karasick and D. Strip, ACM Trans. Graph. 14(1), 21 (1995), DOI: 10.1145/200972.200976. Crossref, Web of Science, Google Scholar
D. Liao and S. Fang, Fast volumetric csg modeling using standard graphics system, Proc. Seventh ACM Symp. Solid Modeling and Applications (ACM Press, 2002) pp. 204–211. Google Scholar
W. F. McColl , BSP programming , Proc. DIMACS Workshop on Specification of Parallel Algorithms , eds. G. Blellocj and et. al ( Americal Mathetical Society , 1994 ) . Google Scholar
B. F. Naylor, Comput. Aided Des. 22(4), 250 (1990), DOI: 10.1016/0010-4485(90)90055-H. Crossref, Web of Science, Google Scholar
B. F. Naylor, J. Amanatides and W. Thibault, Comput. Graph. 24(4), 115 (1990). Crossref, Web of Science, Google Scholar
Z. Panet al., A new bsp tree framework incorporating dynamic lod models, VRST '00: Proc. ACM Symp. Virtual Reality Software and Technology (ACM Press, 2000) pp. 134–141. Google Scholar
A. Paoluzzi , Geometric Programming for Computer Aided Design ( John Wiley & Sons , Chichester, UK , 2003 ) . Crossref, Google Scholar
A. Paoluzzi, V. Pascucci and G. Scorzelli, Progressive dimension-independent boolean operations, Proc. 9-th ACM Symp. Solid Modeling and Applications, eds. G. Elber, N. Patrikalakis and P. Brunet (2004) pp. 203–212. Google Scholar
J. Peters , Efficient one-sided linearization of spline geometry , Mathematics of Surfaces X , Lecture Notes in Computer Science , eds. R. R. Martin and M. Wilson ( Springer , 2003 ) . Google Scholar
A. Rappoport and S. Spitz, Interactive boolean operations for conceptual design of 3-d solids, SIGGRAPH '97: Proc. 24th Ann. Conf. Computer Graphics and Interactive Techniques (ACM Press/Addison-Wesley Publishing Co., 1997) pp. 269–278. Google Scholar
V. Shapiro , Handbook of Computer Aided Design , eds. G. Farin , J. Hoschek and M. S. Kim ( Elsevier Science Publishers , 2001 ) . Google Scholar
K. Sugihara and M. Iri, Int. J. Comput. Geom. Appl. 4(2), 179 (1994), DOI: 10.1142/S0218195994000124. Link, Web of Science, Google Scholar
L. Valliant , Handbook of Theoretical Computer Science , ed. J. Van Leeuwen ( Elsevier Science Publishers , 1990 ) . Google Scholar
T. Woo, IEEE Comput. Graph. Appl. 5(3), 19 (1985), DOI: 10.1109/MCG.1985.276337. Crossref, Web of Science, Google Scholar
G. M. Ziegler , Lectures on Polytopes , Number 152 in Graduate texts in mathematics ( Springer-Verlag , New York, NY , 1995 ) . Crossref, Google Scholar