View Full Version : How to find the faces inside an outline ?

 prettyPixel10 October 2005, 12:42 AMLet's say I have an outline and I search the faces inside this outline. http://users.skynet.be/arketip/CGtalk/outline.gif I search a method or ideas... I'll be thankful for any answer.
stuh505
10 October 2005, 12:54 AM
Compute the averaged center of all the points in the circle.

Then calculate the distance of each circular point from the central point, and also calculate the angle that is formed by a ray extending from the center point to each outside point.

Then, go through all the verts on the shape...calculate the angle of the line from the center-point to that vert, and from this angle you know which line segment of the region you are dealing with....calculate the point on that line, and if the distance to that point is greater than the distance to the vertex then the point is within the selected region. Collect all the faces that have all 3 verts in the region

stuh505
10 October 2005, 01:00 AM
diagram

http://img484.imageshack.us/img484/9454/findin5ak.jpg
only prob is this is O(N) of the number verts in the object

Blue
10 October 2005, 01:28 AM
Concave outlines would complicate this. Is that a possibility?

prettyPixel
10 October 2005, 01:30 AM
Interesting method based on the distance.
I think this kind of method has a problem: what does it occur if the form is concave ?

Maybe It exists methods completely different ?

thomas: exact....

prettyPixel
10 October 2005, 01:42 AM
We can find the faces of the outline.
It is easy : something like this:
polyOp.getFacesUsingEdges \$ outlineEdges

But this collect the faces inside and outside....
The first problem is to select only the faces inside. How to do that ?
After that, a routine could fill the last faces.

stuh505
10 October 2005, 01:59 AM
The matID fill plugin in my signature does this. All you have to do is select one face that's inside, and then get all the adjacent faces. Then remove any faces that are outside the border. Continue this process until you aren't selecting new faces.

eek
10 October 2005, 02:49 AM
Well a dirty hack could be to make a tmp shape do a 0.1 extrude of the shape, then collapse that extruded face and read the face count, then delete the tmp shape.

eek

Blue
10 October 2005, 06:41 AM
stuh505: how to get that one face? imagine the outline is not a simple convex shape.

eek: what if the geo is not flat, what does the 0.1 extrude do? what does knowing the face count do?

My thoughts were not far from eeks as far as using a temp object to get internal faces.

generate the linear spline from the outline
generate a mesh from the spline with sufficient volume to pass through the souce geo in the area of the selection
use a volume select mod to select the faces that are within the temp mesh geo
This is a hack as well, but it's all I have at the moment :) More thinking to do to get a proper answer.

Things that could make this more complicated would be geo that loop back on themselves like a torus, outlines that loop, outlines that overlap but dont self intersect, outlines that have an average normal that is not up in Z, if there is more than one contiguous outlines, and a few more that I'm sure I just haven't thought out yet.

eek
10 October 2005, 07:12 AM
Ok Blue,

eek: what if the geo is not flat, what does the 0.1 extrude do? what does knowing the face count do?

Ok, make a tmp shape, put an extrude modifier on it of 0.1, convert it to whatever (probably poly),collapse the extruded face, and do a \$.faces on the tmp. Append to an array and delete the tmp.

I wont matter whether the shape is off because the extrude is only 0.1.

If this a shapepoly, then its even simplier do an extrude of the face by 0.1 then collapse. Then you can do whatever you want with the faces. Get how many, etc etc You could do a make planar on the poly/mesh before extude as your only working with a tmp.

There's more ways of understanding convex/concave hulls and stuff - but i cant discuss it here.(nda)

eek

Blue
10 October 2005, 09:04 AM
There's more ways of understanding convex/concave hulls and stuff - but i cant discuss it here.(nda)

:)

I still don't understand your method eek, and I have no real idea of what the face count will do for you, it's not like the temp geo will have the same triangulation or even the same interior vert count.

prettyPixel: this should work on your example but it is a hack

DisableSceneRedraw
try(
polyOp.createShape \$ #selection name:"tempSplineShape"
max create mode
\$tempSplineShape.pos.z = \$tempSplineShape.pos.z - 10
addModifier \$ (Vol__Select level:2 volume:3 node:\$tempSplineShape) ui:on
subobjectlevel=4
max modify mode
selectedFacesList = \$.modifiers[1].GetSelection #Face node:\$
max create mode
polyOp.setFaceSelection \$ selectedFacesList
delete \$tempSplineShape
deleteModifier \$ 1
deleteModifier \$ 1
max modify mode
subobjectlevel=4
)catch(try(delete \$tempSplineShape)catch())
EnableSceneRedraw

eek
10 October 2005, 09:09 AM
ahhhahah i think were doing the same thing. Roughly speaking :thumbsup:.

gotta sleepp....cubic bsplines on brain.....

eek

prettyPixel
10 October 2005, 12:38 PM
Thank you for the answers !

I have a new idea:

1- Initially we select a face randomly. The face 1 for example.
2- We collect all the adjacent faces to this face, until the outline or the border of the object (the open edges). That is like the routine of Stuh but with 2 outlines.
3- We deduce the inverse selection. We thus have two selections of faces: internal and external.
4- A routine determines which is inside the outline : we can calculate the average of the distance between each face and the center of the outline. The one who has the smallest distance is probably the internal selection.

What do you think about that ?

Light
10 October 2005, 01:00 PM
Hey I have just added this feature to Orionflame, and it works great.

It might take a while before I post the code here as I have used alot of predefined fns of Orionflame. At least I will be sure to explain my method.

Thanks for the idea! :thumbsup:

Light

prettyPixel
10 October 2005, 01:53 PM
I am delighted that my idea was able to help you. :cool:

Here is my version.
If You know a means to optimize it, please let me know.

fn getFirstItem theBitArray = (for i in theBitArray do return i)

fn getContinuousFaces obj outlineEdges firstFace =
(
continuousFaces=#{}
facesToInspect=#{firstFace}
while facesToInspect.numberset!=0 do (
currentFace=getFirstItem facesToInspect
for thisEdge in adjacentEdges where ( (outlineEdges*#{thisEdge}).numberset==0 ) do (
newFace=(polyOp.getFacesUsingEdge obj #{thisEdge})-continuousFaces
continuousFaces+=newFace
facesToInspect+=newFace
)--for
facesToInspect[currentFace]=false
)--while
continuousFaces
)--fn

fn getEdgesCenter obj theEdges =
(
theVerts=polyOp.getVertsUsingEdge obj theEdges
theCenter=[0,0,0]
for v in theVerts do theCenter+=polyOp.getVert obj v
theCenter/=theVerts.numberset
)

fn getAverageDistMultiArea obj theFaces theCenter =
(
dist=0.0
for f in theFaces do ( dist+=(distance (polyOp.getFaceCenter obj f) theCenter)*(polyOp.getFaceArea obj f) )
dist/=theFaces.numberset
)

obj=selection[1]
outlineEdges=polyOp.getEdgeSelection obj

theFaces1=getContinuousFaces obj outlineEdges 1
theFaces2=#{1..polyOp.getNumFaces obj}-theFaces1

theOutlineCenter=getEdgesCenter obj outlineEdges
distMultiArea1=getAverageDistMultiArea obj theFaces1 theOutlineCenter
distMultiArea2=getAverageDistMultiArea obj theFaces2 theOutlineCenter

if distMultiArea1<distMultiArea2 then polyOp.setFaceSelection obj theFaces1 else polyOp.setFaceSelection obj theFaces2

subObjectLevel=4
max views redraw

For my function "getFirstItem" .. I am not sure that is the right means. Do you know an another means to get the first Item in a bitarray ?

Light
10 October 2005, 02:12 PM
Do you mean something like (bitArray as array)[1]?

I have tried your code in a few cases but it didnt work. It might be because of my selections.

Here is the video of Select Inside (http://www.orionflame.com/discover/3%20Selection/2%20Select%20Edges/30%20Select%20Inside/01.avi) I have added to the reference. Selects polygons inside a closed edge selection. If the edge selection is open and splits the model all along, it will select the polygons of one side.

I will give a break down of the code, but now it is quite late here and I should get some sleep. :)

Light

prettyPixel
10 October 2005, 02:14 PM
The last challenge : how to correct this error.

http://users.skynet.be/arketip/CGtalk/outlineError.gif

prettyPixel
10 October 2005, 02:30 PM
Do you mean something like (bitArray as array)[1]?
Unfortunately the conversion into an array is slower.
Oh That does not have any importance.

I have tried your code in a few cases but it didnt work. It might be because of my selections.
I don't know. With my function the outline must be closed. Otherwise nothing is selected. And the system based on the center might not work in 3D space.

Here is the video of....
Good work !

prettyPixel
10 October 2005, 02:56 PM
I tested the same examples as on your video without encountering problems.
When we select edges, we often select edges behind the object. We do not see them. That could be that.

Another thing: script will not function if there are dead faces in the object because I suppose that the faces are
#{1..polyOp.getNumFaces obj}

Blue
10 October 2005, 06:26 PM
Light: Video looks good, interested in your method :) does it work just as easily with concave selections and looping selections?

stuh505
10 October 2005, 06:56 PM
I don't know if anyone else has noticed the other thread where I mentioned a mouse tool that works like the Pelt mapping thing, but the idea was to make a select-inside function like this work much easier, to improve my original matID fill script...I still haven't got that mouse tool working though. Pretty pixel, you can determine which section to fill by using the section that uses the least amount of border edges of the object.

Light
10 October 2005, 11:35 PM
Light: Video looks good, interested in your method :) does it work just as easily with concave selections and looping selections?

Thanks alot! It works with concave selections. Looping selections like prettyPixel's second example?

Light

Light
10 October 2005, 11:35 PM
Unfortunately the conversion into an array is slower.
Oh That does not have any importance.

I don't know. With my function the outline must be closed. Otherwise nothing is selected. And the system based on the center might not work in 3D space.

Good work !

Thanks! I tried your method with narrow selections [a few polys], maybe that's the reason?

Light

Light
10 October 2005, 12:23 AM
Here is the break down:

1. Get current edge selection
2. Split It [with undo on]
3. Add new edges to #1
4. Get face elements of #1 [seperating unconnected elements]
5. Collect average center of #4
6. Get average center of #1
7. Undo
8. Select face elements whose average center is closes to #6

For #4, you can use Orionflame.getUnconnectedPolys faceList includeCrossPolys thisForm

IE: Orionflame.getUnconnectedPolys faceElements true bitArray

Light

prettyPixel
10 October 2005, 12:27 AM
Hi all

I removed the bugs of the script. I think that now it works in every case.
Even if there is only a single polygon!

Thank you for your ideas and specially Stuh: the new script is based at first on your last idea.
Light: effectively the previous version doesn't work in all case. You were right. In the previous version if an outline selection start from one border of the object to the opposite border, the selection was erroneous. That is corrected.

Now there is no more calculation of centre or distance in the script.
Just bitarray calculations and research of faces.
I have modified the part where I calculate the second selection as the inverse of the first because it does not work in some cases.
It is better.

http://users.skynet.be/arketip/CGtalk/outlineConcave.gif

fn getFirstItem theBitArray = (for i in theBitArray do return i)

fn getContinuousFaces obj outlineEdges firstFace =
(
continuousFaces=#{}
facesToInspect=#{firstFace}
while facesToInspect.numberset!=0 do (
currentFace=getFirstItem facesToInspect
for thisEdge in adjacentEdges where ( (outlineEdges*#{thisEdge}).numberset==0 ) do (
newFace=(polyOp.getFacesUsingEdge obj #{thisEdge})-continuousFaces
continuousFaces+=newFace
facesToInspect+=newFace
)
facesToInspect[currentFace]=false
)
continuousFaces
)

fn getOutlinesEdges obj theFaces =
(
faceEdges=polyOp.getEdgesUsingFace obj theFaces
openEdges=(for e in faceEdges where (((polyOp.getFacesUsingEdge obj e)*theFaces).numberSet == 1) collect e)as bitarray
)

fn getOutlineFaces obj outlineEdges =
(
theFaces=#{}
facesToInspect=#{1..polyOp.getNumFaces obj}
facesGroup=#()
while facesToInspect.numberset!=0 do (
currentFaces=getContinuousFaces obj outlineEdges (getFirstItem facesToInspect)
append facesGroup currentFaces
facesToInspect-=currentFaces
)
openEdgesGroup=for i=1 to facesGroup.count collect (getOutlinesEdges obj facesGroup[i])
numberOutlineEdges=for i=1 to openEdgesGroup.count collect (openEdgesGroup[i].numberset)
numberOutlineOpenEdges=for i=1 to openEdgesGroup.count collect ((openEdgesGroup[i]*outlineEdges).numberset)
if (amax numberOutlineOpenEdges==amin numberOutlineOpenEdges)
then ( theFaces=facesGroup[findItem numberOutlineEdges (amin numberOutlineEdges)] )
else ( theFaces=facesGroup[findItem numberOutlineOpenEdges (amax numberOutlineOpenEdges)] )
theFaces
)

obj=selection[1]
if classof obj==editable_poly do (
theFaces=getOutlineFaces obj (polyOp.getEdgeSelection obj)
polyOp.setFaceSelection obj theFaces
subObjectLevel=4
max views redraw
)

Light
10 October 2005, 12:36 AM
Hey prettyPixel,

Very nice code! :thumbsup:

Light

prettyPixel
10 October 2005, 01:02 AM
Here is a simplified version of the function getOutlineFaces.
Nevertheless the outline must be without error if not nothing will be selected...

Light, Thanks for the break down of the code ;)

fn getOutlineFaces obj outlineEdges =
(
theFaces=#{}
facesToInspect=#{1..polyOp.getNumFaces obj}
facesGroup=#()
while facesToInspect.numberset!=0 do (
currentFaces=getContinuousFaces obj outlineEdges (getFirstItem facesToInspect)
append facesGroup currentFaces
facesToInspect-=currentFaces
)
for i=1 to facesGroup.count do ( if ( ((getOutlinesEdges obj facesGroup[i])*outlineEdges).numberset == outlineEdges.numberset ) do theFaces=facesGroup[i] )
theFaces
)

Blue
10 October 2005, 02:05 AM
prettyPixel: nice solution :) , when I test this it gives the inverted selection, but it is fast none the less.

prettyPixel
10 October 2005, 08:50 AM
Hi Thomas

I'm interested. For the script which I write, I need a function which always gives the right selection. Especially not the inverse selection because this routine will be included in a script which will make several hundreds of selections... And this selections are deleted!
Could you reproduce the error and make a screen shot of your outline please ?
That's really important for me.

Blue
10 October 2005, 04:33 PM
After restarting max this morning I can't reproduce it on my test scene. If it does it again in a predictable way I'll share.

Blue
11 November 2005, 04:37 AM
Tried a few more configurations and the code seems to be rock solid for me now, I must have had some globals floating around that messed it up before. Way to go prettyPixel.

prettyPixel
11 November 2005, 09:24 AM
No problem Thomas.
I think that you created multiple outlines yesterday. The routine supports only a single outline at the same time. Otherwise the result can be unpredictable.

CGTalk Moderation
11 November 2005, 09:24 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1