What is the best data structure for representing nodes in 3D space?

Question

Hello! ... and thanks for reading...

I'm still learning the ropes so please be forgiving... ;-)

I am writing a function that meshes a solid in space. The mesh is done by using objects of a "Node" class and each node is represented by:

int id
double p
double r

Initially I thought that a map would be the way to go: with a map I can make the association between the "id" key and the second key (a pointer to the node object).

Something like this:

int nodeId;
Node *node;
std::map<int, Node *> NodeMap;

Then, when I create the nodes I just call the "new" operator. E.g in a for loop I do something like this:

node = new Node(i); // the node constructor sets the id to the value of i.

and I add the new node to the map:

NodeMap[i] = node;

But.... I realized that I will need to do a lookup in the map not by first key (the id) but by the p and r parameters (the coordinates of the node).

In other words I will need something that returns the node id given the values of p and r. A map is a perfect container if the lookup is done using the integer first key (id). Does anyone have a suggestion on how to solve this particular problem?

Thanks much! AsvP.

Answer 1

As with any "what should I use to represent this structure" question it does really depend on how you want to interact with it

Scene graphs are common in 3D libraries, they provide a tree based traversal over the nodes, often allowing the transforms, interactions and other attributes to cascade down the tree.

For something to hold objects to be rendered a common structure is a Binary space Partitioning Tree which allows efficient culling of objects which are definitely not visible or occluded by others.

Edit; I missed that you were indexing by floating point. This is normally a bad idea (since the exactness required in most standard maps will causes issues relating to the instability of floating point behaviour). Unless you really want this behaviour

In this case you need to have some way of handling it such as:

• chunking your domain so that you can accurately point at a small section of it and prevent more than one node occupying the same chunk of space.
• Have some way of bucketing your space (possibly requiring adaptive subdivision of areas with higher concentrations of nodes) so that when asking for the point p,r you are given a (possibly empty) set of nodes present in that region.

Answer 2

Have you looked at the available geometry libraries, I'm not an expert in this domain, recently heard about GTL during the preview at boost mailing list.

Answer 3

What are you actually trying to do?

If you have 2 coordinates representing a 3d position, then I assume that they are inputs to some parameterised function which produces the 3 vertex components... if this is the case then what are the nodes actually for? In most cases such a parameterisation can be used to directly produce a mesh.

As an example consider a unit sphere, which takes parameters u,v (0...2PI) and (0...PI) and turns them into coords by doing:

x = sin(u)*cos(v);
y = sin(u)*sin(v);
z = cos(u);

This can be used to create a mesh by varying u and v across the appropriate ranges and merging any duplicated vertices. e.g. take u = 0, u = 0.1, v = 0 and v = 0.1 and you can create four vertices V(u,v) which allow you to create two triangles. Since I'm pretending this is a general case and not a special case you will have to do things like checking if vertices are duplicate and merging them and checking for degenerate triangles and deleting them.

Answer 4

Not to do with the lookup issue, but with your creation of Nodes using new. If the map owns the Nodes, as it seems to do in your case, you can sinply say:

map <int, Node> mymap;     // map of Nodes, not pointers to Nodes
...
myMap[i] = Node( whatever );

This will greatly simplify your memory management. In C++ you should avoid explicit dynamic memory allocation with new wherever possible.

Answer 5

A map<> won't work. C++ associative containers work on the basis of key equality, and comparing floating-point numbers for equality doesn't work at all well.

It sounds like you need to find a node, given x and y. The best way will depend on what you're trying to accomplish. Are you trying to find the nearest node, given the coordinates, or are you going to calculate coordinates that are very close to a node, and then you need to find the node?

For the second, you'll probably be well off sorting the nodes on either the x or y coordinate (I'll assume the x), and doing a binary search to find which nodes have x coordinates very close to your given x. That will generally select a small number of nodes, which can be searched for the approximately correct y.

(Of course, if the nodes are in some sort of predictable grid, you should be able to provide some means to calculate directly, like round x and y to nearest integer if you've got integral lattice points.)

If you need to find the closest node, well, that gets a bit complicated. I don't know enough about this to help much, but there are resources for geometric algorithms.

Answer 6

Jherico hits the nail on the head. I am using two parameters to produce a 3D mesh. The two parameters are cylindrical coordinates. One is the angle and the second is the z along the axis. The radius is a constant, just like his example of a sphere. I can create a mesh, but I need to update it and the function that does the update does not take the id as input argument. It takes the "original position" by using those parameters p and r.