What's a good way to have every tri on a sphere's surface know which hexagon/pentagon cell it's in?

There are lots of games out there that use a planet built from hexagons and pentagons. Before We Leave, for example:

I want to work with a similar thing in Unreal, but I also want to be able to manipulate the shape of the planet at a finer resolution than simply those large cells. So here’s a geodesic icosahedron in Blender, then the same thing with 2 levels of subdivision, and then again with 4 levels of subdivision and some manipulation made possible by the higher vertex count. I’ve added the colours just for visualisation.

https://forums.unrealengine.com/filedata/fetch?id=1867473&d=1614682645

Now taking that shape, returning it to its spherical-ish form and ditching the materials, this is what Unreal sees when it is imported:

https://forums.unrealengine.com/filedata/fetch?id=1867474&d=1614683309

I want to be able to do things like:

  • each cell has its own state/data
  • know which cell any point on the surface is in
  • per-cell material changes
  • operations based on things like counting cells with some state across the whole surface, etc.

The two main caveats are:

  • a high vertex count is required
  • the mesh can be divided into regions with clean edges, ie., regions borders are visually smooth, unlike the red region in the image below. I’ve been going with the icosahedron for this reason, but hexagons aren’t strictly required, only smooth regions are.

https://forums.unrealengine.com/filedata/fetch?id=1867475&d=1614684521

So the question is:*
*How would you go about getting every triangle to know which hexagonal/pentagonal cell it is in?

There might be another path entirely to suggest that ticks the above boxes. I’m interested if so.

Related notes:

  • I’ve read about “sections” in a mesh, but it’s hard to find useful information on them. Maybe that could help.
  • Separating cells by assigning materials in Blender isn’t an option, as meshes could have 500-1000 cells.

It appears there’s no edit option anymore. Sorry for some poor formatting there.

Hello! This problem is not very special and there are several methods to solve it. You can try this one

  • every tri has it’s Direction vector (from center of sphere to tri center). Also you can calculate the same thing for each hexagonal/pentagonal cell. Normalize all those. Now you have some unit length vector for tri (lets call it Test Vector) and an array of unit vectors for each cell (lets call them Cell Class Directions). Now just iterate through all Cell Class Directions and select the one that will give the max dot product with Test Vector

Thanks for the suggestion. :slight_smile: That dot product trick is a good idea but the main problem I’m seeing with it is that it wouldn’t be the max dot product result, but rather a range of max dot product results (due to the triangles in a cell having some variation in their orientations).

Defining that range, to know what’s in a cell and what’s not, feels like just as much a problem as the problem itself and pursuing that approach would start to get a bit inelegant I think… a bit too far down the rabbit hole. The sphere is a bumpy sphere, for example, so trying to calculate a range in advance from some property of geodesic spheres would be prone to the types of bugs I’d rather avoid completely.

While I’m hoping for a better method than this one, this is what I’m currently going with. I won’t mark it as an answer, but it’s maybe it’s worth putting here for posterity anyway:

I’m currently going with an approach that works along mathematical lines; firstly using a 2nd slightly larger “shell” mesh that hasn’t been subdivided at all, to define what the cells actually are. That is placed outside the main mesh (the one with the subdivisions), then for each tri in the main mesh, line trace outwards to the shell and compare the normal it discovers to all normals discovered so far, and build an index of tris-per-cell this way.

But there is often a more “Unreal” way to do things that uses the editor’s abilities to do something in a smarter way than crunching vertices. I’m curious if there is one in this case.

I’m not sure if my last comment worked… there’s no “waiting approval” message appearing.

The short version was: Thanks for the suggestion, nice dot product idea, the main problem was that it would require not just a maximum, but a range of maximums to be defined since the tris in a cell have a variety of orientations. Trying to define that range in a way that isn’t error-prone feels like as much a problem as the problem itself.

An answer I posted describes the approach I’m taking, but it’s waiting for approval. It’s also mathematical, but I’m really wondering if there are some good tools about the Unreal editor that can lead to an approach that isn’t just vertex crunching.

Yeah pretty much what I’m going with, using a 2nd “shell” mesh to define cells. I’ve already written as much but wow this message board takes ages for replies to appear and won’t let a question be edited. :confused:

ray trace from the center, assign each cell an XYZ id.