The aim of this work is to create a library for Boolean operations on 3D polygonal meshes. Resulting library has to support open models, its memory requirements shouldn't exceed those of existing solutions and it should, ideally, support multiple models. Most of the existing solutions are vulnerable to arithmetic inaccuracies, or do not support open meshes. The solution is based on Adaptive Mesh Booleans method which treats input models as adaptive surfaces. This method assumes that input models can be arbitrarily refined and no individual polygon is particularly important. Instead of computing exact polygon intersections, the input meshes are refined in intersection regions, intersecting polygons are discarded and created holes are closed. Advantages of this approach are robustness against numerical errors, support for open meshes, possibility to trade accuracy for computation time and ability to solve cases like co-planar and near-coincident regions. The resulting library offers three Boolean operations: union, difference and intersection.

This project is about finding ways to improve performance of a Computer-Aided-Design (CAD) application running in the web browser. With the new Web API WebGPU, it is now possible to use the GPU to accelerate calculations for CAD applications in the web. In this project, we tried to find if using the GPU could yield significant performance improvements and if they are worth implementing. Typical tasks for a CAD application are split and union, used for finding intersections and combining shapes in geometry, which we parallelized during this project. Our final implementation utilizes lazy evaluation and the HistoPyramid data structure, to compete with a state-of-the-art line-sweep based algorithm called Polygon Clipping. Although the Polygon Clipping intersection is still faster than our implementations in most cases, we found that WebGPU can still give significant performance boosts.

This work deals with an efficient and robust technique of performing Boolean operations on polygonal models. Full robustness is achieved within an internal representation based on planes and BSP (binary space partitioning) trees, in which operations can be carried out exactly in mere fixed precision arithmetic. Necessary conversions from the usual representation to the inner one and back, including their consequences are analyzed in detail. The performance of the method is optimized by a localization scheme in the form of an adaptive octree. The resulting implementation RazeCSG is experimentally compared with implementations used in practice Carve and Maya, which are not fully robust. For large models, RazeCSG shows only twice lower performance in the worst case than Carve, and is at least 130 times faster than Maya.

No description available.

This thesis deals with general polygon boolean operation algorithms. Boolean operations are e.g. intersection, union or difference. A general polygon can be e.g. a selfinterecting polygon with inner hole. Clipping of polygons against a rectangular window is probably the most familiar boolean operation on polygons. At first, basic definitions are listed. Then the principles of a selected set of boolean operation algorithms are reviewed. Finally, a complex comparison of the algorithms is undertaken. Performance as well as the ability to handle degenerate cases are tested. The output of this thesis is an overall evaluation of algorithm properties and a dynamic library that contains the implementation of all of the tested algorithms.

Historically 3D game environments have almost always been immutable. Mutable environments are a technical challenge that will affect performance. For games of the future to continue approaching realism, mutable environments are an essential step. Popularized by the game title Minecraft (2009), the use of voxel engines in games has become increasingly common. However, by the nature of the discrete position of voxels, the method is limited in representing arbitrary polyhedral shapes like angled slopes. It also prohibits smooth mutations including proper movement and rotation of objects within the voxelization. This is generally mitigable with more voxels. However, this paper proposes a more precise solution to the problem. A tetrahedral mesh engine (tetra engine). By altering tetrahedral topology, vertex positions, and material of individual tetrahedrons, tetras are intended to solve the issue of arbitrary polyhedral shapes for voxels. Additionally, the tetrahedral mesh shows other promises such as providing a robust collision detection method and as an acceleration structure for e.g. raycasting. The research question can be summarized as investigating the feasibility of a tetra engine as a mutable game environment. 3 sub-research questions are given: The first regarding performance, the second regarding robustness, and the third different types mutations. The research questions are addressed along with a proof of concept (POC). The POC intends to investigate a proposal for the most efficient robust solution possible for the most basic mutation type known as edits. Because of time constraints, it does not cover all parts of the research questions but works as a bottom-up approach to understand what is required to realize a full-fledged tetra engine. Thus, a large part of the research question is answered theoretically both hypothetically with grounds from the POC and through previous work. The result shows a much more critical robustness consideration than expected and suggests relying on slower but more robust algorithms that are known to work. In conclusion, nothing suggests that a scalable future-proof tetra engine is impossible, but the algorithms required are much less efficient than those for voxels and robustness is an issue to overcome. However, numerous hypothetical advantages particularly regarding deformation and fluid simulation are still recognized and it is not obvious that future mutable environments would not benefit from a tetra engine rather than voxels. / Historiskt sätt har 3D-datorspelmiljöer nästan uteslutande varit oföränderliga. Det finns goda anledningar till detta. Föränderliga miljöer är en teknisk utmaning som påverkar speleffektiviteten. Om man däremot vill fortsätta utveckla mer realistiska datorspel är föränderliga spelmiljöer ett naturligt steg. Spelet Minecraft (2009) populariserade användandet av voxlar i datorspel vars material kan ändras för att förändra miljön. Sedan dess har voxlar i datorspel blivit mer och mer populära. Dock, på grund av voxlars diskreta positioner har de begränsningar i dess förmåga att representera godtyckliga polyedriska former så som arbiträrt vinklade plan. Detta omöjliggör även mjuka rörelser inklusive rörelse och rotering inom voxeliseringen. Det här problemet kan generellt dämpas med hjälp av mindre och fler voxlar. Men, för att lösa problemet ordentligt föreslår den här rapporten en annan lösning, nämligen en tetrahedrisk-mesh-motor (tetramotor). Genom att ändra tetraedrisk topologi, hörn positioner, samt material av individuella tetraedrar ska tetrorna kunna forma arbiträra polyedriska former och lösa problemet med voxlar. Utöver detta visar en tetraedrisk mesh andra intressanta möjligheter likt en metod för robust kollisions hantering och som en accelereringsstruktur för till exempel ray-casting. Forskningsfrågan kan sammanfattas som att utforska tillämpbarheten av en tetramotor för föränderliga datorspelsmiljöer. Tre underfrågor ges: Den första handlar om beräkningseffektivitet, den andra angående robusthet och den tredje oliky typer av mutationer. Forskningsfrågorna angrips med hjälp av en proof of concept lösning (POC). POC:en är menad att utforska ett förslag på en effektiv och robust metod för direkta förändringar. På grund av tidsbegränsningar så täcker inte POC:en alla delar av frågeställningarna men är menad som en botten upp lösning för att inse och förstå kraven för en komplett tetramotor. På grund av detta är en stor del av forskningsfrågorna svarade teoretiskt, både hypotetiskt baserat på insikterna från POC:en och med grund från tidigare forskning. Resultatet visar en mycket mer kritisk hänsyn till robusthet än förväntat och föreslår att man använder sig av långsammare men fungerande existerande lösningar. Slutsatsen är att inget tyder på att en skalbar framtidssäker tetramotor är en omöjlighet, men att algoritmerna är mycket långsammare än de som krävs för voxlar. Däremot finns potentieally fördelar med en tetra motor, främst med hänsyn till deformering och flödessimulering. Det är därför inte självklart att framtida muterbara spelmijöer inte skulle ha fördelar av en tetramotor istället för voxlar.