“Interactive boolean operations on surfel-bounded solids” by Adams and Dutré

In this paper we present an algorithm to perform interactive boolean operations on free-form solids bounded by surfels. We introduce a fast inside-outside test to check whether surfels lie within the bounds of another surfel-bounded solid. This enables us to add, subtract and intersect complex solids at interactive rates. Our algorithm is fast both in displaying and constructing the new geometry resulting from the boolean operation.We present a resampling operator to solve problems resulting from sharp edges in the resulting solid. The operator resamples the surfels intersecting with the surface of the other solid. This enables us to represent the sharp edges with great detail.We believe our algorithm to be an ideal tool for interactive editing of free-form solids.

1. ADAMS, B., AND DUTRÉ, P. 2003. A smoothing operator for boolean operations on surfel-bounded solids. Tech. rep., April.Google Scholar
2. ALEXA, M., BEHR, J., COHEN-OR, D., FLEISHMAN, S., LEVIN, D., AND SILVA, C. T. 2001. Point set surfaces. IEEE Visualization 2001 (October), 21–28. Google ScholarDigital Library
3. BOTSCH, M., WIRATANAYA, A., AND KOBBELT, L. 2002. Efficient high quality rendering of point sampled geometry. In Proceedings of the 13th workshop on Rendering, Eurographics Association, 53–64. Google Scholar
4. CHEN, B., AND NGUYEN, M. X. 2001. Pop: a hybrid point and polygon rendering system for large data. In IEEE Visualization 2001, 45–52. Google ScholarDigital Library
5. COCONU, L., AND HEGE, H.-C. 2002. Hardware-accelerated point-based rendering of complex scenes. In Proceedings of the 13th workshop on Rendering, Eurographics Association, 43–52. Google Scholar
6. COHEN, J. D., ALIAGA, D. G., AND ZHANG, W. 2001. Hybrid simplification: combining multi-resolution polygon and point rendering. In IEEE Visualization 2001, 37–44. Google ScholarDigital Library
7. FOLEY, J. D., VAN DAM, A., FEINER, S. K., AND HUGHES, J. F. 1996. Computer graphics (2nd ed. in C): principles and practice. Addison-Wesley Longman Publishing Co., Inc. Google Scholar
8. GOLDFEATHER, J., HULTQUIST, J. P. M., AND FUCHS, H. 1986. Fast constructive-solid geometry display in the pixel-powers graphics system. In Computer Graphics (Proceedings of SIGGRAPH 86), vol. 20, 107–116. Google Scholar
9. GOLDFEATHER, J., MOLNAR, S., TURK, G., AND FUCHS, H. 1989. Near real-time csg rendering using tree normalization and geometric pruning. IEEE Computer Graphics & Applications 9, 3 (May), 20–28. Google ScholarDigital Library
10. GOTTSCHALK, S. 1996. Seperating axis theorem. Tech. Rep. TR96-024, Dept. of Computer Science, UNC Chapel Hill.Google Scholar
11. GREENSPAN, M., GODIN, G., AND TALBOT, J. 2000. Acceleration of binning nearest neighbor methods. In Proceedings of Vision Interface 2000, 337–344.Google Scholar
12. GROSSMAN, J. P., AND DALLY, W. J. 1998. Point sample rendering. In Eurographics Rendering Workshop 1998, 181–192.Google ScholarCross Ref
13. HOFFMANN, C. M. 1989. Geometric and solid modeling: an introduction. Morgan Kaufmann Publishers Inc. Google Scholar
14. KALAIAH, A., AND VARSHNEY, A. 2001. Differential point rendering. In Rendering Techniques 2001: 12th Eurographics Workshop on Rendering, 139–150. Google ScholarDigital Library
15. KRISTJANSSON, D., BIERMANN, H., AND ZORIN, D. 2001. Approximate boolean operations on free-form solids. In Proceedings of ACM SIGGRAPH 2001, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, 185–194. ISBN 1-58113-292-1. Google Scholar
16. LEVOY, M., AND WHITTED, T. 1985. The use of points as a display primitive. Tech. Rep. TR85-022, January.Google Scholar
17. MUSETH, K., BREEN, D. E., WHITAKER, R. T., AND BARR, A. H. 2002. Level set surface editing operators. ACM Transactions on Graphics 21, 3 (July), 330–338. Google ScholarDigital Library
18. PAULY, M., AND GROSS, M. 2001. Spectral processing of point-sampled geometry. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 379–386. Google Scholar
19. PAULY, M., KOBBELT, L., AND GROSS, M. 2002. Multiresolution modeling of point-sampled geometry. Tech. rep., September.Google Scholar
20. PFISTER, H., ZWICKER, M., VAN BAAR, J., AND GROSS, M. 2000. Surfels: Surface elements as rendering primitives. In Proceedings of ACM SIGGRAPH 2000, ACM Press / ACM SIGGRAPH / Addison Wesley Longman, Computer Graphics Proceedings, Annual Conference Series, 335–342. ISBN 1-58113-208-5. Google ScholarDigital Library
21. RAPPOPORT, A., AND SPITZ, S. 1997. Interactive boolean operations for conceptual design of 3-d solids. In Proceedings of SIGGRAPH 97, Computer Graphics Proceedings, Annual Conference Series, 269–278. Google Scholar
22. REN, L., PFISTER, H., AND ZWICKER, M. 2002. Object space ewa surface splatting: A hardware accelerated approach to high quality point rendering. Computer Graphics Forum 21, 3, 461–470. ISSN 1067-7055.Google ScholarCross Ref
23. RUSINKIEWICZ, S., AND LEVOY, M. 2000. Qsplat: A multiresolution point rendering system for large meshes. In Proceedings of ACM SIGGRAPH 2000, ACM Press / ACM SIGGRAPH / Addison Wesley Longman, Computer Graphics Proceedings, Annual Conference Series, 343–352. ISBN 1-58113-208-5. Google ScholarDigital Library
24. SAMET, H. 1990. The design and analysis of spatial data structures. Addison-Wesley Longman Publishing Co., Inc. Google Scholar
25. ZWICKER, M., PFISTER, H., VAN BAAR, J., AND GROSS, M. 2001. Surface splatting. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 371–378. Google Scholar
26. ZWICKER, M., PAULY, M., KNOLL, O., AND GROSS, M. 2002. Pointshop 3d: An interactive system for point-based surface editing. ACM Transactions on Graphics 21, 3 (July), 322–329. ISSN 0730-0301 (Proceedings of ACM SIGGRAPH 2002). Google ScholarDigital Library