Winged-edge data structure: what can it do ?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Winged-edge data structure: what can it do ?

runsun
Lets say if we can create a winged-edge data structure, or anything similar
to it, in OpenSCAD. For what features is this structure good at? Like,
inserting a data point, edge-flipping, etc ? Can someone familiar with this
field give more complete insight or pointers ? I've spent quite sometime
crawling on the web, but all I could find so far about this structure is the
definition.



-----

$  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets

--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Winged-edge data structure: what can it do ?

NateTG
It's an alternative to split edges data structures, so it's an option if you
want to do subdivision surfaces or irregular meshes.

https://www.youtube.com/watch?v=9uscFr2Hht0

You want a structure like that whenever you're doing an algorithm that
involves interaction between adjacent faces, and the faces are not in a nice
grid.




--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Winged-edge data structure: what can it do ?

runsun
Thx. Obviously I was looking at the wrong places. Nice video. I went through
the class.



-----

$  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets

--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Winged-edge data structure: what can it do ?

Neon22
In reply to this post by runsun
A winged edge data structure has some very useful properties. One of
which is most useful to us.
An object without errors is manifold and as a result water tight. Any
operation performed on it - that maintains the structure - will keep it
that way.

I used this for years on the old Symbolics machines written in LISP
(S-Geometry) and the current working derivative is Wings3D which I use
for all my geometric modelling (not procedural and not biological (Zbrush)).

- http://www.wings3d.com/

If the internal poly rep in OpenSCAD was winged edge then it would
always be safe to do boolean ops.
The problem is when you import a polygonal model from most formats - an
object that is poorly formed has no way to be properly inserted into the
data structure.
The best thing to do - if we went down this path - is to complain and
fail to load. Let the user fix it somewhere else.

Because of the winged edge nature, it is generally implemented as a
bunch of methods to do any operation so no one manipulates the structure
directly and screws it up.
You can see the OS implementation in Wings3D which is regrettably in Erlang.

here's some omre info on winged edge
- http://pages.mtu.edu/%7Eshene/COURSES/cs3621/NOTES/model/winged-e.html


On 3/27/2018 5:47 AM, runsun wrote:

> Lets say if we can create a winged-edge data structure, or anything similar
> to it, in OpenSCAD. For what features is this structure good at? Like,
> inserting a data point, edge-flipping, etc ? Can someone familiar with this
> field give more complete insight or pointers ? I've spent quite sometime
> crawling on the web, but all I could find so far about this structure is the
> definition.
>
>
>
> -----
>
> $  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Winged-edge data structure: what can it do ?

runsun
Thx Neon. Now that reading this, I recall seeing you mentioned it before
(like 2 yr ago?). I also barely recall that you created and applied some
other data structure to OpenSCAD, like half-edge or something ? Do I
remember it correctly ?



-----

$  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets

--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Winged-edge data structure: what can it do ?

Neon22
Hi Runsun,
Alas no it was not I.
This is a useful discussion about both:
-
https://groups.google.com/forum/#!topic/comp.graphics.algorithms/_OPr5jMV7MM

FWIW I prefer the designation CW and CCW for labelling of the edges at
the vertex.
WEDS is primarily an edge structure and is best mentally understood by
placing yourself on an edge - which will have a left and right face and
exactly two vertices. One at the head and tail (hence direction). There
may be many edges also using the (say) head vertex but only one will be
the most CCW and one will be the most CW edge.
So the edgelist can be traversed to cover the entire geometery.

new faces and edges and vertices can be inserted and removed by
following simple rules considering this basic concept. The surface is
always topologically correct.

There is a halfedge implementation here in python for readability but HE
is NG for our use.
- https://github.com/yig/trimesh but its not written very clearly
WE vs HE
- https://stackoverflow.com/questions/34548207/winged-edge-vs-half-edge

Here's a winged edge in LUA
- https://github.com/karai17/lua-winged-edge
but the wings3d code is better IMHO


On 3/28/2018 4:37 AM, runsun wrote:

> Thx Neon. Now that reading this, I recall seeing you mentioned it before
> (like 2 yr ago?). I also barely recall that you created and applied some
> other data structure to OpenSCAD, like half-edge or something ? Do I
> remember it correctly ?
>
>
>
> -----
>
> $  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org