Point Inside 3D Convex Polygon in MASM Assembly

John Jiyang Hou

5.00/5 (3 votes)

4 Mar 2016CPOL5 min read

15.1K

175

An algorithm to determine if a point is inside a 3D convex polygon for a given polygon vertices in MASM Assembly

Download source code - 7.3 MB

Introduction

This is an Assembly version of the original C++ algorithm which can be found here.

Background

Please refer to the original C++ algorithm here.

Prepare

Object Oriented with Struct

Although the Assembly language has no OO feature, we can use its STRUCT to simulate the simple class behavior and use invoke mechanism to make a library based architecture.

Debug in Visual Studio

There is a way to develop MASM Assembly in Visual Studio, you can find how to do this in "VisualStudio ASM Setup" folder or reference my article A 2D List Implementation in MASM Assembly, this makes Assembly debug much easier. Here is a screenshot example, the ESI value 0x00392BB8 is the list pointer value, if you check memory address 0x00392bd8, which is the value at above pointer address, then you will find the list struct data in details with further tracing.

C Functions Used

The C calling convention model for all projects.

ASM

.model flat, c

This takes advantage of using all C functions, i.e., fopen, realloc, printf, etc., for File IO, memory allocation, and console output.

To utilize these functions, compile with additional include path and link with msvcrt.lib, check vcDevEnv.bat and ccm.bat for details.

The C Runtime (crt) Library msvcrt.lib is at "C:\Program Files\Microsoft Visual Studio 10.0\VC\lib\msvcrt.lib", you can dump its modules to check if the C functions you are trying to use are included in this library.

For these functions prototypes, you can find it from online MSDN, or check the files in include path at "C:\Program Files\Microsoft Visual Studio 10.0\VC\include". You even can dig in its source code at "C:\Program Files\Microsoft Visual Studio 10.0\VC\crt\src".

Most of C functions return value in EAX with different meaning, but it might have other registers that are modified after invoking function, i.e., printf modify ECX after its inovking, ECX is sensitive register for LOOP. To find out these details, the easiest way is to debug register values changes before and after calling. There are not too many online resources as expected for these details.

List Implementation

The essential part in main function GeoPolygonProc.asm is using a List data structure.

The Assembly language has no built-in List, an array has to be declared with a pre-known fixed size before its referencing, a bigger than actual requirement array is usually declared with an evaluation of its referencing situation, but in some circumstances, we even don't know how big it should be.

For this GeoProc project, particular in GeoPolygonProc.asm, we need a list to hold all face planes, but we cannot assume how many faces we could find. For each face vertices, we also don't know how many vertice points it could include, so a 2D list is also required to store every face vertices points, the major dimension is face index and minor index is vertice index, this face vertice index is the original order in the polygon vertices.

Once again, here is my article A 2D List Implementation in MASM Assembly to implement basic list and 2D list for DWORD and REAL8 data type.

For this project, we need three more data types to implement their list data structure, one is GeoPoint list, another is GeoPlane list, the third one is GeoFace list. All push methods for the three lists, PushPoint, PushPlane and PushFace have been implemented although the LASGeoProc project does't require GeoFace list because the method PointInside3DPolygon only uses GeoPlane list.

Constants

Here are samples of constants used in the projects:

ASM

...
PFILE TYPEDEF PTR FILE
...
PDWORD TYPEDEF PTR DWORD
...
PListPlane TYPEDEF PTR ListPlane
...

Macros

Here is a sample:

ASM

CmpReal MACRO r1:REQ, r2:REQ
    fld r1
    fcomp r2
    fnstsw ax
    sahf         
endm

List Library

Here is ListI struct and its two methods, for all other List types, please check the attached zip package.

ListI

ASM

ListI STRUCT
    p PDWORD ? ; pointer to beginning address of the list
    n DWORD 0  ; count of elements, initialize with default 0
ListI ENDS

Here is ListI structure diagram:

PushI

Push a DWORD data into a ListI variable.

ASM

; push an integer into a list,
; return ListI member p new memory address in eax, list value (address) is unchanged
PushI proc uses ebx esi ecx,
list : PTR ListI, ; check the value in this address to locate the address of ListI struct object list
element : DWORD
    
    local endPos : DWORD    
    local count : DWORD
    
    ; set esi to list
    ; [esi] is the value in esi address, which is the beginning address of ListI object list,
    ; it is also the address of the ListI object first member p
    ; (ListI PTR [esi]) is the reference to the struct object list    
    ; (ListI PTR [esi]).p is the pointer to beginning address of list.p
    ; (ListI PTR [esi]).n is the value of list.n

    mov esi, list

    ; check if list.p is null via esi
    cmp (ListI PTR [esi]).p, 0

    JNE NOT_NULL ; skip list.p initialization if list.p is not null

    ; initialize list.p and list.n if list.p is null
    invoke calloc, 0, TYPE DWORD ; return allocated memory pointer in eax
    mov (ListI PTR [esi]).p, eax ; initialize list.p
    mov (ListI PTR [esi]).n, 0 ; initialize list.n

NOT_NULL:

    ; get new size in bytes    
    mov esi, list ; address value of the ListI object    
    mov ebx, (ListI PTR [esi]).n ;
    
    mov count, ebx ; original count of elements
    imul ebx, TYPE DWORD ; convert to bytes count
    mov endPos, ebx ; save original last element position
    add ebx, TYPE DWORD ; get new bytes length for realloc
    
    ; realloc to new bytes size for ListI member p, its new pointer address is in eax    
    invoke realloc, (ListI PTR [esi]).p, ebx        
    
    ; set to new memory location
    mov (ListI PTR [esi]).p, eax

    ; append new element
    mov esi, eax ; set ListI member p new pointer offset in esi    
    add esi, endPos ; move esi to the original list last element position
    mov ebx, element ; set new element in ebx
    mov [esi], ebx ; append the new element to the original list last element position    
    
    ; set new count
    mov esi, list ; get original list address from its pointer
    mov ebx, count ; original count of elements
    inc ebx ; get new count of elements
    mov (ListI PTR [esi]).n, ebx ; set new count of list to ListI member n
                
    ret
PushI endp

Push2DI

Push a ListI variable to a List2DI variable.

ASM

; push a 1D list to a 2D list
Push2DI proc uses ebx esi ecx,
list2d: PTR List2DI, ; pointer of 2D list
element : PTR ListI ; the new 1D list element
    
    local elNumber, elBytes, elAddr, elEndAddr : DWORD
    
    ; get new element info

    ; get elBytes
    mov esi, element
    mov ebx, (ListI PTR [esi]).n
    mov elNumber, ebx
    imul ebx, TYPE DWORD
    mov elBytes, ebx
    
    ; get elAddr    
    mov ebx, [esi]
    mov elAddr, ebx

    ; get elEndAddr
    mov ebx, elAddr
    add ebx, elBytes
    mov elEndAddr, ebx

    ; check if list2d.p is null
    mov esi, list2d
    cmp (List2DI PTR [esi]).dp, 0

    JNE NOT_NULL ; skip list2d.p initialization if list2d.p is not null
    
    invoke CopyFirstI, list2d, elAddr, elBytes, elNumber
        
    JMP BLANK

NOT_NULL:

    invoke CopyDPI,list2d, elAddr, elBytes

    invoke CopyNPI, list2d, elNumber

    ; set list2d.n
    mov esi, list2d
    inc (List2DI PTR [esi]).n

BLANK:

    ret
Push2DI endp

ContainsListI

This is the key function to work in SetFacePlanes function within GeoPolygonProc.asm, which utilizes List2DI struct and ListI struct. This function is to check if a new found face is a new face, in that case, the new found face is faceVerticeIndexInOneFace, which is a ListI variable, the faceVerticeIndex is a List2DI variable.

ASM

; check if list2d contains list with ignoring list elements order
ContainsListI proc uses ebx esi,
list2d : PTR List2DI,
list : PTR ListI
        
    local isContains, rows, i : DWORD    
        
    ; initialize return value
    mov isContains, FALSE

    ; get rows
    mov esi, list2d
    mov ebx, (List2DI PTR [esi]).n

    cmp ebx, 0
    JE DONE_FALSE

    mov rows, ebx

    ; copy list to avoid modify original list with sorting
    invoke CopyListI, list, ADDR listCopyI

    ; sort list
    invoke BubbleSortListI, ADDR listCopyI
            
    mov i, 0
    mov ecx,rows     
L1:
        invoke GetListIElement, list2d, i, ADDR tempListI

        invoke BubbleSortListI, ADDR tempListI

        invoke CompareListI, ADDR tempListI, ADDR listCopyI

        cmp eax, TRUE

        JE DONE_TRUE        

        inc i
                
    loop L1

    JMP DONE_FALSE

DONE_TRUE:    

        mov isContains, TRUE    

DONE_FALSE:

        ; return value in eax
        mov eax, isContains

        ret
ContainsListI endp

List GeoProc Library

Here are GeoPoint List and List GeoPlane List structs.

ListPoint

ASM

ListPoint STRUCT
    p PGeoPoint ? ; pointer to beginning address of the list
    n DWORD 0  ; count of elements, initialize with default 0
ListPoint ENDS

ListPlane

ASM

ListPlane STRUCT
    p PGeoPlane ? ; pointer to beginning address of the list
    n DWORD 0  ; count of elements, initialize with default 0
ListPlane ENDS

PushPoint

ASM

; push a GeoPoint into a list, return List member p new memory address in eax
PushPoint proc uses ebx esi,
list : PTR ListPoint,
element : GeoPoint
    
    local endPos, newSize : DWORD    
    local count : DWORD
    
    mov esi, list
    
    ; check if list.n is 0
    cmp (ListPoint PTR [esi]).n, 0

    JNE NOT_NULL ; skip list.p initialization if list.p is not null

    ; initialize list.p and list.n if list.n is 0
    invoke calloc, 1, TYPE GeoPoint ; return allocated memory pointer in eax
    mov (ListPoint PTR [esi]).p, eax ; initialize list.p
    mov (ListPoint PTR [esi]).n, 0 ; initialize list.n

NOT_NULL:

    mov esi, list
    mov ebx, (ListPoint PTR [esi]).n
    cmp ebx, 0
    JNE NOT_BLANK

    mov esi, list
    mov ebx, (ListPoint PTR [esi]).p
    invoke memmove, ebx, ADDR element, TYPE GeoPoint

    mov ebx, 1
    mov (ListPoint PTR [esi]).n, ebx

    JMP DONE

NOT_BLANK:
    ; get new size in bytes
    mov esi, list ; address value of the ListR object
    mov ebx, (ListPoint PTR [esi]).n ; [esi] is the value in esi address, which is the beginning address of ListR member p
    mov count, ebx ; original count of elements
    imul ebx, TYPE GeoPoint ; convert to bytes count
    mov endPos, ebx ; save original last element position
    add ebx, TYPE GeoPoint ; get new bytes length for realloc
    mov newSize, ebx
    
    ; realloc to new bytes size for ListR member p, its new pointer address is in eax    
    mov esi, list
    mov ebx, (ListPoint PTR [esi]).p

    ; realloc will free the original memory if the new memory is different
    invoke realloc, ebx, newSize
    
    ; set to new memory location
    mov (ListPoint PTR [esi]).p, eax

    ; append new element after endPos
    mov ebx, (ListPoint PTR [esi]).p
    add ebx, endPos
    invoke memmove, ebx, ADDR element, TYPE GeoPoint
    
    ; set new count
    mov esi, list ; get original list address from its pointer
    mov ebx, count ; original count of elements
    inc ebx ; get new count of elements
    mov (ListPoint PTR [esi]).n, ebx ; set new count of list to ListR member n
                
DONE:

    ret
PushPoint endp

PushPlane

ASM

; push a GeoPlane into a list, return List member p new memory address in eax
PushPlane proc uses ebx esi,
list : PTR ListPlane,
element : GeoPlane
    
    local endPos, newSize : DWORD    
    local count : DWORD
    
    mov esi, list
    
    ; check if list.n is 0
    cmp (ListPlane PTR [esi]).n, 0

    JNE NOT_NULL ; skip list.p initialization if list.p is not null

    ; initialize list.p and list.n if list.n is 0
    invoke calloc, 1, TYPE GeoPlane ; return allocated memory pointer in eax
    mov (ListPlane PTR [esi]).p, eax ; initialize list.p
    mov (ListPlane PTR [esi]).n, 0 ; initialize list.n

NOT_NULL:

    mov esi, list
    mov ebx, (ListPlane PTR [esi]).n
    cmp ebx, 0
    JNE NOT_BLANK

    mov esi, list
    mov ebx, (ListPlane PTR [esi]).p
    invoke memmove, ebx, ADDR element, TYPE GeoPlane

    mov ebx, 1
    mov (ListPlane PTR [esi]).n, ebx

    JMP DONE

NOT_BLANK:
    ; get new size in bytes
    mov esi, list ; address value of the ListR object
    mov ebx, (ListPlane PTR [esi]).n ; [esi] is the value in esi address, which is the beginning address of ListR member p
    mov count, ebx ; original count of elements
    imul ebx, TYPE GeoPlane ; convert to bytes count
    mov endPos, ebx ; save original last element position
    add ebx, TYPE GeoPlane ; get new bytes length for realloc
    mov newSize, ebx
    
    ; realloc to new bytes size for ListR member p, its new pointer address is in eax    
    mov esi, list
    mov ebx, (ListPlane PTR [esi]).p

    ; realloc will free the original memory if the new memory is different
    invoke realloc, ebx, newSize
    
    ; set to new memory location
    mov (ListPlane PTR [esi]).p, eax

    ; append new element after endPos
    mov ebx, (ListPlane PTR [esi]).p
    add ebx, endPos
    invoke memmove, ebx, ADDR element, TYPE GeoPlane
    
    ; set new count
    mov esi, list ; get original list address from its pointer
    mov ebx, count ; original count of elements
    inc ebx ; get new count of elements
    mov (ListPlane PTR [esi]).n, ebx ; set new count of list to ListR member n
                
DONE:

    ret
PushPlane endp

PushFace

ASM

; push a GeoFace into a list, return List member p new memory address in eax
PushFace proc uses ebx edx eax esi,
list : PTR ListFace,
element : PTR GeoFace

    local numberOfPoints : DWORD ; new element GeoFace.n
    local ptsAddr, idxAddr : DWORD ; new element head address for GeoFace.ptsAddr and GeoFace.idxAddr
    local ptsSize, idxSize: DWORD ; new element size            
    local newGeoFaceAddr : DWORD ; new GeoFace address to copy to
    
    mov esi, list
    
    ; check if list.n is 0
    cmp (ListFace PTR [esi]).n, 0

    JNE NOT_NULL ; skip list.p initialization if list.p is not null

    ; initialize list.p and list.n if list.n is 0
    invoke calloc, 1, TYPE ListFace ; return allocated memory pointer in eax
    mov (ListFace PTR [esi]).p, eax ; initialize list.p
    mov (ListFace PTR [esi]).n, 0 ; initialize list.n
    invoke calloc, 1, TYPE GeoFace ; alloc memory for (ListFace PTR [esi]).p to make it a valid pointer
    mov esi, list
    mov (ListFace PTR [esi]).p, eax

NOT_NULL:

    ; prepare element info for both first time push and further push

    ; get element ptsAddr
    mov esi, element
    mov ebx, (GeoFace PTR [esi]).ptsAddr
    mov ptsAddr, ebx

    ; get element idxAddr
    mov esi, element
    mov ebx, (GeoFace PTR [esi]).idxAddr
    mov idxAddr, ebx

    ; get element numberOfPoints
    mov esi, element
    mov ebx, (GeoFace PTR [esi]).n
    mov numberOfPoints, ebx

    ; get ptsSize
    mov ebx, numberOfPoints
    imul ebx, TYPE GeoPoint
    mov ptsSize, ebx

    ; get idxSize
    mov ebx, numberOfPoints
    imul ebx, TYPE DWORD
    mov idxSize, ebx

    ; check if it is first time push

    mov esi, list
    mov ebx, (ListFace PTR [esi]).n
    cmp ebx, 0

    JNE NOT_BLANK ; Not first time push

    ; First time push

    ; alloc memory and copy ptsAddr    
    invoke calloc, numberOfPoints, TYPE GeoPoint
    mov esi, list
    mov esi, (ListFace PTR [esi]).p
    mov (GeoFace PTR [esi]).ptsAddr, eax
    invoke memmove, (GeoFace PTR [esi]).ptsAddr, ptsAddr, ptsSize

    ; alloc memory and copy idxAddr    
    invoke calloc, numberOfPoints, TYPE DWORD
    mov esi, list
    mov esi, (ListFace PTR [esi]).p    
    mov (GeoFace PTR [esi]).idxAddr, eax
    invoke memmove, (GeoFace PTR [esi]).idxAddr, idxAddr, idxSize

    ; set ListFace.n    
    mov esi, list
    mov (ListFace PTR [esi]).n, 1
    
    ; set ListFace.GeoFace.n
    mov esi, list
    mov esi, (ListFace PTR [esi]).p    
    mov ebx, numberOfPoints
    mov (GeoFace PTR [esi]).n, ebx

    JMP DONE

NOT_BLANK: ; further push

    ; increase count of GeoFace in ListFace firstly
    mov esi, list    
    inc (ListFace PTR [esi]).n

    ; increase len(list->p) to (len(list->p) + TYPE GeoFace)
    mov esi, list    
    mov ebx, (ListFace PTR [esi]).p ; list->p
    mov edx, (ListFace PTR [esi]).n ; new count
    imul edx, TYPE GeoFace ; GeoFace each member length    
    invoke realloc, ebx, edx ; return new memory in eax
    mov esi, list        
    mov (ListFace PTR [esi]).p, eax ; set list->p to new address to hold one more GeoFace

    ; get new GeoFace address in list
    mov esi, list    
    mov ebx, (ListFace PTR [esi]).n
    dec ebx ; original count
    imul ebx, TYPE GeoFace ; original length
    add ebx, (ListFace PTR [esi]).p ; add first GeoFace pointer address
    mov newGeoFaceAddr, ebx ; PTR GeoFace, where to copy new element

    ; allocate GeoFace.ptsAddr for newGeoFaceAddr
    invoke calloc, 1, TYPE DWORD
    mov esi, newGeoFaceAddr
    mov (GeoFace PTR [esi]).ptsAddr, eax ; where to copy element.ptsAddr

    ; allocate GeoFace.idxAddr for newGeoFaceAddr
    invoke calloc, 1, TYPE DWORD
    mov esi, newGeoFaceAddr
    mov (GeoFace PTR [esi]).idxAddr, eax ; where to copy element.idxAddr

    ; set new GeoFace.n firstly
    mov esi, newGeoFaceAddr
    mov ebx, numberOfPoints
    mov (GeoFace PTR [esi]).n, ebx

    ; list memory is ready to copy over element.ptsAddr and element.idxAddr now

    mov esi, newGeoFaceAddr
    invoke malloc, ptsSize
    mov (GeoFace PTR [esi]).ptsAddr, eax
    invoke memmove, (GeoFace PTR [esi]).ptsAddr, ptsAddr, ptsSize

    mov esi, newGeoFaceAddr
    invoke malloc, idxSize
    mov (GeoFace PTR [esi]).idxAddr, eax
    invoke memmove, (GeoFace PTR [esi]).idxAddr, idxAddr, idxSize
            
DONE:

    ret

PushFace endp

GeoProc Libary

GeoPoint

ASM

GeoPoint STRUCT
    x REAL8 0.0
    y REAL8 0.0
    z REAL8 0.0
GeoPoint ENDS

Here is the main part of GeoPoint.asm:

ASM

; New a point
; Receives: x, y, z
; Returns: esi = address of newPoint
NewGeoPoint proc,
    x: REAL8,
     y: REAL8,
    z: REAL8
       
    fld x    
    fstp newPoint.x
    fld y
    fstp newPoint.y
    fld z
    fstp newPoint.z
    
    ; return newPoint
    mov esi, offset newPoint
    
    ret
NewGeoPoint endp

;Add 2 points, addPoint = pt1 + pt2
;Receives: pt1, pt2
;Returns: esi = address of addPoint
AddGeoPoint proc,
    pt1: GeoPoint,
     pt2: GeoPoint    
            
    AddReal pt1.x, pt2.x, addPoint.x
    AddReal pt1.y, pt2.y, addPoint.y
    AddReal pt1.z, pt2.z, addPoint.z    
    
    ; return addPoint
    mov esi, offset addPoint
    
    ret
AddGeoPoint endp

GeoVector

ASM

GeoVector STRUCT
    p0 GeoPoint <?>
    p1 GeoPoint <?>    
    x real8 0.0
    y real8 0.0
    z real8 0.0
GeoVector ENDS

Here is the main part of GeoVector.asm:

ASM

; New a vector
; Receives: p0, p1
; Returns: esi = address of newVector
NewGeoVector proc,
    p0: GeoPoint,     
    p1: GeoPoint            
    
    MovGeoPointM p0, newVector.p0
    MovGeoPointM p1, newVector.p1
    SubReal p1.x, p0.x, newVector.x  
    SubReal p1.y, p0.y, newVector.y
    SubReal p1.z, p0.z, newVector.z
                
    ; return newVector
    mov esi, offset newVector
    
    ret
NewGeoVector endp

;Multiple 2 vectors, cross product = u * v
;Receives: u, v
;Returns: esi = address of mulVector
MulGeoVector proc,
    u: GeoVector,
     v: GeoVector

    local r1, r2 : real8
    local pt : GeoPoint
    
    ; calculate mulVector.x = u.y * v.z - u.z * v.y    
    MulReal u.y, v.z, r1
    MulReal u.z, v.y, r2
    SubReal r1, r2, mulVector.x
    
    ; calculate mulVector.y = u.z * v.x - u.x * v.z    
    MulReal u.z, v.x, r1
    MulReal u.x, v.z, r2
    SubReal r1, r2, mulVector.y

    ; calculate mulVector.z = u.x * v.y - u.y * v.x    
    MulReal u.x, v.y, r1
    MulReal u.y, v.x, r2
    SubReal r1, r2, mulVector.z
    
    ; calculate mulVector.p0 = u.p0
    MovGeoPointM u.p0, mulVector.p0
        
    ; calculate mulVector.p1 = u.p0 + GeoPoint(mulVector.x, mulVector.y, mulVector.z)
    MovGeoPointM mulVector, pt
    
    invoke AddGeoPoint, u.p0, pt    

    GetGeoPoint mulVector.p1
            
    ; return mulVector
    mov esi, offset mulVector
    
    ret
MulGeoVector endp

GeoPlane

ASM

GeoPlane STRUCT
    a REAL8 0.0
    b REAL8 0.0
    cc REAL8 0.0 ; c is reserved word, rename it to "cc" which means "coefficient c"
    d REAL8 0.0
GeoPlane ENDS

Here is the main part of GeoPlane.asm:

ASM

; New a newPlaneB
; Receives: a, b, cc, d
; Returns: esi = address of newPlaneB
NewGeoPlaneB proc,
    p0: GeoPoint,
     p1: GeoPoint,
    p2: GeoPoint
    
    local r1, r2, r3 : REAL8    
    local u : GeoVector
    local v : GeoVector
    local n : GeoVector    
        
    ; u = GeoVector(p0, p1)            
    invoke NewGeoVector, p0, p1    
    GetGeoVector u
        
    ; v = GeoVector(p0, p2)        
    invoke NewGeoVector, p0, p2
    GetGeoVector v
        
    ; normal vector n = u * v    
    invoke MulGeoVector, u, v
    GetGeoVector n
        
    ; get newPlaneB.a, newPlaneB.b, newPlaneB.cc
    fld n.z
    fld n.y
    fld n.x
    fstp newPlaneB.a
    fstp newPlaneB.b
    fstp newPlaneB.cc
    
    ; calculate newPlaneB.d = - (newPlaneB.a * p0.x + newPlaneB.b * p0.y + newPlaneB.cc * p0.z)
    
    MulReal newPlaneB.a, p0.x, r1
    MulReal newPlaneB.b, p0.y, r2
    MulReal newPlaneB.cc, p0.z, r3

    fld r1
    fadd r2
    fadd r3
    fmul minusOne
    fstp newPlaneB.d
                        
    ; return newPlaneB
    mov esi, offset newPlaneB
    
    ret
NewGeoPlaneB endp

; Negative a newPlaneB
; Receives: pl
; Returns: esi = address of negPlane
NegGeoPlane proc,
     pl: GeoPlane
                    
    MulReal pl.a, minusOne, negPlane.a
    MulReal pl.b, minusOne, negPlane.b
    MulReal pl.cc, minusOne, negPlane.cc
    MulReal pl.d, minusOne, negPlane.d
    
    ; return negPlane
    mov esi, offset negPlane
    
    ret
NegGeoPlane endp
    
; Negative a newPlaneB
; Receives: pl
; Returns: eax = address of mulPlane
MulGeoPlane proc,
     pl: GeoPlane,
     pt: GeoPoint
    
    local r1, r2, r3 : REAL8    
    
    ; calculate return value = pt.x * pl.a + pt.y * pl.b + pt.z * pl.cc + pl.d    
    MulReal pt.x, pl.a, r1
    MulReal pt.y, pl.b, r2
    MulReal pt.z, pl.cc, r3

    fld r1
    fadd r2
    fadd r3
    fadd pl.d
    fstp mulPlaneVal        
    
    ; return mulPlane
    mov eax, offset mulPlaneVal
    
    ret
MulGeoPlane endp

GeoPolygon

ASM

GeoPolygon STRUCT    
    ptsAddr PGeoPoint ?    
    n DWORD 0 ; actual number of polygon vertices
GeoPolygon ENDS

Here is the main part of GeoPolygon.asm:

ASM

NewGeoPolygon proc uses esi ebx,
ptsAddr: PTR GeoPoint, ; offset address of vertices array
ptsCount: DWORD, ; number of vertices
                
    local oriAddr, destAddr, byteCount : DWORD

    ; get original address to free
    mov esi, offset newPolygon
    mov ebx, [esi]
    mov oriAddr, ebx

    invoke calloc, ptsCount, TYPE GeoPoint ; return new memory address in eax

    mov destAddr, eax

    mov esi, offset newPolygon
    mov [esi], eax    ; bind newPolygon.ptsAddr to new address

    ; get byte count to copy
    mov ebx, ptsCount
    imul ebx, TYPE GeoPoint
    mov byteCount, ebx

    ; copy to new address
    invoke memmove, destAddr, ptsAddr, byteCount

    mov ebx, ptsCount                
    mov (GeoPolygon PTR newPolygon).n, ebx

    ; try to free original memory
    mov ebx, oriAddr
    cmp ebx, destAddr
    JE SKIP_FREE ; if destAddr == oriAddr

    mov ebx, oriAddr
    cmp ebx, 0
    JE SKIP_FREE ; if oriAddr == 0

    invoke free, oriAddr

SKIP_FREE:

    ; return newPolygon address
    mov eax, offset newPolygon

    ret
NewGeoPolygon endp

GeoFace

ASM

GeoFace STRUCT    
    ptsAddr PGeoPoint ?    
    idxAddr PDWORD ?
    n DWORD 0 ; actual number of face vertices
GeoFace ENDS

Here is the main part of GeoFace.asm:

ASM

; return a face address in eax
NewGeoFace proc uses edi esi ebx,
ptsAddr: PGeoPoint, ; GeoFace vertices array address
idxAddr: PDWORD,
ptsCount: DWORD ; GeoFace array size

    local oriAddr, destPtsAddr, destIdxAddr, ptsByteCount, idxByteCount : DWORD

    ; get original address to free
    mov esi, offset newFace
    mov ebx, [esi]
    mov oriAddr, ebx

    ; allocate memory for newFace.ptsAddr
    invoke calloc, ptsCount, TYPE GeoPoint ; return new memory address in eax

    mov destPtsAddr, eax ; save new memory address

    mov esi, offset newFace
    mov [esi], eax ; bind newFace.ptsAddr to new address
    
    ; allocate memory for newFace.idxAddr
    invoke calloc, ptsCount, TYPE DWORD ; return new memory address in eax

    ; exception check
    test eax, eax
    jz CALLOC_FAIL_IDX ; fail if eax is zero

    mov destIdxAddr, eax ; save new memory address

    mov esi, offset newFace
    add esi, TYPE DWORD ; move to idxAddr struct member address
    mov [esi], eax    ; bind newFace.idxAddr to new address

    ; get ptsAddr bytes count to copy
    mov ebx, ptsCount
    imul ebx, TYPE GeoPoint
    mov ptsByteCount, ebx

    ; get idxAddr bytes count to copy
    mov ebx, ptsCount
    imul ebx, TYPE DWORD
    mov idxByteCount, ebx

    ; copy to new address
    invoke memmove, destPtsAddr, ptsAddr, ptsByteCount
    invoke memmove, destIdxAddr, idxAddr, idxByteCount

    ; set newFace.n
    mov ebx, ptsCount                
    mov (GeoFace PTR newFace).n, ebx

    ; try to free original memory
    mov ebx, oriAddr
    cmp ebx, destPtsAddr
    JE SKIP_FREE ; if destAddr == oriAddr

    mov ebx, oriAddr
    cmp ebx, 0
    JE SKIP_FREE ; if oriAddr == 0

    invoke free, oriAddr

SKIP_FREE:

    ; return newFace address
    mov eax, offset newFace
    JMP DONE

CALLOC_FAIL_IDX: ; exception in calloc idx
    mov eax, 0

DONE:
    ret

NewGeoFace endp

GeoPolygonProc

This is the essential part in the whole project, so the complete code will be shown below. You can find all referencing functions in the attached zip package.

Here is the complete code of GeoPolygonProc.asm:

ASM

.686p
.model flat, c ; use c calling convention

include GeoPolygonProc.inc

.data

newPolygonProc GeoPolygonProc <?>

pPolygon PGeoPolygon ?

tempListR1 ListR <?>
tempListR2 ListR <?>
tempListR3 ListR <?>

MaxUnitMeasureError REAL8 0.001;

tempCR1 REAL8 6.0

tempR1 REAL8 0.0

faceVerticeIndex List2DI <?>

pointInSamePlaneIndex ListI <?>

faceVerticeIndexInOneFace ListI <?>

faceIdxListI ListI <?>
facePtsListPoint ListPoint <?>

.code

InitGeoPolygonProc proc uses esi,

    invoke calloc, 1, TYPE DWORD
    mov esi, offset newPolygonProc
    mov (GeoPolygonProc PTR [esi]).facePlanes, eax

    invoke calloc, 1, TYPE DWORD
    mov esi, offset newPolygonProc
    mov esi, (GeoPolygonProc PTR [esi]).facePlanes
    mov (ListPlane PTR [esi]).p, eax
    mov (ListPlane PTR [esi]).n, 0
    
    invoke calloc, 1, TYPE DWORD
    mov esi, offset newPolygonProc
    mov (GeoPolygonProc PTR [esi]).faces, eax

    invoke calloc, 1, TYPE DWORD
    mov esi, offset newPolygonProc
    mov esi, (GeoPolygonProc PTR [esi]).faces
    mov (ListFace PTR [esi]).p, eax
    mov (ListFace PTR [esi]).n, 0

    ret
InitGeoPolygonProc endp

; return a new polygon proc address in eax
NewGeoPolygonProc proc uses esi ebx,
pPolygonIn: PGeoPolygon ; GeoPolygon pointer

    call InitGeoPolygonProc

    ; save polygon in global variable pPolygon
    mov ebx, pPolygonIn
    mov pPolygon, ebx
          
    ; set newPolygonProc with pPolygon
    call SetBoundary          
    call SetMinError          
    call SetFacePlanes

    ; return newPolygonProc address in eax
    mov eax, offset newPolygonProc

    ret
NewGeoPolygonProc endp    

SetBoundary proc uses ebx esi,

    local n : DWORD

    ; get n
    mov esi, pPolygon
    mov ebx, (GeoPolygon PTR [esi]).n
    mov n, ebx

    ; move esi to ptsAddr beginning address
    mov esi, (GeoPolygon PTR [esi]).ptsAddr

    mov ecx, n ; set loop counter
L1:
    INVOKE PushR, ADDR tempListR1, (GeoPoint PTR [esi]).x
    INVOKE PushR, ADDR tempListR2, (GeoPoint PTR [esi]).y
    INVOKE PushR, ADDR tempListR3, (GeoPoint PTR [esi]).z
    add esi, TYPE GeoPoint ; move to next point
LOOP L1
    
    INVOKE BubbleSortListR, ADDR tempListR1
    INVOKE BubbleSortListR, ADDR tempListR2
    INVOKE BubbleSortListR, ADDR tempListR3
    
    mov esi, offset newPolygonProc ; reset esi

    ; x0 = tempListR1[0], x1=tempListR[n-1]
    LoadListRFirstLast tempListR1, n ; use esi
    fstp (GeoPolygonProc PTR [esi]).x1
    fstp (GeoPolygonProc PTR [esi]).x0

    ; y0 = tempListR2[0], y1=tempListR2[n-1]
    LoadListRFirstLast tempListR2, n
    fstp (GeoPolygonProc PTR [esi]).y1
    fstp (GeoPolygonProc PTR [esi]).y0

    ; z0 = tempListR1[0], z1=tempListR[n-1]
    LoadListRFirstLast tempListR3, n
    fstp (GeoPolygonProc PTR [esi]).z1
    fstp (GeoPolygonProc PTR [esi]).z0
    
    ret        
SetBoundary endp

SetMinError proc,

    mov esi, offset newPolygonProc    

    fld (GeoPolygonProc PTR [esi]).x0
    fabs
    fstp tempR1

    AddAbsR (GeoPolygonProc PTR [esi]).x1, tempR1
    AddAbsR (GeoPolygonProc PTR [esi]).y0, tempR1
    AddAbsR (GeoPolygonProc PTR [esi]).y1, tempR1
    AddAbsR (GeoPolygonProc PTR [esi]).z0, tempR1
    AddAbsR (GeoPolygonProc PTR [esi]).z1, tempR1
    
    fld tempR1
    fmul MaxUnitMeasureError
    fdiv tempCR1 ; sum(abs(6 boundary))/6.0 * fmul MaxUnitMeasureError
    
    ; set minError
    mov esi, offset newPolygonProc    
    fstp (GeoPolygonProc PTR [esi]).minError

    ret
SetMinError endp

SetFacePlanes proc uses ebx edx eax esi,

    local numberOfVertices : DWORD ; number of vertices in the polygon
    local verticesAddr : DWORD ; polygon vertices    
    local i, j, k, l, p, m, inLeftCount, inRightCount : DWORD
    local numberOfFaces : DWORD
    local p0 : GeoPoint
    local p1 : GeoPoint
    local p2 : GeoPoint
    local pt : GeoPoint
    local trianglePlane : GeoPlane
    local negTrianglePlane : GeoPlane
    local dis : REAL8
    local absDis : REAL8    
    local minError : REAL8    
    local tempi, count, idx : DWORD
    local pFace : PGeoFace
    
    ; initialize numberOfFaces
    mov numberOfFaces, 0

    ; get minError
    mov esi, offset newPolygonProc
    fld (GeoPolygonProc PTR [esi]).minError
    fstp minError

    ; get numberOfVertices
    mov esi, pPolygon
    mov ebx, (GeoPolygon PTR [esi]).n
    mov numberOfVertices, ebx
    
    ; move esi to ptsAddr beginning address
    mov ebx, (GeoPolygon PTR [esi]).ptsAddr
    mov verticesAddr, ebx

    mov i, 0
    mov edx, numberOfVertices ; save n to edx for comparing with loop counter
L1:    
    mov edx, numberOfVertices
    cmp i, edx
    JAE L1_DONE ; i < numberOfVertices
    
    ; get p0
    GetGeoPointAtIndex verticesAddr, i, p0
    
    mov ebx, i
    inc ebx
    mov j, ebx ; j = i + 1
L2:
    mov edx, numberOfVertices
    cmp j, edx
    JAE L2_DONE ; j < numberOfVertices

    ; get p1
    GetGeoPointAtIndex verticesAddr, j, p1

    mov ebx, j
    inc ebx
    mov k, ebx ; k = j + 1
L3:
    mov edx, numberOfVertices
    cmp k, edx
    JAE L3_DONE ; k < numberOfVertices

    ; get p2
    GetGeoPointAtIndex verticesAddr, k, p2

    ; get trianglePlane
    INVOKE NewGeoPlaneB, p0, p1, p2    
    GetGeoPlane trianglePlane
    
    ; clear pointInSamePlaneIndex
    INVOKE InitListI, ADDR pointInSamePlaneIndex

    mov inLeftCount, 0
    mov inRightCount, 0
    mov m, 0                                

    mov l, 0
L4:    ; calculate inLeftCount, inRightCount, pointInSamePlaneIndex,
    mov edx, numberOfVertices
    cmp l, edx
    JAE L4_DONE ; l < numberOfVertices

    ; if(l == i || l == j || l == k) then go to next L4 loop
    mov ebx, i
    cmp l, ebx
    JE NEXT_L4
    mov ebx, j
    cmp l, ebx
    JE NEXT_L4
    mov ebx, k
    cmp l, ebx
    JE NEXT_L4

    ; if(l != i && l != j && l != k)
    
    ; get pt    
    GetGeoPointAtIndex verticesAddr, l, pt
    
    ; get dis    
    INVOKE MulGeoPlane, trianglePlane, pt ; return value dis address in eax        
    mov esi, eax
    fld REAL8 PTR[esi] ; load return value dis in st(0)
    fstp dis
    
    fld dis
    fabs
    fstp absDis
    
    fld absDis  
    fcomp minError
    fnstsw ax ; move status word into AX
    sahf ; copy AH into EFLAGS
    jnb SET_LEFT_RIGHT_COUNT ; minError >= absDis then skip
    
    ; if fabs(dis) < minError, it means fabs(dis) ~= 0, then add this index l to pointInSamePlaneIndex    
    INVOKE PUSHI, ADDR pointInSamePlaneIndex, l
    JMP NEXT_L4

SET_LEFT_RIGHT_COUNT:
    
    fldz ; load 0
    fcomp dis
    fnstsw ax ; move status word into AX
    sahf ; copy AH into EFLAGS
    jb ADD_RIGHT_COUNT ; dis > 0 then add inRigthCount

    inc inLeftCount ; if dis < 0 then add inLeftCount
    JMP NEXT_L4

ADD_RIGHT_COUNT:
    inc inRightCount ; if dis > 0 then add inRightCount

NEXT_L4:

    inc l ; next L4
    JMP L4

L4_DONE:

    ; if(inLeftCount == 0 || inRightCount == 0) then a face is found
    mov ebx, inLeftCount
    cmp ebx, 0
    JE FACE_FOUND
    mov ebx, inRightCount
    cmp ebx, 0
    JNE NEXT_L3

FACE_FOUND:

    ; clear faceVerticeIndexInOneFace
    INVOKE InitListI, ADDR faceVerticeIndexInOneFace

    ; add i, j, k to this face vertice index list
    INVOKE PUSHI, ADDR faceVerticeIndexInOneFace, i
    INVOKE PUSHI, ADDR faceVerticeIndexInOneFace, j
    INVOKE PUSHI, ADDR faceVerticeIndexInOneFace, k
        
    mov ebx, pointInSamePlaneIndex.n
    mov m, ebx
    mov p, 0
L5: ; add other vertices in the same triangle plane
    mov ebx, m
    cmp p, ebx
    JAE L5_DONE ; p < n

    GetListIVal pointInSamePlaneIndex, p, tempi
    INVOKE PUSHI, ADDR faceVerticeIndexInOneFace, tempi

    inc p
    JMP L5

L5_DONE:

    ; check if trianglePlane is a new face
    INVOKE ContainsListI, ADDR faceVerticeIndex, ADDR faceVerticeIndexInOneFace

    cmp eax, TRUE
    JE NEXT_L3 ; if faceVerticeIndex already contains faceVerticeIndexInOneFace, it is not a new face

;NEW_FACE:

    ; it is a new face, increase numberOfFaces
    inc numberOfFaces

    ; add new face vertice index
    INVOKE Push2DI, ADDR faceVerticeIndex, ADDR faceVerticeIndexInOneFace

    ; check if inRightCount is 0
    mov ebx, inRightCount
    cmp ebx, 0
    JNE CHECK_LEFT

    ; if(onRightCount == 0) then add new face plane trianglePlane
    
    ;-------------------------------------------------------
    ; set up GeoPolygonProc.facePlanes
    mov esi, offset newPolygonProc
    INVOKE PushPlane, (GeoPolygonProc PTR [esi]).facePlanes, trianglePlane
    ;-------------------------------------------------------

    JMP NEXT_L3
    
CHECK_LEFT: ; if(inLeftCount == 0) then add new face plane (-trianglePlane)

    INVOKE NegGeoPlane, trianglePlane    
    GetGeoPlane negTrianglePlane
    
    ;-------------------------------------------------------
    ; set up GeoPolygonProc.facePlanes    
    mov esi, offset newPolygonProc
    INVOKE PushPlane, (GeoPolygonProc PTR [esi]).facePlanes, negTrianglePlane
    ;-------------------------------------------------------
    
NEXT_L3:

    inc k ; next L3
    JMP L3

L3_DONE:

    inc j ; next L2
    JMP L2

L2_DONE:

    inc i ; next L1
    JMP L1

L1_DONE:

    ; set numberOfFaces    
    mov ebx, numberOfFaces
    
    ;----------------------------------------------------------
    ; set up GeoPolygonProc.numberOfFaces
    mov esi, offset newPolygonProc
    mov (GeoPolygonProc PTR [esi]).numberOfFaces, ebx
    ;----------------------------------------------------------

    mov i, 0    
LFACE:
    mov edx, numberOfFaces
    cmp i, edx
    JAE LFACE_DONE ; i < numberOfFaces
    
    ; get faceIdxListI, vertices indexes in the face
    INVOKE GetListIElement, ADDR faceVerticeIndex, i, ADDR faceIdxListI

    ; get count of vertices in the face
    mov esi, offset faceIdxListI
    mov ebx, (ListI PTR [esi]).n
    mov count, ebx

    invoke InitListPoint, Addr facePtsListPoint

    mov j, 0
L6: ; get facePtsListPoint, vertices points in the face
    mov edx, count
    cmp j, edx
    JAE L6_DONE ; i < count

    ; get idx
    GetListIVal faceIdxListI, j, idx

    ; get pt
    GetGeoPointAtIndex verticesAddr, idx, pt

    INVOKE PushPoint, ADDR facePtsListPoint, pt
    
    inc j ; j++
    JMP L6

L6_DONE:
    
    ; create new face
    INVOKE NewGeoFace, (ListPoint PTR [facePtsListPoint]).p, (ListI PTR [faceIdxListI]).p, count

    mov pFace, eax ; new face address

    ;-------------------------------------------
    ; set up (GeoPolygonProc PTR [esi]).faces
    mov esi, offset newPolygonProc
    INVOKE PushFace, (GeoPolygonProc PTR [esi]).faces, pFace
    ;-------------------------------------------

    inc i ; i++
    JMP LFACE

LFACE_DONE:

    ret
SetFacePlanes endp

PointInside3DPolygon proc uses ebx edx esi,
x: REAL8,
y: REAL8,
z: REAL8

    local i, isInside : DWORD
    local pt : GeoPoint ; input point
    local facePlaneAddr : DWORD ; head address of face planes
    local dis : REAL8 ; value to determine if point is in left or right half space of the face plane.
    
    ; set isInside to true
    mov ebx, TRUE
    mov isInside, ebx
    
    ; get input point
    INVOKE NewGeoPoint, x, y, z
    GetGeoPoint pt
        
    ; set facePlaneAddr to face planes address
    mov esi, offset newPolygonProc
    mov esi, (GeoPolygonProc PTR [esi]).facePlanes
    mov ebx, (ListPlane PTR [esi]).p
    mov facePlaneAddr, ebx
    
    mov i, 0 ; loop counter
    mov esi, offset newPolygonProc
    mov edx, (GeoPolygonProc PTR [esi]).numberOfFaces    
L1:    
    cmp i, edx
    JAE L1_DONE
    
    mov esi, facePlaneAddr
    INVOKE MulGeoPlane, (GeoPlane PTR [esi]), pt ; return value dis address in eax
    mov esi, eax
    fld REAL8 PTR[esi] ; load return value dis in st(0)
    fstp dis

    ; If the point is in the same half space with normal vector
    ; for any face of the 3D convex polygon, then it is outside of the 3D polygon    
    fldz ; load 0
    fcomp dis
    fnstsw ax ; move status word into AX
    sahf ; copy AH into EFLAGS
    jb RETURN_FALSE ; if dis > 0 then return false, point is NOT inside polygon
    
    add facePlaneAddr, TYPE GeoPlane ; go to next face plane

    inc i
    JMP L1

L1_DONE:        

    ; All dis values are positive
    ; For all faces, the point is in the opposite half space with normal vector of the corresponding face planes.
    ; The point is inside the 3D polygon
    JMP RETURN_TRUE            

RETURN_FALSE:

    ; If any dis is negative, then the point is NOT inside the 3D polygon
    mov isInside, FALSE

RETURN_TRUE:

    ; return isInside in eax
    mov eax, isInside

    ret
PointInside3DPolygon endp

end

Test and API Usage

The test program is GeoProcTest.asm, it tests both List library and GeoProc library.

Console Output

Here is the convenient macro to wrap C function printf for console output, since printf will modify EAX and ECX, they are protected in stack in the macro, directly using printf only could be an issue when the printf is in a loop with ECX as a loop count or anywhere an assumption for invariant ECX is required.

ASM

MyPrintf MACRO formatString:REQ, printList:VARARG
    push eax
    push ecx
    INVOKE printf, formatString, printList
    pop ecx
    pop eax    
EndM

Code for List Library Test

Please refer to my article A 2D List Implementation in MASM Assembly, the methods PushPoint and PushPlane in ListGeoProc.asm do not have test program related, they are tested with debug in Visual Studio and approved with their references correctly functioning in GeoPolygonProc.asm.

Code for GeoProc Library Test

Here is main test code, which is also a GeoProc library usage template:

ASM

main PROC
    
    call ListTest        
    call GeoPointTest
    call GeoVectorTest
    call GeoPlaneTest
    call GeoPolygonTest
    call GeoFaceTest    
    call GeoPolygonProcTest
    
    ret
        
main ENDP

GeoPointTest proc
    
    local pt1 : GeoPoint
    local pt2 : GeoPoint
    local pt3 : GeoPoint

    invoke NewGeoPoint, p1.x, p1.y, p1.z

    GetGeoPoint pt1

    invoke NewGeoPoint, p2.x, p2.y, p2.z

    GetGeoPoint pt2
                    
    invoke AddGeoPoint, pt1, pt2    

    GetGeoPoint pt3
    
    ; print title
    
    MyPrintf offset FmtStr, ADDR strGeoPointTitle
    
    ; print first point    
    MyPrintf offset FmtFFF, pt1.x, pt1.y, pt1.z
    ; print second point
    MyPrintf offset FmtFFF, pt2.x, pt2.y, pt2.z
    ; print third sum point
    MyPrintf offset FmtFFF, pt3.x, pt3.y, pt3.z

    ret
GeoPointTest endp

GeoVectorTest proc,

    local pt0 : GeoPoint
    local pt1 : GeoPoint
    local pt2 : GeoPoint

    local u : GeoVector
    local v : GeoVector
    local n : GeoVector

    mov esi, offset vtsArr

    GetGeoPoint pt0
    GetGeoPoint pt1
    GetGeoPoint pt2
    
    invoke NewGeoVector, pt0, pt2

    GetGeoVector u

    invoke NewGeoVector, pt0, pt1
    
    GetGeoVector v
    
    invoke MulGeoVector, u, v

    GetGeoVector n
    
    ; print title
    MyPrintf offset FmtStr, ADDR strGeoVectorTitle
    
    ; print first vector u component
    MyPrintf offset FmtFFF, u.x, u.y, u.z
    ; print second vector v component
    MyPrintf offset FmtFFF, v.x, v.y, v.z
    ; print normal vector n component
    MyPrintf offset FmtFFF, n.x, n.y, n.z

    ret
GeoVectorTest endp

GeoPlaneTest proc,

    local plA : GeoPlane
    local plB : Geoplane
    local negpl : GeoPlane    
    local dis : REAL8
    
    invoke NewGeoPlaneB, p1, p2, p3

    GetGeoPlane plB

    invoke NewGeoPlaneA, pl.a, pl.b, pl.cc, pl.d

    GetGeoPlane plA

    invoke NegGeoPlane, plA
    
    GetGeoPlane negpl    
            
    invoke MulGeoPlane, pl, pt

    mov esi, eax
    fld REAL8 PTR[esi]
    fstp dis

    ; print title
    MyPrintf offset FmtStr, ADDR strGeoPlaneTitle

    ; print first plane
    MyPrintf offset FmtFFFF, plB.a, plB.b, plB.cc, plB.d
    ; print second plane
    MyPrintf offset FmtFFFF, plA.a, plA.b, plA.cc, plA.d
    ; print negative plane
    MyPrintf offset FmtFFFF, negpl.a, negpl.b, negpl.cc, negpl.d

    ; print multiple result
    MyPrintf offset FmtF, dis

    ret
GeoPlaneTest endp

GeoPolygonTest proc uses edi ecx eax ebx,
    
    local count : DWORD
    
    mov eax, LENGTHOF vtsArr    
    mov count, eax
    
    ; printf uses eax, must be called before NewGeoPolygon
    MyPrintf offset FmtStr, ADDR strGeoPolygonTitle

    invoke NewGeoPolygon, ADDR vtsArr, count ; return in eax
        
    mov pPolygon, eax ; save new polygon address

    mov esi, pPolygon    
    mov esi, (GeoPolygon PTR [esi]).ptsAddr    
    mov i, 1
    mov edi, 0
    mov ecx, count
    L3:        
    
        MyPrintf offset FmtIFFF, i, (GeoPoint PTR [esi]).x, (GeoPoint PTR [esi]).y, (GeoPoint PTR [esi]).z
                
        add esi, TYPE GeoPoint ; increase point offset edi with GeoPoint length        
    
        inc i
    loop L3

    mov esi, pPolygon        
    MyPrintf offset FmtInt, (GeoPolygon PTR [esi]).n

    ret
GeoPolygonTest endp

GeoFaceTest proc uses edi ecx eax edx ebx,
    
    local count, ptsAddr, idxAddr, idx : DWORD    
        
    mov eax, LENGTHOF faceIdxArr    
    mov count, eax

    ; printf uses eax, must be called before NewGeoFace
    MyPrintf offset FmtStr, ADDR strGeoFaceTitle

    invoke NewGeoFace, ADDR vtsArr, ADDR faceIdxArr, count

    mov pFace, eax ; save new face address

    mov esi, pFace
    mov ebx, (GeoFace PTR [esi]).ptsAddr    
    mov ptsAddr, ebx
    mov ebx, (GeoFace PTR [esi]).idxAddr    
    mov idxAddr, ebx
        
    mov ecx, count
    L3:        
        
        mov esi, idxAddr
        mov ebx, [esi]
        mov idx, ebx

        mov esi, ptsAddr
        
        MyPrintf offset FmtIFFF, idx, (GeoPoint PTR [esi]).x, (GeoPoint PTR [esi]).y, (GeoPoint PTR [esi]).z
        
        add ptsAddr, TYPE GeoPoint ; move to next point
        add idxAddr, TYPE DWORD ; move to next point index
    
    loop L3

    mov esi, pFace
    MyPrintf offset FmtInt, (GeoFace PTR [esi]).n

    ret
GeoFaceTest endp

GeoPolygonProcTest proc uses edi ecx eax edx ebx,

    local isInside : DWORD
    local count, faceAddr, ptsAddr, idxAddr, idx : DWORD    

    invoke NewGeoPolygonProc, pPolygon
    
    mov pPolygonProc, eax
    mov esi, pPolygonProc

    MyPrintf offset FmtStr, ADDR strGeoPolygonProcTitle

    MyPrintf offset FmtFF, (GeoPolygonProc PTR [esi]).x0, (GeoPolygonProc PTR [esi]).x1
    MyPrintf offset FmtFF, (GeoPolygonProc PTR [esi]).y0, (GeoPolygonProc PTR [esi]).y1
    MyPrintf offset FmtFF, (GeoPolygonProc PTR [esi]).z0, (GeoPolygonProc PTR [esi]).z1    
    MyPrintf offset FmtF, (GeoPolygonProc PTR [esi]).minError    

    MyPrintf offset FmtSI, ADDR strGeoPolygonProcFacePlanes, (GeoPolygonProc PTR [esi]).numberOfFaces

    mov esi, pPolygonProc
    mov ecx, (GeoPolygonProc PTR [esi]).numberOfFaces
    mov esi, (GeoPolygonProc PTR [esi]).facePlanes
    mov esi, (ListPlane PTR [esi]).p
    
L1:
        
    MyPrintf offset FmtFFFF, (GeoPlane PTR [esi]).a, (GeoPlane PTR [esi]).b, (GeoPlane PTR [esi]).cc, (GeoPlane PTR [esi]).d
    
    add esi, TYPE GeoPlane
    LOOP L1

    mov esi, pPolygonProc        
    mov esi, (GeoPolygonProc PTR [esi]).faces
    mov ebx, (ListFace PTR [esi]).p
    mov faceAddr, ebx
    mov ebx, (ListFace PTR [esi]).n
    mov count, ebx
    mov i, 0
L2:
    mov edx, count
    cmp i, edx
    JAE L2_DONE ; i < count
            
    mov esi, faceAddr
    mov ebx, (GeoFace PTR [esi]).ptsAddr    
    mov ptsAddr, ebx
    mov ebx, (GeoFace PTR [esi]).idxAddr    
    mov idxAddr, ebx

    mov ecx, (GeoFace PTR [esi]).n

    MyPrintf offset FmtSI, ADDR strGeoPolygonProcFace, i
L3:        
        
        mov esi, idxAddr
        mov ebx, [esi]
        mov idx, ebx

        mov esi, ptsAddr
        
        MyPrintf offset FmtIFFF, idx, (GeoPoint PTR [esi]).x, (GeoPoint PTR [esi]).y, (GeoPoint PTR [esi]).z
        
        add ptsAddr, TYPE GeoPoint ; move to next point
        add idxAddr, TYPE DWORD ; move to next point index
    
    loop L3    

    add faceAddr, TYPE GeoFace

    inc i
    JMP L2
L2_DONE:
    
    INVOKE PointInside3DPolygon, ptInside.x, ptInside.y, ptInside.z

    mov isInside, eax
    MyPrintf offset FmtInt, isInside

    INVOKE PointInside3DPolygon, ptOutside.x, ptOutside.y, ptOutside.z

    mov isInside, eax
    MyPrintf offset FmtInt, isInside

    ret
GeoPolygonProcTest endp<span id="cke_bm_111E" style="display: none;"> </span>

File IO

This is a preparation for LAS process. File IO is using C functions fopen, fread, fwrite, fprintf and fclose, memory buffer is using malloc and free.

Here are prototypes for these File IO C functions:

ASM

; FILE is a struct, its definition is in
; "C:\Program Files\Microsoft Visual Studio 10.0\VC\include\stdio.h"
fopen PROTO, ; return (PTR FILE)
   filename : PTR BYTE,
   mode : PTR BYTE

fread PROTO, ; return count to read in eax
   buffer : PTR,
   unitsize : DWORD,
   count : DWORD, ; return this value in eax if success
   stream : PTR FILE

fwrite PROTO, ; return bytes count to write to binary file in eax
   buffer : PTR,
   unitsize : DWORD,
   count : DWORD, ; ; return this value in eax if success
stream : PTR FILE

fseek PROTO, ; return 0 in eax if success
   stream : PTR FILE,
   pos : DWORD,
   origin : DWORD

fclose PROTO, ; return 0 in eax if success
   stream : PTR FILE

fprintf PROTO, ; return bytes count to write to text file in eax based on format, if fail then return 0 in eax
   stream : PTR FILE,
   format : PTR BYTE, ; "%15.6f " will return 0x00000010 in eax because format "%15.6f " has 16 bytes to write
   varlist : VARARG

LAS Process

The process has two steps, first use GeoProc library to create a GeoPolygonProc global instance newPolygonProc, then use its PointInside3DPolygon method to check point is inside or outside.

Here is the main part of LASGeoProc.asm:

ASM

.code

main PROC
    
    MyPrintf offset FmtStr, ADDR strBegin
    
    call SetUpGeoPolygonProc

    call LASProcess
    
    MyPrintf offset FmtStr, ADDR strEnd

    ret
        
main ENDP

SetUpGeoPolygonProc Proc,    

    ; create pPolygon
    INVOKE NewGeoPolygon, ADDR vtsArr, vtsCount ; return in eax        
    mov pPolygon, eax ; new GeoPolygon address

    ; create pPolygonProc
    INVOKE NewGeoPolygonProc, pPolygon    
    mov pPolygonProc, eax ; new GeoPolygonProc address

    ; set boundary
    mov esi, pPolygonProc
    fld (GeoPolygonProc PTR [esi]).x0
    fstp x0
    fld (GeoPolygonProc PTR [esi]).x1
    fstp x1
    fld (GeoPolygonProc PTR [esi]).y0
    fstp y0
    fld (GeoPolygonProc PTR [esi]).y1
    fstp y1
    fld (GeoPolygonProc PTR [esi]).z0
    fstp z0
    fld (GeoPolygonProc PTR [esi]).z1
    fstp z1
    
    ret

SetUpGeoPolygonProc endp

LASProcess proc,

    local i, record_loc : DWORD
    local x : REAL8
    local y : REAL8
    local z : REAL8        
    local isInside : DWORD    
    local insideCount : DWORD

    ; open LAS file to read
    INVOKE fopen, ADDR strFileInput, ADDR modeRB
    mov rbFile, eax

    ; open LAS file to write
    INVOKE fopen, ADDR strFileOutputB, ADDR modeWB
    mov wbFile, eax    

    ; open text file to write
    INVOKE fopen, ADDR strFileOutputT, ADDR modeWT
    mov wtFile, eax
    
    ; read summary info
    INVOKE fseek, rbFile, 96, 0
    INVOKE fread, offset offset_to_point_data_value, TYPE DWORD, 1, rbFile

    INVOKE fseek, rbFile, 105, 0
    INVOKE fread, offset record_len, TYPE WORD, 1, rbFile
    INVOKE fread, offset record_num, TYPE DWORD, 1, rbFile

    INVOKE fseek, rbFile, 131, 0
    INVOKE fread, offset x_scale, TYPE REAL8, 1, rbFile
    INVOKE fread, offset y_scale, TYPE REAL8, 1, rbFile
    INVOKE fread, offset z_scale, TYPE REAL8, 1, rbFile
    INVOKE fread, offset x_offset, TYPE REAL8, 1, rbFile
    INVOKE fread, offset y_offset, TYPE REAL8, 1, rbFile
    INVOKE fread, offset z_offset, TYPE REAL8, 1, rbFile

    ; allocate memory for LAS header
    invoke malloc, offset_to_point_data_value
    mov bufHeader, eax
    
    ; read LAS header
    INVOKE fseek, rbFile, 0, 0    
    INVOKE fread, bufHeader, 1, offset_to_point_data_value, rbFile

    ; write LAS header
    INVOKE fwrite, bufHeader, 1, offset_to_point_data_value, wbFile

    ; allocate memory for LAS record    
    invoke malloc, record_len
    mov bufRecord, eax                

    mov i, 0    
    mov insideCount, 0
L1:
    mov edx, record_num
    cmp i, edx
    JAE DONE ; i < record_num

        ; LAS record location
        ; record_loc = offset_to_point_data_value + record_len * i;
        mov ebx, record_len
        imul ebx, i
        add ebx, offset_to_point_data_value
        mov record_loc, ebx
        
        ; read LAS record coordinate
        INVOKE fseek, rbFile, record_loc, 0
        INVOKE fread, offset xi, TYPE DWORD, 1, rbFile
        INVOKE fread, offset yi, TYPE DWORD, 1, rbFile
        INVOKE fread, offset zi, TYPE DWORD, 1, rbFile

        ; convert to actual coordinate

        ; x = (xi * x_scale) + x_offset;
        fild xi
        fmul x_scale
        fadd x_offset
        fstp x

        ; y = (yi * y_scale) + y_offset;
        fild yi
        fmul y_scale
        fadd y_offset
        fstp y

        ; z = (zi * z_scale) + z_offset;
        fild zi
        fmul z_scale
        fadd z_offset
        fstp z
        
        ; filter out points outside of boundary
        CmpReal x0, x
        JNB NEXT
        CmpReal x, x1
        JNB NEXT
        CmpReal y0, y
        JNB NEXT
        CmpReal y, y1
        JNB NEXT
        CmpReal z0, z
        JNB NEXT
        CmpReal z, z1
        JNB NEXT

        ; inside boundary
        
        ; check if point(x,y,z) is inside 3D polygon
        INVOKE PointInside3DPolygon, x, y, z
        mov isInside, eax
        
        ; skip outside points
        cmp isInside, FALSE
        JE NEXT
    
        ; inside points        

        ; read LAS inside record
        INVOKE fseek, rbFile, record_loc, 0
        INVOKE fread, bufRecord, 1, record_len, rbFile
            
        ; write LAS inside record
        INVOKE fwrite, bufRecord, 1, record_len, wbFile
        
        ; write LAS text inside record
        INVOKE fprintf, wtFile, offset FmtOutputFile, x, y, z
                
        inc insideCount
NEXT:

    inc i ; i++
    JMP L1

DONE:

    ; update actual writing count
    INVOKE fseek, wbFile, 107, 0    
    INVOKE fwrite, ADDR insideCount, TYPE DWORD, 1, wbFile

    ; close files
    INVOKE fclose, rbFile
    INVOKE fclose, wbFile
    INVOKE fclose, wtFile

    ; free memory
    invoke free, bufHeader
    invoke free, bufRecord

    ret
LASProcess endp

end

Compile

In Visual Studio, all three projects are automatically built with correct configuration.

Here is a command line compile batch file to build the static library, test and LAS process.

BAT

cls

echo off

rem compile library "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoPoint.asm /Fo GeoPoint.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoVector.asm /Fo GeoVector.obj     
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoPlane.asm /Fo GeoPlane.obj     
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoPolygon.asm /Fo GeoPolygon.obj     
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoFace.asm /Fo GeoFace.obj     
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\GeoPolygonProc.asm /Fo GeoPolygonProc.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\ListGeoProc.asm /Fo ListGeoProc.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\List.asm /Fo List.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\src\ListUtility.asm /Fo ListUtility.obj

rem build library "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\lib.exe" /subsystem:console ^
        /out:.\lib\GeoProc.lib ^
        GeoPoint.obj GeoVector.obj GeoPlane.obj GeoPolygon.obj GeoFace.obj GeoPolygonProc.obj ^
        ListGeoProc.obj List.obj ListUtility.obj

rem compile test "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\ListTest.asm /Fo ListTest.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\GeoProcTest.asm /Fo GeoProcTest.obj
                                                    
rem build test                                                     "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\link.exe" /out:GeoProcTest.exe ^
        /libpath:.\lib GeoProc.lib ^
        /libpath:"C:\Program Files\Microsoft Visual Studio 10.0\VC\lib" msvcrt.lib ^
        GeoProcTest.obj ListTest.obj
                                        
rem compile LASProc     "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
                                          /c .\LASGeoProc.asm /Fo LASGeoProc.obj
                                                    
rem build LASProc                                                     "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\link.exe" /out:LASGeoProc.exe ^
            /libpath:.\lib GeoProc.lib ^
            /libpath:"C:\Program Files\Microsoft Visual Studio 10.0\VC\lib" msvcrt.lib ^
            LASGeoProc.obj                                                    
                                                    
del *.obj

Before running this ccm.bat, either running a complete VC++ vcvars32.bat, or running a minimum version vcDevEnv.bat to set up VC++ development environment in command line like this:

BAT

echo off

set path=C:\Program Files\Microsoft Visual Studio 10.0\Common7\IDE;%path%
set include=C:\Program Files\Microsoft Visual Studio 10.0\VC\INCLUDE;
            C:\Program Files\Microsoft SDKs\Windows\v7.0A\include;%include%
set lib=C:\Program Files\Microsoft Visual Studio 10.0\VC\LIB;
        C:\Program Files\Microsoft SDKs\Windows\v7.0A\lib;
set libpath=C:\Program Files\Microsoft Visual Studio 10.0\VC\LIB;%libpath%

History

3^rd March, 2016
- Initial version
4^th March, 2016
- Second version
- Completed PushFace method

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)