Find visual center of contour/polygon


#21

continue means continue the while loop… but “continue” slows down MXS code and I changed it to:

if (currCell.data.z - bestCell.data.x > precision) do < refine cells > ...

#22

In this case why this check is performed in the while loop?
If this is true the while loop stops?
if (cell.max - bestCell.d >= precision) continue;


#23

no…

originally was:
if d < precision continue loop without refine, if d > do refine

i changed to:

if d > precision do refine, if not skip refine and continue while

I do the same but don’t use continue because it’s slow in MXS

the comments should be changed to:
drill down if there’s a chance of a better solution :upside_down_face:


#24

Yes, in your code. I was asked about the js code where I can’t see when the while loop stops(my js skills are exactly 0). So, I thought that that line stops the loop. Because of this my version of the code works faster than yours - it stops the while loop the first time when the (cell.max - bestCell.d <= precision) is true. Now I have to fix it. :slight_smile:

By the way, you are using expandToInclude which is

    NEW in 3ds Max 2022:: Expands the Box3 value to include the argument value.

Methods

contains <Box3> <Point3>
Returns true if the Point3 value is within the bounds of the Box3 volume.

empty <Box3>
Resets the Box3 value to an “empty” state with meaningless min and max values.

enlargeBy <Box3> <float>
Enlarges the Box3. A Point3 is created from the float f as Point3(f,f,f) and added to min and subtracted from max. If the box is 'empty', the Box3 is centered at (0,0,0) and then enlarged.

expandToInclude <Box3> (<Box3> | <point3> | <point3 array>) transform:<matrix3>
Enlarges the Box3 to include the specified argument value. The transform argument only applies if the value passed is a point3 array, and is applied to the elements of the array.

#25

don’t trust the documentation. Box3 was added in MAX 2015 (but kept secret :wink:)


#26

:joy:


#27

we can change to:

		fn makeBBox points = 
		(
			b = box3()
			expandToInclude b points -- where points is an array
			b
		),

#28

the JS code is:

    while (cellQueue.length) {
        // pick the most promising cell from the queue
        var cell = cellQueue.pop();

        // update the best cell if we found a better one
        if (cell.d > bestCell.d) {
            bestCell = cell;
            if (debug) console.log('found best %f after %d probes', Math.round(1e4 * cell.d) / 1e4, numProbes);
        }

        // do not drill down further if there's no chance of a better solution
        if (cell.max - bestCell.d <= precision) continue;

while is going until cellQueue has items, where cellQueue.pop() pops top item and shrink the list…


#29

Yes, now it is clear. Thank you. I though that this means that the loop has to be stopped, but… :slight_smile:
// do not drill down further if there's no chance of a better solution


#30

is the routine “alignment” dependent ? as local values give different result to world values. Perhaps not, strange things going on :slight_smile:


#31

quite a fun routine… the original c++ works on polys with holes (any other poly after the “first”)… could possibly use if for some kind of mapping layout tool.

this was a rectangle with a few shapes drawn in it and the when the new point of inaccessibility found an new shape drawn round that and repeat


#32

Denis, I have found something strange.
2021-10-14%2016_53_44
The yellow point is created from the first code which you posted.
The red line is created from the last code.
Here is the same spline as an fbx file(saved in max2020): https://drive.google.com/file/d/1HPGhEfTQMzLGcjtPjHNLppfTBdXWNrmL/view?usp=sharing


#33

Serejah, thank you for this site. :slight_smile:

I have pasted the coordiantes of the points of the spline in my previous post, but the result which the code calculates is not as expected. No matter if I use the world or the local coordinates of the knots the returned result is far from the expected one. I know the reason is in the code. Maybe I will try some of the other c# implementations to see what will happen.


#34

my MXS version works the same way. It was ported from c++


#35

I told above that the ring (array of spline points) must be closed for last version. It’s much faster for MXS to not do condition in loops.
Closed - means that the first point is added to the end (duplicated).


#36

i can’t import this file for some unknown reason… i use max 2016


#37

here it is as a 2010 max file

shape.max (184 KB)


#38

Oh, yes. Now it works as expected.

ptsArr = for k = 1 to numKnots myPolygon 1 collect 
		(
			kPos = getKnotPoint myPolygon 1 k
			[kPos.x, kPos.y,0]
		)
		append ptsArr ptsArr[1]
polygon = #(ptsArr)

By the way, if I use precison=0.1 and the while loop is stopped when the currCell.data.z - bestCell.data.x > precision is true for the first time, the result is almost the same as when the while loop is not stopped(this is valid for all the polygons I tested). With precision=1 the situation is not the same and the while loop must not be stopped.


#39

I have a question about this while loop.

qsort cells cellSorter
			while cells.count != 0 do
			(
				-- pick the most promising cell from the queue
				
				currCell = cells[cells.count]
				cells.count = cells.count - 1

				-- update the best cell if we found a better one
				if (currCell.data.x > bestCell.data.x) do
				(
					bestCell = currCell
					if (debug) do format "found best % after % probes... precision:%\n" currCell.data.x numProbes precision
				)

				-- do not drill down further if there's no chance of a better solution
				if (currCell.data.z - bestCell.data.x > precision) do
				(
					-- split the cell into four cells
					h = currCell.data.y/2.0
					append cells (makeCell [currCell.center.x - h, currCell.center.y - h, 0] h polygon)
					append cells (makeCell [currCell.center.x + h, currCell.center.y - h, 0] h polygon)
					append cells (makeCell [currCell.center.x - h, currCell.center.y + h, 0] h polygon)
					append cells (makeCell [currCell.center.x + h, currCell.center.y + h, 0] h polygon)
					numProbes += 4
					
					qsort cells cellSorter  -- !!! only here.
				)
			)

I still wonder why the while loop must not be stopped when (currCell.data.z - bestCell.data.x < precision) is true.
Sorting the cells always forces the while loop to check the most promising cell first. Lets say that after 10 iterations we have the first 3 cells with the same maxDistance, for example 5.3.
The while loop will pick the first cell(of these 3 cells) and when its find that the (currCell.data.z - bestCell.data.x < precision) is true, why we have to check the next cells and to divide the first cell to 4 new cells?

If we divide the first cell to 4 new cells, the maxDistance of each of these 4 new cells has to be less than the maxDistance of the first cell.

If the while loop is not stopped and it picks the second cell(from these 3 cells), it will compare the same values as in previous iteration(it has the same maxDistance as previous cell) and again the (currCell.data.z - bestCell.data.x < precision) will be true. The same will happen with the other 1 cells: (currCell.data.z - bestCell.data.x < precision) will be true.
These 3 cells are the best candidates and they have the same maxDistance. The maxDistance of each one of all other cells is less than the maxDistance of the first best candidate.
In this situation we will have 3 points which will be the centers of the 3 largest inscribed circle in the polygon, and these 3 circles will have the same radius. So, which one of these 3 points will be used as a final result does not matter.

I have tested several polygons and the numProbes: are the same when the while loop is not stopped and when it is stopped the first time when the (currCell.data.z - bestCell.data.x < precision) is true, and the bestCell is always the same. Maybe with proper polygon there will be significant difference between stopped and non stopped while loop.

=======

@Klvnk can you test your c++ version with this shape: https://drive.google.com/file/d/1KfKzjcnb7d-RskR6pQqT54LVELEHqk_m/view?usp=sharing

With precision set to 0.1 the js ported code(with almost all improvements from the Denis’ last version of the script) I have this result:
numProbes: 16750
best distance: 162.478
precision:0.1 time:56803 heap:80946052L

With the last code from Denis:
num probes: 16750
best distance: 162.478
precision:0.1 time:443424 heap:262513116L

With precison = 1.0
JS version:
numProbes: 2422
best distance: 162.478
precision:1 time:1535 heap:11663264L

Denis version:
num probes: 2422
best distance: 162.478
precision:1 time:8332 heap:1278508L


#40

no probs i get this…

a slight deviation I have my xml format for handling max shapes if you’re interested…
xmlshape.ms (6.6 KB)
it’s an importer/exporter I never particularly liked any other of the “factory” options in max.