Maxscript - Check if object convex?

Electro · Nov 2012

Hi there!

Im trying to detect whether or not an object is convex.
The idea was to dot each face normal against every other face normal to ensure theyre pointing away.
This is where I got with the script, bashing my head against the wall for quite a while now so I figured Id put the question out here.
If anyone already has an existing script that checks instead of using this and is willing to share, then that would be great too.

fn checkConvex obj =
(
    onumFaces = polyop.getNumFaces obj
 
    for f=1 to onumFaces do
    (
        normal_faceBase = (polyop.getFaceNormal obj f) --* obj.transform
        nv1 = normalize normal_faceBase

        --print("normal_faceBase: " + normal_faceBase as string)

        for g=1 to onumFaces do
        (
            -- avoid self
            if (f != g) then
            (
                normal_faceCompare = (polyop.getFaceNormal obj g) --* obj.transform
                nv2 = normalize normal_faceCompare
                --print("normal_faceCompare: " + normal_faceCompare as string)

                normalDot = dot nv1 nv2
 
                if (normalDot > 0) then
                    print("concave!")
 
                print("normalDot: " + f as string + "->" + g as string + " = " + normalDot as string)
            )
        )
    )
)

checkConvex $

Any and all help is really appreciated.
Cheers

akramparvez · Nov 2012

Check if the angle between adjacent faces is less that 180 then the object is not convex.
To get the angle between two faces calculate the dot product of the normals and then arc-cosine the value to get the angle.
Since the angle between two vectors(normals) cannot be more that 180. Calculate the cross of the normals and check if any value is less that 0. If it is less then add 180 to the result above to get the actual angle.

WarrenM · Nov 2012

In terms of math, a simple way to test for convexity is:

- for every plane in the mesh
     - for every vertex in the mesh
         - is vertex in front of the plane?
           - yes?  the object is NOT convex

I hope that's understandable in some way.

Electro · Nov 2012

Yeah agreed guys. Those are both good ways. Most likely to go with your way Warren.

It's just the values that max specifically seems to be feeding me are bogus. So if anyone can shed light on why that might be, the rest should be easy.

Norman3D · Nov 2012

If you have massfx or physx it has a set of maxscript functions that will do the work for you

<boolean>nvpx.IsConvex <node>inode

Here is more info.

WarrenM · Nov 2012

The values are bogus ... are they maybe in world space and need to be translated to local or something?

Electro · Nov 2012

Norman3D: couldn't get that to work, was just giving false positives (never managed to get it to return false.

Anyway, it would appear that the result of a dotproduct is always positive.
Thus making it useless.

Not exactly sure what to do about that. $:\$

monster · Nov 2012

nvpx.IsConvex works for me.

Electro · Nov 2012

Really?! I'd love for that 1 line solution to work for me.

Quick simple test. Obviously concave. Reports as true for:

nvpx.IsConvex $

$:\$

monster · Nov 2012

Ah, actually I have having the opposite problem. It always returns false. I had only tested concave objects previously.

It seems to be a caching issue. Whatever was first returned per object the answer will remain until the max file is reloaded. (I tried gc, but it didn't work.)

This is a terrible workaround, but it seems to work for me.

fn isObjConvex obj =
(
	m = obj.name
	holdmaxfile quiet:true
	fetchmaxfile quiet:true
	m = getNodeByName m
	nvpx.IsConvex m
)

isObjConvex $

Electro · Nov 2012

Yeah I see what you mean about the caching issue. I can't afford to do a hold and fetch, I'll be doing this operation hundreds of times

I just tried having it clone and collapse the object and running the operation on that instead, but it doesn't seem to want to update properly for physx to query (or even at all?!)

So I'm still back to needing dotproduct to actually work properly like in real code.

Got any more ideas?

marks · Nov 2012

I remember a conversation at work about baking AO to vertex colour -> clearly the whole mesh will be black if it's concave. Probably not too useful for a low-overhead validation check though.

Electro · Nov 2012

marks: not sure what you mean there regarding AO. AO is all about showing concave cavities.

Sigh... why must max be like this.

akramparvez · Nov 2012

Which version of 3ds Max are you using?
In Max 2011:
-- set the selection level to vertex
subObjectLevel = 1
-- selects the concave vertex
PolyToolsSelect.ConvexConcave 0.0001 1

Any version of Max(Tested in 2010 and 2011):
reactor.GetIsConvex $ 0 --True if convex else false

Electro · Nov 2012

Hi akramparvez, cheers for a couple of things to try and investigate.

I'm using Max 2012. Reactor is removed from it, so the 2nd option doesn't work.

With using that first method... imagine the image I had previously, with that sunken vertex actually flush level with the top face, so it's convex. It ends up selecting this vertex, so that isn't correct $:\$

akramparvez · Nov 2012

It works for me, I changed the value to 0.0 and it works fine.

Electro · Nov 2012

Ah yes, you're right. I assumed it needed a threshold so I just made it smaller before. Turns out the fix was to remove it completely like you said by making it 0.

Cheers

Here's a quick function I made out of it in-case anyone is interested:

fn isConvex obj =
(
	local convex = true
	
	-- set the selection level to vertex
	subObjectLevel = 1
	
	-- selects the concave vertex
	PolyToolsSelect.ConvexConcave 0.0 1
	
	if (obj.selectedVerts.count > 0) then
		convex = false
	
	-- back to object selection level
	subobjectLevel = 0
	
	return convex
)

convexity = isConvex $
print("convex: " + convexity as string)

Neox · Nov 2012

and while you are at it, is there a way to flip all (or better all in selected faces) invisible edges in a mesh to be convex? thats something i've been searching for years

Norman3D · Nov 2012

Neox wrote: »

and while you are at it, is there a way to flip all (or better all in selected faces) invisible edges in a mesh to be convex? thats something i've been searching for years

Hey Steffen, could you show me an example of what you mean?
I guess you mean the "triangulation" that happens in each poly. You want to keep it concave, right?

Neox · Nov 2012

Yeah a quad is made of 2 triangles, and there are 2 ways the inner edge, or inner triangulation can be made.
Often enough artists, especially beginners forget about this or don't care enough. What can happen is, jaggy silhouettes and all kinds of bad shading errors just because of the invisible triangulation.
The bad shading can befixed with normalmaps, but the silhouette can't be fixed that way.

Okay in a forseeable future this can be fixed with displacementmaps, but for now it would be great to have an easy solution, unexperienced artists or lazy people like me could use to fix those issues. In the end its maybe just 10 Minutes worth of work per asset, but it sums up. And unless its a gigantic amount of money, i'd pay for this as well

Norman3D · Nov 2012

Neox wrote: »

Yeah a quad is made of 2 triangles, and there are 2 ways the inner edge, or inner triangulation can be made.
Often enough artists, especially beginners forget about this or don't care enough. What can happen is, jaggy silhouettes and all kinds of bad shading errors just because of the invisible triangulation.
The bad shading can befixed with normalmaps, but the silhouette can't be fixed that way.

Okay in a forseeable future this can be fixed with displacementmaps, but for now it would be great to have an easy solution, unexperienced artists or lazy people like me could use to fix those issues. In the end its maybe just 10 Minutes worth of work per asset, but it sums up. And unless its a gigantic amount of money, i'd pay for this as well

I'm not sure having a concave "triangulation" would always be the "proper" way of doing it, right? Nowadays I'm focusing on tools mostly so I'm a bit rusty with modelling...
In Spec Ops for example, back when we were using the terrain actors instead of staticmeshes to create the dunes we had to "turn" some edges, making them convex in order to keep the silhouette of the dune. Other times the turning would need to be concave.
What I'm saying is that the idea sounds exciting at first, but the more I think about it the less sure I am it's a "global" fix.

Neox · Nov 2012

Thats why i said it would be better to apply it to a selection of polies, as opposed to a global solution

I mean i do characters most of the times and (i guess) pretty much 90% of the times i want the inner triangulation to be convex not concave. but maybe i'm wrong, but from my experience i spend way too much time flipping edges for better results

Norman3D · Nov 2012

Neox wrote: »

Thats why i said it would be better to apply it to a selection of polies, as opposed to a global solution

I mean i do characters most of the times and (i guess) pretty much 90% of the times i want the inner triangulation to be convex not concave. but maybe i'm wrong, but from my experience i spend way too much time flipping edges for better results

Hah! Good point! I will add this to my long to-do list, sounds like fun!

Maxscript - Check if object convex?

Replies