Open FishOrBear opened 4 years ago
@FishOrBear this is really good. I’m not too surprised as that code needs some rework, and the transition to V2 was not straight forward.
Anyway, I’ll take a look at this. Do you want to follow along? If so then I can post updates.
Can this result be without overlapping triangles?
how do you want to do it
@FishOrBear you seem to have specific requirements for the results. Are there errors in the polygons after this routine finishes?
It looks like there is only overlap now.
I want to extract the edge lines of a mesh through a polygon.
For example:
I temporarily turned off the function of reTesselate in order to achieve my purpose.
There are of course other solutions to extract edges.
Extracting the edges of a 3D geometry would be something very special.
In general, the goal of reTesselate is to combine small polygons. The CSG boolean operations tend to chop polygons into smaller and smaller polygons. Therefore, reTesselate was born to combine co-planar polygons that share opposing edges.
But the result will never be anything close to the 'edges'.
Well, I have another algorithm to extract it. It's just that I don't want the triangles to overlap.
So I temporarily closed reTesselate
You have sad that twice now.... ‘triangles overlap’.
Can you provide two overlapping triangles from the example above?
I’m asking because I rewrote reTesselate. The new algorithm does not create any new 3D vertices, so overlapping will not be possible. But I’d like to have a test case.
I think this use case will work
//s
let geo = geom3.fromPoints([[[585.9650675011303, 654.0333333399891, 0], [585.9650675011303, 0, 0], [1287.9139404296875, 0, 0], [585.9650675011303, 654.0333333399891, 0]], [[585.9650675011303, 654.0333333399891, 0], [1287.9139404296875, 0, 0], [1287.9139404296875, 1200, 0], [585.9650675011303, 1200, 0], [585.9650675011303, 654.0333333399891, 0]], [[585.9650675011303, 487.06177308554817, 0], [0, 487.06177308554817, 0], [0, 0, 0], [585.9650675011303, 0, 0], [585.9650675011303, 487.06177308554817, 0]], [[585.9650675011303, 953.0992486712241, 0], [585.9650675011303, 1200, 0], [569.7829030842556, 1200, 0], [585.9650675011303, 953.0992486712241, 0]], [[41.815788313545774, 1161.038587749494, 0], [0, 1200, 0], [0, 1163.7793495535184, 0], [41.815788313545774, 1161.038587749494, 0]], [[580.192984433049, 1041.1672975136432, 0], [569.7829030842556, 1200, 0], [399.0792683898784, 1200, 0], [580.192984433049, 1041.1672975136432, 0]], [[89.10858823427716, 1116.974028679698, 0], [41.815788313545774, 1161.038587749494, 0], [0, 1163.7793495535184, 0], [0, 1111.133491795949, 0], [89.10858823427716, 1116.974028679698, 0]], [[513.8373819542935, 1099.3596856831782, 0], [399.0792683898784, 1200, 0], [363.21825136572335, 1200, 0], [513.8373819542935, 1099.3596856831782, 0]], [[212.83043043921808, 1001.6975292294348, 0], [89.10858823427716, 1116.974028679698, 0], [0, 1111.133491795949, 0], [0, 683.1732572016322, 0], [212.83043043921808, 1001.6975292294348, 0]], [[581.0924424726376, 1027.443739895384, 0], [580.192984433049, 1041.1672975136432, 0], [531.96799718878, 1083.4595391987045, 0], [581.0924424726376, 1027.443739895384, 0]], [[218.0567931242633, 996.827921854922, 0], [212.83043043921808, 1001.6975292294348, 0], [0, 683.1732572016322, 0], [0, 554.6549147914332, 0], [218.0567931242633, 996.827921854922, 0]], [[493.78635656364474, 1112.7573297261627, 0], [363.21825136572335, 1200, 0], [316.8756808655663, 1200, 0], [493.78635656364474, 1112.7573297261627, 0]], [[49.1383416291427, 487.06177308554817, 0], [221.18866516331374, 993.9098336745839, 0], [218.0567931242633, 996.827921854922, 0], [0, 554.6549147914332, 0], [0, 487.06177308554817, 0], [49.1383416291427, 487.06177308554817, 0]], [[581.9527194048013, 1014.3179913595105, 0], [581.0924424726376, 1027.443739895384, 0], [547.8681436727304, 1065.3288629296528, 0], [581.9527194048013, 1014.3179913595105, 0]], [[49.1383416291427, 487.06177308554817, 0], [121.3387404549834, 487.06177308554817, 0], [222.00728710207946, 993.1470914635701, 0], [221.18866516331374, 993.9098336745839, 0], [49.1383416291427, 487.06177308554817, 0]], [[472.1581827354736, 1123.4231622457141, 0], [316.8756808655663, 1200, 0], [246.57062466362078, 1200, 0], [472.1581827354736, 1123.4231622457141, 0]], [[218.827738399571, 977.1627252339831, 0], [121.3387404549834, 487.06177308554817, 0], [186.70594798035887, 487.06177308554817, 0], [218.827738399571, 977.1627252339831, 0]], [[582.7833584469377, 1001.6444454540801, 0], [581.9527194048013, 1014.3179913595105, 0], [561.265848751198, 1045.2778985736759, 0], [582.7833584469377, 1001.6444454540801, 0]], [[217.2505899620678, 953.0992486714372, 0], [186.70594798035887, 487.06177308554817, 0], [217.2505899620678, 487.06177308554817, 0], [217.2505899620678, 953.0992486714372, 0]], [[449.3229776573378, 1131.174688124625, 0], [246.57062466362078, 1200, 0], [103.31238340676235, 1200, 0], [449.3229776573378, 1131.174688124625, 0]], [[583.5925177127425, 989.2986290648014, 0], [582.7833584469377, 1001.6444454540801, 0], [571.9316202354629, 1023.6497247457753, 0], [583.5925177127425, 989.2986290648014, 0]], [[41.815788313545795, 1161.038587749494, 0], [425.6712442587688, 1135.8792779683997, 0], [103.31238340676235, 1200, 0], [0, 1200, 0], [41.815788313545795, 1161.038587749494, 0]], [[584.3879190636148, 977.1627252339455, 0], [583.5925177127425, 989.2986290648014, 0], [579.6833292198446, 1000.8144586324776, 0], [584.3879190636148, 977.1627252339455, 0]], [[401.6077676964492, 1137.45648744104, 0], [41.815788313545795, 1161.038587749494, 0], [89.1085882342773, 1116.9740286796978, 0], [401.6077676964492, 1137.45648744104, 0]], [[299.0498522338729, 1130.7344273136287, 0], [89.1085882342773, 1116.9740286796978, 0], [212.8304304392181, 1001.6975292294347, 0], [299.0498522338729, 1130.7344273136287, 0]], [[313.539283885475, 1131.6841232033587, 0], [299.0498522338729, 1130.7344273136287, 0], [255.34739172003987, 1065.3288629295075, 0], [313.539283885475, 1131.6841232033587, 0]], [[241.94980871197896, 1045.2778985736684, 0], [212.8304304392181, 1001.6975292294347, 0], [218.05679312426327, 996.827921854922, 0], [241.94980871197896, 1045.2778985736684, 0]], [[327.26313294742744, 1132.5836397171047, 0], [313.539283885475, 1131.6841232033587, 0], [271.2475382041619, 1083.4595391987518, 0], [327.26313294742744, 1132.5836397171047, 0]], [[231.28391515742027, 1023.6497247458037, 0], [218.05679312426327, 996.827921854922, 0], [221.18866516331377, 993.9098336745839, 0], [231.28391515742027, 1023.6497247458037, 0]], [[340.3887518543665, 1133.4439458095596, 0], [327.26313294742744, 1132.5836397171047, 0], [289.3782755088521, 1099.3596856831293, 0], [340.3887518543665, 1133.4439458095596, 0]], [[223.53245031363113, 1000.814458632408, 0], [221.18866516331377, 993.9098336745839, 0], [222.00728710207954, 993.14709146357, 0], [223.53245031363113, 1000.814458632408, 0]], [[353.06188489489995, 1134.2745941502255, 0], [340.3887518543665, 1133.4439458095596, 0], [309.429178829119, 1112.7573297260667, 0], [353.06188489489995, 1134.2745941502255, 0]], [[365.40875752726663, 1135.0838580656036, 0], [353.06188489489995, 1134.2745941502255, 0], [331.0573526576802, 1123.4231622458103, 0], [365.40875752726663, 1135.0838580656036, 0]], [[377.54441320450195, 1135.879277968397, 0], [365.40875752726663, 1135.0838580656036, 0], [353.89267980570315, 1131.1746881245763, 0], [377.54441320450195, 1135.879277968397, 0]]])
//e
@FishOrBear thanks
small comment... 3D polygons contain order sets of unique points. the data provided has an redundant first and last point.
Here's the result of the new reTesselate function. Only 27 polygons. 😃
let shape1 = geometry.geom3.fromPoints([
[ [ 585.965087890625, 0, 0 ],
[ 1287.9139404296875, 0, 0 ],
[ 1287.9139404296875, 1200, 0 ],
[ 585.965087890625, 1200, 0 ] ],
[ [ 585.965087890625, 487.061767578125, 0 ],
[ 0, 487.061767578125, 0 ],
[ 0, 0, 0 ],
[ 585.965087890625, 0, 0 ] ],
[ [ 585.965087890625, 953.0992431640625, 0 ],
[ 585.965087890625, 1200, 0 ],
[ 569.7828979492188, 1200, 0 ] ],
[ [ 41.81578826904297, 1161.03857421875, 0 ],
[ 0, 1200, 0 ],
[ 0, 1163.779296875, 0 ] ],
[ [ 580.1929931640625, 1041.1673583984375, 0 ],
[ 569.7828979492188, 1200, 0 ],
[ 399.0792541503906, 1200, 0 ] ],
[ [ 0, 1163.779296875, 0 ],
[ 0, 1111.133544921875, 0 ],
[ 89.10858917236328, 1116.9739990234375, 0 ],
[ 401.6077575683594, 1137.45654296875, 0 ],
[ 41.81578826904297, 1161.03857421875, 0 ] ],
[ [ 513.83740234375, 1099.3597412109375, 0 ],
[ 399.0792541503906, 1200, 0 ],
[ 363.21826171875, 1200, 0 ] ],
[ [ 212.83042907714844, 1001.697509765625, 0 ],
[ 89.10858917236328, 1116.9739990234375, 0 ],
[ 0, 1111.133544921875, 0 ],
[ 0, 683.1732788085938, 0 ] ],
[ [ 581.0924682617188, 1027.4437255859375, 0 ],
[ 580.1929931640625, 1041.1673583984375, 0 ],
[ 531.968017578125, 1083.4595947265625, 0 ] ],
[ [ 218.05679321289062, 996.8279418945312, 0 ],
[ 212.83042907714844, 1001.697509765625, 0 ],
[ 0, 683.1732788085938, 0 ],
[ 0, 487.061767578125, 0 ],
[ 121.33873748779297, 487.061767578125, 0 ],
[ 222.00729370117188, 993.1470947265625, 0 ],
[ 221.18865966796875, 993.9098510742188, 0 ] ],
[ [ 493.7863464355469, 1112.75732421875, 0 ],
[ 363.21826171875, 1200, 0 ],
[ 316.87567138671875, 1200, 0 ] ],
[ [ 581.9526977539062, 1014.3179931640625, 0 ],
[ 581.0924682617188, 1027.4437255859375, 0 ],
[ 547.8681640625, 1065.328857421875, 0 ] ],
[ [ 472.1581726074219, 1123.4232177734375, 0 ],
[ 316.87567138671875, 1200, 0 ],
[ 246.57061767578125, 1200, 0 ] ],
[ [ 218.82774353027344, 977.1627197265625, 0 ],
[ 121.33873748779297, 487.061767578125, 0 ],
[ 186.70594787597656, 487.061767578125, 0 ] ],
[ [ 582.7833862304688, 1001.6444702148438, 0 ],
[ 581.9526977539062, 1014.3179931640625, 0 ],
[ 561.265869140625, 1045.2779541015625, 0 ] ],
[ [ 217.25059509277344, 953.0992431640625, 0 ],
[ 186.70594787597656, 487.061767578125, 0 ],
[ 217.25059509277344, 487.061767578125, 0 ] ],
[ [ 449.3229675292969, 1131.1746826171875, 0 ],
[ 246.57061767578125, 1200, 0 ],
[ 103.31238555908203, 1200, 0 ] ],
[ [ 583.592529296875, 989.2986450195312, 0 ],
[ 582.7833862304688, 1001.6444702148438, 0 ],
[ 571.931640625, 1023.6497192382812, 0 ] ],
[ [ 41.81578826904297, 1161.03857421875, 0 ],
[ 425.6712341308594, 1135.8792724609375, 0 ],
[ 103.31238555908203, 1200, 0 ],
[ 0, 1200, 0 ] ],
[ [ 584.387939453125, 977.1627197265625, 0 ],
[ 583.592529296875, 989.2986450195312, 0 ],
[ 579.683349609375, 1000.814453125, 0 ] ],
[ [ 299.04986572265625, 1130.734375, 0 ],
[ 89.10858917236328, 1116.9739990234375, 0 ],
[ 212.83042907714844, 1001.697509765625, 0 ] ],
[ [ 313.5392761230469, 1131.68408203125, 0 ],
[ 299.04986572265625, 1130.734375, 0 ],
[ 255.34739685058594, 1065.328857421875, 0 ] ],
[ [ 241.94981384277344, 1045.2779541015625, 0 ],
[ 212.83042907714844, 1001.697509765625, 0 ],
[ 218.05679321289062, 996.8279418945312, 0 ] ],
[ [ 327.26312255859375, 1132.5836181640625, 0 ],
[ 313.5392761230469, 1131.68408203125, 0 ],
[ 271.2475280761719, 1083.4595947265625, 0 ] ],
[ [ 231.28392028808594, 1023.6497192382812, 0 ],
[ 218.05679321289062, 996.8279418945312, 0 ],
[ 221.18865966796875, 993.9098510742188, 0 ] ],
[ [ 340.3887634277344, 1133.4439697265625, 0 ],
[ 327.26312255859375, 1132.5836181640625, 0 ],
[ 289.3782653808594, 1099.3597412109375, 0 ] ],
[ [ 223.53245544433594, 1000.814453125, 0 ],
[ 221.18865966796875, 993.9098510742188, 0 ],
[ 222.00729370117188, 993.1470947265625, 0 ] ],
[ [ 353.0618896484375, 1134.2745361328125, 0 ],
[ 340.3887634277344, 1133.4439697265625, 0 ],
[ 309.4291687011719, 1112.75732421875, 0 ] ],
[ [ 365.40875244140625, 1135.0838623046875, 0 ],
[ 353.0618896484375, 1134.2745361328125, 0 ],
[ 331.0573425292969, 1123.4232177734375, 0 ] ],
[ [ 377.5444030761719, 1135.8792724609375, 0 ],
[ 365.40875244140625, 1135.0838623046875, 0 ],
[ 353.8926696777344, 1131.1746826171875, 0 ] ],
])
This result is very good, can I experience it on the current v2 branch? If the algorithm is available, I can test more examples.
update:
I have seen it on https://github.com/jscad/OpenJSCAD.org/pull/499
and I am ready to try
The new function is still under testing. Please wait a few more days.
@z3dev OK, look forward to your good news.
ver:V2
Primitive triangle mesh![image](https://user-images.githubusercontent.com/19372111/71963172-09aa4d00-3236-11ea-9d78-7e1f5f1fc117.png)
reTesselateCoplanarPolygons (draw line![image](https://user-images.githubusercontent.com/19372111/71963177-0f079780-3236-11ea-8971-e433ec588453.png)
reTesselateCoplanarPolygons (draw face![image](https://user-images.githubusercontent.com/19372111/71963193-1af35980-3236-11ea-93fa-0ca5ab43765d.png)
testcode:
Is this expected?
v0.7 testcode:
v0.7 dest count:35 v2 dest count:54
Is there an overlap in the generated polygon, is this also expected?