User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Fri Aug 05, 2022 6:18 pm

I did big cleanup and simplify of "doit()" code, that does determine vertex coordinates of one side vertices of separating circle (orange edges).
And added 2nd parameter for "vtxt()" OpenSCAD module, allowing to not only label vertices with their vertex number.
Finally I added new option "-10" that does determine "vtype" for each vertex when selected (sides 1 and 2, and 0 indicating vertices on separating circle):
(this big diff is best viewed with github split mode)
https://github.com/Hermann-SW/planar_gr ... cf0decc0c8

Code: Select all

./rjs node.tetra.js graphs/C60.a white.70 -10
C60.vtype.png
C60.vtype.png
C60.vtype.png (82.52 KiB) Viewed 2921 times
vtype=1 vertices have horizontal angles in 0°..270° range, vtype=2 vertices in 180°..450° range.

The reason for cleanup work was clear.
Adding new "vtype" related option is preparation for next step.
I had no success with single vertex change spring embedders.
Success happened when solving system of linear equations for determining vertex coordinates.

After vertex coordinates have been determined, for vertices of vtype 1 and 2, I will call "tutte.convex_face_coordinates()" again, but this time I will not pass the vertices on separating circle as fixed coordinates, but the vertices of vtype 1 and 2. That will determine new coordinates for vtype=0 vertices (on separating circle), by calling "tutte.convex_face_coordinates()" once. Inspecting the difference then will show whether repeated determination of vtype=1 and vtype=2 vertices, and then of vtype=0 vertices might approach "better" and "better" spring embeddings or not (whatever "better" will be) ...

P.S:
"better" might be more "regular" spring embedding for C60 like football:
Image
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sat Aug 06, 2022 3:27 am

Two more changes for option "-10":
https://github.com/Hermann-SW/planar_gr ... b63ca53b98
  1. show spherical (gray) pentagons
  2. show vertices of separating circle (vtype=0) full, vtype 1 or 2 vertices half

(2) makes it easier to spot (changes of) most part of separating circle, even on backside through transparent white sphere surface:

Code: Select all

./rjs node.tetra.js graphs/C60.a white.70 -10
C60.vtype.half0.png
C60.vtype.half0.png
C60.vtype.half0.png (80.97 KiB) Viewed 2853 times
You can see all 4 red (full) vertices in this view:
  • middle
  • bottom back near z=10 label
  • back near middle between x=-10 and y=10 label
  • back right near x=10 label (outside of this screenshot)

(1) for easier comparison of C60 sphere spring embedding to football (black pentagons):
Image
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Tue Aug 09, 2022 12:40 am

I stumbled over OpenJsCad again, and it looked promising, but I was not able to get it working in browser.
Then I found joostn's working github.io repo:
http://joostn.github.io/OpenJsCad/

I forked his deprecated OpenJsCad repo and revived his github.io version in it:
https://github.com/Hermann-SW/OpenJsCad

I stripped down index.html to only viewer ...
https://github.com/Hermann-SW/OpenJsCad ... iewer.html
... showing stored .jscad file only:
https://github.com/Hermann-SW/OpenJsCad ... ml#L69-L79

Code: Select all

<textarea id="code" hidden>
function main() {
  var sphere = CSG.sphere({
    center: [0, 0, 0],
    radius: 3,
    resolution: 32
  });
  return sphere.union([sphere.translate([0,0,10]),
    sphere.translate([0,10,0]),
    sphere.translate([10,0,0])]);
}</textarea>
only_viewer.html.png
only_viewer.html.png
only_viewer.html.png (25.68 KiB) Viewed 2687 times

This only works if opening the .html files locally in browser, otherwise publish on github.io would be needed.

Next steps will be to see, whether this working old deprecated version of OpenJsCad allows to create same output I created with OpenSCAD above:
Image


P.S:
https://openjscad.xyz/ does not work for me, providing valid .jscad input and pressing SHIFT+ENTER to compile results in "processing,", "waiting" and then nothing.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Tue Aug 09, 2022 7:31 pm

TIL how to use the current github repo correctly, so no need to use my fork at least now:
https://github.com/jscad/OpenJSCAD.org

"git clone" the repo, then cd into packages/web, finally start webserver in that directory:

Code: Select all

python -m http.server 8000
Then open this URL:
http://127.0.0.1:8000/demo.html

I don't know how to load files yet, but I copied this example
https://www.openjscad.xyz/?uri=https:// ... ad:9621819
into editor opening when clicking on 2nd button from top right.

Pressing "SHIFT+ENTER" compiles and shows result:
jscad.local_webserver.jpg
jscad.local_webserver.jpg
jscad.local_webserver.jpg (89.93 KiB) Viewed 2595 times

The examples have different syntax than the very old version with CSG prefixes.
I stripped down the example above to just a single roundedCylinder that got required:

Code: Select all

const { circle, cuboid, roundedCuboid, roundedCylinder, roundedRectangle } = require('@jscad/modeling').primitives
const { rotateX, rotateY, scale, translate } = require('@jscad/modeling').transforms
const { subtract, union } = require('@jscad/modeling').booleans
const { extrudeLinear } = require('@jscad/modeling').extrusions
const { degToRad } = require('@jscad/modeling').utils
const { measureBoundingBox } = require('@jscad/modeling').measurements

function main() {
  return roundedCylinder({ height: 12, radius: 3, roundRadius: 1, segments: 18 })
}
module.exports = { main }
You can see the result online by clicking on this (share) URL:
https://www.openjscad.xyz/?uri=https:// ... orum/rC.js

[I really like share links, built them into my GraphvizFiddle as well, 2225 bytes long sample URL here]

The feature I really really have to find out is how to zoom in and out, without a mouse with wheel ...


P.S:
Clicking on help button top right leads to User Guide, API Reference, forums, ...:
https://www.openjscad.xyz/


P.P.S:
Just learned how to zoom without mouse wheel on the laptop I have with me:
The view can be rotated, zoomed in or out, and moved by using the mouse buttons. (Or fingers if using a tablet or mobile phone.)
I remembered that my laptop has a touch display (I never used that) and zooming with 2 fingers works as it does on smartphone.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Wed Aug 10, 2022 7:42 pm

I tried to build the basic constructs for planar graph sphere embedding.
"vertex()" was easy (JSCAD does work on radians, unlike OpenSCAD which works on degrees):

Code: Select all

function map_3D(c,sc) {
  return [Math.cos(degToRad(c[0]))*Math.sin(degToRad(c[1]))*sc, Math.sin(degToRad(c[0]))*Math.sin(degToRad(c[1]))*sc, Math.cos(degToRad(c[1]))*sc]
}
...
function vertex(_v, c, half=false) {
    p = coords[_v]
    v = map_3D(p,sc)
    return colorize(c, sphere({radius: 0.5, center: v}))
}
and as next step I implemented "edge()" as well, as step before "edge2()" great circle arc (round) edges:

Code: Select all

function edge(_v,_w) {
    v = map_3D(coords[_v],sc)
    w = map_3D(coords[_w],sc)
    d = [0,0,0]
    x = [0,0,0]
    subtract(d,w,v)
    add(x,v,w)
    scale(w,x,0.5)
    return colorize([0,0,1,1], 
                    translate(w, 
                              rotate([0,Math.acos(d[2]/length(d)),Math.atan2(d[1],d[0])],
                                     cylinder({ radius: 0.1, height: length(d)}))))
}

Unlike OpenSCAD, JSCAD alpha values less than 1 do change appearance, but stuff behind does not shine through. Also the spheres look different:
JSCAD.vertex_edge.js.png
JSCAD.vertex_edge.js.png
JSCAD.vertex_edge.js.png (104.47 KiB) Viewed 2513 times

Here you can inspect
https://stamm-wilbrandt.de/en/forum/JSC ... ex_edge.js
in your browser:
https://www.openjscad.xyz/?uri=https:// ... ex_edge.js


P.S:
I hope to add a 3D toggle to planar graph playground in browser soon ...
https://hermann-sw.github.io/planar_graph_playground/


P.P.S:
The question is, whether JSCAD will be performant enough to present gray spherical polygons (lots of triangles, complex) as here in bowser, with acceptable rotation refreshes:
Image
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Thu Aug 11, 2022 2:09 pm

One step further, "edge2()" (great circle arc) rounded edges now work in JSCAD as well:
JSCAD.vertex_edge2.js.png
JSCAD.vertex_edge2.js.png
JSCAD.vertex_edge2.js.png (67.28 KiB) Viewed 2433 times

Hand edited file for C20 fullerene embedding onto sphere:
https://stamm-wilbrandt.de/en/forum/JSC ... x_edge2.js

You can view, zoom, rotate live in your browser:
https://www.openjscad.xyz/?uri=https:// ... x_edge2.js

Porting "edge2()" from OpenSCAD to JSCAD was not that difficult, besides a bit of juggling with degree/radian angles the same spherical calculations ...

Code: Select all

function edge2(_p1,_p2,_e) {
    p1 = coords[_p1]
    p2 = coords[_p2]
    // al/la/ph: alpha/lambda/phi | lxy/sxy: delta lambda_xy/sigma_xy
    // https://en.wikipedia.org/wiki/Great-circle_navigation#Course
    la1 = degToRad(p1[0])
    la2 = degToRad(p2[0])
    l12 = la2 - la1
    ph1 = degToRad(90 - p1[1])
    ph2 = degToRad(90 - p2[1])
    al1 = Math.atan2(Math.cos(ph2)*Math.sin(l12), Math.cos(ph1)*Math.sin(ph2)-Math.sin(ph1)*Math.cos(ph2)*Math.cos(l12))
    // delta sigma_12
    // https://en.wikipedia.org/wiki/Great-circle_distance#Formulae
    s12 = Math.acos(Math.sin(ph1)*Math.sin(ph2)+Math.cos(ph1)*Math.cos(ph2)*Math.cos(l12))
... and then the JSCAD way of concatenating rotations, extrudeRotate(), ...:

Code: Select all

    return rotate([0,0,la1],
                  rotate([0,-ph1,0],
                         rotate([degToRad(90)-al1, 0, 0],
                                extrudeRotate({segments: 32, angle: s12},
                                              circle({radius: 0.1,center: [sc,0]})))))
}

Next step (JSCAD spherical triangle and spherical polygon) will decide whether the effort sofar was worth it, or whether it becomes too slow for browser ...
viewtopic.php?t=333342&start=50#p2023738
Image
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Thu Aug 11, 2022 8:50 pm

I learned how to use JSCAD params and added look_inside boolean toggle, that allows to "look inside" the white sphere:
https://stamm-wilbrandt.de/en/forum/JSC ... .params.js
x.anim.gif
x.anim.gif
x.anim.gif (101.45 KiB) Viewed 2383 times
The inside vertex sphere halves can be seen only because now sphere with radius reduced by 0.1 got subtracted:

Code: Select all

...
    ,colorize([1,1,1,1],
      subtract(
        sphere({radius: sc, segments: params.wsegments})
        ,sphere({radius: sc-0.1, segments: params.wsegments})
        ,cube({size: params.look_inside?sc:0.01, center: [sc/2,-sc/2,sc/2]})
      )
     )
...

First I used 180 segments as I did with generating OpenSCAD, but that took way to loooong. After reducing to 30 segments the response was OK. 2nd param white_segments allows to play with view and response time, eg. 2 seconds in Chrome developer tools console for 30 segments:

Code: Select all

total time for design regeneration 2009 13
You can play live with new JSCAD.vertex_edge2.params.js in browser:
https://www.openjscad.xyz/?uri=https:// ... .params.js
If enabling "Instant Update", any change of a param updates the view.

Now that I learned about JSCAD "subtract()" ("difference()" in OpenSCAD) #segments time issues, it will be interesting whether when doing "subtract()" for a spherical triangle with convex hull of 6 points, JSCAD design regeneration performance will suffer or not ...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sun Aug 14, 2022 3:17 pm

Made progress with porting sphere embedding OpenSCAD modules to JSCAD, now spherical triangle and spherical polygon work as well in JSCAD. Design regeneration time (can be seen in browser console) for C20 with one gray pentagon is below 3 seconds (on Intel i7 Linux Chrome, will test with 64bit Raspberry Pi OS in 2 weeks). Details in this posting:
https://openjscad.nodebb.com/topic/377/ ... 0482949555
JSCAD.spherical_polygon.js.png
JSCAD.spherical_polygon.js.png
JSCAD.spherical_polygon.js.png (98.57 KiB) Viewed 2179 times

Clicking on "Enable Auoto-zoom" and "Enable Auto-rotate" results in nice animation ...
https://www.openjscad.xyz/?uri=https:// ... polygon.js
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sun Aug 14, 2022 9:50 pm

Done with porting "vtxt()" and "half=true" for "vertex()" optional 3rd argument, details in this posting:
https://openjscad.nodebb.com/topic/377/ ... 0482949561

Link for browser view:
https://www.openjscad.xyz/?uri=https:// ... ex_half.js
JSCAD.vertex_half.js.png
JSCAD.vertex_half.js.png
JSCAD.vertex_half.js.png (65.71 KiB) Viewed 2100 times
Next step is to enable "node.tetra.js" to output either OpenSCAD (x.scad), or JSCAD (scad.js) output.
For JSCAD output, openjscad.xyz does not allow for "data:" scheme URIs:
https://openjscad.nodebb.com/topic/379/ ... 0513473551
So open either local webserver demo.html (eg. "http://127.0.0.1:8000/demo.html") or "https://openjscad.xyz" in browser, click on edit symbol top right and copy in the file you are working on. Then press CTRL+ENTER for refreshing view and continue working on changes.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Mon Aug 15, 2022 10:19 pm

For evaluation whether 12 gray pentagons of a fullerene (12*3*2=72 "sp_tria2()" calls, and 12 "subtract()"s with 6 point "hull()"s) has acceptable performance with JSCAD in browser, I enhanced JSCAD file a lot, with many added parameters:
https://stamm-wilbrandt.de/en/forum/JSCAD.C20_params.js

You can directly play with it clicking here:
https://www.openjscad.xyz/?uri=https:// ... _params.js

I first open Chrome browser console, then tick "Enable Auto-zoom" and "Instant Update", and finally deselect "no pentagons". This is the result:
JSCAD.C20_params.js.png
JSCAD.C20_params.js.png
JSCAD.C20_params.js.png (111.4 KiB) Viewed 2038 times
Because "look_inside" is selected, 3 of the 12 pentagons do not show the gray spherical pentagons. On Intel i7 design regeneration takes less than 5 seconds only.

Next, deselecting "surface of sphere" results in view without white sphere surface:
JSCAD.C20_params.js.2.png
JSCAD.C20_params.js.2.png
JSCAD.C20_params.js.2.png (97.47 KiB) Viewed 2038 times
Here you can see the inner spherical pentagons, which are hidden by white sphere normally.

Finally deselecting "look_inside" shows all 12 gray pentagons, with still less than 5 seconds of design regeneration:
JSCAD.C20_params.js.3.png
JSCAD.C20_params.js.3.png
JSCAD.C20_params.js.3.png (94.53 KiB) Viewed 2038 times

This all works now because of carefully chosen values for gray_points (24) and gray segments (30). With current code the previous values of (40/40) for both from OpenSCAD mean 82/40 for gray points/segments. With those values design regeneration is in 25 seconds area.

Since all fullerenes have exactly 12 pentagons, JSCAD output is useful for performant browser view (will have to test with 64bit Raspberry Pi OS when back home). After design regeneration, rotation in browser is super fast.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Tue Aug 16, 2022 6:39 pm

Instead of not displaying 3 pentagons, I subtracted cube in case of look_inside selected from each pentagon:
https://stamm-wilbrandt.de/en/forum/JSC ... arams_b.js

I tested to color the pentagons with different than grey as well, for planar embedding face 6-coloring on sphere:
https://www.openjscad.xyz/?uri=https:// ... arams_b.js

I found no satisfying way to capture video of JSCAD Auto-rotate, so I just shot a smartphone video and posted one rotation on youtube:
https://www.youtube.com/watch?v=R2BBftH2BKg
JSCAD.C20_params_b.js.tw.png.jpg
JSCAD.C20_params_b.js.tw.png.jpg
JSCAD.C20_params_b.js.tw.png.jpg (54.23 KiB) Viewed 1950 times

JSCAD screenshot is brighter:
JSCAD.C20_params_b.js.png
JSCAD.C20_params_b.js.png
JSCAD.C20_params_b.js.png (116.51 KiB) Viewed 1950 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Thu Aug 18, 2022 10:34 pm

I successfully added JSCAD output option to node.tetra.js — not submitted today, will do after more cleanup tomorrow.

I modified "rjs" script to be able to pass 1st argument if prefixed with "-" to C preprocessor:

Code: Select all

#!/bin/bash
file=$1
shift
if [[ $file == "-"* ]]
then
  opt=$file
  file=$1
  shift
fi
export ARGV0=$file
gcc $opt -E -x c -nostdinc $file | grep -v "^#"  | nodejs - $*

This call with option -10 for vtype output creates "x.jscad" (instead of "x.scad" OpenSCAD output) because of 1st "-DJSCAD" argument:

Code: Select all

stammw@t480ub:~/planar_graph_playground$ ./rjs -DJSCAD node.tetra.js graphs/C60.a white -10
12 pentagons for graph
20 non-pentagons for graph
vertices: 0,5,35,48
max: 34
dists: 5 5 6 6 6 6
false
false
vertices: 0,5,35,48,22,23,47,11,12,36,37,27,28,6,49,50,15,16,17,1,2,4,3,7,8,9,10,24,25,26,39,40,41,42,43,44,45,46,51,52,53,54,55,56,57,58,59
[ 23, 24, 13 ]
M.length: 47
[ 17, 0, 18, 19, 16 ]
[ 2, 1, 39, 40, 3 ]
[ 29, 4, 5, 6, 28 ]
[ 8, 7, 44, 45, 9 ]
[ 24, 10, 11, 12, 23 ]
[ 14, 13, 49, 50, 15 ]
[ 21, 20, 34, 35, 22 ]
[ 26, 25, 36, 37, 27 ]
[ 31, 30, 38, 33, 32 ]
[ 42, 41, 55, 56, 43 ]
[ 47, 46, 57, 58, 48 ]
[ 52, 51, 59, 54, 53 ]
stammw@t480ub:~/planar_graph_playground$ 

C60 fullerene has 60 vertices and 90 edges, so more "design regeneration" time than 5 seconds was to be expected. I am happy that (Intel i7 Linux) Chrome shows less than 10 seconds. After design regeneration rotation+zoom is super fast:
JSCAD.C60_vtype.js.png
JSCAD.C60_vtype.js.png
JSCAD.C60_vtype.js.png (71.06 KiB) Viewed 1865 times
Only JSCAD parameter "look_inside" allows to look inside as before.

You can play with C60 in your browser:
https://www.openjscad.xyz/?uri=https:// ... 0_vtype.js
Enable Auto-zoom, Instant-Update and then toggle "look_inside" and rotate ...


New "rjs" passing "-DJSCAD" or not decides whether "scad.js" or "jscad.js" gets included:

Code: Select all

#ifndef JSCAD
#include "scad.js"
#else
#include "jscad.js"
#endif

Finally "tetra()" for OpenSCAD or "jtetra()" for JSCAD output gets called:

Code: Select all

...
if (!dopent) {
  pent = [];
}
#ifndef JSCAD
tetra(G, M, Math.sqrt(n_vertices(G)), visited, pent);
#else
jtetra(G, M, Math.sqrt(n_vertices(G)), visited, pent);
#endif

"jscad.js" is JSCAD version of OpenSCAD "scad.js", here is "vertex()" definition:

Code: Select all

...
        wlog("function vertex(_v, half=false) {");
        wlog("    p = coords[_v] ");
        wlog("    v = map_3D(p,sc)");
        wlog("    la1 = degToRad(p[0])");
        wlog("    ph1 = degToRad(90 - p[1])");
        wlog("    return colorize([0, 0.7, 0],");
        wlog("        subtract(sphere({radius: 0.5, center: v}),");
        wlog("            translate([0, 0, 0],");
        wlog("                rotate([0, 0, la1],");
        wlog("                    rotate([0, -ph1, 0],");
        wlog("                        translate([sc+0.5, 0],");
        wlog("                            rotate([degToRad(90), 0, degToRad(90)],");
        wlog("                                translate([-0, -0, -1],");
        wlog("                                     cuboid({size: [1, 1, 0.8]})");
        wlog("                                )");
        wlog("                            )");
        wlog("                        )");
        wlog("                    )");
        wlog("                )");
        wlog("            )");
        wlog("        )");
        wlog("    )");
        wlog("}");
...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Fri Aug 19, 2022 11:20 pm

I submitted JSCAD stuff, and then realized that it might be useful to move all the logic from JavaScript into JSCAD output generated in case of "-DJSCAD". I tried and like it, available with latest commit:
https://github.com/Hermann-SW/planar_gr ... 224c3a5379

This command creates the new C60 x.jscad:

Code: Select all

stammw@t480ub:~/planar_graph_playground$ ./rjs -DJSCAD node.tetra.js graphs/C60.a white -10
Sample screenshot with "sphere surface" deselected, and model link to play with in browser:
https://www.openjscad.xyz/?uri=https:// ... vtype_b.js
JSCAD.C60_vtype_b.js.png
JSCAD.C60_vtype_b.js.png
JSCAD.C60_vtype_b.js.png (131.45 KiB) Viewed 1781 times

As you can see, although "half vertex" is selected, the logic still creates full spheres for vertices with vtxt="Type" (possible values are "Id", "Type" and "None") for vertices of type 0 (on orange separating circle).

Possible values for "face coloring" are "Pentagons", "6coloring" and "None". The 2nd value will be made working next.


P.S:
Vertices not made half on separating circle for vtxt="Type" will help working on relocating separating circle vertices, without sphere surface with look_inside for C20 fullerene:
JSCAD.C60_vtype_b.js.2.png
JSCAD.C60_vtype_b.js.2.png
JSCAD.C60_vtype_b.js.2.png (132.88 KiB) Viewed 1754 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sat Aug 20, 2022 10:33 am

If zooming in too much with JSCAD, one gets a view from inside sphere, but the field of view is too small to be interesting (view like sitting in planetarium).

I zoomed out a bit, just outside of sphere, so that front parts of sphere pass very close to camera. Look nice at least. I enabled JSCAD Auto-rotate, captured smartphone video of one rotation and uploaded to youtube:
https://www.youtube.com/watch?v=nr2E-EukS2Q
Attachments
C60.close.JSCAD_animation.yt.jpg
C60.close.JSCAD_animation.yt.jpg
C60.close.JSCAD_animation.yt.jpg (68.9 KiB) Viewed 1627 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sat Aug 20, 2022 8:04 pm

Before making 6coloring option for face coloring, I tested all graphs on whether they work, and whether any graph besides C20 and C60 works with implementation until now.

I found one, graphs/C36.10.a was processable and showed a bug, more on that later.

The other graphs asserted, and it was difficult to find out where in code. So I added assert.assert() messages:
https://github.com/Hermann-SW/planar_gr ... b856908b74

Many asserts stated "doit, wrong orient", and I wanted to mirror the embedding (along any plane straight line).
New tool mirror_embedding.js does just that, by reverting the vertex adjacency lists:
https://github.com/Hermann-SW/planar_gr ... bedding.js
mirror_embedding.js.png
mirror_embedding.js.png
mirror_embedding.js.png (23.82 KiB) Viewed 1545 times

One more graph became processable:

Code: Select all

$ ./rjs mirror_embedding.js graphs/C36.14.a > C36.14.r.a
$
The embedding consists of 3 clusters of 4 (gray) pentagons each, separated by hexagons:
C36.14.r.a.png
C36.14.r.a.png
C36.14.r.a.png (223.6 KiB) Viewed 1545 times

Back to the bug for graphs C36.10.a, I wanted to be able to inspect theta and phi angles of polar coordinates. So I added new "theta" and "phi" values for JSCAD "vtxt":
https://github.com/Hermann-SW/planar_gr ... d7cf776e93

Here are the two problems of graphs/C36.10.a with "phi" values shown, from 0°..270° on separating orange circle bottom right, and from 180°..450° top middle:
C60.phi.wrong12.problem.png
C60.phi.wrong12.problem.png
C60.phi.wrong12.problem.png (177.81 KiB) Viewed 1545 times

The problem bottom right is, that "mark2()" function should have labeled next two vertices on orange circle after red 270° vertex with 270°, but there is only one, and the other is incorrectly labeled 90°. With 270°, the added 180° would place green "134.3" vertex 60° more right (194.3°) because green vertices are centroids of their neighbors. That placement makes much more sense.

Top middle problem is that "mark2()" should have labeled two green vertices on orange circle with 360°, but one is labeled "180.0". With 360 the added 180° place "246.0" vertex 60° more right (306.0°), so then no grey spherical triangle is outside its pentagon (like the triangle of vertices 180°, 246° and top left vertex. Now going to fix the problems to get valid coordinates and then valid gray spherical pentagons ...


P.S:
Here is mirrored C36.14 fullerene for zoom+rotate in browser:
https://openjscad.xyz/?uri=https://stam ... _14_r_a.js
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Mon Aug 22, 2022 1:50 pm

Wow — 3 days ago I asked on JSCAD forum on how to make complete "node.tetra.js" run in browser and view rendered model in browser, and found solution yesterday myself (will look into yetserday answer in that thread as well):
https://openjscad.nodebb.com/topic/380/ ... 1081221674

I just had incorrect mindset. Until now I run "node.tetra.js" to create either x.scad or x.jscad, and then view with OpenSCAD/JSCAD in 2nd step. I only needed a 3rd mode "-DJSCAD_" that does all graph processing in browser, as well as to provide "main()" function for JSCAD viewing.

Before describing the (surprisingly small) "node.tetra.js" and "rjs" diffs, here is new JSCAD_.1.js model online for viewing in browser:
https://openjscad.xyz/?uri=https://stam ... SCAD_.1.js

With Auto-Zoom enabled, it should show similar to this:
JSCAD_.1.js.png
JSCAD_.1.js.png
JSCAD_.1.js.png (84.38 KiB) Viewed 1429 times
Biggest difference of JSCAD_ and JSCAD output is size:
36,367 bytes for JSCAD_, and 19,953 bytes for JSCAD.
No surprise, all the undirected graph code as well as solver for systems of linear equations is part of JSCAD_ output (both modes create "x.jscad").

And runtime is shorter for JSCAD mode than JSCAD_ mode; in JSCAD_ mode first the graph algorithms run, determine all pairs shortest paths, determine shortest paths tetrahedron, then separating circle, then positions separating circle vertices on sphere and finally solves two systems of linear equations to determine all other vertices coordinates. After all that, "main()" rendering displays in browser.

All that happens currently on every update, while graph algorithms need to be run only when selecting a new graph, for what the selection choice element has to be implemented.


Now looking at submitted+committed change:
https://github.com/Hermann-SW/planar_gr ... ff=unified

I decided for no filesystem access for JSCAD_, instead graphs of interest (4 fullerenes for now) are builtin, and can be selected by index 0..3 instead of file name:
JSCAD_.graphs.png
JSCAD_.graphs.png
JSCAD_.graphs.png (33.37 KiB) Viewed 1429 times
Since there is no "process" in browser, I created what is needed (argv, exit()).
Reading file for JSCAD_ is done simply by:

Code: Select all

...
+#ifndef JSCAD_
var adj = parse2file(process.argv[2]);
+#else
+var adj = graphs[parseInt(process.argv[2])];
+#endif
...

New "-DJSCAD_" does not need to run nodejs in "rjs" tool, just the C preprocessor, fixed here:
JSCAD_.rjs_diff.png
JSCAD_.rjs_diff.png
JSCAD_.rjs_diff.png (23.1 KiB) Viewed 1429 times

So (at least) two open issues now, fix the polar coordinates bug for two vertices shown in previous posting, and add graph selection choice element for -DJSCAD_ mode ...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Tue Aug 23, 2022 9:47 pm

Of course I worked on another open issue than the two stated in previous posting, implementing 6coloring.

New function "faces(G)" was needed, returning all faces of G (array of array of vertex):
https://github.com/Hermann-SW/planar_gr ... 17c72335b7

Implementing 6coloring was not difficult based on "faces(G)", "D=dual_graph(G)" and "six_coloring(D)". But doing the coloring of spherical triangles was a nightmare. Finally root cause of problems turned out to be, that in case of one triangle angle being close to 180°, nothing got returned — an nothing cannot be colorized. Fix was to return an invisible small object in that case:
https://github.com/Hermann-SW/planar_gr ... d582d6327d

I am done with JSCAD_ implementation, need to complete JSCAD and OpenSCAD implementation as well before committing. I already captured a video of C60 fullerene face 6coloring with smartphone and uploaded to youtube:
https://www.youtube.com/watch?v=Zl-KumZDBbQ
JSCAD_.C60.face_6coloring.png.jpg
JSCAD_.C60.face_6coloring.png.jpg
JSCAD_.C60.face_6coloring.png.jpg (54.64 KiB) Viewed 1351 times

Looks nicer to me than 6coloring of C60 in plane from much earlier in this thread:
Image


P.S:
I really like how small the diff is for "-DJSCAD_":
JSCAD_.6coloring.diff.png
JSCAD_.6coloring.diff.png
JSCAD_.6coloring.diff.png (78.38 KiB) Viewed 1330 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Thu Aug 25, 2022 3:30 pm

Done with "Implement 6coloring for OpenSCAD, JSCAD and JSCAD_ modes":
https://github.com/Hermann-SW/planar_gr ... 375f7f58c3

C60 fullerene 6coloring for OpenSCAD mode done with this command:

Code: Select all

./rjs node.tetra.js graphs/C60.a white.0 -11
C60 fullerene 6coloring for JSCAD mode done with this command:

Code: Select all

./rjs -DJSCAD node.tetra.js graphs/C60.a white -11
You can view that generated JSCAD model using openscad.xyz with this link:
https://www.openjscad.xyz/?uri=https:// ... g.vtype.js

Here I copied JSCAD (left) and OpenSCAD (right) together, showing same 6coloring algorithm output (only 5 colors are used for this graph) with nearly same view:
C60.6coloring.JSCAD_OpenSCAD.png
C60.6coloring.JSCAD_OpenSCAD.png
C60.6coloring.JSCAD_OpenSCAD.png (115.68 KiB) Viewed 1262 times

JSCAD preview seems to be simpler or better than OpenSCAD preview:
Rotation of "same" model is fast for JSCAD (or JSCAD_) compared to OpenSCAD.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sun Aug 28, 2022 4:27 pm

Back home from 3w vacation, played with latest model in 64bit Raspberry PiOS Chromium browser on my Pi400:
https://www.openjscad.xyz/?uri=https:// ... g.vtype.js
JSCAD.C60.vtype.39s.jpg
JSCAD.C60.vtype.39s.jpg
JSCAD.C60.vtype.39s.jpg (125.37 KiB) Viewed 1065 times
C60 without sphere with 6coloring, and only changing vertex type takes 39 seconds JSCAD design regeneration.
After that rotation as well as Raspberry mouse middle wheel zooming is fast.

Just did same test with Intel i7 Linux Chrome, there design regeneration time is 12 seconds.


Not sure what Chromium is doing, 28GB virtual memory for chromium processes looks strange to me on a 4GB RAM computer:
pi400.chromium.png
pi400.chromium.png
pi400.chromium.png (78.89 KiB) Viewed 1065 times

P.S:
Just tried the model on Intel Celleron j4125 Ubuntu Chrome, and there design regeneration takes 32 sconds, only slightly faster than Pi400 Chrome ...


P.P.S:
Just created same C60 6coloring model for OpenSCAD. "openscad x.scad" on Pi400 takes less than 1 second for total rendering time only. Only rotation and zooming is a little slower than with JSCAD.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Mon Aug 29, 2022 4:39 pm

I had to update my workstation in IBM Böblingen/Germany datacenter [from 2016, Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz]. Only 3 of the 48 cores are used for design regeneration of C60 model in Linux Chrome (on X11 console, only localhost networking), and it takes 12 seconds like on Intel i7 laptop:

Code: Select all

...
jscad-web.min.js:3318 total time for design regeneration 11254 5
setDesignSolids @ jscad-web.min.js:3318
invoke @ jscad-web.min.js:3021
SampleSink.event @ jscad-web.min.js:2970
MergeSink.event @ jscad-web.min.js:2958
IndexSink.event @ jscad-web.min.js:3060
i @ jscad-web.min.js:3108
u.event @ jscad-web.min.js:3108
FilterMapSink.event @ jscad-web.min.js:3012
i @ jscad-web.min.js:3108
u.event @ jscad-web.min.js:3108
u.event @ jscad-web.min.js:2825
r.run @ jscad-web.min.js:2822
s @ jscad-web.min.js:2822
Promise.then (async)
n @ jscad-web.min.js:2822
h.event @ jscad-web.min.js:2822
(anonymous) @ jscad-web.min.js:2822
t @ jscad-web.min.js:3246
a.onmessage @ jscad-web.min.js:3294
jscad-web.min.js:3318 total time for design regeneration 12387 17
...

Code: Select all

stammw:~$ nproc 
48
stammw:~$ 
During design regeneration I looked into "top" reporting — no idea why Chrome uses 1129g ram virtual space, the workstation has "only" 384GB physical RAM ...

Code: Select all

...
MiB Mem : 386139.6 total, 379065.5 free,   5054.4 used,   2019.7 buff/cache
MiB Swap: 386260.0 total, 386260.0 free,      0.0 used. 378821.7 avail Mem 

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND  
  66165 stammw    20   0 1129.5g   1.8g 119124 R 245.4   0.5   4:29.26 chrome   
  ...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Tue Aug 30, 2022 3:25 pm

I fixed the polar coordinates bug for the two vertices near north and south pole. Not the fix I wanted, instead the fix is post mortem, correcting the coordinates after they have been done wrong. Only that way I was able to handle all the different cases correctly:
https://github.com/Hermann-SW/planar_gr ... 6c118d8d84

That commit provided OpenSCAD theta angle view for vertices, this commit provided OpenSCAD phi angle view as well:
https://github.com/Hermann-SW/planar_gr ... 06c6111899

Here you can see OpenSCAD view of C36.10.a with bug (left) and with fix (right). The moved vertex is not at 246+(180/3)=306°, but even a bit further (314.6°) as determined by solving system of linear equations:

Code: Select all

./rjs node.tetra.js graphs/C36.10.a white -13
C36.10.fixed.png
C36.10.fixed.png
C36.10.fixed.png (76.86 KiB) Viewed 951 times

Since fixed code is shared, JSCAD model now is correct as well:

Code: Select all

./rjs -DJSCAD node.tetra.js graphs/C36.10.a white -11
https://openjscad.xyz/?uri=https://stam ... rect.jscad
C36.10.fixed.jscad.png
C36.10.fixed.jscad.png
C36.10.fixed.jscad.png (81.67 KiB) Viewed 951 times

White sphere does shine through a bit for OpenSCAD (can be fixed with more careful selection of numbers for sp_tria2() calls), JSCAD does not have that problem (because of much coarser number of segments for white sphere than OpenSCAD — 30 vs. 180).

Next step is to implement function "is_convex_embedding_3D()" and assert that like "is_embedding()" is asserted for all input graphs. That is still no formal proof that node.tetra.js creates always convex face sphere embeddings, but will choke on any graph that is not immediately (it would have reported C36.10.a immediately with the incorrect polar coordinates).


P.S:
Oops, there is one face that is non-convex, at one of the 4 shortest paths tetrahedron vertices; so more work is needed to convert into an all face convex embedding onto sphere:
C36.10.fixed.non-convex-face.png
C36.10.fixed.non-convex-face.png
C36.10.fixed.non-convex-face.png (44.97 KiB) Viewed 937 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Thu Sep 01, 2022 4:01 pm

I implemented function to determine the directional angle of an edge on the sphere, corresponding to OpenSCAD module alt():

Code: Select all

function al1(_p1,_p2) {
    var p1 = coords[_p1];
    var p2 = coords[_p2];
    // al/la/ph: alpha/lambda/phi | lxy/sxy: delta lambda_xy/sigma_xy
    // https://en.wikipedia.org/wiki/Great-circle_navigation#Course
    var la1 = p1[0];
    var la2 = p2[0];
    var l12 = la2 - la1;
    var ph1 = 90 - p1[1];
    var ph2 = 90 - p2[1];
    return Math.atan2(Math.cos(ph2)*Math.sin(l12), Math.cos(ph1)*Math.sin(ph2)-Math.sin(ph1)*Math.cos(ph2)*Math.cos(l12))/Math.PI*180;
}

Based on that I traversed all edges, and tested whether three successive vertices show an angle > 180° and are concave.
The three vertices 6/7/8 got reported, they correspond to the clearly concave situation from last posting bottom, with angle 227° > 180°:

Code: Select all

...
20 6 7 106.03693924504715 28.80729012948732 77.22964911555982
6 7 8 -132.91134621591198 0 227.08865378408802
concave 6 7 8
7 6 5 28.80729012948732 -126.74423497316522 155.55152510265248
...

But more sequences of vertices got reported, this one being unexpected:

Code: Select all

...
16 17 18 44.97936031256348 -57.053223022393475 102.03258333495694
17 16 15 -126.84023892044107 38.405395868308965 194.75436521124996
concave 17 16 15
17 18 8 90.45471237616199 -7.335407792586213 97.79012016874822
...
194.75° angle is not that easy to compare to 180° angle visually.
So I added black great circle are between vertices 17 and 15, and that clearly shows the angle right of 17-16-15 to be >180°:
C36.10.concave2.png
C36.10.concave2.png
C36.10.concave2.png (46.53 KiB) Viewed 856 times

I was surprised first, but then realized that my too simplistic code to place vertices between two red vertices evenly on great circle arc obviously does not do so:
https://github.com/Hermann-SW/planar_gr ... #L347-L366
I don't know what curve that code does create, but it does not place vertices on great circle arc through both red vertices.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Fri Sep 02, 2022 3:12 pm

While fixing the bug described, I found an OpenSCAD preview problem that exists on Raspberry 64bit OS as well on Intel Ubuntu 22.04. Details here:
https://www.reddit.com/r/openscad/comme ... to_report/
Image


The problem described in previous posting was caused by trying to find circular arc waypoints "the euclidean" (wrong) way.
Formulas to find waypoints on great circle arc are here:
https://en.wikipedia.org/wiki/Great-cir ... way-points

Intermediate points (ϕ,λ) on circular arc can be found with these formulas, after determining a lot of other values:
Image
Image

I implemented this in "mark()" function with this commit:
https://github.com/Hermann-SW/planar_gr ... 8167d4d8a8

But there was a problem with forumula to determine alpha0, it just does not compute correct value.
I did not find correct formula for alpha0 elsewhere, so did quick fix for my application:
https://github.com/Hermann-SW/planar_gr ... #L393-L397

Code: Select all

...
    // https://en.wikipedia.org/wiki/Great-circle_navigation#Finding_way-points
    var al0 = Math.atan2(Math.sin(al1)*Math.cos(ph1), Math.sqrt(Math.cos(al1)*Math.cos(al1)-Math.sin(al1)*Math.sin(al1)*Math.sin(ph1)*Math.sin(ph1)));
    // Wikipedia forumula for al0 is wrong ?!?!?  quick "fix", set to 45°
    al0 = Math.PI/4;
...
[ I stumbled over alpha0 formula wrong before, when implementing "edge2()" module for great circle arc graph edge. At that time I found a way to make "edge2()" work without using alpha0 ... ]

I had to increase "eps" value from 1e-6 to 1e-5, with that only one concave angle gets reported:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C36.10.a white -5
12 pentagons for graph
8 non-pentagons for graph
vertices: 7,12,26,33
max: 28
dists: 5 4 4 5 5 5
false
false
vertices: 7,12,26,33,22,21,3,4,25,17,16,15,34,5,6,8,9,11,10,0,1,2,13,14,23,24,27,28,29,30,31,32,35
concave 6 7 8 -120.00000000000001 0 240
pal: [
  [ 0.9, 0, 0 ],
  [ 0, 0.7, 0.7 ],
  [ 0, 0.9, 0 ],
  [ 0.7, 0, 0.7 ],
  [ 0, 0, 0.9 ],
  [ 0.7, 0.7, 0 ]
]
M.length: 33
pi@pi400-64:~/planar_graph_playground $ 

As reported, angle 6-7-8 has 240° > 180°, so is concave:
C36.10.concave_real.png
C36.10.concave_real.png
C36.10.concave_real.png (51.12 KiB) Viewed 786 times

With this small diff specific to graphs/C36.10.a, vertex 7 gets newly computed coordinate only ...
https://github.com/Hermann-SW/planar_gr ... f7bedd56ca

Code: Select all

 var V12 = [];
 forall_vertices(G, function(v) {
-    if ((v < 3) || (v > 2)) {
+    if ((process.argv[2] !== "graphs/C36.10.a") || (v < 7) || (v > 7)) {
         V12.push(v);
     }
 });
... by solution to systems of linear equations with only unfixed vertex 7:

Code: Select all

var coords4 = tutte.convex_face_coordinates(G, V12, coords);

forall_vertices(G, function(v) {
    if (vtype[v] === 0) {
        coords[v][0] = coords4[0][v];
        coords[v][1] = coords4[1][v];
    }
});

And indeed, no concave angle gets reported:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js graphs/C36.10.a white -10
12 pentagons for graph
8 non-pentagons for graph
vertices: 7,12,26,33
max: 28
dists: 5 4 4 5 5 5
false
false
vertices: 7,12,26,33,22,21,3,4,25,17,16,15,34,5,6,8,9,11,10,0,1,2,13,14,23,24,27,28,29,30,31,32,35
[ 19, 14, 3 ]
pal: [
  [ 0.9, 0, 0 ],
  [ 0, 0.7, 0.7 ],
  [ 0, 0.9, 0 ],
  [ 0.7, 0, 0.7 ],
  [ 0, 0, 0.9 ],
  [ 0.7, 0.7, 0 ]
]
M.length: 33
pi@pi400-64:~/planar_graph_playground $ 
Concave angle 6-7-8 is gone after moving vertex 7, can be seen here as well:
C36.10.concave_simple_fix.png
C36.10.concave_simple_fix.png
C36.10.concave_simple_fix.png (48.28 KiB) Viewed 786 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sat Sep 03, 2022 8:38 pm

HermannSW wrote:
Fri Sep 02, 2022 3:12 pm
While fixing the bug described, I found an OpenSCAD preview problem that exists on Raspberry 64bit OS as well on Intel Ubuntu 22.04. Details here:
https://www.reddit.com/r/openscad/comme ... to_report/
Image
I created github issue on the preview problem ...
https://github.com/openscad/openscad/issues/4345
... and learned a lot about OpenCSG tricks used to ensure fast preview display by comments of others.

Cause of preview problem was camera location very close (but outside) od a difference()d away part.

I learned to use "Thrown Together" as alternative to "Preview" mode, that displays all parts that get differemce()d.
And it did show that some hexagons I created for difference()ing away were faaar to big:
Image


I did a much better job in creating hexagon that is least invasive and still contains spherical triangle. Key was to determine the distance of the plane spanned by triangle vertices to origin, and use inverse to scale the three vertices, details in this github issue comment:
https://github.com/openscad/openscad/is ... 1236088218

Toggling between "Thrown Together" and "Preview" mode shows the much better hexagons created and difference()d:
Image


P.S:
OpenSCAD provides powerful vector operations, allowing to determine distance of plane through v1/v2/v3 to origin "mi" by:
https://github.com/Hermann-SW/planar_gr ... a3e441b5ce

Code: Select all

...
        n = cross(v2-v1, v3-v1);
        a = n * v1;
        mi = abs(a) / norm(n);
...        
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
HermannSW
Posts: 5423
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Sun Sep 04, 2022 4:07 pm

Much more sample graphs — now that embedding works for 4 fullerenes (C20/C36.10/C36.14.r/C60).
With those new graphs more graphs that can be embedded with currently active assertions in node.tetra.js rises.

Number of fullerenes with 2n vertices (or carbon atoms).
(starting with C20, steps of 2)
https://oeis.org/A007894

Number of isolated-pentagon (IPR) fullerenes with 2n vertices (or carbon atoms).
(starting with C60, steps of 2)
https://oeis.org/A046880

I generated all fullerenes with 20..70 vertices, they are "C" prefixed.
And I generated all independent pentagon region fullerenes with 60..100 vertices, prefixed with "I".
In order to save space I used this build script I created in plantri52 folder, which gzips all files:

Code: Select all

#!/bin/bash
rm -rf graphs
mkdir graphs
for((i=20; i<=70; i+=2))
do
  echo C$i; ./fullgen $i code 6 2>err | gzip -9 > graphs/C$i.txt.gz
done
for((i=60; i<=100; i+=2))
do
  echo I$i; ./fullgen $i code 6 ipr 2>err | gzip -9 > graphs/I$i.txt.gz
done
The compression resulted in only 1284KB for all 31846 graphs together:
new_fullerenes.png
new_fullerenes.png
new_fullerenes.png (20.51 KiB) Viewed 656 times
In order to access these graphs, new tool "ful" is used, and "ipr" is a symbolic link to it:
https://github.com/Hermann-SW/planar_gr ... b/main/ful

Passing one argument returns the number of graphs for the number of vertices:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./ful 60 
1812
pi@pi400-64:~/planar_graph_playground $ ./ipr 82
9
pi@pi400-64:~/planar_graph_playground $ ./ful 36
15
pi@pi400-64:~/planar_graph_playground $ 

Passing index additionally returns the extracted and converted to adjacency list graph:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./ful 36 10
[[13,14,1],[0,2,32],[1,23,3],[2,4,33],[3,21,5],[4,6,34],[5,20,7],[6,8,27],[7,18,9],[8,10,28],[9,16,11],[10,12,29],[11,15,13],[12,0,30],[0,15,24],[14,12,16],[15,10,17],[16,18,25],[17,8,19],[18,20,26],[19,6,21],[20,4,22],[21,23,26],[22,2,24],[23,14,25],[24,17,26],[25,19,22],[7,28,35],[27,9,29],[28,11,30],[29,13,31],[30,32,35],[31,1,33],[32,3,34],[33,5,35],[34,27,31]]
pi@pi400-64:~/planar_graph_playground $ diff graphs/C36.10.a <(./ful 36 10)
pi@pi400-64:~/planar_graph_playground $ 
All this is done because I did not want to create each and every graph separately, now only 47 files got added:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ls graphs/[CI]*txt.gz | wc
     47      47     847
pi@pi400-64:~/planar_graph_playground $ 

I embedded I82.1 with node.tetra.js, and two concave angles were reported:

Code: Select all

pi@pi400-64:~/planar_graph_playground $ ./rjs node.tetra.js <(./ipr 82 1) white -10
12 pentagons for graph
31 non-pentagons for graph
vertices: 0,34,45,70
max: 42
dists: 7 7 7 7 7 7
false
false
vertices: 0,34,45,70,46,27,28,69,11,12,58,59,60,50,51,33,71,72,73,74,75,19,1,2,3,6,5,4,7,8,9,10,29,30,31,32,47,48,49,62,63,64,65,66,67,68,76,77,78,79,80,81
[ 28, 24, 30 ]
concave 33 34 6 -120 0 240
concave 80 70 69 20.250103470494917 180 200.2501034704949
pal: [
  [ 0.9, 0, 0 ],
  [ 0, 0.7, 0.7 ],
  [ 0, 0.9, 0 ],
  [ 0.7, 0, 0.7 ],
  [ 0, 0, 0.9 ],
  [ 0.7, 0.7, 0 ]
]
M.length: 52
pi@pi400-64:~/planar_graph_playground $ 

These are the two concave angles with 240° and 200.25° in center:
C82.1.anim.gif
I82.1.anim.gif
C82.1.anim.gif (95.62 KiB) Viewed 656 times
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

Return to “Other programming languages”