PDA

View Full Version : "Make Polygon" still doesn't work as expected - Anyone ?



Weetos
12-26-2007, 03:58 AM
Okay, it's been a long time now, 'Make polygon' has been refined and all and I'm still experiencing problems using it - oh and no and I'm not trying to make polygons out of trillions of points - just four - yes just 4 co-planar points - How hard is that ?

So I lasso select four points of my model, all lying on a same plane, press 'p' and BAM, I get this lovely 180° twisted polygon. CTRLZ and I use the 'old' 'Make Polygon' - Same result - Why 2 tools that are supposed to perform the same task, when none is reliable ?

Is it that hard to make a tool that works like expected ? yeah I know I could select the point clockwise one by one - But I don't care, I want a tool that works with lasso selections - Since NT doesn't seem to want to fix this, is there anyone that knows about a third party plugin that can do rocket-science things like generate valid polygons out of four points?

Thanks for any suggestion

Using 9.3.1, by the way

voriax
12-26-2007, 05:32 AM
As far back as I remember, Make Poly has always worked the same way .. clockwise selection of a set of points. Sometimes you'd get lucky with a lasso and it would create the poly the way you wanted based on it, but usually you had to manually select them.
It would be nice, however, if LW had a smartness about it that would automatically know how to make a poly based on a lasso selection.

Nangleator
12-26-2007, 07:43 AM
IIRC, a lasso select really selects the points in the order they were originally created. There are some cases where it's safe to use it. One of the Proton vids shows him grabbing 24 or so points around a cylinder and it worked fine. I guess "create disk" and other primitives tools create useful point orders.

It's when you're in the middle of a model and grab some points at random that the problems come in. With only four points, I'd say you had a 50% chance of that lasso working right.

Maxx
12-26-2007, 05:20 PM
Weetos - Check to see if your 'p' key is mapped to "Make Polygon" or "Make Poly". I think Make Poly works as you're suggesting, but Make Polygon doesn't.

mccabejc
12-26-2007, 06:06 PM
Yeah, the clockwise bit has always been a bit ludicrous. Though I'm not sure how tough it is to "fix" that. But geesh, if it's do-able I wish they'd do it.

Weetos
12-27-2007, 07:44 AM
Thanks guys for your input

Maxx> actually I tried both, and it sometimes works, but I'd like a tool that works in every occasion

I also tried 'Perspicacious Polygon' from faulknermano (http://thespread.ghostoutpost.com/_theoldspread/index.htm but it gives the same result. I looked for some other 3rd party solution, in vain.

I just can't believe this is so complicated to code - I guess the other 3D packages can manage this, so why LW wouldn't?

I fired up my favorite text editor and I tried to manage this using LScripting, and I came to the conclusion that (as Nangleator said) a lasso selection takes the initial points ID into accounts, so you need to reorder the selected points before attempting to create the polygon. After several attempts, I realized I need to inject some maths in there, in order to be able to generate a clean polygon out of 4 points.

Now the question is, what are the algorithms needed to perform such an operation ? I'm going to try to figure this out :stumped:

Hopper
12-27-2007, 12:43 PM
Now the question is, what are the algorithms needed to perform such an operation ? I'm going to try to figure this out :stumped:
Not knowing an abundant amount of LScript syntax, but being a programmer, the logic would be simple.

You have an array of points. (selection list)
Each point having an ID that is generated in order as they are created.
Using a simple sorting routine (selection, bubble, etc..), sort the selection list by ID (ascending) and perform the create poly function on the new selection list.

Again, not being familiar with LScript syntax, I don't know if an array type construct is available, but there are many ways around this. One being to create the same series of points in an unused layer (sorted of course), creating the poly, then cutting the original and pasting in the new poly. Just make sure to merge points as the final operation.

I will look into the LScript syntax when I get home. Maybe I can post some code. Sounds like a good challenge.

-Cheers.

Hopper
12-27-2007, 01:08 PM
Ok. I missed the boat on that one. I just realized the problem was not the ID order because the lasso tool would basically do that already. Plus the fact that Weetos already stated that. duh... :thumbsdow

So would it make sense to incorporate a "next closest" point function that ignores a point you have already added to your array? Then add each point based on closest proximatey? Or next closest selected point on the next adjoining edge? (if there are any edges that is)

IgnusFast
12-27-2007, 01:38 PM
Wow, I never thought about it, but that's a pretty tricky wicket. My first thought was to edge walk, but what if it's not a closed edge loop? Or just 4 disconnected vertices?

If they all share 1 axis and aren't expected to be a concave shape, they should be able to figure it out mathematically. Pick an arbitrary start point, then walk the list and sort by next-closest. Maybe they're already doing something like that? Only problem is that could flip points on rectangles or capsules with long sides, though. They'd probably have to then look for overlapping vectors and make sure none of them cross; if they do, then they have to do additional sorting.

Or could you again start with an arbitrary vertice in the list, then follow directional rules to walk them, always trying to go in a clockwise direction? Start with one, then look right and up. If nothing fits, then try right. Found the closest one to the right? Okay, now look right again. Nothing? Look right and down. Always start with the same direction, and keep going until you've looped and are out of points. If you're not out of points and you've gone all the way around, you'd have to branch the opposite way from where you were going and keep casting out.

ie, yuck. :) The circular selection requirement is actually fairly reasonable, though a pain in the arse. If you go backward, you have to flip the poly because it assumes a clockwise normal.

Weetos
12-27-2007, 01:55 PM
Wow, Thanks guys :) Nice to see you're interested in my problem

Okay, here's what I have got so far : it seems to work fine on my side, the only drawback is that you may have to flip the generated polygon

If you guys have any tips concerning optimization of this script, feel free to post your suggestions :)


// mkquad.ls By Weetos
// My first attempt at Lscripting so please bare with me :)
//
// This basicaly make a quad out of four selected points, whatever the order

@version 2.4
@warnings
@script modeler
@name MakeQuad
main
{

selmode(USER);

numPts = pointcount();
if(numPts != 4) {
error("you must select 4 points !");
return;
}

for(i = 1; i < 5; i++) {
editbegin();
myquad = createquad(i);
// if myquad_integrity is close to 0 we have a non valid poly
myquad_integrity = round(vmag(polynormal(myquad)),6);
editend();

if ( myquad_integrity == 0 ) { // non valid poly, we need to remove it
editbegin();
del_poly = rempoly(myquad);
editend();
} else {
return;
}

}

}

createquad: mode {
switch(mode) {
case 1:
pointarray[1] = points[1];
pointarray[2] = points[2];
pointarray[3] = points[3];
pointarray[4] = points[4];
break;
case 2:
pointarray[1] = points[1];
pointarray[2] = points[2];
pointarray[3] = points[4];
pointarray[4] = points[3];
break;
case 3:
pointarray[1] = points[2];
pointarray[2] = points[1];
pointarray[3] = points[3];
pointarray[4] = points[4];
break;
case 4:
pointarray[1] = points[4];
pointarray[2] = points[2];
pointarray[3] = points[3];
pointarray[4] = points[1];
break;
}
return(addpolygon(pointarray));
}

Hopper
12-27-2007, 02:14 PM
From the code, it seems you are only interested (at least for testing) in only creating a quad and not a poly with N sides. Is this true? If so, it makes for a less complex solution I'm sure.

art
12-27-2007, 02:29 PM
For convex polygons it should be fairly easy to determine the order of points, given a random set. However, if the polygon is concave and it is not attached to any other geometry the point order could be ambigious as shown in the attached picture. If such concave polygon is attached to other geometry you could probably use the surrounding polygons to determine the right point order. Surrounding geometry can also be used to determine the normal of the polygon.
Can we actually use the array of sorted point IDs? What if the points were created in random order, or turn out that way if the object is complex enough?

Weetos
12-27-2007, 02:35 PM
You're right HopperZ, This code is aimed at creating valid quads, but I'd be also interested in having the ability to create Ngons - unfortunately the crappy method I used in that script isn't suitable for more vertices, since it has to try each vertices combo until the generated polygon has a valid normal

If you have any idea about a more effective way of doing this, please don't hesitate - given that my Lscript knowledge is more than limited

Dexter2999
12-27-2007, 03:13 PM
I stopped coding before some on this board were born....and I have forgotten most of it.

Art has a point in his illustration that simple math isn't going to always answer this because the formula may assume to connect points by an increasing x/decreasing y moving clock wise...or a decreasing y/increasing x value where the wrong variable is taking precedence in the desired order..
the variable taking precedence can alter the point order obviously.
Even doing a formula to measure the distances to determine the closest point to make it the next in order in a formula will often produce a flawed complex poly.

The preference of precedence can change value in different parts of the same shape.

The quad formula should be doable though.

Red_Oddity
12-27-2007, 03:42 PM
When you would work in 2 dimension you could work it out by first checking whether or not vectors between points cross eachother, if so, they don´t belong along eachother inside the creation array, should a poly turn out to be concave you could also check for the final crossing vectors the distance between the points and have it connect the closest point.

The 3rd dimension however complicates this process alot, not to mention when user the selects the order him/her self and wants some funny shaped poly and your algorithm keeps breaking that selection preference.

Weetos
12-28-2007, 02:24 AM
For convex polygons it should be fairly easy to determine the order of points, given a random set. However, if the polygon is concave and it is not attached to any other geometry the point order could be ambigious as shown in the attached picture. If such concave polygon is attached to other geometry you could probably use the surrounding polygons to determine the right point order. Surrounding geometry can also be used to determine the normal of the polygon.


As you stated a given set of points can generate different valid polygons - That's why I tried to stick to the quad problem, which was the main purpose of this thread. Concerning the evaluation of the surrounding geometry in order to determine the normal, I have to dig into this :)

My purpose here is to get a tool that works with lasso selection as described below:

user selects a set of vertices and press 'p'
if there's four points selected, MakeQuad (my script) is used
if there's more or less than four, the vanilla 'Make Poly' tool is used instead


Of course, I have to find a way to determine the *right* normal so it can be totally transparent to the user

zardoz
12-28-2007, 04:02 AM
what if selecting a set of points, this 'make polygon' tool finds the center of these points (in a certain ortographic view) and then rotates a vector from this center to each point (clockwise or anticlockwise) and then creates the polygon? this would not be flawless but I guess it would work ok in some cases...
and what about other software? do they have the same problem?

art
12-28-2007, 07:30 AM
what if selecting a set of points, this 'make polygon' tool finds the center of these points (in a certain ortographic view) and then rotates a vector from this center to each point (clockwise or anticlockwise) and then creates the polygon? this would not be flawless but I guess it would work ok in some cases...
and what about other software? do they have the same problem?

Inspired by this thread I wrote a small script yesterday evening that does something like that. It uses average as the center, not a true centroid but in many cases thats sufficient (and faster). The script works in most common cases, but I bet that concave polygons can make it do stupid things. One problem is that it can create flipped polygons. Given a set of points it is not obvious which way is clockwise. I just realized now that I could add one last scan of the new polygon and look for any consecutive point IDs. If they are flipped, the polygon is probably flipped too.
I can post it if anyone is interested.

zardoz
12-28-2007, 09:42 AM
Originally Posted by art
One problem is that it can create flipped polygons. Given a set of points it is not obvious which way is clockwise.
yep I imagined that this would make the polygon flipped (or not).



Originally Posted by art
The script works in most common cases, but I bet that concave polygons can make it do stupid things.
I also imagined that this would be a problem but like you said before this could lead to several possibilities. One would be the right one. Is there a way to have it create a polygon and if that's not what we want, tell it to make the polygon again excluding the previous attempt(s)?

art
12-28-2007, 11:43 AM
I tried selecting the new polygon plus all connected geometry (can we use "grow selection" in lscript?) and then running alignpols function, but it still leaves flipped polygons sometimes.

Weetos
12-28-2007, 01:25 PM
I can post it if anyone is interested.

yep I am :) - if you don't mind, of course


Is there a way to have it create a polygon and if that's not what we want, tell it to make the polygon again excluding the previous attempt(s)?

I guess it is possible by inserting a requester that pauses the execution of the script, asking the user if the current solution is acceptable or not

art
12-28-2007, 02:41 PM
Not a perfect solution, but here it is. If anyone improves it, I'd be glad to see.

art
12-28-2007, 05:10 PM
I've found a bug in the logic. I wrongly assumed that the next point would have a minimal angle from the previous one. That is not always the case. I'll try to fix it.

Dexter2999
12-28-2007, 07:54 PM
No matter what you do a shape that curls back on itself (think rotary saw blade) will give you fits unless the point order is determined by some other method than location.

art
12-31-2007, 02:53 PM
It is still far from perfect, but I think I fixed the bug from in the previous script. I'll probably stop here.

zardoz
01-01-2008, 04:00 AM
from the tests I did it works great art! The best 'create polygon' tool we have. I jittered lots of points and it works fine.

thanks for another great tool.

digefxgrp
01-01-2008, 05:58 AM
Years ago Ume (Pictrix) wrote me a custom lsc that allowed a Polygon to be created from any loop of points regardless of the point order in which they were originally created. It handled convex shapes pretty well. The reason I say “pretty well” is it would fail about 1 percent of the time. Even then, success would be achieved by doing the process over using a different start point. At the very worst there would be two adjacent points in the resultant poly that might be flipped. That was easily fixed by using the “Swap Points” plugin.
Unfortunately the script stopped working with 8.x. I never pursued the issue after first reporting the failure as I found alternate methods that work just as well in most cases. The only real advantage his script offered was the points didn’t have to be attached to polys. They could just be out there by themselves.

The way I asked him to write it was:
-Select two (or more) points right next to each other to designate direction.
-If there were tricky (convex) areas, you could select additional points in those areas to help “guide” it along it’s path.

I’ll contact him again and see if he might be willing to resurrect the old script.

digefxgrp
01-01-2008, 07:13 AM
This looks to be interesting. It a script that's called "Beeline Select".

http://blogs.yahoo.co.jp/max3dc/36710300.html

However I couldn't download the script and since the page is all Japanese I have no idea what's going wrong.:stumped:

Weetos
01-01-2008, 07:48 AM
hmm Looks like a 404 error, according to the google translator :
http://www.google.com/translate?u=http%3A%2F%2Fwww.geocities.jp%2Fcoordi nates_3d%2Flscripts%2Fstop&langpair=ja%7Cen&hl=en&ie=UTF8

Not sure if this tool is available elsewhere ?

art
01-02-2008, 08:18 AM
from the tests I did it works great art! The best 'create polygon' tool we have. I jittered lots of points and it works fine.

thanks for another great tool.

no problem, I'm glad I could help :)

THREEL
01-02-2008, 09:08 AM
Nice job art! :thumbsup: Personally, I'm going to be assigning a shortcut key to this cool Lscript.

tHANX!

tHREEL, but you can call me AL.

zardoz
01-03-2008, 02:47 AM
assigning a shortcut key to this?? I replaced 'p' with this. lol

Weetos
01-03-2008, 06:23 AM
Yeah I assigned it to the shortcut 'p' as well :)

Great job, art ! Thank you so much for this :thumbsup:

PS: Sorry if I'm asking too much but I would just add to this a feature the NT already has, the ability to create a subpatched poly when the surrounding geometry is subpatched - but I don't really know how to implement this ?

art
01-03-2008, 07:31 AM
I'm not sure if I can detect subpatch state in lscript. Maybe an lscript guru could clarify that for us :)

THREEL
01-03-2008, 07:56 AM
Hi art,

Would it be possible to add some code to this to automatically split the several point poly into quads? I know absolutely nil about Lscripting, but this would be another cool Lscript.

tHANX!

AL

art
01-03-2008, 08:32 AM
I though about something like that after I saw this thread:
http://www.newtek.com/forums/showthread.php?t=74764
but I never spent much time on it. It's tougher than it looks at first.
Of course "quads-only" solution is not always possible, in a pentagon for example , etc.

THREEL
01-03-2008, 08:48 AM
I though about something like that after I saw this thread:
http://www.newtek.com/forums/showthread.php?t=74764
but I never spent much time on it. It's tougher than it looks at first.
Of course "quads-only" solution is not always possible, in a pentagon for example , etc.

I guess I'm thinking more along the line of polygons that are made from randomly placed points. For example: if you had 6 points, you'd end up with 2 quads. If you placed 8 points, you'd end up with 3 quads, etc...

I'm thinking of Make Poly/Split Poly on steroids, maybe?!

tHANX!

AL