Category Computational Geometry

Octree + Ray Collision

Nowadays in applications that work with 3D graphical environments require monitoring the collision between meshes with lots of triangles, so that the computational cost of checking all triangles of both meshes would be too high.

To solve this problem, it’s posible to divide the triangles of the mesh in areas, so we will have a smaller amount of triangles to check for each sector. This creates a data structure in a tree, in which the father wraps to subsectors children. This distribution of data also can be applied in both 2D (Quadtree) and 3D (Octree).

Read More

QuickHull 3D

At the Computational Geometry course I have implemented the Quickhull algorithm for its application in 3D, following the paper “Barber, C. B., Dobkin, D. P., & Huhdanpaa, H. T. (1996). The Quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software, 22(4), 469—483”. And following the example of this java applet developed by UNSW School of Computer Science and Engineering.

Read More