3D triangle generation from list of points

Newbie & Debugging Questions
#1

I’m trying to display a 3D surface based on an arbitrary list of 3D points (kind of like having the points in 3D space, then dropping a blanket down from the Z direction such that the surface lies on top of all the points). No holes or anything like that - I just want to view how the surface looks.

Although this would seem like a very common thing, Ive not found anything in Java 3D or JOGl to just take these points and display it.

Is there a way to do this easily in Java 3D and/or JOGL?

Do I have to convert these points into triangles (in a 3D space) in order to display the surface using one of the many algorithms out there (Delaunay etc.)?
If so, is there a point cloud --> triangle mesh algorithm built in to Java 3D and/or JOGL, or do you know of a Java implementation of one?

Any pointers/suggestions appreciated.

#2

That highly depends on what your points look like. If its very uniform/grid manner, you could just create a list of “indices” that outline how the points should be stitched together into a triangle.

So for a square with the points sent as (x, y): (0,0) (1, 0) (1, 1) (0, 1), the indices would be 0, 2, 1 0 3 2.

the “indices” refer to the points, so index 0 refers to point (0,0) wherase 2 refers to (1,1) because you declared it 3rd…etc. I would suggest doing it in a uniform fashion like Ive outlined above and seeing how things go from there.

HTH, DP :slight_smile:

#3

Generating a 3d mesh from a point cloud is a non-trivial problem.
If you have a read around, you’ll find there are many research papers examining the problem - and an equally large number of proposed algorithms.
I would imagine any half-decent 3rd party solution is likely to have a hefty price tag attached.

#4

You should check out how OBJ files work.

#5

What you’re describing is a convex hull, assuming you want the surface to wrap all the points. Once you know that name, Google can help you can find many algorithms and implementations provided by the academic community.

#6

I think what he’s after is surface reconstruction from 3D point sets.

#7

Many thanks for all the suggestions.

Ok, so Ive already looked at the Convex Hull stuff (since it was referenced from many of the Delaunay papers and web pages I looked at).

What I’m unsure of is if the Convex Hull will generate the triangles for the surface, or if it will “close” the surface thus making a 3D object (which isnt what Im looking to display).
Im trying to build a 3D surface plot of some arbitrary data (Im looking for spikes in some function ouput). Each routine takes many minutes to run (its complex). While trying to make the function smooth, I am varying various input params. Id like to graph the output in real time, such that if I see a spike in the graph, I can kill the test, and try something else - I dont want to have to wait 20 mins just to find out that the function output still isnt smooth.

My understanding of this problem are based on the following:
1.) I need to generate triangles (or quads) from my point cloud so that I can get Java3D (or whatever) to draw these.
I spent several hours looking at Delaunay algorithms to figure out my triangles - how is this different than computing the convex hull?

2.) If my data was on a known XY grid, life would be much easier.

Ive looked at the Convex Hull. Now Im a little confused - the convex hull seems to give me the outer boundary - does it also give me the triangles that make up the surface, or do I need to use the Delaunay algorithm for that?

Thanks for the help.

#8

Can’t you;

Find the min(x,y,z) and max(x,y,z) of your data.
Define a grid of suitable resolution (say 100x100) from min(x,y,z) to max(x,y,z)
for each vertex in the grid
set the vertex height to the highest point within x,y range of the vertex (assuming z is up)
render the grid

It won’t be 100% accurate but it should show spikes clearly enough?

#9

I guess that would work, but having spent hours researching this, Im curious to know how to do it without the grid approach (since I have code that works on an integral XY grid that works now)

#10

Are you sure that such a visualization is the best way to look for spikes? Assuming I understand your problem correctly (which may be a faulty assumption), spikes could occur “behind” your solid object, where a user cannot see them. Mapping the problem into a 2D visualization is probably safer. Alternatively, if you are dealing with a dynamic function whose output could potentially change faster than the visualization or the human eye can catch, I would just use an analytical (non-visual) approach to detect and warn of spikes.

#11

I have a routine in Java3D that will let normalize and let me rotate the surface plot, so this isnt a problem.

We have attacked some problems before like this, and we currently export the data, and import into a 3rd party application, which is a pain.
The “object” is just a surface - imaging banging nails into a block of wood, to various depths, and then dropping a thin cloth over the top - this is all I’m trying to visualize.

Based on what Ive read, I think the Delaunay algorithm in 2D is the way to go (the Convex Hull algo closes off the surface, thus making a solid which isn’t what Im after).
However, although it seems that every geometry researcher on the face of the planet has written a Delaunay Java applet, none of the source works out of the box for what we want to do (which doesnt seem to be too far out there), so I’m currently chopping at one I found that looks promising, but even that one starts with a massive starting triangle, and then plots all the points inside that triangle - which just introduces additional triangles and edges that are not relevant.

The model that is under inspection is very complex, and if I could do this in an analytical manner, I would - however, the number of variables in the model, and the time it takes to execute the model is prohibitive hence why I want to plot it in 3D. Ive already done this for some 2D problems, and it was very effective.

#12

may be you can try this way :

define a square (four new vertices) using the min and max pos of your list of vertices

a---------b
| |
| |
d---------c

so you have two triangles in your face list that define your quad.
f1=a,b,c
f2=c,d,a

than for each vertices in your vertices list look at the triangle that the point lie on (when looking on top) than divide it with three new tirangle.

a---------b
| e |
| |
d---------c

remove f1 from the list and replace it by three new tirangle f3=e,a,b f4=e,b,c f5=e,c,a

you new list is:
f2=c,d,a
f3=e,a,b
f4=e,b,c
f5=e,c,a

repeat that for each vertice in the random vertices list.