plane.fromPoints() implementation buggy

Hermann-SW commented 4 months ago

Expected Behavior

For new testcase

const obs5 = fromPoints(obs1, [-1, -1, -1], [1, -1, -1], [-1, 1, -1], [1, 1, -1])

all pointes lie on plane z==-1, and the normalized normal vector returned should be either [0,0,-1] or [0,0,1].

Actual Behavior

Instead [0,0,0] is returned which cannot be a normal vector. Reason is that two times normal vector computed in loop is [0,0,1], and two times it is [0,0,-1], and summation cancels them 0 as [0,0,0]. Summaion is just wrong.

Steps to Reproduce the Problem

add this test to OpenJSCAD.org/packages/modeling/src/maths/plane/fromPoints.test.js:

pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/maths/plane $ git diff fromPoints.test.js
diff --git a/packages/modeling/src/maths/plane/fromPoints.test.js b/packages/modeling/src/maths/plane/fromPoints.test.js
index 7e924d3b..b4c9297a 100644
--- a/packages/modeling/src/maths/plane/fromPoints.test.js
+++ b/packages/modeling/src/maths/plane/fromPoints.test.js
@@ -17,4 +17,7 @@ test('plane: fromPoints() should return a new plane with correct values', (t) =>
// polygon with co-linear vertices
const obs4 = fromPoints(obs1, [0, 0, 0], [1, 0, 0], [2, 0, 0], [0, 1, 0])
t.true(compareVectors(obs4, [0, 0, 1, 0]))
+
+  const obs5 = fromPoints(obs1, [-1, -1, -1], [1, -1, -1], [-1, 1, -1], [1, 1, -1])
+  t.true(compareVectors(obs5, [0, 0, 1, -1]))  
})
pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/maths/plane $

run

pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/maths/plane $ ../../../../../node_modules/.bin/ava fromPoints.test.js 

plane: fromPoints() should return a new plane with correct values

src/maths/plane/fromPoints.test.js:22

21:   const obs5 = fromPoints(obs1, [-1, -1, -1], [1, -1, -1], [-1, 1, -1]…
22:   t.true(compareVectors(obs5, [0, 0, 1, -1]))                          
23: })                                                                     

Value is not `true`:

false

› fromPoints.test.js:22:9

─

1 test failed
pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/maths/plane $

use "t.is(obs5, [0, 0, 1, -1])" instead to see that indeed invalid [0,0,0] is returned as normal
```
Difference:

[
  0,
  0,
-   0,
-   -0,
+   1,
+   -1,
]
```

Specifications

Version:
Platform: Debian based 64bit Raspberry PiOS, same error on Intel Ubuntu browser
Environment: browser, local ava test

Hermann-SW commented 4 months ago

Fix is available on my fork: https://github.com/jscad/OpenJSCAD.org/compare/master...Hermann-SW:OpenJSCAD.org:master

Only problem is that this single testcase fails after fix, but that is likely because because of incorrect plane.fromPoints() a point too much was returned, and now is not. So likely 863 is correct:

pi@raspberrypi5:~/OpenJSCAD.org/packages/modeling/src/operations/expansions $ ../../../../../node_modules/.bin/ava expand.test.js

  expand: expanding of a geom3 produces expected changes to polygons

  src/operations/expansions/expand.test.js:133

   132:   t.notThrows.skip(() => geom3.validate(obs2))
   133:   t.is(pts2.length, 864)                      
   134: })                                            

  Difference:

  - 863
  + 864

  › expand.test.js:133:5

  ─

  1 test failed
pi@raspberrypi5:~/OpenJSCAD.org/packages/modeling/src/operations/expansions $

Hermann-SW commented 4 months ago

It is not only that single point difference, I did outpus pts2 in both cases, and there are much more (minimal) differences:

pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/operations/expansions $ diff out  ~/OpenJSCAD.org/packages/modeling/src/operations/expansions/out  | head
20c20
<   -       -1.7870337216829664,
---
>   -       -1.7870337216829657,
25c25
<   -       -1.7870337216829664,
---
>   -       -1.7870337216829657,
30c30
<   -       -5.322567627615704,
pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/operations/expansions $ diff out  ~/OpenJSCAD.org/packages/modeling/src/operations/expansions/out | wc --lines
23983
pi@raspberrypi5:~/old/OpenJSCAD.org/packages/modeling/src/operations/expansions $

z3dev commented 4 months ago

Yeah. This is the issue that I mentioned about the ordering of the points. The points have to create a valid polygon, i.e. non-crossing edges.

I completed an implementation of a best-fit algorithm. See #1322 for the code changes. I believe this would be a better choice for the general use cases.

Hermann-SW commented 4 months ago

Yeah. This is the issue that I mentioned about the ordering of the points. The points have to create a valid polygon, i.e. non-crossing edges.

@z3dev Interesting, and you are right, my example above in this issue was with intersection of 2 of the 4 edges: fromPoints(obs1, [-1, -1, -1], [1, -1, -1], [-1, 1, -1], [1, 1, -1])

*--*
 \/
 /\
*--*

I did rewrite for no intersection ... console.log(plane.fromPoints([], [-1, -1, -1], [1, -1, -1], [1, 1, -1], [-1, 1, -1]))

*--*
|  |
|  |
*--*

... and indeed non-null normal gets returned in first three components:

With your new function for the general case a wontfix for this function would be OK. But only with updating doc stating that no "intersections" in the plane are allowed: https://jscad.app/docs/module-modeling_maths_plane.html#.fromPoints

z3dev commented 4 months ago

@Hermann-SW thanks again for the feedback, and great discussion.

jscad / OpenJSCAD.org