5 ms·

Yeah, the painter's algorithm fails with certain geometries, like when polygons intersect each other, or when they overlap in a certain way. Maybe I should com

Yeah, the painter's algorithm fails with certain geometries, like when polygons intersect each other, or when they overlap in a certain way. Maybe I should compare min positions rather than centroids, but I don't think that would fix those cases. I think the only real fix involves splitting up the polygons for the failure cases, which seems complex.

namirez 7y ago
You're right! The min positions won't resolve the issue either and, unfortunately, there is no trivial fix for it. Handling intersecting polygons, as you said, is a bit more complex, but for overlapping polygons it's possible to find the Z-order robustly by computing the intersections with the line of sight.
- ZenPsycho 7y ago
  perhaps you could preprocess the shape using the Binary Space Partitioning (BSP) algorithm. there’s a step in the algorithm that finds polygons that would cause z-sorting conflict and splits them along the exact line you need to resolve the conflict. you end up with a data structure that gives you the z sorting order for any camera angle.
JoshTriplett 7y ago
If you have only one camera angle, you can certainly do polygon intersection to avoid dealing with overlapping polygons. It's not necessarily going to be as efficient (or rather, as hardware-acceleratable) as computing Z at each point and maintaining a Z-buffer, but that would assume a fixed resolution.
- whatshisface 7y ago
  This isn't raster rendering, he is producing an SVG file.
  - JoshTriplett 7y ago
    You're entirely right; I've edited my comment accordingly. Thank you.
klodolph 7y ago
Centroids is a reasonable approximation, if your geometry is not very coarse. PlayStation games often used this because the hardware lacked a depth buffer.
bayesian_horse 7y ago
For triangles only the intersection case matters. General Polygons could be a bit more complicated. As long as the object is watertight, it's easier. I recently ran into similar problems to be solved in Python, because I am trying to build a replacement for OpenSCAD by duct-taping together various Python packages. Shapely is quite useful for 2D geometry (like intersection and stuff). PyMesh is extremely useful for 3D meshes, but hard to build. There are some non photorealistic rendering (NPR) options for Blender, many of them implemented in Python. I don't know if they can output SVG data currently. ThreeJs has an SVG engine, meaning a backend that outputs SVG.
- sitkack 7y ago
  > build a replacement for OpenSCAD I am very interested in this.
  - williamaadams 7y ago
    There was quite a lot of openscad replacement going on in 2011. I even made a lua based alternative.
  - bayesian_horse 7y ago
    My first attempt was using the Blender API, you can take a look at https://github.com/akloster/blender-vraag https://github.com/akloster/blender-vraag Currently I am trying to reimplement the "construct" part with Pymesh and Shapely, but I haven't published it yet.
  - tapia 7y ago
    Have you tried python-occ? http://www.pythonocc.org/ http://www.pythonocc.org/
    - bayesian_horse 7y ago
      Thank you for the suggestion. I hadn't seen that yet. From a cursory look it's not completely what I am looking for, but maybe it can be useful. One of the problems for me is that I am sort of stumbling into this "CAD" thing from a coding perspective. CAD programs like Fusion 360° or FreeCAD seem a bit too complicated for me, and through my grappling with the concepts I am reinventing some concepts/tools. Particularly I want to develop 3D printed objects the same way I would do data science: Start with Jupyter notebooks, iterate, maybe end up with parametric Python scripts.

namirez 7y ago

You're right! The min positions won't resolve the issue either and, unfortunately, there is no trivial fix for it. Handling intersecting polygons, as you said, is a bit more complex, but for overlapping polygons it's possible to find the Z-order robustly by computing the intersections with the line of sight.

ZenPsycho 7y ago
perhaps you could preprocess the shape using the Binary Space Partitioning (BSP) algorithm. there’s a step in the algorithm that finds polygons that would cause z-sorting conflict and splits them along the exact line you need to resolve the conflict. you end up with a data structure that gives you the z sorting order for any camera angle.

JoshTriplett 7y ago

If you have only one camera angle, you can certainly do polygon intersection to avoid dealing with overlapping polygons. It's not necessarily going to be as efficient (or rather, as hardware-acceleratable) as computing Z at each point and maintaining a Z-buffer, but that would assume a fixed resolution.

whatshisface 7y ago
This isn't raster rendering, he is producing an SVG file.
- JoshTriplett 7y ago
  You're entirely right; I've edited my comment accordingly. Thank you.

klodolph 7y ago

Centroids is a reasonable approximation, if your geometry is not very coarse. PlayStation games often used this because the hardware lacked a depth buffer.

bayesian_horse 7y ago

For triangles only the intersection case matters. General Polygons could be a bit more complicated. As long as the object is watertight, it's easier. I recently ran into similar problems to be solved in Python, because I am trying to build a replacement for OpenSCAD by duct-taping together various Python packages. Shapely is quite useful for 2D geometry (like intersection and stuff). PyMesh is extremely useful for 3D meshes, but hard to build. There are some non photorealistic rendering (NPR) options for Blender, many of them implemented in Python. I don't know if they can output SVG data currently. ThreeJs has an SVG engine, meaning a backend that outputs SVG.

sitkack 7y ago
> build a replacement for OpenSCAD I am very interested in this.
- williamaadams 7y ago
  There was quite a lot of openscad replacement going on in 2011. I even made a lua based alternative.
- bayesian_horse 7y ago
  My first attempt was using the Blender API, you can take a look at https://github.com/akloster/blender-vraag https://github.com/akloster/blender-vraag Currently I am trying to reimplement the "construct" part with Pymesh and Shapely, but I haven't published it yet.
- tapia 7y ago
  Have you tried python-occ? http://www.pythonocc.org/ http://www.pythonocc.org/
  - bayesian_horse 7y ago
    Thank you for the suggestion. I hadn't seen that yet. From a cursory look it's not completely what I am looking for, but maybe it can be useful. One of the problems for me is that I am sort of stumbling into this "CAD" thing from a coding perspective. CAD programs like Fusion 360° or FreeCAD seem a bit too complicated for me, and through my grappling with the concepts I am reinventing some concepts/tools. Particularly I want to develop 3D printed objects the same way I would do data science: Start with Jupyter notebooks, iterate, maybe end up with parametric Python scripts.