Point Inside 3D Convex Polygon in MASM Assembly
5.00/5 (3 votes)
An algorithm to determine if a point is inside a 3D convex polygon for a given polygon vertices in MASM Assembly
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.
.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:
...
PFILE TYPEDEF PTR FILE
...
PDWORD TYPEDEF PTR DWORD
...
PListPlane TYPEDEF PTR ListPlane
...
Macros
Here is a sample:
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
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.
; 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.
; 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.
; 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
ListPoint STRUCT
p PGeoPoint ? ; pointer to beginning address of the list
n DWORD 0 ; count of elements, initialize with default 0
ListPoint ENDS
ListPlane
ListPlane STRUCT
p PGeoPlane ? ; pointer to beginning address of the list
n DWORD 0 ; count of elements, initialize with default 0
ListPlane ENDS
PushPoint
; 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
; 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
; 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
GeoPoint STRUCT
x REAL8 0.0
y REAL8 0.0
z REAL8 0.0
GeoPoint ENDS
Here is the main part of GeoPoint.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
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:
; 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
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:
; 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
GeoPolygon STRUCT
ptsAddr PGeoPoint ?
n DWORD 0 ; actual number of polygon vertices
GeoPolygon ENDS
Here is the main part of GeoPolygon.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
GeoFace STRUCT
ptsAddr PGeoPoint ?
idxAddr PDWORD ?
n DWORD 0 ; actual number of face vertices
GeoFace ENDS
Here is the main part of GeoFace.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:
.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.
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:
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:
; 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:
.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.
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:
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
- 3rd March, 2016
- Initial version
- 4th March, 2016
- Second version
- Completed
PushFacemethod