Create good mesh problem

[Gears_Gears]

Hi!

I am working on script to turn ring of points into mesh grid that follows Rhino’s quad topology rules (every point has 4 edges, unless of course it is on the border of the mesh!)

This is straightforward if the set of points is equal to their convex hull. The problem is, if they are not (see picture below, where I have a crescent-like), I can get bad quad if I do not choose which points to make each quad carefully!

Since the point of the script is to not have to look at every ring and choose how to make quad, how can I make sure to have as good a quad-ding as possible? (bad quad-ding as in, the set of points of the quad is not equal to the convex hull of these points. I realize that it is not possible to always avoid these for, but I want to minimize them)

When I search topology or bad-quads, I just get a bunch of blender tutorials on quad-ding and, of course they are all about dragging points by hand! I think I am missing some vocabulary or key-words in my search.

Thanks so much!

[Gears_Gears]

In an unsuccessful attempt, I tried to measure the angles to detect the crescent-shape situation, but it seems I cannot tell grasshopper which direction to measure the angle from (i.e. an angle is acute from one side but obtuse from the other).

[Gears_Gears]

It looks like whenever the center is very close to moving outside the shape itself, the generic way to make quad (use center point as the center vertex) result in very bad quad (not just not-convex, also flipped)

[PeterFotiadis (Pfotiad0)]

Given the opportunity … get a demo for the general case (impossible - obviously - to solve it without code). That type of stuff is used - mostly - for filling Mesh Holes, meshing any Polyline … blah, blah.

BTW: PlanB is to use K2 (seriously slower)

[AndersDeleuran]

I’m sure this is possible without scripting, but here’s a potential GHPython solution (that assumes a centerpoint in addition to the ring points):

230523_ConcaveQuadMeshDisc_00.gh (5.4 KB)

[Gears_Gears]

Thanks for your reply! I will look up on mesh holes and poly line meshing!

One condition I am trying to follow is Rhino’s topology rule, which is that each non-border vertex has four lines leading up to it. From the demo, it looks like getting triangles is one way to go at the problem!

[Gears_Gears]

Thanks for your help! It looks like ordering of the vertices affects the quality of the quads–for example, in the bottom picture face 1 0 7 8 is a ‘bad quad.’ How could this the quality of the vertex be improved?

[PeterFotiadis (Pfotiad0)]

@Gears_Gears

I will look up

There’s various levels of efficiency on that puzzle (and obviously the top dog solutions are kept internal - for more than obvious reasons).

Given the opportunity:

1. If your collection is convex then a weighted sum of pts is a way to start (plus ordering the pts: classic Sort by angle etc etc).
2. But the general case is 1M miles away from that sort of thinking (most notably if you are after some “good looking” solution … meaning in fact some sort of MOO (LOL) plus " auto enhancing" the Poly nodes (see below [case: Polylines - NOT Mesh Holes]). That’s achievable but only if the Elapsed per candidate is “reasonable”.

[Gears_Gears]

Thanks for your detailed reply! This is way more complicated than I thought!

[AndersDeleuran]

@Gears_Gears

… in the bottom picture face 1 0 7 8 is a ‘bad quad.’

So “bad” means that the face quadrilateral is concave?

@Gears_Gears

How could this the quality of the vertex be improved?

If quality then implies having zero concave faces, there are multiple solutions depending on your requirements (e.g. can vertices be moved? can vertices be deleted? can faces be triangles?). You could:

1. Solve the problem globally prior to meshing by computing the convex hull of the ring points. And then deleting or projecting points that are not in the convex hull onto it.

2. Solve the problem locally during/after meshing by identifying concave faces (e.g. by computing internal face angles and finding ones above 180 degrees) and then deleting/projecting offending vertices within such faces to make them convex.

Either way, you probably need to provide context/additional cases and specify your requirements a bit for us to provide more meaningful suggestions/solutions.

[PeterFotiadis (Pfotiad0)]

Start from here. Level required: mid to advanced (and forget MOO “optimization” for the moment).

If you do that in C# I could provide help/tips (but not the solution: strictly internal stuff etc etc).

A-robust-hole-filling-algorithm-for-triangular-mesh.pdf (660.6 KB)

[AndersDeleuran]

@AndersDeleuran

Solve the problem locally during/ after meshing by identifying concave faces (e.g. by computing internal face angles and finding ones above 180 degrees) and then deleting/ projecting offending vertices within such faces to make them convex.

Just tried implementing this (along with the option to shift the ring points), seems to work okay assuming we’re allowing to move vertices.

230526_ConcaveQuadMeshDisc_00.gh (7.3 KB)

[Gears_Gears]

Thanks very much for sharing! I just started learning the C# code!

[Gears_Gears]

Thanks very much for your detailed explanation! I recreated the problem in the gh file below and wrote down a (working but not robust solution. I think the latter part of my code shows how getting better code can really save users from fitting simple ideas to complex network of modules. You pointed that out in a related post and I really agree!):

The goal is to create quad-ding where:
1 besides vertices on the border of the mean, every vertex has exactly 4 edges (no more no less, to follow Rhino’s topology rule) ← this is the main reason I could use remshing-topology related tools, since the create mesh that don’t follow the topology rule
in other words, my mesh will be a grid that follows a shape (You have a very good solution for the convex case that is more elegant than mine)
2 not move any points
3 In my (much more long-winded) solution (I am doing the 3x3 case, which needs 12 vertices; the example), I enumerate all possible vertex ordering to find the best one. Then, I tally up the number of concave (thanks a lot for the vocabulary-I could not figure out a way to describe them!) quads (detecting them by comparison against convex hull).
quad_mesh_problem.gh (25.4 KB)

In the use-case for this code, I of course expect there to be right number of vertices!

The current idea is that for the internal vertices, I use the area centroid as guide. This did not work because once the centroid leaves the area I am doing the quad-ding for, I actually get flipped quads, which I don’t know how to prevent.

Also:
1 I know it’s probably not possible to get no concave quad-ding at all, so I am just trying to minimize the m (while getting a valid mesh where we don’t have faces lying on top of each other!)
2 currently, my example problem has two neighboring vertices evenly spaced out (this is not required at all!). I think one way to get a better set of starting vertices would be to move some neighbors closer to each other. However, I don’t have a good logic behind how to do that, and I could not find a good way to translate my experience retopologizing by hand
3 ideally, the quad-ding mimics the ‘overall shape’ in some way. In this case, the ‘overall shape’ is a quad. Depending on the complexity of the shape, we could dynamically improve the grid (e.g. for simple bean shape, we can use 2x2. For complex-er shape, we can go 3x3 or 4x4 quad-ding)

[Gears_Gears]

by ‘following’ the shape I mean:
1 minimize the ‘white space’, which is difference between: space covered by quad-ding, and space of the ‘overall shape’
2 minimize the over-shooting, which is quad-ding covering space that is outside the boundary (in the crescent, we can see this is unavoidable for the left arc, since we are putting straight line on curve that is concave

[PeterFotiadis (Pfotiad0)]

@Gears_Gears

I enumerate all possible vertex

Some tips:

1. Order your pts (if are random) CW/CCW. This allows to monitor vector angles. Get the center according some logic (classic: weights and/or some other). If centers are many (i.e. using different logics) do the following into a Loop.
2. Create a suitable Class that samples (into a List of the defined custom Type) all quad solutions (i.e. starting from idx%pts.Count etc etc). Add a Property for the rating (for instance IF you are after “as much” as possible “even” quad angles … compute the rating accordingly [in a way … as we do in MOO]). Of course this is related to the center Pt as well … meaning that a small piece of K2 C# code (as an option) could help
3. OrderBy rating the List.

BTW: In any case AVOID tuples for monitoring the qued indices (who uses tuples these days?). In fact you don’t need to enumerate the quad indices at all since you can implicitly calculate’m (never date the same girl twice etc etc).

Say:

BTW: Obvioulsy during the “permutations” (LOL) you can skip a given solution if a Vertex is concave (VS the previous/next). But this not safe since we are after an “optimum” rating … so let the idiot (the computer) to count all the beans.

BTW: for the center pt (general case: unsuitable pts collections so to speak) … the so called visual center algos may help (Google that one).

[Gears_Gears]

Thanks a lot for your detailed reply! It looks like I have my work cut out!

[PeterFotiadis (Pfotiad0)]

Use something like this (pts [and P] in CW order) for angle rating - per quad, then per solution (if multi solutions are in the menu).

public void GetAngles(int idx, Point3d[] P, int rMode){ // P: Quad pts

    double[] A = new double[4];

    for(int i = 0; i < 4;i++){
      Point3d prev = P[(i + 4 - 1) % 4];
      Point3d curr = P[i];
      Point3d next = P[(i + 1) % 4];

      Vector3d v1 = prev - curr;  Vector3d v2 = next - curr;
      double a = Vector3d.VectorAngle(v1, v2, plane);

      A[i] = Math.Round(RhinoMath.ToDegrees(a), 2);
    }
    angles.AddRange(A, new GH_Path(idx));

    double rate = 0;
    if(rMode == 1) rate = A.Max() - A.Min();
    else{
      double avg = A.Average();
      double sum = A.Sum(d => Math.Pow(d - avg, 2));
      rate = Math.Round(Math.Sqrt((sum) / (A.Length - 1)), 2);
    }
    rating.Add(rate, new GH_Path(idx));
  }

[Gears_Gears]

Thanks so much for your detailed explanation! My code currently stops at at making a 3x3 grid because that seems to let me get away (not have flipped faces or too much concave quads) with not doing closer analysis, while avoiding extraordinary vertices.