Max triangulation errors

[senorpablo]

I have a script which produces some semi complex shapes and converts them to edit poly. The shapes can have holes, but they're all orthogonal edges, and can always be triangulated without issue, with some manual turning of edges. Max triangulation works well on the simple cases, but starts to have issues with medium to complex shapes. The retriangulate function often does more harm than good. I'm a little surprised(but not really) this functionality, which is core to 3d modeling, isn't better handled in Max. 

Attached is an example of a very simple shape which does not triangulate correctly.

I know this is probably a very complex problem to solve, but thought I'd throw it out to see if anyone here has any specific experience solving this issue. 

[klvnk]

yeah the built in  triangulation is a bit limited, I don't know anything in mxs but there's a few c++ implementation of sweepline routines knocking around (although they can also have issues with miss matched vert densities and polys with duplicate verts) that can get very good results.

max vs sweepline

max on the left sweepline on the right

[denisT.MaxDoctor]

---

@klvnk wrote:

... there's a few c++ implementation of sweepline routines 

---

are we only talking about the 2D case?

[denisT.MaxDoctor]

Subdivide Modifier works better 😉

[klvnk]

looks a lot like sweepline triangulation to me... sweepline overlayed with subdivide

[senorpablo]

I'll take  a look at sweepline, thanks. If you had to guess, how big of a job would it be to implement in mxs?

[senorpablo]

The shapes I'm working with are planar, so they could be considered 2d in most respects.

[senorpablo]

@denisT.MaxDoctor  Subdivide is an interesting idea. I tried it out, but I don't get the same results you are: 

I tried various combinations, applying it to the spline, and to the spline converted to edit mesh/ edit poly first. I get the same result above. I'm using Max 2020.

[denisT.MaxDoctor]

This is the same result as I showed above. The only difference is in the visibility of the edges. To make the edges invisible, set "Display Subdivision" to OFF.

[senorpablo]

---

@denisT.MaxDoctor wrote:

This is the same result as I showed above. The only difference is in the visibility of the edges. To make the edges invisible, set "Display Subdivision" to OFF.

---

The results are different than what you show. With subdivision, I get a bad tringle in the same place as using edit poly. You can tell because the shading is not consistent. This is with edges only off--no difference. 

[denisT.MaxDoctor]

set the Subdivide to a very high size (at least greater than the length of long diagonal of the object's bbox)

[senorpablo]

---

@denisT.MaxDoctor wrote:

set the Subdivide to a very high size (at least greater than the length of long diagonal of the object's bbox)

---

In my screenshots, the subdivision size is set to greater than the objects size in any axis.

Did you alter the spline mesh from my sample file in any way before taking your screenshot? If the verts are moved at all the triangulation changes.

[denisT.MaxDoctor]

I have not tried your file (well, first of all, it is saved in version 2020 but my test version is 2016). Besides, it's not a big deal to make such a spline yourself.

Finally, I tried your file ... what can I say ... "we wanted to make it better, but it ended as usual"

They changed the Subdivide algorithm in 2020 and it no longer works as well as it did in 2016.

Alas ...

[klvnk]

I think now that the subdivide mod was (is) some form of constrained delaunay triangulation (CDT) it gives very similar results to sweepline in many cases. Though the versions I've looked at do suffer from similar problems as sweepline (not liking duplicates and self intersecting poly edges). Odd that they've changed it in later versions what ever the code is it works well as a triangulator and does seems they fixed issues suffed by other routines. Surprised it's not be used to replace the default poly triangulation.

[domo.spaji]

I don't have that "error" with your file (in 2021).

Although, can reproduce it by altering (Spline) verts pos.

But Subdivide mod. fixing it - same way in Max 2015 and 2021...

But you have to ensure you have planar spline (verts) all the time - not case in your file...

Although all verts showing 0,0 on X...

Apply Turn To Poly mod. with checked "Require Planar Polygons"  and 0 treshold, than move 1st spline vert (little Z amount in World/View coord. system to see that.

[domo.spaji]

Retriangulate is useful for fixing (bad) triangulation on concave polygons, not for nicer, more equal sided tris -

as can be well seen in retriangulating letter C example. 

[domo.spaji]

[domo.spaji]

Delaunay triangulation does not minimize edge length gif... ^^^(upstairs)

... so like "oversized" subdivide modifier.