Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (574) Games in Android Showcase (154) games submitted by our members Games in WIP (620) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 3D triangle generation from list of points  (Read 3921 times) 0 Members and 1 Guest are viewing this topic.
StanAccy

Junior Newbie

 « Posted 2008-06-29 20:47:25 »

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.

darkprophet

Senior Devvie

 « Reply #1 - Posted 2008-06-29 22:02:52 »

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

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Abuse

JGO Knight

Medals: 17

falling into the abyss of reality

 « Reply #2 - Posted 2008-06-30 01:10:19 »

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.

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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #3 - Posted 2008-06-30 02:17:49 »

You should check out how OBJ files work.

See my work:
OTC Software
purpleguitar

Junior Devvie

 « Reply #4 - Posted 2008-06-30 12:01:19 »

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.

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.
cylab

JGO Ninja

Medals: 78

 « Reply #5 - Posted 2008-06-30 12:51:52 »

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

Mathias - I Know What [you] Did Last Summer!
StanAccy

Junior Newbie

 « Reply #6 - Posted 2008-06-30 15:24:21 »

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.
SimonH
 « Reply #7 - Posted 2008-06-30 18:26:41 »

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?

People make games and games make people
StanAccy

Junior Newbie

 « Reply #8 - Posted 2008-06-30 19:39:12 »

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)
purpleguitar

Junior Devvie

 « Reply #9 - Posted 2008-07-01 11:43:09 »

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.
StanAccy

Junior Newbie

 « Reply #10 - Posted 2008-07-01 13:33:38 »

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.
DzzD
 « Reply #11 - Posted 2008-07-01 14:43:09 »

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

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.

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Riven (28 views) 2015-04-16 10:48:47 Duke0200 (42 views) 2015-04-16 01:59:01 Fairy Tailz (32 views) 2015-04-14 20:13:12 Riven (33 views) 2015-04-12 21:36:37 bus hotdog (49 views) 2015-04-10 02:39:32 CopyableCougar4 (51 views) 2015-04-10 00:51:04 BurntPizza (51 views) 2015-04-06 22:06:58 ags1 (53 views) 2015-04-02 10:58:48 Riven (52 views) 2015-04-01 18:27:05 ags1 (69 views) 2015-03-31 10:55:12
 theagentd 27x BurntPizza 17x wessles 15x 65K 11x kingroka123 11x Rayvolution 11x alwex 11x KevinWorkman 9x kevglass 8x phu004 8x Hanksha 7x SHC 7x Olo 7x ra4king 7x Ecumene 7x Roquen 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org