Polygon triangulation


Yesterday my curiosity overcame the fear and I started some experiments with jME. I want to incorporate a modern 3D engine in my existing CAD application (not a game) that currently uses Java 3D. But Java 3D sucks badly. I want to get rid off the old and outdated Java 3D code. The appication is used to draw houses - walls, floors, roofs, etc. I am interested how to represent a wall in jME3. The other objects are similar. A wall is represented by an extruded polygon. That polygon could have holes. It seems that jME works only with triangulated geometry. I’ve found the class com.jmex.font3D.math.Triangulator that maybe will fit to my needs. But unfortunately, I cannot find it anywhere in jMonkeyEngine3 SDK. And there is no trace of the hole com.jmex package? Is it deprecated in version 3? It appears only in the docs.


jmex is jme2 only.

Meshes sent to the video card are triangles, so to handle quads and “non-triangulated” surfaces you will have to fake the look of a flat surface in the client. The Quad class does this already: it is actually just two triangles. You could represent your walls by extruding Quads, then you have a bunch of quads, already triangulated for you.

10x for the fast the reply! My wall is actually represented by the java.awt.Area class and it could be not just a simple rectangle and also could have arbitrary holes inside. Decomposing it to a bunch of quads is not something trivial. Is there any analog of Triangulator class inside jME3?

You would have to use multiple quads to represent a wall with holes in it. For example a wall with a single window could be made of four quads.

There is no triangulator class for jme3, however it might not be that hard to convert the jmex one.

It can depend a bit how the walls are interacted with: static and never changing, or modifiable where you can create and remove windows. For the latter having quads might make more sense than a tri mesh.

Manually creating the quads is not feasible, because the real task is more complicated than I explained. I explained it more simply than actually is. The walls are very dynamic so I need a solution for arbitrary polygon with holes. Do you know if jME Triangulator works stable and why it is deprecated? I could integrate it in my project if it works fine. Porting Java3D triangulator looks more difficult.

It is deprecated because all of jme2 is deprecated. The underlying mesh, material, geometry structure is different in jme3 than in jme2.

So if your meshes are more complex, all you really need is a triangulation algorithm (many free ones on the web) that can produce some sort of set of triangles. Triangles can then be created into a mesh quite easily. You should be able to borrow from the jmex triangulator the algorithm that produces triangles and adapt it for jme3. There is a jme2->jme3 model converter available, you might be able to look at its source for guidance on the conversion: http://hub.jmonkeyengine.org/groups/contribution-depot-jme3/forum/topic/jme2-loader-almost-in-update-center/

I promise you that there is a reasonably straightforward triangulation algorithm out there that will handle any arbitrary complexity polygon-with-holes situation. You’ve already simplified things a lot by constraining it to two dimensions.

Remember that game models can have many thousands of vertexes. Your triangle algorithm doesn’t have to be perfect - just not terrible.

Which algorithm or implementation do you mean? I’m not sure what is going to be the best for me. In 99.99% of my cases, the total vertices in the polygon (including the hole) will be not more than 8-9.

And BTW I will rely on the triangulation only for visualization.

I don’t have a specific algorithm in mind but I sketched out a quick model in my head that would work so I assume there are more optimal solutions out there.

The algorithm I thought of in my head was essentially a flood fill that would work out from one corner covering the space in triangles until it completed. I did a bit of googling though and found a few possibilities like:

You could take the full set of points for your wall and do a http://en.wikipedia.org/wiki/Delaunay_triangulation on them and then go back through and delete (or never generate) the triangles inside the sections to remove. Google also found http://en.wikipedia.org/wiki/Ruppert’s_algorithm which may apply as well.

Check out: http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html for a visual demonstration.

Basically have a google for meshing/triangulation algorithms and see what you like the look of…

Delaunay is not ideal for triangulating a mesh. It can cause problems if the mesh is an exact square, and it doesn’t handle holes (you have to remove them manually afterwards). There’s easier routines and I wouldn’t pick it first.

But as you said, there are many implementations on google. Java Topology Suite (JTS) has a triangulation implementation, and it is worth looking at the code for the jme2 one.

Beaten to it

There’s constrained Delaunay for weird meshes. Pretty sure DT/CDT is the most commonly used algorithms out there? :o

Constrained Dealunay is a better choice than regular Dealunay but I’m not sure if it is the best (depends on too many requirements), possibly most common. It’s been too long since I have researched this topic to provide a valid and up-to-date opinion.

I will first try with jmex Triangulator. If it has any problems, I will try to implement DT or CDT. 10x for all the advices, keep up the good work! 8)

Hello again! I wanted to inform you that Glyph3D triangulator worked. The solution is not fully tested yet. There’s the result for now:



Not bad for 2 days after start with jMonkey!!! Thank you guys for this wonderful engine! It is so nice and interesting to work with like a kid playing with its favourite toys!

BTW. Could you tell me a solution for that stitching / bleeding of the shadows? Maybe I need to override the polygon offset of the shadow material or the wall material’s?

1 Like

What shadows are those? Is it PSSM with 1 split? Just asking because of those white squares.

@androlo said:
What shadows are those? Is it PSSM with 1 split? Just asking because of those white squares.

Yes, this is using the PSSM, but what do you mean 1 split? The 3 white squares are some debug views of jME3.

In that debug view the right side of the wall is cut off so its not in the shadow map. Perhaps that’s the issue?

Do you use ppsm shadow renderer? also make sure your shadow direction is never 90degree to surface, that currently creates artifacts.


I had some similar issues with grass quads and pssm shadows. It became better by using more splits (you can set the number of splits, I’m using 3. I think you can set it both in the PSSMrenderer constructor and through a setter.

Maybe my problems also has something to do with that 90 degree stuff. They are perpendicular to the ground.