Convex Hulls are essential for a Collision-Detection system. Without Convex-Hulls, a game engine would not be able to detect collision among convex objects. Unfortunately, computing Convex-Hulls is complicated and time-consuming. Luckily for us, Joseph O'Rourke wrote a fantastic book called Computational Geometry in C. In it, he provides an algorithm, "Incremental Algorithm," which computes the Convex-Hull's vertices of a 3D mesh. However, not only does he provide a detailed explanation of the algorithm, but he also provides the complete implementation of the algorithm in C.

I modified the algorithm a tiny bit so that it works in C++ and with floating-point numbers. I also made the algorithm more user-friendly. I implemented a simple class which imports mesh data from Blender. So, instead of manually inputting mesh data, you simply run a script which imports the data for you. This process makes it easier for you to create any 3D model and obtain its convex hull vertices.

So let's go through a quick tutorial that I made for you:

Step 1.

Download the algorithm from my GitHub.

Step 2.

Open the Xcode project and open up the following file: "blenderFile.ch". The project will read mesh data from this file and use it as the input data for the algorithm.

Step 3.

Locate Blender in your Application folder and Right-click on the icon. If you have no idea what Blender is or how to open it, I suggest you read this article.

Click on Show Package Content

Next, click on the Contents folder and then click on MacOS. Finally, Click on Blender.

This action should fire up Blender 3D along with the Terminal.

Blender 3D normally starts up with:

The Default view as active
A Cube model in the center of the application

Step 4.

The Default view is perfect when you want to create a model. Since you want to develop a script, you need to switch to the Scripting view as shown below.

The Scripting View should now look as shown below.

Step 5.

Locate the lower bottom section of the application and click on New. This action should bring up a scripting page.

Step 6.

The Blender-Python script below retrieves attributes data from a mesh such as its vertices.

import bpy

#class for Model. This contains all the attributes of the model
class Model:
    def __init__(self):
        self.prehullvertices=[]


def main():

    #1. create a Model object
    model=Model()

    #2. Search for all objects in the  scene
    for models in bpy.context.scene.objects:

        #3. check if the object is a 3D mesh
        if(models.type=="MESH"):

        #4.get the individual vertices to compute convex hull
            for prehullvertices in bpy.context.scene.objects[models.name].data.vertices:

                #get the coordinate
                prehullvertex=prehullvertices.co               

                model.prehullvertices.append(prehullvertex)


            print("<?xml version=\"1.0\" encoding=\"utf-8\"?>")
            print("<Model xmlns=\"\" version=\"0.0.1\">")

            print("<asset>")
            print("<meshes>")
            print("<mesh>")
            print("<prehullvertices>",end="")

            for i in range(0,len(model.prehullvertices)):

                print("%f %f %f "%tuple(model.prehullvertices[i]),end="")   

            print("</prehullvertices>")
            print("</mesh>")
            print("</meshes>")
            print("</asset>")

            print("</Model>")

if __name__ == '__main__':
    main()

Copy and paste it into the scripting page as shown below:

Step 7.

If you click on Run Script, the 3D model's vertices should show up in your terminal.

Step 8.

Copy the data shown in the terminal and paste it into the "blenderFile.ch". (Make sure to delete any previous data in the file).

Step 9.

Now, run the Xcode project. The output log window shows the vertices of the computed Convex-Hull.

This is the cool part about the project. You can simply create a 3D model in Blender, run the Blender-Python script, copy the data found in the terminal, paste it in the "blenderFile.ch", run the Xcode project and get the Convex-Hull vertices. You do not need to input the data manually.

I hope it helps.

P.S. Make sure to follow these tips:

It is a good idea to delete the data in the terminal before you run the script. Use "Command+k" (mac) to delete the data in the terminal.
Make sure to remove any previous data in the "blenderFile.ch" before providing new data.

Update

If you get the following error when you run the Xcode project:

Follow the following steps:

On the toolbar of Xcode, click on "Product":

Then click on "Scheme"->"Edit Scheme":

In the "Working Directory" section, click the checkbox "Use custom working directory" and navigate to the folder the main.c file is located. The main.c file is in the ComputingConvexHull folder.

That should fix the problem.

Computing the Convex Hull of a 3D mesh