Implement `hatch` entity

[dotoritos-kim]

Hello, I'd like to implement the parser and renderer for hatch entity. Since this feature is essential to the CAD user, IMO it's important and valuable to proceed. My final goal is implementing a rendering logic for hatch, but to do so I have to parse hatch entity first.

If someone has any plan to do so (or even currently doing it), let's talk about more so that I can help and elaborate. If it's not, may I proceed to implement such feature? @vagran

Milestones

TBD

Reference

• dxf hatch entity specification

[vagran]

Hello, Yes this feature is quite useful indeed. But it is also quite challenging to implement, and this is the reason why it is not implemented yet. Parsing hathing entity parameters is trivial, however rendering is not. AFAIK nobody is implementing it now. But before proceding with your implementation, it indeed should be discussed about your vision or ideas of the implementation. Which technique do you plan to use for hatch rendering? It should be performant enough, not to slow down huge DXFs rendering.

[dotoritos-kim]

Which technique do you plan to use for hatch rendering? It should be performant enough, not to slow down huge DXFs rendering.

My first suggestion of approach is using Material for predefined hatching pattern. Within my comprehension, Material is kind of textures. By using this approach, all I have to do is implement the creation of material with given specification. Any translation and transformation will be done on three.js side.

I found that there is a Custom Shader Material third party. I'm not sure this helps us or not, but at least there is a chance to be so. This might helps us define custom textures.

it indeed should be discussed about your vision or ideas of the implementation

Still more research is required for other possibilities. For example, more procedural options (see this) might be computational challenging. But I think these kind of hatching is less urgent than predefined things. I'm not sure whether it it possible or desirable to implement 100% spec-covering, since this library doesn't seem to aim for making a general CAD editor. For such thing, we need to discuss the direction of developments.

[vagran]

Material is just a set of parameters used when rendering any 3D primitive. Currently dxf-viewer uses custom shaders (not that plugin, just own shaders) to render entities in most optimal way (for example, saving render buffers space by working with 2D coordinates only). There is a way to render a hatch as a texture. In such case you need to pre-render hatch texture tile (which should be able to be seamleassly repeated in both vertical and horizontal directions), then render a polygon filled with this texture. The polygon shape may be quite complex, with inner loops defined by hatch boundaries or external referenced entities. There is a drawback in this solution - when the drawing is scaled up, limited resolution of the hatch texture will be visible. Using signed distance field texture may improve the situation. However, as I see in Autodesk viewer, hatch pattern lines remain fixed width when scaling, thus meaning they are rendered as lines primitives. This approach is challenging in terms of calculating hatch pattern final shape after clipping with the hatch boundaries. Also resulting primitives should be rendered in most optimal way, not to cause explosive increase of used draw calls on a big DXF with a lot of hatched areas.

[dotoritos-kim]

Thank you for your detailed explanation. I want to provide some of my thoughts with respect to your observations and other references:

1. To see your exaplanation, using texture seems to be easy to implement, but may cause blurry looking. Therefore if I could I'll not use such strategy.
2. I'll stick to the one using line primitives.

let p: [0, 1] → R^2 be the closed curve defined by Boundary Path Data, where p(0) = p(1). (Loop)
let P ⊆ R^2 be the closed bounded set where bd(P) = { p(t): t ∈ [0, 1] }
let f: [0, 1] → R^2 be any (partial) curve for the hatch pattern.
let F = { f(t): t ∈ [0, 1] }

Find continues curves g1, g2, ..., gk where 
  ∀t∈[0, 1], g(t) ∈ P ∩ F and 
  ∪gk([0, 1]) = P ∩ F

What I have to do is just find some interval(s) in [0, 1], for each interval I, f(I) is in P. For the simplicity, Let's fix f is restricted to a single straight line, at least for right now. (scaling up is trivial, and within my comprehension, every (hatch) pattern is set of lines)

Computing strategy to find such intersecting point should be differ to the property of P.

P can be split into segments differently with boundary path type flag and edge type.

• Line is the easiest one, it's just midschool math.
• Polyline is just set of lines.
• Circular and Elliptic curve is pretty annoying but it can be explicitly computed some how.
• Spline is the most hardest one since there is a degree parameter which makes computation horrible. It takes O(degree^2) to compute the exact point for arbitrary t. And more worse thing is, there is no direct explicit form for arbitrary degree, but non linear recursive form only- so I can't solve analytically. For this case I have to use numerical approach.

If there are N lines for f and M segments for p, then exactly NM solving process is required. I don't have further optimization idea for just right now to drop this complexity.

[dotoritos-kim]

Simple Algorithm Showcase for Polyline

• Analytically compute every intersection points, and then determine from which point to start
• Even-Odd Rule to determine whether start point is inside
• Alternates from start point to end for each intersection points on pattern line to be included in such set or not.
• It's possible to optimize using kd-tree by quering only required sides of polygon- but note that this should be done with huge boundary path length.

https://editor.p5js.org/Phryxia/sketches/LleM_jJ1h

[vagran]

OK, this might work. One more thing to keep in mind: island detection. Boundaries may be nested each to other (with arbitrary big nesting depth), so only areas between them should be hatched. Boundaries intersection should be handled in some way as well. Probably the work should be started by creating some good test file with all these cases represented, to compare its rendering in some reference viewer (e.g. Autodesk online viewer) and dxf-viewer future implementation. Embedded boundaries vs boundaries defined by external entities should be covered as well. BTW spline support should not be a problem, since in all cases you need to compute intersection not with the original curve, but with its tesselation result which is used for final rendering, i.e. baiscally with some polyline which is currently produced by arcs, circles, ellipses and splines.

[dotoritos-kim]

since in all cases you need to compute intersection not with the original curve, but with its tesselation result which is used for final rendering, i.e. baiscally with some polyline which is currently produced by arcs, circles, ellipses and splines.

pretty brilliant!

One more thing to keep in mind: island detection. Boundaries may be nested each to other (with arbitrary big nesting depth), so only areas between them should be hatched.

I thought this might be hard but it wasn't. It was trivial than I expected. Whether polylines are nested or not doesn't affect to the algorithm. All I have to do is just count the intersections and determine the start point is interior.

Note that degenerate cases are ambiguous whether it's truley outside or inside. Nevertheless it works fine with even-odd rule, by not letting adjacent surfaces being not both inside or outside.

https://editor.p5js.org/Phryxia/sketches/LleM_jJ1h

But still there is buggy behavior as you can see above- edge case for the vertex. If line crosses path's vertex (or intersection of two path for degenerate cases) exactly, it is counted as twice currently. This screws up entire even-odd rule. To handle this I should think about handling near vertex case.

[dotoritos-kim]

After few tweaking, I realize that hazard one is vertex-case only. Degenerate or wrapping path doesn't matter since it can be thought of separated area.

And vertex case can be detected easily, because solving linear equation of two line return two interpolation value t1 and t2. While t1 is used to cut the pattern, t2 can be used to detect whetherwhere intersection is occur one of two vertices. With tracking the duplication, this can be elliminated.

This logic is applied to above demo link

[vagran]

That's interesting findings. What if you would account intersection with line only in range t [0; 1), thus including 0 and excluding 1? So in case of shared vertex it will be accounted only for the second line, not the first one.

[dotoritos-kim]

What if you would account intersection with line only in range t [0; 1), thus including 0 and excluding 1?

This is why I love to cooperate for ideation. You're right, I confirmed that such approach is theoretically and practically works perfectly, and it's performance-healthy as duplication check is not required.

[dotoritos-kim]

And the last small detail: Defining area (or positions) to generate pattern is just bounding box of given geometry, which can be obtained within O(n) time complexity, for n boundary path length.

[vagran]

OK, looks like things are getting serious, so there is no way back anymore :) Let's plan the work.

First, we should define the limited scope.

1. I think for initial implementation we can support only pattern fill (group 70=0), solid fill will be unimplemented for now.
2. No support for MPolygon.
3. Group 75 (Hatch style). I think value 1 can be left unsupported for now (Hatch outermost area only (Outer style)). It looks untrivially to support it since (if I correctly understand its meaning), we need to calculate boundary based on surrounding entities which may be heavy-weight task, and it might require some spatial index to make it work on big files. 0 (Hatch “odd parity” area) is basically what you have just researched. Value 2 (Hatch through entire area) does not look like is a complex task. If I correctly understand, we need to calculate some union envelope shape for all boundaries, and than apply hatch lines intersection algorithm to the resulting shape.
4. Group 76 hatch pattern type. I did not really get what is the difference between 0 = User-defined and 2 = Custom. We need to support the one which provides pattern definition in the HATCH entity. Type 1 = Predefined should be supported just conceptually - we will define a couple of built-in (most simple and widely used) patterns from this list.
5. Group 77 Hatch pattern double flag - I am unsure what it does (lines are doubled?). Probably we can ignore it initially, and draw everything not doubled.
6. I did not really get what "seed point" means. Sounds like origin for pattern instantiation, but why they are multiple?
7. Group 92 Boundary path type flag - support 0 = Default; 1 = External; 2 = Polyline. The rest seems to be less common and less triavial to implement.
8. Group 72 Edge type - all of them (1 = Line; 2 = Circular arc; 3 = Elliptic arc; 4 = Spline).
9. Everything for pattern definition.

Overall milestones to do in dxf-viewer code and architecture design:

1. We need to implement HATCH entity parsing into a convenient form.
2. We need to refactor DxfScene entities decomposition code so that tesselated curves can be obtained for a given entity (either existing entity in DXF for external boundary reference, or by circle/ellipse/spline definition in HATCH entity. They should be in OCS coordinates before any transformations are applied.
3. We need to create an index for all DXF entities so that quick lookup by handle value can be done (required for external boundary references). I am not sure if block instance referencing is possible. Probably should leave unsupported it initially.
4. Module for calculating pattern fill (based on your research).
5. HATCH entity decomposition handler based on all above components.

Actual tasks for current stage:

1. We need sample files which demonstrate most of features we want to cover, and any corner cases we know about (like this one with vertex intersection). Probably can be created in some software like QCAD, with manual inspection of resulting DXF in text editor to confirm it contains necessary features. May be some manual editing of DXF produced by CAD software, if the software is not capable enough. We need variuos kinds of boundaries, with various edge types, nestings and instersections, external entities references. We need variety of used hatch styles (odd parity/though entire area). We need user-defined patterns with clearly identifiable origin point, several variations of scale and rotation. Some supported built-in pattern example. Target is to ensure such samples are properly displayed in the reference viewer and make the same result in the dxf-viewer.
2. Math research should be continued to get solution also for Hatch style 2 (Hatch through entire area) mentioned above. We need to calculate polyline for union of several overallapping boundaries. In case some of them are isolated we should get several loops as a result. Also it would be nice to check if it is a proper definition of what should be done, by creating sample file with such kind of hatch style and several overlapping and non-overlapping loops and checking how they are displayed in the Autodesk viewer.

3. When we have all the algorithms prototyped the actual code can be created. I propose to isolate it in a separate file with a clean and simple interface. In my vision, I see the following interface:

   • A class incapsulating the calculator state and providing methods to get pattern definition area, and to clip a particular pattern line segment (resulting zero or many resulting segments to draw). Describing it in TypeScript:

     
     type Point = {x: number, y: number}
     type Loop = Point[]
     type LineSegment = Point[] // two elements, start and end
     type BBox = {min: Point, max: Point}

   class PatternFillCalculator { constructor(loops: Loop[])

   GetPatternBounds(base: Point, angle: number, scale: number): BBox
   
   ClipLine(line: LineSegment): LineSegment[]

   }

   
   Pattern bounds should be returned in pattern local coordinates (pattern starts in [0; 0] oriented horizontally, scale 1). So that pattern synthesizer code could iterate all rows of the pattern in the returned region, and clip each individual line (keep in mind that pattern row may be not only a single line, but some complex shape as well, see some [predefined patterns](https://ezdxf.readthedocs.io/en/stable/tutorials/hatch.html#predefined-hatch-pattern). The synthesizer will break such pattern into individual line segments, and will clip each one separately.

I have created dev-hatch branch in dxf-viewer repository, so that I could share my effort as well, and we could synchronize the development. Just create a branch in your repository based on this branch, and merge it there periodically (git rebase is also a good thing to use to rebase your changes on top of it). Remember that this branch should not contain any unrelated changes to make it possible to get a clean PR later. I will probably start with the parser stuff.

[dotoritos-kim]

Seems to be a long journey. As I haven't inspect the entire code base, few parts of your explanation seems unclear for right now but by proceeding from small implementation I think I can get there soon.

First I'll proceed to implement parser. And here a very simple hatch example generated by qcad.

simple.zip

This has seven hatchs defined by external. (QCAD can only create a hatch by external as my understanding) Top left one is polyline. More complex example (more than 1 depth nesting, varied edge types...) has to be done manually. Note that line-looking one with right bottom one is degenerate case. Image is rendered by reference viewer.

By the way, do you have any plan to introduce typescript to this repo? If you're busy, I can help you that first. This will help everyone develop more easily, with rich support for IDE and more safe code behavior. I have experienced (for example) handling lots of configuration file related to repository. (Note that I'm actually the author of that, but for some private reason I'm using coworker's account)

[vagran]

By the way, do you have any plan to introduce typescript to this repo?

Yes, it is in my todo list indeed. It looks quite trivial to migrate the core code to it. However, I had a plan to significantly rewrite the parser simultanenously with this migration. Introducing strong typing into its current implementation (which is forked 3rd-party component) seems is not straight forward. Also it would be nice to change overall approach used in the parser, to make it true streaming parser. Currently it loads all the DXF text content fully in the memory as a single string, which limits the possible DXF size to ~1GB, then browser JS string size limit is reached. Also memory consumption equal to file size is not necessary. I have DXF sample which has big embedded OLE object, which we could easily ignore and display the rest content, but it cannot be loaded due to this unnecessary bufferring.

If you want, I can start this migration before proceeding with hatching implementation. However, I do not see real possibility to parallel this work. Describing all the types in DXF viewer is a task for me, since I am the only person knowing this in details. Some advices on configuration and overall layout might be welcome indeed.

If we proceed with this way, I would advice you to continue on hatching task, since it can be effectively paralleled. Having full implementation of PatternFillCalculator would be nice to have when hatching implementation starts. You may also think about some testing for it. Currently dxf-viewer does not have any testing framework at all. It would be nice to introduce something, and start covering core logic with some kind of tests.

BTW constructor(loops: Loop[]) in the interface definition above should also accept parameter for hatch style (odd parity / entire area).

[dotoritos-kim]

Introducing strong typing into its current implementation (which is forked 3rd-party component) seems is not straight forward

Oh I see. I think it's very important issue. So let's make typescript to wait for refactoring.

If you want, I can start this migration before proceeding with hatching implementation. However, I do not see real possibility to parallel this work.

Since I have some deadline for my contraction, it's hard to wait until the migration. I'm also pessimiste to parallel work- especially current commit policy: squash merge. Note that sqaush and even rebase merge, conflicts a lot. (Not rebasing my branch but it matters when merging PR on github) This is because git's conflict detection is based on finding common ancestor and compare them, and squash & rebase merge has only one parent. It's a matter of preference, but obviously parallel working and squashing often fight each other as my experience at company's works.

Therefore, I think implementing hatch ASAP seems to be better option.

Currently dxf-viewer does not have any testing framework at all. It would be nice to introduce something, and start covering core logic with some kind of tests.

I definetely agree. I've used jest and it was reliable, and was easy to use for unit test. Preparing test environment doesn't introduce breaking changes, so I'd happy to do so. This state of js chart would make you help.

[vagran]

OK, let's postpone TypeScript and focus on hatching now. I still propose you to get PatternFillCalculator done, and I will prepare dxf-viewer for hatching implementation (milestones 1,2,3 from my message with action plan).

[vagran]

I'm also pessimiste to parallel work- especially current commit policy: squash merge. Note that sqaush and even rebase merge, conflicts a lot.

Actually conflicts occurs independently from using or not using rebase, if the same place is changed simultaneously in different branches, you will get conflict anyway. You can use any merge policy you want, I can handle the final reintegration to master branch to make the history linear. Just need to ensure that our changes are based on the same branch (dev-hatch is created for that in this repo).

[dotoritos-kim]

I still propose you to get PatternFillCalculator done

Oh, that's the priority. I'll go for it~ Can I introduce jest with above also?

And by the way, few hours before I sketched following parser structure so that I can get some meaningful data. (The time that I haven't thought about separating PatternFillCalculator) Can you consider this sturcture when you implement hatch parser? I've seen other parser file, but as there are duplicated group code on hatch references so it can't be applied to hatch parser. I think this might be helpful.

// declarative schema for each 
const Schema = [
  {
    // Subclass marker (=AcDbHatch)
    code: 100,
    name: 'subclassMarker',
    parse: (value, scanner) => value // value parma should be injected from scanner.next().value
  },
  // Elevation point (in OCS)
  {
    code: 10,
    name: 'elevationPoint',
    parse: (value, scanner) => helpers.parsePoint(scanner)
  },
  // Extrusion direction (optional)
  {
    code: 210,
    name: 'extrusionDirection',
    parse: (value, scanner) => helpers.parsePoint(scanner),
    fallback: { // for optional field, 
      x: 0,
      y: 0,
      z: 1,
    }
  },
  // ... 
}

// common logic (pseudocode)
let sptr = 0
let curr = scanner.next()
while not eof:
  const schema = Schema[sptr++]
  const entity = {}

  if schema.code ≠ curr.code:
    if !schema.fallback: throw error
    entity[schema.name] = fallback
    continue

  entity[schema.name] = schema.parse(curr.value, scanner)
  curr = scanner.next()

[vagran]

Can I introduce jest with above also?

Sure. It would be nice to start some movement to this direction. jest looks good, seems like it is state-of-the-art for JS unit testing.

Can you consider this sturcture when you implement hatch parser?

Declarative approach is a way to go, indeed. I will consider something similar when will make a rewrite of a parser. However, currently it may be better to follow existing code look-and-fill. Another quick notes on your code - it assumes some specific groups order, I am not sure if it is always the case for real-world files. I did not find this requirement in DXF specification, it may be asserted for some sequences like 10,20,30 for 3D coordinates, but not really clear about overall order in an entity. There might be different software which produces DXF, and the viewer should be kept as compatible as possible, and tolerate possible misordering. Another issue is improper subclassMarker handling. This marker occurs several times in a single entity and separates virtual class hierarchy for that entity. E.g. entity typically starts by subclass AcDbEntity, which is base class, for all entities, followed by common groups for all entities, like handle, layer, color, then next more specific subclass, e.g. AcDbDimension followed by fields from this subclass, then even more specific one, e.g. AcDbAlignedDimension, then AcDbRotatedDimension and so on. Theoretically the parser should maintain current subclass name when parsing entity, and it might interpret same group codes differently depending on context. However current implementation does not do anything similar, just relying all codes have their dedicated meaning in current entity context, also being tolerant to groups misordering. BTW elevationPoint does not seem to be required in dxf viewer, according to the description it is some elevation Z value specified, which is not necessary for 2D viewer.

[dotoritos-kim]

Sure. It would be nice to start some movement to this direction. jest looks good, seems like it is state-of-the-art for JS unit testing.

Thanks I'll do it.

I did not find this requirement in DXF specification, it may be asserted for some sequences like 10,20,30 for 3D coordinates, but not really clear about overall order in an entity.

I even found saying DO NOT rely on order that here. Therefore you're right. But I wonder the case of undeterminable case like hatch. For such cases should be handled using little bit order. But it seems that they are somehow split by further subclass.

Another issue is improper subclassMarker handling. This marker occurs several times in a single entity and separates virtual class hierarchy for that entity.

Just forget about this- I misunderstood the specification group code.

BTW elevationPoint does not seem to be required in dxf viewer, according to the description it is some elevation Z value specified, which is not necessary for 2D viewer.

Yeah, if you worries about redundant memories to hold such field, they must be commented out.

---

so I think current implementation may parse correctly with few modification. (Though I haven't inspect all entities, and also I don't have sense to detect which I should ignore or not) Anyway for hatch, following should be considered.

100 | Subclass marker (AcDbHatch)
10 | Elevation point (in OCS)
...
10 | Seed point (in OCS)

And I'll just concentrate on calculator, at least for now. (and jest)

[vagran]

Did you get, what does this "seed point" mean? Why there can be multiple seed points specified? I did not find any information on that, my current assumption is that it defines hatch pattern instantiation origin coordinate. And multiple of them means that the pattern can be instantiated multiple times in one HATCH entity with different offset applied. This is the thing which should be checked as well by creating corresponding sample file and checking it in the reference viewer. Then "base point" in a pattern definition line should be somehow defined as well. I currently assume it is its anchor point which corresponds to seed point when instantiated, just like with BLOCK (base point there) and INSERT (insertion point there).

Just for fun I have asked ChatGPT about that, and it answered exactly the same as I assumed, however you might know that information it provides is not yet considered to be reliable, and it does not provide any source references for that. ChatGPT_dxf_hatch_seed_points.pdf

And yes, this is exactly the case, when subclass markers should be considered and should affect current parsing context. For now, it is quite trivially to remember last subclass encountered and interpret group 10 accordingly. In the future, I will implement some declarative approach, when the parser will be rewritten.

[dotoritos-kim]

@vagran

Did you get, what does this "seed point" mean?

I think I found the right one... but I can't understand what is exactly means as I'm not expert on using CAD... Can you explain to me this docs more easier?

https://help.autodesk.com/view/ASMECH/2016/ENU/?guid=GUID-1C7B56A1-D396-4A28-9A6F-51C07438B46E

[vagran]

@vagran

Did you get, what does this "seed point" mean?

I think I found the right one... but I can't understand what is exactly means as I'm not expert on using CAD... Can you explain to me this docs more easier?

https://help.autodesk.com/view/ASMECH/2016/ENU/?guid=GUID-1C7B56A1-D396-4A28-9A6F-51C07438B46E

Seems this doc is not related to hatch seed points, looks like completely different topic. But I think my assumptions described in my previous message look believable enough, just need to check them by making a sample file.

[vagran]

I have implemented basic parsing for HATCH entity. I did not finish spline boundary type parsing, will do it later.

I noticed that QCAD always creates pattern as pre-defined, referencing it by name, even for completely custom patterns like QCAD logo. It defines simple line as a fallback, so it is always displayed as simple line hatch in the reference viewer. Also was unable to find example files with custom pattern. Probably will need to somehow synthesise one. Actually this also is valid for most of other hatch features.

By the way, if the solid fill will be supported in the future, seems the current approach will need to be redesigned. Solid infill will need polygon definition (probably in form of polygon with holes structure). Thus the algorithm will need to generate such polygons. Then it will probably be more efficient to clip the pattern lines by these polygons.

[dotoritos-kim]

Math research should be continued to get solution also for Hatch style 2 (Hatch through entire area) mentioned above. We need to calculate polyline for union of several overallapping boundaries.

My idea during this week was far from here. I misunderstood that type 2 is solid infill. I haven't got any idea for infill. Anyway here is idea for type 2.

At first I tried to create a union set (=polygon) but roughly it costs O(n^2) time complexity, because I have to check each possible line pairs. But suddenly I was possible to think another idea.

I observed following propreties.

clip(line, path1 ∪ path2) = clip(line, path1) ∪ clip(line, path2)

Computing clip(line, path1) is already implemented. And union of two (or more) lines is pretty straight forward. This algorithm uses greedy approach (still it's guaranteed to be optimal), by sorting lines by starting point, and merge by looking each line's start and end point.

// I: array of lines
function unionIntervals(I):
  sort I by each starting point in increasing order

  let S := {}
  let s := I[1].start
  let e := I[1].end

  foreach k := 2, 3, ..., n:
    let I[k] be [a, b)
    if a ≤ e ∧ b > e:
      e := b
    if a > e:
      S := S ∪ [s, e)
      s := a
      e := b
  S := S ∪ [s, e)

  return S

This takes O(n lg n) time complexity with respect to total path's edge count *n).

Here's TypeScript implementation.

type Line = [number, number]

const data = [
    [0, 1, 3, 5],
    [1, 2, 3, 4],
    [0, 2],
]

function getSortedLines(data: number[][]): Line[] {
    const lines = [] as [number, number][]

    for (const bin of data) {
        for (let i = 0; i < bin.length; i += 2) {
            lines.push([bin[i], bin[i + 1]])
        }
    }
    lines.sort((la, lb) => la[0] - lb[0])

    return lines
}

function unionLines(sortedLines: Line[]) {
    const result = [] as Line[]
    let [s, e] = sortedLines[0]

    for (const [a, b] of sortedLines) {
        if (a <= e && b > e) {
            e = b
        }
        if (a > e) {
            result.push([s, e])
            s = a
            e = b
        }
    }
    result.push([s, e])
    return result
}

console.log(unionLines(getSortedLines(data)))

The remain part is simple, just iterate above for each lines.

Generating polygon seems to be more tricky. I'll think for it.

[dotoritos-kim]

Prototyping hatch style 2 done. Note that this algorithm doesn't generate unified polygon.

Demo: https://editor.p5js.org/Phryxia/sketches/LleM_jJ1h

[vagran]

Nice! I'll try to integrate your PR and make it render some first examples in a couple of days. BTW feel free to add yourself to the AUTHORS file with the next change.

[vagran]

@kimkanghyune I have committed code which now is able to generate some pattern lines (it does not pretend to be correct now, not yet fully verified). I have fixed a couple of problems in your code which caused exceptions in this commit. However, there are still some problems. I have this exception on the attached file:

RangeError: Invalid array length
    at HatchCalculator._RefineTSegments (webpack-internal:///../dxf-viewer/src/hatch/patternFillCalculator.js:207:23)
    at HatchCalculator._ClipLineOddParity (webpack-internal:///../dxf-viewer/src/hatch/patternFillCalculator.js:62:28)
    at HatchCalculator.ClipLine (webpack-internal:///../dxf-viewer/src/hatch/patternFillCalculator.js:41:19)
    at RenderLine (webpack-internal:///../dxf-viewer/src/DxfScene.js:1054:34)
    at RenderLine.next (<anonymous>)
    at DxfScene._DecomposeHatch (webpack-internal:///../dxf-viewer/src/DxfScene.js:1083:20)
    at _DecomposeHatch.next (<anonymous>)
    at DxfScene._ProcessDxfEntity (webpack-internal:///../dxf-viewer/src/DxfScene.js:288:16)
    at DxfScene.Build (webpack-internal:///../dxf-viewer/src/DxfScene.js:169:12)
    at async DxfWorker._Load (webpack-internal:///../dxf-viewer/src/DxfWorker.js:168:5)

Seems that some edge case is not handled, please take a look. simplest-hatch.dxf.zip

[dotoritos-kim]

However, there are still some problems. I have this exception on the attached file:

I don't understand that I've even miss such simple edge case. This is caused while refining intersections into line semgents. Here is more robust case diagram. I'll fix it right now.

[vagran]

Thanks, it works now. I have visualised pattern bounding box in line coordinates system, and yes, it may happen that bounding box edge is collapsing with pattern boundary edge.

I think another edge case is visible when pattern line starts on a vertex:

(hatching line directions and scale seems to be wrong now, but it makes the problem visible).

Here is its bounding box:

[vagran]

Implemented support for dashes as well. Now will need to add some pre-defined patterns. Also it seems that AutoCAD online viewer does not account pattern angle and scale for some reason. Also it does not recognise patterns produced by QCAD, and always renders them as defined by line definition in HATCH entity, QCAD always places there single 45deg line. So now it is quite problematic to verify if everything is displayed correctly since there is no ground truth anymore.

[vagran]

I have attached sample file which demonstrates the problem in current dev-hatch state with drawing hatch line which starts at boundary vertex and goes outside. hatched-triangle.dxf.zip

[dotoritos-kim]

@vagran

That starting point issue is trickier than I thought. It's caused by one point intersection like

Let's call this singular point. Singular point is when one of starting point or end point of line is exactly on the other line segments.

Singular point makes several complex situations. Look at this.

They're not compatible with current odd-even parity approach. I'm thinkig more robust method, and maybe there will be no significant stuructural changes. But still needs time to think and verify. I roughly sketched what should I consider like below:

The core point is, whether the neighbor being inside or outside is the key. All I have to do is just pick middle point between two intersection points, and check they're inside or outside.

Yet checking inside/outside is very performance intensive since it has to check every edges of the path. Therefore I eventually have to use spatial indexing data structure (like kd tree or R-tree...). But first I just fix that problem using naive algorithm to prove concept.

Also I have to deal with numerical error caused by linear equation solver, when detecting singular or not. Even we discard the end point, there might be some chances to fit in [0, 1) interval (like being 0.999989887)

[vagran]

May be this paper can give some ideas.

BTW is this case properly handled?

I will try to create test sample for it.

[vagran]

May be this paper can give some ideas.

BTW is this case properly handled?

I will try to create test sample for it.

This one seems to be currently working: hatch-colinear-edge.dxf.zip

[vagran]

Found non-working case: hatch-colinear-edge.dxf.zip

[vagran]

@kimkanghyune Your fix works with all my synthetic cases created so far. However I have one real-world DXF file where hatching is displayed improperly. I cannot share it publicly, so I have sent it to your e-mail specified in your commits. The file is pretty big, I did not yet managed to analyse which edge case is caused this problem and create a small synthetic test file.

[vagran]

Created one more problematic test file: hatch-colinear-edge-2.dxf.zip hatch-colinear-edge-3.dxf.zip

[vagran]

I also have some thoughts on making the algorithm more robust.

1. We can relax requirements for ClipLine() method if it helps. We can say that the line passed to it always starts and ends outside the boundary loops. To do this, I can add some margins to a calculated bounding box of the pattern, and pass in these extended margins. Dashed lines can be clipped with the resulting clipped segments instead of clipping each separate dash (this probably is way to go in any case, because it is more optimal performance-wise).
2. I would use pseudo-cross-product sign with each edge to check the crossing direction. For edges of a single loop, these directions should alternate. If there are sequential segments with the same crossing direction, they should be collapsed (this way workaround with checking vertex only on one line side is not needed). Zero indicates colinearity, so the line should be clipped by segment start. However next non-colinear edge crossing direction should change sign relative to the one preceding colinear edge, to switch line state (in case line continues, it should start from colinear edge end). This way colinear segment should be treated mostly like shared vertex between edges. These directions should be scoped by a separate loops. Encountering different loop should always switch line state. I will try to illustrate this by some drawing later.
3. Did you consider simpler cross-product based approach to calculate line segments intersection? Described in this answer, code example here.

[vagran]

Tried to illustrate what I mean: Enable/Disable state is toggled when same loop cross direction (+/-) changed or loop (A/B) changed. Colinear edges do not change the state. When vertex like one between edge checks 11 and 12 is passed, it toggles state twice in the same point, so such short segments can be filtered out by (almost) zero length.

Assuming any winding direction of a loop is not needed, just cross-product sign alternation matters.

However this approach still may have problem with some edge cases, just one more idea to think about.

[dotoritos-kim]

We can say that the line passed to it always starts and ends outside the boundary loops.

As think of numerical error, I think doing so help stability. But what about custom patterns? There are many cases of non-linear structure like these

Dashed lines can be clipped with the resulting clipped segments instead of clipping each separate dash (this probably is way to go in any case, because it is more optimal performance-wise).

Great idea. It'll help drastically to reduce size of inputs.

Enable/Disable state is toggled when same loop cross direction (+/-) changed or loop (A/B) changed.

Looks like very robust than we've done before. But how can I know loop B is encounted while going along the paths of A? I'm afraid that sorting edges isn't helpful in this case... Do you have any good idea for?

However this approach still may have problem with some edge cases, just one more idea to think about.

What kind of edge cases occur?

[vagran]

But what about custom patterns? There are many cases of non-linear structure like these

Before I started to draw this picture, I was pretty sure, that custom patterns are represented in the same way, just each separate line (marked by it own color on the picture) has its own entry in the pattern definition, with its own angle, offset, and dash length: However, now, I am already not sure if it is possible for every pattern, unless they are crafted with some limitation on used coordinates. Will need to research this question (investigate .pat file format used in AutoCAD to store them). In case they are not using approach used in DXF, and defined as shapes, then it is still possible to use proposed approach, by extending each shape segment up to pattern bounding box, clipping it, and then clipping the shape segment against the extended line clipping result (overhead opposed to optimisation with dashes, but this is mostly not about optimisation but about increasing robustness, by working with lines which always start and end outside the boundary).

But how can I know loop B is encounted while going along the paths of A? I'm afraid that sorting edges isn't helpful in this case... Do you have any good idea for?

What kind of edge cases occur?

That was exactly one of edge cases which was on my mind. However I have now tried to analyse a bunch of them, and did not find any case when it should not work. Do you have some example which you think might not be working?

[dotoritos-kim]

@vagran

Uhmmm- Since we're not professional researcher, theoretically perfect implementation is hard to achieve... IMO. Rather just using verified method is better unless our method is guaranteed to be perform well. (Still above journey was fun)

I've studied several geometric algorithms from basic to advanced recent days, and tried to find some convincing paper and implementation, and here's the popular polygon boolean operation method, which support intersect (≒clip) or union of polygons.

I'm not sure just clipping line is possible or not directly (since line is not polygon), but still it's possible to clip line with this method by clipping degenerate polygon (just two lines looping two points). It's sooooo powerful that even support for hole.

They're several implementation, and one I gave has the most star on github.

[vagran]

@kimkanghyune I just committed alternative implementation of clipping based on my previous thoughts. In general, it looks good, the only additional condition is that side checking is performed only for connected edges of a loop, unconnected edges toggle the state in any case. That's because I found a case with complex polygon which does not work with initial theory: Here the red line crosses same loop edges twice from right side, then twice from left side. So this side check seems to be only necessary for robust check near shared edge.

All of my test samples "mostly" renders correctly, even the big file I have previously shared with you. "Mostly" because incorrect renders, as determined by debugging, are caused by numerically unstable function for segments intersection (I have taken one with cross-products). It may not detect colinearity (and returns some intersection point not lying on one of the segments), or may produce empty result for a shared vertex for both connected edges. I will think how to make it robust.

Also THROUGH_ALL style seems to be trivially implementable. It just need to be counted how many times a loop is crossed from one side, and from another, if both are equal for all loops, then the segment is currently outside of any loop.

[vagran]

BTW Fun fact, QCAD does not detect colinearity in one of my samples, and renders hatch line on top of colinear edge:

[dotoritos-kim]

@vagran

That's great!

That's because I found a case with complex polygon which does not work with initial theory:

I'd like to claim strongly that we don't have to support such illegal polygons concisely. They are so abnormal, so that there is no reason to put such polygons in production purpose CAD file. Unless we use verified academic method like I posted here, it's akward to support such edge case.

And I was forgot to reply to this

Do you have some example which you think might not be working?

Nope that's why I asked you so- because I couldn't find it.

[dotoritos-kim]

(I have taken one with cross-products). It may not detect colinearity (and returns some intersection point not lying on one of the segments), or may produce empty result for a shared vertex for both connected edges. I will think how to make it robust.

How about this approach? When deciding they're parallel, divide by product of both vector's length.

// From https://github.com/vagran/dxf-viewer/commit/b6176a8c92c6a40b0fa4477d1682c49bd6e9cea6#diff-220bdbc8f96c16e045dbce1c8faf4bf0e86cdbe10b73de126d19d4ec2aabe1ffR22
if (Math.abs(S / (a.length() * b.length()))

By doing this we can get rid of length of vectors and extract sin(theta) only where theta is angle between two vectors. Since I removed the length of them, although more numerical error cumulates, it's safe to increase decision boundary because it's pure sin(theta).

[dotoritos-kim]

By the way, I'll implement some patterns in this list. I think I should postpond this for some private reason... I have more urgent things than implementing patterns.

[vagran]

I'd like to claim strongly that we don't have to support such illegal polygons concisely. They are so abnormal, so that there is no reason to put such polygons in production purpose CAD file.

Yes, that's true, however, when you release some product in real world, you will be very surprised about variety of use cases users will encounter. All unhandled edge cases will return back in opened issues, with examples which somehow handled in other software and are improperly displayed in dxf-viewer. So it should be done as robust as possible.

I also thought about it, and have some ideas to make it rock-solid. All this instability should not be a problem. First, I initially planned to detect separately colinear edges and do not try to calculate intersections with them, but use them to clip resulted segments. This was net yet implemented, and I think it will not be a problem to detect colinearity with some threshold by some method, like one you have described. Another thing I understood during debugging, is a way to properly handle such cases: Because of this instability, it might happen, that intersection is detected with edge A and not edge B (or wise versa), i.e. line parameter for A may be 0.999999, and for B -0.00001. Or even with neither of such edges (e.g. 1.0001 for A and -0.0001 for B):

That is what I have seen in my examples. The solution is, first, allow some margin on acceptable parameter range (out of [0; 1]) and, second, to force intersection calculation for connected edge if there was intersection near edge endpoint. And then apply side comparison logic - in case it intersects both edges from one side, it is state toggling, otherwise no toggling (or toggle on very small distance, which is then filtered out). The edge may be either directly connected or via one or more colinear segments, same logic applies, ignoring interim colinear segment(s).

[vagran]

Unless we use verified academic method like I posted https://github.com/vagran/dxf-viewer/issues/36#issuecomment-1503154751, it's akward to support such edge case.

Once it is done and proved to be working, one can write a paper about this method and make it academic :grin: