CGTalk > Technical > Graphics Programming
Login register
reply share thread « Previous Thread | Next Thread »  
 
Thread Tools Search this Thread Display Modes
Old 07-09-2014, 11:14 PM   #1
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
Loop Selections

Hi,
I'm looking for code that shows how to do loop selections in C++.
I code mostly for Cinema4D. But I think I can convert code that's in Maya or other apps format.

The main problem I'm having is that polygons don't follow a static set of shared edges. They are often spun randomly.
For example. The b-c edge on one polygon is not always the shared a-b edge in the neighboring polygon. They don't always follow as set pattern. So I can't just simply select all of the a-b edges to get a loop selection from it.

Is there a standard loop selection type of code that all of the 3D programs use?
This seems like something that all graphics programmers would have in their tool box. But I can't seem to find one with Google.

Thanks,
-ScottA
__________________
My Gallery
 
Old 07-10-2014, 06:23 AM   #2
ThE_JacO
MOBerator-X
 
ThE_JacO's Avatar
CGSociety Member
portfolio
Raffaele Fragapane
That Creature Dude
Animal Logic
Sydney, Australia
 
Join Date: Jul 2002
Posts: 10,954
There are many ways to do it, and what results you get depends on how you want to deal with fringe cases, how diminutive or extensive you want them to be and so on.
In every app you can see loops selecting somewhat differently when they reach poles and so on, and that's because they use different rule-sets and handle fringes and termination differently.

The absolute simplest way to do loops is to treat your edges as directional vectors (normalized) and use a dot product on the neighbourhood, and pick the most parallel one, and keep doing it until the original edge is met in the neighbourhood look-up (loop is closed).
For simple topologies this will work just fine, say loops around a cylinder, but with no additional handling for some perfectly legal topos a skewed angle will send it crawling all over the mesh.

Ultimately the principle is the same, look up connected edges, apply rule, move on until terminal condition (first edge met, boundary met, non manifold spot, whatever you decide the terminator to be).

Other rules to bias the pick of the next edge could be to weigh the fan, so if two edges come very close in parallel value but one is in the middle of the fanned neighbourhood projected on the current point's normal you will pick the one with better bisecting index (in the middle of a fan of N connected elements).

You can also choose to use boundaries as terminators, or to given them very high weight if your originator is also a boundary (this way the edgeloop tool becomes a hole/boundary selection tool as well) and so on.

Arbitrarily connected topologies don't have any parametric qualities to them, so there is no best or universally accepted way to do edge loops, only many different ways to interpret the connectivity and heuristically (guesswork) get decent coherence out of it.
__________________
"As an online CG discussion grows longer, the probability of the topic being shifted to subsidies approaches 1"

Free Maya Nodes
 
Old 07-10-2014, 07:57 AM   #3
Per-Anders
helper bunny
 
Per-Anders's Avatar
CGTalk Forum Leader
portfolio
Per-Anders Edwards
Developer
The Third Party
USA
 
Join Date: Sep 2002
Posts: 12,712
Actually the simplest method is simply to do a ring selection then pick a side and use that for your loop selection, fewer calculations all round, and the result is a guaranteed loop without deviation due to direction (a parallel edge is not a guarantee of parallel flow), points often have multiple edges emanating, but edges typically belong to only one or two polygons.

It's a fairly trivial task in Cinema (ignoring the inbuilt functions that already give you this), simply pick your edge, get the next edge along in the polygon (perpendicular), this is your first ring edge, then calculate the ring by stepping to the opposite (left or right depending on the previous loop edge shared point), use the Neighbor class to get the next polygon from the edge, rinse and repeat till you either run out of opposite edges or hit an edge that's already been used. The algorithm will work in any 3D application, although not all apps have equivalents of the neighbor class built in to their API's in which case you will need to create your own lookup maps.
__________________
The Third Party | Homepage | My Reel
"You need to know what you're doing before you start, and to start because you need what you're doing."
 
Old 07-10-2014, 03:26 PM   #4
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
It's not trivial for me.
I can't figure out the proper questions to ask. And how to solve them in my code.
All I really want is to be able to select the neighboring point (right,left,up,or down) from the currently selected point/points. And so on ...every time I run the code.
I basically need a clamped edge loop that stops when it finds the first neighboring point along an edge in a specific direction.
Basically, taking edge loop code and adding a break to it's loop.

So far I've done it two ways which are not working very good.
Version1:
I used angles and point distances to find the closest points. Then select the point if it falls with a range.
This is horribly complicated and I'm still not getting the proper results from it.

Version2:
I use the neighbor class in C4D on the selected polygons to get the neighboring polygons.
This class has a function called GetPolyInfo() which lets me select the neighboring polygons.
There's an option in it which lets me grab the right[2], left[1], up[0], down[3] neighbor polygon.
It's really nice because it selects the same edge even if the polygons are spun in various ways.
And then I get the point I want to select (a,b,c,d) from that neighbor polygon I selected.
This works fairly well. And I can make a loop selection by running the code multiple times(which is how I want it to work).
But there's a problem with this...I don't want to have to select a polygon. I want to select a point and then get it's neighbor (right, left,top bottom) every time I run it. Resulting in a point loop selection.

I can get the neighboring points, edges, and polygons.
But I don't know how to filter them to get the specific ones so that I can create a loop selection in a specific direction if I keep executing the code.

FYI:
The reason I want this is because I'd like to grow select in points mode in only one direction. And C4D doesn't have that option.
The grow select tool selects the neighboring points in all directions.

-ScottA
__________________
My Gallery
 
Old 07-10-2014, 07:27 PM   #5
Per-Anders
helper bunny
 
Per-Anders's Avatar
CGTalk Forum Leader
portfolio
Per-Anders Edwards
Developer
The Third Party
USA
 
Join Date: Sep 2002
Posts: 12,712
If you're talking the specifics of the C4D API, then you will also find the Neighbor class offers GetEdgePolys, GetNeighbor (the manifold opposite edge to the passed poly along the passed edge) and GetPointPolys, but it does not have GetPointEdges. For you to calculate the edges radiating from a point you must then call GetPointPolys, iterate through the passed array of polygons, find the edges that contain your point and do whatever you need to with them.

However, you do not need to do that if you use the edge ring method. In that instance you simply use the GetNeighbor or GetEdgePolys functions to return the opposite polygon to the edge that you're on, then use the NGon functions to retrieve the full NGon index (as the Neighbor class standard functions deal with the simplified quads and tri's), increase the edge index in the polygon + 2 (or -2 depending on the side being used), and rinse and repeat. You can then determine how you wish to handle poles. The side + or - 2 is always onwards, rather than backwards, you only need to calculate for yourself which side of the ring edge the loop is on to make sure you carry on in the right direction, and that's just a matter of comparing the point indexes.
__________________
The Third Party | Homepage | My Reel
"You need to know what you're doing before you start, and to start because you need what you're doing."
 
Old 07-10-2014, 09:15 PM   #6
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
I might be misunderstanding what you're saying. But I'd rather not use the edge ring method.

I'm able to get the polygons that the point belongs to. Using the GetPointPolys() function. And also with my own custom code that I dreamed up too.
But I just can't figure out how to select the neighboring point in a specific direction. It's frustrating to know how to use all of this code and still be stuck on something that seems like it should be very simple to do.
I was hoping that if I saw some loop selection code. Any code, in any language, in any app. That it might show me what I'm missing.


-ScottA
__________________
My Gallery

Last edited by Scott Ayers : 07-10-2014 at 11:39 PM.
 
Old 07-11-2014, 01:37 AM   #7
Per-Anders
helper bunny
 
Per-Anders's Avatar
CGTalk Forum Leader
portfolio
Per-Anders Edwards
Developer
The Third Party
USA
 
Join Date: Sep 2002
Posts: 12,712
If that's your algorithm then you need to do is what Raf said, a dot product between the incoming and outgoing edges to determine which is the best candidate, pick that edge and move on.

What is the particular problem you're unable to get past with this algorithm?

If it helps I've quickly put together some pseudo code with cinema classes to outline the rough order of events in such an algorithm -

Code:
Neighbor nbr; if (!nbr.Init(pointCount, polygons, polygonCount, nullptr)) return false; //edge and poly are derived from the original edge targeted edgePointIndex1 = polygons[poly][edge]; edgePointIndex2 = polygons[poly][edge + 1]; edgePoint1 = points[edgePointIndex1]; edgePoint2 = points[edgePointIndex2]; loop till the selection finishes { edgeDirection = (edgePoint2 - edgePoint1).GetNormalized(); nbr.GetPointPolys(edgePointIndex2, &neighborPolys, &neighborPolyCount); mostParallel = 0.0; //Limit it to only edges that actually are in line down to 90 degrees, no lower (set this to -1.0 to allow any edge so long as it's in the closest to facing direction) candidateEdgeIndex = NOTOK; for each poly in the list of neighborPolys { //Get the internal point index within the (quad) polygon of the shared point for (i = 0; i < 3; i++) { if (poly[i] == edgePointIndex2) { polyPointIndex = i; break; } } //Get the two candidate edges for this point //in truth we could probably skip one as edges are shared, but winding order would require another test to be sure leftEdge = (points[poly[polyPointIndex - 1]] - edgePoint2).GetNormalized(); rightEdge = (points[poly[polyPointIndex + 1]] - edgePoint2).GetNormalized(); //Don't forget to skip any polygons or edges that are internal to an n-gon //Check to see which is the most parallel edge parallel = Dot(edgeDirection, leftEdge); if (parallel > mostParallel) { mostParallel = parallel; candidateEdgeIndex = index of poly * 4 + polyPointIndex; winding = -1; } parallel = Dot(edgeDirection, rightEdge); if (parallel > mostParallel) { mostParallel = parallel; candidateEdgeIndex = index of poly * 4 + polyPointIndex; winding = 1; } } if (candidateEdgeIndex == NOTOK) break; //No more edges //Also you should check that the edge hasn't already been used, if so then exit as the loop is "complete", just use a simple flag array or if you prefer a BaseSelect will do the job nicely too poly = candidateEdgeIndex>>2; edge = candidateEdgeIndex&3; //Shift the points along to calculate the next edge edgePointIndex1 = edgePointIndex2; edgePointIndex2 = polygons[poly][edge + winding]; edgePoint1 = edgePoint2; edgePoint2 = points[edgePointIndex2]; //Select the resulting edge finalEdge = poly * 4 + ((edge + winding)&3); loopEdgeSelection->Select(finalEdge); //Though in cinema dont' forget to also select the opposite edge on the neighbor polygon }
__________________
The Third Party | Homepage | My Reel
"You need to know what you're doing before you start, and to start because you need what you're doing."
 
Old 07-11-2014, 07:29 PM   #8
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
Thank you for the pseudo code Anders. I really appreciate the effort.
But some of it is not making sense to me. There's too much pseudo in your pseudo code.
You're doing some things that don't make sense to me. Like getting polygon index #s and comparing them to the edge point's index #. And that doesn't make sense to me.
Code:
//Get the internal point index within the (quad) polygon of the shared point for(i = 0; i<3; i++) { if (poly[i] == edgePointIndex2) //<---How does this return poly point indices? { polyPointIndex = i; break; } }


Then you've got this code. Which seems like the most important part of the code. Which get's the Vector direction for the Left&Right Edges.
Code:
leftEdge = (points[poly[polyPointIndex - 1]] - edgePoint2).GetNormalized(); rightEdge = (points[poly[polyPointIndex + 1]] - edgePoint2).GetNormalized();

I don't understand how this code works. And I can't get that far in my code to test it. Because the polyPointIndex loop does not return the expected points inside the neigboring polygons.


This is what I've got so far.
-I get the selected edge
-I get the two points in the selected edge
-I get the neighboring polygons that the second point in the selected edge belongs to.
But then I'm stuck. And I can't get the points in the neighboring polygons using your code.
So I never get to that part of the point where I compare the selected edge the left&right edges.

My Code:
Code:
PolygonObject *obj = (PolygonObject*) doc->GetActiveObject(); if(!obj || obj->GetType() != Opolygon) return FALSE; CPolygon *polygons = obj->GetPolygonW(); Vector *points = obj->GetPointW(); Neighbor nbr; if(!nbr.Init(obj->GetPointCount(), obj->GetPolygonW(), obj->GetPolygonCount(), NULL)) return FALSE; //Get the selected edge's point index numbers LONG edgePointIndex1 = NULL; LONG edgePointIndex2 = NULL; BaseSelect *esel = obj->GetSelectedEdges(&nbr,obj->GetEdgeS()); LONG seg=0,a,b; while(esel->GetRange(seg++, MAXLONGl, &a, &b)) { for(LONG i=a; i<=b; ++i) { edgePointIndex1 = i; edgePointIndex2 = i+1; //GePrint( LongToString(edgePointIndex1) + " " + LongToString(edgePointIndex2) ); } } BaseSelect::Free(esel); //Get the positions of the two points in the selected edge Vector edgePoint1 = points[edgePointIndex1]; Vector edgePoint2 = points[edgePointIndex2]; //GePrint( RealToString(edgePoint1.x) + " " + RealToString(edgePoint1.y) + " " + RealToString(edgePoint1.z)); //GePrint( RealToString(edgePoint2.x) + " " + RealToString(edgePoint2.y) + " " + RealToString(edgePoint2.z)); //Get the direction the selected edge is pointing in Vector edgeDirection = (edgePoint2 - edgePoint1).GetNormalized(); //GePrint("Edge Direction = " + RealToString(edgeDirection.x) + " " + RealToString(edgeDirection.y) + " " + RealToString(edgeDirection.z)); //Get the polygons attached to the second edge point LONG *neighborPolys = NULL; LONG neighborPolyCount = NULL; nbr.GetPointPolys(edgePointIndex2, &neighborPolys, &neighborPolyCount); //Get the neighbor polygons and their points LONG nbrpolys = NULL; LONG polyPointIndex = NULL; for(LONG i=0; i<neighborPolyCount; i++) { //Get the index numbers for the neighboring polygons around the second edge point nbrpolys = neighborPolys[i]; //GePrint(LongToString(nbrpolys)); //Get the internal point index within the (quad) polygon of the shared point for(LONG j=0; i<3; i++) { neighborPolys[j] = polyPointIndex; //<---This makes no sense to me? //GePrint("nbr Point index's = " + LongToString(polyPointIndex)); if(neighborPolys[j] == edgePointIndex2) { polyPointIndex = i; break; } } GePrint("Shared Point = " + LongToString(polyPointIndex)); //Always returns zero!! }



-ScottA
__________________
My Gallery
 
Old 07-13-2014, 03:10 AM   #9
Per-Anders
helper bunny
 
Per-Anders's Avatar
CGTalk Forum Leader
portfolio
Per-Anders Edwards
Developer
The Third Party
USA
 
Join Date: Sep 2002
Posts: 12,712
Hi Scott. I'll do my best to answer your questions.

With regards your first two questions it's possible that you're not aware that the CPolygon offers you array subscript operator access to it's points for several Cinema versions in addition to the more traditional direct .a, .b, .c and .d access. So myPolygon[1] is the same as myPolygon.b. Hopefully that should clear up your first two points.

Looking at your own code perhaps you need a refresher in the way selections are stored. For example this piece of code will not work or give you the result you are after :
Code:
while(esel->GetRange(seg++, MAXLONGl, &a, &b)) { for(LONG i=a; i<=b; ++i) { edgePointIndex1 = i; edgePointIndex2 = i+1; //GePrint( LongToString(edgePointIndex1) + " " + LongToString(edgePointIndex2) ); } }


Within Cinema edge indeces are stored as the polygon index * 4 + edge within polygon. See the SDK docs for this e.g. PolygonObject::GetEdgeS().

To retrieve actual point indeces from the edge selection you must retrieve the polygon
Code:
Int32 polygonIndex = edgePointIndex / 4;

Then the edge itself, the simplest way as it's always from 0-3 is to use a bitmask i.e.
Code:
Int32 edgeIndex = edgePointIndex&3;

And finally you retrieve the two point indeces from this thus
Code:
const CPolygon* polys = object->GetPointR(); Int32 firstEdgeIndex = polys[polygonIndex][edgeIndex]; Int32 secondEdgeIndex = polys[polygonIndex][edgeIndex + 1];

Q: Why can you be so cavalier about the addition? A: Because the array subscript operator for the CPolygon has been designed to allow such abuse and uses the modulus of the passed index and the point point to return the correct corner point index.

Q: Why pass the edge index to the polygon? A: Because the edge index directly relates to the polygon index and is always made up of the two points poly[edge] and poly[edge + 1].

My psuedo code example wasn't very pseudo, you really only need to swap out the for loop calls and feed it the correct initial inputs and it should give you a rough result.

Every application has a different set of internal data structures and accessors, so this is not going to be transportable code. However hopefully this answers your questions with regards the specifics of the Cinema plugin for you.
__________________
The Third Party | Homepage | My Reel
"You need to know what you're doing before you start, and to start because you need what you're doing."
 
Old 07-13-2014, 03:48 PM   #10
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
Yeah. I discovered that yesterday. And I've been going crazy trying to solve it.
I got that code from Matthias Bobber on the cafe years ago. And I've been posting there for help.
So far I haven't gotten an answer.

I really appreciate your help. But I need to see an actual working example of how to get the points of a selected edge. Because your examples are missing things that I can't figure out how to write. You're using generalizations in your code examples like this:
Code:
Int32 polygonIndex = edgePointIndex / 4

And I have no idea where you're getting edgePointIndex from?

And this makes no sense to me either: const CPolygon *poly = obj->GetPointR();
That will not compile.

What I need is an actual working example of getting the points of the selected edge that I can paste into VS and run. So I can step through it and see how it's done from start to finish.
Maybe I'm a strange person. But I just can't comprehend things when it's written with words like this.
I need to have working code that I can step through and make notes in.
That's the only way I can comprehend this stuff. Words just confuse me.

-ScottA
__________________
My Gallery
 
Old 07-13-2014, 07:30 PM   #11
Scott Ayers
Kaiju Creator
Scott Ayers
USA
 
Join Date: Feb 2005
Posts: 988
Never mind.
I managed to figure it out with some Python code I had in my notes:
This is a working example that gets the points from selected edges:
Code:
PolygonObject *obj = (PolygonObject*) doc->GetActiveObject(); if(!(obj && (obj->GetType() == Opolygon))) return FALSE; BaseSelect *EdgeS = obj->GetEdgeS(); if(EdgeS->GetCount() < 1) return FALSE; //The number of edges = the number of polygons * 4 LONG maxEdgeCnt = obj->GetPolygonCount()*4; CPolygon *polygons = obj->GetPolygonW(); BaseSelect *PointS = BaseSelect::Alloc(); GeDynamicArray<LONG>EdgeInd; for(LONG i=0; i<maxEdgeCnt; i++) { if( EdgeS->IsSelected(i) ) { //GePrint(LongToString(i)); EdgeInd.Push(i); } } for(LONG i=0; i<EdgeInd.GetCount(); i++) //For each element in the EdgeInd array { LONG edge = EdgeInd[i]; LONG PolyInd = int(edge/4); LONG PolyEdgeInd = edge-4*(PolyInd); CPolygon Polygon = polygons[PolyInd]; //Store the selected points in memory in the "PointS" BaseSelect array if( PolyEdgeInd == 0) { PointS->Select(Polygon.a); PointS->Select(Polygon.b); } else if( PolyEdgeInd == 1) { PointS->Select(Polygon.b); PointS->Select(Polygon.c); } else if( PolyEdgeInd == 2) { PointS->Select(Polygon.c); PointS->Select(Polygon.d); } else if( PolyEdgeInd == 3) { PointS->Select(Polygon.d); PointS->Select(Polygon.a); } } //Select the points using the PointS array PointS->CopyTo(obj->GetPointS()); //Free the memory used BaseSelect::Free(PointS); EdgeInd.FreeArray();


I need to see actual working compilable code like this in order to learn how to do new things I've never done before.
I don't know why. But words and pseudo code just get me confused.

With that problem solved. I have to try once again to figure out how to select the neighboring point in a specific direction.

Thanks a lot for your help Anders,
-ScottA
__________________
My Gallery
 
reply share thread


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
CGSociety
Society of Digital Artists
www.cgsociety.org

Powered by vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

All times are GMT. The time now is 07:01 PM.


Powered by vBulletin
Copyright ©2000 - 2016, Jelsoft Enterprises Ltd.