Pantograph 0.5 is out.

rocketship · November 1, 2008, 1:03pm

Migius,

That’s strange…it could be because its just drawing new shapes on top of each other. The code that I removed was an attempt to remove the previous shapes before drawing new ones…

I had hoped that libMing was optimized not to draw shapes that were completely hidden, but maybe not.

RS

alxarch · November 2, 2008, 4:11am

as migius said we were on our way to develop a solution for vector rendering since we thought you ve given up. I am finishing with a polygon clipper for python that’s weiler-style. The problem with weiler is the handling of special caces. it is far more efficient than the sutherland clipper that you have used for pantograph. so when i get back home i will read your code to manage to find a way to connect my clipper. We had preffered to avoid the bsp tree solution for sorting and resorted to brute force clipper detection. But your solution seems better, since you handle backfaces and hidden parts already. Will be in touch. Mail me if you want at alxarch ^ at ^ gmail ^ dot ^ com

Cheers,
alxarch

PS Congratulations for the newborn!, and as we say in greece:
Να σου ζήσει!

rocketship · November 2, 2008, 9:26am

alxarch,

I don’t think the BSP-Sorting is the bottleneck anymore (though its still slow). The limit is really in 2d clipping, especially if we replace Polygon for 2d clipping. The current method is still pretty brute-force: I think to improve on Polygon we’d have to code smarter, not just replace what Polygon does right now…

RS

alxarch · November 2, 2008, 9:40am

right now i think what’s the most slow part of the code is the classifications. The checks not as fast aas they could be and they are repeted on various places because of the functions. Clipping should happen on poly level and not on edge level as it is happening now. Don’t bother for now though, fix the bugs and when i am done with the clipper wee will all sit down and revise the classes to come up with a faster scheme. On the google doc there’s no explanation of the hidden faces handling.
Cheers,
alxarch

PS my clipper got delayed because of the special cases handling. I hope i’ll have it finishedd by next Monday. I see in your code that you use a lot of stuff from wolfram math, check out geometryalgorithms.com also, they have very optimised stuff.

rocketship · November 3, 2008, 4:21pm

alxarch,

Hmmm…I’m not sure what you mean by clipping on the polygon level v. edge level. Clipping the edges means that each edge is only clipped once, instead of twice (since each edge is shared by two polygons). It would be great to speed up classification - I think if there’s any candidate for a C function, that would be it. We’re already caching the classifications a fair amount where possible…

I look forward to seeing the new clipping module - I’ve spent entirely too long looking at this one!

cheers,
RS

PS Hidden faces are fairly easy, actually - once we know they’re hidden, we only have to track the important edges, and no further clipping is necessary - they’re just held until the drawing stage.

Rickyx · November 4, 2008, 5:58pm

I did it all but I get from console (WinVista32bit):

 
   File "&lt;string&gt;", line 1, in &lt;module&gt;
   File "C:\Program Files\Blender Foundation\Blender\.blender\scripts\pantograph.py", line 38, in &lt;module&gt;
         import pantographLib
    File "C:\Program Files\Blender Foundation\Blender\.blender\scripts\pantographLib.py", line 71, in &lt;module&gt;
         setTolerance&lt;EPSILON2D&gt;
#this controls the tolerance of the Polygon package
NameError: name "setTolerance" is not defined

What I did wrong?

migius · November 4, 2008, 11:36pm

hi Rickyx,
setTolerance<EPSILON2D> error means the Polygon Library is not properly installed.
I have tested on winXP, don’t know if Vista accepts the same libraries.
migius

rocketship · November 5, 2008, 8:01am

I updated the “bleeding edge” version. More clipping improvements.

migius · November 5, 2008, 8:56am

There are still clipping artifacts with my test model. Watching for the next update

/uploads/default/original/3X/5/1/51aa6e0a28d4e51b8a5d4dbfa4724089af23467c.pngd=1225905176

bug report: pantograph.py, line 001: the white space before #BPY blocks registering in scripts menu (tested on winXP platform).

rocketship · November 5, 2008, 9:52am

Migius-
AHA! I could not figure out why it wasn’t showing up in the scripts menu!

I’m still having a funny problem where the segment-combining algorithm (combinePolylines) doubles back on itself and breaks the chain…

thanks,
RS

migius · November 5, 2008, 9:58am

Go to blender scripts folder, there is the newest version included in 2.48a release.
Or get it from svn on projects.blender.org

hope you will not break your work on sorting and clipping routines.

alxarch · November 5, 2008, 11:07am

you need to insall polygon library
http://download.dezentral.de/soft/Python/Polygon/

alxarch · November 5, 2008, 11:29am

damn! small screen, migius had already answered that one
@ rokcketship:
there are still artifacts. Intersecting edges don’t show up in the version which lies in our svn. Is there an svn repo of pantograph so i can monitor your changes?
ok i am currently revising your code

first comment: converting meshes to screen space can happen by multiplying verts locations with an ortho or a perspective matrix and it will be really faster
second comment: I changed the classifying functions and the split face face to be faster and saner. lots of stuff changed but i still don’t get the edges in the intersecting lines to show up, have you fixed this?
third comment: your idea about clipping only edges is nice but it requires to retain mesh connectivity data which really slows down clipping and splitting (lots of if a in list) which ends up slowing down things. In my polygon clipping approach i use only polygons (meaning converting each face into a separate polygon) that way the program needs more memory but not a lot since python is great at handling duplicate data in memory. I really think keeping mesh connectivity data should be replaced by independent polygons. The problem then will be creases which should be handled with edge flags during mesh2poly conversion. This would also speed up rendering and exporting and sorting.
fourth comment (the good one): i like the interface

i’ll be in touch, i’ll post my changes as soon as i finish revising your code. I will also attempt a rewrite of the core to use polygons instead of mesh data. (Things would be really easier to debug and extend with independent polys)

migius · November 5, 2008, 11:46am

look at the the “bleeding edge” version above in this thread.
I will add this version branch to our svn now. Although Rocketship is not registered there yet…

Edit: @akxarch: bleedingEdge added to svn.

rocketship · November 5, 2008, 1:39pm

@Migius,

I think I’m registered… at least on Blender Projects…

@alxarch

#1 - ummm…yeah. Do you know of another way?
Currently it’s Object Space>Camera Space> [clipping] >Screen Coords

#2 - By intersecting edges, do you mean intersections between surfaces? This is the “Material Silhouette” linetype - basically, it just draws a polyline around each material, creating a division between intersecting surfaces as long as they have different materials.

#3 - Sets are much faster than lists in places where you don’t need to maintain an order - and the code ends up being much shorter. I’m not sure how you are planning to maintain linetype data, beyond silhouettes… I agree that poly-only clipping would be far faster, but how do we keep from losing edge data?

-RS

alxarch · November 5, 2008, 3:22pm

#1
as i said, multiplying vert coords directly with the camera inverse matrix or with a perspective inverse matrix translates the cords directly(also multiply with object’s matrix)
#2
by intersecting edges i mean this edges at the split of two faces that intersect, no matter what materials, and it should be handled as a mesh linetype.

#3
on a polygon each edge can have it’s flags stored on the first vertex. Edge flags can be inherrited by blender’s edge flags(ie NGONS) or by other checks during mesh conversion (sihlouete for example can be the edges at the xy limits of the object where xy in camera space coords). Also planer islands (coplanar faces) can be found during this phase. The only problem i can see right now is the case of a series of coplanar faces creating a polygon with a hole. This scould also be handled by polygon clipping since holes just need their order reversed and the clipping code adjusted to handle them but in the beginning we could just keep the outer ring. I will try to make a prototype to demonstrate the classes i have in mind. My polygon clipper is near completion. i just need to handle one special cases or two but now i use an improved weiler-atherton that handles special cases more delicately and i need to adjust the rules a bit to fit the special cases.

alxarch · November 5, 2008, 6:33pm

i had posted an answer already but it didn’t came through so here it is again:
#1:
my mistake, got confused by other part of the code. Still i see (yet) no use of linking the mesh to a proxy object and to the scene
#2:
i mean that it should function just like hidden lines shading in cad software
#3:
ok i have spent my evening exploring more of the bleeding edge code
i think that things get complicated a lot because of the connectivity handling
since all conversion of blender mesh to pantograph goes through getFromObject and we have a temp Mesh to play with (without affecting real geometry) i suggest the following:

explore the temp mesh, flagging edges as necessary(NGON,SHARP), if there are no flags available (ie silhouette) use a hack(ie select the edge) or use an aligned list of flags.
then convert all faces to polygons with edge flags on the first vertex of each edge. Polygons are collections of Points and Points have prev, next, flags etc. Polygons hold material, layer, object data etc and have related methods (ie point inside, split2Poly)
create the BSPTree of all polys
clip all polys
produce flatten drawing (all remaining polys)
convert all polys to desired output (here flags kick in again and depending on output)

The only part i have no idea how it’s getting affected is the interactivity of the interface. If it needs connectivity data to work then i am talking out my ass here. But logically it needs none.

Cheers,
alxarch

PS i will send my modifications for classifications and splitting tomorrow (it should give a small performance boost)

rocketship · November 6, 2008, 5:07am

alxarch,

Yes, getting rid of the proxy objects would be nice - but it seemed like a shorthand way of converting non-mesh objects and modifiers to meshes. Also, it was important to be able to grab the original “mesh” edges, but then also the triangulation is vital - using Blender’s built-in triangulation only made sense.
I think intersection edges will be easier with your clipping - with the BSP, because you’re only clipping with infinite planes, finding the actual edge of intersection is definitely non-trivial!
I thought about this several times, as most of the fast clipping algorithms(and Blender’s mesh module) only track verts and polys, not full connectivity. But isn’t tracking vert indexes basically a half-edge data structure? (Each edge has two halves, one going each direction and attached to an adjoining face) I would love to implement a HE structure, if I understood them better!

Looking forward to the code…

RS

carbon2 · November 6, 2008, 5:44am

does anyone tried if it is working on mac? plus what i need to install? thanks

rocketship · November 6, 2008, 9:27am

c2,

I have received queries from people trying to install it, but no confirmation that they have installed it. In theory, all of the dependencies should be cross-platform, but I would have no clue where to begin.

RS