New geom3.fromPointsConvex() from @platypii in pull request 1343

[Hermann-SW]

All Submissions:

• [x] Have you followed the guidelines in our Contributing document?
• [x] Have you checked to ensure there aren't other open Pull Requests for the same update/change?
• [x] Does your submission pass tests?

Note: please do NOT include build files (those generate by the build-xxx commands) with your PR,

Thank you for your help in advance, much appreciated !

This is followup pull request based on discussion in #1343.

This is script that can be used in npm run dev:

const jscad = require('@jscad/modeling')
const { geom3 } = jscad.geometries

function main() {
  let out = []
  for(x=-9;x<=9;++x)
    for(y=-9;y<=9;++y)
     for(z=-9;z<=9;++z)
        if (x*x+y*y+z*z <= 96)
          out.push([x,y,z])
   return geom3.fromPointsConvex(out)       
}

module.exports = { main }

New fromPointsConvex.test.js is more complex than previous (check faces and #edges), for $n=96$ instead of $n=5$:

const test = require('ava')

const { fromPointsConvex } = require('./index')

test('fromPointsConvex (listofpoints)', (t) => {
  let out = []
  for(x=-9;x<=9;++x)
    for(y=-9;y<=9;++y)
     for(z=-9;z<=9;++z)
        if (x*x+y*y+z*z <= 96)
          out.push([x,y,z])

  let obs = fromPointsConvex(out)
  t.is(obs.polygons.length, 170)
  t.true(obs.polygons.every((f) => ([3,4,8,9].indexOf(f.vertices.length) !== -1)))
  let c = [0,0,0,0,0,0,0,0,0,0]
  obs.polygons.forEach((f) => c[f.vertices.length]++)
  t.is(c[3], 120);
  t.is(c[4], 24);
  t.is(c[8], 18);
  t.is(c[9], 8);
  let edges2 = 336*2
  obs.polygons.forEach((f) => edges2 -= f.vertices.length)
  t.is(edges2, 0);
})

No easy test for (unique) #vertices (= #edges + 2 -#faces = 336 + 2 -170 = 168).

[Hermann-SW]

You just need to rename to fromPointsConvex.d.ts for the tests to pass. It needs to be .d.ts not .d.js.

Really? I tested and verified that new test works, so the x for "Does your submission pass tests?" was correct. Just tested again and it works (again):

hermann@j4105:~/OpenJSCAD.org$ npm test

@jscad/openjscad@2.0.0 test
...
@jscad/modeling:   ✔ geometries › geom3 › fromPoints › fromPoints: throws for improper points
@jscad/modeling:   ✔ geometries › geom3 › fromPointsConvex › fromPointsConvex (listofpoints) (233ms)
@jscad/modeling:   ✔ geometries › geom3 › fromToCompactBinary › toCompactBinary: converts geom3 (default)
...

Anyway I did the change you proposed in latest commit.

[Hermann-SW]

Locally 2 web testcases fail now ...

...
@jscad/web:   ✔ taps (3 taps) (554ms)
@jscad/web:   ✔ taps (3 taps) direct element (553ms)
@jscad/web:   ✖ zooms (from pinch) `t.end()` was never called
@jscad/web:   ✖ zooms (from pinch) direct element `t.end()` was never called
@jscad/web:   Unhandled rejection in src/most-gestures/gestures.test.js
@jscad/web:   TypeError: Failed to execute 'dispatchEvent' on 'EventTarget': parameter 1 is not of type 'Event'.
@jscad/web:   › convert (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/generated/Event.js:286:11)
@jscad/web:   › Window.dispatchEvent (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/generated/EventTarget.js:141:16)
@jscad/web:   › src/most-gestures/zooms.js:28:20
@jscad/web:   › TapSink.event (node_modules/most/lib/combinator/transform.js:80:3)
@jscad/web:   › FilterSink.event (node_modules/most/lib/fusion/Filter.js:51:21)
@jscad/web:   › TapSink.event (node_modules/most/lib/combinator/transform.js:81:13)
@jscad/web:   › Object.tryEvent (node_modules/most/lib/source/tryEvent.js:14:10)
@jscad/web:   › HTMLDivElement.addEvent (node_modules/most/lib/source/EventTargetSource.js:30:14)
@jscad/web:   › innerInvokeEventListeners (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/events/EventTarget-impl.js:315:27)
@jscad/web:   › invokeEventListeners (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/events/EventTarget-impl.js:266:3)
@jscad/web:   Unhandled rejection in src/most-gestures/gestures.test.js
@jscad/web:   TypeError: Failed to execute 'dispatchEvent' on 'EventTarget': parameter 1 is not of type 'Event'.
@jscad/web:   › convert (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/generated/Event.js:286:11)
@jscad/web:   › Window.dispatchEvent (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/generated/EventTarget.js:141:16)
@jscad/web:   › src/most-gestures/zooms.js:28:20
@jscad/web:   › TapSink.event (node_modules/most/lib/combinator/transform.js:80:3)
@jscad/web:   › FilterSink.event (node_modules/most/lib/fusion/Filter.js:51:21)
@jscad/web:   › TapSink.event (node_modules/most/lib/combinator/transform.js:81:13)
@jscad/web:   › Object.tryEvent (node_modules/most/lib/source/tryEvent.js:14:10)
@jscad/web:   › HTMLDivElement.addEvent (node_modules/most/lib/source/EventTargetSource.js:30:14)
@jscad/web:   › innerInvokeEventListeners (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/events/EventTarget-impl.js:315:27)
@jscad/web:   › invokeEventListeners (node_modules/browser-env/node_modules/jsdom/lib/jsdom/living/events/EventTarget-impl.js:266:3)
@jscad/web:   ─
@jscad/web:   zooms (from pinch)
@jscad/web:   Error: `t.end()` was never called
@jscad/web:   zooms (from pinch) direct element
@jscad/web:   Error: `t.end()` was never called
@jscad/web:   ─
@jscad/web:   2 tests failed
@jscad/web:   2 unhandled rejections
lerna ERR! npm run test exited 1 in '@jscad/web'
lerna WARN complete Waiting for 1 child process to exit. CTRL-C to exit immediately.
hermann@j4105:~/OpenJSCAD.org$ 

[z3dev]

@Hermann-SW Another developer reported the same, failed test case in the web project

I tried a fresh install, which did not have those failures. What version of NODEJS are you using?

[Hermann-SW]

@z3dev I saw the failures after deleting and fresh installing my fork. Now I installed https://github.com/jscad/OpenJSCAD.org.git and see the same two errors there. Just npm install and npm test ...

I upgraded to latest stable node yesterday because of conditional chaining operator used in JavaScript version of PARI/GP: https://pari.math.u-bordeaux.fr/archives/pari-users-2405/msg00031.html I am working on using PARI/GP commands in a JSCAD script. Was on v12 node before, there were no testcase failures for this repo.

hermann@j4105:~/OpenJSCAD.org$ node -v
v20.13.1
hermann@j4105:~/OpenJSCAD.org$ uname -a
Linux j4105 6.5.0-35-generic #35~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Tue May  7 09:00:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
hermann@j4105:~/OpenJSCAD.org$ head -1 /etc/os-release 
PRETTY_NAME="Ubuntu 22.04.4 LTS"
hermann@j4105:~/OpenJSCAD.org$ 

[Hermann-SW]

Hi, I did the uniquePoints changes. There is no geom3.isValid(), so I added validate(obs) instead.

hermann@j4105:~/OpenJSCAD.org/packages/modeling/src/geometries/geom3$ /home/hermann/OpenJSCAD.org/node_modules/.bin/ava "*.test.js" --verbose --timeout 2m

  ✔ clone › clone: Creates a clone on an empty geom3
  ✔ clone › clone: Creates a clone of a populated geom3
  ✔ applyTransforms › applyTransforms: Updates a geom3 with transformed polygons
  ✔ create › create: Creates an empty geom3
  ✔ create › create: Creates a populated geom3
  ✔ fromPoints › fromPoints: Creates a populated geom3
  ✔ fromPoints › fromPoints: throws for improper points
  ✔ invert › invert: Creates a invert on an empty geom3
  ✔ invert › invert: Creates a invert of a populated geom3
  ✔ fromToCompactBinary › toCompactBinary: converts geom3 (default)
  ✔ isA › isA: identifies created geom3
  ✔ isA › isA: identifies non geom3
  ✔ fromToCompactBinary › toCompactBinary: converts geom3 into a compact form
  ✔ fromToCompactBinary › fromCompactBinary: convert a compact form into a geom3
  ✔ fromPointsConvex › fromPointsConvex (uniquePoints) (130ms)
  ✔ toPoints › toPoints: Creates an array of points from a populated geom3
  ✔ transform › transform: Adjusts the transforms of a populated geom3
  ─

  17 tests passed
hermann@j4105:~/OpenJSCAD.org/packages/modeling/src/geometries/geom3$ 

[Hermann-SW]

Thanks for approving and merging.

I was not sure why unique points are needed and looked into the 2D and 3D quickhull algorithms (not implementation here). I saw no reason for requirement of unique points and tried with below script. Now every point is present twice, and the order of creation of 2nd points is different to 1st. It works, and script outputs the exact same number of #faces/#edges: 170 / 336 as with unique points. Since #vertices = #edges + 2 - #faces, the number of vertices is same as well. This seems to prove that unique points in no requirement for quickhull ...

const jscad = require('@jscad/modeling')
const { geom3 } = jscad.geometries

function main() {
  let out = []
  for(x=-9;x<=9;++x)
    for(y=-9;y<=9;++y)
      for(z=-9;z<=9;++z)
        if (x*x+y*y+z*z <= 96)
          out.push([x,y,z])
// make all points duplicates, in different order
  for(z=-9;z<=9;++z)
    for(y=-9;y<=9;++y)
      for(x=-9;x<=9;++x)
        if (x*x+y*y+z*z <= 96)
          out.push([x,y,z])

   ret = geom3.fromPointsConvex(out)
   edges=0; ret.polygons.forEach((f) => edges += f.vertices.length); edges/=2
   console.log("#faces/#edges: ",ret.polygons.length,"/",edges)
   return ret
}

module.exports = { main }

[z3dev]

I was not sure why unique points are needed and looked into the 2D and 3D quickhull algorithms (not implementation here). I saw no reason for requirement of unique points and tried with below script.

Interesting. Both @platypii and I assumed that the algorithms needed a set of unique points. I believe this was documented somewhere in the algorithm source / API. But maybe we should test again. If not required then the creation of a set of unique points can be dropped, and everything runs faster. 👍