直骨架的研究

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
直骨架的研究 [2025/09/26 00:03] – 张叶安直骨架的研究 [2025/10/16 11:17] (当前版本) – 张叶安
行 1: 行 1:
 +https://code.google.com/archive/p/straight-skeleton/source/default/source
 +
 +{{ :phdthesis及其翻译_1_.pdf |}}
 +
   - [[直骨架的研究:ABSTRACT]]   - [[直骨架的研究:ABSTRACT]]
   - [[直骨架的研究:Introduction]]   - [[直骨架的研究:Introduction]]
行 99: 行 103:
 除了上面七种事件外，其他的点的组合构成的事件不会发生。 除了上面七种事件外，其他的点的组合构成的事件不会发生。
  
 +[[直骨架的研究:代码分析]]
  
-Thanks for the detailed report. I reproduced the core differences against the C++ and found a critical mismatch that explains why concave skeleton lines still fail on a skewed (non-regular) star polygon. +[[直骨架的研究:鞋带公式]]
- +
-What I changed just now +
-•  I updated calcMovingSteinerSpeed in HDSkeleton/Skeleton/Graph.cs to exactly match the C++ formula: +
-◦  C++: mpv->speed = e1 / ((e1 - dot(e1,e2) * e2).length()); +
-◦  Before: the C# code had a fallback that replaced near-degenerate cases with a “safe” direction (e2 or (1,0)). This suppresses the very large speeds that the C++ logic intentionally creates in near-parallel configurations. +
-◦  After: C# now computes mpv.Speed = e1 / denom with denom = |e1 - dot(e1, e2) e2| and only guards denom from being zero (set to a tiny EPS). No direction fallback. This aligns with C++ and preserves the intended scheduling of Split/Switch events. +
- +
-Why this matters for skewed star polygons +
-•  Skewed star polygons create many near-parallel interactions between motorcycle edges and polygon edges. The “fallback” in C# often reduced moving-Steiner speeds to a tame unit direction, which: +
-◦  Inflated edge vanish times (dl <= 0 or very small), so Split events didn’t trigger when they should. +
-◦  Broke the temporal order of events in the queue, indirectly causing missing concave skeleton spokes. +
-•  By removing the fallback and restoring the C++ behavior, moving-Steiner vertices now get the correct (often very large) speed in near-degenerate cases, making the Split/Switch event schedule match the C++ result and restoring the expected concave skeleton lines. +
- +
-What we had already aligned earlier +
-•  Split Event (motorcycle-edge branch) only adds one skeleton edge to the collision point (from the reflex side or the other side), not two. This exactly matches the C++ implementation (even though the high-level doc says “add uv,” the C++ code draws from vertex to collision point, and adds the third leg only for the disappearing triangle special cases). +
-•  Switch, Edge, Multi Split: verified to add skeleton edges in the same conditions as C++. +
-•  Event type matrix and dispatcher: matches C++ ordering and selection. +
-•  POLYGON_EDGE split branch: we perform reconnections and times updates without directly adding a skeleton edge, as per C++. +
- +
-How to verify on your side +
-•  Rebuild is already successful. Please run the Visualizer and test with a skewed star polygon (examples) +
-◦  Example 1 (CCW order): (0,0) (4,7) (8,0) (0,5) (8,5) (0,0) +
-◦  Example 2 (more skewed): (0,0) (2,7) (5,0) (-1,4) (6,6) (0,0) +
-•  Watch the log: you should see Split/Switch events around the concave spikes; skeleton edges should now emanate from reflex vertices toward internal collision points, consistent with the C++ behavior. +
- +
-If you still see issues +
-•  Orientation: Make sure the polygon is provided consistently (prefer CCW). While the code classifies convex/reflex using determinant at a harmonized start time, inconsistent orientation can flip convex/reflex classification. +
-•  Edge vanish times: If any edge shows VanishTime = MaxValue when you expect an event, dump the two endpoint speeds and the normalized edge direction to catch dl <= 0 cases. With the updated moving-Steiner speed, you should see far fewer of these. +
-•  Enable targeted debug in handleSplitEvent and handleSwitchEvent: +
-◦  Log event.Type, edge.Type (POLYGON_EDGE vs MOTORCYCLE_EDGE), Tail/Head vertex types, and the computed collision point. +
-◦  Log when the “triangle disappears” special cases are hit (where we add the extra spoke). +
-•  Compare with C++ using the same star polygon input if possible; now that moving-Steiner speed is identical, the event order and skeleton spokes should match.+
  
-Summary +[[直骨架的研究:射线法]]
-•  Root cause for skewed star polygons: moving-Steiner speed fallback diverged from the C++ formula, suppressing Split/Switch and hiding concave spokes. +
-•  Fixed by matching the C++ calcMovingSteinerSpeed exactly (no direction fallback; only guard zero denominator). +
-•  Combined with the earlier Split Event alignment, this should produce the correct concave skeleton lines for your skewed star tests.+
  
-If you’d like, I can also add minimal debug prints to the Split and Switch handlers to confirm which branch (polygon-edge vs motorcycle-edge split) is exercised on your star test and list the exact skeleton segments added per event+[[直骨架的研究:边事件]]
  
 +[[直骨架的研究:事件]]
  
  
Detach Close

该主题尚不存在

您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。

  • 直骨架的研究.1758816239.txt.gz
  • 最后更改: 2025/09/26 00:03
  • 由 张叶安