Hi,
I have seems to be simple problem. But cannot figure out how to start.
I have simple quad mesh, it is grid, but with pixelated edges.
I want to decompose this pattern into 4 pixel tile pattern on the right, and skip not full tiles.
Any suggestion would be much appreciated.
Hi Petras
Do you have “control” over qaud-corner-points = did you created quad-polygons from your points or it is result of some meshing operation?
Anyway, solution requires that you are able to Map each qaud-polyline(QP) to 2D array.
Maping has fo fulfill following conditions:
Now, to be able to do reverese-maping from 2D array to QPs, we can choose our array to be Guid[,] of QPs, so our array will be Guid[a,b], Guid[a,b] mapping2DArray = new Guid[a,b] (you have to determinet a and b).
Map method will be int[] MapQS( PolyLine qp)
int[] 2dCoordinate = new int[2]
2dCoordinate = MapQS( qp) //qp is quad-polyline
mapping2DArray[ 2dCoordinate[0], 2dCoordinate [1] ) = qp.Guid ;
After Mapping you will have 2d array where on place of holes value will be Guid.Empty, and everywhre else will be Guid of corespondong QP. You have actully “unRolled” the mash to 2d array.
Now you create same size 2d Array Tile2D[,], populate it with tile whatever shape you want, compare it against your mapping2DArray and keep only those tiles for which there is no “hole” in mapping2DArray .
Implementation of thsi part should be simple.
Everything you need is to know how to map QPs to 2d array.
Radovan
It is a result of meshing operation. I have quad mesh like this and I can get corners.
I was also thinking about 2D mapping.
Maybe I did not follow or misunderstood.
But what do you think would be a right way to map it to 2D. As quad mesh face indexing has no specific order.
So if I have a large 2D grid, how to start?
I see.
So if quad-grid is result of meshing then you have to implement your mapping method from ground.
To be able to do 2d-mapping you have to determine inaginary u and v direction of your quad grid.
So we have quad-polylines, let QPi be an arbitrary quad-polyline.
Create two lists of integers, UCoord and VCoord which will be coordiante of our QP in mapping2DArray.
Create one list of Guids, qpGuids where we store guid of particular QP.
So for fist QP we process we will have qpGuids[0]= QP.Guid, UCoord[0]= u-coordinate, VCoord[0]= v-coordinate.
For second QP we will have qpGuids[1]= QP.Guid, UCoord[1]= u-coordinate, VCoord= v-coordinate, and so on.
We also create collection of all available QPs not yet processed, QPsToProcess.
Start with selecting any QPi. i=0.
Remove QPi from collection QPsToProcess.
QPi will be center of our mappingArray, CurrentU= 0, CurrentV=0. (mappingArray can have negative index as well - see following).
So we have first qpGuids[0]= QP.Guid, UCoord[0]= CurrentU (=0), VCoord[0]= CurrentV (=0).
Choose one edge on QP and define it as u direction (direction from center of QP to that edge).
Choose neighboring edge on QP, next segment of polyline (in direction of polyline points) and define it as v direction.
So now we have u and v direction.!
Now we move to neghbouring QPs. There are 4 dirrection we can move +u, -u, +v and -v.
Lets do it for +u direction, it is analog for any other direction. We move to +u only if there is neighbour QP there.
So you have origin QP, QP0.
Increased i++. Neigbour QP, QP1…
Condition that QP1 is neighbour of of QP0 (and vice versa) is that +u segment of QP0 is equal to - (-u) segment of QP1.
It is important that all QPs have same orientation = polylines have points oriented in same direction,
It means that QP0 ‘+u’ is LINE( QP0[0], QP0[1] ), and QP1 ‘-u’ is LINE( QP1[2], QP1[3] ), so
QP0[0] = QP1[3], QP0[1] = QP1[2] which gives us that :
QP0 ‘+u’ segment = - QP1 ‘-u’ segment
So you have to compare QP which is being currently porccessed with previous one and sort the polyline points if neccesary.
So becasue we moved to +u direction and found neighbur there QPi:
CurrentU= 1, CurrentV=0.
and we can write to our lists following
qpGuids[1]= QP.Guid,
UCoord[1]= CurrentU (=1),
VCoord[1]= CurrentV (=0).
Remove QPi from collection QPsToProcess.
And we can go on.
And obviously we can do it as recursion for all 4 directions!
Radovan
Actualy +v direction should be this
R
Halfedge meshes are perfect for this kind of topology traversal. Because each halfedge always knows its next/previous/opposite value, you can trace your tile pretty easily.
So the script starts from a “Seed” halfedge, and then starts growing a tile. As it goes around, it identifies new “spawning” halfedges to generate tiles from, and adds them to the list of tiles “to do”. After it picks each new seed halfedge from the bottom of this list, it removes it. The trick is to keep track of which halfedges have already been visited, and to prevent them from being visited again, and also to kill the current tile when the tile runs into any vertex that isn’t valence 4. This way it grows the tiles across the mesh as you like.
With some extension, you could for sure introduce ways for it to negotiate naked edges (without outright preventing any non-valence 4 vertex as it does now…) but I’ll leave that to you . 
Here’s the script that does the trick, using Plankton.
private void RunScript(Mesh M, Curve S, int L, int W, ref object A)
{
PlanktonMesh P = M.ToPlanktonMesh();
int s = -1;
int e = -1;
for (int i = 0; i < P.Vertices.Count; i++)
{
if (P.Vertices[i].ToPoint3d().DistanceTo(S.PointAtStart) < RhinoDoc.ActiveDoc.ModelAbsoluteTolerance)
{
s = i;
continue;
}
else if(P.Vertices[i].ToPoint3d().DistanceTo(S.PointAtEnd) < RhinoDoc.ActiveDoc.ModelAbsoluteTolerance)
{
e = i;
continue;
}
if (s > -1 && e > -1)
{
break;
}
}
var visited = new bool[P.Halfedges.Count];
var startHEs = new List<int>() {P.Halfedges.FindHalfedge(s, e)};
var tiles = new List<List<int>>();
int exiter = 0; // safety check to ensure no infinite looping
var turnIndices = new List<int>() // Indices where the tile drawing should turn
{
L / 2 - 1,
L / 2 - 1 + W,
L / 2 - 1 + W + L ,
L / 2 - 1 + W + L + W
};
var spawnIndices1 = new List<int>() // Indices where opposite halfedges can "spawn" new tiles
{
L / 2 - 1,
L / 2 + W + L - 1
};
var spawnIndices2 = new List<int>() // Indices where "caddy corner" opposite halfedges can "spawn" new tiles
{
L / 2 + W,
L / 2 + W + L + W
};
while(startHEs.Count > 0 && exiter < P.Halfedges.Count)
{
int he = startHEs[0];
startHEs.RemoveAt(0);
var tile = new List<int>();
bool append = true;
for (int i = 0; i < L * 2 + W * 2; i++)
{
if (visited[he])
{
append = false;
break;
}
visited[he] = true;
tile.Add(he);
if (P.Vertices.GetValence(P.Halfedges[he].StartVertex) != 4)
{
append = false;
break;
}
if (spawnIndices1.Contains(i))
{
int spawnIndex = P.Halfedges.GetPairHalfedge(he);
if (!visited[spawnIndex])
{
startHEs.Add(spawnIndex);
}
}
else if(spawnIndices2.Contains(i))
{
int spawnIndex = P.Halfedges.GetPairHalfedge(he);
spawnIndex = P.Halfedges[spawnIndex].NextHalfedge;
spawnIndex = P.Halfedges.GetPairHalfedge(spawnIndex);
spawnIndex = P.Halfedges[spawnIndex].NextHalfedge;
if (!visited[spawnIndex])
{
startHEs.Add(spawnIndex);
}
}
he = P.Halfedges[he].NextHalfedge;
if (!turnIndices.Contains(i))
{
he = P.Halfedges.GetPairHalfedge(he);
he = P.Halfedges[he].NextHalfedge;
}
}
if(append)
{
tiles.Add(tile);
}
exiter += 1;
}
var polylines = new List<Polyline>();
foreach (var tile in tiles)
{
var p = new List<Point3d>();
foreach (var he in tile)
{
p.Add(P.Vertices[P.Halfedges[he].StartVertex].ToPoint3d());
}
p.Add(p[0]);
polylines.Add(new Polyline(p));
}
A = polylines;
}
tile.gh (68.9 KB)
Wow… thank you a lot for this;)