Given any non-transparent 3D object, it is impossible to confidently discern the exact shape of the object by looking upon it from a stationary, single viewpoint. Due to all the possible configuration of faces that are hidden to the stationary viewpoint, a rotation around the object is most effective in confidently determining the object’s shape. My goal is to create a function that will return a video of the optimal rotation of any given 3D object to illustrate its shape. I chose this project because of my passion for 3D printing and design, as well as my interest in geometry.
How it Works:
How it Works:
The shape of any 3D object will become apparent to an onlooker if every surface on the shape comes into view in a reasonable transition during the video. My project is basically finding a path of the camera around the 3D object so that every face is seen at least once, and optimizing this path to make it the most easy for an onlooker to understand the shape. While this may seem simple, it is not as easy as it looks. The option of receiving any 3D object, even imported ones, opens up the possibility of running into exceptions and complications.
Finding surrounding faces of vertices:
Finding surrounding faces of vertices:
A vertex is always connected to at least three adjacent faces on a reasonable angle. By positioning the camera to be pointed at a vertex, we can guarantee that the adjacent faces will be visible.
Position the viewpoint to be pointed at the vertex of a 3D shape (a cube for simplicity) and observe the faces visible:
Graphics3D[Cube[],ViewPoint{1,1,1}]
Out[]=
With a more complex shape, the claim holds as adjacent faces are all visible:
Graphics3DIcosahedron[],ViewPoint0,0,-
5
50-10
5
Out[]=
Now we must find a function that tells us the adjacent faces of any and all vertices of a given 3D object (aka the faces that will be seen when positioning the camera above the vertex).
Setting the 3D object as a model to be worked with later:
Model=ExampleData[{"Geometry3D","SpaceShuttle"}]
Out[]=
Now I want to simplify the model and get its very basic shape, in order to avoid complications. The 3D object, as is, may contain holes or hollow points. Since my approach relies on interacting and accounting for every face of the 3D object, interior faces and concave surfaces may cause the camera to phase through walls or miss faces. To most efficiently simplify the model, I will find the convex hull of the object, or the smallest convex set that entirely contains the object. Think of this as putting the model into a deflated balloon and watching the balloon shrink to match the shape. Essentially, we are neutralizing exceptions and other dangerous examples that can break our algorithm and converting the complex 3D object into a much simpler one to work with.
Finding the convex hull of the object:
ModelRegion=ConvexHullMesh[MeshCoordinates[DiscretizeGraphics[Model]]]
Out[]=
I will now refer to the convex hull model as the ModelRegion. Working with the ModelRegion, I can find the total amount of vertices on the simplified object. This will help me know when to stop the functions that I will use later and better fits the functions to the unique model, avoiding redundant calculations.
Finding the total count of vertices that lie on the ModelRegion:
vertexCount=MeshCellCount[ModelRegion,0]
Out[]=
66
Now, we must find the faces immediately adjacent to any given vertex and most importantly have an easy way to read and use them later on. To accomplish this, we can tap into the 3D mesh region's automatic numbering system for both faces and vertices to achieve an easy way to identify and store face and vertexes. The finding of adjacent faces can be done with AdjacentMeshcells.
An example of finding the immediately adjacent faces for a vertex on a dodecahedron and a visualization to demonstrate the approach:
AdjacentMeshCells[Dodecahedron[],{0,11},2]HighlightMesh[Dodecahedron[],AdjacentMeshCells[Dodecahedron[],{0,11},2],MeshCellLabel->{0->"Index",2->"Index"}]
Out[]=
{{2,2},{2,3},{2,4}}
Out[]=
The AdjacentMeshCells returns the faces having been categorized by the MeshRegion identification system. Each identifier in the numbering system is represented as a list of 2 entities, being dimension and identification number. For example, a face on our ModelRegion might have the identifier {2,3}, meaning dimension 2 (2D face) and face 3 (the third face of the model), while a vertex on our model might have identifier {0,11}, meaning dimension 0 (a point) and vertex 11 (11th vertex on the model). By mapping the AdjacentMeshCells function over every vertex (kept track by going from 1 to vertexCount), we can find the neighboring faces for every vertex of the ModelRegion.
A function that finds the immediately adjacent faces for every single vertex of the ModelRegion:
(neighborFaces=(AdjacentMeshCells[ModelRegion,{0,#},2]&/@Range[vertexCount]))//Short
Out[]//Short=
{{{2,35},{2,36},{2,46},{2,47},{2,51},{2,52},{2,53},{2,68},{2,69}},64,{1}}
The output of the above function will find a list of sublists of entries. Each sublist corresponds to a vertex of the ModelRegion, increasing in canonical order (ex: the first sublist corresponds to vertex, the second sublist corresponds to the second vertex, etc). Each entry in the sublist corresponds to a face that consists of the vertex in question, formatted as {2, Identification number}. I can now work with this list to find the smallest group of vertices in which all the object's faces are covered.
Nested Function to find a covering set of vertices:
Nested Function to find a covering set of vertices:
A covering set of vertices is a series of vertices that, when taken together, accounts for every face on the 3D object at least once in their collection of immediately adjacent faces. I will aim to find the smallest covering set of vertices for the given 3D object, in order to find the optimal rotation in which every face of the object can be seen. I begin by finding the total list of all faces, all of which are unaccounted for initially.
Finding the total list of faces on the ModelRegion, formatted identical to the format of the entries from the adjacent faces of vertices function:
(FaceList=({2,#}&/@Range[MeshCellCount[ModelRegion,2]]))//Short
Out[]//Short=
{{2,1},{2,2},{2,3},{2,4},{2,5},109,{2,115},{2,116},{2,117},{2,118},{2,119}}
In order to find the covering set, I will have to utilize a nesting function. Let's call a suitable vertex any vertex whose immediately adjacent faces have all been yet unaccounted for. I will begin by finding all the suitable vertices on the ModelRegion, in order to get the smallest covering set of vertices. This can be achieved by finding if all the adjacent faces of a given vertex is contained inside the list of unaccounted-for faces.
Checking if all the adjacent faces of a given vertex (vertex 1 in this case) is contained inside the list of unaccounted-for faces (total list of faces on ModelRegion initially):
ContainsAll[FaceList,neighborFaces[[1]]]
Out[]=
True
This checks that every neighboring face of the given vertex is unaccounted for. If they are all contained, said vertex will be a suitable vertex, therefore we can account for all its adjacent faces and remove all neighbor faces to the vertex from the list of unaccounted-for faces. This is done by finding the complement of the list of unaccounted-for faces with the neighbor faces of the vertex. If adjacent faces is not all unaccounted for, it is not a suitable vertex, so we can return an unmodified list of unaccounted-for faces.
Removing the accounted for faces from list of unaccounted-for faces if Suitable Vertex, returning unmodified list if not:
Making this function a nesting function, it can build upon all previous entries, and after inputting the number of vertices, this function will return a list of faces that are not neighbors to suitable vertices.
Nesting function built on the function shown above:
However, I also need to find a way to store all the suitable vertices in a way to be easily accessible for future use. I was graced by luck because the unaccounted-for faces and the neighbor faces for a given vertex both follow the format of being a list {2, Identification number}. This means that I can store the vertexes directly in the list of unaccounted faces as non-list, single numbers, and they will be spared from the influence of the recursive formula. So, after making the modifications, I am left with a function that returns a list of numbers, each of which are an identification number for a suitable vertex, followed by several lists, each of which correspond to an unaccounted for face.
Defining the function to work recursively and find a list of suitable vertices followed by a list of unaccounted for faces:
Running the function an amount of times equal to the number of vertices on the ModelRegion:
Now that I have accounted for all neighboring faces of suitable vertices, I need to factor in the faces of all non-suitable vertices that account for all the remaining unaccounted-for faces. Lets call these Remaining Vertices.
This can be done through a nested function similar to the function shown above, except it will modify the list of unaccounted for faces as long as any entry from the list of neighboring faces of the given vertex also appears in the list of the remaining unaccounted-for faces, instead of all neighboring faces having to appear in the list of remaining unaccounted-for faces.
Using ContainsAny to find Remaining Vertices:
Similarly, the function will store the vertex identification numbers of Remaining Vertices as single numbers in the output list.
Defining the function to work recursively and find a list that is a collection of both suitable vertices and Remaining Vertices:
Running the function an amount of times equal to the number of vertices on the ModelRegion and sorting it into canonical order for organization:
Now that I have obtained the small covering set of vertices, I can begin to use this information to find the path of the camera to create the video.
Finding the camera path:
Finding the camera path:
Having obtained the covering set of vertices, I can find the coordinates of each vertex in the set.
Finding the coordinates for every vertex in the covering set of vertices:
While I can just use all these points to make the camera path, it will be highly redundant because I was working with the assumption that only immediately adjacent faces will be visible when pointing the camera at a given vertex, whereas this is not the case in practice and many other faces can be seen both at the vertex location and on the path as the camera moves towards the vertex location. Using the entire covering set of vertices to make a path will result in an unbalanced, dizzying and redundant video, which would be far from optimal. I can simplify the set of coordinates that I am working with through FindClusters.
Visualizing the clusters found from the CoveringVertexCoords:
I will reduce the covering set of vertices to only the necessary vertices by finding clusters of vertices close together, whose adjacent faces will likely all be seen by pointing the camera to the general region, and finding the mean coordinate of all the vertices.
Visualizing the points of the simplified position paths for the camera using the mean coordinates of 10 clusters:
I aimed to find an amount of clusters equal to one-fifth the total number of vertices in the covering set of vertices, since this would simplify the path to a reasonable degree while maintaining accuracy.
Finding the mean coordinate for each of the clusters of vertices from the covering set of vertices:
Visualization of the mean coordinate for each of the clusters of vertices from the covering set of vertices:
Just to make sure the video resulting from the camera moving to each of these points accurately illustrates the shape of the 3D object, I also will include two points from each of the three coordinate axes for the camera to path to. These points will be distanced equal to the farthest distance of any point on the ModelRegion from the center in the positive and negative direction of the origin on all three axes, in order to avoid unnecessary zooming in and out of the camera during the video and preserving video quality.
Finding the max distance of any point on the ModelRegion from the origin:
Finding the CameraPoints, the points that make up the path in which the camera will path on:
Visualization of the CameraPoints:
After determining the CameraPoints, the next step is to just make the camera path. This can be done with FindShortestTour, which will find the ordering of the points to make the shortest looping path connecting all the given points, with 1 corresponding to the first coordinate, 2 corresponding to the second coordinate, etc. Mapping the part function for CameraPoints over each entry in the resulting list of FindShortestTour in order will find the coordinates in order to make the optimal path for the camera to move on.
Finding the ordering of CameraPoints coordinates to make the optimal path for Camera to move on:
Taking this list of ordered coordinates, I can construct the camera path as a BSpline function to create a smooth video with minimal jerking.
Constructing the path curve for the camera to move along:
Visualizing the path curve:
I zoomed out the camera by 500% from the vertex coordinate in order to better see the object in its entirety and give my code more room for error to still work properly. I can now move the camera along this path curve, finding 101 points along the curve spaced out equally to take a snapshot. Each of these snapshots can be converted into the frames for a GIF video of the rotation around the object.
Capturing the 101 snapshots from the camera as it makes its way along the path:
Building the snapshots into a GIF:
Making the GIF video accessible:
Displaying the GIF after downloading:
Complete Code:
Complete Code:
Here is the complete, working code to find the optimal rotation about a 3D object to fulling illustrate its shape:
Final Output (examples):
Final Output (examples):
Organized display of the function applied on various 3D objects:
Conclusion:
Conclusion:
The output is a video that is a combination of 101 frames from the camera as it makes it way around the 3D object on the optimal rotational camera path. This project was quite challenging despite its simplistic prompt, and required me to cycle through numerous different approaches, each of which had its own problems. Throughout the process of the development of my project, I learned a few very valuable things. Firstly, it quickly became apparent to me the difficulties of visualizing the shapes of the countless possibilities for complex, inputted 3D objects. Secondly, I learned the importance of not being too married to an initial idea, since it will likely have its fair share of complications. Lastly, this experience has taught me the power of perspective when it comes to approaching daunting problems, as the task became much more doable when I stopped concerning myself with having a dynamically rotated object with a stationary camera to instead having a dynamically rotated camera with a stationary object.
Future Work
Future Work
I plan on extending this project to more complex situations where a rotation illustrating the shape of the object is not as intuitive by a human. One possibility that has captured my interest is exploring the possibilities of finding an optimal way to illustrate or represent a 4D object such as a tesseract or a 120Cell in 3D space by moving along a path in the 4th dimension in addition to the path in 3rd dimension. However, this project will be very complicated as it will be difficult to find a movement in the 4th dimension coupled with movement in the 3rd dimension to optimally illustrate the shape, so a project like this will likely be done by moving the camera in the third dimension along the object at fixed positions in the fourth dimension, resulting in a long video for even the relatively simplest of 4D objects. I believe this approach will be doable, however it might be a little difficult to interpret and very complicated to implement.
Credits
Credits
I would like to thank my mentor Kevin for guiding me through the project and making me feel comfortable exploring various different approaches.